| 1 |
/* hash - hashing table processing. |
| 2 |
Copyright (C) 1998-1999, 2001, 2003, 2009-2024 Free Software Foundation, |
| 3 |
Inc. |
| 4 |
Written by Jim Meyering <[email protected]>, 1998. |
| 5 |
|
| 6 |
This file is free software: you can redistribute it and/or modify |
| 7 |
it under the terms of the GNU Lesser General Public License as |
| 8 |
published by the Free Software Foundation; either version 2.1 of the |
| 9 |
License, or (at your option) any later version. |
| 10 |
|
| 11 |
This file is distributed in the hope that it will be useful, |
| 12 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 |
GNU Lesser General Public License for more details. |
| 15 |
|
| 16 |
You should have received a copy of the GNU Lesser General Public License |
| 17 |
along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
| 18 |
|
| 19 |
/* A generic hash table package. */ |
| 20 |
|
| 21 |
/* Make sure USE_OBSTACK is defined to 1 if you want the allocator to use |
| 22 |
obstacks instead of malloc, and recompile 'hash.c' with same setting. */ |
| 23 |
|
| 24 |
#ifndef HASH_H_ |
| 25 |
# define HASH_H_ |
| 26 |
|
| 27 |
/* This file uses _GL_ATTRIBUTE_DEALLOC, _GL_ATTRIBUTE_DEPRECATED, |
| 28 |
_GL_ATTRIBUTE_MALLOC, _GL_ATTRIBUTE_NODISCARD, _GL_ATTRIBUTE_PURE, |
| 29 |
_GL_ATTRIBUTE_RETURNS_NONNULL. */ |
| 30 |
#if !_GL_CONFIG_H_INCLUDED |
| 31 |
#error "Please include config.h first." |
| 32 |
#endif |
| 33 |
|
| 34 |
# include <stdio.h> |
| 35 |
|
| 36 |
# ifdef __cplusplus |
| 37 |
extern "C" { |
| 38 |
# endif |
| 39 |
|
| 40 |
struct hash_tuning |
| 41 |
{ |
| 42 |
/* This structure is mainly used for 'hash_initialize', see the block |
| 43 |
documentation of 'hash_reset_tuning' for more complete comments. */ |
| 44 |
|
| 45 |
float shrink_threshold; /* ratio of used buckets to trigger a shrink */ |
| 46 |
float shrink_factor; /* ratio of new smaller size to original size */ |
| 47 |
float growth_threshold; /* ratio of used buckets to trigger a growth */ |
| 48 |
float growth_factor; /* ratio of new bigger size to original size */ |
| 49 |
bool is_n_buckets; /* if CANDIDATE really means table size */ |
| 50 |
}; |
| 51 |
|
| 52 |
typedef struct hash_tuning Hash_tuning; |
| 53 |
|
| 54 |
struct hash_table; |
| 55 |
|
| 56 |
typedef struct hash_table Hash_table; |
| 57 |
|
| 58 |
/* |
| 59 |
* Information and lookup. |
| 60 |
*/ |
| 61 |
|
| 62 |
/* The following few functions provide information about the overall hash |
| 63 |
table organization: the number of entries, number of buckets and maximum |
| 64 |
length of buckets. */ |
| 65 |
|
| 66 |
/* Return the number of buckets in the hash table. The table size, the total |
| 67 |
number of buckets (used plus unused), or the maximum number of slots, are |
| 68 |
the same quantity. */ |
| 69 |
extern size_t hash_get_n_buckets (const Hash_table *table) |
| 70 |
_GL_ATTRIBUTE_PURE; |
| 71 |
|
| 72 |
/* Return the number of slots in use (non-empty buckets). */ |
| 73 |
extern size_t hash_get_n_buckets_used (const Hash_table *table) |
| 74 |
_GL_ATTRIBUTE_PURE; |
| 75 |
|
| 76 |
/* Return the number of active entries. */ |
| 77 |
extern size_t hash_get_n_entries (const Hash_table *table) |
| 78 |
_GL_ATTRIBUTE_PURE; |
| 79 |
|
| 80 |
/* Return the length of the longest chain (bucket). */ |
| 81 |
extern size_t hash_get_max_bucket_length (const Hash_table *table) |
| 82 |
_GL_ATTRIBUTE_PURE; |
| 83 |
|
| 84 |
/* Do a mild validation of a hash table, by traversing it and checking two |
| 85 |
statistics. */ |
| 86 |
extern bool hash_table_ok (const Hash_table *table) |
| 87 |
_GL_ATTRIBUTE_PURE; |
| 88 |
|
| 89 |
extern void hash_print_statistics (const Hash_table *table, FILE *stream); |
| 90 |
|
| 91 |
/* If ENTRY matches an entry already in the hash table, return the |
| 92 |
entry from the table. Otherwise, return NULL. */ |
| 93 |
extern void *hash_lookup (const Hash_table *table, const void *entry); |
| 94 |
|
| 95 |
/* |
| 96 |
* Walking. |
| 97 |
*/ |
| 98 |
|
| 99 |
/* The functions in this page traverse the hash table and process the |
| 100 |
contained entries. For the traversal to work properly, the hash table |
| 101 |
should not be resized nor modified while any particular entry is being |
| 102 |
processed. In particular, entries should not be added, and an entry |
| 103 |
may be removed only if there is no shrink threshold and the entry being |
| 104 |
removed has already been passed to hash_get_next. */ |
| 105 |
|
| 106 |
/* Return the first data in the table, or NULL if the table is empty. */ |
| 107 |
extern void *hash_get_first (const Hash_table *table) |
| 108 |
_GL_ATTRIBUTE_PURE; |
| 109 |
|
| 110 |
/* Return the user data for the entry following ENTRY, where ENTRY has been |
| 111 |
returned by a previous call to either 'hash_get_first' or 'hash_get_next'. |
| 112 |
Return NULL if there are no more entries. */ |
| 113 |
extern void *hash_get_next (const Hash_table *table, const void *entry); |
| 114 |
|
| 115 |
/* Fill BUFFER with pointers to active user entries in the hash table, then |
| 116 |
return the number of pointers copied. Do not copy more than BUFFER_SIZE |
| 117 |
pointers. */ |
| 118 |
extern size_t hash_get_entries (const Hash_table *table, void **buffer, |
| 119 |
size_t buffer_size); |
| 120 |
|
| 121 |
typedef bool (*Hash_processor) (void *entry, void *processor_data); |
| 122 |
|
| 123 |
/* Call a PROCESSOR function for each entry of a hash table, and return the |
| 124 |
number of entries for which the processor function returned success. A |
| 125 |
pointer to some PROCESSOR_DATA which will be made available to each call to |
| 126 |
the processor function. The PROCESSOR accepts two arguments: the first is |
| 127 |
the user entry being walked into, the second is the value of PROCESSOR_DATA |
| 128 |
as received. The walking continue for as long as the PROCESSOR function |
| 129 |
returns nonzero. When it returns zero, the walking is interrupted. */ |
| 130 |
extern size_t hash_do_for_each (const Hash_table *table, |
| 131 |
Hash_processor processor, void *processor_data); |
| 132 |
|
| 133 |
/* |
| 134 |
* Allocation and clean-up. |
| 135 |
*/ |
| 136 |
|
| 137 |
/* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1. |
| 138 |
This is a convenience routine for constructing other hashing functions. */ |
| 139 |
extern size_t hash_string (const char *string, size_t n_buckets) |
| 140 |
_GL_ATTRIBUTE_PURE; |
| 141 |
|
| 142 |
extern void hash_reset_tuning (Hash_tuning *tuning); |
| 143 |
|
| 144 |
typedef size_t (*Hash_hasher) (const void *entry, size_t table_size); |
| 145 |
typedef bool (*Hash_comparator) (const void *entry1, const void *entry2); |
| 146 |
typedef void (*Hash_data_freer) (void *entry); |
| 147 |
|
| 148 |
/* Reclaim all storage associated with a hash table. If a data_freer |
| 149 |
function has been supplied by the user when the hash table was created, |
| 150 |
this function applies it to the data of each entry before freeing that |
| 151 |
entry. This function preserves errno, like 'free'. */ |
| 152 |
extern void hash_free (Hash_table *table); |
| 153 |
|
| 154 |
/* Allocate and return a new hash table, or NULL upon failure. The initial |
| 155 |
number of buckets is automatically selected so as to _guarantee_ that you |
| 156 |
may insert at least CANDIDATE different user entries before any growth of |
| 157 |
the hash table size occurs. So, if have a reasonably tight a-priori upper |
| 158 |
bound on the number of entries you intend to insert in the hash table, you |
| 159 |
may save some table memory and insertion time, by specifying it here. If |
| 160 |
the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE |
| 161 |
argument has its meaning changed to the wanted number of buckets. |
| 162 |
|
| 163 |
TUNING points to a structure of user-supplied values, in case some fine |
| 164 |
tuning is wanted over the default behavior of the hasher. If TUNING is |
| 165 |
NULL, the default tuning parameters are used instead. If TUNING is |
| 166 |
provided but the values requested are out of bounds or might cause |
| 167 |
rounding errors, return NULL. |
| 168 |
|
| 169 |
The user-supplied HASHER function, when not NULL, accepts two |
| 170 |
arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a |
| 171 |
slot number for that entry which should be in the range 0..TABLE_SIZE-1. |
| 172 |
This slot number is then returned. |
| 173 |
|
| 174 |
The user-supplied COMPARATOR function, when not NULL, accepts two |
| 175 |
arguments pointing to user data, it then returns true for a pair of entries |
| 176 |
that compare equal, or false otherwise. This function is internally called |
| 177 |
on entries which are already known to hash to the same bucket index, |
| 178 |
but which are distinct pointers. |
| 179 |
|
| 180 |
The user-supplied DATA_FREER function, when not NULL, may be later called |
| 181 |
with the user data as an argument, just before the entry containing the |
| 182 |
data gets freed. This happens from within 'hash_free' or 'hash_clear'. |
| 183 |
You should specify this function only if you want these functions to free |
| 184 |
all of your 'data' data. This is typically the case when your data is |
| 185 |
simply an auxiliary struct that you have malloc'd to aggregate several |
| 186 |
values. |
| 187 |
|
| 188 |
Set errno on failure; otherwise errno is unspecified. */ |
| 189 |
_GL_ATTRIBUTE_NODISCARD |
| 190 |
extern Hash_table *hash_initialize (size_t candidate, |
| 191 |
const Hash_tuning *tuning, |
| 192 |
Hash_hasher hasher, |
| 193 |
Hash_comparator comparator, |
| 194 |
Hash_data_freer data_freer) |
| 195 |
_GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC (hash_free, 1); |
| 196 |
|
| 197 |
/* Like hash_initialize, but invokes xalloc_die instead of returning NULL. */ |
| 198 |
/* This function is defined by module 'xhash'. */ |
| 199 |
_GL_ATTRIBUTE_NODISCARD |
| 200 |
extern Hash_table *hash_xinitialize (size_t candidate, |
| 201 |
const Hash_tuning *tuning, |
| 202 |
Hash_hasher hasher, |
| 203 |
Hash_comparator comparator, |
| 204 |
Hash_data_freer data_freer) |
| 205 |
_GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC (hash_free, 1) |
| 206 |
_GL_ATTRIBUTE_RETURNS_NONNULL; |
| 207 |
|
| 208 |
/* Make all buckets empty, placing any chained entries on the free list. |
| 209 |
Apply the user-specified function data_freer (if any) to the data of any |
| 210 |
affected entries. */ |
| 211 |
extern void hash_clear (Hash_table *table); |
| 212 |
|
| 213 |
/* |
| 214 |
* Insertion and deletion. |
| 215 |
*/ |
| 216 |
|
| 217 |
/* For an already existing hash table, change the number of buckets through |
| 218 |
specifying CANDIDATE. The contents of the hash table are preserved. The |
| 219 |
new number of buckets is automatically selected so as to _guarantee_ that |
| 220 |
the table may receive at least CANDIDATE different user entries, including |
| 221 |
those already in the table, before any other growth of the hash table size |
| 222 |
occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the |
| 223 |
exact number of buckets desired. Return true iff the rehash succeeded, |
| 224 |
false (setting errno) otherwise. */ |
| 225 |
_GL_ATTRIBUTE_NODISCARD |
| 226 |
extern bool hash_rehash (Hash_table *table, size_t candidate); |
| 227 |
|
| 228 |
/* If ENTRY matches an entry already in the hash table, return the pointer |
| 229 |
to the entry from the table. Otherwise, insert ENTRY and return ENTRY. |
| 230 |
Return NULL (setting errno) if the storage required for insertion |
| 231 |
cannot be allocated. This implementation does not support |
| 232 |
duplicate entries or insertion of NULL. */ |
| 233 |
_GL_ATTRIBUTE_NODISCARD |
| 234 |
extern void *hash_insert (Hash_table *table, const void *entry); |
| 235 |
|
| 236 |
/* Same as hash_insert, but invokes xalloc_die instead of returning NULL. */ |
| 237 |
/* This function is defined by module 'xhash'. */ |
| 238 |
extern void *hash_xinsert (Hash_table *table, const void *entry); |
| 239 |
|
| 240 |
/* Insert ENTRY into hash TABLE if there is not already a matching entry. |
| 241 |
|
| 242 |
Return -1 (setting errno) upon memory allocation failure. |
| 243 |
Return 1 if insertion succeeded. |
| 244 |
Return 0 if there is already a matching entry in the table, |
| 245 |
and in that case, if MATCHED_ENT is non-NULL, set *MATCHED_ENT |
| 246 |
to that entry. |
| 247 |
|
| 248 |
This interface is easier to use than hash_insert when you must |
| 249 |
distinguish between the latter two cases. More importantly, |
| 250 |
hash_insert is unusable for some types of ENTRY values. When using |
| 251 |
hash_insert, the only way to distinguish those cases is to compare |
| 252 |
the return value and ENTRY. That works only when you can have two |
| 253 |
different ENTRY values that point to data that compares "equal". Thus, |
| 254 |
when the ENTRY value is a simple scalar, you must use |
| 255 |
hash_insert_if_absent. ENTRY must not be NULL. */ |
| 256 |
extern int hash_insert_if_absent (Hash_table *table, const void *entry, |
| 257 |
const void **matched_ent); |
| 258 |
|
| 259 |
/* If ENTRY is already in the table, remove it and return the just-deleted |
| 260 |
data (the user may want to deallocate its storage). If ENTRY is not in the |
| 261 |
table, don't modify the table and return NULL. */ |
| 262 |
extern void *hash_remove (Hash_table *table, const void *entry); |
| 263 |
|
| 264 |
/* Same as hash_remove. This interface is deprecated. |
| 265 |
FIXME: Remove in 2022. */ |
| 266 |
_GL_ATTRIBUTE_DEPRECATED |
| 267 |
extern void *hash_delete (Hash_table *table, const void *entry); |
| 268 |
|
| 269 |
# ifdef __cplusplus |
| 270 |
} |
| 271 |
# endif |
| 272 |
|
| 273 |
#endif |