xref: /titanic_52/usr/src/cmd/isns/isnsd/htable.c (revision fcf3ce441efd61da9bb2884968af01cb7c1452cc)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <pthread.h>
#include <libelf.h>
#include <libelf.h>

#include "isns_server.h"
#include "isns_cache.h"
#include "isns_htab.h"
#include "isns_log.h"

#define	UID_REUSABLE(T, X)	((T) - (X)->t >= ONE_DAY)

/*
 * external variables.
 */
extern int cache_flag;

/*
 * ****************************************************************************
 * avl_search:
 *	search a node from an AVL tree.
 *
 * tab	- the hash table.
 * uid	- the object UID.
 * return - the node which matches the object UID.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
avl_search(
	const htab_t *tab,
	const uint32_t uid
)
{
	htab_itemx_t *x = tab->avlt;

	while (x != NULL) {
		if (x->uid > uid) {
			x = x->l;
		} else if (x->uid < uid) {
			x = x->r;
		} else {
			break;
		}
	}

	return (x);
}

/*
 * ****************************************************************************
 * avl_search_next:
 *	search a node from an AVL tree, the object UID of the node
 *	is next to the previous object UID.
 *
 * tab	- the hash table.
 * uid	- the previous object UID.
 * return - the next node.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
avl_search_next(
	const htab_t *tab,
	const uint32_t uid
)
{
	htab_itemx_t *p = NULL;
	htab_itemx_t *x = tab->avlt;

	while (x != NULL) {
		if (x->uid > uid) {
			p = x;
			x = x->l;
		} else if (x->uid <= uid) {
			x = x->r;
		}
	}

	return (p);
}

/*
 * ****************************************************************************
 * avl_ll:
 *	perform LL balance rotation on an AVL tree (or the subtree).
 *
 * a	- the left child.
 * b	- the right child.
 * return - the new root.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
avl_ll(
	htab_itemx_t *a,
	htab_itemx_t *b
)
{
	/* rotate right */
	a->l = b->r;
	a->bf = 0;
	b->r = a;
	b->bf = 0;

	return (b);
}

/*
 * ****************************************************************************
 * avl_rr:
 *	perform RR balance rotation on an AVL tree (or the subtree).
 *
 * a	- the left child.
 * b	- the right child.
 * return - the new root.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
avl_rr(
	htab_itemx_t *a,
	htab_itemx_t *b
)
{
	/* rotate left */
	a->r = b->l;
	a->bf = 0;
	b->l = a;
	b->bf = 0;

	return (b);
}

/*
 * ****************************************************************************
 * avl_lr:
 *	perform LR balance rotation on an AVL tree (or the subtree).
 *
 * a	- the left child.
 * b	- the right child.
 * return - the new root.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
avl_lr(
	htab_itemx_t *a,
	htab_itemx_t *b
)
{
	htab_itemx_t *c;

	c = b->r;

	/* rotate left and then right */
	a->l = c->r;
	c->r = a;
	b->r = c->l;
	c->l = b;

	/* update balance factor */
	switch (c->bf) {
	case -1:
		/* on c's right */
		a->bf = 0;
		b->bf = 1;
		break;
	case 0:
		/* on c itself */
		a->bf = 0;
		b->bf = 0;
		break;
	case 1:
		/* on c's left */
		a->bf = -1;
		b->bf = 0;
		break;
	}
	c->bf = 0;

	return (c);
}

/*
 * ****************************************************************************
 * avl_rl:
 *	perform RL balance rotation on an AVL tree (or the subtree).
 *
 * a	- the left child.
 * b	- the right child.
 * return - the new root.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
avl_rl(
	htab_itemx_t *a,
	htab_itemx_t *b
)
{
	htab_itemx_t *c;

	c = b->l;

	/* rotate right and then left */
	a->r = c->l;
	c->l = a;
	b->l = c->r;
	c->r = b;

	/* update balance factor */
	switch (c->bf) {
	case -1:
		/* on c's right */
		a->bf = 1;
		b->bf = 0;
		break;
	case 0:
		/* on c itself */
		a->bf = 0;
		b->bf = 0;
		break;
	case 1:
		/* on c's left */
		a->bf = 0;
		b->bf = -1;
		break;
	}
	c->bf = 0;

	return (c);
}

