hash.c

   1 /*
   2  * Some generic hashing helpers.
   3  */
   4 #include "cache.h"
   5 #include "hash.h"
   6
   7 /*
   8  * Look up a hash entry in the hash table. Return the pointer to
   9  * the existing entry, or the empty slot if none existed. The caller
  10  * can then look at the (*ptr) to see whether it existed or not.
  11  */
  12 static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table)
  13 {
  14         unsigned int size = table->size, nr = hash % size;
  15         struct hash_table_entry *array = table->array;
  16
  17         while (array[nr].ptr) {
  18                 if (array[nr].hash == hash)
  19                         break;
  20                 nr++;
  21                 if (nr >= size)
  22                         nr = 0;
  23         }
  24         return array + nr;
  25 }
  26
  27
  28 /*
  29  * Insert a new hash entry pointer into the table.
  30  *
  31  * If that hash entry already existed, return the pointer to
  32  * the existing entry (and the caller can create a list of the
  33  * pointers or do anything else). If it didn't exist, return
  34  * NULL (and the caller knows the pointer has been inserted).
  35  */
  36 static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table)
  37 {
  38         struct hash_table_entry *entry = lookup_hash_entry(hash, table);
  39
  40         if (!entry->ptr) {
  41                 entry->ptr = ptr;
  42                 entry->hash = hash;
  43                 table->nr++;
  44                 return NULL;
  45         }
  46         return &entry->ptr;
  47 }
  48
  49 static void grow_hash_table(struct hash_table *table)
  50 {
  51         unsigned int i;
  52         unsigned int old_size = table->size, new_size;
  53         struct hash_table_entry *old_array = table->array, *new_array;
  54
  55         new_size = alloc_nr(old_size);
  56         new_array = xcalloc(sizeof(struct hash_table_entry), new_size);
  57         table->size = new_size;
  58         table->array = new_array;
  59         table->nr = 0;
  60         for (i = 0; i < old_size; i++) {
  61                 unsigned int hash = old_array[i].hash;
  62                 void *ptr = old_array[i].ptr;
  63                 if (ptr)
  64                         insert_hash_entry(hash, ptr, table);
  65         }
  66         free(old_array);
  67 }
  68
  69 void *lookup_hash(unsigned int hash, const struct hash_table *table)
  70 {
  71         if (!table->array)
  72                 return NULL;
  73         return lookup_hash_entry(hash, table)->ptr;
  74 }
  75
  76 void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)
  77 {
  78         unsigned int nr = table->nr;
  79         if (nr >= table->size/2)
  80                 grow_hash_table(table);
  81         return insert_hash_entry(hash, ptr, table);
  82 }
  83
  84 int for_each_hash(const struct hash_table *table, int (*fn)(void *))
  85 {
  86         int sum = 0;
  87         unsigned int i;
  88         unsigned int size = table->size;
  89         struct hash_table_entry *array = table->array;
  90
  91         for (i = 0; i < size; i++) {
  92                 void *ptr = array->ptr;
  93                 array++;
  94                 if (ptr) {
  95                         int val = fn(ptr);
  96                         if (val < 0)
  97                                 return val;
  98                         sum += val;
  99                 }
 100         }
 101         return sum;
 102 }
 103
 104 void free_hash(struct hash_table *table)
 105 {
 106         free(table->array);
 107         table->array = NULL;
 108         table->size = 0;
 109         table->nr = 0;
 110 }