00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00059 #ifndef GHT_HASH_TABLE_H
00060 #define GHT_HASH_TABLE_H
00061
00062 #include <stdlib.h>
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
00096
00097
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
00110
00111
00112
00113 typedef struct
00114 {
00115 int i_curr_bucket;
00116 ght_hash_entry_t *p_entry;
00117 ght_hash_entry_t *p_next;
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
00170 ght_hash_entry_t **pp_entries;
00171 int *p_nr;
00172 int i_size_mask;
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
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