xref: /illumos-gate/usr/src/cmd/isns/isnsd/isns_htab.h (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 #ifndef _ISNS_HTAB_H
28 #define	_ISNS_HTAB_H
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 #define	HASH_RATIO	(3)
35 #define	MAX_LOGSIZE	(sizeof (uint32_t) * 8 - 1)
36 #define	HVAL_MASK	(((uint32_t)1 << MAX_LOGSIZE) - 1)
37 #define	BAD_HVAL_MASK	((uint32_t)1 << MAX_LOGSIZE)
38 #define	VALID_HVAL(H)	((H) & HVAL_MASK)
39 #define	BAD_HVAL(H)	(((H) & BAD_HVAL_MASK) == BAD_HVAL_MASK)
40 
41 #define	FLAGS_CTRL_MASK		(0x10000000)
42 #define	FLAGS_CHUNK_MASK	(0x00001111)
43 
44 typedef struct htab_item {
45 	uint32_t hval;
46 	void *p;
47 	struct htab_item *next;
48 } htab_item_t;
49 
50 typedef struct htab_itemx {
51 	uint32_t uid;
52 	uint32_t hval;
53 	uint32_t t;
54 	int bf;
55 	struct htab_itemx *l;
56 	struct htab_itemx *r;
57 	struct htab_itemx *n;
58 } htab_itemx_t;
59 
60 typedef struct htab {
61 	int flags;
62 	struct cache *c;
63 	htab_item_t **items;
64 	uint16_t logsize;
65 	uint16_t chunks;
66 	uint32_t mask;
67 	uint32_t count;
68 	/* AVL tree of the object UIDs */
69 	htab_itemx_t *avlt;
70 	/* the biggest UID in the tree */
71 	uint32_t buid;
72 	/* fifo list of available UIDs */
73 	htab_itemx_t *list;
74 	htab_itemx_t *tail;
75 } htab_t;
76 
77 #define	UID_FLAGS_SEQ	(0x1)
78 
79 #define	FOR_EACH_ITEM(HTAB, UID, STMT)	\
80 {\
81 	UID = htab_get_next(HTAB, UID);\
82 	while (UID != 0) {\
83 		STMT\
84 		UID = htab_get_next(HTAB, UID);\
85 	}\
86 }
87 
88 void htab_init(void);
89 htab_t *htab_create(int, uint16_t, uint16_t);
90 void htab_destroy(htab_t *);
91 uint32_t htab_compute_hval(const uchar_t *);
92 int htab_add(htab_t *, void *, int, uint32_t *, int *);
93 isns_obj_t *htab_remove(htab_t *, void *, uint32_t, int);
94 int htab_lookup(htab_t *, void *, uint32_t,
95 	uint32_t *, int (*)(void *, void *), int);
96 uint32_t htab_get_next(htab_t *, uint32_t);
97 #ifdef DEBUG
98 void htab_dump(htab_t *);
99 #endif
100 
101 #ifdef __cplusplus
102 }
103 #endif
104 
105 #endif /* _ISNS_HTAB_H */
106