Various small fixes
[cgds.git] / src / HashTable.c
... / ...
CommitLineData
1/**
2 * @file HashTable.c
3 */
4
5#include "cgds/HashTable.h"
6
7void _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
17HashTable* _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
24HashTable* 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
52bool hashtable_empty(HashTable* hashTable)
53{
54 return (hashTable->size == 0);
55}
56
57UInt hashtable_size(HashTable* hashTable)
58{
59 return hashTable->size;
60}
61
62// Function (string) key --> (integer) hash [internal usage]
63UInt _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
72void* _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
85void _hashtable_set(HashTable* hashTable, char* key, void* data)
86{
87 UInt hashIdx = _compute_hash(key, hashTable->hashSize);
88 HashCell
89 *cell = hashTable->head[hashIdx],
90 *prev = NULL;
91 while (cell != NULL)
92 {
93 if (strcmp(cell->key, key) == 0)
94 {
95 // Modify:
96 memcpy(cell->data, data, hashTable->dataSize);
97 return;
98 }
99 prev = cell;
100 cell = cell->next;
101 }
102 // New element: insert after prev (which may be NULL)
103 HashCell* newCell = (HashCell*) safe_malloc(sizeof(HashCell));
104 newCell->key = (char*) safe_malloc(strlen(key) + 1);
105 strcpy(newCell->key, key);
106 newCell->data = safe_malloc(hashTable->dataSize);
107 memcpy(newCell->data, data, hashTable->dataSize);
108 newCell->next = NULL;
109 if (prev == NULL)
110 hashTable->head[hashIdx] = newCell;
111 else
112 prev->next = newCell;
113 hashTable->size++;
114}
115
116void hashtable_delete(HashTable* hashTable, char* key)
117{
118 UInt hashIdx = _compute_hash(key, hashTable->hashSize);
119 HashCell
120 *cell = hashTable->head[hashIdx],
121 *prev = NULL;
122 while (cell != NULL)
123 {
124 if (strcmp(cell->key, key) == 0)
125 {
126 if (prev == NULL)
127 hashTable->head[hashIdx] = cell->next;
128 else
129 prev->next = cell->next;
130 safe_free(cell->key);
131 safe_free(cell->data);
132 safe_free(cell);
133 hashTable->size--;
134 break;
135 }
136 prev = cell;
137 cell = cell->next;
138 }
139}
140
141void hashtable_clear(HashTable* hashTable)
142{
143 for (UInt i = 0; i < hashTable->hashSize; i++)
144 {
145 HashCell* cell = hashTable->head[i];
146 while (cell != NULL)
147 {
148 HashCell* next = cell->next;
149 safe_free(cell->key);
150 safe_free(cell->data);
151 safe_free(cell);
152 cell = next;
153 }
154 hashTable->head[i] = NULL;
155 }
156 hashTable->size = 0;
157}
158
159void hashtable_destroy(HashTable* hashTable)
160{
161 hashtable_clear(hashTable);
162 safe_free(hashTable->head);
163 safe_free(hashTable);
164}