ght_hash_table.h

Go to the documentation of this file.

/*-*-c-*- ************************************************************
 * Copyright (C) 2001-2005,  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 15761 2007-07-15 06:08:52Z ska $
 *
 ********************************************************************/

#ifndef GHT_HASH_TABLE_H
#define GHT_HASH_TABLE_H
 
#include <stdlib.h>                    /* size_t */
 
#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

typedef unsigned int ght_uint32_t;

typedef struct s_hash_key
{
  unsigned int i_size;       
  const void *p_key;         
} ght_hash_key_t;
 
/*
 * The structure for hash entries.
 *
 * LOCK: Should be possible to do somewhat atomically
 */
typedef struct s_hash_entry
{
  void *p_data;
 
  struct s_hash_entry *p_next;
  struct s_hash_entry *p_prev;
  struct s_hash_entry *p_older;
  struct s_hash_entry *p_newer;
  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
{
  ght_hash_entry_t *p_entry; /* The current entry */
  ght_hash_entry_t *p_next;  /* The next entry */
} ght_iterator_t;

typedef ght_uint32_t (*ght_fn_hash_t)(ght_hash_key_t *p_key);

typedef void *(*ght_fn_alloc_t)(size_t size);

typedef void (*ght_fn_free_t)(void *ptr);

typedef void (*ght_fn_bucket_free_callback_t)(void *data, const void *key);

typedef struct
{
  unsigned int i_items;              
  unsigned int i_size;               
  ght_fn_hash_t fn_hash;             
  ght_fn_alloc_t fn_alloc;           
  ght_fn_free_t fn_free;             
  ght_fn_bucket_free_callback_t fn_bucket_free; 
  int i_heuristics;                  
  int i_automatic_rehash;            
 
  /* 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 */
  unsigned int bucket_limit;
 
  ght_hash_entry_t *p_oldest;        /* The entry inserted the earliest. */
  ght_hash_entry_t *p_newest;        /* The entry inserted the latest. */
} ght_hash_table_t;

ght_hash_table_t *ght_create(unsigned int i_size);

void ght_set_alloc(ght_hash_table_t *p_ht, ght_fn_alloc_t fn_alloc, ght_fn_free_t fn_free);

void ght_set_hash(ght_hash_table_t *p_ht, ght_fn_hash_t fn_hash);

void ght_set_heuristics(ght_hash_table_t *p_ht, int i_heuristics);

void ght_set_rehash(ght_hash_table_t *p_ht, int b_rehash);

void ght_set_bounded_buckets(ght_hash_table_t *p_ht, unsigned int limit, ght_fn_bucket_free_callback_t fn);
 

unsigned int ght_size(ght_hash_table_t *p_ht);

unsigned int ght_table_size(ght_hash_table_t *p_ht);
 

int ght_insert(ght_hash_table_t *p_ht,
               void *p_entry_data,
               unsigned int i_key_size, const void *p_key_data);

void *ght_replace(ght_hash_table_t *p_ht,
                  void *p_entry_data,
                  unsigned int i_key_size, const void *p_key_data);
 

void *ght_get(ght_hash_table_t *p_ht,
              unsigned int i_key_size, const void *p_key_data);

void *ght_remove(ght_hash_table_t *p_ht,
                 unsigned int i_key_size, const void *p_key_data);

void *ght_first(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, const void **pp_key);

 
void *ght_first_keysize(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, const void **pp_key, unsigned int *size);

void *ght_next(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, const void **pp_key);

 
void *ght_next_keysize(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, const void **pp_key, unsigned int *size);

void ght_rehash(ght_hash_table_t *p_ht, unsigned int i_size);

void ght_finalize(ght_hash_table_t *p_ht);
 
/* exported hash functions */

ght_uint32_t ght_one_at_a_time_hash(ght_hash_key_t *p_key);

ght_uint32_t ght_rotating_hash(ght_hash_key_t *p_key);

ght_uint32_t ght_crc_hash(ght_hash_key_t *p_key);
 
#ifdef USE_PROFILING
void ght_print(ght_hash_table_t *p_ht);
#endif
 
#ifdef __cplusplus
}
#endif
 
#endif /* GHT_HASH_TABLE_H */