hash.h

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