Line data Source code
1 : /***************************************************************************//**
2 :
3 : @file hta.c
4 :
5 : @author Stephen Brennan
6 :
7 : @date Created Tuesday, 20 September 2016
8 :
9 : @brief Hash Table for Any data
10 :
11 : @copyright Copyright (c) 2016, Stephen Brennan. Released under the
12 : Revised BSD License. See the LICENSE.txt file for details.
13 :
14 : This is based on my original hashtable.c implementation, but aims to address
15 : the observation that using DATA is inflexible compared to simply storing
16 : blocks of memory.
17 :
18 : *******************************************************************************/
19 :
20 : #include <string.h>
21 : #include <stdio.h>
22 :
23 : #include "libstephen/ht.h"
24 : #include "libstephen/hta.h"
25 :
26 : /*******************************************************************************
27 :
28 : Private Functions
29 :
30 : *******************************************************************************/
31 :
32 1364 : unsigned int item_size(const smb_hta *obj)
33 : {
34 1364 : return HTA_KEY_OFFSET + obj->key_size + obj->value_size;
35 : }
36 :
37 1356 : unsigned int convert_idx(const smb_hta *obj, unsigned int orig)
38 : {
39 1356 : return orig * item_size(obj);
40 : }
41 :
42 : /**
43 : @brief Find the proper index for insertion into the table.
44 : @param obj Hash table object.
45 : @param key Key we're inserting.
46 : */
47 84 : unsigned int hta_find_insert(const smb_hta *obj, void *key)
48 : {
49 84 : unsigned int index = obj->hash(key) % obj->allocated;
50 84 : unsigned int bufidx = convert_idx(obj, index);
51 84 : unsigned int j = 1;
52 :
53 : // Continue searching until we either find a non-full slot, or we find the key
54 : // we're trying to insert.
55 : // until (cell.mark != full || cell.key == key)
56 : // while (cell.mark == full && cell.key != key)
57 788 : while (HTA_MARK(obj, bufidx) == HT_FULL &&
58 310 : obj->equal(key, obj->table + bufidx + HTA_KEY_OFFSET) != 0) {
59 : // This is quadratic probing, but I'm avoiding squaring numbers:
60 : // j: 1, 3, 5, 7, 9, 11, ..
61 : // index: 0, 1, 4, 9, 16, 25, 36
62 310 : index = (index + j) % obj->allocated;
63 310 : j += 2;
64 310 : bufidx = convert_idx(obj, index);
65 : }
66 :
67 84 : return index;
68 : }
69 :
70 : /**
71 : @brief Find the proper index for retrieval from the table.
72 : @param obj Hash table object.
73 : @param key Key we're looking up.
74 : */
75 158 : unsigned int hta_find_retrieve(const smb_hta *obj, void *key)
76 : {
77 158 : unsigned int index = obj->hash(key) % obj->allocated;
78 158 : unsigned int bufidx = convert_idx(obj, index);
79 158 : unsigned int j = 1;
80 :
81 : // Continue searching until we either find an empty slot, or we find the key
82 : // we're trying to insert.
83 : // until (cell.mark == empty || cell.key == key)
84 : // while (cell.mark != empty && cell.key != key)
85 1389 : while (HTA_MARK(obj, bufidx) != HT_EMPTY &&
86 573 : obj->equal(key, obj->table + bufidx + HTA_KEY_OFFSET) != 0) {
87 : // This is quadratic probing, but I'm avoiding squaring numbers:
88 : // j: 1, 3, 5, 7, 9, 11, ..
89 : // index: 0, 1, 4, 9, 16, 25, 36
90 500 : index = (index + j) % obj->allocated;
91 500 : j += 2;
92 500 : bufidx = convert_idx(obj, index);
93 : }
94 :
95 158 : return index;
96 : }
97 :
98 : /**
99 : @brief Expand the hash table, adding increment to the capacity of the table.
100 :
101 : @param table The table to expand.
102 : */
103 2 : void hta_resize(smb_hta *table)
104 : {
105 : void *old_table;
106 : unsigned int index, old_allocated, bufidx;
107 :
108 : // Step one: allocate new space for the table
109 2 : old_table = table->table;
110 2 : old_allocated = table->allocated;
111 2 : table->length = 0;
112 2 : table->allocated = ht_next_size(old_allocated);
113 2 : table->table = calloc(table->allocated, item_size(table));
114 :
115 : // Step two, add the old items to the new table.
116 64 : for (index = 0; index < old_allocated; index++) {
117 62 : bufidx = convert_idx(table, index);
118 62 : if (((int8_t*)old_table)[bufidx] == HT_FULL) {
119 32 : hta_insert(table, old_table + bufidx + HTA_KEY_OFFSET,
120 32 : old_table + bufidx + HTA_KEY_OFFSET + table->value_size);
121 : }
122 : }
123 :
124 : // Step three: free old data.
125 2 : smb_free(old_table);
126 2 : }
127 :
128 : /**
129 : @brief Return the load factor of a hash table.
130 :
131 : @param table The table to find the load factor of.
132 : @returns The load factor of the hash table.
133 : */
134 87 : double hta_load_factor(smb_hta *table)
135 : {
136 87 : return ((double) table->length) / ((double) table->allocated);
137 : }
138 :
139 : /*******************************************************************************
140 :
141 : Public Interface Functions
142 :
143 : *******************************************************************************/
144 :
145 6 : void hta_init(smb_hta *table, HTA_HASH hash_func, HTA_COMP equal,
146 : unsigned int key_size, unsigned int value_size)
147 : {
148 : // Initialize values
149 6 : table->length = 0;
150 6 : table->allocated = HASH_TABLE_INITIAL_SIZE;
151 6 : table->key_size = key_size;
152 6 : table->value_size = value_size;
153 6 : table->hash = hash_func;
154 6 : table->equal = equal;
155 :
156 : // Allocate table
157 6 : table->table = calloc(HASH_TABLE_INITIAL_SIZE, item_size(table));
158 6 : }
159 :
160 6 : smb_hta *hta_create(HTA_HASH hash_func, HTA_COMP equal,
161 : unsigned int key_size, unsigned int value_size)
162 : {
163 : // Allocate and create the table.
164 : smb_hta *table;
165 6 : table = smb_new(smb_hta, 1);
166 6 : hta_init(table, hash_func, equal, key_size, value_size);
167 6 : return table;
168 : }
169 :
170 6 : void hta_destroy(smb_hta *table)
171 : {
172 6 : smb_free(table->table);
173 6 : }
174 :
175 6 : void hta_delete(smb_hta *table)
176 : {
177 6 : if (!table) {
178 6 : return;
179 : }
180 :
181 6 : hta_destroy(table);
182 6 : smb_free(table);
183 : }
184 :
185 87 : void hta_insert(smb_hta *table, void *key, void *value)
186 : {
187 : unsigned int index, bufidx;
188 87 : if (hta_load_factor(table) > HASH_TABLE_MAX_LOAD_FACTOR) {
189 2 : hta_resize(table);
190 : }
191 :
192 : // First, probe for the key as if we're trying to return it. If we find it,
193 : // we update the existing key.
194 87 : index = hta_find_retrieve(table, key);
195 87 : bufidx = convert_idx(table, index);
196 87 : if (HTA_MARK(table, bufidx) == HT_FULL) {
197 3 : memcpy(table->table + bufidx + HTA_KEY_OFFSET + table->key_size, value,
198 3 : table->value_size);
199 90 : return;
200 : }
201 :
202 : // If we don't find the key, then we find the first open slot or gravestone.
203 84 : index = hta_find_insert(table, key);
204 84 : bufidx = convert_idx(table, index);
205 84 : HTA_MARK(table, bufidx) = HT_FULL;
206 84 : memcpy(table->table + bufidx + HTA_KEY_OFFSET, key, table->key_size);
207 84 : memcpy(table->table + bufidx + HTA_KEY_OFFSET + table->key_size, value,
208 84 : table->value_size);
209 84 : table->length++;
210 : }
211 :
212 8 : void hta_remove(smb_hta *table, void *key, smb_status *status)
213 : {
214 8 : *status = SMB_SUCCESS;
215 8 : unsigned int index = hta_find_retrieve(table, key);
216 8 : unsigned int bufidx = convert_idx(table, index);
217 :
218 : // If the returned slot isn't full, that means we couldn't find it.
219 8 : if (HTA_MARK(table, bufidx) != HT_FULL) {
220 0 : *status = SMB_NOT_FOUND_ERROR;
221 8 : return;
222 : }
223 :
224 : // Mark the slot with a "grave stone", indicating it is deleted.
225 8 : HTA_MARK(table, bufidx) = HT_GRAVE;
226 8 : table->length--;
227 : }
228 :
229 63 : void *hta_get(smb_hta const *table, void *key, smb_status *status)
230 : {
231 63 : *status = SMB_SUCCESS;
232 63 : unsigned int index = hta_find_retrieve(table, key);
233 63 : unsigned int bufidx = convert_idx(table, index);
234 :
235 : // If the slot is not marked full, we didn't find the key.
236 63 : if (HTA_MARK(table, bufidx) != HT_FULL) {
237 6 : *status = SMB_NOT_FOUND_ERROR;
238 6 : return NULL;
239 : }
240 :
241 : // Otherwise, return the value.
242 57 : return table->table + bufidx + HTA_KEY_OFFSET + table->key_size;
243 : }
244 :
245 10 : bool hta_contains(smb_hta const *table, void *key)
246 : {
247 10 : smb_status status = SMB_SUCCESS;
248 10 : hta_get(table, key, &status);
249 10 : return status == SMB_SUCCESS;
250 : }
251 :
252 67 : unsigned int hta_string_hash(void *data)
253 : {
254 67 : char *theString = *(char**)data;
255 67 : unsigned int hash = 0;
256 :
257 763 : while (theString && *theString != '\0' ) {
258 629 : hash = (hash << 5) - hash + *theString;
259 629 : theString++;
260 : }
261 :
262 : // printf("Hash of \"%s\": %u\n", (char*)data.data_ptr, hash);
263 67 : return hash;
264 : }
265 :
266 36 : int hta_string_comp(void *left, void *right)
267 : {
268 36 : char **l = (char**)left, **r = (char**)right;
269 36 : return strcmp(*l,*r);
270 : }
271 :
272 847 : int hta_int_comp(void *left, void *right)
273 : {
274 847 : int *l = (int*)left, *r = (int*)right;
275 847 : return *l - *r;
276 : }
277 :
278 0 : void hta_print(FILE* f, smb_hta const *table, HTA_PRINT key, HTA_PRINT value,
279 : int full_mode)
280 : {
281 : unsigned int i, bufidx;
282 0 : char *MARKS[] = {"EMPTY", " FULL", "GRAVE"};
283 :
284 0 : for (i = 0; i < table->allocated; i++) {
285 0 : bufidx = convert_idx(table, i);
286 0 : int8_t mark = HTA_MARK(table, bufidx);
287 0 : if (full_mode || mark == HT_FULL) {
288 0 : printf("[%04d|%05d|%s]:\n", i, bufidx, MARKS[mark]);
289 0 : if (mark == HT_FULL) {
290 0 : printf(" key: ");
291 0 : key(f, table->table + bufidx + HTA_KEY_OFFSET);
292 0 : printf("\n value: ");
293 0 : value(f, table->table + bufidx + HTA_KEY_OFFSET + table->value_size);
294 0 : printf("\n");
295 : }
296 : }
297 : }
298 0 : }
|
