yBzv8SRV

1/* building block of the hash table, a linked list node that holds key, val, and next node */
2struct entry {
3    char *key;
4    uint64_t value;
5    struct entry *next;
6};
7typedef struct entry entry;
8
9/* the hash table itself, which has buckets that reference the head of each linked list */
10#define tablesize 56010
11entry *hashtable[tablesize];
12
13/* hash function "djb2" by Dan Bernstein */
14int hash(char *key) {
15    unsigned long hash = 5381;
16    int c;
17
18    while ((c = *key++))
19	hash = ((hash << 5) + hash) + c;
20
21    return hash % tablesize; // since we are only using it in our single sized hashtable, modulus it
22}
23
24/* Create a new entry to be added to the hash table. Ensures that memory is allocated and key is copied correctly */
25entry *newentry(char *key, uint64_t val) {
26    entry *new;
27
28    if ((new = malloc(sizeof(entry))) == NULL)
29	return NULL;
30
31    if (((*new).key = strdup(key)) == NULL)
32	return NULL;
33
34    (*new).value = val;
35    (*new).next = NULL;
36
37    return new;
38}
39
40/* Add a new ID to the hash table, or update it if it already exists */
41void add(char *key, uint64_t val) {
42    int bin = hash(key);
43
44    entry *next = hashtable[bin];
45    entry *last;
46
47    /* loop through the correct bin's linked list and see if you find the key */
48    while (next != NULL && (*next).key != NULL && strcmp(key, (*next).key) > 0) {
49	last = next;
50	next = (*next).next;
51    }
52
53    /* If you found it, simply update the value for that key */
54    if (next != NULL && (*next).key != NULL && strcmp(key, (*next).key) == 0) {
55	(*next).value = val;
56    } else {
57	/* Otherwise, make a new entry */
58	entry *new = newentry(key, val);
59        
60	/* And we will add it to the correct bin */
61	if (next == hashtable[bin]) {  // this is the beginning of the linked list
62	    (*new).next = next;
63	    hashtable[bin] = new;
64	} else if (next == NULL) {  // this is the end of the linked list
65	    (*last).next = new;
66	} else {  // anywhere else in the list
67	    (*new).next = next;
68	    (*last).next = new;
69	}
70    }
71}
72
73/* get the value of a given key in the hashtable */
74uint64_t getkey(char *key) {
75    /* get the correct bin as well as the linked list in that bin */
76    int bin = hash(key);
77    entry *result = hashtable[bin];
78
79    /* go through the linked list until we find the correct key (or it ends) */
80    while (result != NULL && (*result).key != NULL && strcmp(key, (*result).key) > 0) {
81	result = (*result).next;
82    }
83
84    /* if we did not find it, give the default value of zero, otherwise return its val */
85    if (result == NULL || (*result).key == NULL || strcmp(key, (*result).key) != 0) {
86	return 0;
87    } else {
88	return (*result).value;
89    }
90
91    return 0;
92}