ports//devel/libdict/work/libdict-0.2.1/hashtable.c

/*
 * hashtable.c
 *
 * Implementation for chained hash table.
 * Copyright (C) 2001 Farooq Mela.
 *
 * $Id: hashtable.c,v 1.11 2001/12/02 07:23:35 farooq Exp $
 *
 * cf. [Gonnet 1984], [Knuth 1998]
 */

#include <stdlib.h>

#include "hashtable.h"
#include "dict_private.h"

/*
 * We store the untruncated hash value in the `hash' field. This speeds up
 * searching and allows us to resize without recomputing the original hash
 * value.
 *
 * If it weren't for iterators, there would be no reason have a `prev' field.
 */

typedef struct hash_node hash_node;
struct hash_node {
	void		*key;
	void		*dat;
	unsigned	 hash;
	hash_node	*next;
	hash_node	*prev;
};

struct hashtable {
	hash_node		**table;
	unsigned		  size;
	dict_cmp_func	  key_cmp;
	dict_hsh_func	  key_hash;
	dict_del_func	  key_del;
	dict_del_func	  dat_del;
	unsigned		  count;
};

struct hashtable_itor {
	hashtable	*table;
	hash_node	*node;
	unsigned	 slot;
};

hashtable *
hashtable_new(dict_cmp_func key_cmp, dict_hsh_func key_hash,
			  dict_del_func key_del, dict_del_func dat_del, unsigned size)
{
	hashtable *table;
	unsigned i;

	ASSERT(key_hash != NULL);
	ASSERT(size != 0);

	if ((table = MALLOC(sizeof(*table))) == NULL)
		return NULL;
	if ((table->table = MALLOC(size * sizeof(hash_node *))) == NULL) {
		FREE(table);
		return NULL;
	}
	for (i = 0; i < size; i++)
		table->table[i] = NULL;

	table->size = size;
	table->key_cmp = key_cmp ? key_cmp : dict_ptr_cmp;
	table->key_hash = key_hash;
	table->key_del = key_del;
	table->dat_del = dat_del;
	table->count = 0;

	return table;
}

dict *
hashtable_dict_new(dict_cmp_func key_cmp, dict_hsh_func key_hash,
				   dict_del_func key_del, dict_del_func dat_del, unsigned size)
{
	dict *dct;
	hashtable *table;

	ASSERT(key_hash != NULL);
	ASSERT(size != 0);

	if ((dct = MALLOC(sizeof(*dct))) == NULL)
		return NULL;

	table = hashtable_new(key_cmp, key_hash, key_del, dat_del, size);
	if (table == NULL) {
		FREE(dct);
		return NULL;
	}

	dct->_object = table;
	dct->_inew = (inew_func)hashtable_dict_itor_new;
	dct->_destroy = (destroy_func)hashtable_destroy;
	dct->_insert = (insert_func)hashtable_insert;
	dct->_probe = (probe_func)hashtable_probe;
	dct->_search = (search_func)hashtable_search;
	dct->_csearch = (csearch_func)hashtable_csearch;
	dct->_remove = (remove_func)hashtable_remove;
	dct->_empty = (empty_func)hashtable_empty;
	dct->_walk = (walk_func)hashtable_walk;
	dct->_count = (count_func)hashtable_count;

	return dct;
}

void
hashtable_destroy(hashtable *table, int del)
{
	ASSERT(table != NULL);

	hashtable_empty(table, del);
	FREE(table->table);
	FREE(table);
}

int
hashtable_insert(hashtable *table, void *key, void *dat, int overwrite)
{
	unsigned hash;
	hash_node *node, *add;

	ASSERT(table != NULL);

	hash = table->key_hash(key);

	for (node = table->table[hash % table->size]; node; node = node->next)
		if (hash == node->hash && table->key_cmp(key, node->key) == 0) {
			if (overwrite == 0)
				return 1;
			if (table->key_del)
				table->key_del(node->key);
			if (table->dat_del)
				table->dat_del(node->dat);
			node->key = key;
			node->dat = dat;
			return 0;
		}

	if ((add = MALLOC(sizeof(*add))) == NULL)
		return -1;
	add->key = key;
	add->dat = dat;
	add->hash = hash;
	add->prev = NULL;

	hash %= table->size;
	add->next = table->table[hash];
	if (table->table[hash])
		table->table[hash]->prev = add;
	table->table[hash] = add;
	table->count++;

	return 0;
}

