fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * CDDL HEADER START
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * or http://www.opensolaris.org/os/licensing.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * See the License for the specific language governing permissions
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * and limitations under the License.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * CDDL HEADER END
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Use is subject to license terms.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <stdio.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <stdlib.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <string.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <sys/types.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <pthread.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <libelf.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include <libelf.h>
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include "isns_server.h"
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include "isns_cache.h"
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include "isns_htab.h"
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#include "isns_log.h"
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#define UID_REUSABLE(T, X) ((T) - (X)->t >= ONE_DAY)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * external variables.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteextern int cache_flag;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_search:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * search a node from an AVL tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_search(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte const htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte const uint32_t uid
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x = tab->avlt;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid > uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = x->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (x->uid < uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = x->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (x);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
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 *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the previous object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the next node.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_search_next(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte const htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte const uint32_t uid
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *p = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x = tab->avlt;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid > uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = x->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (x->uid <= uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = x->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (p);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_ll:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform LL balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_ll(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *a,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *b
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->l = b->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->r = a;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (b);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_rr:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform RR balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_rr(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *a,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *b
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->r = b->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->l = a;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (b);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_lr:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform LR balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_lr(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *a,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *b
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c = b->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate left and then right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->l = c->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c->r = a;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->r = c->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c->l = b;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update balance factor */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte switch (c->bf) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case -1:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case 0:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c itself */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case 1:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = -1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (c);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_rl:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * perform RL balance rotation on an AVL tree (or the subtree).
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * a - the left child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * b - the right child.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the new root.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_rl(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *a,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *b
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c = b->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate right and then left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->r = c->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c->l = a;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->l = c->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c->r = b;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update balance factor */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte switch (c->bf) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case -1:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's right */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case 0:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c itself */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case 1:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* on c's left */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b->bf = -1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (c);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * avl_insert:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * insert a node into an AVL tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * x - the node being added.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic void
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteavl_insert(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *f, *a, *p, *q, *b, *c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int d;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* initialize the new one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->l = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->r = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->avlt == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->avlt = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* locate the position */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte f = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a = tab->avlt;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = tab->avlt;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte q = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (p->bf != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a = p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte f = q;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte q = p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid < q->uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = p->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = p->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* insert it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid < q->uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte q->l = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte q->r = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the balance factor between a to x */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid < a->uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = a->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte d = 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = a->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte d = -1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte b = p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (p != x) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid < p->uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p->bf = 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = p->l;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p->bf = -1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte p = p->r;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* brance is not broken */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (a->bf == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = d;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto bal_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (a->bf + d == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte a->bf = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto bal_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* rotate the tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (d == 1) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (b->bf == 1) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* LL rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c = avl_ll(a, b);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (b->bf == -1) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* LR rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c = avl_lr(a, b);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (b->bf == -1) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* RR rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c = avl_rr(a, b);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (b->bf == 1) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* RL rotate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte c = avl_rl(a, b);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the parent */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (f == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->avlt = c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (f->l == a) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte f->l = c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (f->r == a) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte f->r = c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortebal_done:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x->uid > tab->buid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->buid = x->uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * new_uid:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * allocate new node(s) of the avl tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic htab_itemx_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortenew_uid(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t start, end;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* overflow happened */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search for an unused one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (uid != 0 &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte avl_search(tab, uid) != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* all are used up, sigh! */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (NULL);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* check if there is a gap and the gap needs to be filled up */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid > tab->buid &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte (tab->flags & UID_FLAGS_SEQ) != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte start = tab->buid + 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte start = uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte end = uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* make new UID(s) */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte do {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->hval = BAD_HVAL_MASK;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->t = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put it to the start of the fifo list */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->n = tab->list;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->list = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->tail == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->tail = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = (htab_itemx_t *)malloc(sizeof (htab_itemx_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->uid = start;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->n = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* insert it to the tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte avl_insert(tab, x);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte start ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } while (x != NULL && start <= end && start != 0);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (x);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid_insert:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * insert a new UID node to the avl tree.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic int
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteuid_insert(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t *const uid_p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte const uint32_t hval
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int assignx = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid = *uid_p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x, *n;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search the existing one from the tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = avl_search(tab, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = new_uid(tab, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (!BAD_HVAL(x->hval) &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->hval != hval) {
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 }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* assign a value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = tab->list;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* strip off the used ones */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (x != NULL &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte !BAD_HVAL(x->hval)) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte n = x->n;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->n = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = n;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x == NULL ||
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte UID_REUSABLE(tab->c->timestamp(), x) == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* none is available, make a new one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->list = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = new_uid(tab, tab->buid + 1);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte n = x->n;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->n = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->list = n;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the available list */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->list == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->tail = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte assignx = 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *uid_p = x->uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (-1); /* no memory */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->hval = hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->t = 0; /* registration initial time */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (assignx);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * enlarge_htab:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * enlarge the hash table when it gets too full.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortestatic void
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteenlarge_htab(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t **items;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint16_t logsize;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t oldsz, newsz, mask;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t *item, *tmp, **itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint16_t i;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t j;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* enlarge the logsize by one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte logsize = tab->logsize + 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte newsz = (1 << logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = (htab_item_t **)calloc(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte newsz * tab->chunks, sizeof (htab_item_t *));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* re-hash all items to the new table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte mask = newsz - 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte oldsz = (1 << tab->logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte i = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (i < tab->chunks) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte j = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (j < oldsz) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item = tab->items[(i * oldsz) + j];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (item != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tmp = item->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &items[(i * newsz) +
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte (item->hval & mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid = tab->c->get_uid(item->p);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (*itemp != NULL &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->get_uid((*itemp)->p) >
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &(*itemp)->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item->next = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *itemp = item;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item = tmp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte j ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte i ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte free(tab->items);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->items = items;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->logsize = logsize;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->mask = mask;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte isnslog(LOG_DEBUG, "enlarge_htab", "calloc() failed.");
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_init:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * some generic initialization for the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortevoid
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_init(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* do nothing */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_create:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * create a new hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_create(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int flags,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint16_t logsize,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint16_t chunks
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t **items = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t count;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* do not enlarge it if the logsize reaches the maximum */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (logsize <= MAX_LOGSIZE &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte chunks > 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab = (htab_t *)calloc(1, sizeof (htab_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte count = (1 << logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = (htab_item_t **)calloc(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte count * chunks, sizeof (htab_item_t *));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->flags = flags;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->items = items;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->logsize = logsize;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->chunks = chunks;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->mask = count - 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->count = 1; /* reserve one */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->avlt = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->buid = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->list = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->tail = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte free(tab);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (tab);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_compute_hval:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * compute a hash value for the specified key.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * key - the key of the hash.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the hash value.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteuint32_t
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_compute_hval(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte const uchar_t *key
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* use classic Dan Bernstein hash alorigthm */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t hash = 5381;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while ((c = *key++) != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hash = ((hash << 5) + hash) + c;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (hash);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_add:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * add an object to the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteint
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_add(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte void *p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int flag,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t *uid_p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int *update_p
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int ec = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t *items = NULL, **itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t chunksz;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t flags = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int i;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* compute the hash value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* check for duplicate */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = tab->items[hval & tab->mask];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->c->cmp(items->p, p, 0) == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (flag == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ec = tab->c->replace_hook(items->p, p, uid_p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte update_p == NULL ? 1 : 0);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (update_p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *update_p = 1;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto add_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = items->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* add new object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (update_p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *update_p = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* make new items for the object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = (htab_item_t *)calloc(tab->chunks, sizeof (htab_item_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (items == NULL ||
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->count == 0 ||
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte (++tab->count) == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* no memory or table is full */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ec = ISNS_RSP_INTERNAL_ERROR;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto add_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* check if the table needs is too full */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte chunksz = (1 << tab->logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->count >= (chunksz * HASH_RATIO) &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->logsize < MAX_LOGSIZE) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte enlarge_htab(tab);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte chunksz = (1 << tab->logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put the UID of the object to the avl tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid = tab->c->get_uid(p);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte switch (uid_insert(tab, &uid, hval)) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case -2:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ec = ISNS_RSP_INVALID_REGIS;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto add_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case -1:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ec = ISNS_RSP_INTERNAL_ERROR;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto add_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case 0:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte case 1:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->set_uid(p, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte default:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update data store before putting to hash table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (flag == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* not association object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ec = tab->c->add_hook(p);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put the object to the table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; ec == 0; ) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items[i].hval = hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items[i].p = p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (*itemp != NULL &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->get_uid((*itemp)->p) > uid) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &(*itemp)->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items[i].next = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *itemp = &items[i];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte i ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (i < tab->chunks) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, i, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* cache has been successfully updated */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte SET_CACHE_UPDATED();
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* successfully added */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (ec == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* perform the Default DD behavior */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->ddd(p, '+');
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* set the return uid */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid_p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *uid_p = uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteadd_done:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (ec != 0 && items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte free(items);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (ec);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_remove:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * remove an object from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteisns_obj_t *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_remove(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte void *p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int clone_flag
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte void *zhizi = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte void *clone = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t *items = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t *item, **itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t chunksz;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t flags;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int i;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* get the object hash value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = avl_search(tab, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x != NULL && !BAD_HVAL(x->hval)) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = x->hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto remove_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte flags = 0 | FLAGS_CTRL_MASK;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search the object from the table */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte flags = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte chunksz = (1 << tab->logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; ; ) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (item != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* found it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->c->cmp(item->p, p, 1) == 0) {
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 if ((clone = tab->c->clone(item->p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte clone_flag)) == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->ddd(item->p, '-');
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->count --;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = item;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte zhizi = item->p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (clone == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* remove it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *itemp = item->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (clone == item->p) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* itself is an association object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte goto remove_done;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* replace it with association */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte zhizi = item->p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item->p = clone;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (i == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* obj has been removed or updated */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte SET_CACHE_UPDATED();
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &item->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte i ++;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (zhizi != NULL && i < tab->chunks) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte zhizi, i, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the node in the avl tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x == NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid = tab->c->get_uid(zhizi);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ASSERT(uid != 0);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = avl_search(tab, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ASSERT(x != NULL && !BAD_HVAL(x->hval));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* mark the uid item as invalid */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->hval |= BAD_HVAL_MASK;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* update the timestamp */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->t = tab->c->timestamp();
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* put it to the end of fifo list */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->list != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->tail->n = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->list = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->tail = x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteremove_done:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte free(items);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (zhizi);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_lookup:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * lookup an object from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
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 * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteint
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_lookup(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte void *p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t *uid_p,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int (*callback)(void *, void *),
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int rekey
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t ret = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte void *zhizi = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t *item, **itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x = NULL;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t chunksz;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t flags = 0 | FLAGS_CTRL_MASK;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte int i;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* compute the hash value */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid != 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = avl_search(tab, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = x->hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = BAD_HVAL_MASK;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* find the object */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (!BAD_HVAL(hval)) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte i = flags & FLAGS_CHUNK_MASK;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte chunksz = (1 << tab->logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (item != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (tab->c->cmp(item->p, p, 1) == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte zhizi = item->p;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte break;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &item->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* found it */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (zhizi != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* set the return uid */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (uid_p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *uid_p = tab->c->get_uid(zhizi);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* invoke callback */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (callback != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ret = callback(zhizi, p);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (rekey != 0 && ret == 0) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* Rekey works for one-chunk hash table only. */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte ASSERT(tab->chunks == 1 && x != NULL);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* remove from previous slot */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *itemp = item->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* add it to the new slot */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte flags = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hval = VALID_HVAL(tab->c->get_hval(zhizi, 0, &flags));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x->hval = hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item->hval = hval;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &tab->items[(hval & tab->mask)];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (*itemp != NULL &&
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte (tab->c->get_uid((*itemp)->p) >
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->get_uid(zhizi))) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte itemp = &(*itemp)->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte item->next = *itemp;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *itemp = item;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } else if (uid_p != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* set the return uid to 0 */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *uid_p = 0;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (ret);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_get_next:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * get the next object UID from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * uid - the previous objet UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * return - the next object UID.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forteuint32_t
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_get_next(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t uid
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_itemx_t *x;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte do {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* search the next node from the avl tree */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte x = avl_search_next(tab, uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (x != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uid = x->uid;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* validate the node */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (!BAD_HVAL(x->hval)) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (uid);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte } while (x != NULL);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* no more node is available */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (0);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte/*
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htab_dump:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * dump all objects stored in the hash table for debug purpose.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * tab - the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte *
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ****************************************************************************
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#ifdef DEBUG
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortevoid
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Fortehtab_dump(
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_t *tab
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte{
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t chunksz;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte htab_item_t *items;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte uint32_t i;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte chunksz = (1 << tab->logsize);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; i < chunksz; i++) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = tab->items[i];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte while (items != NULL) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte tab->c->dump(items->p);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte items = items->next;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte }
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte}
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte#endif