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
14struct 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
22struct 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 */
32struct hash_node** hash_get_bucket(struct hash* p_hash, void* p_key);
33struct hash_node* hash_get_node_by_key(struct hash* p_hash, void* p_key);
34
35struct hash*
36hash_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
51void*
52hash_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
62void
63hash_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
92void
93hash_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
120struct hash_node**
121hash_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
131struct hash_node*
132hash_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
148