hash_table.c

PSlib是一个用来生成PostScript文件的类库。提供了一个生成PostScript文件的简单方法。

/*********************************************************************
 *
 * Copyright (C) 2001-2002,  Simon Kagstrom
 *
 * Filename:      hash_table.c
 * Description:   The implementation of the hash table (MK2).
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library 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 Library General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA.
 *
 * $Id: hash_table.c,v 1.3 2007/07/04 13:07:59 steinm Exp $
 *
 ********************************************************************/

#include <stdlib.h> /* malloc */
#include <stdio.h>  /* perror */
#include <errno.h>  /* errno */
#include <string.h> /* memcmp */
#include <assert.h> /* assert */

#include "ght_hash_table.h"

#ifdef WIN32
#define PSLIB_INLINE
#else
#define PSLIB_INLINE inline
#endif

/* Flags for the elements. This is currently unused. */
#define FLAGS_NONE     0 /* No flags */
#define FLAGS_NORMAL   0 /* Normal item. All user-inserted stuff is normal */
#define FLAGS_INTERNAL 1 /* The item is internal to the hash table */

/* Prototypes */
static PSLIB_INLINE void              transpose(ght_hash_table_t *p_ht, ght_uint32_t l_bucket, ght_hash_entry_t *p_entry);
static PSLIB_INLINE void              move_to_front(ght_hash_table_t *p_ht, ght_uint32_t l_bucket, ght_hash_entry_t *p_entry);
static PSLIB_INLINE void              free_entry_chain(ght_hash_table_t *p_ht, ght_hash_entry_t *p_entry);
static PSLIB_INLINE ght_hash_entry_t *search_in_bucket(ght_hash_table_t *p_ht, ght_uint32_t l_bucket, ght_hash_key_t *p_key, unsigned char i_heuristics);

static PSLIB_INLINE void              hk_fill(ght_hash_key_t *p_hk, int i_size, void *p_key);
static PSLIB_INLINE ght_hash_entry_t *he_create(ght_hash_table_t *p_ht, void *p_data, unsigned int i_key_size, void *p_key_data);
static PSLIB_INLINE void              he_finalize(ght_hash_table_t *p_ht, ght_hash_entry_t *p_he);

/* --- private methods --- */

/* Move p_entry one up in its list. */
static PSLIB_INLINE void transpose(ght_hash_table_t *p_ht, ght_uint32_t l_bucket, ght_hash_entry_t *p_entry)
{
  /*
   *  __    __    __    __
   * |A_|->|X_|->|Y_|->|B_|
   *             /
   * =>        p_entry
   *  __    __/   __    __
   * |A_|->|Y_|->|X_|->|B_|
   */
  if (p_entry->p_prev) /* Otherwise p_entry is already first. */
    {
      ght_hash_entry_t *p_x = p_entry->p_prev;
      ght_hash_entry_t *p_a = p_x?p_x->p_prev:NULL;
      ght_hash_entry_t *p_b = p_entry->p_next;

      if (p_a)
	{
	  p_a->p_next = p_entry;
	}
      else /* This element is now placed first */
	{
	  p_ht->pp_entries[l_bucket] = p_entry;
	}

      if (p_b)
	{
	  p_b->p_prev = p_x;
	}
      if (p_x)
	{
	  p_x->p_next = p_entry->p_next;
	  p_x->p_prev = p_entry;
	}
      p_entry->p_next = p_x;
      p_entry->p_prev = p_a;
    }
}

/* Move p_entry first */
static PSLIB_INLINE void move_to_front(ght_hash_table_t *p_ht, ght_uint32_t l_bucket, ght_hash_entry_t *p_entry)
{
  /*
   *  __    __    __
   * |A_|->|B_|->|X_|
   *            /
   * =>  p_entry
   *  __/   __    __
   * |X_|->|A_|->|B_|
   */
  if (p_entry == p_ht->pp_entries[l_bucket])
    {
      return;
    }

  /* Link p_entry out of the list. */
  p_entry->p_prev->p_next = p_entry->p_next;
  if (p_entry->p_next)
    {
      p_entry->p_next->p_prev = p_entry->p_prev;
    }

  /* Place p_entry first */
  p_entry->p_next = p_ht->pp_entries[l_bucket];
  p_entry->p_prev = NULL;
  p_ht->pp_entries[l_bucket]->p_prev = p_entry;
  p_ht->pp_entries[l_bucket] = p_entry;
}

/* Search for an element in a bucket */
static PSLIB_INLINE ght_hash_entry_t *search_in_bucket(ght_hash_table_t *p_ht, ght_uint32_t l_bucket,
						 ght_hash_key_t *p_key, unsigned char i_heuristics)
{
  ght_hash_entry_t *p_e;

  for (p_e = p_ht->pp_entries[l_bucket];
       p_e;
       p_e = p_e->p_next)
    {
      if ((p_e->key.i_size == p_key->i_size) &&
	  (memcmp(p_e->key.p_key, p_key->p_key, p_e->key.i_size) == 0))
	{
	  /* Matching entry found - Apply heuristics, if any */
	  switch (i_heuristics)
	    {
	    case GHT_HEURISTICS_MOVE_TO_FRONT:
	      move_to_front(p_ht, l_bucket, p_e);
	      break;
	    case GHT_HEURISTICS_TRANSPOSE:
	      transpose(p_ht, l_bucket, p_e);
	      break;
	    default:
	      break;
	    }
	  return p_e;
	}
    }
  return NULL;
}