/*
 * ****************************************************************************
 * avl_insert:
 *	insert a node into an AVL tree.
 *
 * tab	- the hash table.
 * x	- the node being added.
 *
 * ****************************************************************************
 */
static void
avl_insert(
	htab_t *tab,
	htab_itemx_t *x
)
{
	htab_itemx_t *f, *a, *p, *q, *b, *c;
	int d;

	/* initialize the new one */
	x->bf = 0;
	x->l = NULL;
	x->r = NULL;

	if (tab->avlt == NULL) {
		tab->avlt = x;
	} else {
		/* locate the position */
		f = NULL;
		a = tab->avlt;
		p = tab->avlt;
		q = NULL;
		while (p != NULL) {
			if (p->bf != 0) {
				a = p;
				f = q;
			}
			q = p;
			if (x->uid < q->uid) {
				p = p->l;
			} else {
				p = p->r;
			}
		}
		/* insert it */
		if (x->uid < q->uid) {
			q->l = x;
		} else {
			q->r = x;
		}
		/* update the balance factor between a to x */
		if (x->uid < a->uid) {
			p = a->l;
			d = 1;
		} else {
			p = a->r;
			d = -1;
		}
		b = p;
		while (p != x) {
			if (x->uid < p->uid) {
				p->bf = 1;
				p = p->l;
			} else {
				p->bf = -1;
				p = p->r;
			}
		}
		/* brance is not broken */
		if (a->bf == 0) {
			a->bf = d;
			goto bal_done;
		} else if (a->bf + d == 0) {
			a->bf = 0;
			goto bal_done;
		}
		/* rotate the tree */
		if (d == 1) {
			if (b->bf == 1) {
				/* LL rotate */
				c = avl_ll(a, b);
			} else if (b->bf == -1) {
				/* LR rotate */
				c = avl_lr(a, b);
			}
		} else {
			if (b->bf == -1) {
				/* RR rotate */
				c = avl_rr(a, b);
			} else if (b->bf == 1) {
				/* RL rotate */
				c = avl_rl(a, b);
			}
		}
		/* update the parent */
		if (f == NULL) {
			tab->avlt = c;
		} else if (f->l == a) {
			f->l = c;
		} else if (f->r == a) {
			f->r = c;
		}
	}

bal_done:
	if (x->uid > tab->buid) {
		tab->buid = x->uid;
	}
}

/*
 * ****************************************************************************
 * new_uid:
 *	allocate new node(s) of the avl tree.
 *
 * tab	- the hash table.
 * uid	- the UID of the node.
 * return - the newly allocated UID node.
 *
 * ****************************************************************************
 */
static htab_itemx_t *
new_uid(
	htab_t *tab,
	uint32_t uid
)
{
	htab_itemx_t *x = NULL;

	uint32_t start, end;

	/* overflow happened */
	if (uid == 0) {
		/* search for an unused one */
		uid ++;
		while (uid != 0 &&
		    avl_search(tab, uid) != NULL) {
			uid ++;
		}
		if (uid == 0) {
			/* all are used up, sigh! */
			return (NULL);
		}
	}

	/* check if there is a gap and the gap needs to be filled up */
	if (uid > tab->buid &&
	    (tab->flags & UID_FLAGS_SEQ) != 0) {
		start = tab->buid + 1;
	} else {
		start = uid;
	}
	end = uid;

	/* make new UID(s) */
	do {
		if (x != NULL) {
			x->hval = BAD_HVAL_MASK;
			x->t = 0;
			/* put it to the start of the fifo list */
			x->n = tab->list;
			tab->list = x;
			if (tab->tail == NULL) {
				tab->tail = x;
			}
		}
		x = (htab_itemx_t *)malloc(sizeof (htab_itemx_t));
		if (x != NULL) {
			x->uid = start;
			x->n = NULL;
			/* insert it to the tree */
			avl_insert(tab, x);
		}
		start ++;
	} while (x != NULL && start <= end && start != 0);

	return (x);
}

