1169695Skan/* An expandable hash tables datatype. 2169695Skan Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc. 3169695Skan Contributed by Vladimir Makarov (vmakarov@cygnus.com). 4169695Skan 5169695SkanThis program is free software; you can redistribute it and/or modify 6169695Skanit under the terms of the GNU General Public License as published by 7169695Skanthe Free Software Foundation; either version 2 of the License, or 8169695Skan(at your option) any later version. 9169695Skan 10169695SkanThis program is distributed in the hope that it will be useful, 11169695Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 12169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13169695SkanGNU General Public License for more details. 14169695Skan 15169695SkanYou should have received a copy of the GNU General Public License 16169695Skanalong with this program; if not, write to the Free Software 17169695SkanFoundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 18169695Skan 19169695Skan/* This package implements basic hash table functionality. It is possible 20169695Skan to search for an entry, create an entry and destroy an entry. 21169695Skan 22169695Skan Elements in the table are generic pointers. 23169695Skan 24169695Skan The size of the table is not fixed; if the occupancy of the table 25169695Skan grows too high the hash table will be expanded. 26169695Skan 27169695Skan The abstract data implementation is based on generalized Algorithm D 28169695Skan from Knuth's book "The art of computer programming". Hash table is 29169695Skan expanded by creation of new hash table and transferring elements from 30169695Skan the old table to the new table. */ 31169695Skan 32169695Skan#ifndef __HASHTAB_H__ 33169695Skan#define __HASHTAB_H__ 34169695Skan 35169695Skan#ifdef __cplusplus 36169695Skanextern "C" { 37169695Skan#endif /* __cplusplus */ 38169695Skan 39169695Skan#include "ansidecl.h" 40169695Skan 41169695Skan#ifndef GTY 42169695Skan#define GTY(X) 43169695Skan#endif 44169695Skan 45169695Skan/* The type for a hash code. */ 46169695Skantypedef unsigned int hashval_t; 47169695Skan 48169695Skan/* Callback function pointer types. */ 49169695Skan 50169695Skan/* Calculate hash of a table entry. */ 51169695Skantypedef hashval_t (*htab_hash) (const void *); 52169695Skan 53169695Skan/* Compare a table entry with a possible entry. The entry already in 54169695Skan the table always comes first, so the second element can be of a 55169695Skan different type (but in this case htab_find and htab_find_slot 56169695Skan cannot be used; instead the variants that accept a hash value 57169695Skan must be used). */ 58169695Skantypedef int (*htab_eq) (const void *, const void *); 59169695Skan 60169695Skan/* Cleanup function called whenever a live element is removed from 61169695Skan the hash table. */ 62169695Skantypedef void (*htab_del) (void *); 63169695Skan 64169695Skan/* Function called by htab_traverse for each live element. The first 65169695Skan arg is the slot of the element (which can be passed to htab_clear_slot 66169695Skan if desired), the second arg is the auxiliary pointer handed to 67169695Skan htab_traverse. Return 1 to continue scan, 0 to stop. */ 68169695Skantypedef int (*htab_trav) (void **, void *); 69169695Skan 70169695Skan/* Memory-allocation function, with the same functionality as calloc(). 71169695Skan Iff it returns NULL, the hash table implementation will pass an error 72169695Skan code back to the user, so if your code doesn't handle errors, 73169695Skan best if you use xcalloc instead. */ 74169695Skantypedef void *(*htab_alloc) (size_t, size_t); 75169695Skan 76169695Skan/* We also need a free() routine. */ 77169695Skantypedef void (*htab_free) (void *); 78169695Skan 79169695Skan/* Memory allocation and deallocation; variants which take an extra 80169695Skan argument. */ 81169695Skantypedef void *(*htab_alloc_with_arg) (void *, size_t, size_t); 82169695Skantypedef void (*htab_free_with_arg) (void *, void *); 83169695Skan 84169695Skan/* This macro defines reserved value for empty table entry. */ 85169695Skan 86169695Skan#define HTAB_EMPTY_ENTRY ((PTR) 0) 87169695Skan 88169695Skan/* This macro defines reserved value for table entry which contained 89169695Skan a deleted element. */ 90169695Skan 91169695Skan#define HTAB_DELETED_ENTRY ((PTR) 1) 92169695Skan 93169695Skan/* Hash tables are of the following type. The structure 94169695Skan (implementation) of this type is not needed for using the hash 95169695Skan tables. All work with hash table should be executed only through 96169695Skan functions mentioned below. The size of this structure is subject to 97169695Skan change. */ 98169695Skan 99169695Skanstruct htab GTY(()) 100169695Skan{ 101169695Skan /* Pointer to hash function. */ 102169695Skan htab_hash hash_f; 103169695Skan 104169695Skan /* Pointer to comparison function. */ 105169695Skan htab_eq eq_f; 106169695Skan 107169695Skan /* Pointer to cleanup function. */ 108169695Skan htab_del del_f; 109169695Skan 110169695Skan /* Table itself. */ 111169695Skan void ** GTY ((use_param, length ("%h.size"))) entries; 112169695Skan 113169695Skan /* Current size (in entries) of the hash table. */ 114169695Skan size_t size; 115169695Skan 116169695Skan /* Current number of elements including also deleted elements. */ 117169695Skan size_t n_elements; 118169695Skan 119169695Skan /* Current number of deleted elements in the table. */ 120169695Skan size_t n_deleted; 121169695Skan 122169695Skan /* The following member is used for debugging. Its value is number 123169695Skan of all calls of `htab_find_slot' for the hash table. */ 124169695Skan unsigned int searches; 125169695Skan 126169695Skan /* The following member is used for debugging. Its value is number 127169695Skan of collisions fixed for time of work with the hash table. */ 128169695Skan unsigned int collisions; 129169695Skan 130169695Skan /* Pointers to allocate/free functions. */ 131169695Skan htab_alloc alloc_f; 132169695Skan htab_free free_f; 133169695Skan 134169695Skan /* Alternate allocate/free functions, which take an extra argument. */ 135169695Skan void * GTY((skip)) alloc_arg; 136169695Skan htab_alloc_with_arg alloc_with_arg_f; 137169695Skan htab_free_with_arg free_with_arg_f; 138169695Skan 139169695Skan /* Current size (in entries) of the hash table, as an index into the 140169695Skan table of primes. */ 141169695Skan unsigned int size_prime_index; 142169695Skan}; 143169695Skan 144169695Skantypedef struct htab *htab_t; 145169695Skan 146169695Skan/* An enum saying whether we insert into the hash table or not. */ 147169695Skanenum insert_option {NO_INSERT, INSERT}; 148169695Skan 149169695Skan/* The prototypes of the package functions. */ 150169695Skan 151169695Skanextern htab_t htab_create_alloc (size_t, htab_hash, 152169695Skan htab_eq, htab_del, 153169695Skan htab_alloc, htab_free); 154169695Skan 155169695Skanextern htab_t htab_create_alloc_ex (size_t, htab_hash, 156169695Skan htab_eq, htab_del, 157169695Skan void *, htab_alloc_with_arg, 158169695Skan htab_free_with_arg); 159169695Skan 160169695Skan/* Backward-compatibility functions. */ 161169695Skanextern htab_t htab_create (size_t, htab_hash, htab_eq, htab_del); 162169695Skanextern htab_t htab_try_create (size_t, htab_hash, htab_eq, htab_del); 163169695Skan 164169695Skanextern void htab_set_functions_ex (htab_t, htab_hash, 165169695Skan htab_eq, htab_del, 166169695Skan void *, htab_alloc_with_arg, 167169695Skan htab_free_with_arg); 168169695Skan 169169695Skanextern void htab_delete (htab_t); 170169695Skanextern void htab_empty (htab_t); 171169695Skan 172169695Skanextern void * htab_find (htab_t, const void *); 173169695Skanextern void ** htab_find_slot (htab_t, const void *, enum insert_option); 174169695Skanextern void * htab_find_with_hash (htab_t, const void *, hashval_t); 175169695Skanextern void ** htab_find_slot_with_hash (htab_t, const void *, 176169695Skan hashval_t, enum insert_option); 177169695Skanextern void htab_clear_slot (htab_t, void **); 178169695Skanextern void htab_remove_elt (htab_t, void *); 179169695Skanextern void htab_remove_elt_with_hash (htab_t, void *, hashval_t); 180169695Skan 181169695Skanextern void htab_traverse (htab_t, htab_trav, void *); 182169695Skanextern void htab_traverse_noresize (htab_t, htab_trav, void *); 183169695Skan 184169695Skanextern size_t htab_size (htab_t); 185169695Skanextern size_t htab_elements (htab_t); 186169695Skanextern double htab_collisions (htab_t); 187169695Skan 188169695Skan/* A hash function for pointers. */ 189169695Skanextern htab_hash htab_hash_pointer; 190169695Skan 191169695Skan/* An equality function for pointers. */ 192169695Skanextern htab_eq htab_eq_pointer; 193169695Skan 194169695Skan/* A hash function for null-terminated strings. */ 195169695Skanextern hashval_t htab_hash_string (const void *); 196169695Skan 197169695Skan/* An iterative hash function for arbitrary data. */ 198169695Skanextern hashval_t iterative_hash (const void *, size_t, hashval_t); 199169695Skan/* Shorthand for hashing something with an intrinsic size. */ 200169695Skan#define iterative_hash_object(OB,INIT) iterative_hash (&OB, sizeof (OB), INIT) 201169695Skan 202169695Skan#ifdef __cplusplus 203169695Skan} 204169695Skan#endif /* __cplusplus */ 205169695Skan 206169695Skan#endif /* __HASHTAB_H */ 207