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