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-2010 OpenVPN Technologies, 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
20 *  along with this program (see the file COPYING included with this
21 *  distribution); if not, write to the Free Software Foundation, Inc.,
22 *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
23 */
24
25#ifndef LIST_H
26#define LIST_H
27
28/*
29 * This code is a fairly straightforward hash
30 * table implementation using Bob Jenkins'
31 * hash function.
32 *
33 * Hash tables are used in OpenVPN to keep track of
34 * client instances over various key spaces.
35 */
36
37#if P2MP_SERVER
38
39/* define this to enable special list test mode */
40/*#define LIST_TEST*/
41
42#include "basic.h"
43#include "buffer.h"
44
45#define hashsize(n) ((uint32_t)1<<(n))
46#define hashmask(n) (hashsize(n)-1)
47
48struct hash_element
49{
50  void *value;
51  const void *key;
52  unsigned int hash_value;
53  struct hash_element *next;
54};
55
56struct hash_bucket
57{
58  struct hash_element *list;
59};
60
61struct hash
62{
63  int n_buckets;
64  int n_elements;
65  int mask;
66  uint32_t iv;
67  uint32_t (*hash_function)(const void *key, uint32_t iv);
68  bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
69  struct hash_bucket *buckets;
70};
71
72struct hash *hash_init (const int n_buckets,
73			const uint32_t iv,
74			uint32_t (*hash_function)(const void *key, uint32_t iv),
75			bool (*compare_function)(const void *key1, const void *key2));
76
77void hash_free (struct hash *hash);
78
79bool hash_add (struct hash *hash, const void *key, void *value, bool replace);
80
81struct hash_element *hash_lookup_fast (struct hash *hash,
82				       struct hash_bucket *bucket,
83				       const void *key,
84				       uint32_t hv);
85
86bool hash_remove_fast (struct hash *hash,
87		       struct hash_bucket *bucket,
88		       const void *key,
89		       uint32_t hv);
90
91void hash_remove_by_value (struct hash *hash, void *value);
92
93struct hash_iterator
94{
95  struct hash *hash;
96  int bucket_index;
97  struct hash_bucket *bucket;
98  struct hash_element *elem;
99  struct hash_element *last;
100  bool bucket_marked;
101  int bucket_index_start;
102  int bucket_index_end;
103};
104
105void hash_iterator_init_range (struct hash *hash,
106			       struct hash_iterator *hi,
107			       int start_bucket,
108			       int end_bucket);
109
110void hash_iterator_init (struct hash *hash, struct hash_iterator *iter);
111struct hash_element *hash_iterator_next (struct hash_iterator *hi);
112void hash_iterator_delete_element (struct hash_iterator *hi);
113void hash_iterator_free (struct hash_iterator *hi);
114
115uint32_t hash_func (const uint8_t *k, uint32_t length, uint32_t initval);
116
117uint32_t void_ptr_hash_function (const void *key, uint32_t iv);
118bool void_ptr_compare_function (const void *key1, const void *key2);
119
120#ifdef LIST_TEST
121void list_test (void);
122#endif
123
124static inline uint32_t
125hash_value (const struct hash *hash, const void *key)
126{
127  return (*hash->hash_function)(key, hash->iv);
128}
129
130static inline int
131hash_n_elements (const struct hash *hash)
132{
133  return hash->n_elements;
134}
135
136static inline int
137hash_n_buckets (const struct hash *hash)
138{
139  return hash->n_buckets;
140}
141
142static inline struct hash_bucket *
143hash_bucket (struct hash *hash, uint32_t hv)
144{
145  return &hash->buckets[hv & hash->mask];
146}
147
148static inline void *
149hash_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    ret = he->value;
159
160  return ret;
161}
162
163/* NOTE: assumes that key is not a duplicate */
164static inline void
165hash_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
182static inline bool
183hash_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 /* P2MP_SERVER */
196#endif /* LIST */
197