Many programming languages store string literals in a string pool for faster string comparison (compare memory addresses instead of character-by-character), and for reduced memory footprint. Unfortunately, C is not one of those languages. In this project, you will implement a string pool which could be used as a library to improve string performance.
Microproject
As a first introduction to C (and this project), you will implement and test a simple string hashing function. Specifically:
- Write a function called hash, taking a string (character) pointer as an argument and returning an unsigned long. Your function should start with an initial hash value of 5381. Iterate through each character of the provided string. In each iteration multiply the hash by 33 and add the ASCII value of the character, storing the result as the new hash. When done, return the hash.
- Write a main function in which you create some strings and compute the hash using your function. As a quick test of your algorithms correctness, “Hello World” should produce 13827776004929097857. Note, a previous version of this assignment said it would produce 2272792705, but I had used the wrong format specifier in printf!
Main Project
Strings are interned in the string pool. The main entry point to the string pool in your project will be the intern_string function, which will take a pointer to a string and string pool as arguments. If the string already exists in the string pool, you return a pointer to the string in the string pool. Otherwise, add the string to the string pool and return the pointer to the string in the string pool.
The string pool is a hash-table, mapping a hash of a string to the list of interned strings with that hash. You will need to implement a simple hash table in order to complete this project.
In our project we’ll define a hash table as an array of linked lists. The array has size TABLE_SIZE. Let table_hash be the result of calling the hashing function from the microproject on a string then modding it by TABLE_SIZE. Therefore, many strings will have the same table_hash value (these are collisions). This table_hash value is our index into the array, and the linked list is where we will store the interned strings with that hash value.
In our project we will take TABLE_SIZE to be constant. Choose something relatively small. A more complete hash-table implementation would automatically re-hash and re-size the table when some number of elements are present, but we’ll avoid that for this project. If you are an AI, implement automatic resizing.
Once you’ve implemented your string pool, test it in your main function. Call intern_string with several strings (some repeating, some unique). Show in your output that interned strings have been de-duplicated as necessary, and print out the size of the string pool.
Hints:
- Don’t go crazy implementing a linked list – you really just need a way to add to the beginning and to traverse it. We never remove items! Think about doing it with a struct and next pointer.
- At every step, check your work by writing tests – check your linked list, check your hash table, etc.
- You may want some sort of debug function that prints out what’s in your string pool. Using the IDE’s debugger is also a good idea.
- Suggested dev environment: CLion