$29
CSCI 247 Computer Systems I Lab 4 : pointers The Objectives of this lab are the following: • C's array/pointer duality • Understand the use of make and makefiles • Casting pointers in C (specifically to and from void*) • Defining, passing, and calling functions by pointer As was the case for labs 1 through 4, ask the TAs lots of questions. They are there to help. And, you CAN work with peers in completing the labs. This is a bit tricky when everybody is remote; you may use slack, email, discord, etc. Up to you. But, in no circumstances should you SHARE code, which involves emailing code and then submitting it as your own. Overview This lab asks you to complete a generic sorting algorithm by adding a third, function parameter to an existing function, and update the two test programs that you are being provided to use your new parameter. The below instructions walk you through the first two parts of this lab: completing the sort_array function and updating sort_strings. Specifics The goal is to develop a general purpose sorting routine, that is capable to sort using any data type. The generalized function is defined in sort.h and implemented in sort.c. Get these functions from /home/jagodzf/public_html/teaching/csci247/labs/lab4 The array to be sorted contains void*s. A void* is simply a pointer to an unknown type. Let's say that I have an array of strings, for example. The actual array is an array of char*s and would look like: Array: +--------+------+------+ | | | | | | | | | | | +----+---+--+---+--+---+ | | | +--------------+ | | +------------------> |Third string\0| | | +--------------+ | | +---------------+ | +-------------------------> |Second string\0| | +---------------+ | +--------------+ +--------------------------------> |First string\0| +--------------+ Page 2 CSCI 247, Lab 4 Filip Jagodzinski, Summer 2020 The array has size 3, but each string has a different length. For the most part, we don't care what the pointers point at. Here is the problem: we care what the pointers point at regarding ordering. The only way I can compare void*s is by where they point in memory. This is not helpful. Pointers into the .text section would sort before .data or the stack. I need a generic way to compare two unknown data types. Consider the example above: an array of strings. I could add a compare-function for strings in sort.c. This function would look something like this: static int ordered_strings (void* left, void* right) { char* left_string = (char*) left; char* right_string= (char*) right; return strcmp (left_string, right_string) < 0; } All this function does is cast the void*s to char*s. We happen to know that this is correct in this example. The actual comparison is performed by the C-library function strcmp. The test in sort_array needs updating. Currently, the test looks like this: if ( Array[i] < Array[i+1] ) { swap(&Array[i], &Array[i+1]); have_swapped = 1; } See how it compares the addresses? For strings, the test would look like this: if ( ordered_strings (Array[i], Array[i+1]) ) { swap(&Array[i], &Array[i+1]); have_swapped = 1; } This will work for strings, but defeats the goal; this is not a generic sorting function. Instead of adding every possible ordering of every data type to sort_array, we can pass a comparison function as an argument. Technically we cannot pass a function as an argument, but we can pass a pointer to a function. This syntax, however, is strange. Right now, sort_array looks like this: void sort_array(void* Array[], unsigned size); Page 3 CSCI 247, Lab 4 Filip Jagodzinski, Summer 2020 We need to add a third parameter, let's call it ordered. In C, we usually declare the type followed by the name (e.g., void* Array[], unsigned size, etc.). The name of the function pointer is in the middle and has a weird set of parentheses. The new declaration of sort_array looks like this: void sort_array(void* Array[], unsigned size, int (*ordered)(void*,void*)); See what I mean about the strange syntax! The parentheses around the symbol bind the asterisk to the name rather than to the return type. Otherwise, it would be a function that returns an int*. Using the function is straight-forward. The test now looks like this: if ( ordered(Array[i], Array[i+1]) ) { swap(&Array[i], &Array[i+1]); have_swapped = 1; } We can use the function parameter like any other function, but only within sort_array. Now the caller must provide an array, its size, and a function that determines if the two -- whateverthey-are – are in the correct order. Let's fix sort_strings. Right now, it only passes the first two arguments to sort_array. We need to create the third argument, a function that compares two strings, but we have already done this. However, we put it in the wrong file. Move compare_strings from sort.c to sort_strings.c. Now we can correct the call to sort_array in main: sort_array((void**)data, data_size, &ordered_strings); Makefiles and make Provided in the directory named above is the file Makefile. The utility make is the command-line program which issues compilation instructions that are specified in the file Makefile. The use of a Makefile streamlines the compilation process. Since we have only fixed sort_strings, asking make to build everything would create a bunch of errors. There are many details to using make, which we don’t cover in detail here. For the time being, just know that a Makefile includes variables names, and individual instructions for different pieces of code that you want compiled. In the Readme file that you are given, there are multiple compilation instructions, including all, sort.o, check, etc, and including clean. Each of these is accompanied by instructions of what the compiler should do IF the user invokes that compilation option. We can build just sort_strings with the following make command: $make sort_strings Page 4 CSCI 247, Lab 4 Filip Jagodzinski, Summer 2020 What does clean do? And all? Ask your TA! Hint : issue make clean, look at the directory structure, and then issue make sort_strings, and look at the directory. What has changed? And we can use sort_strings to test: $./sort_strings "rodeo" and "reading" are out of order "reading" and "polish" are out of order "polish" and "lima" are out of order "lima" and "job" are out of order Hmm, something went wrong. I think we sorted in the wrong direction. One of your tasks is to fix this. The second set of tests is sort_struct. This one is slightly more complicated. Rather than strings, it is an array of pointers to structures. Create an ordering function such that sort_array orders the cars in ascending order or years. What you must do • Finish implementing the generic sort_arrays function • Update sort_strings to sort in alphabetic order • Update sort_structs to sort in increase model year order. Important: Do not modify the for-loop in the main functions. It is there to ensure that the arrays are sorted in the correct order. Rubric and submission Please upload the following files to canvas • sort.c • sort.h • sort_strings.c • sort_structs.c Submit the asked-for files as the Lab 4 Submission item on Canvas. You must submit your file by the due date/time specified on Canvas. Sorting strings correctly 5 points Sorting cars correctly 7points Coding style 3 points 15 points