Assigned: Tuesday, Mar 1, 2016
Due: Monday, Mar 7, 2016 at 10:30pm
Collaboration: Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted.
In this lab, you will implement four different abstract data types that support concurrent access by multiple threads and write tests to verify that your data structures work correctly under concurrent modification. You will implement a stack, queue, and associative array. You will then test these implementations using the Google Test framework.
The starter code for this lab is available at github.com/grinnell-cs/213-data-structures. Follow the usual procedures for forking and adding your partner as a collaborator.
As you likely remember from CSC 161, a stack is a simple data structure that supports two operations: adding items to the top, and removing items from the top. Implement a thread-safe stack with the following interface:
my_stack_t
This type holds all of the information you need to access a stack. It should probably be defined as a struct. As a user of your stack implementation, I should not need to know what is inside this struct.
my_stack_t* stack_create()
This function takes no parameters, and returns a my_stack_t* that contains no elements.
void stack_destroy(my_stack_t* stack)
This function takes a my_stack_t and destroys it. This should free any allocated memory associated with the given my_stack_t*. It is not safe to do anything with the my_stack_t* after it has been passed to this function.
void stack_push(my_stack_t* stack, const char* element)
Push a string onto the stack. The provided my_stack_t* must have been created with stack_create, and must not have been passed to stack_destroy. If the string parameter is NULL, it should not be pushed onto the stack.
const char* stack_pop(my_stack_t* stack)
Pop a string off of the stack. The provided my_stack_t* must have been created with stack_create, and mus tnot have been passed to stack_destroy. If the stack is empty, stack_pop should return NULL. If the stack is not empty, the string on the top of the stack should be removed from the stack and returned.
You are free to choose any implementation method you like for your stack, but you may not assume an upper limit on the number of elements that will be in the stack. That means a static-size array will not work for your stack.
You must also make your stack reentrant; it must be possible to have two or more independent stacks that can be pushed and popped independently. This means no global variables in your stack implementation.
Multiple threads may access the same stack at the same time, so you will need to use synchronization inside your stack implementation to maintain the integrity of this data structure. When we think about data structures, it is often helpful to write down invariants—statements that must always be true about the data structure. Your synchronization for the stack data structure must maintain the following invariants:
Invariant 1: For every value V that has been pushed onto the stack p times and returned by pop q times, there must be p-q copies of this value on the stack.
Invariant 2: No value should ever be returned by pop if it was not first passed to push.
Invariant 3: If a thread pushes value A and then pushes value B, and no other thread pushes these specific values, A must not be popped from the stack before popping B.
Invariant 1 describes the basic requirements for most reasonable data structures: items that are added to the data structure but not removed should still be contained in the data structure. There cannot be a negative number of copies of a value on the stack, so this also implies that a value should never be returned from pop more times than it has been pushed.
Invariant 2 just says the stack is not allowed to “generate” new values that were never added to the stack. This is another reasonable requirement for most data structures.
Invariant 3 is specific to stacks: it restricts the order in which pop may return values, based on the order these values are pushed. This invariant says nothing about the order of pushes and pops between threads: If two threads are pushing onto the stack simultaneously, both values should end up on the stack in some order. If one thread pushes a value while the other thread pops a value, the popping thread could receive the old or new top value from the stack.
You will use the Google Test framework to test your data structure implementations in this lab.
The file partA/tests.cc, included in the starter code, has one example test. You can create as many test cases as you would like in tests.cc. Running the partA executable or typing make test anywhere in the project will run your tests and report the results.
The provided test code uses ASSERT_EQ to require that two values are equal, and ASSERT_NE to require that two values are not equal.
When comparing strings, make sure to use ASSERT_STREQ and ASSERT_STRNE.
You can find simple test guidance on the Google Test Primer, and a complete list of comparisons on the Advanced Guide.
Because our data structure implementations are designed to be concurrent, you will need to test accesses to your data structure using multiple threads. One common strategy is to create a few threads, have them issue many accesses to a data structure for a long enough time that they are bound to overlap, then check the consistency of the data structure at the end.
For example, we might want to test the second invariant, that stacks cannot “generate” values, as follows:
"A"s, "B"s, and "C"s to the stack.ASSERT_EQ to check that the number of "A"s matches the number of times each thread pushed "A" times the number of threads, and so on for "B" and "C".You may need several tests like this to completely cover your invariants. Thread interactions are difficult to control, so an improperly-synchronized data structure may sometimes pass all of its tests. If you make your tests run longer, with enough concurrent accesses, you are more likely to catch an error.
Your grade for this part of the lab will depend on several factors:
Like a stack, a queue has a very simple interface. However, a queue returns elements in the order they were added to the queue, not the reverse. These data structures are often described with the acronyms LIFO (last in, first out) and FIFO (first in, first out) for stacks and queues, respectively. Your queue should implement the following interface:
my_queue_t
This type holds all of the information you need to access a queue. It should probably be defined as a struct. As a user of your queue implementation, I should not need to know what is inside this struct.
my_queue_t* queue_create()
This function takes no parameters, and returns an empty queue.
void queue_destroy(my_queue_t* queue)
This function takes a my_queue_t* and destroys it. This should free any allocated memory associated with the given queue. It is not safe to do anything with the my_queue_t* after it has been passed to this function.
void queue_put(my_queue_t* queue, const char* element)
This function takes a queue that was returned from queue_create (and has not been passed to queue_destroy) and a string to add to the queue. It then adds element to the queue unless element is NULL, in which case the function should do nothing.
const char* queue_take(my_queue_t* queue)
This function takes a queue that was returned from queue_create (and has not been passed to queue_destroy), removes the first elemtn in the queue, and returns this element. If the queue is empty, the function should return NULL.
You are free to choose any implementation method you would like for your queue, provided you do not assume any upper bound on the number of elements in the queue. As with your stack implementation, the queue must be reentrant: independent queue can exist simultaneously, so no globals please.
As with your stack, the queue may be accessed simultaneously by multiple threads. Add synchronization to your queue to maintain the data structure’s integrity.
Write invariants for the queue data structure and enforce these invariants using synchronization. You should include your queue invariants in the README.md file in your project. The invariants for the stack data structure may be helpful as you develop your queue invariants.
Use the Google Test framework to test your queue implementation. Make sure your tests adequately check all of the invariants you specify. Remember that thread interactions are difficult to control, so an improperly-synchronized data structure may pass all of its tests. If you make your tests run longer, with enough concurrent accesses, you are more likely to catch an error.
Your grade for this part of the lab will depend on several factors:
One particularly useful abstract datatype is an associative array, also known as a dictionary in python and map in C++ and Java. An associative array works like an array with two major differences: the index into an associative array is not necessarily an integer (we will use strings for this lab), and the “array” does not have a fixed size. We will implement an associative array that stores strings, and also uses strings as indices into the associative array.
To access an associative array, you may get the value with a given key, set a key to a particular value, or remove the entry for a given key.
To keep function names short, we will use the name “dict” for this datatype in the interface below. Your associative array should have the following interface:
my_dict_t
This type holds all of the information required to access a dictionary. It should probably be a struct, but as a user of your data structure implementation I should not need to know anything about this type.
my_dict_t* dict_create()
This function takes no parameters, and returns an empty dictionary.
void dict_destroy(my_dict_t* dict)
This function takes a my_dict_t* and destroys it. This should free any allocated memory associated with the dictionary. It is not safe to do anything with the my_dict_t* after it has been passed to this function.
void dict_set(my_dict_t* dict, const char* key, const char* value)
This function adds or updates an entry in dict. If there is already an entry for key, then its value will be updated. If no entry exists for key, a new one is added.
const char* dict_get(my_dict_t* dict, const char* key)
This function looks up a key in dict. If there is an entry for key, the last value associated with this key is returned. If no matching entry exists, the function returns NULL.
void dict_remove(my_dist_t* dict, const char* key)
This function removes any entry associated with key. If there is no entry for key, this function does nothing.
You are free to choose any implementation method for your associative array, with some reservations. You may not assume any upper bound on the number of elements that will be in a dictionary, your implementation must be re-entrant, and you may not use a linked list to implement the entire dictionary.
Hash tables and binary search trees are both reasonable implementation strategies.
Please describe the implementation approach you are using for your dictionary in README.md, including both the underlying data structure (hash table, binary tree, etc.) and the synchronization strategy you are using.
Multiple threads may access the same dictionary concurrently, and you are required to allow concurrent accesses whenever possible; two calls to get, for example, should not block each other. The exact details of what kinds of accesses can happen in parallel will depend on your implementation. Document the types of accesses that may will block each other in your README.md, along with the data structure invariants that your locking scheme preserves.
Use Google Test to check the invariants you specified for your dictionary data structure. Remember that thread interactions are difficult to control, so an improperly-synchronized data structure may pass all of its tests. If you make your tests run longer, with enough concurrent accesses, you are more likely to catch an error.
You do not need to test whether certain accesses will proceed in parallel or not. This is especially difficult to check with testing, so you will likely need to resort to careful code reading to verify that your synchronization scheme is working.
Your grade for this part of the lab will depend on several factors: