QUARK  0.9.0
QUARK-QUeuingAndRuntimeforKernels
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
icl_hash.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Types

struct  icl_entry_s
struct  icl_hash_s

Macros

#define icl_hash_foreach(ht, tmpint, tmpent, kp, dp)

Typedefs

typedef struct icl_entry_s icl_entry_t
typedef struct icl_hash_s icl_hash_t

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 *, void *)
icl_entry_ticl_hash_insert (icl_hash_t *, void *, void *)
icl_entry_ticl_hash_update_insert (icl_hash_t *, void *, void *, void **)
int icl_hash_destroy (icl_hash_t *, void(*)(void *), void(*)(void *))
int icl_hash_dump (FILE *, icl_hash_t *)
int icl_hash_delete (icl_hash_t *ht, void *key, void(*free_key)(void *), void(*free_data)(void *))

Detailed Description

Header file for icl_hash routines.

Definition in file icl_hash.h.


Macro Definition Documentation

#define icl_hash_foreach (   ht,
  tmpint,
  tmpent,
  kp,
  dp 
)
Value:
for (tmpint=0;tmpint<ht->nbuckets; tmpint++) \
for (tmpent=ht->buckets[tmpint]; \
tmpent!=NULL&&((kp=tmpent->key)!=NULL)&&((dp=tmpent->data)!=NULL); \
tmpent=tmpent->next)

Definition at line 48 of file icl_hash.h.


Typedef Documentation

typedef struct icl_entry_s icl_entry_t
typedef struct icl_hash_s icl_hash_t

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 ,
void(*)(void *)  ,
void(*)(void *)   
)
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 ,
void *  ,
void *   
)
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;
}