/* Free a chain of entries (in a bucket) */
static PSLIB_INLINE void free_entry_chain(ght_hash_table_t *p_ht, ght_hash_entry_t *p_entry)
{
  ght_hash_entry_t *p_e = p_entry;

  while(p_e)
    {
      ght_hash_entry_t *p_e_next = p_e->p_next;
      he_finalize(p_ht, p_e);
      p_e = p_e_next;
    }
}


/* Fill in the data to a existing hash key */
static PSLIB_INLINE void hk_fill(ght_hash_key_t *p_hk, int i_size, void *p_key)
{
  assert(p_hk);

  p_hk->i_size = i_size;
  p_hk->p_key = p_key;
}

/* Create an hash entry */
static PSLIB_INLINE ght_hash_entry_t *he_create(ght_hash_table_t *p_ht, void *p_data,
					  unsigned int i_key_size, void *p_key_data)
{
  ght_hash_entry_t *p_he;

  /*
   * An element like the following is allocated:
   *        elem->p_key
   *       /   elem->p_key->p_key_data
   *  ____|___/________
   * |elem|key|key data|
   * |____|___|________|
   *
   * That is, the key and the key data is stored "inline" within the
   * hash entry.
   *
   * This saves space since malloc only is called once and thus avoids
   * some fragmentation. Thanks to Dru Lemley for this idea.
   */
  if ( !(p_he = (ght_hash_entry_t*)p_ht->fn_alloc (sizeof(ght_hash_entry_t)+i_key_size, p_ht->userdata)) )
    {
      fprintf(stderr, "fn_alloc failed!\n");
      return NULL;
    }

  p_he->p_data = p_data;
  p_he->p_next = NULL;
  p_he->p_prev = NULL;

  /* Create the key */
  p_he->key.i_size = i_key_size;
  p_he->key.p_key = (void*)(p_he+1);
  memcpy(p_he->key.p_key, p_key_data, i_key_size);

  return p_he;
}

/* Finalize (free) a hash entry */
static PSLIB_INLINE void he_finalize(ght_hash_table_t *p_ht, ght_hash_entry_t *p_he)
{
  assert(p_he);

#if !defined(NDEBUG)
  p_he->p_next = NULL;
  p_he->p_prev = NULL;
#endif /* NDEBUG */

  /* Free the entry */
  p_ht->fn_free(p_he, p_ht->userdata);
}

/* Allocate memory */
static void *ght_malloc(size_t size, void *data)
{
	return(malloc(size));
}

/* Free memory */
static void ght_free(void *ptr, void *data)
{
	free(ptr);
}

/* --- Exported methods --- */
/* Create a new hash table */
ght_hash_table_t *ght_create(unsigned int i_size)
{
  ght_hash_table_t *p_ht;
  int i=0;

  if ( !(p_ht = (ght_hash_table_t*)malloc (sizeof(ght_hash_table_t))) )
    {
      perror("malloc");
      return NULL;
    }

  /* Set the size of the hash table to the nearest 2^i higher then i_size */
  p_ht->i_size = 0;
  while(p_ht->i_size < i_size)
    {
      p_ht->i_size = 1<<i++;
    }

  p_ht->i_size_mask = (1<<(i-1))-1; /* Mask to & with */
  p_ht->i_items = 0;

  p_ht->fn_hash = ght_one_at_a_time_hash;

  /* Standard values for allocations */
  p_ht->fn_alloc = ght_malloc;
  p_ht->fn_free = ght_free;
	p_ht->userdata = NULL;

  /* Set flags */
  p_ht->i_heuristics = GHT_HEURISTICS_NONE;
  p_ht->i_automatic_rehash = FALSE;

  /* Create an empty bucket list. */
  if ( !(p_ht->pp_entries = (ght_hash_entry_t**)malloc(p_ht->i_size*sizeof(ght_hash_entry_t*))) )
    {
      perror("malloc");
      free(p_ht);
      return NULL;
    }
  memset(p_ht->pp_entries, 0, p_ht->i_size*sizeof(ght_hash_entry_t*));

  /* Initialise the number of entries in each bucket to zero */
  if ( !(p_ht->p_nr = (int*)malloc(p_ht->i_size*sizeof(int))))
    {
      perror("malloc");
      free(p_ht->pp_entries);
      free(p_ht);
      return NULL;
    }
  memset(p_ht->p_nr, 0, p_ht->i_size*sizeof(int));

  return p_ht;
}

/* Set the allocation/deallocation function to use */
void ght_set_alloc(ght_hash_table_t *p_ht, ght_fn_alloc_t fn_alloc, ght_fn_free_t fn_free, void *data)
{
  p_ht->fn_alloc = fn_alloc;
  p_ht->fn_free = fn_free;
	p_ht->userdata = data;
}

/* Set the hash function to use */
void ght_set_hash(ght_hash_table_t *p_ht, ght_fn_hash_t fn_hash)
{
  p_ht->fn_hash = fn_hash;
}

/* Set the heuristics to use. */
void ght_set_heuristics(ght_hash_table_t *p_ht, int i_heuristics)
{
  p_ht->i_heuristics = i_heuristics;
}

/* Set the rehashing status of the table. */
void ght_set_rehash(ght_hash_table_t *p_ht, int b_rehash)
{
  p_ht->i_automatic_rehash = b_rehash;
}

/* Get the number of items in the hash table */
unsigned int ght_size(ght_hash_table_t *p_ht)
{
  return p_ht->i_items;
}