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 mistakesmemcpy
/memmove
are functions that let us copy around arbitrary bytes from one location to another.memcpy
does not support overlapping src/destination memory regions, whilememmove
does.- We can use pointer arithmetic plus casting to
char *
to do pointer arithmetic with avoid *
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
- 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 Cabs()
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 sizenbytes
?
(char *)arr + i * nbytes
- What is the
void*
passed as the first argument tobsearch
? What is thevoid*
thatbsearch
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 achar *
. This is why the code works with the special comparison function, as that one doesn't dereference thevoid *
parameter twice for the key's first character, but does dereference thevoid *
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, andvoid*
pointers by definition do not define a pointee type. For this reason, we must casevoid*
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 tobsearch
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
.