wm: ticl

ref: fb90d152ef67420872ed6f7a479b0fa6f201a725
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"

/*
 * Destroy the hash table and, if the free_key_val flag is true, free the keys and values.
 */
static void
destroy_and_free(struct htable *ht, int free_key_val)
{
	unsigned int i;
	struct htnode *n, *tmp;

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

/*
 * Insert a new node or, if the replace flag is true, replace the value of an existing node.
 */
static int
insert_or_replace_val(struct htable *ht, void *key, void *val, int replace)
{
	unsigned int i;
	struct htnode *n, *ln;	/* current and last node */

	i = ht->hash(key, ht->cap);
	ln = NULL;
	for (n = ht->nodes[i]; n != NULL; n = n->next) {
		/* if key already exist */
		if (ht->key_cmp(key, n->key) == 0) {
			if (replace) {
				ht->val_free(n->val);
				n->val = val;
				return 0;
			} else {
				return -1;
			}
		}
		ln = n;
	}

	if (replace)	/* failed to replace */
		return -1;

	if ((n = malloc(sizeof(struct htnode))) == NULL) {
		perror("error: malloc");
		return -1;
	}
	n->key = key;
	n->val = val;
	n->next = NULL;
	/* link to the last node */
	if (ln == NULL)
		ht->nodes[i] = n;
	else
		ln->next = n;
	ht->len++;
	return 0;
}

/*
 * Remove a node or, if the replace flag is true, change the key of the node.
 */
static int
remove_or_replace_key(struct htable *ht, void *key, int replace, void *newkey)
{
	unsigned int i;
	struct htnode *n, *ln;	/* current and last node */

	i = ht->hash(key, ht->cap);
	ln = NULL;
	for (n = ht->nodes[i]; n != NULL; n = n->next) {
		if (ht->key_cmp(key, n->key) == 0) {
			ht->key_free(n->key);
			if (!replace) {
				ht->val_free(n->val);
			} else {
				if (htinsert(ht, newkey, n->val) == -1)
					return -1;
			}
			/* link to the last node */
			if (ln == NULL)
				ht->nodes[i] = n->next;
			else
				ln->next = n->next;
			free(n);
			return 0;
		}
		ln = n;
	}
	return -1;
}

struct htable *
htcreate(hash_fn *hash, key_cmp_fn *key_cmp, key_free_fn *key_free,
			val_free_fn *val_free, unsigned int cap)
{
	unsigned int i;
	struct htable *ht;

	if ((ht = malloc(sizeof(struct htable))) == NULL) {
		perror("error: malloc");
		return NULL;
	}
	if ((ht->nodes = malloc(cap * sizeof(struct htnode *))) == NULL) {
		perror("error: malloc");
		return NULL;
	}
	for (i = 0; i < cap; i++)
		ht->nodes[i] = NULL;

	ht->cap		= cap;
	ht->len		= 0;
	ht->hash	= hash;
	ht->key_cmp	= key_cmp;
	ht->key_free	= key_free;
	ht->val_free	= val_free;
	return ht;
}

void
htdestroy(struct htable *ht)
{
	destroy_and_free(ht, 1);
}

void *
htsearch(struct htable *ht, void *key)
{
	unsigned int i;
	struct htnode *n;

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

int
htinsert(struct htable *ht, void *key, void *val)
{
	return insert_or_replace_val(ht, key, val, 0);
}

int
htremove(struct htable *ht, void *key)
{
	return remove_or_replace_key(ht, key, 0, NULL);
}

int
htmodkey(struct htable *ht, void *oldkey, void *newkey)
{
	return remove_or_replace_key(ht, oldkey, 1, newkey);
}

int
htmodval(struct htable *ht, void *key, void *newval)
{
	return insert_or_replace_val(ht, key, newval, 1);
}

struct htable *
htresize(struct htable *ht, unsigned int newcap)
{
	struct htable	 *newht;
	struct htiter	  it;

	newht = htcreate(ht->hash, ht->key_cmp, ht->key_free, ht->val_free, newcap);
	if (newht == NULL)
		return NULL;

	htiter_init(&it);
	while(htiterate(ht, &it)) {
		if (htinsert(newht, it.node->key, it.node->val) == -1) {
			htdestroy(newht);
			return NULL;
		}
	}

	destroy_and_free(ht, 0);
	return newht;
}

void
htiter_init(struct htiter *it)
{
	it->index = 0;
	it->node = NULL;
}

int
htiterate(struct htable *ht, struct htiter *it)
{
	if (it->node != NULL)
		it->node = it->node->next;

	while (it->node == NULL && it->index < ht->cap) {
		it->node = ht->nodes[it->index];
		it->index++;
	}

	if (it->node != NULL)
		return 1;
	else
		return 0;
}