hash.c

   1 /*
   2  * netsniff-ng - the packet sniffing beast
   3  * Copyright 2009, 2010 Daniel Borkmann.
   4  * Subject to the GPL, version 2.
   5  */
   6
   7 #include "hash.h"
   8 #include "xmalloc.h"
   9
  10 /* Hash table implementation from the GIT project. */
  11 /* Copyright 2008 (C) Linus Torvalds, GPL version 2 */
  12
  13 /*
  14  * Look up a hash entry in the hash table. Return the pointer to
  15  * the existing entry, or the empty slot if none existed. The caller
  16  * can then look at the (*ptr) to see whether it existed or not.
  17  */
  18 static struct hash_table_entry *lookup_hash_entry(unsigned int hash,
  19                                                   const struct hash_table
  20                                                                    *table)
  21 {
  22         unsigned int size = table->size, nr = hash % size;
  23         struct hash_table_entry *array = table->array;
  24         while (array[nr].ptr) {
  25                 if (array[nr].hash == hash)
  26                         break;
  27                 nr++;
  28                 if (nr >= size)
  29                         nr = 0;
  30         }
  31         return array + nr;
  32 }
  33
  34
  35 /*
  36  * Insert a new hash entry pointer into the table.
  37  *
  38  * If that hash entry already existed, return the pointer to
  39  * the existing entry (and the caller can create a list of the
  40  * pointers or do anything else). If it didn't exist, return
  41  * NULL (and the caller knows the pointer has been inserted).
  42  */
  43 static void **insert_hash_entry(unsigned int hash, void *ptr,
  44                                 struct hash_table *table)
  45 {
  46         struct hash_table_entry *entry = lookup_hash_entry(hash, table);
  47         if (!entry->ptr) {
  48                 entry->ptr = ptr;
  49                 entry->hash = hash;
  50                 table->nr++;
  51                 return NULL;
  52         }
  53         return &entry->ptr;
  54 }
  55
  56 /*
  57  * Removes a hash entry pointer from the table.
  58  *
  59  * If that hash does not exist, NULL is returned, or, if that hash
  60  * exists and is the first entry, ptr_next will be set to that entry
  61  * and NULL is returned. Otherwise the caller must maintain the
  62  * remaining list.
  63  */
  64 static void *remove_hash_entry(unsigned int hash, void *ptr, void *ptr_next,
  65                                struct hash_table *table)
  66 {
  67         struct hash_table_entry *entry = lookup_hash_entry(hash, table);
  68         if (!entry->ptr)
  69                 return NULL;
  70         else if (entry->ptr == ptr) {
  71                 entry->ptr = ptr_next;
  72                 entry->hash = hash;
  73                 if (!ptr_next)
  74                         table->nr--;
  75                 return NULL;
  76         } else
  77                 return entry->ptr;
  78 }
  79
  80 static void grow_hash_table(struct hash_table *table)
  81 {
  82         unsigned int i;
  83         unsigned int old_size = table->size, new_size;
  84         struct hash_table_entry *old_array = table->array, *new_array;
  85         new_size = alloc_nr(old_size);
  86         new_array = xzmalloc(sizeof(struct hash_table_entry) * new_size);
  87         table->size = new_size;
  88         table->array = new_array;
  89         table->nr = 0;
  90         for (i = 0; i < old_size; i++) {
  91                 unsigned int hash = old_array[i].hash;
  92                 void *ptr = old_array[i].ptr;
  93                 if (ptr)
  94                         insert_hash_entry(hash, ptr, table);
  95         }
  96         if (old_array)
  97                 xfree(old_array);
  98 }
  99
 100 void *lookup_hash(unsigned int hash, const struct hash_table *table)
 101 {
 102         if (!table->array)
 103                 return NULL;
 104         return lookup_hash_entry(hash, table)->ptr;
 105 }
 106
 107 void *remove_hash(unsigned int hash, void *ptr, void *ptr_next,
 108                   struct hash_table *table)
 109 {
 110         if (!table->array)
 111                 return NULL;
 112         return remove_hash_entry(hash, ptr, ptr_next, table);
 113 }
 114
 115 void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)
 116 {
 117         unsigned int nr = table->nr;
 118         if (nr >= table->size/2)
 119                 grow_hash_table(table);
 120         return insert_hash_entry(hash, ptr, table);
 121 }
 122
 123 int for_each_hash(const struct hash_table *table, int (*fn)(void *))
 124 {
 125         int sum = 0;
 126         unsigned int i;
 127         unsigned int size = table->size;
 128         struct hash_table_entry *array = table->array;
 129         for (i = 0; i < size; i++) {
 130                 void *ptr = array->ptr;
 131                 array++;
 132                 if (ptr) {
 133                         int val = fn(ptr);
 134                         if (val < 0)
 135                                 return val;
 136                         sum += val;
 137                 }
 138         }
 139         return sum;
 140 }
 141
 142 int for_each_hash_int(const struct hash_table *table, int (*fn)(void *, int),
 143                       int arg)
 144 {
 145         int sum = 0;
 146         unsigned int i;
 147         unsigned int size = table->size;
 148         struct hash_table_entry *array = table->array;
 149         for (i = 0; i < size; i++) {
 150                 void *ptr = array->ptr;
 151                 array++;
 152                 if (ptr) {
 153                         int val = fn(ptr, arg);
 154                         if (val < 0)
 155                                 return val;
 156                         sum += val;
 157                 }
 158         }
 159         return sum;
 160 }
 161
 162 void free_hash(struct hash_table *table)
 163 {
 164         if (table->array)
 165                 xfree(table->array);
 166         table->array = NULL;
 167         table->size = 0;
 168         table->nr = 0;
 169 }