1/*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License as
4 * published by the Free Software Foundation; either version 2 of
5 * the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
15 * MA 02111-1307 USA
16 */
17/*
18 * Part of Very Secure FTPd
19 * Licence: GPL v2
20 * Author: Chris Evans
21 * hash.c
22 *
23 * Routines to handle simple hash table lookups and modifications.
24 */
25
26#include "hash.h"
27#include "sysutil.h"
28#include "utility.h"
29
30struct hash_node
31{
32  void* p_key;
33  void* p_value;
34  struct hash_node* p_prev;
35  struct hash_node* p_next;
36};
37
38struct hash
39{
40  unsigned int buckets;
41  unsigned int key_size;
42  unsigned int value_size;
43  hashfunc_t hash_func;
44  struct hash_node** p_nodes;
45};
46
47/* Internal functions */
48struct hash_node** hash_get_bucket(struct hash* p_hash, void* p_key);
49struct hash_node* hash_get_node_by_key(struct hash* p_hash, void* p_key);
50
51struct hash*
52hash_alloc(unsigned int buckets, unsigned int key_size,
53           unsigned int value_size, hashfunc_t hash_func)
54{
55  unsigned int size;
56  struct hash* p_hash = vsf_sysutil_malloc(sizeof(*p_hash));
57  p_hash->buckets = buckets;
58  p_hash->key_size = key_size;
59  p_hash->value_size = value_size;
60  p_hash->hash_func = hash_func;
61  size = sizeof(struct hash_node*) * buckets;
62  p_hash->p_nodes = vsf_sysutil_malloc(size);
63  vsf_sysutil_memclr(p_hash->p_nodes, size);
64  return p_hash;
65}
66
67void*
68hash_lookup_entry(struct hash* p_hash, void* p_key)
69{
70  struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key);
71  if (!p_node)
72  {
73    return p_node;
74  }
75  return p_node->p_value;
76}
77
78void
79hash_add_entry(struct hash* p_hash, void* p_key, void* p_value)
80{
81  struct hash_node** p_bucket;
82  struct hash_node* p_new_node;
83  if (hash_lookup_entry(p_hash, p_key))
84  {
85    bug("duplicate hash key");
86  }
87  p_bucket = hash_get_bucket(p_hash, p_key);
88  p_new_node = vsf_sysutil_malloc(sizeof(*p_new_node));
89  p_new_node->p_prev = 0;
90  p_new_node->p_next = 0;
91  p_new_node->p_key = vsf_sysutil_malloc(p_hash->key_size);
92  vsf_sysutil_memcpy(p_new_node->p_key, p_key, p_hash->key_size);
93  p_new_node->p_value = vsf_sysutil_malloc(p_hash->value_size);
94  vsf_sysutil_memcpy(p_new_node->p_value, p_value, p_hash->value_size);
95
96  if (!*p_bucket)
97  {
98    *p_bucket = p_new_node;
99  }
100  else
101  {
102    p_new_node->p_next = *p_bucket;
103    (*p_bucket)->p_prev = p_new_node;
104    *p_bucket = p_new_node;
105  }
106}
107
108void
109hash_free_entry(struct hash* p_hash, void* p_key)
110{
111  struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key);
112  if (!p_node)
113  {
114    bug("hash node not found");
115  }
116  vsf_sysutil_free(p_node->p_key);
117  vsf_sysutil_free(p_node->p_value);
118
119  if (p_node->p_prev)
120  {
121    p_node->p_prev->p_next = p_node->p_next;
122  }
123  else
124  {
125    struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key);
126    *p_bucket = p_node->p_next;
127  }
128  if (p_node->p_next)
129  {
130    p_node->p_next->p_prev = p_node->p_prev;
131  }
132
133  vsf_sysutil_free(p_node);
134}
135
136struct hash_node**
137hash_get_bucket(struct hash* p_hash, void* p_key)
138{
139  unsigned int bucket = (*p_hash->hash_func)(p_hash->buckets, p_key);
140  if (bucket >= p_hash->buckets)
141  {
142    bug("bad bucket lookup");
143  }
144  return &(p_hash->p_nodes[bucket]);
145}
146
147struct hash_node*
148hash_get_node_by_key(struct hash* p_hash, void* p_key)
149{
150  struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key);
151  struct hash_node* p_node = *p_bucket;
152  if (!p_node)
153  {
154    return p_node;
155  }
156  while (p_node != 0 &&
157         vsf_sysutil_memcmp(p_key, p_node->p_key, p_hash->key_size) != 0)
158  {
159    p_node = p_node->p_next;
160  }
161  return p_node;
162}
163
164