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
  25         while (array[nr].ptr) {
  26                 if (array[nr].hash == hash)
  27                         break;
  28                 nr++;
  29                 if (nr >= size)
  30                         nr = 0;
  31         }
  32
  33         return array + nr;
  34 }
  35
  36
  37 /*
  38  * Insert a new hash entry pointer into the table.
  39  *
  40  * If that hash entry already existed, return the pointer to
  41  * the existing entry (and the caller can create a list of the
  42  * pointers or do anything else). If it didn't exist, return
  43  * NULL (and the caller knows the pointer has been inserted).
  44  */
  45 static void **insert_hash_entry(unsigned int hash, void *ptr,
  46                                 struct hash_table *table)
  47 {
  48         struct hash_table_entry *entry = lookup_hash_entry(hash, table);
  49
  50         if (!entry->ptr) {
  51                 entry->ptr = ptr;
  52                 entry->hash = hash;
  53
  54                 table->nr++;
  55
  56                 return NULL;
  57         }
  58
  59         return &entry->ptr;
  60 }
  61
  62 /*
  63  * Removes a hash entry pointer from the table.
  64  *
  65  * If that hash does not exist, NULL is returned, or, if that hash
  66  * exists and is the first entry, ptr_next will be set to that entry
  67  * and NULL is returned. Otherwise the caller must maintain the
  68  * remaining list.
  69  */
  70 static void *remove_hash_entry(unsigned int hash, void *ptr, void *ptr_next,
  71                                struct hash_table *table)
  72 {
  73         struct hash_table_entry *entry = lookup_hash_entry(hash, table);
  74
  75         if (!entry->ptr)
  76                 return NULL;
  77
  78         else if (entry->ptr == ptr) {
  79                 entry->ptr = ptr_next;
  80                 entry->hash = hash;
  81
  82                 if (!ptr_next)
  83                         table->nr--;
  84
  85                 return NULL;
  86         } else
  87                 return entry->ptr;
  88 }
  89
  90 static void grow_hash_table(struct hash_table *table)
  91 {
  92         unsigned int i;
  93         unsigned int old_size = table->size, new_size;
  94         struct hash_table_entry *old_array = table->array, *new_array;
  95
  96         new_size = alloc_nr(old_size);
  97         new_array = xzmalloc(sizeof(struct hash_table_entry) * new_size);
  98
  99         table->size = new_size;
 100         table->array = new_array;
 101         table->nr = 0;
 102
 103         for (i = 0; i < old_size; i++) {
 104                 unsigned int hash = old_array[i].hash;
 105                 void *ptr = old_array[i].ptr;
 106
 107                 if (ptr)
 108                         insert_hash_entry(hash, ptr, table);
 109         }
 110
 111         free(old_array);
 112 }
 113
 114 void *lookup_hash(unsigned int hash, const struct hash_table *table)
 115 {
 116         if (!table->array)
 117                 return NULL;
 118
 119         return lookup_hash_entry(hash, table)->ptr;
 120 }
 121
 122 void *remove_hash(unsigned int hash, void *ptr, void *ptr_next,
 123                   struct hash_table *table)
 124 {
 125         if (!table->array)
 126                 return NULL;
 127
 128         return remove_hash_entry(hash, ptr, ptr_next, table);
 129 }
 130
 131 void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)
 132 {
 133         unsigned int nr = table->nr;
 134
 135         if (nr >= table->size/2)
 136                 grow_hash_table(table);
 137
 138         return insert_hash_entry(hash, ptr, table);
 139 }
 140
 141 int for_each_hash(const struct hash_table *table, int (*fn)(void *))
 142 {
 143         int sum = 0;
 144         unsigned int i;
 145         unsigned int size = table->size;
 146         struct hash_table_entry *array = table->array;
 147
 148         for (i = 0; i < size; i++) {
 149                 void *ptr = array->ptr;
 150
 151                 array++;
 152                 if (ptr) {
 153                         int val = fn(ptr);
 154                         if (val < 0)
 155                                 return val;
 156
 157                         sum += val;
 158                 }
 159         }
 160
 161         return sum;
 162 }
 163
 164 int for_each_hash_int(const struct hash_table *table, int (*fn)(void *, int),
 165                       int arg)
 166 {
 167         int sum = 0;
 168         unsigned int i;
 169         unsigned int size = table->size;
 170         struct hash_table_entry *array = table->array;
 171
 172         for (i = 0; i < size; i++) {
 173                 void *ptr = array->ptr;
 174
 175                 array++;
 176                 if (ptr) {
 177                         int val = fn(ptr, arg);
 178                         if (val < 0)
 179                                 return val;
 180
 181                         sum += val;
 182                 }
 183         }
 184
 185         return sum;
 186 }
 187
 188 void free_hash(struct hash_table *table)
 189 {
 190         free(table->array);
 191
 192         table->array = NULL;
 193         table->size = 0;
 194         table->nr = 0;
 195 }