fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * CDDL HEADER START
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * The contents of this file are subject to the terms of the
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Common Development and Distribution License (the "License").
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * You may not use this file except in compliance with the License.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * See the License for the specific language governing permissions
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * and limitations under the License.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * When distributing Covered Code, include this CDDL HEADER in each
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * If applicable, add the following below this CDDL HEADER, with the
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * fields enclosed by brackets "[]" replaced with your own identifying
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * information: Portions Copyright [yyyy] [name of copyright owner]
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * CDDL HEADER END
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Use is subject to license terms.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#define UID_REUSABLE(T, X) ((T) - (X)->t >= ONE_DAY)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * external variables.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_search:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * search a node from an AVL tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the node which matches the object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_search_next:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * search a node from an AVL tree, the object UID of the node
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * is next to the previous object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the previous object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the next node.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform LL balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->l = b->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform RR balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->r = b->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform LR balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate left and then right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->l = c->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->r = c->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update balance factor */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte switch (c->bf) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c itself */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform RL balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate right and then left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->r = c->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->l = c->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update balance factor */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte switch (c->bf) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c itself */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_insert:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * insert a node into an AVL tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * x - the node being added.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *f, *a, *p, *q, *b, *c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* initialize the new one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* locate the position */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (p->bf != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* insert it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the balance factor between a to x */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (p != x) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* brance is not broken */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (a->bf == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (a->bf + d == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate the tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (d == 1) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* LL rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* LR rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* RR rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* RL rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the parent */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (f->l == a) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (f->r == a) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * allocate new node(s) of the avl tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the UID of the node.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the newly allocated UID node.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* overflow happened */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search for an unused one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (uid != 0 &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* all are used up, sigh! */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* check if there is a gap and the gap needs to be filled up */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* make new UID(s) */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put it to the start of the fifo list */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = (htab_itemx_t *)malloc(sizeof (htab_itemx_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* insert it to the tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } while (x != NULL && start <= end && start != 0);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid_insert:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * insert a new UID node to the avl tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid_p- the pointer of the UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hval - the hash value of the new node.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - 0: no UID value assigned;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * 1: assigned an UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * -1: no memory.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * -2: invalid UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search the existing one from the tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* the item with this uid will override an */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* existing item, we treat this as an error */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (-2);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* assign a value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* strip off the used ones */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (x != NULL &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* none is available, make a new one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the available list */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->t = 0; /* registration initial time */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * enlarge_htab:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * enlarge the hash table when it gets too full.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* enlarge the logsize by one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* re-hash all items to the new table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (j < oldsz) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte isnslog(LOG_DEBUG, "enlarge_htab", "calloc() failed.");
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_init:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * some generic initialization for the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* do nothing */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_create:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * create a new hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * flags - UID_FLAGS_SEQ: the UID in the table needs to be sequential.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * logsize - the hash table logsize.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * chunks - the number of seperated chunks of the table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the newly created hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* do not enlarge it if the logsize reaches the maximum */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_compute_hval:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * compute a hash value for the specified key.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * key - the key of the hash.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the hash value.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* use classic Dan Bernstein hash alorigthm */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while ((c = *key++) != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * add an object to the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * p - the object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * flag - 0: not an association object; otherwise association object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid_p- pointer of UID for returning.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * update_p - pointer of update flag for returning.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - error code.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* compute the hash value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* check for duplicate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* add new object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* make new items for the object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = (htab_item_t *)calloc(tab->chunks, sizeof (htab_item_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* no memory or table is full */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* check if the table needs is too full */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put the UID of the object to the avl tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update data store before putting to hash table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* not association object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put the object to the table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; ec == 0; ) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, i, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* cache has been successfully updated */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* successfully added */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (ec == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* perform the Default DD behavior */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* set the return uid */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_remove:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * remove an object from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * p - the lookup control for the object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the UID of the object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * clone_flag - indicate if the removing is for an association object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the removed object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* get the object hash value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search the object from the table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; ; ) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* found it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* make an association object if the object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* has membership in user-defined DD(s). */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (i == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* remove it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* itself is an association object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* replace it with association */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (i == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* obj has been removed or updated */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the node in the avl tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* mark the uid item as invalid */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the timestamp */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put it to the end of fifo list */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_lookup:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * lookup an object from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * p - the lookup control for the item.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the UID of the object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid_p- the pointer of UID for returning.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * callback - callback function if the object is found.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * rekey - flag that indicates if the callback function will update
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * the key of the object.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - error code.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int (*callback)(void *, void *),
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* compute the hash value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* find the object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* found it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* set the return uid */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* invoke callback */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* Rekey works for one-chunk hash table only. */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* remove from previous slot */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* add it to the new slot */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(zhizi, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* set the return uid to 0 */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_get_next:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * get the next object UID from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the previous objet UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the next object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search the next node from the avl tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* validate the node */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } while (x != NULL);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* no more node is available */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_dump:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * dump all objects stored in the hash table for debug purpose.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; i < chunksz; i++) {