A concurrent hash table is a data structure that allows multiple threads to perform operations on a shared collection of key-data pairs, without causing data corruption or inconsistency. The concurrent hash table consists of a linked list of nodes, each of which stores some data associated with the key. The hash value is computed by applying a hash function to the key.

Note that for this assignment, we will not be taking into consideration hash collisions. We will use Jenkins’s one_at_a_time hash function which has a very low collision rate for the number of hashes we will be working with. Regardless, your test data and the final data set you will be graded against will be guaranteed collision-free.

The concurrent hash table supports the following functions:

• insert(key, values): This function inserts a new key-data pair into the hash table, or updates the value of an existing key. To insert a key-data pair, the function first computes the hash value of the key and locates the corresponding entry in the linked list. Then, it acquires the write lock that protects the list and searches the linked list for the key. If the key is found, it updates the value. Otherwise, it creates a new node and inserts it in the list. Finally, it releases the write lock and returns.
• delete(key): This function deletes a key-data pair from the hash table, if it exists. To delete a key-data pair, the function first computes the hash value of the key and locates the corresponding node. Then, it acquires the write lock that protects the list and searches the linked list for the key. If the key is found, it removes the node from the list and frees the memory. Otherwise, it does nothing. Finally, it releases the write lock and returns.
• search(key): This function searches for a key-data pair in the hash table and returns the value, if it exists. To search for a key-data pair, the function first computes the hash value of the key and locates the corresponding node. Then, it acquires the read lock that protects the list and searches the linked list for the key. If the key is found, it returns the value. Otherwise, it returns NULL. Finally, it releases the read lock and returns. The caller should then print the record or “No Record Found” if the return is NULL.

The Hash Table Structure¶

typedef struct hash_struct
{
  uint32_t hash;
  char name[50];
  uint32_t salary;
  struct hash_struct *next;
} hashRecord;

https://github.com/remzi-arpacidusseau/ostep-code/tree/master/threads-sema

Note:

• You will also need to grab common.h and common_threads.h from here:
  • https://github.com/remzi-arpacidusseau/ostep-code/tree/master/include
• Sample Reader-Writer locks implementation is here:
  • https://github.com/remzi-arpacidusseau/ostep-code/blob/master/threads-sema/rwlock.c

The Command File¶

Your program must read a text file called commands.txt containing some configuration information, commands, and data values. Do not read it from the console. You should hard code "commands.txt" into your program.

List of Commands and their parameters¶

threads,11,0
insert,Richard Garriot,40000
insert,Sid Meier,50000
insert,Shigeru Miyamoto,51000
insert,Hideo Kojima,45000
insert,Gabe Newell,49000
insert,Roberta Williams,45900
insert,Carol Shaw,41000
print,0,0
search,Shigeru Miyamoto,0
delete,Sid Meier,0
print,0,0

Expected Output¶

Output should be written to a file called output.txt in the same directory as the main chash program and the commands.txt file.

Commands¶

Write out each command as they’re executed, along with their parameters in this format:
INSERT,Name,Salary

Examples:¶

INSERT,John Doe,45000
DELETE,John Doe
SEARCH,John Doe

Locks¶

Write out when locks are acquired and released along with the lock type:

Examples:¶

READ LOCK ACQUIRED
READ LOCK RELEASED
WRITE LOCK ACQUIRED
WRITE LOCK RELEASED

Data Output¶

Single Record Print (e.g., from Search)¶

Print the hash value, name, and salary:
36474636,John Doe,45000

List Print¶

Use the single record print for each record:

53958970,John Doe,50000
60118794,Jane Doe,41000
71650320,Bob Smith,45900
595880477,Jennifer Brown,49000
3139972584,Shin Xi,45000
4030153111,Rocky Lancaster,51000

The list should be sorted by the hash value.

Final Print¶

After the final command, print a blank line and the following summary information:
Number of lock acquisition and release operations and the contents of the table after all operations are completed:

Number of lock acquisitions: 12
Number of lock releases: 12
Final Table:
53958970,John Doe,50000
60118794,Jane Doe,41000
71650320,Bob Smith,45900
595880477,Jennifer Brown,49000
3139972584,Shin Xi,45000
4030153111,Rocky Lancaster,51000

Final Deliverables:¶

• Unzip your file.
• Run make to compile it into the main executable chash
• Your program will read commands.txt and then produce output.txt

AI Policy¶

When using AI assistants, please adhere to the following policies and suggestions:

• Put Effort into Crafting High-Quality Prompts: Tools like ChatGPT and CoPilot, while useful, have serious limitations, and hence are often incorrect. If you provide minimum effort prompts, you will get low quality results. You will need to refine your prompts in order to get good outcomes. This will take concerted effort.
• Be Aware of AI Limitations: Even if you have crafted well-constructed prompts, do not blindly trust anything an AI assistant tool says or outputs. If it gives a snippet of code, number, or fact, assume that it is wrong unless you either know it to be correct or check it with another source. You are responsible for any errors or omissions provided by the tool, and these tools tend to work best for topics you fully understand.
• Give the AI Tool Proper Attribution: AI is a tool, and one that you must acknowledge using. Thus, you must provide these tools proper attribution if you use them for assignments. As such, you are required to provide a paragraph or two either in a comment or in the README file explaining what you used the AI for, and what prompts you used to get the results. Failure to do this will result in a violation of UCF Academic Integrity policies.
• Know When to Use and Not Use AI Tools Be thoughtful about when AI tools are useful and when they are not. Don’t use the tool if it isn’t appropriate, or if you do not have full grasp of a given concept from class.

credit to Dr. Kevin Moran for this succinct summary of AI use policy!

Grading Rubric¶

100 points total