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*
hash_alloc(unsigned int buckets,unsigned int key_size,unsigned int value_size,hashfunc_t hash_func)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 = (unsigned int) 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*
hash_lookup_entry(struct hash * p_hash,void * p_key)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
hash_add_entry(struct hash * p_hash,void * p_key,void * p_value)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
hash_free_entry(struct hash * p_hash,void * p_key)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**
hash_get_bucket(struct hash * p_hash,void * p_key)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*
hash_get_node_by_key(struct hash * p_hash,void * p_key)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
148