1 | /* hash - hashing table processing. |
2 | Copyright (C) 1998-1999, 2001, 2003, 2009-2019 Free Software Foundation, |
3 | Inc. |
4 | Written by Jim Meyering <meyering@ascend.com>, 1998. |
5 | |
6 | This program is free software: you can redistribute it and/or modify |
7 | it under the terms of the GNU General Public License as published by |
8 | the Free Software Foundation; either version 3 of the License, or |
9 | (at your option) any later version. |
10 | |
11 | This program 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 General Public License for more details. |
15 | |
16 | You should have received a copy of the GNU 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 | # include <stdio.h> |
28 | # include <stdbool.h> |
29 | |
30 | /* The __attribute__ feature is available in gcc versions 2.5 and later. |
31 | The warn_unused_result attribute appeared first in gcc-3.4.0. */ |
32 | # if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) |
33 | # define _GL_ATTRIBUTE_WUR __attribute__ ((__warn_unused_result__)) |
34 | # else |
35 | # define _GL_ATTRIBUTE_WUR /* empty */ |
36 | # endif |
37 | |
38 | # ifndef _GL_ATTRIBUTE_DEPRECATED |
39 | /* The __attribute__((__deprecated__)) feature |
40 | is available in gcc versions 3.1 and newer. */ |
41 | # if __GNUC__ < 3 || (__GNUC__ == 3 && __GNUC_MINOR__ < 1) |
42 | # define _GL_ATTRIBUTE_DEPRECATED /* empty */ |
43 | # else |
44 | # define _GL_ATTRIBUTE_DEPRECATED __attribute__ ((__deprecated__)) |
45 | # endif |
46 | # endif |
47 | |
48 | typedef size_t (*Hash_hasher) (const void *, size_t); |
49 | typedef bool (*Hash_comparator) (const void *, const void *); |
50 | typedef void (*Hash_data_freer) (void *); |
51 | typedef bool (*Hash_processor) (void *, void *); |
52 | |
53 | struct hash_tuning |
54 | { |
55 | /* This structure is mainly used for 'hash_initialize', see the block |
56 | documentation of 'hash_reset_tuning' for more complete comments. */ |
57 | |
58 | float shrink_threshold; /* ratio of used buckets to trigger a shrink */ |
59 | float shrink_factor; /* ratio of new smaller size to original size */ |
60 | float growth_threshold; /* ratio of used buckets to trigger a growth */ |
61 | float growth_factor; /* ratio of new bigger size to original size */ |
62 | bool is_n_buckets; /* if CANDIDATE really means table size */ |
63 | }; |
64 | |
65 | typedef struct hash_tuning Hash_tuning; |
66 | |
67 | struct hash_table; |
68 | |
69 | typedef struct hash_table Hash_table; |
70 | |
71 | /* Information and lookup. */ |
72 | size_t hash_get_n_buckets (const Hash_table *) _GL_ATTRIBUTE_PURE; |
73 | size_t hash_get_n_buckets_used (const Hash_table *) _GL_ATTRIBUTE_PURE; |
74 | size_t hash_get_n_entries (const Hash_table *) _GL_ATTRIBUTE_PURE; |
75 | size_t hash_get_max_bucket_length (const Hash_table *) _GL_ATTRIBUTE_PURE; |
76 | bool hash_table_ok (const Hash_table *) _GL_ATTRIBUTE_PURE; |
77 | void hash_print_statistics (const Hash_table *, FILE *); |
78 | void *hash_lookup (const Hash_table *, const void *); |
79 | |
80 | /* Walking. */ |
81 | void *hash_get_first (const Hash_table *) _GL_ATTRIBUTE_PURE; |
82 | void *hash_get_next (const Hash_table *, const void *); |
83 | size_t hash_get_entries (const Hash_table *, void **, size_t); |
84 | size_t hash_do_for_each (const Hash_table *, Hash_processor, void *); |
85 | |
86 | /* Allocation and clean-up. */ |
87 | size_t hash_string (const char *, size_t) _GL_ATTRIBUTE_PURE; |
88 | void hash_reset_tuning (Hash_tuning *); |
89 | Hash_table *hash_initialize (size_t, const Hash_tuning *, |
90 | Hash_hasher, Hash_comparator, |
91 | Hash_data_freer) _GL_ATTRIBUTE_WUR; |
92 | Hash_table *hash_xinitialize (size_t, const Hash_tuning *, |
93 | Hash_hasher, Hash_comparator, |
94 | Hash_data_freer) _GL_ATTRIBUTE_WUR; |
95 | void hash_clear (Hash_table *); |
96 | void hash_free (Hash_table *); |
97 | |
98 | /* Insertion and deletion. */ |
99 | bool hash_rehash (Hash_table *, size_t) _GL_ATTRIBUTE_WUR; |
100 | void *hash_insert (Hash_table *, const void *) _GL_ATTRIBUTE_WUR; |
101 | |
102 | int hash_insert_if_absent (Hash_table *table, const void *entry, |
103 | const void **matched_ent); |
104 | void *hash_delete (Hash_table *, const void *); |
105 | |
106 | #endif |
107 | |