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-2025 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, see <https://www.gnu.org/licenses/>.
21 */
22
23#ifndef LIST_H
24#define LIST_H
25
26/*
27 * This code is a fairly straightforward hash
28 * table implementation using Bob Jenkins'
29 * hash function.
30 *
31 * Hash tables are used in OpenVPN to keep track of
32 * client instances over various key spaces.
33 */
34
35
36#include "basic.h"
37#include "buffer.h"
38
39#define hashsize(n) ((uint32_t)1 << (n))
40#define hashmask(n) (hashsize(n) - 1)
41
43{
44 void *value;
45 const void *key;
46 unsigned int hash_value;
48};
49
51{
53};
54
55struct hash
56{
59 int mask;
60 uint32_t iv;
61 uint32_t (*hash_function)(const void *key, uint32_t iv);
62 bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
64};
65
66struct hash *hash_init(const int n_buckets, const uint32_t iv,
67 uint32_t (*hash_function)(const void *key, uint32_t iv),
68 bool (*compare_function)(const void *key1, const void *key2));
69
70void hash_free(struct hash *hash);
71
72bool hash_add(struct hash *hash, const void *key, void *value, bool replace);
73
74struct hash_element *hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket,
75 const void *key, uint32_t hv);
76
77bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv);
78
79void hash_remove_by_value(struct hash *hash, void *value);
80
92
93void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket,
94 int end_bucket);
95
96void hash_iterator_init(struct hash *hash, struct hash_iterator *iter);
97
99
101
102void hash_iterator_free(struct hash_iterator *hi);
103
104uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval);
105
106static inline uint32_t
107hash_value(const struct hash *hash, const void *key)
108{
109 return (*hash->hash_function)(key, hash->iv);
110}
111
112static inline int
114{
115 return hash->n_elements;
116}
117
118static inline int
120{
121 return hash->n_buckets;
122}
123
124static inline struct hash_bucket *
125hash_bucket(struct hash *hash, uint32_t hv)
126{
127 return &hash->buckets[hv & hash->mask];
128}
129
130static inline void *
131hash_lookup(struct hash *hash, const void *key)
132{
133 void *ret = NULL;
134 struct hash_element *he;
135 uint32_t hv = hash_value(hash, key);
136 struct hash_bucket *bucket = &hash->buckets[hv & hash->mask];
137
138 he = hash_lookup_fast(hash, bucket, key, hv);
139 if (he)
140 {
141 ret = he->value;
142 }
143
144 return ret;
145}
146
147/* NOTE: assumes that key is not a duplicate */
148static inline void
149hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv,
150 void *value)
151{
152 struct hash_element *he;
153
154 ALLOC_OBJ(he, struct hash_element);
155 he->value = value;
156 he->key = key;
157 he->hash_value = hv;
158 he->next = bucket->list;
159 bucket->list = he;
160 ++hash->n_elements;
161}
162
163static inline bool
164hash_remove(struct hash *hash, const void *key)
165{
166 uint32_t hv;
167 struct hash_bucket *bucket;
168 bool ret;
169
170 hv = hash_value(hash, key);
171 bucket = &hash->buckets[hv & hash->mask];
172 ret = hash_remove_fast(hash, bucket, key, hv);
173 return ret;
174}
175
176#endif /* LIST */
#define ALLOC_OBJ(dptr, type)
Definition buffer.h:1037
#define key2
Definition cert_data.h:80
static const char *const key1
Definition cert_data.h:55
static bool hash_remove(struct hash *hash, const void *key)
Definition list.h:164
void hash_iterator_init(struct hash *hash, struct hash_iterator *iter)
Definition list.c:236
void hash_iterator_free(struct hash_iterator *hi)
Definition list.c:272
struct hash_element * hash_iterator_next(struct hash_iterator *hi)
Definition list.c:278
static void * hash_lookup(struct hash *hash, const void *key)
Definition list.h:131
static int hash_n_elements(const struct hash *hash)
Definition list.h:113
void hash_iterator_delete_element(struct hash_iterator *hi)
Definition list.c:310
struct hash_element * hash_lookup_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition list.c:81
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:37
void hash_iterator_init_range(struct hash *hash, struct hash_iterator *hi, int start_bucket, int end_bucket)
Definition list.c:215
static uint32_t hash_value(const struct hash *hash, const void *key)
Definition list.h:107
static int hash_n_buckets(const struct hash *hash)
Definition list.h:119
bool hash_remove_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv)
Definition list.c:109
uint32_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval)
Definition list.c:415
void hash_free(struct hash *hash)
Definition list.c:61
bool hash_add(struct hash *hash, const void *key, void *value, bool replace)
Definition list.c:139
void hash_remove_by_value(struct hash *hash, void *value)
Definition list.c:167
static void hash_add_fast(struct hash *hash, struct hash_bucket *bucket, const void *key, uint32_t hv, void *value)
Definition list.h:149
struct hash_element * list
Definition list.h:52
void * value
Definition list.h:44
const void * key
Definition list.h:45
struct hash_element * next
Definition list.h:47
unsigned int hash_value
Definition list.h:46
bool bucket_marked
Definition list.h:88
int bucket_index_end
Definition list.h:90
struct hash_bucket * bucket
Definition list.h:85
struct hash * hash
Definition list.h:83
int bucket_index_start
Definition list.h:89
struct hash_element * elem
Definition list.h:86
int bucket_index
Definition list.h:84
struct hash_element * last
Definition list.h:87
Definition list.h:56
uint32_t(* hash_function)(const void *key, uint32_t iv)
Definition list.h:61
struct hash_bucket * buckets
Definition list.h:63
int n_buckets
Definition list.h:57
int mask
Definition list.h:59
uint32_t iv
Definition list.h:60
bool(* compare_function)(const void *key1, const void *key2)
Definition list.h:62
int n_elements
Definition list.h:58
Container for bidirectional cipher and HMAC key material.
Definition crypto.h:240
Container for unidirectional cipher and HMAC key material.
Definition crypto.h:152