release/src/router/vsftpd/hash.c

   1 /*
   2  * Part of Very Secure FTPd
   3  * Licence: GPL v2
   4  * Author: Chris Evans
   5  * hash.c
   6  *
   7  * Routines to handle simple hash table lookups and modifications.
   8  */
   9
  10 #include "hash.h"
  11 #include "sysutil.h"
  12 #include "utility.h"
  13
  14 struct hash_node
  15 {
  16   void* p_key;
  17   void* p_value;
  18   struct hash_node* p_prev;
  19   struct hash_node* p_next;
  20 };
  21
  22 struct hash
  23 {
  24   unsigned int buckets;
  25   unsigned int key_size;
  26   unsigned int value_size;
  27   hashfunc_t hash_func;
  28   struct hash_node** p_nodes;
  29 };
  30
  31 /* Internal functions */
  32 struct hash_node** hash_get_bucket(struct hash* p_hash, void* p_key);
  33 struct hash_node* hash_get_node_by_key(struct hash* p_hash, void* p_key);
  34
  35 struct hash*
  36 hash_alloc(unsigned int buckets, unsigned int key_size,
  37            unsigned int value_size, hashfunc_t hash_func)
  38 {
  39   unsigned int size;
  40   struct hash* p_hash = vsf_sysutil_malloc(sizeof(*p_hash));
  41   p_hash->buckets = buckets;
  42   p_hash->key_size = key_size;
  43   p_hash->value_size = value_size;
  44   p_hash->hash_func = hash_func;
  45   size = sizeof(struct hash_node*) * buckets;
  46   p_hash->p_nodes = vsf_sysutil_malloc(size);
  47   vsf_sysutil_memclr(p_hash->p_nodes, size);
  48   return p_hash;
  49 }
  50
  51 void*
  52 hash_lookup_entry(struct hash* p_hash, void* p_key)
  53 {
  54   struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key);
  55   if (!p_node)
  56   {
  57     return p_node;
  58   }
  59   return p_node->p_value;
  60 }
  61
  62 void
  63 hash_add_entry(struct hash* p_hash, void* p_key, void* p_value)
  64 {
  65   struct hash_node** p_bucket;
  66   struct hash_node* p_new_node;
  67   if (hash_lookup_entry(p_hash, p_key))
  68   {
  69     bug("duplicate hash key");
  70   }
  71   p_bucket = hash_get_bucket(p_hash, p_key);
  72   p_new_node = vsf_sysutil_malloc(sizeof(*p_new_node));
  73   p_new_node->p_prev = 0;
  74   p_new_node->p_next = 0;
  75   p_new_node->p_key = vsf_sysutil_malloc(p_hash->key_size);
  76   vsf_sysutil_memcpy(p_new_node->p_key, p_key, p_hash->key_size);
  77   p_new_node->p_value = vsf_sysutil_malloc(p_hash->value_size);
  78   vsf_sysutil_memcpy(p_new_node->p_value, p_value, p_hash->value_size);
  79
  80   if (!*p_bucket)
  81   {
  82     *p_bucket = p_new_node;
  83   }
  84   else
  85   {
  86     p_new_node->p_next = *p_bucket;
  87     (*p_bucket)->p_prev = p_new_node;
  88     *p_bucket = p_new_node;
  89   }
  90 }
  91
  92 void
  93 hash_free_entry(struct hash* p_hash, void* p_key)
  94 {
  95   struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key);
  96   if (!p_node)
  97   {
  98     bug("hash node not found");
  99   }
 100   vsf_sysutil_free(p_node->p_key);
 101   vsf_sysutil_free(p_node->p_value);
 102
 103   if (p_node->p_prev)
 104   {
 105     p_node->p_prev->p_next = p_node->p_next;
 106   }
 107   else
 108   {
 109     struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key);
 110     *p_bucket = p_node->p_next;
 111   }
 112   if (p_node->p_next)
 113   {
 114     p_node->p_next->p_prev = p_node->p_prev;
 115   }
 116
 117   vsf_sysutil_free(p_node);
 118 }
 119
 120 struct hash_node**
 121 hash_get_bucket(struct hash* p_hash, void* p_key)
 122 {
 123   unsigned int bucket = (*p_hash->hash_func)(p_hash->buckets, p_key);
 124   if (bucket >= p_hash->buckets)
 125   {
 126     bug("bad bucket lookup");
 127   }
 128   return &(p_hash->p_nodes[bucket]);
 129 }
 130
 131 struct hash_node*
 132 hash_get_node_by_key(struct hash* p_hash, void* p_key)
 133 {
 134   struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key);
 135   struct hash_node* p_node = *p_bucket;
 136   if (!p_node)
 137   {
 138     return p_node;
 139   }
 140   while (p_node != 0 &&
 141          vsf_sysutil_memcmp(p_key, p_node->p_key, p_hash->key_size) != 0)
 142   {
 143     p_node = p_node->p_next;
 144   }
 145   return p_node;
 146 }
 147