/*
 * ****************************************************************************
 * uid_insert:
 *	insert a new UID node to the avl tree.
 *
 * tab	- the hash table.
 * uid_p- the pointer of the UID.
 * hval	- the hash value of the new node.
 * return -	0: no UID value assigned;
 *		1: assigned an UID.
 *		-1: no memory.
 *		-2: invalid UID.
 *
 * ****************************************************************************
 */
static int
uid_insert(
	htab_t *tab,
	uint32_t *const uid_p,
	const uint32_t hval
)
{
	int assignx = 0;

	uint32_t uid = *uid_p;

	htab_itemx_t *x, *n;

	if (uid != 0) {
		/* search the existing one from the tree */
		x = avl_search(tab, uid);
		if (x == NULL) {
			x = new_uid(tab, uid);
		} else if (!BAD_HVAL(x->hval) &&
		    x->hval != hval) {
			/* the item with this uid will override an */
			/* existing item, we treat this as an error */
			return (-2);
		}
	} else {
		/* assign a value */
		x = tab->list;
		/* strip off the used ones */
		while (x != NULL &&
		    !BAD_HVAL(x->hval)) {
			n = x->n;
			x->n = NULL;
			x = n;
		}

		if (x == NULL ||
		    UID_REUSABLE(tab->c->timestamp(), x) == 0) {
			/* none is available, make a new one */
			tab->list = x;
			x = new_uid(tab, tab->buid + 1);
		} else {
			n = x->n;
			x->n = NULL;
			tab->list = n;
		}
		/* update the available list */
		if (tab->list == NULL) {
			tab->tail = NULL;
		}
		assignx = 1;
		if (x != NULL) {
			*uid_p = x->uid;
		}
	}

	if (x == NULL) {
		return (-1); /* no memory */
	}

	x->hval = hval;
	x->t = 0; /* registration initial time */

	return (assignx);
}

/*
 * ****************************************************************************
 * enlarge_htab:
 *	enlarge the hash table when it gets too full.
 *
 * tab	- the hash table.
 *
 * ****************************************************************************
 */
static void
enlarge_htab(
	htab_t *tab
)
{
	htab_item_t **items;
	uint16_t logsize;
	uint32_t oldsz, newsz, mask;
	htab_item_t *item, *tmp, **itemp;
	uint16_t i;
	uint32_t j;

	uint32_t uid;

	/* enlarge the logsize by one */
	logsize = tab->logsize + 1;
	newsz = (1 << logsize);
	items = (htab_item_t **)calloc(
	    newsz * tab->chunks, sizeof (htab_item_t *));
	/* re-hash all items to the new table */
	if (items != NULL) {
		mask = newsz - 1;
		oldsz = (1 << tab->logsize);
		i = 0;
		while (i < tab->chunks) {
			j = 0;
			while (j < oldsz) {
				item = tab->items[(i * oldsz) + j];
				while (item != NULL) {
					tmp = item->next;
					itemp = &items[(i * newsz) +
					    (item->hval & mask)];
					uid = tab->c->get_uid(item->p);
					while (*itemp != NULL &&
					    tab->c->get_uid((*itemp)->p) >
					    uid) {
						itemp = &(*itemp)->next;
					}
					item->next = *itemp;
					*itemp = item;
					item = tmp;
				}
				j ++;
			}
			i ++;
		}
		free(tab->items);
		tab->items = items;
		tab->logsize = logsize;
		tab->mask = mask;
	} else {
		isnslog(LOG_DEBUG, "enlarge_htab", "calloc() failed.");
	}
}

/*
 * ****************************************************************************
 * htab_init:
 *	some generic initialization for the hash table.
 *
 * ****************************************************************************
 */
void
htab_init(
)
{
	/* do nothing */
}

/*
 * ****************************************************************************
 * htab_create:
 *	create a new hash table.
 *
 * flags - UID_FLAGS_SEQ: the UID in the table needs to be sequential.
 * logsize - the hash table logsize.
 * chunks  - the number of seperated chunks of the table.
 * return  - the newly created hash table.
 *
 * ****************************************************************************
 */
