Imported Upstream version 2.2.1upstream/2.2.1

1 files changed, 196 insertions, 0 deletions

diff --git a/list.h b/list.h
new file mode 100644
index 0000000..adde36b
--- /dev/null
+++ b/list.h
@@ -0,0 +1,196 @@
+/*
+ *  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 */