· 7 years ago · Oct 25, 2018, 03:02 PM
1/**
2 * @file icl_hash.c
3 *
4 * Dependency free hash table implementation.
5 *
6 * This simple hash table implementation should be easy to drop into
7 * any other peice of code, it does not depend on anything else :-)
8 *
9 * @author Jakub Kurzak
10 */
11/* $Id: icl_hash.c 2838 2011-11-22 04:25:02Z mfaverge $ */
12/* $UTK_Copyright: $ */
13
14#include <stdlib.h>
15#include <stdio.h>
16#include <string.h>
17#include <assert.h>
18
19#include "icl_hash.h"
20
21#include <limits.h>
22
23
24#define BITS_IN_int ( sizeof(int) * CHAR_BIT )
25#define THREE_QUARTERS ((int) ((BITS_IN_int * 3) / 4))
26#define ONE_EIGHTH ((int) (BITS_IN_int / 8))
27#define HIGH_BITS ( ~((unsigned int)(~0) >> ONE_EIGHTH ))
28/**
29 * A simple string hash.
30 *
31 * An adaptation of Peter Weinberger's (PJW) generic hashing
32 * algorithm based on Allen Holub's version. Accepts a pointer
33 * to a datum to be hashed and returns an unsigned integer.
34 * From: Keith Seymour's proxy library code
35 *
36 * @param[in] key -- the string to be hashed
37 *
38 * @returns the hash index
39 */
40unsigned int
41hash_pjw(void* key)
42{
43 char *datum = (char *)key;
44 unsigned int hash_value, i;
45
46 if(!datum) return 0;
47
48 for (hash_value = 0; *datum; ++datum) {
49 hash_value = (hash_value << ONE_EIGHTH) + *datum;
50 if ((i = hash_value & HIGH_BITS) != 0)
51 hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
52 }
53 return (hash_value);
54}
55
56int string_compare(void* a, void* b)
57{
58 return (strcmp( (char*)a, (char*)b ) == 0);
59}
60
61
62/**
63 * Create a new hash table.
64 *
65 * @param[in] nbuckets -- number of buckets to create
66 * @param[in] hash_function -- pointer to the hashing function to be used
67 * @param[in] hash_key_compare -- pointer to the hash key comparison function to be used
68 *
69 * @returns pointer to new hash table.
70 */
71
72icl_hash_t *
73icl_hash_create( int nbuckets, unsigned int (*hash_function)(void*), int (*hash_key_compare)(void*, void*) )
74{
75 icl_hash_t *ht;
76 int i;
77
78 ht = (icl_hash_t*) malloc(sizeof(icl_hash_t));
79 if(!ht) return NULL;
80
81 ht->nentries = 0;
82 ht->buckets = (icl_entry_t**)malloc(nbuckets * sizeof(icl_entry_t*));
83 if(!ht->buckets) return NULL;
84
85 ht->nbuckets = nbuckets;
86 for(i=0;i<ht->nbuckets;i++)
87 ht->buckets[i] = NULL;
88
89 ht->hash_function = hash_function ? hash_function : hash_pjw;
90 ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;
91
92 return ht;
93}
94
95/**
96 * Search for an entry in a hash table.
97 *
98 * @param ht -- the hash table to be searched
99 * @param key -- the key of the item to search for
100 *
101 * @returns pointer to the data corresponding to the key.
102 * If the key was not found, returns NULL.
103 */
104
105void *
106icl_hash_find(icl_hash_t *ht, void* key)
107{
108 icl_entry_t* curr;
109 unsigned int hash_val;
110
111 if(!ht || !key) return NULL;
112
113 hash_val = (* ht->hash_function)(key) % ht->nbuckets;
114
115 for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
116 if ( ht->hash_key_compare(curr->key, key))
117 return(curr->data);
118
119 return NULL;
120}
121
122/**
123 * Insert an item into the hash table.
124 *
125 * @param ht -- the hash table
126 * @param key -- the key of the new item
127 * @param data -- pointer to the new item's data
128 *
129 * @returns pointer to the new item. Returns NULL on error.
130 */
131
132icl_entry_t *
133icl_hash_insert(icl_hash_t *ht, void* key, void *data)
134{
135 icl_entry_t *curr;
136 unsigned int hash_val;
137
138 if(!ht || !key) return NULL;
139
140 hash_val = (* ht->hash_function)(key) % ht->nbuckets;
141
142 for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
143 if ( ht->hash_key_compare(curr->key, key))
144 return(NULL); /* key already exists */
145
146 /* if key was not found */
147 curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
148 if(!curr) return NULL;
149
150 curr->key = key;
151 curr->data = data;
152 curr->next = ht->buckets[hash_val]; /* add at start */
153
154 ht->buckets[hash_val] = curr;
155 ht->nentries++;
156
157 return curr;
158}
159
160/**
161 * Replace entry in hash table with the given entry.
162 *
163 * @param ht -- the hash table
164 * @param key -- the key of the new item
165 * @param data -- pointer to the new item's data
166 * @param olddata -- pointer to the old item's data (set upon return)
167 *
168 * @returns pointer to the new item. Returns NULL on error.
169 */
170
171icl_entry_t *
172icl_hash_update_insert(icl_hash_t *ht, void* key, void *data, void **olddata)
173{
174 icl_entry_t *curr, *prev;
175 unsigned int hash_val;
176
177 if(!ht || !key) return NULL;
178
179 hash_val = (* ht->hash_function)(key) % ht->nbuckets;
180
181 /* Scan bucket[hash_val] for key */
182 for (prev=NULL,curr=ht->buckets[hash_val]; curr != NULL; prev=curr, curr=curr->next)
183 /* If key found, remove node from list, free old key, and setup olddata for the return */
184 if ( ht->hash_key_compare(curr->key, key)) {
185 if (olddata != NULL) {
186 *olddata = curr->data;
187 free(curr->key);
188 }
189
190 if (prev == NULL)
191 ht->buckets[hash_val] = curr->next;
192 else
193 prev->next = curr->next;
194 }
195
196 /* Since key was either not found, or found-and-removed, create and prepend new node */
197 curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
198 if(curr == NULL) return NULL; /* out of memory */
199
200 curr->key = key;
201 curr->data = data;
202 curr->next = ht->buckets[hash_val]; /* add at start */
203
204 ht->buckets[hash_val] = curr;
205 ht->nentries++;
206
207 if(olddata!=NULL && *olddata!=NULL)
208 *olddata = NULL;
209
210 return curr;
211}
212
213/**
214 * Free one hash table entry located by key (key and data are freed using functions).
215 *
216 * @param ht -- the hash table to be freed
217 * @param key -- the key of the new item
218 * @param free_key -- pointer to function that frees the key
219 * @param free_data -- pointer to function that frees the data
220 *
221 * @returns 0 on success, -1 on failure.
222 */
223int icl_hash_delete(icl_hash_t *ht, void* key, void (*free_key)(void*), void (*free_data)(void*))
224{
225 icl_entry_t *curr, *prev;
226 unsigned int hash_val;
227
228 if(!ht || !key) return -1;
229 hash_val = (* ht->hash_function)(key) % ht->nbuckets;
230
231 prev = NULL;
232 for (curr=ht->buckets[hash_val]; curr != NULL; ) {
233 if ( ht->hash_key_compare(curr->key, key)) {
234 if (prev == NULL) {
235 ht->buckets[hash_val] = curr->next;
236 } else {
237 prev->next = curr->next;
238 }
239 if (*free_key && curr->key) (*free_key)(curr->key);
240 if (*free_data && curr->data) (*free_data)(curr->data);
241 ht->nentries++;
242 free(curr);
243 return 0;
244 }
245 prev = curr;
246 curr = curr->next;
247 }
248 return -1;
249}
250
251/**
252 * Free hash table structures (key and data are freed using functions).
253 *
254 * @param ht -- the hash table to be freed
255 * @param free_key -- pointer to function that frees the key
256 * @param free_data -- pointer to function that frees the data
257 *
258 * @returns 0 on success, -1 on failure.
259 */
260int
261icl_hash_destroy(icl_hash_t *ht, void (*free_key)(void*), void (*free_data)(void*))
262{
263 icl_entry_t *bucket, *curr, *next;
264 int i;
265
266 if(!ht) return -1;
267
268 for (i=0; i<ht->nbuckets; i++) {
269 bucket = ht->buckets[i];
270 for (curr=bucket; curr!=NULL; ) {
271 next=curr->next;
272 if (*free_key && curr->key) (*free_key)(curr->key);
273 if (*free_data && curr->data) (*free_data)(curr->data);
274 free(curr);
275 curr=next;
276 }
277 }
278
279 if(ht->buckets) free(ht->buckets);
280 if(ht) free(ht);
281
282 return 0;
283}
284
285/**
286 * Dump the hash table's contents to the given file pointer.
287 *
288 * @param stream -- the file to which the hash table should be dumped
289 * @param ht -- the hash table to be dumped
290 *
291 * @returns 0 on success, -1 on failure.
292 */
293
294int
295icl_hash_dump(FILE* stream, icl_hash_t* ht)
296{
297 icl_entry_t *bucket, *curr;
298 int i;
299
300 if(!ht) return -1;
301
302 for(i=0; i<ht->nbuckets; i++) {
303 bucket = ht->buckets[i];
304 for(curr=bucket; curr!=NULL; ) {
305 if(curr->key)
306 fprintf(stream, "icl_hash_dump: %s: %p\n", (char *)curr->key, curr->data);
307 curr=curr->next;
308 }
309 }
310
311 return 0;
312}