← Back to branch summary

~ubuntu-branches/ubuntu/utopic/xen/utopic

« back to all changes in this revision

Viewing changes to tools/vnet/libxutil/hash_table.c

  • Committer: Bazaar Package Importer
  • Author(s): Bastian Blank
  • Date: 2010-05-06 15:47:38 UTC
  • mto: (1.3.1) (15.1.1 sid) (4.1.1 experimental)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20100506154738-agoz0rlafrh1fnq7
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/vnet/libxutil/hash_table.c
 
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
 */
 
18
 
 
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
 
28
 
 
29
#include "allocate.h"
 
30
#include "hash_table.h"
 
31
 
 
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
 */
 
40
 
 
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
*/
 
48
 
 
49
#define hashsize(n) ((ub4)1<<(n))
 
50
#define hashmask(n) (hashsize(n)-1)
 
51
 
 
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
}
 
90
 
 
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.
 
100
 
 
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.
 
106
 
 
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);
 
109
 
 
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.
 
112
 
 
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
*/
 
118
 
 
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;
 
125
 
 
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 */
 
130
 
 
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
   }
 
140
 
 
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
}
 
163
 
 
164
ub4 hash(const ub1 *k, ub4 length, ub4 initval){
 
165
    return _hash(k, length, initval);
 
166
}
 
167
 
 
168
/*============================================================================*/
 
169
 
 
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
}
 
179
 
 
180
/** Initialize a hash table.
 
181
 *
 
182
 * @param table to initialize
 
183
 */
 
184
static void HashTable_init(HashTable *table){
 
185
    int i;
 
186
 
 
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
}
 
194
 
 
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
}
 
218
 
 
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
}
 
231
 
 
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;
 
242
 
 
243
    bucket = get_bucket(table, hashcode);
 
244
    old_head = bucket->head;
 
245
    bucket->count++;
 
246
    bucket->head = entry;
 
247
    entry->next = old_head;
 
248
}
 
249
 
 
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;
 
264
 
 
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
}
 
288
 
 
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
}
 
314
 
 
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
}
 
329
 
 
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
}
 
339
 
 
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
}
 
355
 
 
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;
 
370
 
 
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
}
 
380
 
 
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
}
 
394
 
 
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
}
 
411
 
 
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
}
 
422
 
 
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;
 
434
 
 
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
}
 
445
 
 
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
}
 
456
 
 
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
}
 
477
    
 
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
}
 
492
 
 
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
/*==========================================================================*/
 
503
 
 
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
}
 
521
 
 
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;
 
535
 
 
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
}
 
551
 
 
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
}
 
563
 
 
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;
 
578
 
 
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
}
 
598
 
 
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;
 
610
 
 
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
}
 
631
 
 
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;
 
638
 
 
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
}
 
647
 
 
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;
 
654
 
 
655
    for(i = 0; i < n; i++){
 
656
        bucket_clear(table, table->buckets + i);
 
657
    }
 
658
}