ia64/xen-unstable

view tools/vnet/libxutil/hash_table.c @ 6766:219d96d545fc

merge?
author cl349@firebug.cl.cam.ac.uk
date Mon Sep 12 20:00:41 2005 +0000 (2005-09-12)
parents 9f22db685802
children 71b0f00f6344
line source
1 /*
2 * Copyright (C) 2001 - 2004 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 <limits.h>
31 #include "allocate.h"
32 #include "hash_table.h"
34 /** @file
35 * Base support for hashtables.
36 *
37 * Hash codes are reduced modulo the number of buckets to index tables,
38 * so there is no need for hash functions to limit the range of hashcodes.
39 * In fact it is assumed that hashcodes do not change when the number of
40 * buckets in the table changes.
41 */
43 /*==========================================================================*/
44 /** Number of bits in half a word. */
45 //#if __WORDSIZE == 64
46 //#define HALF_WORD_BITS 32
47 //#else
48 #define HALF_WORD_BITS 16
49 //#endif
51 /** Mask for lo half of a word. On 32-bit this is
52 * (1<<16) - 1 = 65535 = 0xffff
53 * It's 4294967295 = 0xffffffff on 64-bit.
54 */
55 #define LO_HALF_MASK ((1 << HALF_WORD_BITS) - 1)
57 /** Get the lo half of a word. */
58 #define LO_HALF(x) ((x) & LO_HALF_MASK)
60 /** Get the hi half of a word. */
61 #define HI_HALF(x) ((x) >> HALF_WORD_BITS)
63 /** Do a full hash on both inputs, using DES-style non-linear scrambling.
64 * Both inputs are replaced with the results of the hash.
65 *
66 * @param pleft input/output word
67 * @param pright input/output word
68 */
69 void pseudo_des(unsigned long *pleft, unsigned long *pright){
70 // Bit-rich mixing constant.
71 static const unsigned long a_mixer[] = {
72 0xbaa96887L, 0x1e17d32cL, 0x03bcdc3cL, 0x0f33d1b2L, };
74 // Bit-rich mixing constant.
75 static const unsigned long b_mixer[] = {
76 0x4b0f3b58L, 0xe874f0c3L, 0x6955c5a6L, 0x55a7ca46L, };
78 // Number of iterations - must be 2 or 4.
79 static const int ncycle = 4;
80 //static const int ncycle = 2;
82 unsigned long left = *pleft, right = *pright;
83 unsigned long v, v_hi, v_lo;
84 int i;
86 for(i=0; i<ncycle; i++){
87 // Flip some bits in right to get v.
88 v = right;
89 v ^= a_mixer[i];
90 // Get lo and hi halves of v.
91 v_lo = LO_HALF(v);
92 v_hi = HI_HALF(v);
93 // Non-linear mix of the halves of v.
94 v = ((v_lo * v_lo) + ~(v_hi * v_hi));
95 // Swap the halves of v.
96 v = (HI_HALF(v) | (LO_HALF(v) << HALF_WORD_BITS));
97 // Flip some bits.
98 v ^= b_mixer[i];
99 // More non-linear mixing.
100 v += (v_lo * v_hi);
101 v ^= left;
102 left = right;
103 right = v;
104 }
105 *pleft = left;
106 *pright = right;
107 }
109 /** Hash a string.
110 *
111 * @param s input to hash
112 * @return hashcode
113 */
114 Hashcode hash_string(char *s){
115 Hashcode h = 0;
116 if(s){
117 for( ; *s; s++){
118 h = hash_2ul(h, *s);
119 }
120 }
121 return h;
122 }
124 /** Get the bucket for a hashcode in a hash table.
125 *
126 * @param table to get bucket from
127 * @param hashcode to get bucket for
128 * @return bucket
129 */
130 inline HTBucket * get_bucket(HashTable *table, Hashcode hashcode){
131 return table->buckets + (hashcode % table->buckets_n);
132 }
134 /** Initialize a hash table.
135 * Can be safely called more than once.
136 *
137 * @param table to initialize
138 */
139 void HashTable_init(HashTable *table){
140 int i;
142 if(!table->init_done){
143 table->init_done = 1;
144 table->next_id = 0;
145 for(i=0; i<table->buckets_n; i++){
146 HTBucket *bucket = get_bucket(table, i);
147 bucket->head = 0;
148 bucket->count = 0;
149 }
150 table->entry_count = 0;
151 }
152 }
154 /** Allocate a new hashtable.
155 * If the number of buckets is not positive the default is used.
156 * The number of buckets should usually be prime.
157 *
158 * @param buckets_n number of buckets
159 * @return new hashtable or null
160 */
161 HashTable *HashTable_new(int buckets_n){
162 HashTable *z = ALLOCATE(HashTable);
163 if(!z) goto exit;
164 if(buckets_n <= 0){
165 buckets_n = HT_BUCKETS_N;
166 }
167 z->buckets = (HTBucket*)allocate(buckets_n * sizeof(HTBucket));
168 if(!z->buckets){
169 deallocate(z);
170 z = 0;
171 goto exit;
172 }
173 z->buckets_n = buckets_n;
174 HashTable_init(z);
175 exit:
176 return z;
177 }
179 /** Free a hashtable.
180 * Any entries are removed and freed.
181 *
182 * @param h hashtable (ignored if null)
183 */
184 void HashTable_free(HashTable *h){
185 if(h){
186 HashTable_clear(h);
187 deallocate(h->buckets);
188 deallocate(h);
189 }
190 }
192 /** Push an entry on the list in the bucket for a given hashcode.
193 *
194 * @param table to add entry to
195 * @param hashcode for the entry
196 * @param entry to add
197 */
198 static inline void push_on_bucket(HashTable *table, Hashcode hashcode,
199 HTEntry *entry){
200 HTBucket *bucket;
201 HTEntry *old_head;
203 bucket = get_bucket(table, hashcode);
204 old_head = bucket->head;
205 bucket->count++;
206 bucket->head = entry;
207 entry->next = old_head;
208 }
210 /** Change the number of buckets in a hashtable.
211 * No-op if the number of buckets is not positive.
212 * Existing entries are reallocated to buckets based on their hashcodes.
213 * The table is unmodified if the number of buckets cannot be changed.
214 *
215 * @param table hashtable
216 * @param buckets_n new number of buckets
217 * @return 0 on success, error code otherwise
218 */
219 int HashTable_set_buckets_n(HashTable *table, int buckets_n){
220 int err = 0;
221 HTBucket *old_buckets = table->buckets;
222 int old_buckets_n = table->buckets_n;
223 int i;
225 if(buckets_n <= 0){
226 err = -EINVAL;
227 goto exit;
228 }
229 table->buckets = (HTBucket*)allocate(buckets_n * sizeof(HTBucket));
230 if(!table->buckets){
231 err = -ENOMEM;
232 table->buckets = old_buckets;
233 goto exit;
234 }
235 table->buckets_n = buckets_n;
236 for(i=0; i<old_buckets_n; i++){
237 HTBucket *bucket = old_buckets + i;
238 HTEntry *entry, *next;
239 for(entry = bucket->head; entry; entry = next){
240 next = entry->next;
241 push_on_bucket(table, entry->hashcode, entry);
242 }
243 }
244 deallocate(old_buckets);
245 exit:
246 return err;
247 }
249 /** Adjust the number of buckets so the table is neither too full nor too empty.
250 * The table is unmodified if adjusting fails.
251 *
252 * @param table hash table
253 * @param buckets_min minimum number of buckets (use default if 0 or negative)
254 * @return 0 on success, error code otherwise
255 */
256 int HashTable_adjust(HashTable *table, int buckets_min){
257 int buckets_n = 0;
258 int err = 0;
259 if(buckets_min <= 0) buckets_min = HT_BUCKETS_N;
260 if(table->entry_count >= table->buckets_n){
261 // The table is dense - expand it.
262 buckets_n = 2 * table->buckets_n;
263 } else if((table->buckets_n > buckets_min) &&
264 (4 * table->entry_count < table->buckets_n)){
265 // The table is more than minimum size and sparse - shrink it.
266 buckets_n = 2 * table->entry_count;
267 if(buckets_n < buckets_min) buckets_n = buckets_min;
268 }
269 if(buckets_n){
270 err = HashTable_set_buckets_n(table, buckets_n);
271 }
272 return err;
273 }
275 /** Allocate a new entry for a given value.
276 *
277 * @param value to put in the entry
278 * @return entry, or 0 on failure
279 */
280 HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value){
281 HTEntry *z = ALLOCATE(HTEntry);
282 if(z){
283 z->hashcode = hashcode;
284 z->key = key;
285 z->value = value;
286 }
287 return z;
288 }
290 /** Free an entry.
291 *
292 * @param z entry to free
293 */
294 inline void HTEntry_free(HTEntry *z){
295 if(z){
296 deallocate(z);
297 }
298 }
300 /** Free an entry in a hashtable.
301 * The table's entry_free_fn is used is defined, otherwise
302 * the HTEntry itself is freed.
303 *
304 * @param table hashtable
305 * @param entry to free
306 */
307 inline void HashTable_free_entry(HashTable *table, HTEntry *entry){
308 if(!entry)return;
309 if(table && table->entry_free_fn){
310 table->entry_free_fn(table, entry);
311 } else {
312 HTEntry_free(entry);
313 }
314 }
316 /** Get the first entry satisfying a test from the bucket for the
317 * given hashcode.
318 *
319 * @param table to look in
320 * @param hashcode indicates the bucket
321 * @param test_fn test to apply to elements
322 * @param arg first argument to calls to test_fn
323 * @return entry found, or 0
324 */
325 inline HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
326 TableTestFn *test_fn, TableArg arg){
327 HTBucket *bucket;
328 HTEntry *entry = 0;
329 HTEntry *next;
331 bucket = get_bucket(table, hashcode);
332 for(entry = bucket->head; entry; entry = next){
333 next = entry->next;
334 if(test_fn(arg, table, entry)){
335 break;
336 }
337 }
338 return entry;
339 }
341 /** Test hashtable keys for equality.
342 * Uses the table's key_equal_fn if defined, otherwise pointer equality.
343 *
344 * @param key1 key to compare
345 * @param key2 key to compare
346 * @return 1 if equal, 0 otherwise
347 */
348 inline int HashTable_key_equal(HashTable *table, void *key1, void *key2){
349 return (table->key_equal_fn ? table->key_equal_fn(key1, key2) : key1==key2);
350 }
352 /** Compute the hashcode of a hashtable key.
353 * The table's key_hash_fn is used if defined, otherwise the address of
354 * the key is hashed.
355 *
356 * @param table hashtable
357 * @param key to hash
358 * @return hashcode
359 */
360 inline Hashcode HashTable_key_hash(HashTable *table, void *key){
361 return (table->key_hash_fn ? table->key_hash_fn(key) : hash_ul((unsigned long)key));
362 }
364 /** Test if an entry has a given key.
365 *
366 * @param arg containing key to test for
367 * @param table the entry is in
368 * @param entry to test
369 * @return 1 if the entry has the key, 0 otherwise
370 */
371 static inline int has_key(TableArg arg, HashTable *table, HTEntry *entry){
372 return HashTable_key_equal(table, arg.ptr, entry->key);
373 }
375 /** Get an entry with a given key.
376 *
377 * @param table to search
378 * @param key to look for
379 * @return entry if found, null otherwise
380 */
381 #if 0
382 inline HTEntry * HashTable_get_entry(HashTable *table, void *key){
383 TableArg arg = { ptr: key };
384 return HashTable_find_entry(table, HashTable_key_hash(table, key), has_key, arg);
385 }
386 #else
387 inline HTEntry * HashTable_get_entry(HashTable *table, void *key){
388 Hashcode hashcode;
389 HTBucket *bucket;
390 HTEntry *entry = 0;
391 HTEntry *next;
393 hashcode = HashTable_key_hash(table, key);
394 bucket = get_bucket(table, hashcode);
395 for(entry = bucket->head; entry; entry = next){
396 next = entry->next;
397 if(HashTable_key_equal(table, key, entry->key)){
398 break;
399 }
400 }
401 return entry;
402 }
403 #endif
405 /** Get the value of an entry with a given key.
406 *
407 * @param table to search
408 * @param key to look for
409 * @return value if an entry was found, null otherwise
410 */
411 inline void * HashTable_get(HashTable *table, void *key){
412 HTEntry *entry = HashTable_get_entry(table, key);
413 return (entry ? entry->value : 0);
414 }
416 /** Print the buckets in a table.
417 *
418 * @param table to print
419 */
420 void show_buckets(HashTable *table, IOStream *io){
421 int i,j ;
422 IOStream_print(io, "entry_count=%d buckets_n=%d\n", table->entry_count, table->buckets_n);
423 for(i=0; i<table->buckets_n; i++){
424 if(0 || table->buckets[i].count>0){
425 IOStream_print(io, "bucket %3d %3d %10p ", i,
426 table->buckets[i].count,
427 table->buckets[i].head);
428 for(j = table->buckets[i].count; j>0; j--){
429 IOStream_print(io, "+");
430 }
431 IOStream_print(io, "\n");
432 }
433 }
434 HashTable_print(table, io);
435 }
437 /** Print an entry in a table.
438 *
439 * @param entry to print
440 * @param arg a pointer to an IOStream to print to
441 * @return 0
442 */
443 static int print_entry(TableArg arg, HashTable *table, HTEntry *entry){
444 IOStream *io = (IOStream*)arg.ptr;
445 IOStream_print(io, " b=%4lx h=%08lx i=%08lx |-> e=%8p k=%8p v=%8p\n",
446 entry->hashcode % table->buckets_n,
447 entry->hashcode,
448 entry->index,
449 entry, entry->key, entry->value);
450 return 0;
451 }
453 /** Print a hash table.
454 *
455 * @param table to print
456 */
457 void HashTable_print(HashTable *table, IOStream *io){
458 IOStream_print(io, "{\n");
459 HashTable_map(table, print_entry, (TableArg){ ptr: io });
460 IOStream_print(io, "}\n");
461 }
462 /*==========================================================================*/
464 /** Get the next entry id to use for a table.
465 *
466 * @param table hash table
467 * @return non-zero entry id
468 */
469 static inline unsigned long get_next_id(HashTable *table){
470 unsigned long id;
472 if(table->next_id == 0){
473 table->next_id = 1;
474 }
475 id = table->next_id++;
476 return id;
477 }
479 /** Add an entry to the bucket for the
480 * given hashcode.
481 *
482 * @param table to insert in
483 * @param hashcode indicates the bucket
484 * @param key to add an entry for
485 * @param value to add an entry for
486 * @return entry on success, 0 on failure
487 */
488 inline HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value){
489 HTEntry *entry = HTEntry_new(hashcode, key, value);
490 if(entry){
491 entry->index = get_next_id(table);
492 push_on_bucket(table, hashcode, entry);
493 table->entry_count++;
494 }
495 return entry;
496 }
498 /** Move the front entry for a bucket to the correct point in the bucket order as
499 * defined by the order function. If this is called every time a new entry is added
500 * the bucket will be maintained in sorted order.
501 *
502 * @param table to modify
503 * @param hashcode indicates the bucket
504 * @param order entry comparison function
505 * @return 0 if an entry was moved, 1 if not
506 */
507 int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order){
508 HTEntry *new_entry = NULL, *prev = NULL, *entry = NULL;
509 HTBucket *bucket;
510 int err = 1;
512 bucket = get_bucket(table, hashcode);
513 new_entry = bucket->head;
514 if(!new_entry || !new_entry->next) goto exit;
515 for(entry = new_entry->next; entry; prev = entry, entry = entry->next){
516 if(order(new_entry, entry) <= 0) break;
517 }
518 if(prev){
519 err = 0;
520 bucket->head = new_entry->next;
521 new_entry->next = entry;
522 prev->next = new_entry;
523 }
524 exit:
525 return err;
526 }
528 /** Add an entry to a hashtable.
529 * The entry is added to the bucket for its key's hashcode.
530 *
531 * @param table to insert in
532 * @param key to add an entry for
533 * @param value to add an entry for
534 * @return entry on success, 0 on failure
535 */
536 inline HTEntry * HashTable_add(HashTable *table, void *key, void *value){
537 return HashTable_add_entry(table, HashTable_key_hash(table, key), key, value);
538 }
541 /** Remove entries satisfying a test from the bucket for the
542 * given hashcode.
543 *
544 * @param table to remove from
545 * @param hashcode indicates the bucket
546 * @param test_fn test to apply to elements
547 * @param arg first argument to calls to test_fn
548 * @return number of entries removed
549 */
550 inline int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
551 TableTestFn *test_fn, TableArg arg){
552 HTBucket *bucket;
553 HTEntry *entry, *prev = 0, *next;
554 int removed_count = 0;
556 bucket = get_bucket(table, hashcode);
557 for(entry = bucket->head; entry; entry = next){
558 next = entry->next;
559 if(test_fn(arg, table, entry)){
560 if(prev){
561 prev->next = next;
562 } else {
563 bucket->head = next;
564 }
565 bucket->count--;
566 table->entry_count--;
567 removed_count++;
568 HashTable_free_entry(table, entry);
569 entry = 0;
570 }
571 prev = entry;
572 }
573 return removed_count;
574 }
576 /** Remove entries with a given key.
577 *
578 * @param table to remove from
579 * @param key of entries to remove
580 * @return number of entries removed
581 */
582 inline int HashTable_remove(HashTable *table, void *key){
583 #if 1
584 Hashcode hashcode;
585 HTBucket *bucket;
586 HTEntry *entry, *prev = 0, *next;
587 int removed_count = 0;
589 hashcode = HashTable_key_hash(table, key);
590 bucket = get_bucket(table, hashcode);
591 for(entry = bucket->head; entry; entry = next){
592 next = entry->next;
593 if(HashTable_key_equal(table, key, entry->key)){
594 if(prev){
595 prev->next = next;
596 } else {
597 bucket->head = next;
598 }
599 bucket->count--;
600 table->entry_count--;
601 removed_count++;
602 HashTable_free_entry(table, entry);
603 entry = 0;
604 }
605 prev = entry;
606 }
607 return removed_count;
608 #else
609 return HashTable_remove_entry(table, HashTable_key_hash(table, key),
610 has_key, (TableArg){ ptr: key});
611 #endif
612 }
614 /** Remove (and free) all the entries in a bucket.
615 *
616 * @param bucket to clear
617 */
618 static inline void bucket_clear(HashTable *table, HTBucket *bucket){
619 HTEntry *entry, *next;
621 for(entry = bucket->head; entry; entry = next){
622 next = entry->next;
623 HashTable_free_entry(table, entry);
624 }
625 bucket->head = 0;
626 table->entry_count -= bucket->count;
627 bucket->count = 0;
628 }
630 /** Remove (and free) all the entries in a table.
631 *
632 * @param table to clear
633 */
634 void HashTable_clear(HashTable *table){
635 int i, n = table->buckets_n;
637 for(i=0; i<n; i++){
638 bucket_clear(table, table->buckets + i);
639 }
640 }