hash.c

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