468de8139420139d40a9296895a71171f05a1f78
[cgds.git] / src / HashTable.c
1 /**
2 * @file HashTable.c
3 */
4
5 #include "cgds/HashTable.h"
6
7 void _hashtable_init(HashTable* hashTable, size_t dataSize, size_t hashSize)
8 {
9 hashTable->hashSize = hashSize;
10 hashTable->dataSize = dataSize;
11 hashTable->head = safe_malloc(hashSize * sizeof(HashCell*));
12 for (UInt i = 0; i < hashSize; i++)
13 hashTable->head[i] = NULL;
14 hashTable->size = 0;
15 }
16
17 HashTable* _hashtable_new(size_t dataSize, size_t hashSize)
18 {
19 HashTable* hashTable = (HashTable*) safe_malloc(sizeof(HashTable));
20 _hashtable_init(hashTable, dataSize, hashSize);
21 return hashTable;
22 }
23
24 HashTable* hashtable_copy(HashTable* hashTable)
25 {
26 HashTable* hashTableCopy =
27 _hashtable_new(hashTable->dataSize, hashTable->hashSize);
28 hashTableCopy->size = hashTable->size;
29 for (UInt i = 0; i < hashTable->hashSize; i++)
30 {
31 HashCell *cell = hashTable->head[i],
32 *cellCopy = hashTableCopy->head[i],
33 *prev = NULL;
34 while (cell != NULL)
35 {
36 // cellCopy == NULL (from empty list)
37 cellCopy = (HashCell*) safe_malloc(sizeof(HashCell));
38 cellCopy->key = (char*) safe_malloc(strlen(cell->key) + 1);
39 strcpy(cellCopy->key, cell->key);
40 cellCopy->data = safe_malloc(hashTable->dataSize);
41 memcpy(cellCopy->data, cell->data, hashTable->dataSize);
42 if (prev == NULL) hashTableCopy->head[i] = cellCopy;
43 else prev->next = cellCopy;
44 prev = cellCopy;
45 cell = cell->next;
46 }
47 if (cellCopy != NULL) cellCopy->next = NULL;
48 }
49 return hashTableCopy;
50 }
51
52 bool hashtable_empty(HashTable* hashTable)
53 {
54 return (hashTable->size == 0);
55 }
56
57 UInt hashtable_size(HashTable* hashTable)
58 {
59 return hashTable->size;
60 }
61
62 // Function (string) key --> (integer) hash [internal usage]
63 UInt _compute_hash(char* key, size_t hashSize)
64 {
65 UInt res = 0;
66 for (unsigned char* s = key; *s != '\0'; s++)
67 // NOTE: '31' from here https://stackoverflow.com/a/4384446
68 res = (*s + 31 * res) % hashSize;
69 return res;
70 }
71
72 void* _hashtable_get(HashTable* hashTable, char* key)
73 {
74 UInt hashIdx = _compute_hash(key, hashTable->hashSize);
75 HashCell* cell = hashTable->head[hashIdx];
76 while (cell != NULL)
77 {
78 if (strcmp(cell->key, key) == 0)
79 return cell->data;
80 cell = cell->next;
81 }
82 return NULL;
83 }
84
85 void _hashtable_set(HashTable* hashTable, char* key, void* data)
86 {
87 UInt hashIdx = _compute_hash(key, hashTable->hashSize);
88 HashCell *cell = hashTable->head[hashIdx],
89 *prev = NULL;
90 while (cell != NULL)
91 {
92 if (strcmp(cell->key, key) == 0)
93 {
94 // Modify:
95 memcpy(cell->data, data, hashTable->dataSize);
96 return;
97 }
98 prev = cell;
99 cell = cell->next;
100 }
101 // New element: insert after prev (which may be NULL)
102 HashCell* newCell = (HashCell*) safe_malloc(sizeof(HashCell));
103 newCell->key = (char*) safe_malloc(strlen(key) + 1);
104 strcpy(newCell->key, key);
105 newCell->data = safe_malloc(hashTable->dataSize);
106 memcpy(newCell->data, data, hashTable->dataSize);
107 newCell->next = NULL;
108 if (prev == NULL)
109 hashTable->head[hashIdx] = newCell;
110 else
111 prev->next = newCell;
112 hashTable->size++;
113 }
114
115 void hashtable_delete(HashTable* hashTable, char* key)
116 {
117 UInt hashIdx = _compute_hash(key, hashTable->hashSize);
118 HashCell *cell = hashTable->head[hashIdx],
119 *prev = NULL;
120 while (cell != NULL)
121 {
122 if (strcmp(cell->key, key) == 0)
123 {
124 if (prev == NULL)
125 hashTable->head[hashIdx] = cell->next;
126 else
127 prev->next = cell->next;
128 safe_free(cell->key);
129 safe_free(cell->data);
130 safe_free(cell);
131 hashTable->size--;
132 break;
133 }
134 prev = cell;
135 cell = cell->next;
136 }
137 }
138
139 void hashtable_clear(HashTable* hashTable)
140 {
141 for (UInt i = 0; i < hashTable->hashSize; i++)
142 {
143 HashCell* cell = hashTable->head[i];
144 while (cell != NULL)
145 {
146 HashCell* next = cell->next;
147 safe_free(cell->key);
148 safe_free(cell->data);
149 safe_free(cell);
150 cell = next;
151 }
152 hashTable->head[i] = NULL;
153 }
154 hashTable->size = 0;
155 }
156
157 void hashtable_destroy(HashTable* hashTable)
158 {
159 hashtable_clear(hashTable);
160 safe_free(hashTable->head);
161 safe_free(hashTable);
162 }