Andrew's git - gitweb.git/blob

   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 */
  12static 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 */
  36static 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
  49static 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
  69void *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
  76void **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
  84int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data)
  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, data);
  96                        if (val < 0)
  97                                return val;
  98                        sum += val;
  99                }
 100        }
 101        return sum;
 102}
 103
 104void free_hash(struct hash_table *table)
 105{
 106        free(table->array);
 107        table->array = NULL;
 108        table->size = 0;
 109        table->nr = 0;
 110}