htab_t *
htab_create(
	int flags,
	uint16_t logsize,
	uint16_t chunks
)
{
	htab_t *tab = NULL;
	htab_item_t **items = NULL;
	uint32_t count;

	/* do not enlarge it if the logsize reaches the maximum */
	if (logsize <= MAX_LOGSIZE &&
	    chunks > 0) {
		tab = (htab_t *)calloc(1, sizeof (htab_t));
		if (tab != NULL) {
			count = (1 << logsize);
			items = (htab_item_t **)calloc(
			    count * chunks, sizeof (htab_item_t *));
			if (items != NULL) {
				tab->flags = flags;
				tab->items = items;
				tab->logsize = logsize;
				tab->chunks = chunks;
				tab->mask = count - 1;
				tab->count = 1; /* reserve one */
				tab->avlt = NULL;
				tab->buid = 0;
				tab->list = NULL;
				tab->tail = NULL;
			} else {
				free(tab);
				tab = NULL;
			}
		}
	}

	return (tab);
}

/*
 * ****************************************************************************
 * htab_compute_hval:
 *	compute a hash value for the specified key.
 *
 * key - the key of the hash.
 * return - the hash value.
 *
 * ****************************************************************************
 */
uint32_t
htab_compute_hval(
	const uchar_t *key
)
{
	/* use classic Dan Bernstein hash alorigthm */
	uint32_t hash = 5381;
	int c;

	while ((c = *key++) != 0) {
		hash = ((hash << 5) + hash) + c;
	}

	return (hash);
}

/*
 * ****************************************************************************
 * htab_add:
 *	add an object to the hash table.
 *
 * tab	- the hash table.
 * p	- the object.
 * flag	- 0: not an association object; otherwise association object.
 * uid_p- pointer of UID for returning.
 * update_p - pointer of update flag for returning.
 * return - error code.
 *
 * ****************************************************************************
 */
int
htab_add(
	htab_t *tab,
	void *p,
	int flag,
	uint32_t *uid_p,
	int *update_p
)
{
	int ec = 0;

	htab_item_t *items = NULL, **itemp;
	uint32_t chunksz;
	uint32_t flags = 0;
	uint32_t hval;
	uint32_t uid = 0;
	int i;

	/* compute the hash value */
	hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));

	/* check for duplicate */
	items = tab->items[hval & tab->mask];
	while (items != NULL) {
		if (tab->c->cmp(items->p, p, 0) == 0) {
			if (flag == 0) {
				ec = tab->c->replace_hook(items->p, p, uid_p,
				    update_p == NULL ? 1 : 0);
			}
			if (update_p != NULL) {
				*update_p = 1;
			}
			items = NULL;
			goto add_done;
		}
		items = items->next;
	}

	/* add new object */
	if (update_p != NULL) {
		*update_p = 0;
	}

	/* make new items for the object */
	items = (htab_item_t *)calloc(tab->chunks, sizeof (htab_item_t));

	if (items == NULL ||
	    tab->count == 0 ||
	    (++tab->count) == 0) {
		/* no memory or table is full */
		ec = ISNS_RSP_INTERNAL_ERROR;
		goto add_done;
	}

	/* check if the table needs is too full */
	chunksz = (1 << tab->logsize);
	if (tab->count >= (chunksz * HASH_RATIO) &&
	    tab->logsize < MAX_LOGSIZE) {
		enlarge_htab(tab);
		chunksz = (1 << tab->logsize);
	}

	/* put the UID of the object to the avl tree */
	uid = tab->c->get_uid(p);
	switch (uid_insert(tab, &uid, hval)) {
	case -2:
		ec = ISNS_RSP_INVALID_REGIS;
		goto add_done;
	case -1:
		ec = ISNS_RSP_INTERNAL_ERROR;
		goto add_done;
	case 0:
		break;
	case 1:
		tab->c->set_uid(p, uid);
		break;
	default:
		break;
	}

	/* update data store before putting to hash table */
	if (flag == 0) {
		/* not association object */
		ec = tab->c->add_hook(p);
	}

	/* put the object to the table */
	for (i = 0; ec == 0; ) {
		items[i].hval = hval;
		items[i].p = p;
		itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
		while (*itemp != NULL &&
		    tab->c->get_uid((*itemp)->p) > uid) {
			itemp = &(*itemp)->next;
		}
		items[i].next = *itemp;
		*itemp = &items[i];
		i ++;
		if (i < tab->chunks) {
			hval = VALID_HVAL(tab->c->get_hval(p, i, &flags));
		} else {
			break;
		}
	}

	/* cache has been successfully updated */
	SET_CACHE_UPDATED();

	/* successfully added */
	items = NULL;

	if (ec == 0) {
		/* perform the Default DD behavior */
		tab->c->ddd(p, '+');

		/* set the return uid */
		if (uid_p != NULL) {
			*uid_p = uid;
		}
	}
