CSC161 2010F, Class 46: Hash Tables Lab

Overview:
* Unit Tests, Revisited.
* Review of intended structure.
* malloc and free.
* Code Reading.
* Lab.

Admin:
* No HW9.
* No HW10.
* Exam distributed Wednesday.
* EC for the Con Brio - Anti-Wooden-Trains concert at 9:30 tonight in Rotunda
* YES WE HAVE CLASS ON TUESDAY!
  * No you don't have reading.
* YES WE HAVE CLASS ON WEDNESDAY!
  If AW's brother misses class on Wednesday, he has a special extra class 
  on Friday.
* Gruesome tales from the history of CS:
  Always mount a scratch monkey!

Review of intented structure
* See picture on real whiteboard
* Insert, version 1:
  Find the cell corresponding to the key
  If there's nothing there, 
    Add a new element with appropriate key/value pair
* Lookup, version 1 (and final version)
  Find the cell corresponding to the key
  * If there's nothing there ... return NULL
  * If there's something there, see if the key matches
    If so, return the value
  * If not, look at the "next" element 
    * If there's nothing there ... return NULL
    * If there's something there, see if the key matches
      If so, return the value
    * If not, look at the "next" element 
* Insert, version 2
  Find the cell corresponding to the key
  If there's nothing there, 
    Add a new element with appropriate key/value pair
  If there's something there,
    Check to see if the key matches
    If so, replace the value
    If not, Go on to the next element
    [And do the same stuff again]

One big issue: We create new "things" in this code
* New arrays of unknown initial size (table->contents)
* New elements (each time we add a new key/value pair)
* New copies of strings (each time we add a new key/value pair)

How do we allocate new memory in C?
* malloc (size) gives you size bytes of memory (or NULL if it can't
  allocate)
* Given a particular type of value, you can find out how many bytes
  it needs with sizeof(TYPE)
  * "I need an array of 25 ints."
  * int *arr;
  * arr = malloc (25 * sizeof(int));
* strdup(str) allocates memory for a duplicate of str.
* malloc comes from stdlib.h
* sizeof is standard C and does not need a library.  
* You can't keep allocating memory - You will eventually run out.
  * You must free things that you are no longer using