1 // ************************************************************************
2 //
3 // Copyright (c) 1995-2002 Juniper Networks, Inc. All rights reserved.
4 //
5 // Permission is hereby granted, without written agreement and without
6 // license or royalty fees, to use, copy, modify, and distribute this
7 // software and its documentation for any purpose, provided that the
8 // above copyright notice and the following three paragraphs appear in
9 // all copies of this software.
10 //
11 // IN NO EVENT SHALL JUNIPER NETWORKS, INC. BE LIABLE TO ANY PARTY FOR
12 // DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
13 // ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
14 // JUNIPER NETWORKS, INC. HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
15 // DAMAGE.
16 //
17 // JUNIPER NETWORKS, INC. SPECIFICALLY DISCLAIMS ANY WARRANTIES,
18 // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
20 // NON-INFRINGEMENT.
21 //
22 // THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND JUNIPER
23 // NETWORKS, INC. HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
24 // UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
25 //
26 // ************************************************************************
27
28
29
30 /* ihash.c --
31 *
32 * Implements "internal" hash, i.e. hash on user supplied structures,
33 * without need for parallel hash entry structs.
34 *
35 * pointers involving users structs are cast to (void *)
36 * This should make the pointer arithmetic work out regardless
37 * of alignments within structs.
38 *
39 * See ihash.h
40 *
41 */
42
43 #define DEREF(ptr,offset) ((ptr)+(offset))
44
45 static char rcsid[] = "$Header$";
46 #include <string.h>
47 #include <stdio.h>
48 #include "utils/magic.h"
49 #include "utils/malloc.h"
50 #include "utils/utils.h"
51 #include "utils/ihash.h"
52
53
54 /*
55 * The following defines the ratio of # entries to # buckets
56 * at which we rebuild the table to make it larger.
57 */
58 static int iHashResizeRatio = 3;
59
60 /* forward reference */
61 static void iHashResize(IHashTable *table);
62
63 /* create a new hash table */
64 /* offsets should be generated by pointer subtraction of (void *) pointers */
IHashInit(int nBuckets,int keyOffset,int nextOffset,int (* hashFn)(void * key),int (* sameKeyFn)(void * key1,void * key2))65 extern IHashTable *IHashInit(
66 int nBuckets,
67 int keyOffset,
68 int nextOffset,
69 int (*hashFn)(void* key),
70 int (*sameKeyFn)(void* key1, void* key2)
71 )
72 {
73 IHashTable *table;
74
75 table = (IHashTable *)mallocMagic(sizeof(IHashTable));
76 table->iht_table = (void **)callocMagic(sizeof(void *)*nBuckets);
77 table->iht_nBucketsInit = nBuckets;
78 table->iht_nBuckets = nBuckets;
79 table->iht_nEntries = 0;
80 table->iht_keyOffset = keyOffset;
81 table->iht_nextOffset = nextOffset;
82 table->iht_hashFn = hashFn;
83 table->iht_sameKeyFn = sameKeyFn;
84
85 return table;
86 }
87
88
89
90 /* free hash table (does not free client structures) */
IHashFree(IHashTable * table)91 void IHashFree(IHashTable *table)
92 {
93 freeMagic((char *) table->iht_table); /* free buckets */
94 freeMagic((char *) table);
95 }
96
97 /* delete all entrys (and restore initial hash table size) */
IHashClear(IHashTable * table)98 void IHashClear(IHashTable *table)
99 {
100 /* reinitial bucket array */
101 freeMagic((char *) table->iht_table);
102 table->iht_table = (void **)callocMagic(sizeof(void *)*table->iht_nBucketsInit);
103
104 table->iht_nBuckets = table->iht_nBucketsInit;
105 table->iht_nEntries = 0;
106 }
107
108 /* lookup an entry in table */
IHashLookUp(IHashTable * table,void * key)109 void *IHashLookUp(IHashTable *table, void *key)
110 {
111 int hash;
112 int bucket;
113 void *entry;
114
115 hash = (table->iht_hashFn)(key);
116 bucket = ABS(hash) % table->iht_nBuckets;
117
118 for(entry=table->iht_table[bucket];
119 entry && !(table->iht_sameKeyFn)(key, DEREF(entry,(table->iht_keyOffset)));
120 entry = *((void **) DEREF(entry,table->iht_nextOffset))) /* empty body*/;
121
122 return entry;
123 }
124
125
126 /* return next matching entry */
IHashLookUpNext(IHashTable * table,void * prevEntry)127 void *IHashLookUpNext(IHashTable *table, void *prevEntry)
128 {
129 void *entry;
130 void *key = DEREF(prevEntry,table->iht_keyOffset);
131 int hash = (table->iht_hashFn)(key);
132 int bucket = ABS(hash) % table->iht_nBuckets;
133
134 for(entry = *((void **) DEREF(prevEntry,table->iht_nextOffset));
135 entry && !(table->iht_sameKeyFn)(key,DEREF(entry,table->iht_keyOffset));
136 entry = *((void **) DEREF(entry,table->iht_nextOffset))) /* empty body*/;
137
138 return entry;
139 }
140
141 /* add an entry in table */
IHashAdd(IHashTable * table,void * entry)142 void IHashAdd(IHashTable *table, void *entry)
143 {
144 int hash;
145 int bucket;
146
147 /* ASSERT(!IHashLookUp(IHashTable, entry+IHashTable->iht_keyOffset),"IHashAdd"); */
148
149 hash = (table->iht_hashFn)(DEREF(entry,table->iht_keyOffset));
150 bucket = ABS(hash) % table->iht_nBuckets;
151
152 *(void **)DEREF(entry,table->iht_nextOffset) = table->iht_table[bucket];
153 table->iht_table[bucket] = entry;
154 table->iht_nEntries++;
155
156 /* if table getting crowded, resize it */
157 if(table->iht_nEntries/table->iht_nBuckets >= iHashResizeRatio)
158 {
159 iHashResize(table);
160 }
161 }
162
163 /* deletes an entry from table */
164 /*
165 * NOTE: bplane code assumes IHashDelete() does not restructure table!
166 * (IHashLookUpNext() is called before IHashDelete(), and then the enum.
167 * is continued with further IHashLookUpNext() calls.
168 */
IHashDelete(IHashTable * table,void * entry)169 void IHashDelete(IHashTable *table, void *entry)
170 {
171 int hash;
172 int bucket;
173 void **pp;
174 int nextOffset = table->iht_nextOffset;
175
176 hash = (table->iht_hashFn)DEREF(entry,table->iht_keyOffset);
177 bucket = ABS(hash) % table->iht_nBuckets;
178
179 for(pp = &table->iht_table[bucket];
180 (*pp) && (*pp) != entry;
181 pp = DEREF((*pp),nextOffset));
182
183 ASSERT(*pp,"IHashDelete");
184 (*pp) = * (void **) DEREF(entry,nextOffset);
185 table->iht_nEntries--;
186 }
187
188 /* return number of entries in table */
IHashEntries(IHashTable * table)189 int IHashEntries(IHashTable *table)
190 {
191 return table->iht_nEntries;
192 }
193
194 /* call back client func on each entry in hashtable */
IHashEnum(IHashTable * table,void (* clientFunc)(void * entry))195 void IHashEnum(IHashTable *table, void (*clientFunc)(void *entry))
196 {
197 int bucket;
198
199 for(bucket=0; bucket<table->iht_nBuckets; bucket++)
200 {
201 void *entry;
202 for(entry=table->iht_table[bucket];
203 entry;
204 entry = *((void **) DEREF(entry,table->iht_nextOffset)))
205 {
206 (*clientFunc)(entry);
207 }
208 }
209 }
210
211 /* grow hash table */
iHashResize(IHashTable * table)212 static void iHashResize(IHashTable *table)
213 {
214 void **oldBuckets = table->iht_table;
215 int oldSize = table->iht_nBuckets;
216 int newSize = oldSize*4;
217 int bucket;
218
219 /* alloc a new table */
220 table->iht_table = (void **)callocMagic(sizeof(void *)*newSize);
221 table->iht_nBuckets = newSize;
222 table->iht_nEntries = 0;
223
224 /* add back all entries in old table */
225 for(bucket=0; bucket<oldSize; bucket++)
226 {
227 void *entry;
228 void *next;
229 for(entry=oldBuckets[bucket];
230 entry;
231 entry = next)
232 {
233 next = *((void **) DEREF(entry,table->iht_nextOffset));
234 IHashAdd(table,entry);
235 }
236 }
237
238 /* finally, free old table */
239 freeMagic((char *) oldBuckets);
240 }
241
242 /* print out statistics */
IHashStats(IHashTable * table)243 void IHashStats(IHashTable *table)
244 {
245 int bucket;
246
247 fprintf(stderr,"Internal Hash Statistics:\n");
248 fprintf(stderr,"\tinitial buckets = %d\n", table->iht_nBucketsInit);
249 fprintf(stderr,"\tbuckets = %d\n", table->iht_nBuckets);
250 fprintf(stderr,"\tentries = %d\n", table->iht_nEntries);
251 fprintf(stderr,"\tkey offset = %d\n", table->iht_keyOffset);
252 fprintf(stderr,"\tnext offset = %d\n", table->iht_nextOffset);
253 fprintf(stderr,"\ndistribution: ");
254
255 for(bucket=0; bucket<table->iht_nBuckets; bucket++)
256 {
257 void *entry;
258 int num = 0;
259 for(entry=table->iht_table[bucket];
260 entry;
261 entry = *((void **) DEREF(entry,table->iht_nextOffset)))
262 {
263 num++;
264 }
265 fprintf(stderr,"%d ",num);
266 }
267 }
268
269 /* return statistics on hash table (returns memory utilized by table) */
IHashStats2(IHashTable * table,int * nBuckets,int * nEntries)270 int IHashStats2(IHashTable *table,
271 int *nBuckets, /* if non-null return num buckets here */
272 int *nEntries) /* if non-null return num entries here */
273 {
274
275 if(nBuckets) *nBuckets = table->iht_nBuckets;
276 if(nEntries) *nEntries = table->iht_nEntries;
277
278 return
279 IHashAlignedSize(sizeof(IHashTable)) +
280 IHashAlignedSize(sizeof(void *)* table->iht_nBuckets);
281 }
282
283 /* hash for key fields that are pointers to strings */
IHashStringPKeyHash(void * key)284 int IHashStringPKeyHash(void *key)
285 {
286 char *s = * (char **) key;
287 int i=0;
288
289 /* Add up the characters as though this were a number */
290 while (*s != 0) i = (i*10) + (*s++ - '0');
291 if(i<0) i = -i;
292
293 return i;
294 }
295
296 /* compare string pointer keys */
IHashStringPKeyEq(void * key1,void * key2)297 int IHashStringPKeyEq(void *key1, void *key2)
298 {
299 return strcmp(* (char **) key1, * (char **) key2)==0;
300 }
301
302 /* hash for key fields that are strings */
IHashStringKeyHash(void * key)303 int IHashStringKeyHash(void *key)
304 {
305 char *s = (char *) key;
306 int i=0;
307
308 /* Add up the characters as though this were a number */
309 while (*s != 0) i = (i*10) + (*s++ - '0');
310 if(i<0) i = -i;
311
312 return i;
313 }
314
315 /* compare string keys */
IHashStringKeyEq(void * key1,void * key2)316 int IHashStringKeyEq(void *key1, void *key2)
317 {
318 return strcmp((char *) key1, (char *) key2)==0;
319 }
320
321 /* hash for key fields that are 32 bit words */
IHashWordKeyHash(void * keyp)322 int IHashWordKeyHash(void *keyp)
323 {
324 /* just use the value of word itself! */
325 return * (int *) keyp;
326 }
327
328 /* compare struc for 32 bit word keys */
IHashWordKeyEq(void * key1p,void * key2p)329 int IHashWordKeyEq(void *key1p, void *key2p)
330 {
331 return ( *(int *) key1p == * (int *) key2p);
332 }
333
334
335 /* hash for n-byte field */
336 static __inline__ int
iHash(void * key,int n)337 iHash(void *key, int n)
338 {
339 char *s = (char *) key;
340 int hash=0;
341 int i;
342
343 /* Add up the characters as though this were a number */
344 for(i=0;i<n;i++) hash = (hash*10) + (s[i] - '0');
345 if(hash<0) hash = -hash;
346
347 return hash;
348 }
349
350 /* hash for key fields that are four words long */
IHash4WordKeyHash(void * keyp)351 int IHash4WordKeyHash(void *keyp)
352 {
353 return iHash(keyp,4*sizeof(int));
354 }
355
356 /* compare struc for 4 word keys */
IHash4WordKeyEq(void * key1p,void * key2p)357 int IHash4WordKeyEq(void *key1p, void *key2p)
358 {
359 return (memcmp(key1p,key2p,4*sizeof(int)) == 0);
360 }
361