1 /*
2 * OpenVPN -- An application to securely tunnel IP networks
3 * over a single TCP/UDP port, with support for SSL/TLS-based
4 * session authentication and key exchange,
5 * packet encryption, packet authentication, and
6 * packet compression.
7 *
8 * Copyright (C) 2002-2018 OpenVPN Inc <sales@openvpn.net>
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License version 2
12 * as published by the Free Software Foundation.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 */
23
24 #ifndef LIST_H
25 #define LIST_H
26
27 /*
28 * This code is a fairly straightforward hash
29 * table implementation using Bob Jenkins'
30 * hash function.
31 *
32 * Hash tables are used in OpenVPN to keep track of
33 * client instances over various key spaces.
34 */
35
36 /* define this to enable special list test mode */
37 /*#define LIST_TEST*/
38
39 #include "basic.h"
40 #include "buffer.h"
41
42 #define hashsize(n) ((uint32_t)1<<(n))
43 #define hashmask(n) (hashsize(n)-1)
44
45 struct hash_element
46 {
47 void *value;
48 const void *key;
49 unsigned int hash_value;
50 struct hash_element *next;
51 };
52
53 struct hash_bucket
54 {
55 struct hash_element *list;
56 };
57
58 struct hash
59 {
60 int n_buckets;
61 int n_elements;
62 int mask;
63 uint32_t iv;
64 uint32_t (*hash_function)(const void *key, uint32_t iv);
65 bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
66 struct hash_bucket *buckets;
67 };
68
69 struct hash *hash_init(const int n_buckets,
70 const uint32_t iv,
71 uint32_t (*hash_function)(const void *key, uint32_t iv),
72 bool (*compare_function)(const void *key1, const void *key2));
73
74 void hash_free(struct hash *hash);
75
76 bool hash_add(struct hash *hash, const void *key, void *value, bool replace);
77
78 struct hash_element *hash_lookup_fast(struct hash *hash,
79 struct hash_bucket *bucket,
80 const void *key,
81 uint32_t hv);
82
83 bool hash_remove_fast(struct hash *hash,
84 struct hash_bucket *bucket,
85 const void *key,
86 uint32_t hv);
87
88 void hash_remove_by_value(struct hash *hash, void *value);
89
90 struct hash_iterator
91 {
92 struct hash *hash;
93 int bucket_index;
94 struct hash_bucket *bucket;
95 struct hash_element *elem;
96 struct hash_element *last;
97 bool bucket_marked;
98 int bucket_index_start;
99 int bucket_index_end;
100 };
101
102 void hash_iterator_init_range(struct hash *hash,
103 struct hash_iterator *hi,
104 int start_bucket,
105 int end_bucket);
106
107 void hash_iterator_init(struct hash *hash, struct hash_iterator *iter);
108
109 struct hash_element *hash_iterator_next(struct hash_iterator *hi);
110
111 void hash_iterator_delete_element(struct hash_iterator *hi);
112
113 void hash_iterator_free(struct hash_iterator *hi);
114
115 uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval);
116
117 #ifdef LIST_TEST
118 void list_test(void);
119
120 #endif
121
122 static inline uint32_t
hash_value(const struct hash * hash,const void * key)123 hash_value(const struct hash *hash, const void *key)
124 {
125 return (*hash->hash_function)(key, hash->iv);
126 }
127
128 static inline int
hash_n_elements(const struct hash * hash)129 hash_n_elements(const struct hash *hash)
130 {
131 return hash->n_elements;
132 }
133
134 static inline int
hash_n_buckets(const struct hash * hash)135 hash_n_buckets(const struct hash *hash)
136 {
137 return hash->n_buckets;
138 }
139
140 static inline struct hash_bucket *
hash_bucket(struct hash * hash,uint32_t hv)141 hash_bucket(struct hash *hash, uint32_t hv)
142 {
143 return &hash->buckets[hv & hash->mask];
144 }
145
146 static inline void *
hash_lookup(struct hash * hash,const void * key)147 hash_lookup(struct hash *hash, const void *key)
148 {
149 void *ret = NULL;
150 struct hash_element *he;
151 uint32_t hv = hash_value(hash, key);
152 struct hash_bucket *bucket = &hash->buckets[hv & hash->mask];
153
154 he = hash_lookup_fast(hash, bucket, key, hv);
155 if (he)
156 {
157 ret = he->value;
158 }
159
160 return ret;
161 }
162
163 /* NOTE: assumes that key is not a duplicate */
164 static inline void
hash_add_fast(struct hash * hash,struct hash_bucket * bucket,const void * key,uint32_t hv,void * value)165 hash_add_fast(struct hash *hash,
166 struct hash_bucket *bucket,
167 const void *key,
168 uint32_t hv,
169 void *value)
170 {
171 struct hash_element *he;
172
173 ALLOC_OBJ(he, struct hash_element);
174 he->value = value;
175 he->key = key;
176 he->hash_value = hv;
177 he->next = bucket->list;
178 bucket->list = he;
179 ++hash->n_elements;
180 }
181
182 static inline bool
hash_remove(struct hash * hash,const void * key)183 hash_remove(struct hash *hash, const void *key)
184 {
185 uint32_t hv;
186 struct hash_bucket *bucket;
187 bool ret;
188
189 hv = hash_value(hash, key);
190 bucket = &hash->buckets[hv & hash->mask];
191 ret = hash_remove_fast(hash, bucket, key, hv);
192 return ret;
193 }
194
195 #endif /* LIST */
196