~ubuntu-branches/ubuntu/oneiric/openvpn/oneiric

/*

 *  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 */