Sorting a binary data file Task Write a C program that reads a file of binary data records as described in the structure description file. The program will obtain the file name as a command line parameter (see below, pg 4). The program will read and print all the records in a binary data file where each record has the format described in filestruct-description.txt. The program will read the input file (parameter 1), storing all the records into a dynamic array in memory. The program should then sort the data records and write the output file (parameter 2) in sorted order. Use the Linux library sort routine qsort to perform the sorting. Your program will need to store all the records in memory in order to sort them. The program will allocate a dynamic array of structs (or some other data structure), and read the data file into the array. You do not know how large the file may be, so you must accommodate different file sizes. Here are two possible approaches 1. Dynamic sized array: Allocate an initial array of some size (e.g. 100 records) and then if (while reading the file) you find that the array is not large enough then use realloc to increase (e.g. double) the size of it. Realloc allocates a new larger array in memory and copies the data from the existing array to the new larger array, before freeing the original array. Repeatedly doubling the size allows you to accommodate arbitrarily large data files without copying the data too many times. See the Unix manual pages for malloc and realloc. 2. Compute the number of records from the file size: This is a systems approach that will require some reading to find out how to achieve. There is a system call stat that can tell you the total number of bytes in a file. There are also other ways to find out how many bytes are in a file but you should NOT read the entire file just to find out how big it is! Your file description gives you the information about how long each record is, so you can compute the number of records in the file from the number of bytes. You can then allocate an array of struct to the exact correct size using malloc. See the Unix manual pages for stat and malloc. After sorting the records, write them out in binary form. It is suggested to use fwrite to write each field individually The output files must exactly match the sample output files provided. In order to complete this task: You must know: Reading and writing binary data files Opening and closing files. Working with pointers to structures. Memory allocation, dynamically sizing an array. Using system library routines (specifically, a system library sort routine). Writing code to compare structures with a lexical sort order. Using a function pointer in C. C language features you may need to know: fwrite system library call to write binary data to a file qsort system library call to sort data Memory allocation, and freeing memory Resources: filestruct-description.txt: ? Describes the members of the C data structure which correspond to fields in the records of the data file. filestruct-sort.txt: ? Specifies the sorting order. input-*.bin: ? Sample binary input files. output-*.bin: ? Sample binary output files corresponding to the input files. ? The output files contain the same data as the input files, but the records are sorted. Lexical Sorting The records are to be sorted according to the values in various fields of the records. The sort order specification lists the fields that should be considered, and for each field it specifies whether that field is sorted in ascending or descending order. If you are familiar with sorting in Excel, this works similarly. For example, consider the following simple text file, shown with line numbers. The first line is the header line that gives the name of each member of the record structure. 1. horse, cat, paper, train 2. 3, word, 1.4, 1 3. 4, wood, 1.4, 1 4. 1, word, 1.7, 0 5. 2, word, 1.5, 0 The final sorted text file is: horse, cat, paper, train 2, word, 1.5, 0 1, word, 1.7, 0 3, word, 1.4, 1 4, wood, 1.4, 1 About the Data File Format The new format input data files will contain the same information as the original format output data files, but the records of the input files are not sorted. The data formats of individual fields can be different in the new data format compared to the original data format. In particular: Numeric fields can be represented as any of the numeric types: signed or unsigned integers in 8, 16 or 32 bits; float or double. Note carefully: This means that an integer type in the original file format may be represented as floating point in the new file format, and also that a float in the original file format may be represented as an integer in the new file format. Booleans can be represented in 8, 16, or 32 bits, or several Boolean fields can be packed into a field of 8 bits each Boolean will occupy a specific bit position in the field. Strings can have a different length and characters can be converted to strings in the new format. In cases where a field has a different numeric type in the new format, we guarantee that the sample data values present in the input and output files will semantically correspond (i.e. they will have the same meaning). For example, if the input file has 16-bit signed integers but the output file has 8-bit unsigned integers then the sample data values for that field will all be positive values in the range 0 to 255, since these values can be represented in both 16-bit signed integers and 8-bit unsigned integers. As another example, if the input file has 8-bit signed integers and the output file has 32-bit unsigned integers, then the data values for that field will all be positive values in the range 0 to 127, since these values can be represented as both 8-bit signed integers and 32-bit unsigned integers.

Attachments:

description.pdf