ticl

htable.c (4220B)

---

 /*
  * 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;
 }