QUARK  0.9.0
QUARK-QUeuingAndRuntimeforKernels
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
icl_hash.c File Reference
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "icl_hash.h"
#include <limits.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/Subroutines

icl_hash_ticl_hash_create (int nbuckets, unsigned int(*hash_function)(void *), int(*hash_key_compare)(void *, void *))
void * icl_hash_find (icl_hash_t *ht, void *key)
icl_entry_ticl_hash_insert (icl_hash_t *ht, void *key, void *data)
icl_entry_ticl_hash_update_insert (icl_hash_t *ht, void *key, void *data, void **olddata)
int icl_hash_delete (icl_hash_t *ht, void *key, void(*free_key)(void *), void(*free_data)(void *))
int icl_hash_destroy (icl_hash_t *ht, void(*free_key)(void *), void(*free_data)(void *))
int icl_hash_dump (FILE *stream, icl_hash_t *ht)

Detailed Description

Dependency free hash table implementation.

This simple hash table implementation should be easy to drop into any other peice of code, it does not depend on anything else :-)

Author:
Jakub Kurzak

Definition in file icl_hash.c.


Macro Definition Documentation

#define BITS_IN_int   ( sizeof(int) * CHAR_BIT )

Definition at line 24 of file icl_hash.c.

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

Definition at line 27 of file icl_hash.c.

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

Definition at line 26 of file icl_hash.c.

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

Definition at line 25 of file icl_hash.c.


Function/Subroutine 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:
[in]nbuckets– number of buckets to create
[in]hash_function– pointer to the hashing function to be used
[in]hash_key_compare– pointer to the hash key comparison function to be used
Returns:
pointer to new hash table.

Definition at line 73 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.

{
int i;
ht = (icl_hash_t*) malloc(sizeof(icl_hash_t));
assert(ht!=NULL);
if(!ht) return NULL;
ht->nentries = 0;
ht->buckets = (icl_entry_t**)malloc(nbuckets * sizeof(icl_entry_t*));
assert(ht->buckets!=NULL);
if(!ht->buckets) return NULL;
ht->nbuckets = nbuckets;
for(i=0;i<ht->nbuckets;i++)
ht->buckets[i] = NULL;
ht->hash_function = hash_function ? hash_function : hash_pjw;
ht->hash_key_compare = hash_key_compare ? hash_key_compare : string_compare;
return ht;
}

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 227 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.

{
icl_entry_t *curr, *prev;
unsigned int hash_val;
if(!ht || !key) return -1;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
prev = NULL;
for (curr=ht->buckets[hash_val]; curr != NULL; ) {
if ( ht->hash_key_compare(curr->key, key)) {
if (prev == NULL) {
ht->buckets[hash_val] = curr->next;
} else {
prev->next = curr->next;
}
if (*free_key && curr->key) (*free_key)(curr->key);
if (*free_data && curr->data) (*free_data)(curr->data);
ht->nentries++;
free(curr);
return 0;
}
prev = curr;
curr = curr->next;
}
return -1;
}
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 265 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.

{
icl_entry_t *bucket, *curr, *next;
int i;
if(!ht) return -1;
for (i=0; i<ht->nbuckets; i++) {
bucket = ht->buckets[i];
for (curr=bucket; curr!=NULL; ) {
next=curr->next;
if (*free_key && curr->key) (*free_key)(curr->key);
if (*free_data && curr->data) (*free_data)(curr->data);
free(curr);
curr=next;
}
}
if(ht->buckets) free(ht->buckets);
if(ht) free(ht);
return 0;
}

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 300 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.

{
icl_entry_t *bucket, *curr;
int i;
if(!ht) return -1;
for(i=0; i<ht->nbuckets; i++) {
bucket = ht->buckets[i];
for(curr=bucket; curr!=NULL; ) {
if(curr->key)
fprintf(stream, "icl_hash_dump: %s: %p\n", (char *)curr->key, curr->data);
curr=curr->next;
}
}
return 0;
}
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.

{
icl_entry_t* curr;
unsigned int hash_val;
if(!ht || !key) return NULL;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
if ( ht->hash_key_compare(curr->key, key))
return(curr->data);
return NULL;
}

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 135 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.

{
icl_entry_t *curr;
unsigned int hash_val;
if(!ht || !key) return NULL;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
if ( ht->hash_key_compare(curr->key, key))
return(NULL); /* key already exists */
/* if key was not found */
curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
assert(curr != NULL);
if(!curr) return NULL;
curr->key = key;
curr->data = data;
curr->next = ht->buckets[hash_val]; /* add at start */
ht->buckets[hash_val] = curr;
ht->nentries++;
return curr;
}

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 175 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.

{
icl_entry_t *curr, *prev;
unsigned int hash_val;
if(!ht || !key) return NULL;
hash_val = (* ht->hash_function)(key) % ht->nbuckets;
/* Scan bucket[hash_val] for key */
for (prev=NULL,curr=ht->buckets[hash_val]; curr != NULL; prev=curr, curr=curr->next)
/* If key found, remove node from list, free old key, and setup olddata for the return */
if ( ht->hash_key_compare(curr->key, key)) {
if (olddata != NULL) {
*olddata = curr->data;
free(curr->key);
}
if (prev == NULL)
ht->buckets[hash_val] = curr->next;
else
prev->next = curr->next;
}
/* Since key was either not found, or found-and-removed, create and prepend new node */
curr = (icl_entry_t*)malloc(sizeof(icl_entry_t));
assert(curr!=NULL);
if(curr == NULL) return NULL; /* out of memory */
curr->key = key;
curr->data = data;
curr->next = ht->buckets[hash_val]; /* add at start */
ht->buckets[hash_val] = curr;
ht->nentries++;
if(olddata!=NULL && *olddata!=NULL)
*olddata = NULL;
return curr;
}