OpenVPN
list.h
Go to the documentation of this file.
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 #if P2MP_SERVER
37 
38 /* define this to enable special list test mode */
39 /*#define LIST_TEST*/
40 
41 #include "basic.h"
42 #include "buffer.h"
43 
44 #define hashsize(n) ((uint32_t)1<<(n))
45 #define hashmask(n) (hashsize(n)-1)
46 
48 {
49  void *value;
50  const void *key;
51  unsigned int hash_value;
52  struct hash_element *next;
53 };
54 
56 {
57  struct hash_element *list;
58 };
59 
60 struct hash
61 {
62  int n_buckets;
64  int mask;
66  uint32_t (*hash_function)(const void *key, uint32_t iv);
67  bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
69 };
70 
71 struct hash *hash_init(const int n_buckets,
72  const uint32_t iv,
73  uint32_t (*hash_function)(const void *key, uint32_t iv),
74  bool (*compare_function)(const void *key1, const void *key2));
75 
76 void hash_free(struct hash *hash);
77 
78 bool hash_add(struct hash *hash, const void *key, void *value, bool replace);
79 
80 struct hash_element *hash_lookup_fast(struct hash *hash,
81  struct hash_bucket *bucket,
82  const void *key,
83  uint32_t hv);
84 
85 bool hash_remove_fast(struct hash *hash,
86  struct hash_bucket *bucket,
87  const void *key,
88  uint32_t hv);
89 
90 void hash_remove_by_value(struct hash *hash, void *value);
91 
93 {
94  struct hash *hash;
97  struct hash_element *elem;
98  struct hash_element *last;
102 };
103 
104 void hash_iterator_init_range(struct hash *hash,
105  struct hash_iterator *hi,
106  int start_bucket,
107  int end_bucket);
108 
109 void hash_iterator_init(struct hash *hash, struct hash_iterator *iter);
110 
111 struct hash_element *hash_iterator_next(struct hash_iterator *hi);
112 
114 
115 void hash_iterator_free(struct hash_iterator *hi);
116 
117 uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval);
118 
119 #ifdef LIST_TEST
120 void list_test(void);
121 
122 #endif
123 
124 static inline uint32_t
125 hash_value(const struct hash *hash, const void *key)
126 {
127  return (*hash->hash_function)(key, hash->iv);
128 }
129 
130 static inline int
131 hash_n_elements(const struct hash *hash)
132 {
133  return hash->n_elements;
134 }
135 
136 static inline int
137 hash_n_buckets(const struct hash *hash)
138 {
139  return hash->n_buckets;
140 }
141 
142 static inline struct hash_bucket *
144 {
145  return &hash->buckets[hv & hash->mask];
146 }
147 
148 static inline void *
149 hash_lookup(struct hash *hash, const void *key)
150 {
151  void *ret = NULL;
152  struct hash_element *he;
153  uint32_t hv = hash_value(hash, key);
154  struct hash_bucket *bucket = &hash->buckets[hv & hash->mask];
155 
156  he = hash_lookup_fast(hash, bucket, key, hv);
157  if (he)
158  {
159  ret = he->value;
160  }
161 
162  return ret;
163 }
164 
165 /* NOTE: assumes that key is not a duplicate */
166 static inline void
168  struct hash_bucket *bucket,
169  const void *key,
170  uint32_t hv,
171  void *value)
172 {
173  struct hash_element *he;
174 
175  ALLOC_OBJ(he, struct hash_element);
176  he->value = value;
177  he->key = key;
178  he->hash_value = hv;
179  he->next = bucket->list;
180  bucket->list = he;
181  ++hash->n_elements;
182 }
183 
184 static inline bool
185 hash_remove(struct hash *hash, const void *key)
186 {
187  uint32_t hv;
188  struct hash_bucket *bucket;
189  bool ret;
190 
191  hv = hash_value(hash, key);
192  bucket = &hash->buckets[hv & hash->mask];
193  ret = hash_remove_fast(hash, bucket, key, hv);
194  return ret;
195 }
196 
197 #endif /* P2MP_SERVER */
198 #endif /* LIST */
#define ALLOC_OBJ(dptr, type)
Definition: buffer.h:1045
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition: list.h:167
struct hash_element * next
Definition: list.h:52
int n_elements
Definition: list.h:63
const void * key
Definition: list.h:50
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition: list.c:292
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:117
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition: list.c:324
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: list.c:590
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition: list.h:66
struct hash_bucket * bucket
Definition: list.h:96
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket)
Definition: list.c:226
struct hash_element * list
Definition: list.h:57
struct hash_bucket * buckets
Definition: list.h:68
int bucket_index_start
Definition: list.h:100
unsigned __int32 uint32_t
Definition: config-msvc.h:121
static void * hash_lookup(struct hash *hash, const void *key)
Definition: list.h:149
uint32_t iv
Definition: list.h:65
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition: list.c:150
int mask
Definition: list.h:64
static int hash_n_buckets(const struct hash *hash)
Definition: list.h:137
int bucket_index
Definition: list.h:95
Container for bidirectional cipher and HMAC key material.
Definition: crypto.h:181
static struct hash_bucket * hash_bucket(struct hash *hash, uint32_t hv)
Definition: list.h:143
void hash_remove_by_value(struct hash *hash, void *value)
Definition: list.c:178
unsigned __int8 uint8_t
Definition: config-msvc.h:123
int n_buckets
Definition: list.h:62
struct hash_element * last
Definition: list.h:98
int bucket_index_end
Definition: list.h:101
bool(* compare_function)(const void *key1, const void *key2)
Definition: list.h:67
static int hash_n_elements(const struct hash *hash)
Definition: list.h:131
static bool hash_remove(struct hash *hash, const void *key)
Definition: list.h:185
bool bucket_marked
Definition: list.h:99
#define bool
Definition: simple.c:61
void * value
Definition: list.h:49
void hash_free(struct hash *hash)
Definition: list.c:66
void hash_iterator_init(struct hash *hash, struct hash_iterator *iter)
Definition: list.c:249
struct hash * hash_init(const int n_buckets, const uint32_t iv, uint32_t(*hash_function)(const void *key, uint32_t iv), bool(*compare_function)(const void *key1, const void *key2))
Definition: list.c:41
Definition: list.h:60
struct hash_element * elem
Definition: list.h:97
void hash_iterator_free(struct hash_iterator *hi)
Definition: list.c:286
Container for unidirectional cipher and HMAC key material.
Definition: crypto.h:151
struct hash * hash
Definition: list.h:94
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:86
unsigned int hash_value
Definition: list.h:51