ght_hash_table.h

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

/*********************************************************************
 * Copyright (C) 2001, 2003-2004-2002,  Simon Kagstrom
 *
 * Filename:      ght_hash_table.h.in
 * Description:   The definitions used in the hash table.
 *
 * 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: ght_hash_table.h.in,v 1.4 2007/07/04 13:07:59 steinm Exp $
 *
 ********************************************************************/

/**
 * @file
 * libghthash is a generic hash table used for storing arbitrary
 * data.
 *
 * Libghthash really stores pointers to data - the hash
 * table knows nothing about the actual type of the data.
 *
 * A simple example to get started can be found in the
 * <TT>example/simple.c</TT> file found in the distribution.
 * <TT>hash_test.c</TT> provides a more comlpete example.
 *
 * Some basic properties of the hash table are:
 *
 * - Both the data stored and the keys are of void type, which
 *   means that you can store any kind of data.
 *
 * - The only functions you probably will need to start is:
 *   - ght_create(), which creates a new hash table.d
 *   - ght_insert(), which inserts a new entry into a table.
 *   - ght_get(), which searches for an entry.
 *   - ght_remove(), which removes and entry.
 *   - ght_finalize(), which destroys a hash table.
 *
 * - Inserting entries is done without first creating a key,
 *   i.e. you insert with the data, the datasize, the key and the
 *   key size directly.
 *
 * - The hash table copies the key data when inserting new
 *   entries. This means that you should <I>not</I> malloc() the key
 *   before inserting a new entry.
 *
 */
#ifndef GHT_HASH_TABLE_H
#define GHT_HASH_TABLE_H

#include <stdlib.h>                    /* size_t */
#ifndef WIN32
#include <stdint.h>                    /* uint32_t */
#endif

