/*
* This file is part of libdom.
* Licensed under the MIT License,
* http://www.opensource.org/licenses/mit-license.php
* Copyright 2006 Rob Kendrick <rjek@rjek.com>
* Copyright 2006 Richard Wilson <info@tinct.net>
* Copyright 2009 Bo Yang <struggleyb.nku@gmail.com>
*/
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
#ifdef TEST_RIG
#include <stdio.h>
#endif
#include "utils/hashtable.h"
#include <libwapcaplet/libwapcaplet.h>
/* The hash table entry */
struct _dom_hash_entry {
void *key; /**< The key pointer */
void *value; /**< The value pointer */
struct _dom_hash_entry *next; /**< Next entry */
};
/* The hash table */
struct dom_hash_table {
const dom_hash_vtable *vtable; /**< Vtable */
void *pw; /**< Client data */
unsigned int nchains; /**< Number of chains */
struct _dom_hash_entry **chain; /**< The chain head */
uint32_t nentries; /**< The entries in this table */
};
/**
* Create a new hash table, and return a context for it. The memory consumption
* of a hash table is approximately 8 + (nchains * 12) bytes if it is empty.
*
* \param chains Number of chains/buckets this hash table will have. This
* should be a prime number, and ideally a prime number just
* over a power of two, for best performance and distribution
* \param vtable Client vtable
* \param pw Client private data
* \return struct dom_hash_table containing the context of this hash table or
* NULL if there is insufficent memory to create it and its chains.
*/
dom_hash_table *_dom_hash_create(unsigned int chains,
const dom_hash_vtable *vtable, void *pw)
{
dom_hash_table
*r
= malloc(sizeof(struct dom_hash_table
)); if (r == NULL) {
return NULL;
}
r->vtable = vtable;
r->pw = pw;
r->nentries = 0;
r->nchains = chains;
r
->chain
= calloc(chains
, sizeof(struct _dom_hash_entry
*)); if (r->chain == NULL) {
return NULL;
}
return r;
}
/**
* Clone a hash table.
*
* \param ht Hash table to clone.
*
* \return The cloned hash table.
*/
dom_hash_table *_dom_hash_clone(dom_hash_table *ht)
{
void *key = NULL, *nkey = NULL;
void *value = NULL, *nvalue = NULL;
uintptr_t c1, *c2 = NULL;
struct dom_hash_table *ret;
ret = _dom_hash_create(ht->nchains, ht->vtable, ht->pw);
if (ret == NULL)
return NULL;
while ( (key = _dom_hash_iterate(ht, &c1, &c2)) != NULL) {
nkey = ht->vtable->clone_key(key, ht->pw);
if (nkey == NULL) {
_dom_hash_destroy(ret);
return NULL;
}
value = _dom_hash_get(ht, key);
nvalue = ht->vtable->clone_value(value, ht->pw);
if (nvalue == NULL) {
ht->vtable->destroy_key(nkey, ht->pw);
_dom_hash_destroy(ret);
return NULL;
}
if (_dom_hash_add(ret, nkey, nvalue, false) == false) {
_dom_hash_destroy(ret);
return NULL;
}
}
return ret;
}
/**
* Destroys a hash table, freeing all memory associated with it.
*
* \param ht Hash table to destroy. After the function returns, this
* will nolonger be valid
*/
void _dom_hash_destroy(dom_hash_table *ht)
{
unsigned int i;
if (ht == NULL)
return;
for (i = 0; i < ht->nchains; i++) {
if (ht->chain[i] != NULL) {
struct _dom_hash_entry *e = ht->chain[i];
while (e) {
struct _dom_hash_entry *n = e->next;
ht->vtable->destroy_key(e->key, ht->pw);
ht->vtable->destroy_value(e->value, ht->pw);
e = n;
}
}
}
}
/**
* Adds a key/value pair to a hash table
*
* \param ht The hash table context to add the key/value pair to.
* \param key The key to associate the value with.
* \param value The value to associate the key with.
* \return true if the add succeeded, false otherwise. (Failure most likely
* indicates insufficent memory to make copies of the key and value.
*/
bool _dom_hash_add(dom_hash_table *ht, void *key, void *value,
bool replace)
{
unsigned int h, c;
struct _dom_hash_entry *e;
if (ht == NULL || key == NULL || value == NULL)
return false;
h = ht->vtable->hash(key, ht->pw);
c = h % ht->nchains;
for (e = ht->chain[c]; e; e = e->next) {
if (ht->vtable->key_isequal(key, e->key, ht->pw)) {
if (replace == true) {
e->value = value;
return true;
} else {
return false;
}
}
}
e
= malloc(sizeof(struct _dom_hash_entry
)); if (e == NULL) {
return false;
}
e->key = key;
e->value = value;
e->next = ht->chain[c];
ht->chain[c] = e;
ht->nentries++;
return true;
}
/**
* Looks up a the value associated with with a key from a specific hash table.
*
* \param ht The hash table context to look up
* \param key The key to search for
* \return The value associated with the key, or NULL if it was not found.
*/
void *_dom_hash_get(struct dom_hash_table *ht, void *key)
{
unsigned int h, c;
struct _dom_hash_entry *e;
if (ht == NULL || key == NULL)
return NULL;
h = ht->vtable->hash(key, ht->pw);
c = h % ht->nchains;
for (e = ht->chain[c]; e; e = e->next) {
if (ht->vtable->key_isequal(key, e->key, ht->pw))
return e->value;
}
return NULL;
}
/**
* Delete the key from the hashtable.
*
* \param ht The hashtable object
* \param key The key to delete
* \return The deleted value
*/
void *_dom_hash_del(struct dom_hash_table *ht, void *key)
{
unsigned int h, c;
struct _dom_hash_entry *e, *p;
void *ret;
if (ht == NULL || key == NULL)
return NULL;
h = ht->vtable->hash(key, ht->pw);
c = h % ht->nchains;
p = ht->chain[c];
for (e = p; e; p = e, e = e->next) {
if (ht->vtable->key_isequal(key, e->key, ht->pw)) {
if (p != e) {
p->next = e->next;
} else {
/* The first item in this chain is target*/
ht->chain[c] = e->next;
}
ret = e->value;
ht->nentries--;
return ret;
}
}
return NULL;
}
/**
* Iterate through all available hash keys.
*
* \param ht The hash table context to iterate.
* \param c1 Pointer to first context
* \param c2 Pointer to second context (set to 0 on first call)
* \return The next hash key, or NULL for no more keys
*/
void *_dom_hash_iterate(struct dom_hash_table *ht, unsigned long int *c1,
unsigned long int **c2)
{
struct _dom_hash_entry **he = (struct _dom_hash_entry **) c2;
if (ht == NULL)
return NULL;
if (!*he)
*c1 = -1;
else
*he = (*he)->next;
if (*he)
return (*he)->key;
while (!*he) {
(*c1)++;
if (*c1 >= ht->nchains)
return NULL;
*he = ht->chain[*c1];
}
return (*he)->key;
}
/**
* Get the number of elements in this hash table
*
* \param ht The hash table
*
* \return the number of elements
*/
uint32_t _dom_hash_get_length(struct dom_hash_table *ht)
{
return ht->nentries;
}
/*-----------------------------------------------------------------------*/
/* A simple test rig. To compile, use:
* gcc -g -o hashtest -I../ -I../../include -DTEST_RIG hashtable.c
*
* If you make changes to this hash table implementation, please rerun this
* test, and if possible, through valgrind to make sure there are no memory
* leaks or invalid memory accesses. If you add new functionality, please
* include a test for it that has good coverage along side the other tests.
*/
#ifdef TEST_RIG
/**
* Hash a pointer, returning a 32bit value.
*
* \param ptr The pointer to hash.
* \return the calculated hash value for the pointer.
*/
static inline unsigned int _dom_hash_pointer_fnv(void *ptr)
{
return (unsigned int) ptr;
}
static void *test_alloc(void *p, size_t size, void *ptr)
{
if (p != NULL) {
return NULL;
}
if (p == NULL) {
}
}
int main(int argc, char *argv[])
{
struct dom_hash_table *a, *b;
FILE *dict;
char keybuf[BUFSIZ], valbuf[BUFSIZ];
int i;
char *cow="cow", *moo="moo", *pig="pig", *oink="oink",
*chicken="chikcken", *cluck="cluck",
*dog="dog", *woof="woof", *cat="cat",
*meow="meow";
void *ret;
a = _dom_hash_create(79, _dom_hash_pointer_fnv, test_alloc, NULL);
b = _dom_hash_create(103, _dom_hash_pointer_fnv, test_alloc, NULL);
_dom_hash_add(a, cow, moo ,true);
_dom_hash_add(b, moo, cow ,true);
_dom_hash_add(a, pig, oink ,true);
_dom_hash_add(b, oink, pig ,true);
_dom_hash_add(a, chicken, cluck ,true);
_dom_hash_add(b, cluck, chicken ,true);
_dom_hash_add(a, dog, woof ,true);
_dom_hash_add(b, woof, dog ,true);
_dom_hash_add(a, cat, meow ,true);
_dom_hash_add(b, meow, cat ,true);
#define MATCH(x,y) assert(!strcmp((char *)hash_get(a, x), (char *)y)); \
assert(!strcmp((char *)hash_get(b, y), (char *)x))
MATCH(cow, moo);
MATCH(pig, oink);
MATCH(chicken, cluck);
MATCH(dog, woof);
MATCH(cat, meow);
assert(hash_get_length
(a
) == 5); assert(hash_get_length
(b
) == 5);
_dom_hash_del(a, cat);
_dom_hash_del(b, meow);
assert(hash_get
(a
, cat
) == NULL
); assert(hash_get
(b
, meow
) == NULL
);
assert(hash_get_length
(a
) == 4); assert(hash_get_length
(b
) == 4);
_dom_hash_destroy(a, NULL, NULL);
_dom_hash_destroy(b, NULL, NULL);
/* This test requires /usr/share/dict/words - a large list of English
* words. We load the entire file - odd lines are used as keys, and
* even lines are used as the values for the previous line. we then
* work through it again making sure everything matches.
*
* We do this twice - once in a hash table with many chains, and once
* with a hash table with fewer chains.
*/
a = _dom_hash_create(1031, _dom_hash_pointer_fnv, test_alloc, NULL);
b = _dom_hash_create(7919, _dom_hash_pointer_fnv, test_alloc, NULL);
dict
= fopen("/usr/share/dict/words", "r"); if (dict == NULL) {
fprintf(stderr
, "Unable to open /usr/share/dict/words - \ extensive testing skipped.\n");
}
_dom_hash_add(a, keybuf, valbuf, true);
_dom_hash_add(b, keybuf, valbuf, true);
}
for (i = 0; i < 5; i++) {
fseek(dict
, 0, SEEK_SET
);
}
}
_dom_hash_destroy(a, NULL, NULL);
_dom_hash_destroy(b, NULL, NULL);
return 0;
}
#endif