hash.h

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