Part 1 should cause no problems. Parts 2 and 3 are a bit harder. You are to make the database thread-safe. And to help you test your code, you are to add some additional features.
The database consists of a collection of nodes, organized as an unbalanced binary search tree. An empty database consists of a header, pointing to NULL. Otherwise the database contains some number of name-value pairs, each stored in a node. Each node contains two pointers to nodes, a left child and a right child. All names in the nodes in the tree pointed to by a node's left child are lexicographically less than the node's name; all names in the nodes in the tree pointed to by the node's right child are lexicographically greater than the node's name. The database implementation is in db.h and db.c.
The add routine calls search to verify that the node to be added is not present. Search returns in its third argument (an out argument) a pointer to the node that should be the node-to-be-added's parent. Add then creates the new node and connects it to its parent.
Remove is a bit more difficult. It first checks to make sure the node we're deleting exists, by calling search. Search returns a pointer to the node (if it exists) and, in its third argument, a pointer to that node's parent. Let's call the node we're deleting dnode. If it has no children, it is simply deleted and the pointer that referred to it (in its parent) is set to NULL. If it has one null child pointer, then it's also easy: the pointer field that referred to it in its parent is set to point to the non-null child. If both children are non-null, things are a bit tougher.
Consider the subtree headed by dnode's right child. Let's call the node with the lexicographically smallest name in that subtree xnode. This node's name is, however, lexicographically greater than all the names of the nodes in the subtree headed by dnode's left child. Suppose we replace dnode with xnode (i.e., we copy xnode's name and value into dnode and remove xnode from where it was in the right subtree). The resulting tree is well-formed: everything in xnode's left subtree has a name that's lexicographically less than xnode's, and everything in xnode's right subtree has a name that's lexicographically greater than xnode's. Furthermore, since we've gotten rid of dnode, then resulting tree doesn't have dnode in it. So, we reduced the problem of deleting dnode to that of deleting xnode. But, since xnode was the smallest node in the left subtree, it's easy to delete, since it has no left child.
There are two ways to make this code thread-safe. The first is the easiest and is known as coarse-grained locking. We have a single readers-writers lock protecting the entire tree. A thread simply locks the readers-writers lock (read-locking it or write-locking it, as appropriate) before doing an operation and unlocks it afterwards. The more interesting approach is known as fine-grained locking, in which a separate readers-writers lock is associated with each node. Thus only the portion of the database being manipulated is locked.
You are to implement both approaches (first doing coarse-grained locking). Note that the fine-grained approach is fairly difficult. Make certain that your coarse-grained solution works before getting started on the fine-grained solution.
To help you test your code, you should further modify server.c by adding start and stop commands: typing s in the main window (the one in which you typed "server") causes all client threads to stop handling input until g (for go) is typed in the same window. Use a condition variable (combined with a mutex) to implement this feature.
Within the directory hw1Part2_3 are two scripts to help you test your solution: test1 and test2.
There's another lengthy test script named WindowScript, along with an alternative version of interface.c named interface2.c. If you replace interface.c with the contents of interface2.c and rerun make, then whenever a client window is created, it automatically executes the contents of WindowScript without your having to type anything in it. This might make it even easier to test your code.
Note: Doing the fine-grained version is difficult. Make sure your coarse-grained solution works before you attempt a fine-grained one. Also, don't start working on the fine-grained solution until you've implemented the start and stop commands.