1 | |
---|
2 | /* |
---|
3 | * bltHash.h -- |
---|
4 | * |
---|
5 | * Copyright 2001 Silicon Metrics Corporation. |
---|
6 | * |
---|
7 | * Permission to use, copy, modify, and distribute this software and |
---|
8 | * its documentation for any purpose and without fee is hereby |
---|
9 | * granted, provided that the above copyright notice appear in all |
---|
10 | * copies and that both that the copyright notice and warranty |
---|
11 | * disclaimer appear in supporting documentation, and that the names |
---|
12 | * of Lucent Technologies any of their entities not be used in |
---|
13 | * advertising or publicity pertaining to distribution of the software |
---|
14 | * without specific, written prior permission. |
---|
15 | * |
---|
16 | * Silicon Metrics disclaims all warranties with regard to this |
---|
17 | * software, including all implied warranties of merchantability and |
---|
18 | * fitness. In no event shall Lucent Technologies be liable for any |
---|
19 | * special, indirect or consequential damages or any damages |
---|
20 | * whatsoever resulting from loss of use, data or profits, whether in |
---|
21 | * an action of contract, negligence or other tortuous action, arising |
---|
22 | * out of or in connection with the use or performance of this |
---|
23 | * software. |
---|
24 | * |
---|
25 | * Bob Jenkins, 1996. hash.c. Public Domain. |
---|
26 | * Bob Jenkins, 1997. lookup8.c. Public Domain. |
---|
27 | * |
---|
28 | * Copyright (c) 1991-1993 The Regents of the University of California. |
---|
29 | * Copyright (c) 1994 Sun Microsystems, Inc. |
---|
30 | * |
---|
31 | * See the file "license.terms" for information on usage and redistribution |
---|
32 | * of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
---|
33 | * |
---|
34 | * RCS: @(#) $Id: bltHash.h.in,v 1.5 2002/07/14 00:08:13 ghowlett Exp $ |
---|
35 | */ |
---|
36 | |
---|
37 | #ifndef RP_HASH_H |
---|
38 | #define RP_HASH_H 1 |
---|
39 | |
---|
40 | #ifndef RP_INT_H |
---|
41 | #ifndef SIZEOF_LONG |
---|
42 | #define SIZEOF_LONG @SIZEOF_LONG@ |
---|
43 | #endif |
---|
44 | #ifndef SIZEOF_LONG_LONG |
---|
45 | #define SIZEOF_LONG_LONG @SIZEOF_LONG_LONG@ |
---|
46 | #endif |
---|
47 | #ifndef SIZEOF_INT |
---|
48 | #define SIZEOF_INT @SIZEOF_INT@ |
---|
49 | #endif |
---|
50 | #ifndef SIZEOF_VOID_P |
---|
51 | #define SIZEOF_VOID_P @SIZEOF_VOID_P@ |
---|
52 | #endif |
---|
53 | #ifndef HAVE_INTTYPES_H |
---|
54 | #if @HAVE_INTTYPES_H@ |
---|
55 | #define HAVE_INTTYPES_H 1 |
---|
56 | #endif |
---|
57 | #endif |
---|
58 | #endif /* !RP_INT_H */ |
---|
59 | |
---|
60 | #ifdef HAVE_INTTYPES_H |
---|
61 | #include <inttypes.h> |
---|
62 | #else |
---|
63 | #if (SIZEOF_VOID_P == 8) |
---|
64 | #if (SIZEOF_LONG == 8) |
---|
65 | typedef signed long int64_t; |
---|
66 | typedef unsigned long uint64_t; |
---|
67 | #else |
---|
68 | typedef signed long long int64_t; |
---|
69 | typedef unsigned long long uint64_t; |
---|
70 | #endif /* SIZEOF_LONG == 8 */ |
---|
71 | #else |
---|
72 | #ifndef __CYGWIN__ |
---|
73 | typedef signed int int32_t; |
---|
74 | #endif /* __CYGWIN__ */ |
---|
75 | typedef unsigned int uint32_t; |
---|
76 | #endif /* SIZEOF_VOID_P == 8 */ |
---|
77 | #endif /* HAVE_INTTYPES_H */ |
---|
78 | |
---|
79 | #if (SIZEOF_VOID_P == 8) |
---|
80 | typedef uint64_t Rp_Hash; |
---|
81 | #else |
---|
82 | typedef uint32_t Rp_Hash; |
---|
83 | #endif /* SIZEOF_VOID_P == 8 */ |
---|
84 | |
---|
85 | #include "RpPool.h" |
---|
86 | |
---|
87 | /* |
---|
88 | * Acceptable key types for hash tables: |
---|
89 | */ |
---|
90 | #define RP_STRING_KEYS 0 |
---|
91 | #define RP_ONE_WORD_KEYS ((size_t)-1) |
---|
92 | |
---|
93 | /* |
---|
94 | * Forward declaration of Rp_HashTable. Needed by some C++ compilers |
---|
95 | * to prevent errors when the forward reference to Rp_HashTable is |
---|
96 | * encountered in the Rp_HashEntry structure. |
---|
97 | */ |
---|
98 | |
---|
99 | #ifdef __cplusplus |
---|
100 | struct Rp_HashTable; |
---|
101 | #endif |
---|
102 | |
---|
103 | typedef union { /* Key has one of these forms: */ |
---|
104 | void *oneWordValue; /* One-word value for key. */ |
---|
105 | unsigned long words[1]; /* Multiple integer words for key. |
---|
106 | * The actual size will be as large |
---|
107 | * as necessary for this table's |
---|
108 | * keys. */ |
---|
109 | char string[4]; /* string for key. The actual size |
---|
110 | * will be as large as needed to hold |
---|
111 | * the key. */ |
---|
112 | } Rp_HashKey; |
---|
113 | |
---|
114 | /* |
---|
115 | * Structure definition for an entry in a hash table. No-one outside |
---|
116 | * Rp should access any of these fields directly; use the macros |
---|
117 | * defined below. |
---|
118 | */ |
---|
119 | typedef struct Rp_HashEntry { |
---|
120 | struct Rp_HashEntry *nextPtr; /* Pointer to next entry in this |
---|
121 | * hash bucket, or NULL for end of |
---|
122 | * chain. */ |
---|
123 | Rp_Hash hval; |
---|
124 | |
---|
125 | ClientData clientData; /* Application stores something here |
---|
126 | * with Rp_SetHashValue. */ |
---|
127 | Rp_HashKey key; /* MUST BE LAST FIELD IN RECORD!! */ |
---|
128 | } Rp_HashEntry; |
---|
129 | |
---|
130 | /* |
---|
131 | * Structure definition for a hash table. Must be in blt.h so clients |
---|
132 | * can allocate space for these structures, but clients should never |
---|
133 | * access any fields in this structure. |
---|
134 | */ |
---|
135 | #define RP_SMALL_HASH_TABLE 4 |
---|
136 | typedef struct Rp_HashTable { |
---|
137 | Rp_HashEntry **buckets; /* Pointer to bucket array. Each |
---|
138 | * element points to first entry in |
---|
139 | * bucket's hash chain, or NULL. */ |
---|
140 | Rp_HashEntry *staticBuckets[RP_SMALL_HASH_TABLE]; |
---|
141 | /* Bucket array used for small tables |
---|
142 | * (to avoid mallocs and frees). */ |
---|
143 | size_t numBuckets; /* Total number of buckets allocated |
---|
144 | * at **buckets. */ |
---|
145 | size_t numEntries; /* Total number of entries present |
---|
146 | * in table. */ |
---|
147 | size_t rebuildSize; /* Enlarge table when numEntries gets |
---|
148 | * to be this large. */ |
---|
149 | Rp_Hash mask; /* Mask value used in hashing |
---|
150 | * function. */ |
---|
151 | unsigned int downShift; /* Shift count used in hashing |
---|
152 | * function. Designed to use high |
---|
153 | * order bits of randomized keys. */ |
---|
154 | size_t keyType; /* Type of keys used in this table. |
---|
155 | * It's either RP_STRING_KEYS, |
---|
156 | * RP_ONE_WORD_KEYS, or an integer |
---|
157 | * giving the number of ints that |
---|
158 | * is the size of the key. |
---|
159 | */ |
---|
160 | Rp_HashEntry *(*findProc) _ANSI_ARGS_((struct Rp_HashTable *tablePtr, |
---|
161 | CONST void *key)); |
---|
162 | Rp_HashEntry *(*createProc) _ANSI_ARGS_((struct Rp_HashTable *tablePtr, |
---|
163 | CONST void *key, int *newPtr)); |
---|
164 | |
---|
165 | Rp_Pool hPool; /* Pointer to the pool allocator used |
---|
166 | * for entries in this hash table. If |
---|
167 | * NULL, the standard Tcl_Alloc, |
---|
168 | * Tcl_Free routines will be used |
---|
169 | * instead. |
---|
170 | */ |
---|
171 | } Rp_HashTable; |
---|
172 | |
---|
173 | /* |
---|
174 | * Structure definition for information used to keep track of searches |
---|
175 | * through hash tables: |
---|
176 | */ |
---|
177 | |
---|
178 | typedef struct { |
---|
179 | Rp_HashTable *tablePtr; /* Table being searched. */ |
---|
180 | unsigned long nextIndex; /* Index of next bucket to be |
---|
181 | * enumerated after present one. */ |
---|
182 | Rp_HashEntry *nextEntryPtr; /* Next entry to be enumerated in the |
---|
183 | * the current bucket. */ |
---|
184 | } Rp_HashSearch; |
---|
185 | |
---|
186 | /* |
---|
187 | * Macros for clients to use to access fields of hash entries: |
---|
188 | */ |
---|
189 | |
---|
190 | #define Rp_GetHashValue(h) ((h)->clientData) |
---|
191 | #define Rp_SetHashValue(h, value) ((h)->clientData = (ClientData)(value)) |
---|
192 | #define Rp_GetHashKey(tablePtr, h) \ |
---|
193 | ((void *) (((tablePtr)->keyType == RP_ONE_WORD_KEYS) ? \ |
---|
194 | (void *)(h)->key.oneWordValue : (h)->key.string)) |
---|
195 | |
---|
196 | /* |
---|
197 | * Macros to use for clients to use to invoke find and create procedures |
---|
198 | * for hash tables: |
---|
199 | */ |
---|
200 | #define Rp_FindHashEntry(tablePtr, key) \ |
---|
201 | (*((tablePtr)->findProc))(tablePtr, key) |
---|
202 | #define Rp_CreateHashEntry(tablePtr, key, newPtr) \ |
---|
203 | (*((tablePtr)->createProc))(tablePtr, key, newPtr) |
---|
204 | |
---|
205 | EXTERN void Rp_InitHashTable _ANSI_ARGS_((Rp_HashTable *tablePtr, |
---|
206 | size_t keyType)); |
---|
207 | |
---|
208 | EXTERN void Rp_InitHashTableWithPool _ANSI_ARGS_((Rp_HashTable *tablePtr, |
---|
209 | size_t keyType)); |
---|
210 | |
---|
211 | EXTERN void Rp_DeleteHashTable _ANSI_ARGS_((Rp_HashTable *tablePtr)); |
---|
212 | |
---|
213 | EXTERN void Rp_DeleteHashEntry _ANSI_ARGS_((Rp_HashTable *tablePtr, |
---|
214 | Rp_HashEntry *entryPtr)); |
---|
215 | |
---|
216 | EXTERN Rp_HashEntry *Rp_FirstHashEntry _ANSI_ARGS_((Rp_HashTable *tablePtr, |
---|
217 | Rp_HashSearch *searchPtr)); |
---|
218 | |
---|
219 | EXTERN Rp_HashEntry *Rp_NextHashEntry _ANSI_ARGS_((Rp_HashSearch *srchPtr)); |
---|
220 | |
---|
221 | EXTERN char *Rp_HashStats _ANSI_ARGS_((Rp_HashTable *tablePtr)); |
---|
222 | |
---|
223 | #endif /* RP_HASH_H */ |
---|