list.c

OpenVPN is a robust and highly flexible tunneling application that uses all of the encryption, authe

/*
 *  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-2004 James Yonan <[e-mail]>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  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
 */

#ifdef WIN32
#include "config-win32.h"
#else
#include "config.h"
#endif

#include "syshead.h"

#if P2MP

#include "list.h"
#include "misc.h"

#include "memdbg.h"

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))
{
  struct hash *h;
  int i;

  ASSERT (n_buckets > 0);
  ALLOC_OBJ_CLEAR (h, struct hash);
  h->n_buckets = (int) adjust_power_of_2 (n_buckets);
  h->mask = h->n_buckets - 1;
  h->hash_function = hash_function;
  h->compare_function = compare_function;
  h->iv = get_random ();
  ALLOC_ARRAY (h->buckets, struct hash_bucket, h->n_buckets);
  for (i = 0; i < h->n_buckets; ++i)
    {
      struct hash_bucket *b = &h->buckets[i];
      b->list = NULL;
      //mutex_init (&b->mutex);
    }
  return h;
}

void
hash_free (struct hash *hash)
{
  int i;
  for (i = 0; i < hash->n_buckets; ++i)
    {
      struct hash_bucket *b = &hash->buckets[i];
      struct hash_element *he = b->list;

      //mutex_destroy (&b->mutex);
      while (he)
	{
	  struct hash_element *next = he->next;
	  free (he);
	  he = next;
	}
    }
  free (hash->buckets);
  free (hash);
}

struct hash_element *
hash_lookup_fast (struct hash *hash,
		  struct hash_bucket *bucket,
		  const void *key,
		  uint32_t hv)
{
  struct hash_element *he;
  struct hash_element *prev = NULL;

  he = bucket->list;

  while (he)
    {
      if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
	{
	  /* move to head of list */
	  if (prev)
	    {
	      prev->next = he->next;
	      he->next = bucket->list;
	      bucket->list = he;
	    }
	  return he;
	}
      prev = he;
      he = he->next;
    }

  return NULL;
}

bool
hash_remove_fast (struct hash *hash,
		  struct hash_bucket *bucket,
		  const void *key,
		  uint32_t hv)
{
  struct hash_element *he;
  struct hash_element *prev = NULL;

  he = bucket->list;

  while (he)
    {
      if (hv == he->hash_value && (*hash->compare_function)(key, he->key))
	{
	  if (prev)
	    prev->next = he->next;
	  else
	    bucket->list = he->next;
	  free (he);
	  --hash->n_elements;
	  return true;
	}
      prev = he;
      he = he->next;
    }
  return false;
}

bool
hash_add (struct hash *hash, const void *key, void *value, bool replace)
{
  uint32_t hv;
  struct hash_bucket *bucket;
  struct hash_element *he;
  bool ret = false;

  hv = hash_value (hash, key);
  bucket = &hash->buckets[hv & hash->mask];
  //mutex_lock (&bucket->mutex);

  if ((he = hash_lookup_fast (hash, bucket, key, hv))) /* already exists? */
    {
      if (replace)
	{
	  he->value = value;
	  ret = true;
	}
    }
  else
    {
      hash_add_fast (hash, bucket, key, hv, value);
      ret = true;
    }

  //mutex_unlock (&bucket->mutex);

  return ret;
}

void
hash_remove_by_value (struct hash *hash, void *value, bool autolock)
{
  struct hash_iterator hi;
  struct hash_element *he;

  hash_iterator_init (hash, &hi, autolock);
  while ((he = hash_iterator_next (&hi)))
    {
      if (he->value == value)
	hash_iterator_delete_element (&hi);
    }
  hash_iterator_free (&hi);
}

static void
hash_remove_marked (struct hash *hash, struct hash_bucket *bucket)
{
  struct hash_element *prev = NULL;
  struct hash_element *he = bucket->list;

  while (he)
    {
      if (!he->key) /* marked? */
	{
	  struct hash_element *newhe;
	  if (prev)
	    newhe = prev->next = he->next;
	  else
	    newhe = bucket->list = he->next;
	  free (he);
	  --hash->n_elements;
	  he = newhe;
	}
      else
	{
	  prev = he;
	  he = he->next;
	}
    }
}

uint32_t
void_ptr_hash_function (const void *key, uint32_t iv)
{
  return hash_func ((const void *)&key, sizeof (key), iv);
}

bool
void_ptr_compare_function (const void *key1, const void *key2)
{
  return key1 == key2;
}

void
hash_iterator_init_range (struct hash *hash,
		       struct hash_iterator *hi,
		       bool autolock,
		       int start_bucket,
		       int end_bucket)
{
  if (end_bucket > hash->n_buckets)
    end_bucket = hash->n_buckets;

  ASSERT (start_bucket >= 0 && start_bucket <= end_bucket);

  hi->hash = hash;
  hi->elem = NULL;
  hi->bucket = NULL;
  hi->autolock = autolock;
  hi->last = NULL;
  hi->bucket_marked = false;
  hi->bucket_index_start = start_bucket;
  hi->bucket_index_end = end_bucket;
  hi->bucket_index = hi->bucket_index_start - 1;
}

void
hash_iterator_init (struct hash *hash,
		    struct hash_iterator *hi,
		    bool autolock)
{
  hash_iterator_init_range (hash, hi, autolock, 0, hash->n_buckets);
}

static inline void
hash_iterator_lock (struct hash_iterator *hi, struct hash_bucket *b)
{
  if (hi->autolock)
    {
      //mutex_lock (&b->mutex);
    }
  hi->bucket = b;
  hi->last = NULL;
  hi->bucket_marked = false;
}

static inline void
hash_iterator_unlock (struct hash_iterator *hi)
{
  if (hi->bucket)
    {
      if (hi->bucket_marked)
	{
	  hash_remove_marked (hi->hash, hi->bucket);
	  hi->bucket_marked = false;
	}
      if (hi->autolock)
	{
	  //mutex_unlock (&hi->bucket->mutex);
	}
      hi->bucket = NULL;
      hi->last = NULL;
    }
}

static inline void
hash_iterator_advance (struct hash_iterator *hi)
{
  hi->last = hi->elem;
  hi->elem = hi->elem->next;
}

void
hash_iterator_free (struct hash_iterator *hi)
{
  hash_iterator_unlock (hi);
}

struct hash_element *
hash_iterator_next (struct hash_iterator *hi)
{
  struct hash_element *ret = NULL;
  if (hi->elem)
    {
      ret = hi->elem;
      hash_iterator_advance (hi);
    }
  else
    {
      while (++hi->bucket_index < hi->bucket_index_end)
	{
	  struct hash_bucket *b;
	  hash_iterator_unlock (hi);
	  b = &hi->hash->buckets[hi->bucket_index];
	  if (b->list)
	    {
	      hash_iterator_lock (hi, b);
	      hi->elem = b->list;
	      if (hi->elem)
		{
		  ret = hi->elem;
		  hash_iterator_advance (hi);
		  break;
		}
	    }