int
hashtable_probe(hashtable *table, void *key, void **dat)
{
	unsigned hash, mhash;
	hash_node *node, *prev, *add;
	void *tmp;

	ASSERT(table != NULL);
	ASSERT(dat != NULL);

	hash = table->key_hash(key);
	mhash = hash % table->size;

	prev = NULL;
	node = table->table[mhash];
	for (; node; prev = node, node = node->next)
		if (hash == node->hash && table->key_cmp(key, node->key) == 0)
			break;
	if (node) {
		if (prev) { /* Tranpose. */
			SWAP(prev->key, node->key, tmp);
			SWAP(prev->dat, node->dat, tmp);
			SWAP(prev->hash, node->hash, hash);
			node = prev;
		}
		*dat = node->dat;
		return 0;
	}

	if ((add = MALLOC(sizeof(*add))) == NULL)
		return -1;
	add->key = key;
	add->dat = *dat;
	add->hash = hash;
	add->prev = NULL;

	add->next = table->table[mhash];
	if (table->table[mhash])
		table->table[mhash]->prev = add;
	table->table[mhash] = add;
	table->count++;
	return 1;
}

void *
hashtable_search(hashtable *table, const void *key)
{
	unsigned hash;
	hash_node *node, *prev;
	void *tmp;

	ASSERT(table != NULL);

	hash = table->key_hash(key);
	prev = NULL;
	node = table->table[hash % table->size];
	for (; node; prev = node, node = node->next)
		if (hash == node->hash && table->key_cmp(key, node->key) == 0)
			break;
	if (node) {
		if (prev) {
			/*
			 * Tranpose. This typically offers better performance than move-to-
			 * front, but requires a fairly large number of accesses to
			 * take a randomly ordered chain and re-arrange it to nearly
			 * optimal. According to [Gonnet 1984] it may take Big-Omega(n^2)
			 * to come within 1+epsilon of the final state.
			 */
			SWAP(prev->key, node->key, tmp);
			SWAP(prev->dat, node->dat, tmp);
			SWAP(prev->hash, node->hash, hash);
			node = prev;
		}
		/* Node was already at front of list. */
		return node->dat;
	}
	return NULL;
}

const void *
hashtable_csearch(const hashtable *table, const void *key)
{
	ASSERT(table != NULL);

	/*
	 * Cast OK, we want to be able to tranpose, which doesnt modify the
	 * contents of table, only the ordering of items on the chain.
	 */
	return hashtable_search((hashtable *)table, key);
}

int
hashtable_remove(hashtable *table, const void *key, int del)
{
	hash_node *node, *prev;
	unsigned hash, mhash;

	ASSERT(table != NULL);

	hash = table->key_hash(key);
	mhash = hash % table->size;

	prev = NULL;
	node = table->table[mhash];
	for (; node; prev = node, node = node->next)
		if (hash == node->hash && table->key_cmp(key, node->key) == 0)
			break;
	if (node == NULL)
		return -1;

	if (prev)
		prev->next = node->next;
	else
		table->table[mhash] = node->next;

	if (node->next)
		node->next->prev = prev;

	if (del) {
		if (table->key_del)
			table->key_del(node->key);
		if (table->dat_del)
			table->dat_del(node->dat);
	}
	FREE(node);
	table->count--;
	return 0;
}

void
hashtable_empty(hashtable *table, int del)
{
	hash_node *node, *next;
	hash_node **tbl;
	unsigned slot, size;

	ASSERT(table != NULL);

	tbl = table->table;
	size = table->size;

	for (slot = 0; slot < size; slot++) {
		if ((node = tbl[slot]) != NULL) {
			tbl[slot] = NULL;
			do {
				next = node->next;
				if (del) {
					if (table->key_del)
						table->key_del(node->key);
					if (table->dat_del)
						table->dat_del(node->dat);
				}
				FREE(node);
			} while ((node = next) != NULL);
		}
	}

	table->count = 0;
}

