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