#ifdef __cplusplus
extern "C" {
#endif

#define GHT_HEURISTICS_NONE          0
#define GHT_HEURISTICS_TRANSPOSE     1
#define GHT_HEURISTICS_MOVE_TO_FRONT 2
#define GHT_AUTOMATIC_REHASH         4

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

/** unsigned 32 bit integer. */
/*typedef unsigned  _ght_uint32_t;*/
#ifndef WIN32
typedef uint32_t ght_uint32_t;
#else
typedef unsigned int ght_uint32_t;
#endif

/**
 * The structure for hash keys. You should not care about this
 * structure unless you plan to write your own hash functions.
 */
typedef struct s_hash_key
{
  unsigned int i_size;       /**< The size in bytes of the key p_key */
  void *p_key;               /**< A pointer to the key. */
} ght_hash_key_t;

/*
 * The structure for hash entries.
 */
typedef struct s_hash_entry
{
  void *p_data;

  struct s_hash_entry *p_next;
  struct s_hash_entry *p_prev;
  ght_hash_key_t key;
} ght_hash_entry_t;

/*
 * The structure used in iterations. You should not care about the
 * contents of this, it will be filled and updated by ght_first() and
  * ght_next().
 */
typedef struct
{
  int i_curr_bucket;         /* The current bucket */
  ght_hash_entry_t *p_entry; /* The current entry */
  ght_hash_entry_t *p_next;  /* The next entry */
} ght_iterator_t;

/**
 * Definition of the hash function pointers. @c ght_fn_hash_t should be
 * used when implementing new hash functions. Look at the supplied
 * hash functions, like @c ght_one_at_a_time_hash(), for examples of hash
 * functions.
 *
 * @param p_key the key to calculate the hash value for.
 *
 * @return a 32 bit hash value.
 *
 * @see @c ght_one_at_a_time_hash(), @c ght_rotating_hash(),
 *      @c ght_crc_hash()
 */
typedef ght_uint32_t (*ght_fn_hash_t)(ght_hash_key_t *p_key);

/**
 * Definition of the allocation function pointers. This is simply the
 * same definition as @c malloc().
 *
 * @param size the size to allocate. This will always be
 *        <TT>sizeof(ght_hash_entry_t) + sizeof(ght_hash_key_t) +
 *        key_size</TT>.
 *
 * @return a pointer to the allocated region, or NULL if the
 *         allocation failed.
 */
typedef void *(*ght_fn_alloc_t)(size_t size, void *data);

/**
 * Definition of the deallocation function pointers. This is simply the
 * same definition as @c free().
 *
 * @param ptr a pointer to the region to free.
 */
typedef void (*ght_fn_free_t)(void *ptr, void *data);


/**
 * The hash table structure.
 */
typedef struct
{
  unsigned int i_items;              /**< The current number of items in the table */
  unsigned int i_size;               /**< The number of buckets */
  ght_fn_hash_t fn_hash;             /**< The hash function used */
  ght_fn_alloc_t fn_alloc;           /**< The function used for allocating entries */
  ght_fn_free_t fn_free;             /**< The function used for freeing entries */
	void *userdata;                    /**< User data passed to alloc and free */
  int i_heuristics;                  /**< The type of heuristics used */
  int i_automatic_rehash;            /**< TRUE if automatic rehashing is used */

  /* private: */
  ght_hash_entry_t **pp_entries;
  int *p_nr;                         /* The number of entries in each bucket */
  int i_size_mask;                   /* The number of bits used in the size */
} ght_hash_table_t;

/**
 * Create a new hash table. The number of buckets should be about as
 * big as the number of elements you wish to store in the table for
 * good performance. The number of buckets is rounded to the next
 * higher power of two.
 *
 * The hash table is created with @c ght_one_at_a_time_hash() as hash
 * function, automatic rehashing disabled, @c malloc() as the memory
 * allocator and no heuristics.
 *
 * @param i_size the number of buckets in the hash table. Giving a
 *        non-power of two here will round the size up to the next
 *        power of two.
 *
 * @see ght_one_at_a_time_hash(), ght_rotating_hash(), ght_crc_hash(),
 * @see ght_set_heuristics(), ght_set_rehash()
 *
 * @return a pointer to the hash table or NULL upon error.
 */
ght_hash_table_t *ght_create(unsigned int i_size);

/**
 * Set the allocation/freeing functions to use for a hash table. The
 * allocation function will only be called when a new entry is
 * inserted.
 *
 * The allocation size will always be <TT>sizeof(ght_hash_entry_t) +
 * sizeof(ght_hash_key_t) + key_size</TT>. The actual size varies with
 * the key size.
 *
 * If this function is <I>not</I> called, @c malloc() and @c free()
 * will be used for allocation and freeing.
 *
 * @warning Always call this function <I>before</I> any entries are
 *          inserted into the table. Otherwise, the new free() might be called
 *          on something that were allocated with another allocation function.
 *
 * @param p_ht the hash table to set the memory management functions
 *        for.
 * @param fn_alloc the allocation function to use.
 * @param fn_free the 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);

/**
 * Set the hash function to use for a hash table.
 *
 * @warning Always call this function before any entries are inserted
 *          into the table. Otherwise, it will not be possible to find entries
 *          that were inserted before this function was called.
 *
 * @param p_ht the hash table set the hash function for.
 * @param fn_hash the hash function.
 */
void ght_set_hash(ght_hash_table_t *p_ht, ght_fn_hash_t fn_hash);

/**
 * Set the heuristics to use for the hash table. The possible values are:
 *
 * - <TT>GHT_HEURISTICS_NONE</TT>: Don't use any heuristics.
 * - <TT>0</TT>: Same as above.
 * - <TT>GHT_HEURISTICS_TRANSPOSE</TT>: Use transposing heuristics. An
 *   accessed element will move one step up in the bucket-list with this
 *   method.
 * - <TT>GHT_HEURISTICS_MOVE_TO_FRONT</TT>: Use move-to-front
 *   heuristics. An accessed element will be moved the front of the
 *   bucket list with this method.
 *
 * @param p_ht the hash table set the heuristics for.
 * @param i_heuristics the heuristics to use.
 */
void ght_set_heuristics(ght_hash_table_t *p_ht, int i_heuristics);

/**
 * Enable or disable automatic rehashing.
 *
 * With automatic rehashing, the table will rehash itself when the
 * number of elements in the table are twice as many as the number of
 * buckets. You should note that automatic rehashing will cause your
 * application to be really slow when the table is rehashing (which
 * might happen at times when you need speed), you should therefore be
 * careful with this in time-constrainted applications.