PULSAR  1.0.0
Parallel Ultra Light Systolic Array Runtime
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
icl_hash.c File Reference

dependency free hash table implementation More...

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include "icl_hash.h"
Include dependency graph for icl_hash.c:

Go to the source code of this file.

Macros

#define BITS_IN_int   (sizeof(int) * CHAR_BIT)
 
#define THREE_QUARTERS   ((int)((BITS_IN_int * 3) / 4))
 
#define ONE_EIGHTH   ((int)(BITS_IN_int / 8))
 
#define HIGH_BITS   (~((unsigned int)(~0) >> ONE_EIGHTH))
 

Functions

icl_hash_ticl_hash_create (int nbuckets, unsigned int(*hash_function)(void *), int(*hash_key_compare)(void *, void *))
 Create a new hash table. More...
 
void * icl_hash_find (icl_hash_t *ht, void *key)
 Search for an entry in a hash table. More...
 
icl_entry_ticl_hash_insert (icl_hash_t *ht, void *key, void *data)
 Insert an item into the hash table. More...
 
icl_entry_ticl_hash_update_insert (icl_hash_t *ht, void *key, void *data, void **olddata)
 Replace entry in hash table with the given entry. More...
 
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. More...
 
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. More...
 
int icl_hash_dump (FILE *stream, icl_hash_t *ht)
 Dump the hash table's contents to the given file pointer. More...
 

Detailed Description

dependency free hash table implementation

Author
Keith Seymour
Jakub Kurzak

PULSAR Runtime http://icl.eecs.utk.edu/pulsar/ Copyright (C) 2012-2013 University of Tennessee.

Definition in file icl_hash.c.

Macro Definition Documentation

#define BITS_IN_int   (sizeof(int) * CHAR_BIT)

Definition at line 20 of file icl_hash.c.

#define HIGH_BITS   (~((unsigned int)(~0) >> ONE_EIGHTH))

Definition at line 23 of file icl_hash.c.

#define ONE_EIGHTH   ((int)(BITS_IN_int / 8))

Definition at line 22 of file icl_hash.c.

#define THREE_QUARTERS   ((int)((BITS_IN_int * 3) / 4))

Definition at line 21 of file icl_hash.c.

Function Documentation

icl_hash_t* icl_hash_create ( int  nbuckets,
unsigned int(*)(void *)  hash_function,
int(*)(void *, void *)  hash_key_compare 
)

Create a new hash table.

Parameters
nbuckets– number of buckets to create
hash_function– pointer to the hashing function to be used
hash_key_compare– pointer to the hash key comparison function to be used
Returns
pointer to new hash table.

Definition at line 70 of file icl_hash.c.

References icl_hash_s::buckets, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_hash_s::nbuckets, and icl_hash_s::nentries.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
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
unsigned int(* hash_function)(void *)
Definition: icl_hash.h:29
Definition: icl_hash.h:19

Here is the caller graph for this function:

int icl_hash_delete ( icl_hash_t ht,
void *  key,
void(*)(void *)  free_key,
void(*)(void *)  free_data 
)

Free one hash table entry located by key. Key and data are freed using functions.

Parameters
ht– the hash table to be freed
key– the key of the new item
free_key– pointer to function that frees the key
free_data– pointer to function that frees the data
Returns
0 on success, -1 on failure.

Definition at line 232 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, icl_hash_s::nentries, and icl_entry_s::next.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
struct icl_entry_s * next
Definition: icl_hash.h:22
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
unsigned int(* hash_function)(void *)
Definition: icl_hash.h:29
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20
int icl_hash_destroy ( icl_hash_t ht,
void(*)(void *)  free_key,
void(*)(void *)  free_data 
)

Free hash table structures. Key and data are freed using functions.

Parameters
ht– the hash table to be freed
free_key– pointer to function that frees the key
free_data– pointer to function that frees the data
Returns
0 on success, -1 on failure.

Definition at line 279 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_entry_s::key, icl_hash_s::nbuckets, and icl_entry_s::next.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
struct icl_entry_s * next
Definition: icl_hash.h:22
int nbuckets
Definition: icl_hash.h:26
void * data
Definition: icl_hash.h:21
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20

Here is the caller graph for this function:

int icl_hash_dump ( FILE *  stream,
icl_hash_t ht 
)

Dump the hash table's contents to the given file pointer.

Parameters
stream– the file to which the hash table should be dumped
ht– the hash table to be dumped
Returns
0 on success, -1 on failure.

Definition at line 319 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_entry_s::key, icl_hash_s::nbuckets, and icl_entry_s::next.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
struct icl_entry_s * next
Definition: icl_hash.h:22
int nbuckets
Definition: icl_hash.h:26
void * data
Definition: icl_hash.h:21
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20
void* icl_hash_find ( icl_hash_t ht,
void *  key 
)

Search for an entry in a hash table.

Parameters
ht– the hash table to be searched
key– the key of the item to search for
Returns
pointer to the data corresponding to the key. If the key was not found, returns NULL.

Definition at line 108 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, and icl_entry_s::next.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
struct icl_entry_s * next
Definition: icl_hash.h:22
int nbuckets
Definition: icl_hash.h:26
int(* hash_key_compare)(void *, void *)
Definition: icl_hash.h:30
void * data
Definition: icl_hash.h:21
unsigned int(* hash_function)(void *)
Definition: icl_hash.h:29
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20

Here is the caller graph for this function:

icl_entry_t* icl_hash_insert ( icl_hash_t ht,
void *  key,
void *  data 
)

Insert an item into the hash table.

Parameters
ht– the hash table
key– the key of the new item
data– pointer to the new item's data
Returns
pointer to the new item. Returns NULL on error.

Definition at line 134 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, icl_hash_s::nentries, and icl_entry_s::next.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
struct icl_entry_s * next
Definition: icl_hash.h:22
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
unsigned int(* hash_function)(void *)
Definition: icl_hash.h:29
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20

Here is the caller graph for this function:

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.

Parameters
ht– the hash table
key– the key of the new item
data– pointer to the new item's data
olddata– pointer to the old item's data (set upon return)
Returns
pointer to the new item. Returns NULL on error.

Definition at line 173 of file icl_hash.c.

References icl_hash_s::buckets, icl_entry_s::data, icl_hash_s::hash_function, icl_hash_s::hash_key_compare, icl_entry_s::key, icl_hash_s::nbuckets, icl_hash_s::nentries, and icl_entry_s::next.

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 }
icl_entry_t ** buckets
Definition: icl_hash.h:28
struct icl_entry_s * next
Definition: icl_hash.h:22
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
unsigned int(* hash_function)(void *)
Definition: icl_hash.h:29
Definition: icl_hash.h:19
void * key
Definition: icl_hash.h:20