Main Page | Class List | Directories | File List | Class Members | File Members

ght_hash_table.h

Go to the documentation of this file.
00001 /* -*-c-mode-*- *******************************************************
00002  * Copyright (C) 2001, 2003, 2005-2004-2002,  Simon Kagstrom
00003  *
00004  * Filename:      ght_hash_table.h.in
00005  * Description:   The definitions used in the hash table.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Library General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Library General Public
00018  * License along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
00020  * 02111-1307, USA.
00021  *
00022  * $Id: ght_hash_table.h.in 2473 2005-05-08 08:08:27Z ska $
00023  *
00024  ********************************************************************/
00025 
00059 #ifndef GHT_HASH_TABLE_H
00060 #define GHT_HASH_TABLE_H
00061 
00062 #include <stdlib.h>                    /* size_t */
00063 
00064 #ifdef __cplusplus
00065 extern "C" {
00066 #endif
00067 
00068 #define GHT_HEURISTICS_NONE          0
00069 #define GHT_HEURISTICS_TRANSPOSE     1
00070 #define GHT_HEURISTICS_MOVE_TO_FRONT 2
00071 #define GHT_AUTOMATIC_REHASH         4
00072 
00073 #ifndef TRUE
00074 #define TRUE 1
00075 #endif
00076 
00077 #ifndef FALSE
00078 #define FALSE 0
00079 #endif
00080 
00082 typedef unsigned int ght_uint32_t;
00083 
00088 typedef struct s_hash_key
00089 {
00090   unsigned int i_size;       
00091   void *p_key;               
00092 } ght_hash_key_t;
00093 
00094 /*
00095  * The structure for hash entries.
00096  *
00097  * LOCK: Should be possible to do somewhat atomically
00098  */
00099 typedef struct s_hash_entry
00100 {
00101   void *p_data;
00102 
00103   struct s_hash_entry *p_next;
00104   struct s_hash_entry *p_prev;
00105   ght_hash_key_t key;
00106 } ght_hash_entry_t;
00107 
00108 /*
00109  * The structure used in iterations. You should not care about the
00110  * contents of this, it will be filled and updated by ght_first() and
00111   * ght_next().
00112  */
00113 typedef struct
00114 {
00115   int i_curr_bucket;         /* The current bucket */
00116   ght_hash_entry_t *p_entry; /* The current entry */
00117   ght_hash_entry_t *p_next;  /* The next entry */
00118 } ght_iterator_t;
00119 
00133 typedef ght_uint32_t (*ght_fn_hash_t)(ght_hash_key_t *p_key);
00134 
00145 typedef void *(*ght_fn_alloc_t)(size_t size);
00146 
00153 typedef void (*ght_fn_free_t)(void *ptr);
00154 
00155 
00159 typedef struct
00160 {
00161   unsigned int i_items;              
00162   unsigned int i_size;               
00163   ght_fn_hash_t fn_hash;             
00164   ght_fn_alloc_t fn_alloc;           
00165   ght_fn_free_t fn_free;             
00166   int i_heuristics;                  
00167   int i_automatic_rehash;            
00169   /* private: */
00170   ght_hash_entry_t **pp_entries;
00171   int *p_nr;                         /* The number of entries in each bucket */
00172   int i_size_mask;                   /* The number of bits used in the size */
00173 } ght_hash_table_t;
00174 
00194 ght_hash_table_t *ght_create(unsigned int i_size);
00195 
00217 void ght_set_alloc(ght_hash_table_t *p_ht, ght_fn_alloc_t fn_alloc, ght_fn_free_t fn_free);
00218 
00229 void ght_set_hash(ght_hash_table_t *p_ht, ght_fn_hash_t fn_hash);
00230 
00246 void ght_set_heuristics(ght_hash_table_t *p_ht, int i_heuristics);
00247 
00262 void ght_set_rehash(ght_hash_table_t *p_ht, int b_rehash);
00263 
00271 unsigned int ght_size(ght_hash_table_t *p_ht);
00272 
00280 unsigned int ght_table_size(ght_hash_table_t *p_ht);
00281 
00282 
00317 int ght_insert(ght_hash_table_t *p_ht,
00318                void *p_entry_data,
00319                unsigned int i_key_size, void *p_key_data);
00320 
00333 void *ght_replace(ght_hash_table_t *p_ht,
00334                   void *p_entry_data,
00335                   unsigned int i_key_size, void *p_key_data);
00336 
00337 
00348 void *ght_get(ght_hash_table_t *p_ht,
00349               unsigned int i_key_size, void *p_key_data);
00350 
00361 void *ght_remove(ght_hash_table_t *p_ht,
00362                  unsigned int i_key_size, void *p_key_data);
00363 
00405 void *ght_first(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, void **pp_key);
00406 
00426 void *ght_next(ght_hash_table_t *p_ht, ght_iterator_t *p_iterator, void **pp_key);
00427 
00444 void ght_rehash(ght_hash_table_t *p_ht, unsigned int i_size);
00445 
00468 void ght_finalize(ght_hash_table_t *p_ht);
00469 
00470 /* exported hash functions */
00471 
00484 ght_uint32_t ght_one_at_a_time_hash(ght_hash_key_t *p_key);
00485 
00496 ght_uint32_t ght_rotating_hash(ght_hash_key_t *p_key);
00497 
00508 ght_uint32_t ght_crc_hash(ght_hash_key_t *p_key);
00509 
00510 #ifdef USE_PROFILING
00511 
00515 void ght_print(ght_hash_table_t *p_ht);
00516 #endif
00517 
00518 #ifdef __cplusplus
00519 }
00520 #endif
00521 
00522 #endif /* GHT_HASH_TABLE_H */

Generated on Sun May 8 10:26:32 2005 for libghthash by  doxygen 1.4.2