list.h

/*
 *  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-2009 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 "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 *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, 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 */