Lab 4 Solutions

Written by John Louie, with modifications by Nick Troccoli and Lisa Yan

Introduction

What would a callback comparison function that can be passed to qsort look like if we wanted to arrange an array of ints in order of increasing absolute value? (hint - the builtin C abs() function can calculate absolute value).

Answer:

int abs_fn(const void *a, const void *b) {
    return abs(*(int *)a) - abs(*(int *)b);
}

(Side note: this has issues in some cases with INT_MIN since technically abs(INT_MIN) is undefined, though it returns INT_MIN (e.g. if a is INT_MIN and b is 0). To handle that case, we'd want to do an explicit check for INT_MIN. Otherwise, there's no overflow, as positive - positive (same as positive + negative) cannot overflow. The check for INT_MIN would need to make whichever number is INT_MIN come second, since its absolute value by definition would be the largest - e.g. if *a is INT_MIN and *b isn't, return 1. For the reverse, return -1. If both are INT_MIN, return 0.)

Lecture Review

The key goal for lab4 is to provide practice working with generics, including void *, memcpy/memmove, and function pointers. Here are some key concepts relevant to this week's lab:

  • We can use void * to represent a generic pointer to "something"
  • void * loses information about data types - there is less error checking and it is more prone to mistakes
  • memcpy/memmove are functions that let us copy around arbitrary bytes from one location to another. memcpy does not support overlapping src/destination memory regions, while memmove does.
  • We can use pointer arithmetic plus casting to char * to do pointer arithmetic with a void * to advance it by a specific number of bytes.
  • we can pass functions as parameters to other functions by specifying one or more function pointer parameters
  • a function pointer lets us pass logic that the caller has access to to the callee. For instance, we pass a function to bubble_sort that knows how to compare two elements of the type we are sorting.
  • functions with generic operations must always deal with pointers to the data they care about. For instance, comparison functions must cast and dereference their received elements before comparing them.

Solutions

1) void * and Pitfalls

Q1: Look carefully to identify the subtle differences between the compare_strings_alphabetically and compare_letters_alphabetically callbacks. Could you use compare_letters_alphabetically to sort an array of strings by the first letter? Why or why not?

A1: No: compare_letters would treat part of the address of the first character in the string as a character to compare. Not what we want!

Q2: Now it's your turn; try implementing the comparison function compare_strings_by_first_character to sort strings in alphabetical order by their first character. Hint: remember that characters can be compared numerically e.g. A is less than B.

A2: See below:

int compare_strings_by_first_character(const void *a, const void *b) {
    const char *str1 = *(const char **)a;
    const char *str2 = *(const char **)b;
    return str1[0] - str2[0];

    // alternative: return **(const char **)a - **(const char **)b;
}

Q3: Why is there no compile or runtime error from our mistake? How does qsort behave in this case? Drawing memory diagrams and/or tracing in gdb may be very helpful in understanding the behavior.

A3: The compiler and runtime don't know anything funky is going on - they compare bytes as they're told! void * has few provided checks. Valgrind doesn't help either. The character comparison treats each int as a character and compares them, so the reported max is the int with the largest least-significant-byte (because of endianness, the first address of each element really points to its least-significant byte).

2) Debugging: bsearch Bug

Q4: On what operation in the code does it crash? Why? (Hint: try printing out parts of the expression it crashes on in GDB and see what errors out)

A4: Line 15: return **(const char **)p - **(const char **)q;. It crashes when we try to do **(const char **)p because p can't be dereferenced twice.

Q5: What bsearch detail does this code depend on to work? (Hint: what does the first parameter of the comparison function represent? How about the second? Check out the second paragraph of the manual page).

A5: bsearch always passes the key as the first parameter, and the array member as the second parameter, to the comparison function.

Q6: How can we fix the code to make the program work correctly and use the same comparison function compare_first_characters for both sort and search? (Hint: take a closer look at the values of the parameters passed into bsearch when calling it).

A6: The problem is that the key passed into bsearch must be a pointer to what to look for. The code in this program passes in the key itself, which is a char *. This is why the code works with the special comparison function, as that one doesn't dereference the void * parameter twice for the key's first character, but does dereference the void * parameter twice for the array member. Therefore, the fix is to pass in &key as the first parameter.

3) GDB Tip: Printing Arrays

Make sure to try the steps yourself to walk through how to print out an array when being passed to a function; this GDB tip can come in handy on assign4 in particular!

Lab Checkoff Answers

  1. Sketch the code for a callback comparison function that can be passed to qsort to arrange an array of ints in order of increasing absolute value (hint - the builtin C abs() function can calculate absolute value).
int abs_fn(const void *a, const void *b) {
    return abs(*(int *)a) - abs(*(int *)b);
}

(See introduction for a side note about an edge case with INT_MIN)

  • What is the idiomatic expression to access the location of the ith member of a generic array arr with element byte size nbytes?
(char *)arr + i * nbytes
  • What is the void* passed as the first argument to bsearch? What is the void* that bsearch returns? the first argument is a pointer to the key being searched for. The return value is a pointer to the element found, or NULL if no element was found.
  • How can we modify the line of code that calls bsearch to fix the bug? Why does this modification resolve the issue? The fix is to pass in &key as the first parameter. The problem is that the key passed into bsearch must be a pointer to what to look for. The code in this program passes in the key itself, which is a char *. This is why the code works with the special comparison function, as that one doesn't dereference the void * parameter twice for the key's first character, but does dereference the void * parameter twice for the array member. Passing in &key corrects the level of indirection issue.

Lab-End Thought Questions

  • Why must you typecast a void* in a pointer-arithmetic expression? Pointer arithmetic relies on the size of the pointee type, and void* pointers by definition do not define a pointee type. For this reason, we must case void* pointers before performing pointer arithmetic so C knows how big each "hop" is.
  • An asymmetric comparison function is one that casts its two void* arguments to different pointee types. Why is passing an asymmetric comparison function to bsearch almost certainly an indication of programmer error? Both elements being compared should have the same type with the same level of indirection!
  • C search functions commonly return a pointer to the found element (if any), not the found element itself. Why is this? If search functions are generic, they cannot return the found element itself because it could be any size. Instead, it can only return a pointer to the found element, since all pointers are the same size (8 bytes).

[Optional] Extra Problems

memmove

Q1: The function's interface declares its parameters as void* pointers, but internally it manipulates these pointers as char*. Why the inconsistency? What would be the consequence of trying to reconcile the discrepancy by declaring the interface as char* or changing the implementation to use void*?

A1: It casts to char * so we interpret the memory at the source and destination addresses in 1 byte increments. If we made the parameters char *s, then you would have to cast each pointer you pass to memmove as that type. If we used only void * in the implementation, we couldn't dereference it!

Q2: What special case is being handled on line 5?

A2: When src and dst are equal, meaning no copying is needed.

Q3: Review the man pages for memcpy and memmove to understand the differences between these two functions. What special case is being handled on line 9?

A3: This checks whether the memory regions actually overlap. memcpy stipulates that the regions of memory should not overlap, while memmove can handle that case.

Q4: What two cases are being divided by the if/else on Lines 13/17? Why are both cases necessary?

A4: These cases separate out logic for when the sources overlap in different ways. There needs to be special handling because in some cases just copying byte over one by one could overwrite bytes in the source that have not yet been copied over. If the destination comes before the source, then we should copy bytes in order from the start of source. Even if we overwrite a byte in the source while writing to the destination, that byte will have already been copied over earlier. We can't copy bytes in reverse order, because this might overwrite earlier bytes of source that we have not copied over yet. However, if the destination comes after the source, then we need to copy bytes in the reverse order. If we iterated from the first byte and copied there, then we would overwrite a later source byte before copying it over.

Q5: The man page for memmove states that the operation takes place as though it copies the data twice (src->temp, temp->dst), which implies that call to memmove might take twice as long as memcpy. However, the musl implementation doesn't operate in this literal manner. It does correctly handle overlap, but not by copying twice. What does it do instead? Take a look at lines 14-16 and lines 18-20 in particular - what is going on in each of these loops? In this implementation, what then is the expected added cost of using memmove over memcpy?

A5: memmove copies in place! If the destination comes before the source, then we should copy bytes in order from the start of source. Even if we overwrite a byte in the source while writing to the destination, that byte will have already been copied over earlier. We can't copy bytes in reverse order, because this might overwrite earlier bytes of source that we have not copied over yet. However, if the destination comes after the source, then we need to copy bytes in the reverse order. If we iterated from the first byte and copied there, then we would overwrite a later source byte before copying it over. So it's in reality not much more inefficient (if at all) than memcpy. The only difference is using memcpy in your code conveys to the reader that you know the memory regions do not overlap.

Q6: Trace the call musl_memmove(NULL, "cs107", 0). Will it result in a segmentation fault from trying to read/write an invalid pointer? Why or why not? What about the call musl_memmove(NULL, "cs107", -1)? Verify your understanding by running the memmove.c program.

A6: memcpy will correctly handle the call with NULL and "cs107" and n = 0; however, when you pass in -1 the size_t will interpret that as a large unsigned value and crash when trying to dereference NULL.