debuggers.hg

view tools/vnet/libxutil/hash_table.c @ 0:7d21f7218375

Exact replica of unstable on 051908 + README-this
author Mukesh Rathor
date Mon May 19 15:34:57 2008 -0700 (2008-05-19)
parents
children
line source
1 /*
2 * Copyright (C) 2001 - 2005 Mike Wray <mike.wray@hp.com>
3 *
4 * This library is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation; either version 2.1 of the License, or
7 * (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
19 #ifdef __KERNEL__
20 # include <linux/config.h>
21 # include <linux/module.h>
22 # include <linux/kernel.h>
23 # include <linux/errno.h>
24 #else
25 # include <errno.h>
26 # include <stddef.h>
27 #endif
29 #include "allocate.h"
30 #include "hash_table.h"
32 /** @file
33 * Base support for hashtables.
34 *
35 * Hash codes are reduced modulo the number of buckets to index tables,
36 * so there is no need for hash functions to limit the range of hashcodes.
37 * In fact it is assumed that hashcodes do not change when the number of
38 * buckets in the table changes.
39 */
41 /*============================================================================*/
42 /*
43 --------------------------------------------------------------------
44 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
45 You can use this free for any purpose. It has no warranty.
46 --------------------------------------------------------------------
47 */
49 #define hashsize(n) ((ub4)1<<(n))
50 #define hashmask(n) (hashsize(n)-1)
52 /*
53 --------------------------------------------------------------------
54 mix -- mix 3 32-bit values reversibly.
55 For every delta with one or two bit set, and the deltas of all three
56 high bits or all three low bits, whether the original value of a,b,c
57 is almost all zero or is uniformly distributed,
58 * If mix() is run forward or backward, at least 32 bits in a,b,c
59 have at least 1/4 probability of changing.
60 * If mix() is run forward, every bit of c will change between 1/3 and
61 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
62 mix() was built out of 36 single-cycle latency instructions in a
63 structure that could supported 2x parallelism, like so:
64 a -= b;
65 a -= c; x = (c>>13);
66 b -= c; a ^= x;
67 b -= a; x = (a<<8);
68 c -= a; b ^= x;
69 c -= b; x = (b>>13);
70 ...
71 Unfortunately, superscalar Pentiums and Sparcs can't take advantage
72 of that parallelism. They've also turned some of those single-cycle
73 latency instructions into multi-cycle latency instructions. Still,
74 this is the fastest good hash I could find. There were about 2^^68
75 to choose from. I only looked at a billion or so.
76 --------------------------------------------------------------------
77 */
78 #define mix(a,b,c) \
79 { \
80 a -= b; a -= c; a ^= (c>>13); \
81 b -= c; b -= a; b ^= (a<<8); \
82 c -= a; c -= b; c ^= (b>>13); \
83 a -= b; a -= c; a ^= (c>>12); \
84 b -= c; b -= a; b ^= (a<<16); \
85 c -= a; c -= b; c ^= (b>>5); \
86 a -= b; a -= c; a ^= (c>>3); \
87 b -= c; b -= a; b ^= (a<<10); \
88 c -= a; c -= b; c ^= (b>>15); \
89 }
91 /*
92 --------------------------------------------------------------------
93 hash() -- hash a variable-length key into a 32-bit value
94 k : the key (the unaligned variable-length array of bytes)
95 len : the length of the key, counting by bytes
96 level : can be any 4-byte value
97 Returns a 32-bit value. Every bit of the key affects every bit of
98 the return value. Every 1-bit and 2-bit delta achieves avalanche.
99 About 36+6len instructions.
101 The best hash table sizes are powers of 2. There is no need to do
102 mod a prime (mod is sooo slow!). If you need less than 32 bits,
103 use a bitmask. For example, if you need only 10 bits, do
104 h = (h & hashmask(10));
105 In which case, the hash table should have hashsize(10) elements.
107 If you are hashing n strings (ub1 **)k, do it like this:
108 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
110 By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
111 code any way you wish, private, educational, or commercial. It's free.
113 See http://burlteburtle.net/bob/hash/evahash.html
114 Use for hash table lookup, or anything where one collision in 2^32 is
115 acceptable. Do NOT use for cryptographic purposes.
116 --------------------------------------------------------------------
117 */
119 static inline ub4 _hash(const ub1 *k, ub4 length, ub4 initval)
120 //register ub1 *k; /* the key */
121 //register ub4 length; /* the length of the key */
122 //register ub4 initval; /* the previous hash, or an arbitrary value */
123 {
124 /*register*/ ub4 a,b,c,len;
126 /* Set up the internal state */
127 len = length;
128 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
129 c = initval; /* the previous hash value */
131 /*---------------------------------------- handle most of the key */
132 while (len >= 12)
133 {
134 a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
135 b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
136 c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
137 mix(a,b,c);
138 k += 12; len -= 12;
139 }
141 /*------------------------------------- handle the last 11 bytes */
142 c += length;
143 switch(len) /* all the case statements fall through */
144 {
145 case 11: c+=((ub4)k[10]<<24);
146 case 10: c+=((ub4)k[9]<<16);
147 case 9 : c+=((ub4)k[8]<<8);
148 /* the first byte of c is reserved for the length */
149 case 8 : b+=((ub4)k[7]<<24);
150 case 7 : b+=((ub4)k[6]<<16);
151 case 6 : b+=((ub4)k[5]<<8);
152 case 5 : b+=k[4];
153 case 4 : a+=((ub4)k[3]<<24);
154 case 3 : a+=((ub4)k[2]<<16);
155 case 2 : a+=((ub4)k[1]<<8);
156 case 1 : a+=k[0];
157 /* case 0: nothing left to add */
158 }
159 mix(a,b,c);
160 /*-------------------------------------------- report the result */
161 return c;
162 }
164 ub4 hash(const ub1 *k, ub4 length, ub4 initval){
165 return _hash(k, length, initval);
166 }
168 /*============================================================================*/
170 /** Get the bucket for a hashcode in a hash table.
171 *
172 * @param table to get bucket from
173 * @param hashcode to get bucket for
174 * @return bucket
175 */
176 inline HTBucket * get_bucket(HashTable *table, Hashcode hashcode){
177 return table->buckets + (hashcode % table->buckets_n);
178 }
180 /** Initialize a hash table.
181 *
182 * @param table to initialize
183 */
184 static void HashTable_init(HashTable *table){
185 int i;
187 for(i = 0; i < table->buckets_n; i++){
188 HTBucket *bucket = get_bucket(table, i);
189 bucket->head = NULL;
190 bucket->count = 0;
191 }
192 table->entry_count = 0;
193 }
195 /** Allocate a new hashtable.
196 * If the number of buckets is not positive the default is used.
197 *
198 * @param buckets_n number of buckets
199 * @return new hashtable or null
200 */
201 HashTable *HashTable_new(int buckets_n){
202 HashTable *z = ALLOCATE(HashTable);
203 if(!z) goto exit;
204 if(buckets_n <= 0){
205 buckets_n = HT_BUCKETS_N;
206 }
207 z->buckets = (HTBucket*)allocate(buckets_n * sizeof(HTBucket));
208 if(!z->buckets){
209 deallocate(z);
210 z = NULL;
211 goto exit;
212 }
213 z->buckets_n = buckets_n;
214 HashTable_init(z);
215 exit:
216 return z;
217 }
219 /** Free a hashtable.
220 * Any entries are removed and freed.
221 *
222 * @param h hashtable (ignored if null)
223 */
224 void HashTable_free(HashTable *h){
225 if(h){
226 HashTable_clear(h);
227 deallocate(h->buckets);
228 deallocate(h);
229 }
230 }
232 /** Push an entry on the list in the bucket for a given hashcode.
233 *
234 * @param table to add entry to
235 * @param hashcode for the entry
236 * @param entry to add
237 */
238 static inline void push_on_bucket(HashTable *table, Hashcode hashcode,
239 HTEntry *entry){
240 HTBucket *bucket;
241 HTEntry *old_head;
243 bucket = get_bucket(table, hashcode);
244 old_head = bucket->head;
245 bucket->count++;
246 bucket->head = entry;
247 entry->next = old_head;
248 }
250 /** Change the number of buckets in a hashtable.
251 * No-op if the number of buckets is not positive.
252 * Existing entries are reallocated to buckets based on their hashcodes.
253 * The table is unmodified if the number of buckets cannot be changed.
254 *
255 * @param table hashtable
256 * @param buckets_n new number of buckets
257 * @return 0 on success, error code otherwise
258 */
259 int HashTable_set_buckets_n(HashTable *table, int buckets_n){
260 int err = 0;
261 HTBucket *old_buckets = table->buckets;
262 int old_buckets_n = table->buckets_n;
263 int i;
265 if(buckets_n <= 0){
266 err = -EINVAL;
267 goto exit;
268 }
269 table->buckets = (HTBucket*)allocate(buckets_n * sizeof(HTBucket));
270 if(!table->buckets){
271 err = -ENOMEM;
272 table->buckets = old_buckets;
273 goto exit;
274 }
275 table->buckets_n = buckets_n;
276 for(i=0; i < old_buckets_n; i++){
277 HTBucket *bucket = old_buckets + i;
278 HTEntry *entry, *next;
279 for(entry = bucket->head; entry; entry = next){
280 next = entry->next;
281 push_on_bucket(table, entry->hashcode, entry);
282 }
283 }
284 deallocate(old_buckets);
285 exit:
286 return err;
287 }
289 /** Adjust the number of buckets so the table is neither too full nor too empty.
290 * The table is unmodified if adjusting fails.
291 *
292 * @param table hash table
293 * @param buckets_min minimum number of buckets (use default if 0 or negative)
294 * @return 0 on success, error code otherwise
295 */
296 int HashTable_adjust(HashTable *table, int buckets_min){
297 int buckets_n = 0;
298 int err = 0;
299 if(buckets_min <= 0) buckets_min = HT_BUCKETS_N;
300 if(table->entry_count >= table->buckets_n){
301 // The table is dense - expand it.
302 buckets_n = 2 * table->buckets_n;
303 } else if((table->buckets_n > buckets_min) &&
304 (4 * table->entry_count < table->buckets_n)){
305 // The table is more than minimum size and sparse - shrink it.
306 buckets_n = 2 * table->entry_count;
307 if(buckets_n < buckets_min) buckets_n = buckets_min;
308 }
309 if(buckets_n){
310 err = HashTable_set_buckets_n(table, buckets_n);
311 }
312 return err;
313 }
315 /** Allocate a new entry for a given value.
316 *
317 * @param value to put in the entry
318 * @return entry, or 0 on failure
319 */
320 HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value){
321 HTEntry *z = ALLOCATE(HTEntry);
322 if(z){
323 z->hashcode = hashcode;
324 z->key = key;
325 z->value = value;
326 }
327 return z;
328 }
330 /** Free an entry.
331 *
332 * @param z entry to free
333 */
334 inline void HTEntry_free(HTEntry *z){
335 if(z){
336 deallocate(z);
337 }
338 }
340 /** Free an entry in a hashtable.
341 * The table's entry_free_fn is used is defined, otherwise
342 * the HTEntry itself is freed.
343 *
344 * @param table hashtable
345 * @param entry to free
346 */
347 inline void HashTable_free_entry(HashTable *table, HTEntry *entry){
348 if(!entry) return;
349 if(table && table->entry_free_fn){
350 table->entry_free_fn(table, entry);
351 } else {
352 HTEntry_free(entry);
353 }
354 }
356 /** Get the first entry satisfying a test from the bucket for the
357 * given hashcode.
358 *
359 * @param table to look in
360 * @param hashcode indicates the bucket
361 * @param test_fn test to apply to elements
362 * @param arg first argument to calls to test_fn
363 * @return entry found, or 0
364 */
365 inline HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
366 TableTestFn *test_fn, TableArg arg){
367 HTBucket *bucket;
368 HTEntry *entry = NULL;
369 HTEntry *next;
371 bucket = get_bucket(table, hashcode);
372 for(entry = bucket->head; entry; entry = next){
373 next = entry->next;
374 if(test_fn(arg, table, entry)){
375 break;
376 }
377 }
378 return entry;
379 }
381 /** Test hashtable keys for equality.
382 * Uses the table's key_equal_fn if defined, otherwise pointer equality.
383 *
384 * @param key1 key to compare
385 * @param key2 key to compare
386 * @return 1 if equal, 0 otherwise
387 */
388 inline int HashTable_key_equal(HashTable *table, void *key1, void *key2){
389 if(table->key_size){
390 return memcmp(key1, key2, table->key_size) == 0;
391 }
392 return (table->key_equal_fn ? table->key_equal_fn(key1, key2) : key1 == key2);
393 }
395 /** Compute the hashcode of a hashtable key.
396 * The table's key_hash_fn is used if defined, otherwise the address of
397 * the key is hashed.
398 *
399 * @param table hashtable
400 * @param key to hash
401 * @return hashcode
402 */
403 inline Hashcode HashTable_key_hash(HashTable *table, void *key){
404 if(table->key_size){
405 return _hash(key, table->key_size, 0);
406 }
407 return (table->key_hash_fn
408 ? table->key_hash_fn(key)
409 : hash_hvoid(0, &key, sizeof(key)));
410 }
412 /** Test if an entry has a given key.
413 *
414 * @param arg containing key to test for
415 * @param table the entry is in
416 * @param entry to test
417 * @return 1 if the entry has the key, 0 otherwise
418 */
419 static inline int has_key(TableArg arg, HashTable *table, HTEntry *entry){
420 return HashTable_key_equal(table, arg.ptr, entry->key);
421 }
423 /** Get an entry with a given key.
424 *
425 * @param table to search
426 * @param key to look for
427 * @return entry if found, null otherwise
428 */
429 inline HTEntry * HashTable_get_entry(HashTable *table, void *key){
430 Hashcode hashcode;
431 HTBucket *bucket;
432 HTEntry *entry = NULL;
433 HTEntry *next;
435 hashcode = HashTable_key_hash(table, key);
436 bucket = get_bucket(table, hashcode);
437 for(entry = bucket->head; entry; entry = next){
438 next = entry->next;
439 if(HashTable_key_equal(table, key, entry->key)){
440 break;
441 }
442 }
443 return entry;
444 }
446 /** Get the value of an entry with a given key.
447 *
448 * @param table to search
449 * @param key to look for
450 * @return value if an entry was found, null otherwise
451 */
452 inline void * HashTable_get(HashTable *table, void *key){
453 HTEntry *entry = HashTable_get_entry(table, key);
454 return (entry ? entry->value : 0);
455 }
457 /** Print the buckets in a table.
458 *
459 * @param table to print
460 */
461 void show_buckets(HashTable *table, IOStream *io){
462 int i,j ;
463 IOStream_print(io, "entry_count=%d buckets_n=%d\n", table->entry_count, table->buckets_n);
464 for(i=0; i < table->buckets_n; i++){
465 if(0 || table->buckets[i].count>0){
466 IOStream_print(io, "bucket %3d %3d %10p ", i,
467 table->buckets[i].count,
468 table->buckets[i].head);
469 for(j = table->buckets[i].count; j>0; j--){
470 IOStream_print(io, "+");
471 }
472 IOStream_print(io, "\n");
473 }
474 }
475 HashTable_print(table, io);
476 }
478 /** Print an entry in a table.
479 *
480 * @param entry to print
481 * @param arg a pointer to an IOStream to print to
482 * @return 0
483 */
484 static int print_entry(TableArg arg, HashTable *table, HTEntry *entry){
485 IOStream *io = (IOStream*)arg.ptr;
486 IOStream_print(io, " b=%4lx h=%08lx |-> e=%8p k=%8p v=%8p\n",
487 entry->hashcode % table->buckets_n,
488 entry->hashcode,
489 entry, entry->key, entry->value);
490 return 0;
491 }
493 /** Print a hash table.
494 *
495 * @param table to print
496 */
497 void HashTable_print(HashTable *table, IOStream *io){
498 IOStream_print(io, "{\n");
499 HashTable_map(table, print_entry, (TableArg){ ptr: io });
500 IOStream_print(io, "}\n");
501 }
502 /*==========================================================================*/
504 /** Add an entry to the bucket for the
505 * given hashcode.
506 *
507 * @param table to insert in
508 * @param hashcode indicates the bucket
509 * @param key to add an entry for
510 * @param value to add an entry for
511 * @return entry on success, 0 on failure
512 */
513 inline HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value){
514 HTEntry *entry = HTEntry_new(hashcode, key, value);
515 if(entry){
516 push_on_bucket(table, hashcode, entry);
517 table->entry_count++;
518 }
519 return entry;
520 }
522 /** Move the front entry for a bucket to the correct point in the bucket order as
523 * defined by the order function. If this is called every time a new entry is added
524 * the bucket will be maintained in sorted order.
525 *
526 * @param table to modify
527 * @param hashcode indicates the bucket
528 * @param order entry comparison function
529 * @return 0 if an entry was moved, 1 if not
530 */
531 int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order){
532 HTEntry *new_entry = NULL, *prev = NULL, *entry = NULL;
533 HTBucket *bucket;
534 int err = 1;
536 bucket = get_bucket(table, hashcode);
537 new_entry = bucket->head;
538 if(!new_entry || !new_entry->next) goto exit;
539 for(entry = new_entry->next; entry; prev = entry, entry = entry->next){
540 if(order(new_entry, entry) <= 0) break;
541 }
542 if(prev){
543 err = 0;
544 bucket->head = new_entry->next;
545 new_entry->next = entry;
546 prev->next = new_entry;
547 }
548 exit:
549 return err;
550 }
552 /** Add an entry to a hashtable.
553 * The entry is added to the bucket for its key's hashcode.
554 *
555 * @param table to insert in
556 * @param key to add an entry for
557 * @param value to add an entry for
558 * @return entry on success, 0 on failure
559 */
560 inline HTEntry * HashTable_add(HashTable *table, void *key, void *value){
561 return HashTable_add_entry(table, HashTable_key_hash(table, key), key, value);
562 }
564 /** Remove entries satisfying a test from the bucket for the
565 * given hashcode.
566 *
567 * @param table to remove from
568 * @param hashcode indicates the bucket
569 * @param test_fn test to apply to elements
570 * @param arg first argument to calls to test_fn
571 * @return number of entries removed
572 */
573 inline int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
574 TableTestFn *test_fn, TableArg arg){
575 HTBucket *bucket;
576 HTEntry *entry, *prev = NULL, *next;
577 int removed_count = 0;
579 bucket = get_bucket(table, hashcode);
580 for(entry = bucket->head; entry; entry = next){
581 next = entry->next;
582 if(test_fn(arg, table, entry)){
583 if(prev){
584 prev->next = next;
585 } else {
586 bucket->head = next;
587 }
588 bucket->count--;
589 table->entry_count--;
590 removed_count++;
591 HashTable_free_entry(table, entry);
592 entry = NULL;
593 }
594 prev = entry;
595 }
596 return removed_count;
597 }
599 /** Remove entries with a given key.
600 *
601 * @param table to remove from
602 * @param key of entries to remove
603 * @return number of entries removed
604 */
605 inline int HashTable_remove(HashTable *table, void *key){
606 Hashcode hashcode;
607 HTBucket *bucket;
608 HTEntry *entry, *prev = NULL, *next;
609 int removed_count = 0;
611 hashcode = HashTable_key_hash(table, key);
612 bucket = get_bucket(table, hashcode);
613 for(entry = bucket->head; entry; entry = next){
614 next = entry->next;
615 if(HashTable_key_equal(table, key, entry->key)){
616 if(prev){
617 prev->next = next;
618 } else {
619 bucket->head = next;
620 }
621 bucket->count--;
622 table->entry_count--;
623 removed_count++;
624 HashTable_free_entry(table, entry);
625 entry = NULL;
626 }
627 prev = entry;
628 }
629 return removed_count;
630 }
632 /** Remove (and free) all the entries in a bucket.
633 *
634 * @param bucket to clear
635 */
636 static inline void bucket_clear(HashTable *table, HTBucket *bucket){
637 HTEntry *entry, *next;
639 for(entry = bucket->head; entry; entry = next){
640 next = entry->next;
641 HashTable_free_entry(table, entry);
642 }
643 bucket->head = NULL;
644 table->entry_count -= bucket->count;
645 bucket->count = 0;
646 }
648 /** Remove (and free) all the entries in a table.
649 *
650 * @param table to clear
651 */
652 void HashTable_clear(HashTable *table){
653 int i, n = table->buckets_n;
655 for(i = 0; i < n; i++){
656 bucket_clear(table, table->buckets + i);
657 }
658 }