void
hashtable_walk(hashtable *table, dict_vis_func visit)
{
	hash_node *node;
	unsigned i;

	ASSERT(table != NULL);
	ASSERT(visit != NULL);

	for (i = 0; i < table->size; i++)
		for (node = table->table[i]; node; node = node->next)
			if (visit(node->key, node->dat) == 0)
				goto out;
out: ;
}

unsigned
hashtable_count(const hashtable *table)
{
	ASSERT(table != NULL);

	return table->count;
}

unsigned
hashtable_size(const hashtable *table)
{
	ASSERT(table != NULL);

	return table->size;
}

unsigned
hashtable_slots_used(const hashtable *table)
{
	unsigned i, count = 0;

	ASSERT(table != NULL);

	for (i = 0; i < table->size; i++)
		if (table->table[i])
			count++;
	return count;
}

int
hashtable_resize(hashtable *table, unsigned size)
{
	hash_node **ntable;
	hash_node *node, *next;
	unsigned i, hash;

	ASSERT(table != NULL);
	ASSERT(size != 0);

	if (table->size == size)
		return 0;

	if ((ntable = MALLOC(size * sizeof(hash_node *))) == NULL)
		return -1;

	for (i = 0; i < size; i++)
		ntable[i] = NULL;

	/*
	 * This way of resizing completely reverses(!) the effects of the trans-
	 * positions that we have been doing in probes and lookups. Hopefully
	 * resizing the hashtable is something that is done rarely or not at all,
	 * so this won't make too much difference.
	 */
	for (i = 0; i < table->size; i++) {
		for (node = table->table[i]; node; node = next) {
			next = node->next;
			hash = node->hash % size;
			node->next = ntable[hash];
			node->prev = NULL;
			if (ntable[hash])
				ntable[hash]->prev = node;
			ntable[hash] = node;
		}
	}

	FREE(table->table);
	table->table = ntable;
	table->size = size;

	return 0;
}

#define RETVALID(itor)	return itor->node != NULL

hashtable_itor *
hashtable_itor_new(hashtable *table)
{
	hashtable_itor *itor;

	ASSERT(table != NULL);

	if ((itor = MALLOC(sizeof(*itor))) == NULL)
		return NULL;

	itor->table = table;
	itor->node = NULL;
	itor->slot = 0;

	hashtable_itor_first(itor);
	return itor;
}

dict_itor *
hashtable_dict_itor_new(hashtable *table)
{
	dict_itor *itor;

	ASSERT(table != NULL);

	if ((itor = MALLOC(sizeof(*itor))) == NULL)
		return NULL;
	if ((itor->_itor = hashtable_itor_new(table)) == NULL) {
		FREE(itor);
		return NULL;
	}

	itor->_destroy = (idestroy_func)hashtable_itor_destroy;
	itor->_valid = (valid_func)hashtable_itor_valid;
	itor->_invalid = (invalidate_func)hashtable_itor_invalidate;
	itor->_next = (next_func)hashtable_itor_next;
	itor->_prev = (prev_func)hashtable_itor_prev;
	itor->_nextn = (nextn_func)hashtable_itor_nextn;
	itor->_prevn = (prevn_func)hashtable_itor_prevn;
	itor->_first = (first_func)hashtable_itor_first;
	itor->_last = (last_func)hashtable_itor_last;
	itor->_search = (isearch_func)hashtable_itor_search;
	itor->_key = (key_func)hashtable_itor_key;
	itor->_data = (data_func)hashtable_itor_data;
	itor->_cdata = (cdata_func)hashtable_itor_cdata;
	itor->_setdata = (dataset_func)hashtable_itor_set_data;

	return itor;
}

void
hashtable_itor_destroy(hashtable_itor *itor)
{
	ASSERT(itor != NULL);

	FREE(itor);
}

int
hashtable_itor_valid(const hashtable_itor *itor)
{
	ASSERT(itor != NULL);

	RETVALID(itor);
}