add_done:
	if (ec != 0 && items != NULL) {
		free(items);
	}

	return (ec);
}

/*
 * ****************************************************************************
 * htab_remove:
 *	remove an object from the hash table.
 *
 * tab	- the hash table.
 * p	- the lookup control for the object.
 * uid	- the UID of the object.
 * clone_flag - indicate if the removing is for an association object.
 * return - the removed object.
 *
 * ****************************************************************************
 */
isns_obj_t *
htab_remove(
	htab_t *tab,
	void *p,
	uint32_t uid,
	int clone_flag
)
{
	void *zhizi = NULL;
	void *clone = NULL;
	htab_item_t *items = NULL;
	htab_item_t *item, **itemp;
	htab_itemx_t *x = NULL;
	uint32_t chunksz;
	uint32_t flags;
	uint32_t hval;
	int i;

	/* get the object hash value */
	if (uid != 0) {
		x = avl_search(tab, uid);
		if (x != NULL && !BAD_HVAL(x->hval)) {
			hval = x->hval;
		} else {
			goto remove_done;
		}
	} else {
		flags = 0 | FLAGS_CTRL_MASK;
		hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
	}

	/* search the object from the table */
	flags = 0;
	chunksz = (1 << tab->logsize);
	for (i = 0; ; ) {
		itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
		item = *itemp;
		while (item != NULL) {
			/* found it */
			if (tab->c->cmp(item->p, p, 1) == 0) {
				/* make an association object if the object */
				/* has membership in user-defined DD(s). */
				if (i == 0) {
					if ((clone = tab->c->clone(item->p,
					    clone_flag)) == NULL) {
						tab->c->ddd(item->p, '-');
						tab->count --;
						items = item;
						zhizi = item->p;
					}
				}
				if (clone == NULL) {
					/* remove it */
					*itemp = item->next;
				} else if (clone == item->p) {
					/* itself is an association object */
					goto remove_done;
				} else {
					/* replace it with association */
					zhizi = item->p;
					item->p = clone;
				}
				if (i == 0) {
					/* obj has been removed or updated */
					SET_CACHE_UPDATED();
				}
				break;
			}
			itemp = &item->next;
			item = *itemp;
		}
		i ++;
		if (zhizi != NULL && i < tab->chunks) {
			hval = VALID_HVAL(tab->c->get_hval(
			    zhizi, i, &flags));
		} else {
			break;
		}
	}

	/* update the node in the avl tree */
	if (items != NULL) {
		if (x == NULL) {
			uid = tab->c->get_uid(zhizi);
			ASSERT(uid != 0);
			x = avl_search(tab, uid);
		}
		ASSERT(x != NULL && !BAD_HVAL(x->hval));
		/* mark the uid item as invalid */
		x->hval |= BAD_HVAL_MASK;
		/* update the timestamp */
		x->t = tab->c->timestamp();
		/* put it to the end of fifo list */
		if (tab->list != NULL) {
			tab->tail->n = x;
		} else {
			tab->list = x;
		}
		tab->tail = x;
	}

remove_done:
	if (items != NULL) {
		free(items);
	}

	return (zhizi);
}

