1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright (c) 1999, 2001 by Sun Microsystems, Inc.
* All rights reserved.
*/
#ifndef _HASH_H
#define _HASH_H
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* hash.h: Hash Table structures, defines, and prototypes.
*
* The locking strategy behind hash.c is actually quite simple,
* but does need some explaining. Basically, we have three different
* locks to worry about; one at the hash table level, one at the
* bucket level and one at the node level.
*
* +===================+
* | Hash | Hash | +---------+ +---------+
* | Table | Bucket |<--->|HashEntry|<--->|HashEntry|
* | | | +---------+ +---------+
* | * | * | / \ / \
* | | | | |
* | | | \ / \ /
* | | | +---------+ +---------+
* | | | | * Node | | * Node |
* +===================+ +---------+ +---------+
*
* * = Lock is present
*
* When we walk through the Hash Table to add an item, it first
* gets the hash bucket index, and locks the whole row (or bucket)
* with a write lock. a HashEntry is then added at the head of the
* bucket queue. If a node lock was requested, via a function
* parameter, the node is locked. This is particularly useful if
* additional work will be done to the node. The Hash Table lock
* is then locked with a write lock, and the table counter is
* incremented, then the lock is unlocked. Lastly, the hash
* bucket is unlocked, and the function returns.
*
* When the code needs to find a node in the hash table, the
* hash bucket (row) is locked, and all nodes in the row are
* compare with the key provided. The caller may also provide
* a pointer to a helper routine, which is used to further
* qualify searches. If a match is found, the node is locked
* (if requested), and the pointer to the node is retruned to
* the caller.
*
* If a node is to be deleted from the table, the row is write
* locked, the row is searched for a match, based on the key and
* the data to the pointer. If a match is found, the HashEntry
* is deleted. The table lock is then write locked, decremented
* and unlocked. Finally, the bucket lock is released.
*
*/
#ifdef __cplusplus
extern "C" {
#endif
enum {
LOCK_NONE,
LOCK_READ,
LOCK_WRITE
};
typedef struct hash_entry {
struct hash_entry *next;
enum {
HASH_INT_KEY,
HASH_STR_KEY
} hashKeyType;
void *data;
uint32_t key; /* Hopefully somewhere in *data */
unsigned char keyLen; /* keyLen can't be more than 255 chars now */
unsigned char *keyData;
} HashEntry;
#define HASH_TBL_SIZE 256
/*
* If uniqueData is set to non-zero, then the bucket will be searched for
* for uniqueness.
*/
typedef struct hash_table {
size_t size;
int uniqueData;
rwlock_t hashLock;
rwlock_t bucketLock[HASH_TBL_SIZE];
HashEntry *buckets[HASH_TBL_SIZE];
} HashTable;
#define HASH_BIT_COUNT 8
#ifdef _BIG_ENDIAN
#define HASHIT(key) \
((uint32_t)((key >> HASH_BIT_COUNT) ^ (key)) \
& ~(~0 << HASH_BIT_COUNT))
#else
#define HASHIT(key) \
((uint32_t)((key << HASH_BIT_COUNT) ^ (key)) >> \
(uint32_t)(32 - HASH_BIT_COUNT))
#endif
extern int InitHash(HashTable *);
extern int linkHashTableEntryUint(HashTable *, uint32_t, void *, int);
extern int linkHashTableEntryString(HashTable *, unsigned char *, uint32_t,
void *, int);
extern boolean_t delHashTableEntryUint(HashTable *, void *,
uint32_t, int);
extern boolean_t delHashTableEntryString(HashTable *, void *, unsigned char *,
uint32_t, int);
extern void *findHashTableEntryUint(HashTable *, uint32_t, int,
boolean_t (*fcnt)(void *, uint32_t, uint32_t, uint32_t), uint32_t,
uint32_t,
uint32_t);
extern void *findHashTableEntryString(HashTable *, unsigned char *, uint32_t,
int, boolean_t (*fcnt)(void *, uint32_t, uint32_t, uint32_t), uint32_t,
uint32_t, uint32_t);
extern boolean_t changeHashEntryStringToUint(HashTable *, void *,
unsigned char *, uint32_t, uint32_t);
extern void getAllHashTableEntries(HashTable *, boolean_t (*fcnt)(void *,
uint32_t), int, uint32_t, boolean_t shutdown_flag);
extern void *enumerateAllHashTableEntries(HashTable *,
uint32_t *,
uint32_t *,
int);
extern void initEnumeratorState(void *, size_t);
#ifdef __cplusplus
}
#endif
#endif /* _HASH_H */
|
