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
31extern "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
44typedef struct htab_item {
45	uint32_t hval;
46	void *p;
47	struct htab_item *next;
48} htab_item_t;
49
50typedef 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
60typedef 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
88void htab_init(void);
89htab_t *htab_create(int, uint16_t, uint16_t);
90void htab_destroy(htab_t *);
91uint32_t htab_compute_hval(const uchar_t *);
92int htab_add(htab_t *, void *, int, uint32_t *, int *);
93isns_obj_t *htab_remove(htab_t *, void *, uint32_t, int);
94int htab_lookup(htab_t *, void *, uint32_t,
95	uint32_t *, int (*)(void *, void *), int);
96uint32_t htab_get_next(htab_t *, uint32_t);
97#ifdef DEBUG
98void htab_dump(htab_t *);
99#endif
100
101#ifdef __cplusplus
102}
103#endif
104
105#endif /* _ISNS_HTAB_H */
106