/*
 * ****************************************************************************
 * htab_lookup:
 *	lookup an object from the hash table.
 *
 * tab	- the hash table.
 * p	- the lookup control for the item.
 * uid	- the UID of the object.
 * uid_p- the pointer of UID for returning.
 * callback - callback function if the object is found.
 * rekey - flag that indicates if the callback function will update
 *		the key of the object.
 * return - error code.
 *
 * ****************************************************************************
 */
int
htab_lookup(
	htab_t *tab,
	void *p,
	uint32_t uid,
	uint32_t *uid_p,
	int (*callback)(void *, void *),
	int rekey
)
{
	uint32_t ret = 0;
	void *zhizi = NULL;
	htab_item_t *item, **itemp;
	htab_itemx_t *x = NULL;
	uint32_t chunksz;
	uint32_t flags = 0 | FLAGS_CTRL_MASK;
	uint32_t hval;
	int i;

	/* compute the hash value */
	if (uid != 0) {
		x = avl_search(tab, uid);
		if (x != NULL) {
			hval = x->hval;
		} else {
			hval = BAD_HVAL_MASK;
		}
	} else {
		hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
	}

	/* find the object */
	if (!BAD_HVAL(hval)) {
		i = flags & FLAGS_CHUNK_MASK;
		chunksz = (1 << tab->logsize);
		itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
		item = *itemp;
		while (item != NULL) {
			if (tab->c->cmp(item->p, p, 1) == 0) {
				zhizi = item->p;
				break;
			}
			itemp = &item->next;
			item = *itemp;
		}
	}

	/* found it */
	if (zhizi != NULL) {
		/* set the return uid */
		if (uid_p != NULL) {
			*uid_p = tab->c->get_uid(zhizi);
		}
		/* invoke callback */
		if (callback != NULL) {
			ret = callback(zhizi, p);
		}
		if (rekey != 0 && ret == 0) {
			/* Rekey works for one-chunk hash table only. */
			ASSERT(tab->chunks == 1 && x != NULL);
			/* remove from previous slot */
			*itemp = item->next;
			/* add it to the new slot */
			flags = 0;
			hval = VALID_HVAL(tab->c->get_hval(zhizi, 0, &flags));
			x->hval = hval;
			item->hval = hval;
			itemp = &tab->items[(hval & tab->mask)];
			while (*itemp != NULL &&
			    (tab->c->get_uid((*itemp)->p) >
			    tab->c->get_uid(zhizi))) {
				itemp = &(*itemp)->next;
			}
			item->next = *itemp;
			*itemp = item;
		}
	} else if (uid_p != NULL) {
		/* set the return uid to 0 */
		*uid_p = 0;
	}

	return (ret);
}

/*
 * ****************************************************************************
 * htab_get_next:
 *	get the next object UID from the hash table.
 *
 * tab	- the hash table.
 * uid	- the previous objet UID.
 * return - the next object UID.
 *
 * ****************************************************************************
 */
uint32_t
htab_get_next(
	htab_t *tab,
	uint32_t uid
)
{
	htab_itemx_t *x;

	do {
		/* search the next node from the avl tree */
		x = avl_search_next(tab, uid);
		if (x != NULL) {
			uid = x->uid;
			/* validate the node */
			if (!BAD_HVAL(x->hval)) {
				return (uid);
			}
		}
	} while (x != NULL);

	/* no more node is available */
	return (0);
}

/*
 * ****************************************************************************
 * htab_dump:
 *	dump all objects stored in the hash table for debug purpose.
 *
 * tab	- the hash table.
 *
 * ****************************************************************************
 */
#ifdef DEBUG
void
htab_dump(
	htab_t *tab
)
{
	uint32_t chunksz;
	htab_item_t *items;

	uint32_t i;

	chunksz = (1 << tab->logsize);

	for (i = 0; i < chunksz; i++) {
		items = tab->items[i];
		while (items != NULL) {
			tab->c->dump(items->p);
			items = items->next;
		}
	}
}
#endif