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