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