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_t *	icl_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_t *	icl_hash_insert (icl_hash_t *, void *, void *)
icl_entry_t *	icl_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.

{
    icl_hash_t *ht;
    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;
}