hashtab.h revision 130561
160484Sobrien/* An expandable hash tables datatype. 2130561Sobrien Copyright (C) 1999, 2000, 2002, 2003 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 1760484SobrienFoundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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. */ 5177298Sobrientypedef hashval_t (*htab_hash) PARAMS ((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). */ 5860484Sobrientypedef int (*htab_eq) PARAMS ((const void *, const void *)); 5960484Sobrien 6060484Sobrien/* Cleanup function called whenever a live element is removed from 6160484Sobrien the hash table. */ 6260484Sobrientypedef void (*htab_del) PARAMS ((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. */ 6860484Sobrientypedef int (*htab_trav) PARAMS ((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. */ 74104834Sobrientypedef PTR (*htab_alloc) PARAMS ((size_t, size_t)); 75104834Sobrien 76104834Sobrien/* We also need a free() routine. */ 77104834Sobrientypedef void (*htab_free) PARAMS ((PTR)); 78104834Sobrien 79130561Sobrien/* Memory allocation and deallocation; variants which take an extra 80130561Sobrien argument. */ 81130561Sobrientypedef PTR (*htab_alloc_with_arg) PARAMS ((void *, size_t, size_t)); 82130561Sobrientypedef void (*htab_free_with_arg) PARAMS ((void *, void *)); 83130561Sobrien 8460484Sobrien/* Hash tables are of the following type. The structure 8560484Sobrien (implementation) of this type is not needed for using the hash 8660484Sobrien tables. All work with hash table should be executed only through 87130561Sobrien functions mentioned below. The size of this structure is subject to 88130561Sobrien change. */ 8960484Sobrien 90104834Sobrienstruct htab GTY(()) 9160484Sobrien{ 9260484Sobrien /* Pointer to hash function. */ 9360484Sobrien htab_hash hash_f; 9460484Sobrien 9560484Sobrien /* Pointer to comparison function. */ 9660484Sobrien htab_eq eq_f; 9760484Sobrien 9860484Sobrien /* Pointer to cleanup function. */ 9960484Sobrien htab_del del_f; 10060484Sobrien 10160484Sobrien /* Table itself. */ 102104834Sobrien PTR * GTY ((use_param (""), length ("%h.size"))) entries; 10360484Sobrien 10460484Sobrien /* Current size (in entries) of the hash table */ 10560484Sobrien size_t size; 10660484Sobrien 10760484Sobrien /* Current number of elements including also deleted elements */ 10860484Sobrien size_t n_elements; 10960484Sobrien 11060484Sobrien /* Current number of deleted elements in the table */ 11160484Sobrien size_t n_deleted; 11260484Sobrien 11360484Sobrien /* The following member is used for debugging. Its value is number 11460484Sobrien of all calls of `htab_find_slot' for the hash table. */ 11560484Sobrien unsigned int searches; 11660484Sobrien 11760484Sobrien /* The following member is used for debugging. Its value is number 11860484Sobrien of collisions fixed for time of work with the hash table. */ 11960484Sobrien unsigned int collisions; 12077298Sobrien 121104834Sobrien /* Pointers to allocate/free functions. */ 122104834Sobrien htab_alloc alloc_f; 123104834Sobrien htab_free free_f; 124130561Sobrien 125130561Sobrien /* Alternate allocate/free functions, which take an extra argument. */ 126130561Sobrien PTR GTY((skip (""))) alloc_arg; 127130561Sobrien htab_alloc_with_arg alloc_with_arg_f; 128130561Sobrien htab_free_with_arg free_with_arg_f; 12960484Sobrien}; 13060484Sobrien 13160484Sobrientypedef struct htab *htab_t; 13260484Sobrien 13377298Sobrien/* An enum saying whether we insert into the hash table or not. */ 13477298Sobrienenum insert_option {NO_INSERT, INSERT}; 13577298Sobrien 13660484Sobrien/* The prototypes of the package functions. */ 13760484Sobrien 138104834Sobrienextern htab_t htab_create_alloc PARAMS ((size_t, htab_hash, 139104834Sobrien htab_eq, htab_del, 140104834Sobrien htab_alloc, htab_free)); 14177298Sobrien 142130561Sobrienextern htab_t htab_create_alloc_ex PARAMS ((size_t, htab_hash, 143130561Sobrien htab_eq, htab_del, 144130561Sobrien PTR, htab_alloc_with_arg, 145130561Sobrien htab_free_with_arg)); 146130561Sobrien 147104834Sobrien/* Backward-compatibility functions. */ 148104834Sobrienextern htab_t htab_create PARAMS ((size_t, htab_hash, htab_eq, htab_del)); 149104834Sobrienextern htab_t htab_try_create PARAMS ((size_t, htab_hash, htab_eq, htab_del)); 150104834Sobrien 151130561Sobrienextern void htab_set_functions_ex PARAMS ((htab_t, htab_hash, 152130561Sobrien htab_eq, htab_del, 153130561Sobrien PTR, htab_alloc_with_arg, 154130561Sobrien htab_free_with_arg)); 155130561Sobrien 15660484Sobrienextern void htab_delete PARAMS ((htab_t)); 15760484Sobrienextern void htab_empty PARAMS ((htab_t)); 15860484Sobrien 15977298Sobrienextern PTR htab_find PARAMS ((htab_t, const void *)); 16077298Sobrienextern PTR *htab_find_slot PARAMS ((htab_t, const void *, 16177298Sobrien enum insert_option)); 16277298Sobrienextern PTR htab_find_with_hash PARAMS ((htab_t, const void *, 16377298Sobrien hashval_t)); 16477298Sobrienextern PTR *htab_find_slot_with_hash PARAMS ((htab_t, const void *, 16577298Sobrien hashval_t, 16677298Sobrien enum insert_option)); 16760484Sobrienextern void htab_clear_slot PARAMS ((htab_t, void **)); 16860484Sobrienextern void htab_remove_elt PARAMS ((htab_t, void *)); 16960484Sobrien 17060484Sobrienextern void htab_traverse PARAMS ((htab_t, htab_trav, void *)); 171130561Sobrienextern void htab_traverse_noresize PARAMS ((htab_t, htab_trav, void *)); 17260484Sobrien 17360484Sobrienextern size_t htab_size PARAMS ((htab_t)); 17460484Sobrienextern size_t htab_elements PARAMS ((htab_t)); 17560484Sobrienextern double htab_collisions PARAMS ((htab_t)); 17660484Sobrien 17777298Sobrien/* A hash function for pointers. */ 17877298Sobrienextern htab_hash htab_hash_pointer; 17977298Sobrien 18077298Sobrien/* An equality function for pointers. */ 18177298Sobrienextern htab_eq htab_eq_pointer; 18277298Sobrien 18389857Sobrien/* A hash function for null-terminated strings. */ 18489857Sobrienextern hashval_t htab_hash_string PARAMS ((const PTR)); 18589857Sobrien 186130561Sobrien/* An iterative hash function for arbitrary data. */ 187130561Sobrienextern hashval_t iterative_hash PARAMS ((const PTR, size_t, hashval_t)); 188130561Sobrien/* Shorthand for hashing something with an intrinsic size. */ 189130561Sobrien#define iterative_hash_object(OB,INIT) iterative_hash (&OB, sizeof (OB), INIT) 190130561Sobrien 19160484Sobrien#ifdef __cplusplus 19260484Sobrien} 19360484Sobrien#endif /* __cplusplus */ 19460484Sobrien 19560484Sobrien#endif /* __HASHTAB_H */ 196