hash.h

   1 #ifndef HASH_H
   2 #define HASH_H
   3
   4 /*
   5  * These are some simple generic hash table helper functions.
   6  * Not necessarily suitable for all users, but good for things
   7  * where you want to just keep track of a list of things, and
   8  * have a good hash to use on them.
   9  *
  10  * It keeps the hash table at roughly 50-75% free, so the memory
  11  * cost of the hash table itself is roughly
  12  *
  13  *      3 * 2*sizeof(void *) * nr_of_objects
  14  *
  15  * bytes.
  16  *
  17  * FIXME: on 64-bit architectures, we waste memory. It would be
  18  * good to have just 32-bit pointers, requiring a special allocator
  19  * for hashed entries or something.
  20  */
  21 struct hash_table_entry {
  22         unsigned int hash;
  23         void *ptr;
  24 };
  25
  26 struct hash_table {
  27         unsigned int size, nr;
  28         struct hash_table_entry *array;
  29 };
  30
  31 extern void *lookup_hash(unsigned int hash, const struct hash_table *table);
  32 extern void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table);
  33 extern int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data);
  34 extern void free_hash(struct hash_table *table);
  35
  36 static inline void init_hash(struct hash_table *table)
  37 {
  38         table->size = 0;
  39         table->nr = 0;
  40         table->array = NULL;
  41 }
  42
  43 static inline void preallocate_hash(struct hash_table *table, unsigned int elts)
  44 {
  45         assert(table->size == 0 && table->nr == 0 && table->array == NULL);
  46         table->size = elts * 2;
  47         table->array = xcalloc(sizeof(struct hash_table_entry), table->size);
  48 }
  49
  50 #endif