xref: /illumos-gate/usr/src/cmd/isns/isnsd/htable.c (revision fcf3ce441efd61da9bb2884968af01cb7c1452cc)
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