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-2023 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 
46 {
47  void *value;
48  const void *key;
49  unsigned int hash_value;
50  struct hash_element *next;
51 };
52 
54 {
55  struct hash_element *list;
56 };
57 
58 struct hash
59 {
60  int n_buckets;
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 */
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 
91 {
92  struct hash *hash;
95  struct hash_element *elem;
96  struct hash_element *last;
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 
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
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
129 hash_n_elements(const struct hash *hash)
130 {
131  return hash->n_elements;
132 }
133 
134 static inline int
135 hash_n_buckets(const struct hash *hash)
136 {
137  return hash->n_buckets;
138 }
139 
140 static inline struct hash_bucket *
141 hash_bucket(struct hash *hash, uint32_t hv)
142 {
143  return &hash->buckets[hv & hash->mask];
144 }
145 
146 static inline void *
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
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
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 */
hash::n_elements
int n_elements
Definition: list.h:61
hash_n_elements
static int hash_n_elements(const struct hash *hash)
Definition: list.h:129
hash_bucket
static struct hash_bucket * hash_bucket(struct hash *hash, uint32_t hv)
Definition: list.h:141
key2
#define key2
Definition: cert_data.h:82
hash_remove_by_value
void hash_remove_by_value(struct hash *hash, void *value)
Definition: list.c:175
hash_iterator
Definition: list.h:90
hash
Definition: list.h:58
hash_element::next
struct hash_element * next
Definition: list.h:50
key1
static const char *const key1
Definition: cert_data.h:56
hash_iterator::bucket_index_end
int bucket_index_end
Definition: list.h:99
hash_element::value
void * value
Definition: list.h:47
hash_remove
static bool hash_remove(struct hash *hash, const void *key)
Definition: list.h:183
hash_lookup
static void * hash_lookup(struct hash *hash, const void *key)
Definition: list.h:147
hash::buckets
struct hash_bucket * buckets
Definition: list.h:66
key
Container for unidirectional cipher and HMAC key material.
Definition: crypto.h:149
hash::hash_function
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition: list.h:64
hash_add_fast
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition: list.h:165
ALLOC_OBJ
#define ALLOC_OBJ(dptr, type)
Definition: buffer.h:1061
hash_add
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition: list.c:147
hash_element::key
const void * key
Definition: list.h:48
hash_bucket::list
struct hash_element * list
Definition: list.h:55
hash_free
void hash_free(struct hash *hash)
Definition: list.c:63
hash_iterator::elem
struct hash_element * elem
Definition: list.h:95
hash_remove_fast
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:114
hash_func
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition: list.c:587
hash::mask
int mask
Definition: list.h:62
hash_iterator_free
void hash_iterator_free(struct hash_iterator *hi)
Definition: list.c:283
hash_iterator::bucket_index
int bucket_index
Definition: list.h:93
hash_iterator_init
void hash_iterator_init(struct hash *hash, struct hash_iterator *iter)
Definition: list.c:246
buffer.h
hash_init
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:38
hash::iv
uint32_t iv
Definition: list.h:63
hash_lookup_fast
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition: list.c:83
hash_iterator::bucket
struct hash_bucket * bucket
Definition: list.h:94
basic.h
hash_iterator_init_range
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket)
Definition: list.c:223
hash_element
Definition: list.h:45
hash_bucket
Definition: list.h:53
hash_iterator::bucket_index_start
int bucket_index_start
Definition: list.h:98
hash_iterator::hash
struct hash * hash
Definition: list.h:92
hash_element::hash_value
unsigned int hash_value
Definition: list.h:49
key2
Container for bidirectional cipher and HMAC key material.
Definition: crypto.h:179
hash::n_buckets
int n_buckets
Definition: list.h:60
hash_iterator::bucket_marked
bool bucket_marked
Definition: list.h:97
hash_n_buckets
static int hash_n_buckets(const struct hash *hash)
Definition: list.h:135
hash::compare_function
bool(* compare_function)(const void *key1, const void *key2)
Definition: list.h:65
hash_iterator::last
struct hash_element * last
Definition: list.h:96
hash_iterator_next
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition: list.c:289
hash_value
static uint32_t hash_value(const struct hash *hash, const void *key)
Definition: list.h:123
hash_iterator_delete_element
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition: list.c:321