PULSAR  1.0.0
Parallel Ultra Light Systolic Array Runtime
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
icl_hash.c
Go to the documentation of this file.
1 
12 #include <stdlib.h>
13 #include <stdio.h>
14 #include <string.h>
15 #include <assert.h>
16 #include <limits.h>
17 
18 #include "icl_hash.h"
19 
20 #define BITS_IN_int (sizeof(int) * CHAR_BIT)
21 #define THREE_QUARTERS ((int)((BITS_IN_int * 3) / 4))
22 #define ONE_EIGHTH ((int)(BITS_IN_int / 8))
23 #define HIGH_BITS (~((unsigned int)(~0) >> ONE_EIGHTH))
24 
26 
38 static unsigned int hash_pjw(void *key)
39 {
40  char *datum = (char*)key;
41  unsigned int hash_value, i;
42 
43  if(!datum)
44  return 0;
45 
46  for (hash_value = 0; *datum; ++datum) {
47  hash_value = (hash_value << ONE_EIGHTH) + *datum;
48  if ((i = hash_value & HIGH_BITS) != 0)
49  hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
50  }
51  return (hash_value);
52 }
53 
55 static int string_compare(void *a, void *b)
56 {
57  return (strcmp( (char*)a, (char*)b ) == 0);
58 }
59 
61 
71  int nbuckets,
72  unsigned int (*hash_function)(void*),
73  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)
80  return NULL;
81 
82  ht->nentries = 0;
83  ht->buckets = (icl_entry_t**)malloc(nbuckets*sizeof(icl_entry_t*));
84  if(!ht->buckets) {
85  free(ht);
86  return NULL;
87  }
88  ht->nbuckets = nbuckets;
89  for(i = 0; i < ht->nbuckets; i++)
90  ht->buckets[i] = NULL;
91 
92  ht->hash_function = hash_function ? hash_function : hash_pjw;
93  ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;
94 
95  return ht;
96 }
97 
99 
108 void *icl_hash_find(icl_hash_t *ht, void* key)
109 {
110  icl_entry_t* curr;
111  unsigned int hash_val;
112 
113  if(!ht || !key)
114  return NULL;
115 
116  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
117  for (curr = ht->buckets[hash_val]; curr != NULL; curr = curr->next)
118  if (ht->hash_key_compare(curr->key, key))
119  return(curr->data);
120 
121  return NULL;
122 }
123 
125 
134 icl_entry_t* icl_hash_insert(icl_hash_t *ht, void* key, void *data)
135 {
136  icl_entry_t *curr;
137  unsigned int hash_val;
138 
139  if(!ht || !key)
140  return NULL;
141 
142  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
143  for (curr = ht->buckets[hash_val]; curr != NULL; curr = curr->next)
144  if (ht->hash_key_compare(curr->key, key))
145  return(NULL); /* key already exists */
146 
147  /* if key was not found */
148  curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
149  if(!curr)
150  return NULL;
151 
152  curr->key = key;
153  curr->data = data;
154  curr->next = ht->buckets[hash_val]; /* add at start */
155 
156  ht->buckets[hash_val] = curr;
157  ht->nentries++;
158 
159  return curr;
160 }
161 
163 
174  icl_hash_t *ht, void* key, void *data, void **olddata)
175 {
176  icl_entry_t *curr, *prev;
177  unsigned int hash_val;
178 
179  if(!ht || !key)
180  return NULL;
181 
182  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
183 
184  /* Scan bucket[hash_val] for key */
185  for (prev = NULL, curr=ht->buckets[hash_val];
186  curr != NULL;
187  prev = curr, curr = curr->next)
188  /* If key found, remove node from list,
189  free old key, and setup olddata for the return */
190  if (ht->hash_key_compare(curr->key, key)) {
191  if (olddata != NULL) {
192  *olddata = curr->data;
193  free(curr->key);
194  }
195  if (prev == NULL)
196  ht->buckets[hash_val] = curr->next;
197  else
198  prev->next = curr->next;
199  }
200 
201  /* Since key was either not found,
202  or found-and-removed, create and prepend new node */
203  curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
204  if(curr == NULL)
205  return NULL; /* out of memory */
206 
207  curr->key = key;
208  curr->data = data;
209  curr->next = ht->buckets[hash_val]; /* add at start */
210 
211  ht->buckets[hash_val] = curr;
212  ht->nentries++;
213 
214  if (olddata != NULL && *olddata != NULL)
215  *olddata = NULL;
216 
217  return curr;
218 }
219 
221 
233  icl_hash_t *ht, void* key,
234  void (*free_key)(void*),
235  void (*free_data)(void*))
236 {
237  icl_entry_t *curr, *prev;
238  unsigned int hash_val;
239 
240  if(!ht || !key)
241  return -1;
242 
243  hash_val = (*ht->hash_function)(key) % ht->nbuckets;
244 
245  prev = NULL;
246  for (curr = ht->buckets[hash_val]; curr != NULL;) {
247  if (ht->hash_key_compare(curr->key, key)) {
248  if (prev == NULL) {
249  ht->buckets[hash_val] = curr->next;
250  }
251  else {
252  prev->next = curr->next;
253  }
254  if (*free_key && curr->key)
255  (*free_key)(curr->key);
256  if (*free_data && curr->data)
257  (*free_data)(curr->data);
258  ht->nentries++;
259  free(curr);
260  return 0;
261  }
262  prev = curr;
263  curr = curr->next;
264  }
265  return -1;
266 }
267 
269 
280  icl_hash_t *ht,
281  void (*free_key)(void*),
282  void (*free_data)(void*))
283 {
284  icl_entry_t *bucket, *curr, *next;
285  int i;
286 
287  if(!ht)
288  return -1;
289 
290  for (i = 0; i < ht->nbuckets; i++) {
291  bucket = ht->buckets[i];
292  for (curr = bucket; curr!=NULL;) {
293  next = curr->next;
294  if (*free_key && curr->key)
295  (*free_key)(curr->key);
296  if (*free_data && curr->data)
297  (*free_data)(curr->data);
298  free(curr);
299  curr = next;
300  }
301  }
302  if (ht->buckets)
303  free(ht->buckets);
304  if (ht)
305  free(ht);
306 
307  return 0;
308 }
309 
311 
319 int icl_hash_dump(FILE *stream, icl_hash_t *ht)
320 {
321  icl_entry_t *bucket, *curr;
322  int i;
323 
324  if(!ht)
325  return -1;
326 
327  for (i = 0; i < ht->nbuckets; i++) {
328  bucket = ht->buckets[i];
329  for (curr = bucket; curr!=NULL;) {
330  if (curr->key)
331  fprintf(stream, "icl_hash_dump: %s: %p\n", (char*)curr->key, curr->data);
332  curr=curr->next;
333  }
334  }
335  return 0;
336 }
int icl_hash_destroy(icl_hash_t *ht, void(*free_key)(void *), void(*free_data)(void *))
Free hash table structures. Key and data are freed using functions.
Definition: icl_hash.c:279
int icl_hash_dump(FILE *stream, icl_hash_t *ht)
Dump the hash table&#39;s contents to the given file pointer.
Definition: icl_hash.c:319
#define ONE_EIGHTH
Definition: icl_hash.c:22
icl_entry_t ** buckets
Definition: icl_hash.h:28
#define HIGH_BITS
Definition: icl_hash.c:23
struct icl_entry_s * next
Definition: icl_hash.h:22
icl_entry_t * icl_hash_insert(icl_hash_t *ht, void *key, void *data)
Insert an item into the hash table.
Definition: icl_hash.c:134
#define THREE_QUARTERS
Definition: icl_hash.c:21
int nbuckets
Definition: icl_hash.h:26
int nentries
Definition: icl_hash.h:27
int(* hash_key_compare)(void *, void *)
Definition: icl_hash.h:30
void * data
Definition: icl_hash.h:21
icl_entry_t * icl_hash_update_insert(icl_hash_t *ht, void *key, void *data, void **olddata)
Replace entry in hash table with the given entry.
Definition: icl_hash.c:173
dependency free hash table
void * icl_hash_find(icl_hash_t *ht, void *key)
Search for an entry in a hash table.
Definition: icl_hash.c:108
unsigned int(* hash_function)(void *)
Definition: icl_hash.h:29
icl_hash_t * icl_hash_create(int nbuckets, unsigned int(*hash_function)(void *), int(*hash_key_compare)(void *, void *))
Create a new hash table.
Definition: icl_hash.c:70
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20
int icl_hash_delete(icl_hash_t *ht, void *key, void(*free_key)(void *), void(*free_data)(void *))
Free one hash table entry located by key. Key and data are freed using functions. ...
Definition: icl_hash.c:232