diff options
Diffstat (limited to '')
| -rw-r--r-- | list.h | 220 |
1 files changed, 220 insertions, 0 deletions
@@ -0,0 +1,220 @@ +/* + * OpenVPN -- An application to securely tunnel IP networks + * over a single TCP/UDP port, with support for SSL/TLS-based + * session authentication and key exchange, + * packet encryption, packet authentication, and + * packet compression. + * + * Copyright (C) 2002-2005 OpenVPN Solutions LLC <info@openvpn.net> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program (see the file COPYING included with this + * distribution); if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef LIST_H +#define LIST_H + +/* + * This code is a fairly straightforward hash + * table implementation using Bob Jenkins' + * hash function. + * + * Hash tables are used in OpenVPN to keep track of + * client instances over various key spaces. + */ + +#if P2MP_SERVER + +/* define this to enable special list test mode */ +/*#define LIST_TEST*/ + +#include "basic.h" +#include "thread.h" +#include "buffer.h" + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) + +struct hash_element +{ + void *value; + const void *key; + unsigned int hash_value; + struct hash_element *next; +}; + +struct hash_bucket +{ + MUTEX_DEFINE (mutex); + struct hash_element * volatile list; +}; + +struct hash +{ + int n_buckets; + int n_elements; + int mask; + uint32_t iv; + uint32_t (*hash_function)(const void *key, uint32_t iv); + bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */ + struct hash_bucket *buckets; +}; + +struct hash *hash_init (const int n_buckets, + uint32_t (*hash_function)(const void *key, uint32_t iv), + bool (*compare_function)(const void *key1, const void *key2)); + +void hash_free (struct hash *hash); + +bool hash_add (struct hash *hash, const void *key, void *value, bool replace); + +struct hash_element *hash_lookup_fast (struct hash *hash, + struct hash_bucket *bucket, + const void *key, + uint32_t hv); + +bool hash_remove_fast (struct hash *hash, + struct hash_bucket *bucket, + const void *key, + uint32_t hv); + +void hash_remove_by_value (struct hash *hash, void *value, bool autolock); + +struct hash_iterator +{ + struct hash *hash; + int bucket_index; + struct hash_bucket *bucket; + struct hash_element *elem; + struct hash_element *last; + bool bucket_marked; + bool autolock; + int bucket_index_start; + int bucket_index_end; +}; + +void hash_iterator_init_range (struct hash *hash, + struct hash_iterator *hi, + bool autolock, + int start_bucket, + int end_bucket); + +void hash_iterator_init (struct hash *hash, struct hash_iterator *iter, bool autolock); +struct hash_element *hash_iterator_next (struct hash_iterator *hi); +void hash_iterator_delete_element (struct hash_iterator *hi); +void hash_iterator_free (struct hash_iterator *hi); + +uint32_t hash_func (const uint8_t *k, uint32_t length, uint32_t initval); + +uint32_t void_ptr_hash_function (const void *key, uint32_t iv); +bool void_ptr_compare_function (const void *key1, const void *key2); + +#ifdef LIST_TEST +void list_test (void); +#endif + +static inline uint32_t +hash_value (const struct hash *hash, const void *key) +{ + return (*hash->hash_function)(key, hash->iv); +} + +static inline int +hash_n_elements (const struct hash *hash) +{ + return hash->n_elements; +} + +static inline int +hash_n_buckets (const struct hash *hash) +{ + return hash->n_buckets; +} + +static inline struct hash_bucket * +hash_bucket (struct hash *hash, uint32_t hv) +{ + return &hash->buckets[hv & hash->mask]; +} + +static inline void +hash_bucket_lock (struct hash_bucket *bucket) +{ + mutex_lock (&bucket->mutex); +} + +static inline void +hash_bucket_unlock (struct hash_bucket *bucket) +{ + mutex_unlock (&bucket->mutex); +} + +static inline void * +hash_lookup_lock (struct hash *hash, const void *key, uint32_t hv) +{ + void *ret = NULL; + struct hash_element *he; + struct hash_bucket *bucket = &hash->buckets[hv & hash->mask]; + + mutex_lock (&bucket->mutex); + he = hash_lookup_fast (hash, bucket, key, hv); + if (he) + ret = he->value; + mutex_unlock (&bucket->mutex); + + return ret; +} + +static inline void * +hash_lookup (struct hash *hash, const void *key) +{ + return hash_lookup_lock (hash, key, hash_value (hash, key)); +} + +/* NOTE: assumes that key is not a duplicate */ +static inline void +hash_add_fast (struct hash *hash, + struct hash_bucket *bucket, + const void *key, + uint32_t hv, + void *value) +{ + struct hash_element *he; + + ALLOC_OBJ (he, struct hash_element); + he->value = value; + he->key = key; + he->hash_value = hv; + he->next = bucket->list; + bucket->list = he; + ++hash->n_elements; +} + +static inline bool +hash_remove (struct hash *hash, const void *key) +{ + uint32_t hv; + struct hash_bucket *bucket; + bool ret; + + hv = hash_value (hash, key); + bucket = &hash->buckets[hv & hash->mask]; + mutex_lock (&bucket->mutex); + ret = hash_remove_fast (hash, bucket, key, hv); + mutex_unlock (&bucket->mutex); + return ret; +} + +#endif /* P2MP_SERVER */ +#endif /* LIST */ |