Setup

Register for the project using the registration tool and clone the repository as explained in the setup instructions.

You MUST work solo on this project! You may not collaborate at all with anyone else! Please use the SSH link found at the picture after clicking the link in the registration email:

Introduction

In webserver01, we implemented a dictionary that uses a linked list to support retrieval of values given a key. However, in the future, we may want our dictionary to be sorted, or to use non-char * strings and values, or to use a different backing data structure. In these cases, we want to be able to interact with our dictionary without being tied to the specific methods defined by our ll_map_t implementation. To resolve this, we will perform generification on our dictionary, where we will define an interface that all dictionaries must abide by, and then allow the individual implementations of the dictionary to add instance variables and other public methods on top of this interface. We’ve seen this idea in CS 2 already: whenever we needed to access a dictionary in Java, we could use the Map interface if we didn’t care how the dictionary was implemented. One of our goals for this project is to port this idea over to C. Here, our public interface for the dictionary will contain the following methods that we believe all dictionaries should perform:

• A method to free the dictionary
• A method that returns the size of the dictionary
• A method that puts a (key, value) pair into a dictionary
• A method that gets a value from the dictionary given a key
• A method that removes a key from a dictionary
• A method that returns all keys from a dictionary

Outside of requiring these methods, we don’t constrain down the dictionaries any further: their keys and values can be any type we want, they can support any additional methods they want, and they can store any hidden data that we want. As long as our public methods are all supported, any type of dictionary will fit into our interface.

Interfaces, in C

In an interface, we have some function headers that state what an implementation can do. For example, a dictionary can have key-value pairs added (dict_put) or retrieved (dict_get), among other things. One of the strengths of interfaces is that a client does not need to choose a specific implementation. If we write a function that takes dict_t * as an argument, a client can pass in any kind of dictionary! However, different implementations of an interface will need to store different data, as well as different specific functions (for example, a linked list has no need for a hash function). Additionally, each instance of a generic dictionary may have different freeing needs. So how do we accomplish this, while still having a unified interface in one type? We can extend our use of void * and function pointers, with a little bit of casting magic.

First, note the dict_t struct in include/dict.h. Here, we declare all the functions that a dictionary must implement, and require that an instance of the struct provide function pointers to implementations. We also have two other fields: map_impl (a generic pointer to instance-specific data), and funcs (an array of instance-specific function pointers). We declare an instance of this struct in library/ll.c, as _ll_base. This instance is static. In C, the static keyword means that this global function or variable is “seen” only in the file in which it’s declared, similar to “private” in Java.

Still in ll.c, the ll_init function is our linked list constructor. It takes one argument, a ll_funcs_t struct that contains functions specific to this particular linked list instance (see include/ll.h). We call dict_init with the following arguments:

• A struct that declares the mapping of dict_t interface functions to specific linked list implementations.

• _ll_init, an initializing function (_ll_init). This is prefixed with an underscore to indicate that it’s for internal use. It’s also not yet implemented.

• (function_t *)&funcs (the provided argument), re-interpreted as an array of function_t, which is a generic function pointer (include/dict.h). We will discuss this operation further below.

• sizeof(ll_funcs_t)

So what’s happening with funcs and the sizeof here – we’re casting it to a totally different type, how is this valid? Looking back at the ll_funcs_t definition, note the “__attribute__((packed))”. This is an “attribute” that guarantees that each field of the struct is directly adjacent in memory. Since every field is a (function) pointer, we know that the packed memory layout of ll_funcs_t is equivalent to an array of function pointers. Thus, this cast is valid! Because the pointer doesn’t preserve the struct size, we also pass the number of bytes in the array as the last argument. (Why might struct fields not be adjacent? The compiler might insert padding bytes for “alignment”, which is out of scope for this course.)

Looking inside dict_init, a few things happen:

• Create a new dict_t by mallocing, but for a larger size than usual. This is because the function_t *funcs[]; field in dict_t is a “flexible array member”. Since different dictionaries may need different numbers of instance-specific functions, we need a way to represent this. While we could make it an allocation, we’d like to avoid doing that. A flexible array allows marking the “header” of a variable-length object, such as an array of unspecified length! We know show many bytes we need for funcs from the funcs_size argument, so we just add that many.

• Copy the function pointers from template into the new dict_t.

• Call init() to get the state for this particular implementation of a dictionary interface.

• Copy functions into the flexible-length array funcs.

Generifying ll_map_t

In order to get ourselves comfortable with the new dictionary interface, we’re going to convert our linked list dictionary from webserver01 to use our new interface. However, as we make this change, there are a couple of things we should keep in mind:

• Since our dictionary interface now allows the keys and values to be any type, we will need special functions to handle key comparison as well as key and value freeing. These functions have been loaded into ll_funcs; anytime we wish to perform one of these operations, we should cast the funcs array to a ll_funcs_t *, and call the function directly through that pointer.

• Our implementation of get_keys() will need to change slightly from before. In our original implementation, ll_get_keys() created a copy of the keys and returned them in a new string array. However, now that we’re working with a generic type for keys, copying is no longer necessarily supported. As a result, our new get_keys() function will return pointers to the keys stored in our linked list nodes.

  • It is important to note that in this new implementation, since we are providing pointers to internal memory (or memory that is still owned by the nodes), it is not necessarily the case that the data that the pointers correspond to will be valid after we make any modification to our map. Therefore, making any change to the linked list may invalidate the pointers returned by get_keys(). For example, after calling ll_remove(), the key that was removed will have been freed, and the pointer in the returned key array will now be dangling.

With these changes in mind, we are ready to implement our linked list using the new dictionary interface:

Fixed-Size Hashmap

We will now use our dictionary interface to support another type of dictionary: hash tables! In this project, we will implement a linear-probing hash table, just like the one we discussed in lecture. As with our linked list implementation, we will need to support each of six methods implemented in the public interface. Here are some things to keep in mind as you implement the hash table:

• Just like the linked list dictionary, our hash table needs to support arbitrary key and value types. As a result, the functions for checking key equality as well as key and value freeing have been provided in hashtable_funcs_t. Additionally, since we’re implementing a hash table, there’s also a new function, key_hash, which returns the hash of a key. We can call these functions similarly to how we called them for our linked list.

• In this week’s project, we will be implementing a fixed-size hash table. As a result, we will not need to support resizing or rehashing in this project. (We will implement those functions next week!)

Other than these constraints, we will leave the design of the hash table up to you. As long as you have implemented a linear-probing hash table that correctly supports the public interface we’ve provided, you may design the internal structure and helper functions of the hash table however you’d like.

Once you’ve implemented both the linked list and hash table dictionaries, run make test to run all the tests.