Post-task self check

Written by Julie Zelenski

As you vanquish each CS107 assignment and lab, a little celebration is definitely in order, but once the excitement dies down, take a moment to reflect on how far you've come and what new knowledge and skills you have to take forward. To help you gauge your progress, for each assignment/lab, we identify some of its takeaways and offer a few thought questions you can use as a self-check on your post-task understanding. If you find the responses don't come easily, it may be a sign a little extra review is warranted. These questions are not to be handed in or graded. You're encouraged to freely discuss these with your peers and course staff to solidify any gaps in you understanding before moving on from a task. They could also be useful as review before the exams.

Assign0: Unix

You now have your environment configured and should be starting to feel comfortable with the command-line interface, can navigate the filesystem, edit files, and generally get around in unix. Off to a great start!

• Identify a few different techniques to avoid painstakingly typing the entirety of long command you want to execute?
• How do you copy and paste in your chosen editor?
• What is the difference between commit and submit?

Lab1: Tools and debugging

You should now feel acquainted with basic use of tools such as make, gdb, sanitycheck, and Valgrind. You've also been getting into a testing mindset, developing testing strategies, and done a little wrangling with C-strings. All of these skills are very helpful for assignment 1!

• Consider this excerpt from mywc.c that shows an idiomatic loop to read a file line-by-line:

  char line[MAX_LINE_LEN];
  
  while (fgets(line, sizeof(line), fp) != NULL) {
      int len = strlen(line);
      if (line[len-1] == '\n') line[len-1] = '\0';
      ...
  

  Explain how this code operates. If the file does not end with a newline, what happens to this code when reading the last line? What is the behavior if the next line to be read is 1000 characters and MAX_LINE_LEN is only 500? Does it raise an error, crash, truncate the line, or ...? Where could you look to find details about fgets if you aren't sure what it does in this situation?

• When do you supply the command-line arguments to a program you wish to run under gdb: when starting gdb or from within gdb when running the program?

• How do you customize the tests used by sanity check?
• Which is the bigger problem: memory errors or memory leaks? Why? How can you tell which is which in a Valgrind report?

Assign1: Unix utilities

Congrats on your first complete C programs! This was great practice with C-strings, strxxx functions, use of tools, software testing, and a little refresher on recursion to boot. At the end of the quarter, many students recall this first assignment as one of the tougher ones -- not so much due to code/algorithm complexity, but because of the effort needed to become comfortable with the new tools/environment and find your way through the sparse, unforgiving world of C. Celebrate this important milestone and remember the investment you make now in gaining proficiency will pay off throughout the quarter.

• What is the benefit/downside of having . (the current directory) in your PATH?
• In which situations does a call to strncpy null-terminate the destination string and in which does it not? What are some of the consequences that result from using a string that is not properly null-terminated?
• Write an expression that reports whether a given char* has a matching prefix/suffix N chars long. What would happen if your expression were evaluated with a value for N that was longer the string's length?
• In the original starter code, the function search() took two arguments of type const char * and a third of type const char **. Explain the purpose of the extra level of indirection on that third argument.
• The standard C library has a atoi() function that converts a string of digits to a decimal, but no standard function that converts in reverse. Describe a technique could you use to convert a number to a string equivalent.
• How can you gauge whether your program has acceptable performance in terms of runtime or memory efficiency?

Lab2: Arrays and pointers

You should be continuing to build up your gdb and Valgrind repertoire and becoming comfortable with thinking about and manipulating memory/pointers in terms of raw bytes and addresses. Arrays and pointers are ubiquitous in C and a good understanding of them is essential.

• Although & applied to the name of a stack-allocated array (e.g. &buffer) is a legal and well-defined expression, it isn't really sensible. Explain why such use is a sure sign of an error/misunderstanding on the part of the programmer.
• Why must the caller catch the return value from realloc? Why doesn't realloc just re-assign the pointer when it's necessary to move the memory block?
• A Valgrind report complains that Address 0x420d50 is 0 bytes after a block of size 24 alloc'd . Your roommate insists Valgrind is off-base and paranoid because the program runs just fine. Explain to them why accessing memory "0 bytes after" is an actual problem, even though it might be asymptomatic in some contexts.
• Explain how to use lfind with an appropriate callback to re-implement the functionality of strlen.

Assign2: Void* client

All these gyrations with CMap/CVector were to bring about a rock-solid understanding of the client use of a void* interface. The critical mastery is correctly passing/receiving the void*s flying around: what level of indirection to use, what typecasts are needed, using * and & in exactly and only the necessary places. You should know without question how to determine the necessary level of indirection and correctly apply it. It's also valuable to understand and be able to reason through the consequences of getting it wrong.

• What is the purpose of the realloc function? What happens if you attempt to realloc a string that wasn't malloc'ed in the first place?
• The fragment-reading code employs the idiom of using maximum-sized storage on stack temporarily and copying to persistent right-sized dynamic memory. Explain why this technique is necessary/appropriate given the characteristics of the stack and heap.
• The CVector and regular C array fill similar needs. What CVector features make it more client-friendly than direct use of a raw C array? In what ways can the CVector be more difficult to use correctly than an array?
• Explain how ownership of memory works when storing a key/value pair into a CMap. The key passed to cmap_put is a char* -- where does it point to? is allocation required? who allocates it? is the pointer itself copied or its contents (the pointee)? will memory need to be freed? who will free it? What are the answers to those same questions for the void* value passed to cmap_put?
• The client can create a collection to store elements of any desired type, whether it be int, bool, struct, or pointers to any type. In which situations is it appropriate for the element to be a pointer type? What extra precautions need to be taken by the client when storing elements of pointer type?
• The stdlib function free matches the prototype for the cleanup client callback used by CVector/CMap. However it is never the right function to use as a cleanup fn. Explain why not.
• The original version of searchdir stored a char array as the CVector element. Your revised version stores a char* instead. Although arrays and pointers have a kind of equivalence in certain contexts, this is not the case here. Explain/diagram the differences between the two designs and the effect is has on the storage used and code needed.

Lab3: Bits, bytes, and ints

Now with command of the bitwise operators and understanding of masks, you can access and manipulate bits. Be sure to have a solid grasp on the representation of unsigned values as a binary polynomial and signed values in two's complement and be comfortable relating bitwise tweaks to changes in numeric value. Know what happens on assignment between integer family types of different bitwidths and signed-ness.

• Explain the difference between memcpy and memmove and when to use each.
• What are the three modifiers to gdb's x command? Show the x command to print a 2-member array of 4-byte integers in hex and again to print that same memory as 8 single-byte characters.
• Write an expression to create the integer bit mask that has all ones in the N most significant bits and zeros elsewhere.
• How can you determine if an integer bit pattern has a pair of consecutive 'on' bits? (Straightforward to do using a loop, but there is also a clever single expression...)
• Consider rounding the magnitude of an integer up to power of two (e.g. 3 rounds to 4, 4 to 4, 5 to 8, for negative: -3 rounds to -4, -4 to -4, and so on). What changes do you make to the bit pattern of a positive int to round to power of two? What about for a negative int?
• The argument to malloc is size_t (unsigned). Consider the erroneous call malloc(-1), which seems to make no sense at all. What happens when you try to compile such a call? What happens when it executes?

Assign3: Void* implementation

You are now unstoppable in terms of manipulating raw memory. You know how to use the type system to your advantage wherever you can, but also how to work without it where you must. You know the care required to make a proper call to memcpy/memmove, exactly where and why you need a typecast, and have increased vigilant about using the correct level of indirection.

• Why is it so beneficial to decompose the common expressions from CVector/CMap into shared helper functions rather than repeat code?
• Why must you typecast a void* in a pointer-arithmetic expression?
• Setting each field of a CMap cell (next, key, value) is best done with its own specific technique: next as assignment with typecast, key with strcpy, value using memcpy. What's the difference between those options? What makes one technique more appropriate than the others in a given situation?
• How does cvec_next use the previous to orient itself within the iteration? What happens if the client passes an invalid pointer for previous? How about for cmap_next? Would it be possible to reliably detect/assert that the client has passed an invalid pointer? Why or why not?