usr/src/cmd/isns/isnsd/htable.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21
  22 /*
  23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <sys/types.h>
  31 #include <pthread.h>
  32 #include <libelf.h>
  33 #include <libelf.h>
  34
  35 #include "isns_server.h"
  36 #include "isns_cache.h"
  37 #include "isns_htab.h"
  38 #include "isns_log.h"
  39
  40 #define UID_REUSABLE(T, X)      ((T) - (X)->t >= ONE_DAY)
  41
  42 /*
  43  * external variables.
  44  */
  45 extern int cache_flag;
  46
  47 /*
  48  * ****************************************************************************
  49  * avl_search:
  50  *      search a node from an AVL tree.
  51  *
  52  * tab  - the hash table.
  53  * uid  - the object UID.
  54  * return - the node which matches the object UID.
  55  *
  56  * ****************************************************************************
  57  */
  58 static htab_itemx_t *
  59 avl_search(
  60         const htab_t *tab,
  61         const uint32_t uid
  62 )
  63 {
  64         htab_itemx_t *x = tab->avlt;
  65
  66         while (x != NULL) {
  67                 if (x->uid > uid) {
  68                         x = x->l;
  69                 } else if (x->uid < uid) {
  70                         x = x->r;
  71                 } else {
  72                         break;
  73                 }
  74         }
  75
  76         return (x);
  77 }
  78
  79 /*
  80  * ****************************************************************************
  81  * avl_search_next:
  82  *      search a node from an AVL tree, the object UID of the node
  83  *      is next to the previous object UID.
  84  *
  85  * tab  - the hash table.
  86  * uid  - the previous object UID.
  87  * return - the next node.
  88  *
  89  * ****************************************************************************
  90  */
  91 static htab_itemx_t *
  92 avl_search_next(
  93         const htab_t *tab,
  94         const uint32_t uid
  95 )
  96 {
  97         htab_itemx_t *p = NULL;
  98         htab_itemx_t *x = tab->avlt;
  99
 100         while (x != NULL) {
 101                 if (x->uid > uid) {
 102                         p = x;
 103                         x = x->l;
 104                 } else if (x->uid <= uid) {
 105                         x = x->r;
 106                 }
 107         }
 108
 109         return (p);
 110 }
 111
 112 /*
 113  * ****************************************************************************
 114  * avl_ll:
 115  *      perform LL balance rotation on an AVL tree (or the subtree).
 116  *
 117  * a    - the left child.
 118  * b    - the right child.
 119  * return - the new root.
 120  *
 121  * ****************************************************************************
 122  */
 123 static htab_itemx_t *
 124 avl_ll(
 125         htab_itemx_t *a,
 126         htab_itemx_t *b
 127 )
 128 {
 129         /* rotate right */
 130         a->l = b->r;
 131         a->bf = 0;
 132         b->r = a;
 133         b->bf = 0;
 134
 135         return (b);
 136 }
 137
 138 /*
 139  * ****************************************************************************
 140  * avl_rr:
 141  *      perform RR balance rotation on an AVL tree (or the subtree).
 142  *
 143  * a    - the left child.
 144  * b    - the right child.
 145  * return - the new root.
 146  *
 147  * ****************************************************************************
 148  */
 149 static htab_itemx_t *
 150 avl_rr(
 151         htab_itemx_t *a,
 152         htab_itemx_t *b
 153 )
 154 {
 155         /* rotate left */
 156         a->r = b->l;
 157         a->bf = 0;
 158         b->l = a;
 159         b->bf = 0;
 160
 161         return (b);
 162 }
 163
 164 /*
 165  * ****************************************************************************
 166  * avl_lr:
 167  *      perform LR balance rotation on an AVL tree (or the subtree).
 168  *
 169  * a    - the left child.
 170  * b    - the right child.
 171  * return - the new root.
 172  *
 173  * ****************************************************************************
 174  */
 175 static htab_itemx_t *
 176 avl_lr(
 177         htab_itemx_t *a,
 178         htab_itemx_t *b
 179 )
 180 {
 181         htab_itemx_t *c;
 182
 183         c = b->r;
 184
 185         /* rotate left and then right */
 186         a->l = c->r;
 187         c->r = a;
 188         b->r = c->l;
 189         c->l = b;
 190
 191         /* update balance factor */
 192         switch (c->bf) {
 193         case -1:
 194                 /* on c's right */
 195                 a->bf = 0;
 196                 b->bf = 1;
 197                 break;
 198         case 0:
 199                 /* on c itself */
 200                 a->bf = 0;
 201                 b->bf = 0;
 202                 break;
 203         case 1:
 204                 /* on c's left */
 205                 a->bf = -1;
 206                 b->bf = 0;
 207                 break;
 208         }
 209         c->bf = 0;
 210
 211         return (c);
 212 }
 213
 214 /*
 215  * ****************************************************************************
 216  * avl_rl:
 217  *      perform RL balance rotation on an AVL tree (or the subtree).
 218  *
 219  * a    - the left child.
 220  * b    - the right child.
 221  * return - the new root.
 222  *
 223  * ****************************************************************************
 224  */
 225 static htab_itemx_t *
 226 avl_rl(
 227         htab_itemx_t *a,
 228         htab_itemx_t *b
 229 )
 230 {
 231         htab_itemx_t *c;
 232
 233         c = b->l;
 234
 235         /* rotate right and then left */
 236         a->r = c->l;
 237         c->l = a;
 238         b->l = c->r;
 239         c->r = b;
 240
 241         /* update balance factor */
 242         switch (c->bf) {
 243         case -1:
 244                 /* on c's right */
 245                 a->bf = 1;
 246                 b->bf = 0;
 247                 break;
 248         case 0:
 249                 /* on c itself */
 250                 a->bf = 0;
 251                 b->bf = 0;
 252                 break;
 253         case 1:
 254                 /* on c's left */
 255                 a->bf = 0;
 256                 b->bf = -1;
 257                 break;
 258         }
 259         c->bf = 0;
 260
 261         return (c);
 262 }
 263
 264 /*
 265  * ****************************************************************************
 266  * avl_insert:
 267  *      insert a node into an AVL tree.
 268  *
 269  * tab  - the hash table.
 270  * x    - the node being added.
 271  *
 272  * ****************************************************************************
 273  */
 274 static void
 275 avl_insert(
 276         htab_t *tab,
 277         htab_itemx_t *x
 278 )
 279 {
 280         htab_itemx_t *f, *a, *p, *q, *b, *c;
 281         int d;
 282
 283         /* initialize the new one */
 284         x->bf = 0;
 285         x->l = NULL;
 286         x->r = NULL;
 287
 288         if (tab->avlt == NULL) {
 289                 tab->avlt = x;
 290         } else {
 291                 /* locate the position */
 292                 f = NULL;
 293                 a = tab->avlt;
 294                 p = tab->avlt;
 295                 q = NULL;
 296                 while (p != NULL) {
 297                         if (p->bf != 0) {
 298                                 a = p;
 299                                 f = q;
 300                         }
 301                         q = p;
 302                         if (x->uid < q->uid) {
 303                                 p = p->l;
 304                         } else {
 305                                 p = p->r;
 306                         }
 307                 }
 308                 /* insert it */
 309                 if (x->uid < q->uid) {
 310                         q->l = x;
 311                 } else {
 312                         q->r = x;
 313                 }
 314                 /* update the balance factor between a to x */
 315                 if (x->uid < a->uid) {
 316                         p = a->l;
 317                         d = 1;
 318                 } else {
 319                         p = a->r;
 320                         d = -1;
 321                 }
 322                 b = p;
 323                 while (p != x) {
 324                         if (x->uid < p->uid) {
 325                                 p->bf = 1;
 326                                 p = p->l;
 327                         } else {
 328                                 p->bf = -1;
 329                                 p = p->r;
 330                         }
 331                 }
 332                 /* brance is not broken */
 333                 if (a->bf == 0) {
 334                         a->bf = d;
 335                         goto bal_done;
 336                 } else if (a->bf + d == 0) {
 337                         a->bf = 0;
 338                         goto bal_done;
 339                 }
 340                 /* rotate the tree */
 341                 if (d == 1) {
 342                         if (b->bf == 1) {
 343                                 /* LL rotate */
 344                                 c = avl_ll(a, b);
 345                         } else if (b->bf == -1) {
 346                                 /* LR rotate */
 347                                 c = avl_lr(a, b);
 348                         }
 349                 } else {
 350                         if (b->bf == -1) {
 351                                 /* RR rotate */
 352                                 c = avl_rr(a, b);
 353                         } else if (b->bf == 1) {
 354                                 /* RL rotate */
 355                                 c = avl_rl(a, b);
 356                         }
 357                 }
 358                 /* update the parent */
 359                 if (f == NULL) {
 360                         tab->avlt = c;
 361                 } else if (f->l == a) {
 362                         f->l = c;
 363                 } else if (f->r == a) {
 364                         f->r = c;
 365                 }
 366         }
 367
 368 bal_done:
 369         if (x->uid > tab->buid) {
 370                 tab->buid = x->uid;
 371         }
 372 }
 373
 374 /*
 375  * ****************************************************************************
 376  * new_uid:
 377  *      allocate new node(s) of the avl tree.
 378  *
 379  * tab  - the hash table.
 380  * uid  - the UID of the node.
 381  * return - the newly allocated UID node.
 382  *
 383  * ****************************************************************************
 384  */
 385 static htab_itemx_t *
 386 new_uid(
 387         htab_t *tab,
 388         uint32_t uid
 389 )
 390 {
 391         htab_itemx_t *x = NULL;
 392
 393         uint32_t start, end;
 394
 395         /* overflow happened */
 396         if (uid == 0) {
 397                 /* search for an unused one */
 398                 uid ++;
 399                 while (uid != 0 &&
 400                     avl_search(tab, uid) != NULL) {
 401                         uid ++;
 402                 }
 403                 if (uid == 0) {
 404                         /* all are used up, sigh! */
 405                         return (NULL);
 406                 }
 407         }
 408
 409         /* check if there is a gap and the gap needs to be filled up */
 410         if (uid > tab->buid &&
 411             (tab->flags & UID_FLAGS_SEQ) != 0) {
 412                 start = tab->buid + 1;
 413         } else {
 414                 start = uid;
 415         }
 416         end = uid;
 417
 418         /* make new UID(s) */
 419         do {
 420                 if (x != NULL) {
 421                         x->hval = BAD_HVAL_MASK;
 422                         x->t = 0;
 423                         /* put it to the start of the fifo list */
 424                         x->n = tab->list;
 425                         tab->list = x;
 426                         if (tab->tail == NULL) {
 427                                 tab->tail = x;
 428                         }
 429                 }
 430                 x = (htab_itemx_t *)malloc(sizeof (htab_itemx_t));
 431                 if (x != NULL) {
 432                         x->uid = start;
 433                         x->n = NULL;
 434                         /* insert it to the tree */
 435                         avl_insert(tab, x);
 436                 }
 437                 start ++;
 438         } while (x != NULL && start <= end && start != 0);
 439
 440         return (x);
 441 }
 442
 443 /*
 444  * ****************************************************************************
 445  * uid_insert:
 446  *      insert a new UID node to the avl tree.
 447  *
 448  * tab  - the hash table.
 449  * uid_p- the pointer of the UID.
 450  * hval - the hash value of the new node.
 451  * return -     0: no UID value assigned;
 452  *              1: assigned an UID.
 453  *              -1: no memory.
 454  *              -2: invalid UID.
 455  *
 456  * ****************************************************************************
 457  */
 458 static int
 459 uid_insert(
 460         htab_t *tab,
 461         uint32_t *const uid_p,
 462         const uint32_t hval
 463 )
 464 {
 465         int assignx = 0;
 466
 467         uint32_t uid = *uid_p;
 468
 469         htab_itemx_t *x, *n;
 470
 471         if (uid != 0) {
 472                 /* search the existing one from the tree */
 473                 x = avl_search(tab, uid);
 474                 if (x == NULL) {
 475                         x = new_uid(tab, uid);
 476                 } else if (!BAD_HVAL(x->hval) &&
 477                     x->hval != hval) {
 478                         /* the item with this uid will override an */
 479                         /* existing item, we treat this as an error */
 480                         return (-2);
 481                 }
 482         } else {
 483                 /* assign a value */
 484                 x = tab->list;
 485                 /* strip off the used ones */
 486                 while (x != NULL &&
 487                     !BAD_HVAL(x->hval)) {
 488                         n = x->n;
 489                         x->n = NULL;
 490                         x = n;
 491                 }
 492
 493                 if (x == NULL ||
 494                     UID_REUSABLE(tab->c->timestamp(), x) == 0) {
 495                         /* none is available, make a new one */
 496                         tab->list = x;
 497                         x = new_uid(tab, tab->buid + 1);
 498                 } else {
 499                         n = x->n;
 500                         x->n = NULL;
 501                         tab->list = n;
 502                 }
 503                 /* update the available list */
 504                 if (tab->list == NULL) {
 505                         tab->tail = NULL;
 506                 }
 507                 assignx = 1;
 508                 if (x != NULL) {
 509                         *uid_p = x->uid;
 510                 }
 511         }
 512
 513         if (x == NULL) {
 514                 return (-1); /* no memory */
 515         }
 516
 517         x->hval = hval;
 518         x->t = 0; /* registration initial time */
 519
 520         return (assignx);
 521 }
 522
 523 /*
 524  * ****************************************************************************
 525  * enlarge_htab:
 526  *      enlarge the hash table when it gets too full.
 527  *
 528  * tab  - the hash table.
 529  *
 530  * ****************************************************************************
 531  */
 532 static void
 533 enlarge_htab(
 534         htab_t *tab
 535 )
 536 {
 537         htab_item_t **items;
 538         uint16_t logsize;
 539         uint32_t oldsz, newsz, mask;
 540         htab_item_t *item, *tmp, **itemp;
 541         uint16_t i;
 542         uint32_t j;
 543
 544         uint32_t uid;
 545
 546         /* enlarge the logsize by one */
 547         logsize = tab->logsize + 1;
 548         newsz = (1 << logsize);
 549         items = (htab_item_t **)calloc(
 550             newsz * tab->chunks, sizeof (htab_item_t *));
 551         /* re-hash all items to the new table */
 552         if (items != NULL) {
 553                 mask = newsz - 1;
 554                 oldsz = (1 << tab->logsize);
 555                 i = 0;
 556                 while (i < tab->chunks) {
 557                         j = 0;
 558                         while (j < oldsz) {
 559                                 item = tab->items[(i * oldsz) + j];
 560                                 while (item != NULL) {
 561                                         tmp = item->next;
 562                                         itemp = &items[(i * newsz) +
 563                                             (item->hval & mask)];
 564                                         uid = tab->c->get_uid(item->p);
 565                                         while (*itemp != NULL &&
 566                                             tab->c->get_uid((*itemp)->p) >
 567                                             uid) {
 568                                                 itemp = &(*itemp)->next;
 569                                         }
 570                                         item->next = *itemp;
 571                                         *itemp = item;
 572                                         item = tmp;
 573                                 }
 574                                 j ++;
 575                         }
 576                         i ++;
 577                 }
 578                 free(tab->items);
 579                 tab->items = items;
 580                 tab->logsize = logsize;
 581                 tab->mask = mask;
 582         } else {
 583                 isnslog(LOG_DEBUG, "enlarge_htab", "calloc() failed.");
 584         }
 585 }
 586
 587 /*
 588  * ****************************************************************************
 589  * htab_init:
 590  *      some generic initialization for the hash table.
 591  *
 592  * ****************************************************************************
 593  */
 594 void
 595 htab_init(
 596 )
 597 {
 598         /* do nothing */
 599 }
 600
 601 /*
 602  * ****************************************************************************
 603  * htab_create:
 604  *      create a new hash table.
 605  *
 606  * flags - UID_FLAGS_SEQ: the UID in the table needs to be sequential.
 607  * logsize - the hash table logsize.
 608  * chunks  - the number of seperated chunks of the table.
 609  * return  - the newly created hash table.
 610  *
 611  * ****************************************************************************
 612  */
 613 htab_t *
 614 htab_create(
 615         int flags,
 616         uint16_t logsize,
 617         uint16_t chunks
 618 )
 619 {
 620         htab_t *tab = NULL;
 621         htab_item_t **items = NULL;
 622         uint32_t count;
 623
 624         /* do not enlarge it if the logsize reaches the maximum */
 625         if (logsize <= MAX_LOGSIZE &&
 626             chunks > 0) {
 627                 tab = (htab_t *)calloc(1, sizeof (htab_t));
 628                 if (tab != NULL) {
 629                         count = (1 << logsize);
 630                         items = (htab_item_t **)calloc(
 631                             count * chunks, sizeof (htab_item_t *));
 632                         if (items != NULL) {
 633                                 tab->flags = flags;
 634                                 tab->items = items;
 635                                 tab->logsize = logsize;
 636                                 tab->chunks = chunks;
 637                                 tab->mask = count - 1;
 638                                 tab->count = 1; /* reserve one */
 639                                 tab->avlt = NULL;
 640                                 tab->buid = 0;
 641                                 tab->list = NULL;
 642                                 tab->tail = NULL;
 643                         } else {
 644                                 free(tab);
 645                                 tab = NULL;
 646                         }
 647                 }
 648         }
 649
 650         return (tab);
 651 }
 652
 653 /*
 654  * ****************************************************************************
 655  * htab_compute_hval:
 656  *      compute a hash value for the specified key.
 657  *
 658  * key - the key of the hash.
 659  * return - the hash value.
 660  *
 661  * ****************************************************************************
 662  */
 663 uint32_t
 664 htab_compute_hval(
 665         const uchar_t *key
 666 )
 667 {
 668         /* use classic Dan Bernstein hash alorigthm */
 669         uint32_t hash = 5381;
 670         int c;
 671
 672         while ((c = *key++) != 0) {
 673                 hash = ((hash << 5) + hash) + c;
 674         }
 675
 676         return (hash);
 677 }
 678
 679 /*
 680  * ****************************************************************************
 681  * htab_add:
 682  *      add an object to the hash table.
 683  *
 684  * tab  - the hash table.
 685  * p    - the object.
 686  * flag - 0: not an association object; otherwise association object.
 687  * uid_p- pointer of UID for returning.
 688  * update_p - pointer of update flag for returning.
 689  * return - error code.
 690  *
 691  * ****************************************************************************
 692  */
 693 int
 694 htab_add(
 695         htab_t *tab,
 696         void *p,
 697         int flag,
 698         uint32_t *uid_p,
 699         int *update_p
 700 )
 701 {
 702         int ec = 0;
 703
 704         htab_item_t *items = NULL, **itemp;
 705         uint32_t chunksz;
 706         uint32_t flags = 0;
 707         uint32_t hval;
 708         uint32_t uid = 0;
 709         int i;
 710
 711         /* compute the hash value */
 712         hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
 713
 714         /* check for duplicate */
 715         items = tab->items[hval & tab->mask];
 716         while (items != NULL) {
 717                 if (tab->c->cmp(items->p, p, 0) == 0) {
 718                         if (flag == 0) {
 719                                 ec = tab->c->replace_hook(items->p, p, uid_p,
 720                                     update_p == NULL ? 1 : 0);
 721                         }
 722                         if (update_p != NULL) {
 723                                 *update_p = 1;
 724                         }
 725                         items = NULL;
 726                         goto add_done;
 727                 }
 728                 items = items->next;
 729         }
 730
 731         /* add new object */
 732         if (update_p != NULL) {
 733                 *update_p = 0;
 734         }
 735
 736         /* make new items for the object */
 737         items = (htab_item_t *)calloc(tab->chunks, sizeof (htab_item_t));
 738
 739         if (items == NULL ||
 740             tab->count == 0 ||
 741             (++tab->count) == 0) {
 742                 /* no memory or table is full */
 743                 ec = ISNS_RSP_INTERNAL_ERROR;
 744                 goto add_done;
 745         }
 746
 747         /* check if the table needs is too full */
 748         chunksz = (1 << tab->logsize);
 749         if (tab->count >= (chunksz * HASH_RATIO) &&
 750             tab->logsize < MAX_LOGSIZE) {
 751                 enlarge_htab(tab);
 752                 chunksz = (1 << tab->logsize);
 753         }
 754
 755         /* put the UID of the object to the avl tree */
 756         uid = tab->c->get_uid(p);
 757         switch (uid_insert(tab, &uid, hval)) {
 758         case -2:
 759                 ec = ISNS_RSP_INVALID_REGIS;
 760                 goto add_done;
 761         case -1:
 762                 ec = ISNS_RSP_INTERNAL_ERROR;
 763                 goto add_done;
 764         case 0:
 765                 break;
 766         case 1:
 767                 tab->c->set_uid(p, uid);
 768                 break;
 769         default:
 770                 break;
 771         }
 772
 773         /* update data store before putting to hash table */
 774         if (flag == 0) {
 775                 /* not association object */
 776                 ec = tab->c->add_hook(p);
 777         }
 778
 779         /* put the object to the table */
 780         for (i = 0; ec == 0; ) {
 781                 items[i].hval = hval;
 782                 items[i].p = p;
 783                 itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
 784                 while (*itemp != NULL &&
 785                     tab->c->get_uid((*itemp)->p) > uid) {
 786                         itemp = &(*itemp)->next;
 787                 }
 788                 items[i].next = *itemp;
 789                 *itemp = &items[i];
 790                 i ++;
 791                 if (i < tab->chunks) {
 792                         hval = VALID_HVAL(tab->c->get_hval(p, i, &flags));
 793                 } else {
 794                         break;
 795                 }
 796         }
 797
 798         /* cache has been successfully updated */
 799         SET_CACHE_UPDATED();
 800
 801         /* successfully added */
 802         items = NULL;
 803
 804         if (ec == 0) {
 805                 /* perform the Default DD behavior */
 806                 tab->c->ddd(p, '+');
 807
 808                 /* set the return uid */
 809                 if (uid_p != NULL) {
 810                         *uid_p = uid;
 811                 }
 812         }
 813 add_done:
 814         if (ec != 0 && items != NULL) {
 815                 free(items);
 816         }
 817
 818         return (ec);
 819 }
 820
 821 /*
 822  * ****************************************************************************
 823  * htab_remove:
 824  *      remove an object from the hash table.
 825  *
 826  * tab  - the hash table.
 827  * p    - the lookup control for the object.
 828  * uid  - the UID of the object.
 829  * clone_flag - indicate if the removing is for an association object.
 830  * return - the removed object.
 831  *
 832  * ****************************************************************************
 833  */
 834 isns_obj_t *
 835 htab_remove(
 836         htab_t *tab,
 837         void *p,
 838         uint32_t uid,
 839         int clone_flag
 840 )
 841 {
 842         void *zhizi = NULL;
 843         void *clone = NULL;
 844         htab_item_t *items = NULL;
 845         htab_item_t *item, **itemp;
 846         htab_itemx_t *x = NULL;
 847         uint32_t chunksz;
 848         uint32_t flags;
 849         uint32_t hval;
 850         int i;
 851
 852         /* get the object hash value */
 853         if (uid != 0) {
 854                 x = avl_search(tab, uid);
 855                 if (x != NULL && !BAD_HVAL(x->hval)) {
 856                         hval = x->hval;
 857                 } else {
 858                         goto remove_done;
 859                 }
 860         } else {
 861                 flags = 0 | FLAGS_CTRL_MASK;
 862                 hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
 863         }
 864
 865         /* search the object from the table */
 866         flags = 0;
 867         chunksz = (1 << tab->logsize);
 868         for (i = 0; ; ) {
 869                 itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
 870                 item = *itemp;
 871                 while (item != NULL) {
 872                         /* found it */
 873                         if (tab->c->cmp(item->p, p, 1) == 0) {
 874                                 /* make an association object if the object */
 875                                 /* has membership in user-defined DD(s). */
 876                                 if (i == 0) {
 877                                         if ((clone = tab->c->clone(item->p,
 878                                             clone_flag)) == NULL) {
 879                                                 tab->c->ddd(item->p, '-');
 880                                                 tab->count --;
 881                                                 items = item;
 882                                                 zhizi = item->p;
 883                                         }
 884                                 }
 885                                 if (clone == NULL) {
 886                                         /* remove it */
 887                                         *itemp = item->next;
 888                                 } else if (clone == item->p) {
 889                                         /* itself is an association object */
 890                                         goto remove_done;
 891                                 } else {
 892                                         /* replace it with association */
 893                                         zhizi = item->p;
 894                                         item->p = clone;
 895                                 }
 896                                 if (i == 0) {
 897                                         /* obj has been removed or updated */
 898                                         SET_CACHE_UPDATED();
 899                                 }
 900                                 break;
 901                         }
 902                         itemp = &item->next;
 903                         item = *itemp;
 904                 }
 905                 i ++;
 906                 if (zhizi != NULL && i < tab->chunks) {
 907                         hval = VALID_HVAL(tab->c->get_hval(
 908                             zhizi, i, &flags));
 909                 } else {
 910                         break;
 911                 }
 912         }
 913
 914         /* update the node in the avl tree */
 915         if (items != NULL) {
 916                 if (x == NULL) {
 917                         uid = tab->c->get_uid(zhizi);
 918                         ASSERT(uid != 0);
 919                         x = avl_search(tab, uid);
 920                 }
 921                 ASSERT(x != NULL && !BAD_HVAL(x->hval));
 922                 /* mark the uid item as invalid */
 923                 x->hval |= BAD_HVAL_MASK;
 924                 /* update the timestamp */
 925                 x->t = tab->c->timestamp();
 926                 /* put it to the end of fifo list */
 927                 if (tab->list != NULL) {
 928                         tab->tail->n = x;
 929                 } else {
 930                         tab->list = x;
 931                 }
 932                 tab->tail = x;
 933         }
 934
 935 remove_done:
 936         if (items != NULL) {
 937                 free(items);
 938         }
 939
 940         return (zhizi);
 941 }
 942
 943 /*
 944  * ****************************************************************************
 945  * htab_lookup:
 946  *      lookup an object from the hash table.
 947  *
 948  * tab  - the hash table.
 949  * p    - the lookup control for the item.
 950  * uid  - the UID of the object.
 951  * uid_p- the pointer of UID for returning.
 952  * callback - callback function if the object is found.
 953  * rekey - flag that indicates if the callback function will update
 954  *              the key of the object.
 955  * return - error code.
 956  *
 957  * ****************************************************************************
 958  */
 959 int
 960 htab_lookup(
 961         htab_t *tab,
 962         void *p,
 963         uint32_t uid,
 964         uint32_t *uid_p,
 965         int (*callback)(void *, void *),
 966         int rekey
 967 )
 968 {
 969         uint32_t ret = 0;
 970         void *zhizi = NULL;
 971         htab_item_t *item, **itemp;
 972         htab_itemx_t *x = NULL;
 973         uint32_t chunksz;
 974         uint32_t flags = 0 | FLAGS_CTRL_MASK;
 975         uint32_t hval;
 976         int i;
 977
 978         /* compute the hash value */
 979         if (uid != 0) {
 980                 x = avl_search(tab, uid);
 981                 if (x != NULL) {
 982                         hval = x->hval;
 983                 } else {
 984                         hval = BAD_HVAL_MASK;
 985                 }
 986         } else {
 987                 hval = VALID_HVAL(tab->c->get_hval(p, 0, &flags));
 988         }
 989
 990         /* find the object */
 991         if (!BAD_HVAL(hval)) {
 992                 i = flags & FLAGS_CHUNK_MASK;
 993                 chunksz = (1 << tab->logsize);
 994                 itemp = &tab->items[(i * chunksz) + (hval & tab->mask)];
 995                 item = *itemp;
 996                 while (item != NULL) {
 997                         if (tab->c->cmp(item->p, p, 1) == 0) {
 998                                 zhizi = item->p;
 999                                 break;
1000                         }
1001                         itemp = &item->next;
1002                         item = *itemp;
1003                 }
1004         }
1005
1006         /* found it */
1007         if (zhizi != NULL) {
1008                 /* set the return uid */
1009                 if (uid_p != NULL) {
1010                         *uid_p = tab->c->get_uid(zhizi);
1011                 }
1012                 /* invoke callback */
1013                 if (callback != NULL) {
1014                         ret = callback(zhizi, p);
1015                 }
1016                 if (rekey != 0 && ret == 0) {
1017                         /* Rekey works for one-chunk hash table only. */
1018                         ASSERT(tab->chunks == 1 && x != NULL);
1019                         /* remove from previous slot */
1020                         *itemp = item->next;
1021                         /* add it to the new slot */
1022                         flags = 0;
1023                         hval = VALID_HVAL(tab->c->get_hval(zhizi, 0, &flags));
1024                         x->hval = hval;
1025                         item->hval = hval;
1026                         itemp = &tab->items[(hval & tab->mask)];
1027                         while (*itemp != NULL &&
1028                             (tab->c->get_uid((*itemp)->p) >
1029                             tab->c->get_uid(zhizi))) {
1030                                 itemp = &(*itemp)->next;
1031                         }
1032                         item->next = *itemp;
1033                         *itemp = item;
1034                 }
1035         } else if (uid_p != NULL) {
1036                 /* set the return uid to 0 */
1037                 *uid_p = 0;
1038         }
1039
1040         return (ret);
1041 }
1042
1043 /*
1044  * ****************************************************************************
1045  * htab_get_next:
1046  *      get the next object UID from the hash table.
1047  *
1048  * tab  - the hash table.
1049  * uid  - the previous objet UID.
1050  * return - the next object UID.
1051  *
1052  * ****************************************************************************
1053  */
1054 uint32_t
1055 htab_get_next(
1056         htab_t *tab,
1057         uint32_t uid
1058 )
1059 {
1060         htab_itemx_t *x;
1061
1062         do {
1063                 /* search the next node from the avl tree */
1064                 x = avl_search_next(tab, uid);
1065                 if (x != NULL) {
1066                         uid = x->uid;
1067                         /* validate the node */
1068                         if (!BAD_HVAL(x->hval)) {
1069                                 return (uid);
1070                         }
1071                 }
1072         } while (x != NULL);
1073
1074         /* no more node is available */
1075         return (0);
1076 }
1077
1078 /*
1079  * ****************************************************************************
1080  * htab_dump:
1081  *      dump all objects stored in the hash table for debug purpose.
1082  *
1083  * tab  - the hash table.
1084  *
1085  * ****************************************************************************
1086  */
1087 #ifdef DEBUG
1088 void
1089 htab_dump(
1090         htab_t *tab
1091 )
1092 {
1093         uint32_t chunksz;
1094         htab_item_t *items;
1095
1096         uint32_t i;
1097
1098         chunksz = (1 << tab->logsize);
1099
1100         for (i = 0; i < chunksz; i++) {
1101                 items = tab->items[i];
1102                 while (items != NULL) {
1103                         tab->c->dump(items->p);
1104                         items = items->next;
1105                 }
1106         }
1107 }
1108 #endif