diff options
Diffstat (limited to 'list.h')
| -rw-r--r-- | list.h | 196 |
1 files changed, 0 insertions, 196 deletions
@@ -1,196 +0,0 @@ -/* - * 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-2010 OpenVPN Technologies, Inc. <sales@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 "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 -{ - struct hash_element *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, - const uint32_t iv, - 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); - -struct hash_iterator -{ - struct hash *hash; - int bucket_index; - struct hash_bucket *bucket; - struct hash_element *elem; - struct hash_element *last; - bool bucket_marked; - int bucket_index_start; - int bucket_index_end; -}; - -void hash_iterator_init_range (struct hash *hash, - struct hash_iterator *hi, - int start_bucket, - int end_bucket); - -void hash_iterator_init (struct hash *hash, struct hash_iterator *iter); -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_lookup (struct hash *hash, const void *key) -{ - void *ret = NULL; - struct hash_element *he; - uint32_t hv = hash_value (hash, key); - struct hash_bucket *bucket = &hash->buckets[hv & hash->mask]; - - he = hash_lookup_fast (hash, bucket, key, hv); - if (he) - ret = he->value; - - return ret; -} - -/* 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]; - ret = hash_remove_fast (hash, bucket, key, hv); - return ret; -} - -#endif /* P2MP_SERVER */ -#endif /* LIST */ |