wm: ticl

ref: 5ff9649e6c51bae0dd09f218e4943fa5f4d458be
dir: /htable.c/

/*
 * This work is dedicated to the public domain.
 * See COPYING file for more information.
 */

#include <stdlib.h>
#include <stdio.h>

#include "htable.h"
#include "utils.h"

static unsigned int
hash(Htable *ht, void *key)
{
	unsigned int i;
	unsigned int sum = 0;

	/* very simple hash function */
	for (i = 0; i < (unsigned int)ht->keylenfn(key); i++) {
		sum += ((unsigned char *)key)[i] * (i + 1);
	}
	return (sum % ht->cap);
}

Htable *
htcreate(KeyLenFn *keylenfn, KeyCmpFn *keycmpfn, FreeKeyFn *freekeyfn, FreeValFn *freevalfn, unsigned int cap)
{
	unsigned int i;
	Htable *ht;

	if (keylenfn == NULL)	fatal("keylenfn cannot be NULL");
	if (keycmpfn == NULL)	fatal("keycmpfn cannot be NULL");

	ht = ecalloc(1, sizeof(Htable));
	ht->nodes	= ecalloc(cap, sizeof(Htnode));
	ht->cap		= cap;
	ht->len		= 0;
	ht->keylenfn	= keylenfn;
	ht->keycmpfn	= keycmpfn;
	ht->freekeyfn	= freekeyfn;
	ht->freevalfn	= freevalfn;

	for (i = 0; i < cap; i++)
		ht->nodes[i] = NULL;
	return ht;
}

static void
__htdestroy(Htable *ht, int dofree)
{
	unsigned int i;
	Htnode *n;
	Htnode *tmp;

	for (i = 0; i < ht->cap; i++) {
		for (n = ht->nodes[i]; n != NULL;) {
			if (dofree) {
				ht->freekeyfn(n->key);
				ht->freevalfn(n->val);
			}
			tmp = n;
			n = n->next;
			free(tmp);
		}
	}
	free(ht->nodes);
	free(ht);
}

void
htdestroy(Htable *ht)
{
	__htdestroy(ht, 1);
}

void *
htsearch(Htable *ht, void *key)
{
	unsigned int i;
	Htnode *n;

	i = hash(ht, key);
	for (n = ht->nodes[i]; n != NULL; n = n->next) {
		if (ht->keycmpfn(key, n->key) == 0)
			return n->val;
	}
	return NULL;
}

int
htinsert(Htable *ht, void *key, void *val)
{
	unsigned int i;
	Htnode *n;	/* current node */
	Htnode *pn;	/* previous node */

	pn = NULL;
	i = hash(ht, key);
	for (n = ht->nodes[i]; n != NULL; n = n->next) {
		/*if key already exist, override value */
		if (ht->keycmpfn(key, n->key) == 0) {
			ht->freekeyfn(n->key);
			ht->freevalfn(n->val);
			n->key = key;
			n->val = val;
			return -1;
		}
		pn = n;
	}

	/* create a new node */
	n = ecalloc(1, sizeof(Htnode));
	n->key = key;
	n->val = val;
	n->next = NULL;
	/* link to the previous node */
	if (pn == NULL)
		ht->nodes[i] = n;
	else
		pn->next = n;
	/* increment the hash table length */
	ht->len++;
	return 1;
}

static int
__htremove(Htable *ht, void *key, int freeval)
{
	unsigned int i;
	Htnode *n;	/* current node */
	Htnode *pn;	/* previous node */

	pn = NULL;
	i = hash(ht, key);
	for (n = ht->nodes[i]; n != NULL; n = n->next) {
		if (ht->keycmpfn(key, n->key) == 0) {
			/* free node memory */
			ht->freekeyfn(n->key);
			if (freeval)
				ht->freevalfn(n->val);
			/* link to the previous node */
			if (pn == NULL)
				ht->nodes[i] = n->next;
			else
				pn->next = n->next;
			/* free the node */
			free(n);
			return 1;
		}
		pn = n;
	}
	return -1;
}

int
htremove(Htable *ht, void *key)
{
	return __htremove(ht, key, 1);
}

int
htsetkey(Htable *ht, void *oldkey, void *newkey)
{
	void *val = NULL;
	if ((val = htsearch(ht, oldkey)) == NULL)
		return -1;
	__htremove(ht, oldkey, 0);
	htinsert(ht, newkey, val);
	return 1;
}

void
htresize(Htable *ht, unsigned int ncap)
{
	unsigned int i, tmp;
	Htable *nht;	/* new hash table */
	Htnode *n;	/* current node */
	Htnode **list;	/* list of nodes */

	/* create a new hash table */
	nht = htcreate(ht->keylenfn, ht->keycmpfn, ht->freekeyfn, ht->freevalfn, ncap);
	for (i = 0; i < ht->cap; i++) {
		for (n = ht->nodes[i]; n != NULL; n = n->next)
			htinsert(nht, n->key, n->val);
	}

	/* swap old hash table with new one */
	list = ht->nodes;
	ht->nodes = nht->nodes;
	nht->nodes = list;

	tmp = ht->cap;
	ht->cap = nht->cap;
	nht->cap = tmp;

	tmp = ht->len;
	ht->len = nht->len;
	nht->len = tmp;

	/* destroy new(old) hash table */
	__htdestroy(nht, 0);
}

int
htiterate(Htable *ht, Htiter *it)
{
	if (it->index == 0 && it->node == NULL) {
		it->index = 0;
		it->node = ht->nodes[0];
	} else {
		it->node = it->node->next;
	}

	while (it->index < ht->cap) {
		while (it->node != NULL) {
			return 1;
			it->node = it->node->next;
		}
		it->index++;
		it->node = ht->nodes[it->index];
	}
	return 0;
}