void
hashtable_itor_invalidate(hashtable_itor *itor)
{
	ASSERT(itor != NULL);

	itor->node = NULL;
	itor->slot = 0;
}

int
hashtable_itor_next(hashtable_itor *itor)
{
	unsigned slot;
	hash_node *node;

	ASSERT(itor != NULL);

	if ((node = itor->node) == NULL)
		return hashtable_itor_first(itor);

	slot = itor->slot;
	node = node->next;
	if (node) {
		itor->node = node;
		return 1;
	}

	while (++slot < itor->table->size)
		if ((node = itor->table->table[slot]) != NULL)
			break;
	itor->node = node;
	itor->slot = node ? slot : 0;
	RETVALID(itor);
}

int
hashtable_itor_prev(hashtable_itor *itor)
{
	unsigned slot;
	hash_node *node;

	ASSERT(itor != NULL);

	if ((node = itor->node) == NULL)
		return hashtable_itor_last(itor);

	slot = itor->slot;
	node = node->prev;
	if (node) {
		itor->node = node;
		return 1;
	}

	while (slot > 0)
		if ((node = itor->table->table[--slot]) != NULL) {
			for (; node->next; node = node->next)
				/* void */;
			break;
		}
	itor->node = node;
	itor->slot = slot;

	RETVALID(itor);
}

int
hashtable_itor_nextn(hashtable_itor *itor, unsigned count)
{
	ASSERT(itor != NULL);

	if (!count)
		RETVALID(itor);

	while (count) {
		if (!hashtable_itor_next(itor))
			break;
		count--;
	}
	return count == 0;
}

int
hashtable_itor_prevn(hashtable_itor *itor, unsigned count)
{
	ASSERT(itor != NULL);

	if (!count)
		RETVALID(itor);

	while (count) {
		if (!hashtable_itor_prev(itor))
			break;
		count--;
	}
	return count == 0;
}

int
hashtable_itor_first(hashtable_itor *itor)
{
	unsigned slot;

	ASSERT(itor != NULL);

	for (slot = 0; slot < itor->table->size; slot++)
		if (itor->table->table[slot])
			break;
	if (slot == itor->table->size) {
		itor->node = NULL;
		slot = 0;
	} else {
		itor->node = itor->table->table[slot];
		itor->slot = (int)slot;
	}
	RETVALID(itor);
}

int
hashtable_itor_last(hashtable_itor *itor)
{
	unsigned slot;

	ASSERT(itor != NULL);

	for (slot = itor->table->size; slot;)
		if (itor->table->table[--slot])
			break;
	if ((int)slot < 0) {
		itor->node = NULL;
		itor->slot = 0;
	} else {
		hash_node *node;

		for (node = itor->table->table[slot]; node->next; node = node->next)
			/* void */;
		itor->node = node;
		itor->slot = slot;
	}
	RETVALID(itor);
}

int
hashtable_itor_search(hashtable_itor *itor, const void *key)
{
	hash_node *node;
	unsigned hash;

	hash = itor->table->key_hash(key);
	node = itor->table->table[hash % itor->table->size];
	for (; node; node = node->next)
		if (hash == node->hash && itor->table->key_cmp(key, node->key) == 0)
			break;
	itor->node = node;
	itor->slot = node ? (hash % itor->table->size) : 0;
	return node != NULL;
}

const void *
hashtable_itor_key(const hashtable_itor *itor)
{
	ASSERT(itor != NULL);

	return itor->node ? itor->node->key : NULL;
}

void *
hashtable_itor_data(hashtable_itor *itor)
{
	ASSERT(itor != NULL);

	return itor->node ? itor->node->dat : NULL;
}

const void *
hashtable_itor_cdata(const hashtable_itor *itor)
{
	ASSERT(itor != NULL);

	return itor->node ? itor->node->dat : NULL;
}

int
hashtable_itor_set_data(hashtable_itor *itor, void *dat, int del)
{
	ASSERT(itor != NULL);

	if (itor->node == NULL)
		return -1;

	if (del && itor->table->dat_del)
			itor->table->dat_del(itor->node->dat);
	itor->node->dat = dat;
	return 0;
}
syntax highlighted by Code2HTML, v. 0.9.1