QUARK  0.9.0
QUARK-QUeuingAndRuntimeforKernels
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
icl_hash.c
Go to the documentation of this file.
1 
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 
40 static unsigned int
41 hash_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 
56 static int string_compare(void* a, void* b)
57 {
58  return (strcmp( (char*)a, (char*)b ) == 0);
59 }
60 
61 
72 icl_hash_t *
73 icl_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  assert(ht!=NULL);
80  if(!ht) return NULL;
81 
82  ht->nentries = 0;
83  ht->buckets = (icl_entry_t**)malloc(nbuckets * sizeof(icl_entry_t*));
84  assert(ht->buckets!=NULL);
85  if(!ht->buckets) return NULL;
86 
87  ht->nbuckets = nbuckets;
88  for(i=0;i<ht->nbuckets;i++)
89  ht->buckets[i] = NULL;
90 
91  ht->hash_function = hash_function ? hash_function : hash_pjw;
92  ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;
93 
94  return ht;
95 }
96 
107 void *
108 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) return NULL;
114 
115  hash_val = (* ht->hash_function)(key) % ht->nbuckets;
116 
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 
134 icl_entry_t *
135 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) return NULL;
141 
142  hash_val = (* ht->hash_function)(key) % ht->nbuckets;
143 
144  for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
145  if ( ht->hash_key_compare(curr->key, key))
146  return(NULL); /* key already exists */
147 
148  /* if key was not found */
149  curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
150  assert(curr != NULL);
151  if(!curr) return NULL;
152 
153  curr->key = key;
154  curr->data = data;
155  curr->next = ht->buckets[hash_val]; /* add at start */
156 
157  ht->buckets[hash_val] = curr;
158  ht->nentries++;
159 
160  return curr;
161 }
162 
174 icl_entry_t *
175 icl_hash_update_insert(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) 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]; curr != NULL; prev=curr, curr=curr->next)
186  /* If key found, remove node from list, free old key, and setup olddata for the return */
187  if ( ht->hash_key_compare(curr->key, key)) {
188  if (olddata != NULL) {
189  *olddata = curr->data;
190  free(curr->key);
191  }
192 
193  if (prev == NULL)
194  ht->buckets[hash_val] = curr->next;
195  else
196  prev->next = curr->next;
197  }
198 
199  /* Since key was either not found, or found-and-removed, create and prepend new node */
200  curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
201  assert(curr!=NULL);
202  if(curr == NULL) return NULL; /* out of memory */
203 
204  curr->key = key;
205  curr->data = data;
206  curr->next = ht->buckets[hash_val]; /* add at start */
207 
208  ht->buckets[hash_val] = curr;
209  ht->nentries++;
210 
211  if(olddata!=NULL && *olddata!=NULL)
212  *olddata = NULL;
213 
214  return curr;
215 }
216 
227 int icl_hash_delete(icl_hash_t *ht, void* key, void (*free_key)(void*), void (*free_data)(void*))
228 {
229  icl_entry_t *curr, *prev;
230  unsigned int hash_val;
231 
232  if(!ht || !key) return -1;
233  hash_val = (* ht->hash_function)(key) % ht->nbuckets;
234 
235  prev = NULL;
236  for (curr=ht->buckets[hash_val]; curr != NULL; ) {
237  if ( ht->hash_key_compare(curr->key, key)) {
238  if (prev == NULL) {
239  ht->buckets[hash_val] = curr->next;
240  } else {
241  prev->next = curr->next;
242  }
243  if (*free_key && curr->key) (*free_key)(curr->key);
244  if (*free_data && curr->data) (*free_data)(curr->data);
245  ht->nentries++;
246  free(curr);
247  return 0;
248  }
249  prev = curr;
250  curr = curr->next;
251  }
252  return -1;
253 }
254 
264 int
265 icl_hash_destroy(icl_hash_t *ht, void (*free_key)(void*), void (*free_data)(void*))
266 {
267  icl_entry_t *bucket, *curr, *next;
268  int i;
269 
270  if(!ht) return -1;
271 
272  for (i=0; i<ht->nbuckets; i++) {
273  bucket = ht->buckets[i];
274  for (curr=bucket; curr!=NULL; ) {
275  next=curr->next;
276  if (*free_key && curr->key) (*free_key)(curr->key);
277  if (*free_data && curr->data) (*free_data)(curr->data);
278  free(curr);
279  curr=next;
280  }
281  }
282 
283  if(ht->buckets) free(ht->buckets);
284  if(ht) free(ht);
285 
286  return 0;
287 }
288 
289 
299 int
300 icl_hash_dump(FILE* stream, icl_hash_t* ht)
301 {
302  icl_entry_t *bucket, *curr;
303  int i;
304 
305  if(!ht) return -1;
306 
307  for(i=0; i<ht->nbuckets; i++) {
308  bucket = ht->buckets[i];
309  for(curr=bucket; curr!=NULL; ) {
310  if(curr->key)
311  fprintf(stream, "icl_hash_dump: %s: %p\n", (char *)curr->key, curr->data);
312  curr=curr->next;
313  }
314  }
315 
316  return 0;
317 }