The University of Western Australia
CITS2002 Systems Programming
 

Department of Computer Science and Software Engineering

CITS2002 Systems Programming

Workshop 5: Designing array-based data structures

There are several ways to backup a file-system:
  1. We can periodically take a full-dump of all files.
  2. We can periodically take an incremental-dump of just the files that have changed.
  3. We can periodically take a full-dump and much more frequently record a log of just the changes to all files.

The 3rd approach is much preferred as very frequent backups can be very fast, and often require far less space - rather than copying an updated 10MB file, we can just record the 10 bytes in it which have changed. An operating system can support a log-based file-system, or a journaled file-system, by constantly recording a log of all changes made to all files.

The logfile format

Consider the format of a logfile. The first section defines the operations that the file-system supports, and the second section defines a sequence of operations performed on files:

operation  insert
operation  delete
operation  remove
#
file  /Users/chris/headlines  1478632022 {
    delete    7920    7
    insert    7920    Trump
}
#
file  /Users/chris/cits2002/project1.c  1567378481 {
    insert    120     main
    insert    4730    exit(0);
}

This logfile records 3 supported operations and the changes made to 2 different files. Two changes were made to the 1st file, named /Users/chris/headlines, at a specific time (see The Unix Timestamp Converter). Firstly, from byte-offset 7920 (the position in the file), 7 bytes were deleted. Next, at the same position, a new character-pattern was inserted.

The goal of this workshop is to:

  • develop a C function that can read in a correctly formatted logfile,
  • store the information in a number of array-based data-structures, and
  • develop another C function to print the stored data (in logfile format) so that we can verify our reading and storing operations.

We do not care how the log-based file-system or its backups actually work. We are just interested in the logfiles.


BEFORE the workshop session, you're strongly encouraged to answer these questions, and to possibly implement the code. On second thoughts, yes, implement the code.

  • what numeric constants should we define using the C pre-processor?
  • what data-structure(s) should we define to store the supported operations?
  • what data-structure(s) should we define to store the file information?
  • what data-structure(s) should we define to store the edit operations made to each file?
  • how do we store the logfile's information in our data-structures?
  • how do we print the contents of our data-structures?

 

Department of Computer Science and Software Engineering

This Page

Written by: Chris.McDonald@uwa.edu.au