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 *
avl_search(const htab_t * tab,const uint32_t uid)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 *
avl_search_next(const htab_t * tab,const uint32_t uid)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 *
avl_ll(htab_itemx_t * a,htab_itemx_t * b)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 *
avl_rr(htab_itemx_t * a,htab_itemx_t * b)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 *
avl_lr(htab_itemx_t * a,htab_itemx_t * b)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 *
avl_rl(htab_itemx_t * a,htab_itemx_t * b)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
avl_insert(htab_t * tab,htab_itemx_t * x)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 *
new_uid(htab_t * tab,uint32_t uid)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
uid_insert(htab_t * tab,uint32_t * const uid_p,const uint32_t hval)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
enlarge_htab(htab_t * tab)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
htab_init()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 *
htab_create(int flags,uint16_t logsize,uint16_t chunks)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
htab_compute_hval(const uchar_t * key)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
htab_add(htab_t * tab,void * p,int flag,uint32_t * uid_p,int * update_p)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 *
htab_remove(htab_t * tab,void * p,uint32_t uid,int clone_flag)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
htab_lookup(htab_t * tab,void * p,uint32_t uid,uint32_t * uid_p,int (* callback)(void *,void *),int rekey)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
htab_get_next(htab_t * tab,uint32_t uid)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
htab_dump(htab_t * tab)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
1109