160484Sobrien/* An expandable hash tables datatype. 2218822Sdim Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc. 360484Sobrien Contributed by Vladimir Makarov (vmakarov@cygnus.com). 460484Sobrien 560484SobrienThis program is free software; you can redistribute it and/or modify 660484Sobrienit under the terms of the GNU General Public License as published by 760484Sobrienthe Free Software Foundation; either version 2 of the License, or 860484Sobrien(at your option) any later version. 960484Sobrien 1060484SobrienThis program is distributed in the hope that it will be useful, 1160484Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1260484SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1360484SobrienGNU General Public License for more details. 1460484Sobrien 1560484SobrienYou should have received a copy of the GNU General Public License 1660484Sobrienalong with this program; if not, write to the Free Software 17218822SdimFoundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 1860484Sobrien 1960484Sobrien/* This package implements basic hash table functionality. It is possible 2060484Sobrien to search for an entry, create an entry and destroy an entry. 2160484Sobrien 2260484Sobrien Elements in the table are generic pointers. 2360484Sobrien 2460484Sobrien The size of the table is not fixed; if the occupancy of the table 2560484Sobrien grows too high the hash table will be expanded. 2660484Sobrien 2760484Sobrien The abstract data implementation is based on generalized Algorithm D 2860484Sobrien from Knuth's book "The art of computer programming". Hash table is 2960484Sobrien expanded by creation of new hash table and transferring elements from 3060484Sobrien the old table to the new table. */ 3160484Sobrien 3260484Sobrien#ifndef __HASHTAB_H__ 3360484Sobrien#define __HASHTAB_H__ 3460484Sobrien 3560484Sobrien#ifdef __cplusplus 3660484Sobrienextern "C" { 3760484Sobrien#endif /* __cplusplus */ 3860484Sobrien 39104834Sobrien#include "ansidecl.h" 4060484Sobrien 41104834Sobrien#ifndef GTY 42104834Sobrien#define GTY(X) 43104834Sobrien#endif 44104834Sobrien 4577298Sobrien/* The type for a hash code. */ 4677298Sobrientypedef unsigned int hashval_t; 4777298Sobrien 4860484Sobrien/* Callback function pointer types. */ 4960484Sobrien 5060484Sobrien/* Calculate hash of a table entry. */ 51218822Sdimtypedef hashval_t (*htab_hash) (const void *); 5260484Sobrien 5360484Sobrien/* Compare a table entry with a possible entry. The entry already in 5460484Sobrien the table always comes first, so the second element can be of a 5560484Sobrien different type (but in this case htab_find and htab_find_slot 5660484Sobrien cannot be used; instead the variants that accept a hash value 5760484Sobrien must be used). */ 58218822Sdimtypedef int (*htab_eq) (const void *, const void *); 5960484Sobrien 6060484Sobrien/* Cleanup function called whenever a live element is removed from 6160484Sobrien the hash table. */ 62218822Sdimtypedef void (*htab_del) (void *); 6360484Sobrien 6460484Sobrien/* Function called by htab_traverse for each live element. The first 6560484Sobrien arg is the slot of the element (which can be passed to htab_clear_slot 6660484Sobrien if desired), the second arg is the auxiliary pointer handed to 6760484Sobrien htab_traverse. Return 1 to continue scan, 0 to stop. */ 68218822Sdimtypedef int (*htab_trav) (void **, void *); 6960484Sobrien 70104834Sobrien/* Memory-allocation function, with the same functionality as calloc(). 71104834Sobrien Iff it returns NULL, the hash table implementation will pass an error 72104834Sobrien code back to the user, so if your code doesn't handle errors, 73104834Sobrien best if you use xcalloc instead. */ 74218822Sdimtypedef void *(*htab_alloc) (size_t, size_t); 75104834Sobrien 76104834Sobrien/* We also need a free() routine. */ 77218822Sdimtypedef void (*htab_free) (void *); 78104834Sobrien 79130561Sobrien/* Memory allocation and deallocation; variants which take an extra 80130561Sobrien argument. */ 81218822Sdimtypedef void *(*htab_alloc_with_arg) (void *, size_t, size_t); 82218822Sdimtypedef void (*htab_free_with_arg) (void *, void *); 83130561Sobrien 84218822Sdim/* This macro defines reserved value for empty table entry. */ 85218822Sdim 86218822Sdim#define HTAB_EMPTY_ENTRY ((PTR) 0) 87218822Sdim 88218822Sdim/* This macro defines reserved value for table entry which contained 89218822Sdim a deleted element. */ 90218822Sdim 91218822Sdim#define HTAB_DELETED_ENTRY ((PTR) 1) 92218822Sdim 9360484Sobrien/* Hash tables are of the following type. The structure 9460484Sobrien (implementation) of this type is not needed for using the hash 9560484Sobrien tables. All work with hash table should be executed only through 96130561Sobrien functions mentioned below. The size of this structure is subject to 97130561Sobrien change. */ 9860484Sobrien 99104834Sobrienstruct htab GTY(()) 10060484Sobrien{ 10160484Sobrien /* Pointer to hash function. */ 10260484Sobrien htab_hash hash_f; 10360484Sobrien 10460484Sobrien /* Pointer to comparison function. */ 10560484Sobrien htab_eq eq_f; 10660484Sobrien 10760484Sobrien /* Pointer to cleanup function. */ 10860484Sobrien htab_del del_f; 10960484Sobrien 11060484Sobrien /* Table itself. */ 111218822Sdim void ** GTY ((use_param, length ("%h.size"))) entries; 11260484Sobrien 113218822Sdim /* Current size (in entries) of the hash table. */ 11460484Sobrien size_t size; 11560484Sobrien 116218822Sdim /* Current number of elements including also deleted elements. */ 11760484Sobrien size_t n_elements; 11860484Sobrien 119218822Sdim /* Current number of deleted elements in the table. */ 12060484Sobrien size_t n_deleted; 12160484Sobrien 12260484Sobrien /* The following member is used for debugging. Its value is number 12360484Sobrien of all calls of `htab_find_slot' for the hash table. */ 12460484Sobrien unsigned int searches; 12560484Sobrien 12660484Sobrien /* The following member is used for debugging. Its value is number 12760484Sobrien of collisions fixed for time of work with the hash table. */ 12860484Sobrien unsigned int collisions; 12977298Sobrien 130104834Sobrien /* Pointers to allocate/free functions. */ 131104834Sobrien htab_alloc alloc_f; 132104834Sobrien htab_free free_f; 133130561Sobrien 134130561Sobrien /* Alternate allocate/free functions, which take an extra argument. */ 135218822Sdim void * GTY((skip)) alloc_arg; 136130561Sobrien htab_alloc_with_arg alloc_with_arg_f; 137130561Sobrien htab_free_with_arg free_with_arg_f; 138218822Sdim 139218822Sdim /* Current size (in entries) of the hash table, as an index into the 140218822Sdim table of primes. */ 141218822Sdim unsigned int size_prime_index; 14260484Sobrien}; 14360484Sobrien 14460484Sobrientypedef struct htab *htab_t; 14560484Sobrien 14677298Sobrien/* An enum saying whether we insert into the hash table or not. */ 14777298Sobrienenum insert_option {NO_INSERT, INSERT}; 14877298Sobrien 14960484Sobrien/* The prototypes of the package functions. */ 15060484Sobrien 151218822Sdimextern htab_t htab_create_alloc (size_t, htab_hash, 152218822Sdim htab_eq, htab_del, 153218822Sdim htab_alloc, htab_free); 15477298Sobrien 155218822Sdimextern htab_t htab_create_alloc_ex (size_t, htab_hash, 156218822Sdim htab_eq, htab_del, 157218822Sdim void *, htab_alloc_with_arg, 158218822Sdim htab_free_with_arg); 159130561Sobrien 160104834Sobrien/* Backward-compatibility functions. */ 161218822Sdimextern htab_t htab_create (size_t, htab_hash, htab_eq, htab_del); 162218822Sdimextern htab_t htab_try_create (size_t, htab_hash, htab_eq, htab_del); 163104834Sobrien 164218822Sdimextern void htab_set_functions_ex (htab_t, htab_hash, 165218822Sdim htab_eq, htab_del, 166218822Sdim void *, htab_alloc_with_arg, 167218822Sdim htab_free_with_arg); 168130561Sobrien 169218822Sdimextern void htab_delete (htab_t); 170218822Sdimextern void htab_empty (htab_t); 17160484Sobrien 172218822Sdimextern void * htab_find (htab_t, const void *); 173218822Sdimextern void ** htab_find_slot (htab_t, const void *, enum insert_option); 174218822Sdimextern void * htab_find_with_hash (htab_t, const void *, hashval_t); 175218822Sdimextern void ** htab_find_slot_with_hash (htab_t, const void *, 176218822Sdim hashval_t, enum insert_option); 177218822Sdimextern void htab_clear_slot (htab_t, void **); 178218822Sdimextern void htab_remove_elt (htab_t, void *); 179218822Sdimextern void htab_remove_elt_with_hash (htab_t, void *, hashval_t); 18060484Sobrien 181218822Sdimextern void htab_traverse (htab_t, htab_trav, void *); 182218822Sdimextern void htab_traverse_noresize (htab_t, htab_trav, void *); 18360484Sobrien 184218822Sdimextern size_t htab_size (htab_t); 185218822Sdimextern size_t htab_elements (htab_t); 186218822Sdimextern double htab_collisions (htab_t); 18760484Sobrien 18877298Sobrien/* A hash function for pointers. */ 18977298Sobrienextern htab_hash htab_hash_pointer; 19077298Sobrien 19177298Sobrien/* An equality function for pointers. */ 19277298Sobrienextern htab_eq htab_eq_pointer; 19377298Sobrien 19489857Sobrien/* A hash function for null-terminated strings. */ 195218822Sdimextern hashval_t htab_hash_string (const void *); 19689857Sobrien 197130561Sobrien/* An iterative hash function for arbitrary data. */ 198218822Sdimextern hashval_t iterative_hash (const void *, size_t, hashval_t); 199130561Sobrien/* Shorthand for hashing something with an intrinsic size. */ 200130561Sobrien#define iterative_hash_object(OB,INIT) iterative_hash (&OB, sizeof (OB), INIT) 201130561Sobrien 20260484Sobrien#ifdef __cplusplus 20360484Sobrien} 20460484Sobrien#endif /* __cplusplus */ 20560484Sobrien 20660484Sobrien#endif /* __HASHTAB_H */ 207