hash.h

   1 #ifndef HASH_H
   2 #define HASH_H
   3
   4 /* Hash table implementation from the GIT project. */
   5 /* Copyright 2008 (C) Linus Torvalds, GPL version 2 */
   6 /*
   7  * These are some simple generic hash table helper functions.
   8  * Not necessarily suitable for all users, but good for things
   9  * where you want to just keep track of a list of things, and
  10  * have a good hash to use on them.
  11  *
  12  * It keeps the hash table at roughly 50-75% free, so the memory
  13  * cost of the hash table itself is roughly
  14  *
  15  *      3 * 2*sizeof(void *) * nr_of_objects
  16  *
  17  * bytes.
  18  *
  19  * FIXME: on 64-bit architectures, we waste memory. It would be
  20  * good to have just 32-bit pointers, requiring a special allocator
  21  * for hashed entries or something.
  22  */
  23
  24 #include <stdio.h>
  25
  26 #define alloc_nr(x) (((x) + 16) * 3 / 2)
  27 #define INSERT_HASH_PROTOS(ops, table)                                  \
  28         do {                                                            \
  29                 void **pos = insert_hash((ops).key, &(ops), &(table));  \
  30                 /* We already had an entry there? */                    \
  31                 if (pos) {                                              \
  32                         (ops).next = *pos;                              \
  33                         *pos = &(ops);                                  \
  34                 }                                                       \
  35         } while (0)
  36
  37 struct hash_table_entry {
  38         unsigned int hash;
  39         void *ptr;
  40 };
  41
  42 struct hash_table {
  43         unsigned int size, nr;
  44         struct hash_table_entry *array;
  45 };
  46
  47 extern void *lookup_hash(unsigned int hash, const struct hash_table *table);
  48 extern void **insert_hash(unsigned int hash, void *ptr,
  49                           struct hash_table *table);
  50 extern void *remove_hash(unsigned int hash, void *ptr, void *ptr_next,
  51                          struct hash_table *table);
  52 extern int for_each_hash(const struct hash_table *table, int (*fn)(void *));
  53 extern int for_each_hash_int(const struct hash_table *table,
  54                              int (*fn)(void *, int), int arg);
  55 extern void free_hash(struct hash_table *table);
  56
  57 static inline void init_hash(struct hash_table *table)
  58 {
  59         table->size = 0;
  60         table->nr = 0;
  61         table->array = NULL;
  62 }
  63
  64 static inline unsigned char icase_hash(unsigned char c)
  65 {
  66         return c & ~((c & 0x40) >> 1);
  67 }
  68
  69 static inline unsigned int hash_name(const char *name, int namelen)
  70 {
  71         unsigned int hash = 0x123;
  72         do {
  73                 unsigned char c = *name++;
  74                 c = icase_hash(c);
  75                 hash = hash * 101 + c;
  76         } while (--namelen);
  77         return hash;
  78 }
  79
  80 #endif /* HASH_H */