README.html


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

Unlike in Java or Python, C has a very limited standard library which lacks general collections/data structures. This means that, if you need a particular structure, you'll need to either include an external library, or implement it yourself. In this project, you'll write a very useful data structure called a hash map, which will be useful to you in future assignments. As a starting point, download and extract this tarball. It includes the following basic directory structure,
.
|-- include
|   |-- hashfuncs.h
|   `-- strmap.h
|-- src
|   `-- strmap.c
`-- tests
    `-- strmap_tests.c

The interfaces that you must implement are defined in include/strmap.h. DO NOT EDIT THIS FILE. You should implement this functions, along with any internal helper functions or structures you may want to add, in src/strmap.c. I've provided a suite of unit tests to verify the functionality of your data structure in tests/strmap_tests.c. DO NOT EDIT THIS FILE either.
Specific Tasks
For this project, you must complete the following tasks

    Implement the required functions in src/strmap.c
    Create a Makefile which builds a static library, lib/libmap.a, and builds the unit test program in bin/strmap-tests
    Ensure that all unit tests pass

Submission
Create a tarball containing the following files,
project-1
|-- Makefile
|-- include
|   |-- hashfuncs.h
|   `-- strmap.h
|-- src
|   `-- strmap.c
`-- tests
    `-- strmap_tests.c

and upload it to Canvas by the deadline. Do not alter the provided include or unit test files.
Tips and Advice

    Make sure that any functions or globals that should be internal to your library (private helpers, etc.) are defined as static. Anything in the global namespace of src/strmap.c that is not static should be defined in the header.
    I've provided two different hash functions for your use. The first one, hash_key is a generally appropriate hash function that you'd actually use in a real map. The second, test_hash will only map elements into the first three buckets of the hash table, regardless of how many buckets there are. It is provided to force hash collisions in an easy to predict manner for testing and debugging purposes.
    There's no requirement for the hash table to resize. You can allocate it to a single, static number of buckets and run with it. Just understand that fixed-size hash tables will see large performance degradation as the number of records within them grows. If you'd like, you can implement dynamic resizing similarly to how you would implement a dynamic array. If you do so, remember to rehash every element within the map.
    Make sure that you handle memory allocation failures. I will be overriding your default malloc with one that lets me inject failures to test your error handling.
    Ensure that allocated memory is eventually freed, even on error paths. I will be testing with induced allocation failures and memory instrumentation to search for memory leaks even on error handling paths. 
    In order to compile the unit tests, you will need to link in the unit test library, and include pthreads. The flags for this are,
        
            -lcheck
            -pthread
        
    

Errata

    Some compilers might not like the approach I initially used to suppress unused parameter warnings in include/hashfuncs.h. If you have problems, try applying this patch. It doesn't change anything materially--just switches over to an older technique for suppressing these warnings with better compatibility. [9/4/2025]