1*a9fa9459Szrj /* An expandable hash tables datatype. 2*a9fa9459Szrj Copyright (C) 1999-2016 Free Software Foundation, Inc. 3*a9fa9459Szrj Contributed by Vladimir Makarov (vmakarov@cygnus.com). 4*a9fa9459Szrj 5*a9fa9459Szrj This program is free software; you can redistribute it and/or modify 6*a9fa9459Szrj it under the terms of the GNU General Public License as published by 7*a9fa9459Szrj the Free Software Foundation; either version 2 of the License, or 8*a9fa9459Szrj (at your option) any later version. 9*a9fa9459Szrj 10*a9fa9459Szrj This program is distributed in the hope that it will be useful, 11*a9fa9459Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of 12*a9fa9459Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13*a9fa9459Szrj GNU General Public License for more details. 14*a9fa9459Szrj 15*a9fa9459Szrj You should have received a copy of the GNU General Public License 16*a9fa9459Szrj along with this program; if not, write to the Free Software 17*a9fa9459Szrj Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 18*a9fa9459Szrj 19*a9fa9459Szrj /* This package implements basic hash table functionality. It is possible 20*a9fa9459Szrj to search for an entry, create an entry and destroy an entry. 21*a9fa9459Szrj 22*a9fa9459Szrj Elements in the table are generic pointers. 23*a9fa9459Szrj 24*a9fa9459Szrj The size of the table is not fixed; if the occupancy of the table 25*a9fa9459Szrj grows too high the hash table will be expanded. 26*a9fa9459Szrj 27*a9fa9459Szrj The abstract data implementation is based on generalized Algorithm D 28*a9fa9459Szrj from Knuth's book "The art of computer programming". Hash table is 29*a9fa9459Szrj expanded by creation of new hash table and transferring elements from 30*a9fa9459Szrj the old table to the new table. */ 31*a9fa9459Szrj 32*a9fa9459Szrj #ifndef __HASHTAB_H__ 33*a9fa9459Szrj #define __HASHTAB_H__ 34*a9fa9459Szrj 35*a9fa9459Szrj #ifdef __cplusplus 36*a9fa9459Szrj extern "C" { 37*a9fa9459Szrj #endif /* __cplusplus */ 38*a9fa9459Szrj 39*a9fa9459Szrj #include "ansidecl.h" 40*a9fa9459Szrj 41*a9fa9459Szrj /* The type for a hash code. */ 42*a9fa9459Szrj typedef unsigned int hashval_t; 43*a9fa9459Szrj 44*a9fa9459Szrj /* Callback function pointer types. */ 45*a9fa9459Szrj 46*a9fa9459Szrj /* Calculate hash of a table entry. */ 47*a9fa9459Szrj typedef hashval_t (*htab_hash) (const void *); 48*a9fa9459Szrj 49*a9fa9459Szrj /* Compare a table entry with a possible entry. The entry already in 50*a9fa9459Szrj the table always comes first, so the second element can be of a 51*a9fa9459Szrj different type (but in this case htab_find and htab_find_slot 52*a9fa9459Szrj cannot be used; instead the variants that accept a hash value 53*a9fa9459Szrj must be used). */ 54*a9fa9459Szrj typedef int (*htab_eq) (const void *, const void *); 55*a9fa9459Szrj 56*a9fa9459Szrj /* Cleanup function called whenever a live element is removed from 57*a9fa9459Szrj the hash table. */ 58*a9fa9459Szrj typedef void (*htab_del) (void *); 59*a9fa9459Szrj 60*a9fa9459Szrj /* Function called by htab_traverse for each live element. The first 61*a9fa9459Szrj arg is the slot of the element (which can be passed to htab_clear_slot 62*a9fa9459Szrj if desired), the second arg is the auxiliary pointer handed to 63*a9fa9459Szrj htab_traverse. Return 1 to continue scan, 0 to stop. */ 64*a9fa9459Szrj typedef int (*htab_trav) (void **, void *); 65*a9fa9459Szrj 66*a9fa9459Szrj /* Memory-allocation function, with the same functionality as calloc(). 67*a9fa9459Szrj Iff it returns NULL, the hash table implementation will pass an error 68*a9fa9459Szrj code back to the user, so if your code doesn't handle errors, 69*a9fa9459Szrj best if you use xcalloc instead. */ 70*a9fa9459Szrj typedef void *(*htab_alloc) (size_t, size_t); 71*a9fa9459Szrj 72*a9fa9459Szrj /* We also need a free() routine. */ 73*a9fa9459Szrj typedef void (*htab_free) (void *); 74*a9fa9459Szrj 75*a9fa9459Szrj /* Memory allocation and deallocation; variants which take an extra 76*a9fa9459Szrj argument. */ 77*a9fa9459Szrj typedef void *(*htab_alloc_with_arg) (void *, size_t, size_t); 78*a9fa9459Szrj typedef void (*htab_free_with_arg) (void *, void *); 79*a9fa9459Szrj 80*a9fa9459Szrj /* This macro defines reserved value for empty table entry. */ 81*a9fa9459Szrj 82*a9fa9459Szrj #define HTAB_EMPTY_ENTRY ((PTR) 0) 83*a9fa9459Szrj 84*a9fa9459Szrj /* This macro defines reserved value for table entry which contained 85*a9fa9459Szrj a deleted element. */ 86*a9fa9459Szrj 87*a9fa9459Szrj #define HTAB_DELETED_ENTRY ((PTR) 1) 88*a9fa9459Szrj 89*a9fa9459Szrj /* Hash tables are of the following type. The structure 90*a9fa9459Szrj (implementation) of this type is not needed for using the hash 91*a9fa9459Szrj tables. All work with hash table should be executed only through 92*a9fa9459Szrj functions mentioned below. The size of this structure is subject to 93*a9fa9459Szrj change. */ 94*a9fa9459Szrj 95*a9fa9459Szrj struct htab { 96*a9fa9459Szrj /* Pointer to hash function. */ 97*a9fa9459Szrj htab_hash hash_f; 98*a9fa9459Szrj 99*a9fa9459Szrj /* Pointer to comparison function. */ 100*a9fa9459Szrj htab_eq eq_f; 101*a9fa9459Szrj 102*a9fa9459Szrj /* Pointer to cleanup function. */ 103*a9fa9459Szrj htab_del del_f; 104*a9fa9459Szrj 105*a9fa9459Szrj /* Table itself. */ 106*a9fa9459Szrj void **entries; 107*a9fa9459Szrj 108*a9fa9459Szrj /* Current size (in entries) of the hash table. */ 109*a9fa9459Szrj size_t size; 110*a9fa9459Szrj 111*a9fa9459Szrj /* Current number of elements including also deleted elements. */ 112*a9fa9459Szrj size_t n_elements; 113*a9fa9459Szrj 114*a9fa9459Szrj /* Current number of deleted elements in the table. */ 115*a9fa9459Szrj size_t n_deleted; 116*a9fa9459Szrj 117*a9fa9459Szrj /* The following member is used for debugging. Its value is number 118*a9fa9459Szrj of all calls of `htab_find_slot' for the hash table. */ 119*a9fa9459Szrj unsigned int searches; 120*a9fa9459Szrj 121*a9fa9459Szrj /* The following member is used for debugging. Its value is number 122*a9fa9459Szrj of collisions fixed for time of work with the hash table. */ 123*a9fa9459Szrj unsigned int collisions; 124*a9fa9459Szrj 125*a9fa9459Szrj /* Pointers to allocate/free functions. */ 126*a9fa9459Szrj htab_alloc alloc_f; 127*a9fa9459Szrj htab_free free_f; 128*a9fa9459Szrj 129*a9fa9459Szrj /* Alternate allocate/free functions, which take an extra argument. */ 130*a9fa9459Szrj void *alloc_arg; 131*a9fa9459Szrj htab_alloc_with_arg alloc_with_arg_f; 132*a9fa9459Szrj htab_free_with_arg free_with_arg_f; 133*a9fa9459Szrj 134*a9fa9459Szrj /* Current size (in entries) of the hash table, as an index into the 135*a9fa9459Szrj table of primes. */ 136*a9fa9459Szrj unsigned int size_prime_index; 137*a9fa9459Szrj }; 138*a9fa9459Szrj 139*a9fa9459Szrj typedef struct htab *htab_t; 140*a9fa9459Szrj 141*a9fa9459Szrj /* An enum saying whether we insert into the hash table or not. */ 142*a9fa9459Szrj enum insert_option {NO_INSERT, INSERT}; 143*a9fa9459Szrj 144*a9fa9459Szrj /* The prototypes of the package functions. */ 145*a9fa9459Szrj 146*a9fa9459Szrj extern htab_t htab_create_alloc (size_t, htab_hash, 147*a9fa9459Szrj htab_eq, htab_del, 148*a9fa9459Szrj htab_alloc, htab_free); 149*a9fa9459Szrj 150*a9fa9459Szrj extern htab_t htab_create_alloc_ex (size_t, htab_hash, 151*a9fa9459Szrj htab_eq, htab_del, 152*a9fa9459Szrj void *, htab_alloc_with_arg, 153*a9fa9459Szrj htab_free_with_arg); 154*a9fa9459Szrj 155*a9fa9459Szrj extern htab_t htab_create_typed_alloc (size_t, htab_hash, htab_eq, htab_del, 156*a9fa9459Szrj htab_alloc, htab_alloc, htab_free); 157*a9fa9459Szrj 158*a9fa9459Szrj /* Backward-compatibility functions. */ 159*a9fa9459Szrj extern htab_t htab_create (size_t, htab_hash, htab_eq, htab_del); 160*a9fa9459Szrj extern htab_t htab_try_create (size_t, htab_hash, htab_eq, htab_del); 161*a9fa9459Szrj 162*a9fa9459Szrj extern void htab_set_functions_ex (htab_t, htab_hash, 163*a9fa9459Szrj htab_eq, htab_del, 164*a9fa9459Szrj void *, htab_alloc_with_arg, 165*a9fa9459Szrj htab_free_with_arg); 166*a9fa9459Szrj 167*a9fa9459Szrj extern void htab_delete (htab_t); 168*a9fa9459Szrj extern void htab_empty (htab_t); 169*a9fa9459Szrj 170*a9fa9459Szrj extern void * htab_find (htab_t, const void *); 171*a9fa9459Szrj extern void ** htab_find_slot (htab_t, const void *, enum insert_option); 172*a9fa9459Szrj extern void * htab_find_with_hash (htab_t, const void *, hashval_t); 173*a9fa9459Szrj extern void ** htab_find_slot_with_hash (htab_t, const void *, 174*a9fa9459Szrj hashval_t, enum insert_option); 175*a9fa9459Szrj extern void htab_clear_slot (htab_t, void **); 176*a9fa9459Szrj extern void htab_remove_elt (htab_t, void *); 177*a9fa9459Szrj extern void htab_remove_elt_with_hash (htab_t, void *, hashval_t); 178*a9fa9459Szrj 179*a9fa9459Szrj extern void htab_traverse (htab_t, htab_trav, void *); 180*a9fa9459Szrj extern void htab_traverse_noresize (htab_t, htab_trav, void *); 181*a9fa9459Szrj 182*a9fa9459Szrj extern size_t htab_size (htab_t); 183*a9fa9459Szrj extern size_t htab_elements (htab_t); 184*a9fa9459Szrj extern double htab_collisions (htab_t); 185*a9fa9459Szrj 186*a9fa9459Szrj /* A hash function for pointers. */ 187*a9fa9459Szrj extern htab_hash htab_hash_pointer; 188*a9fa9459Szrj 189*a9fa9459Szrj /* An equality function for pointers. */ 190*a9fa9459Szrj extern htab_eq htab_eq_pointer; 191*a9fa9459Szrj 192*a9fa9459Szrj /* A hash function for null-terminated strings. */ 193*a9fa9459Szrj extern hashval_t htab_hash_string (const void *); 194*a9fa9459Szrj 195*a9fa9459Szrj /* An iterative hash function for arbitrary data. */ 196*a9fa9459Szrj extern hashval_t iterative_hash (const void *, size_t, hashval_t); 197*a9fa9459Szrj /* Shorthand for hashing something with an intrinsic size. */ 198*a9fa9459Szrj #define iterative_hash_object(OB,INIT) iterative_hash (&OB, sizeof (OB), INIT) 199*a9fa9459Szrj 200*a9fa9459Szrj #ifdef __cplusplus 201*a9fa9459Szrj } 202*a9fa9459Szrj #endif /* __cplusplus */ 203*a9fa9459Szrj 204*a9fa9459Szrj #endif /* __HASHTAB_H */ 205