src/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.
   6  */
   7
   8 #include "hash.h"
   9 #include "xmalloc.h"
  10
  11 /* Hash table implementation from the GIT project. */
  12 /* Copyright xxxx (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
  26         while (array[nr].ptr) {
  27                 if (array[nr].hash == hash)
  28                         break;
  29                 nr++;
  30                 if (nr >= size)
  31                         nr = 0;
  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                 table->nr++;
  54                 return NULL;
  55         }
  56
  57         return &entry->ptr;
  58 }
  59
  60 static void grow_hash_table(struct hash_table *table)
  61 {
  62         unsigned int i;
  63         unsigned int old_size = table->size, new_size;
  64         struct hash_table_entry *old_array = table->array, *new_array;
  65
  66         new_size = alloc_nr(old_size);
  67         new_array = xcalloc(sizeof(struct hash_table_entry), new_size);
  68         table->size = new_size;
  69         table->array = new_array;
  70         table->nr = 0;
  71
  72         for (i = 0; i < old_size; i++) {
  73                 unsigned int hash = old_array[i].hash;
  74                 void *ptr = old_array[i].ptr;
  75                 if (ptr)
  76                         insert_hash_entry(hash, ptr, table);
  77         }
  78
  79         if (old_array)
  80                 xfree(old_array);
  81 }
  82
  83 void *lookup_hash(unsigned int hash, const struct hash_table *table)
  84 {
  85         if (!table->array)
  86                 return NULL;
  87         return lookup_hash_entry(hash, table)->ptr;
  88 }
  89
  90 void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)
  91 {
  92         unsigned int nr = table->nr;
  93
  94         if (nr >= table->size/2)
  95                 grow_hash_table(table);
  96         return insert_hash_entry(hash, ptr, table);
  97 }
  98
  99 int for_each_hash(const struct hash_table *table, int (*fn)(void *))
 100 {
 101         int sum = 0;
 102         unsigned int i;
 103         unsigned int size = table->size;
 104         struct hash_table_entry *array = table->array;
 105
 106         for (i = 0; i < size; i++) {
 107                 void *ptr = array->ptr;
 108                 array++;
 109                 if (ptr) {
 110                         int val = fn(ptr);
 111                         if (val < 0)
 112                                 return val;
 113                         sum += val;
 114                 }
 115         }
 116
 117         return sum;
 118 }
 119
 120 void free_hash(struct hash_table *table)
 121 {
 122         if (table->array)
 123                 xfree(table->array);
 124         table->array = NULL;
 125         table->size = 0;
 126         table->nr = 0;
 127 }