Recitation 19

Recitation 19: Intro to C

Generic Sort and Function Pointers:

The hardest part about function pointers is usually just the syntax. I think I made things a little more confusing today by showing the typedef first when it should have been last. Try reasoning over the commented out lines in sort.h and convince yourself that they are all saying the same thing. A useful tool making sense of long type statements is cdecl.org. Then, when you take a look at the typedef, it's often useful to work backwards. For example, when I have typedef struct queue_header* queue; I could say that "I'm defining a type queue and when I dereference it I get a struct queue_header." Similarly, for typedef int (*compare_fun)(elem e1, elem e2); I could say that "I'm defining a type called compare_fun and when I dereference it, I get a function of return type int that takes in two arguments of type elem.".

As an example of when this might be useful, there's a C library with a builtin quicksort function. At a terminal, type man qsort. The function is defined as:

  void qsort(void *base, size_t nmemb, size_t size,
                  int(*compar)(const void *, const void *));

To use it, the function needs to know how to compare two things, so you have to give it a function pointer, very much like in our selection sort example.

As an exercise, try writing a compare function for something other than the strings or ints example already shown. Pay close attention to how function types and casting is used.

Strings:

These are the examples using strings from today. Note that the first two both highlight memory problems. In the first one, the program doesn't seem to run into any problems, since it prints out the correct result, but we actually have out of bounds memory access. In the second one, the error is more apparent. The third file is the string concatenation example we wrote together, mixed with the evil version I wrote.

Strings in C are quite a bit different in than in C0. Well, strings don't really exist in C. We have arrays of characters. These arrays are special because the end in a NULL terminator, represented as '\0'. So, if we wanted to print a char array, the program would read characters until hitting this NULL terminator. We need to explicitly manage this NULL terminator. This has many consequences. Suppose I want to store the string "abc" in a char array. Well, I need to allocate 4 bytes--one extra for the NULL terminator. Also, if you lose the NULL terminator, bad things will happen (as shown in strncpy_fail.c).

Memory Allocation:

We'll get to memory management next week, but for now, we can still talk about memory allocation. In C0, we're used to calling either alloc or alloc_array. In C, we have malloc and calloc. They are defined as:

  void *calloc(size_t nmemb, size_t size);
  void *malloc(size_t size);

Despite visual similarities (pattern matching tricks us), don't equate malloc with alloc and calloc with alloc_array. The only difference between the two is that calloc sets all memory to 0 before giving it to you, like C0 does. Since values of 0 have a meaning in some sense for all types, this can be useful. So, it probably sounds like you should always use calloc. Not so fast! Setting everything to 0 is expensive. If you're just going to immediately overwrite that memory with your data, then there's no sense in zeroing it first. When I say that memory from malloc is not zeroed, this might mean that you're getting memory that your program used previously, but was finished with. So, the old data is still there. So, just because calloc has two arguments and malloc one, doesn't mean that calloc is for arrays and malloc everything else. To further drive home the point, you could write calloc as follows: multiply the two arguments together, call malloc, loop of the memory and zero it, return.

The other important thing is what the arguments actually are. All are of type size_t. This is an unsigned integer, but it may have a different number of bytes than the usual int type. By definition, it's the maximum size any object is allowed to be. So, we're asking for an integral number of bytes, not a type name like in C0. To help with this, we use the sizeof function that takes in a type and tells us how big it is. Suppose I want to allocate an array of 10 ints. I could do the following:

  malloc(10 * sizeof(int));
  calloc(10, sizeof(int));

Don't just say, "well, I know how big an int is" and hardcode 4. The truth is that some types will change their size depending on the platform. For example, a long int is 8 bytes on a 64 bit system and 4 bytes on a 32 bit system.

Other Examples:

These are some examples I made last semester for the intro to C, with some new additions. Some of these I showed today. Due to changes in the schedule, I'm not sure I'll get to the rest. So, I highly recommend going through these. I have a suggested order to do so in README.txt. They are heavily commented and hopefully explain what's going on sufficiently. Most of them highlight new things that we didn't have in C0 or behavior that was defined in C0 that is undefined in C. While poking fun at weird things C does is rather amusing, there's also a lot of educational value to understanding why these things happen, especially when you're debugging.

That being said, don't feel responsible for everything in them. We're throwing a lot all at once--the transition to C is pretty crazy. Hopefully you can appreciate why we've been using C0 up until this point--so that we wouldn't have to worry about all of this from day 1. Topics that are important will be revisited, so don't feel like you need to learn everything there is about C on your own. In particular, I didn't get to macros today. That's definitely important will be revisited on Wednesday next week.

If you have any comments or see any errors, please let me know.