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