PULSAR  2.0.0
Parallel Ultra-Light Systolic Array Runtime
 All Data Structures Files Functions Typedefs Enumerations Macros Groups
icl_hash.c
Go to the documentation of this file.
1 
11 #include <stdlib.h>
12 #include <stdio.h>
13 #include <string.h>
14 #include <assert.h>
15 #include <limits.h>
16 
17 #include "icl_hash.h"
18 
19 #define BITS_IN_int (sizeof(int) * CHAR_BIT)
20 #define THREE_QUARTERS ((int)((BITS_IN_int * 3) / 4))
21 #define ONE_EIGHTH ((int)(BITS_IN_int / 8))
22 #define HIGH_BITS (~((unsigned int)(~0) >> ONE_EIGHTH))
23 
24 static unsigned int hash_pjw(void *key);
25 static int string_compare(void *a, void *b);
26 
28 
39 static unsigned int hash_pjw(void *key)
40 {
41  char *datum = (char*)key;
42  unsigned int hash_value, i;
43 
44  if(!datum)
45  return 0;
46 
47  for (hash_value = 0; *datum; ++datum) {
48  hash_value = (hash_value << ONE_EIGHTH) + *datum;
49  if ((i = hash_value & HIGH_BITS) != 0)
50  hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
51  }
52  return (hash_value);
53 }
54 
56 static int string_compare(void *a, void *b)
57 {
58  return (strcmp( (char*)a, (char*)b ) == 0);
59 }
60 
62 
72  int nbuckets,
73  unsigned int (*hash_function)(void*),
74  int (*hash_key_compare)(void*, void*))
75 {
76  icl_hash_t *ht;
77  int i;
78 
79  ht = (icl_hash_t*)malloc(sizeof(icl_hash_t));
80  if(!ht)
81  return NULL;
82 
83  ht->nentries = 0;
84  ht->buckets = (icl_entry_t**)malloc(nbuckets*sizeof(icl_entry_t*));
85  if(!ht->buckets) {
86  free(ht);
87  return NULL;
88  }
89  ht->nbuckets = nbuckets;
90  for(i = 0; i < ht->nbuckets; i++)
91  ht->buckets[i] = NULL;
92 
93  ht->hash_function = hash_function ? hash_function : hash_pjw;
94  ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;
95 
96  return ht;
97 }
98 
100 
109 void *icl_hash_find(icl_hash_t *ht, void* key)
110 {
111  icl_entry_t* curr;
112  unsigned int hash_val;
113 
114  if(!ht || !key)
115  return NULL;
116 
117  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
118  for (curr = ht->buckets[hash_val]; curr != NULL; curr = curr->next)
119  if (ht->hash_key_compare(curr->key, key))
120  return(curr->data);
121 
122  return NULL;
123 }
124 
126 
135 icl_entry_t* icl_hash_insert(icl_hash_t *ht, void* key, void *data)
136 {
137  icl_entry_t *curr;
138  unsigned int hash_val;
139 
140  if(!ht || !key)
141  return NULL;
142 
143  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
144  for (curr = ht->buckets[hash_val]; curr != NULL; curr = curr->next)
145  if (ht->hash_key_compare(curr->key, key))
146  return(NULL); // The key already exists.
147 
148  // IF key was not found.
149  curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
150  if(!curr)
151  return NULL;
152 
153  curr->key = key;
154  curr->data = data;
155  curr->next = ht->buckets[hash_val]; // Add at the start.
156 
157  ht->buckets[hash_val] = curr;
158  ht->nentries++;
159 
160  return curr;
161 }
162 
164 
175  icl_hash_t *ht, void* key, void *data, void **olddata)
176 {
177  icl_entry_t *curr, *prev;
178  unsigned int hash_val;
179 
180  if(!ht || !key)
181  return NULL;
182 
183  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
184 
185  // Scan bucket[hash_val] for the key.
186  for (prev = NULL, curr=ht->buckets[hash_val];
187  curr != NULL;
188  prev = curr, curr = curr->next)
189  // IF key found, remove the node from the list,
190  // free the old key, and setup olddata for the return.
191  if (ht->hash_key_compare(curr->key, key)) {
192  if (olddata != NULL) {
193  *olddata = curr->data;
194  free(curr->key);
195  }
196  if (prev == NULL)
197  ht->buckets[hash_val] = curr->next;
198  else
199  prev->next = curr->next;
200  }
201 
202  // Since the key was either not found,
203  // or found-and-removed, create and prepend a new node.
204  curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
205  if(curr == NULL)
206  return NULL; // Out of memory.
207 
208  curr->key = key;
209  curr->data = data;
210  curr->next = ht->buckets[hash_val]; // Add at the start.
211 
212  ht->buckets[hash_val] = curr;
213  ht->nentries++;
214 
215  if (olddata != NULL && *olddata != NULL)
216  *olddata = NULL;
217 
218  return curr;
219 }
220 
222 
235  icl_hash_t *ht, void* key,
236  void (*free_key)(void*),
237  void (*free_data)(void*))
238 {
239  icl_entry_t *curr, *prev;
240  unsigned int hash_val;
241 
242  if(!ht || !key)
243  return -1;
244 
245  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
246 
247  prev = NULL;
248  for (curr = ht->buckets[hash_val]; curr != NULL;) {
249  if (ht->hash_key_compare(curr->key, key)) {
250  if (prev == NULL) {
251  ht->buckets[hash_val] = curr->next;
252  }
253  else {
254  prev->next = curr->next;
255  }
256  if (*free_key && curr->key)
257  (*free_key)(curr->key);
258  if (*free_data && curr->data)
259  (*free_data)(curr->data);
260  ht->nentries++;
261  free(curr);
262  return 0;
263  }
264  prev = curr;
265  curr = curr->next;
266  }
267  return -1;
268 }
269 
271 
283  icl_hash_t *ht,
284  void (*free_key)(void*),
285  void (*free_data)(void*))
286 {
287  icl_entry_t *bucket, *curr, *next;
288  int i;
289 
290  if(!ht)
291  return -1;
292 
293  for (i = 0; i < ht->nbuckets; i++) {
294  bucket = ht->buckets[i];
295  for (curr = bucket; curr!=NULL;) {
296  next = curr->next;
297  if (*free_key && curr->key)
298  (*free_key)(curr->key);
299  if (*free_data && curr->data)
300  (*free_data)(curr->data);
301  free(curr);
302  curr = next;
303  }
304  }
305  if (ht->buckets)
306  free(ht->buckets);
307  if (ht)
308  free(ht);
309 
310  return 0;
311 }
312 
314 
323 int icl_hash_dump(FILE *stream, icl_hash_t *ht)
324 {
325  icl_entry_t *bucket, *curr;
326  int i;
327 
328  if(!ht)
329  return -1;
330 
331  for (i = 0; i < ht->nbuckets; i++) {
332  bucket = ht->buckets[i];
333  for (curr = bucket; curr!=NULL;) {
334  if (curr->key)
335  fprintf(stream,
336  "icl_hash_dump: %s: %p\n", (char*)curr->key, curr->data);
337  curr=curr->next;
338  }
339  }
340  return 0;
341 }