/* $Id: hash.c 1541 2006-02-27 21:11:55Z mipsator $ */
/*
* Copyright (c) 2003-2005 Damien Couderc
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
* - Neither the name of the copyright holder(s) nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
*/
/*
* Credits for patches :
* - Marek Habersack
*/
/*******************************************************************
* *
* Hash-coding functions *
* *
*******************************************************************/
#include <stdlib.h>
#include "hash.h"
#include "compat/pmk_stdio.h"
#include "compat/pmk_string.h"
/*#define HASH_DEBUG 1*/
#ifdef HASH_DEBUG
#include "common.h"
#endif
/******************
* hash_compute() *
***********************************************************************
DESCR
compute hash (perfect hashing)
IN
key : key string
OUT
resulting hash
***********************************************************************/
unsigned int hash_compute(char *key, size_t table_size) {
unsigned int len = 0,
hash = 0;
unsigned char c;
c = *key;
while (c != '\0') {
/* sum all characters with modulo */
hash = (hash + (int) c) % table_size;
c = *key;
key++;
len++;
}
/* add the len always with modulo */
hash = (hash + len) % table_size;
return(hash);
}
/***************
* hash_init() *
***********************************************************************
DESCR
init hash structure of character strings
IN
table_size : number of hash elements
OUT
a pointer to the hash structure
***********************************************************************/
htable *hash_init(size_t table_size) {
return(hash_init_adv(table_size, (void *(*)(void *))strdup,
free, hash_str_append));
}
/*******************
* hash_init_adv() *
***********************************************************************
DESCR
init hash structure of objects
IN
table_size : number of hash elements
dupfunc : function to duplicate an object
freefunc : function to free an object
appdfunc : function to create appended object
OUT
a pointer to the hash structure
NOTE
append function will have three arguments (original object,
value to append, misc data) and will return the resulting object
(see hash_append_str for an example).
***********************************************************************/
htable *hash_init_adv(size_t table_size, void *(*dupfunc)(void *),
void (*freefunc)(void *),
void *(*appdfunc)(void *, void *, void *)) {
htable *pht;
hnode *phn;
size_t i;
/* allocate hash table */
pht = (htable *) malloc(sizeof(htable));
if (pht != NULL) {
/* allocate node table */
phn = (hnode *) malloc(sizeof(hnode) * table_size);
if (phn == NULL) {
/* allocation failed then
deallocate and return NULL */
free(pht);
return(NULL);
}
} else {
/* allocation failed, return NULL */
return(NULL);
}
for(i = 0 ; i < table_size ; i++) {
phn[i].first = NULL;
phn[i].last = NULL;
}
/* finish init */
pht->size = table_size;
pht->count = 0;
pht->autogrow = false; /* disabled by default */
pht->dupobj = dupfunc;
pht->freeobj = freefunc;
pht->appdobj = appdfunc;
pht->nodetab = phn;
return(pht);
}
/*****************
* hash_resize() *
***********************************************************************
DESCR
resizing hash table
IN
ht : hash table to resize
newsize : new size
OUT
boolean
***********************************************************************/
bool hash_resize(htable *ht, size_t newsize) {
hcell *phc,
*next;
hnode *newhn;
size_t c = 0,
i;
unsigned int h;
/* allocate new node table */
newhn = (hnode *) malloc(sizeof(hnode) * newsize);
if (newhn == NULL)
return(false);
/* init */
for (i = 0 ; i < newsize ; i++) {
newhn[i].first = NULL;
newhn[i].last = NULL;
}
for (i = 0 ; i < ht->size ; i++) {
phc = ht->nodetab[i].first;
while (phc != NULL) {
h = hash_compute(phc->key, newsize);
next = phc->next;
hash_add_cell(&newhn[h], phc);
phc = next;
c++;
}
}
free(ht->nodetab);
ht->nodetab = newhn;
ht->size = newsize;
return(true);
}
/*******************
* hash_set_grow() *
***********************************************************************
DESCR
set hash table as automatically resizable
IN
ht : hash table to set
OUT
-
***********************************************************************/
void hash_set_grow(htable *ht) {
ht->autogrow = true;
}
/******************
* hash_destroy() *
***********************************************************************
DESCR
destroy hash table
IN
pht : hash table to remove
OUT
number of keys deleted
***********************************************************************/
size_t hash_destroy(htable *pht) {
hcell *p,
*t;
size_t s,
c = 0;
unsigned int i;
if (pht == NULL)
return(0);
s = pht->size;
for(i = 0 ; i < s ; i++) {
p = pht->nodetab[i].first;
t = NULL;
while (p != NULL) {
t = p->next;
hash_free_hcell(pht, p);
c++; /* removed one more key */
p = t;
}
}
free(pht->nodetab);
free(pht);
pht = NULL;
return(c);
}
/**************
* hash_add() *
***********************************************************************
DESCR
add a key in the hash table
IN
pht : hash structure
key : key string
value : value object
OUT
return an error code
HASH_ADD_FAIL : addition failed.
HASH_ADD_OKAY : added (no collision).
HASH_ADD_COLL : added (collision, key chained).
HASH_ADD_UPDT : key already exists, change value.
***********************************************************************/
unsigned int hash_add(htable *pht, char *key, void *value) {
return(hash_update(pht, key, value));
}
/*****************
* hash_update() *
***********************************************************************
DESCR
update or add a key in the hash table
IN
pht : hash structure
key : key string
value : value object
OUT
return an error code
HASH_ADD_FAIL : addition failed.
HASH_ADD_OKAY : added (no collision).
HASH_ADD_COLL : added (collision, key chained).
HASH_ADD_UPDT : key already exists, change value.
***********************************************************************/
unsigned int hash_update(htable *pht, char *key, void *value) {
unsigned int hash,
rval;
hnode *phn;
hcell *phc = NULL;
size_t size;
rval = HASH_ADD_FAIL;
size = pht->size;
/* test remaing free cells */
if (pht->count >= size) {
/* number of cell is higher than the supposed table size */
if (pht->autogrow == false) {
/* fixed size */
return(HASH_ADD_FAIL);
} else {
/* resize the hash table (long) */
if (hash_resize(pht, size * 2) == false) {
/* cannot resize the hash */
return(HASH_ADD_FAIL);
}
}
}
phc = (hcell *) malloc(sizeof(hcell));
if (phc == NULL)
return(rval);
/* if okay put key & value in a new cell */
if (strlcpy_b(phc->key, key, sizeof(phc->key)) == false) {
hash_free_hcell(pht, phc);
return(HASH_ADD_FAIL);
}
phc->value = value;
/* compute hash code */
hash = hash_compute(key, size);
phn = &pht->nodetab[hash];
rval = hash_add_cell(phn, phc);
if (rval == HASH_ADD_OKAY || rval == HASH_ADD_COLL)
pht->count++;
return(rval);
}
/*********************
* hash_update_dup() *
***********************************************************************
DESCR
update or add a key in the hash table but duplicate the value
IN
pht : hash structure
key : key string
value : value object
OUT
return an error code
HASH_ADD_FAIL : addition failed.
HASH_ADD_OKAY : added (no collision).
HASH_ADD_COLL : added (collision, key chained).
HASH_ADD_UPDT : key already exists, change value.
***********************************************************************/
unsigned int hash_update_dup(htable *pht, char *key, void *value) {
return(hash_update(pht, key, pht->dupobj(value)));
}
/*******************
* hash_add_cell() *
***********************************************************************
DESCR
add a new cell in a node
IN
phn : storage node
phc : cell to add
OUT
return an error code
HASH_ADD_OKAY : added (no collision).
HASH_ADD_COLL : added (collision, key chained).
HASH_ADD_UPDT : key already exists, change value.
NOTE
this function does not increment the cell number of the hash table.
***********************************************************************/
unsigned int hash_add_cell(hnode *phn, hcell *phc) {
hcell *np;
phc->next = NULL;
if (phn->first == NULL) {
/* hash code unused */
phn->first = phc;
phn->last = phc;
return(HASH_ADD_OKAY);
} else {
/* collision, hash code already used */
np = phn->first;
/* looking for last element */
while (1) {
if (strncmp(phc->key, np->key, sizeof(phc->key)) == 0) {
/* key already exists */
np->value = phc->value;
phc->value = NULL; /* XXX useless ??? */
/* new cell no longer needed, free struct only */
free(phc);
return(HASH_ADD_UPDT);
} else {
if (np->next == NULL) {
/* last element found */
phn->last = phc;
/* chaining new cell */
np->next = phc;
return(HASH_ADD_COLL);
} else {
np = np->next;
}
}
}
}
}
/********************
* hash_add_array() *
***********************************************************************
DESCR
add an array into the hash table
IN
ht : storage hash table
ary : array to add
size : size of the array
OUT
boolean
***********************************************************************/
bool hash_add_array(htable *pht, hpair *php, size_t size) {
return(hash_add_array_adv(pht, php, size, (void *(*)(void *)) strdup));
}
/************************
* hash_add_array_adv() *
***********************************************************************
DESCR
add an array into the hash table
IN
ht : storage hash table
ary : array to add
size : size of the array
dup_func : object duplication function
OUT
boolean
***********************************************************************/
bool hash_add_array_adv(htable *pht, hpair *php, size_t size, void *(dupfunc)(void *)) {
bool error = false,
rval = false;
htable *pmht;
unsigned int i;
pmht = hash_init(size);
if (pmht == NULL)
return(false);
for (i = 0 ; (i < size) && (error == false) ; i ++) {
if (hash_add(pmht, php[i].key, dupfunc(php[i].value)) == HASH_ADD_FAIL)
error = true;
}
if (error == false) {
hash_merge(pht, pmht);
rval = true;
}
hash_destroy(pmht);
return(rval);
}
/*****************
* hash_append() *
***********************************************************************
DESCR
append a value to the existing value
IN
pht : hash structure
key : key to be appended
value : value to append
misc : extra data to transmit to append function
OUT
return an error code.
HASH_ADD_OKAY : added (no collision).
HASH_ADD_COLL : added (collision, key chained).
HASH_ADD_UPDT : key already exists, change value.
***********************************************************************/
unsigned int hash_append(htable *pht, char *key, void *value, void *misc) {
unsigned int rval;
void *pobj,
*robj;
if (value == NULL) {
#ifdef HASH_DEBUG
debugf("hash_append : value is null");
#endif
return(HASH_ADD_FAIL);
}
if (pht->appdobj == NULL) {
#ifdef HASH_DEBUG
debugf("hash_append : appobj is null");
#endif
return(HASH_ADD_FAIL);
}
pobj = hash_get(pht, key);
if (pobj == NULL) {
/* no previous value, adding given data */
rval = hash_add(pht, key, value);
} else {
robj = pht->appdobj(pobj, value, misc);
if (robj != NULL) {
rval = hash_add(pht, key, robj);
if (rval == HASH_ADD_UPDT)
rval = HASH_ADD_APPD; /* not an update as we append */
} else {
#ifdef HASH_DEBUG
debugf("hash_append : robj is null");
#endif
rval = HASH_ADD_FAIL;
}
}
return(rval);
}
/*****************
* hash_delete() *
***********************************************************************
DESCR
remove a key from the hash table
IN
pht : hash table
key : key to search
OUT
-
***********************************************************************/
void hash_delete(htable *pht, char *key) {
hcell *phc,
*last;
unsigned int hash;
/* compute hash code */
hash = hash_compute(key, pht->size);
phc = pht->nodetab[hash].first;
last = NULL;
while (phc != NULL) {
/* hash not empty */
if (strncmp(key, phc->key, MAX_HASH_KEY_LEN) == 0) {
/* found key */
if (last == NULL) {
/* first cell */
if (phc->next == NULL) {
/* only one cell */
pht->nodetab[hash].first = NULL;
pht->nodetab[hash].last = NULL;
} else {
/* re-link with next cell */
pht->nodetab[hash].first = phc->next;
}
} else {
last->next = phc->next;
if (phc->next == NULL) {
/* delete last cell, update node */
pht->nodetab[hash].last = last;
}
}
hash_free_hcell(pht, phc);
phc = NULL;
pht->count--;
} else {
/* go to next cell */
last = phc;
phc = phc->next;
}
}
/* key not found */
}
/******************
* hash_extract() *
***********************************************************************
DESCR
remove a key from the hash table
IN
pht : hash table
key : key to search
OUT
-
***********************************************************************/
void *hash_extract(htable *pht, char *key) {
hcell *phc,
*last;
unsigned int hash;
void *data = NULL;
/* compute hash code */
hash = hash_compute(key, pht->size);
phc = pht->nodetab[hash].first;
last = NULL;
while (phc != NULL) {
/* hash not empty */
if (strncmp(key, phc->key, MAX_HASH_KEY_LEN) == 0) {
/* found key */
if (last == NULL) {
/* first cell */
if (phc->next == NULL) {
/* only one cell */
pht->nodetab[hash].first = NULL;
pht->nodetab[hash].last = NULL;
} else {
/* re-link with next cell */
pht->nodetab[hash].first = phc->next;
}
} else {
last->next = phc->next;
if (phc->next == NULL) {
/* delete last cell, update node */
pht->nodetab[hash].last = last;
}
}
data = phc->value;
phc->value = NULL;
hash_free_hcell(pht, phc);
pht->count--;
break;
} else {
/* go to next cell */
last = phc;
phc = phc->next;
}
}
/* key not found */
return(data);
}
/**************
* hash_get() *
***********************************************************************
DESCR
get a key from the hash table
IN
pht : hash table
key : key to search
OUT
return the value or NULL
***********************************************************************/
void *hash_get(htable *pht, char *key) {
hcell *phc;
unsigned int hash;
/* compute hash code */
hash = hash_compute(key, pht->size);
phc = pht->nodetab[hash].first;
while (phc != NULL) {
/* hash not empty */
#ifdef HASH_DEBUG
debugf("hash_get : comparing with '%s'", phc->key);
#endif
if (strncmp(key, phc->key, MAX_HASH_KEY_LEN) == 0) {
/* found key, return pointer on value */
return(phc->value);
} else {
/* go to next cell */
phc = phc->next;
}
}
/* key not found */
return(NULL);
}
/****************
* hash_merge() *
***********************************************************************
DESCR
merge one hash table into another
IN
dst_ht : destination table
src_ht : table to merge
OUT
number of merged key
***********************************************************************/
size_t hash_merge(htable *dst_ht, htable *src_ht) {
hcell *p;
size_t s,
c = 0;
unsigned int i;
/* get table size */
s = src_ht->size;
for(i = 0 ; i < s ; i++) {
p = src_ht->nodetab[i].first;
while (p != NULL) {
/* add the key in dst_ht */
if (hash_add(dst_ht, p->key, p->value) != HASH_ADD_FAIL) {
/* merged one more key */
c++;
/* unset p->value to prevent deletion */
p->value = NULL;
}
p = p->next;
}
}
/* return count of merged keys */
return(c);
}
/****************
* hash_nbkey() *
***********************************************************************
DESCR
get number of keys
IN
pht : hash table
OUT
number of keys
***********************************************************************/
size_t hash_nbkey(htable *pht) {
return(pht->count);
}
/***************
* hash_keys() *
***********************************************************************
DESCR
get the keys of the hash table
IN
pht : hash table
OUT
hkeys structure
NOTE
don't forget to free the array after use.
***********************************************************************/
hkeys *hash_keys(htable *pht) {
hcell *p;
hkeys *phk;
unsigned int i,
j = 0;
/* init hkeys struct to be returned */
phk = (hkeys *)malloc(sizeof(hkeys));
if (phk != NULL) {
if (pht->count == 0)
return(NULL);
phk->nkey = pht->count;
/* create an array with a size of the number of keys */
phk->keys = (char **)malloc(sizeof(char *) * phk->nkey);
if (phk->keys != NULL) {
for(i = 0 ; i < pht->size ; i++) {
p = pht->nodetab[i].first;
while (p != NULL) {
/* add the key in key_ary */
phk->keys[j] = p->key;
j++;
p = p->next;
}
}
return(phk);
} else {
#ifdef HASH_DEBUG
debugf("keys alloc failed");
#endif
/* free allocated space only */
free(phk);
}
#ifdef HASH_DEBUG
} else {
debugf("hkeys struct alloc failed");
#endif
}
return(NULL);
}
/**********************
* hash_keys_sorted() *
***********************************************************************
DESCR
get the sorted list of keys of the hash table
IN
pht : hash table
OUT
return an hkeys structure
NOTE
don't forget to free the array after use
***********************************************************************/
static int hash_strcmp(const void *a, const void *b) {
return(strcmp(*(char * const *)a, *(char * const *) b));
}
hkeys *hash_keys_sorted(htable *pht) {
hkeys *phk;
/* build hkey structure */
phk = hash_keys(pht);
if (phk != NULL) {
/* sort key names */
qsort((void *) phk->keys, phk->nkey, sizeof(char *),
hash_strcmp);
}
return(phk);
}
/*********************
* hash_free_hcell() *
***********************************************************************
DESCR
free memory allocated to the hcell structure
IN
phc : structure to free
OUT
-
***********************************************************************/
void hash_free_hcell(htable *pht, hcell *phc) {
if (phc != NULL) {
if (phc->value != NULL) {
if (pht->freeobj != NULL)
#ifdef HASH_DEBUG
debugf("free phcell '%s' data", phc->key);
#endif
pht->freeobj(phc->value);
}
#ifdef HASH_DEBUG
debugf("free phcell '%s'", phc->key);
#endif
free(phc);
}
}
/*********************
* hash_free_hkeys() *
***********************************************************************
DESCR
free memory allocated to the hkeys structure
IN
phk : structure to free
OUT
-
***********************************************************************/
void hash_free_hkeys(hkeys *phk) {
/* doesn't free pointed values */
free(phk->keys);
free(phk);
}
/*********************
* hash_str_append() *
***********************************************************************
DESCR
append function for string hash
IN
orig : XXX
value : XXX
sep : XXX
OUT
-
***********************************************************************/
void *hash_str_append(void *orig, void *value, void *sep) {
char *pbuf;
size_t s;
/* compute needed space */
if (sep != NULL) {
s = strlen((char *) sep);
} else {
s = 0;
}
s = s + strlen((char *) orig) + strlen((char *) value) + 1;
/* allocate space */
pbuf = (char *) malloc(s);
if (strlcpy_b(pbuf, orig, s) == false) {
free(value);
free(pbuf);
#ifdef HASH_DEBUG
debugf("hash_str_append : strlcpy1 failed");
#endif
return(NULL);
}
if ((sep != NULL) && (pbuf[0] != '\0')) {
/* adding separator if provided and if
string is not empty */
if (strlcat_b(pbuf, (char *) sep, s) == false) {
free(value);
free(pbuf);
#ifdef HASH_DEBUG
debugf("hash_str_append : strlcat1 failed");
#endif
return(NULL);
}
}
if (strlcat_b(pbuf, value, s) == false) {
free(value);
free(pbuf);
#ifdef HASH_DEBUG
debugf("hash_str_append : strlcat2 failed");
#endif
return(NULL);
}
free(value);
return((void *) pbuf);
}
/* vim: set noexpandtab tabstop=4 softtabstop=4 shiftwidth=4: */
syntax highlighted by Code2HTML, v. 0.9.1