1 | /* Fully-inline hash table, used mainly for managing TLS descriptors. |
2 | Copyright (C) 1999-2017 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | Contributed by Alexandre Oliva <aoliva@redhat.com> |
5 | |
6 | This file is derived from a 2003's version of libiberty's |
7 | hashtab.c, contributed by Vladimir Makarov (vmakarov@cygnus.com), |
8 | but with most adaptation points and support for deleting elements |
9 | removed. |
10 | |
11 | The GNU C Library is free software; you can redistribute it and/or |
12 | modify it under the terms of the GNU Lesser General Public |
13 | License as published by the Free Software Foundation; either |
14 | version 2.1 of the License, or (at your option) any later version. |
15 | |
16 | The GNU C Library is distributed in the hope that it will be useful, |
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
19 | Lesser General Public License for more details. |
20 | |
21 | You should have received a copy of the GNU Lesser General Public |
22 | License along with the GNU C Library; if not, see |
23 | <http://www.gnu.org/licenses/>. */ |
24 | |
25 | #ifndef INLINE_HASHTAB_H |
26 | # define INLINE_HASHTAB_H 1 |
27 | |
28 | extern void weak_function free (void *ptr); |
29 | |
30 | struct hashtab |
31 | { |
32 | /* Table itself. */ |
33 | void **entries; |
34 | |
35 | /* Current size (in entries) of the hash table */ |
36 | size_t size; |
37 | |
38 | /* Current number of elements. */ |
39 | size_t n_elements; |
40 | |
41 | /* Free function for the entries array. This may vary depending on |
42 | how early the array was allocated. If it is NULL, then the array |
43 | can't be freed. */ |
44 | void (*free) (void *ptr); |
45 | }; |
46 | |
47 | inline static struct hashtab * |
48 | htab_create (void) |
49 | { |
50 | struct hashtab *ht = malloc (sizeof (struct hashtab)); |
51 | |
52 | if (! ht) |
53 | return NULL; |
54 | ht->size = 3; |
55 | ht->entries = malloc (sizeof (void *) * ht->size); |
56 | ht->free = free; |
57 | if (! ht->entries) |
58 | { |
59 | if (ht->free) |
60 | ht->free (ht); |
61 | return NULL; |
62 | } |
63 | |
64 | ht->n_elements = 0; |
65 | |
66 | memset (ht->entries, 0, sizeof (void *) * ht->size); |
67 | |
68 | return ht; |
69 | } |
70 | |
71 | /* This is only called from _dl_unmap, so it's safe to call |
72 | free(). */ |
73 | inline static void |
74 | htab_delete (struct hashtab *htab) |
75 | { |
76 | int i; |
77 | |
78 | for (i = htab->size - 1; i >= 0; i--) |
79 | free (htab->entries[i]); |
80 | |
81 | if (htab->free) |
82 | htab->free (htab->entries); |
83 | free (htab); |
84 | } |
85 | |
86 | /* Similar to htab_find_slot, but without several unwanted side effects: |
87 | - Does not call htab->eq_f when it finds an existing entry. |
88 | - Does not change the count of elements/searches/collisions in the |
89 | hash table. |
90 | This function also assumes there are no deleted entries in the table. |
91 | HASH is the hash value for the element to be inserted. */ |
92 | |
93 | inline static void ** |
94 | find_empty_slot_for_expand (struct hashtab *htab, int hash) |
95 | { |
96 | size_t size = htab->size; |
97 | unsigned int index = hash % size; |
98 | void **slot = htab->entries + index; |
99 | int hash2; |
100 | |
101 | if (! *slot) |
102 | return slot; |
103 | |
104 | hash2 = 1 + hash % (size - 2); |
105 | for (;;) |
106 | { |
107 | index += hash2; |
108 | if (index >= size) |
109 | index -= size; |
110 | |
111 | slot = htab->entries + index; |
112 | if (! *slot) |
113 | return slot; |
114 | } |
115 | } |
116 | |
117 | /* The following function changes size of memory allocated for the |
118 | entries and repeatedly inserts the table elements. The occupancy |
119 | of the table after the call will be about 50%. Naturally the hash |
120 | table must already exist. Remember also that the place of the |
121 | table entries is changed. If memory allocation failures are allowed, |
122 | this function will return zero, indicating that the table could not be |
123 | expanded. If all goes well, it will return a non-zero value. */ |
124 | |
125 | inline static int |
126 | htab_expand (struct hashtab *htab, int (*hash_fn) (void *)) |
127 | { |
128 | void **oentries; |
129 | void **olimit; |
130 | void **p; |
131 | void **nentries; |
132 | size_t nsize; |
133 | |
134 | oentries = htab->entries; |
135 | olimit = oentries + htab->size; |
136 | |
137 | /* Resize only when table after removal of unused elements is either |
138 | too full or too empty. */ |
139 | if (htab->n_elements * 2 > htab->size) |
140 | nsize = _dl_higher_prime_number (htab->n_elements * 2); |
141 | else |
142 | nsize = htab->size; |
143 | |
144 | nentries = calloc (sizeof (void *), nsize); |
145 | if (nentries == NULL) |
146 | return 0; |
147 | htab->entries = nentries; |
148 | htab->size = nsize; |
149 | |
150 | p = oentries; |
151 | do |
152 | { |
153 | if (*p) |
154 | *find_empty_slot_for_expand (htab, hash_fn (*p)) |
155 | = *p; |
156 | |
157 | p++; |
158 | } |
159 | while (p < olimit); |
160 | |
161 | /* Without recording the free corresponding to the malloc used to |
162 | allocate the table, we couldn't tell whether this was allocated |
163 | by the malloc() built into ld.so or the one in the main |
164 | executable or libc. Calling free() for something that was |
165 | allocated by the early malloc(), rather than the final run-time |
166 | malloc() could do Very Bad Things (TM). We will waste memory |
167 | allocated early as long as there's no corresponding free(), but |
168 | this isn't so much memory as to be significant. */ |
169 | |
170 | if (htab->free) |
171 | htab->free (oentries); |
172 | |
173 | /* Use the free() corresponding to the malloc() above to free this |
174 | up. */ |
175 | htab->free = free; |
176 | |
177 | return 1; |
178 | } |
179 | |
180 | /* This function searches for a hash table slot containing an entry |
181 | equal to the given element. To delete an entry, call this with |
182 | INSERT = 0, then call htab_clear_slot on the slot returned (possibly |
183 | after doing some checks). To insert an entry, call this with |
184 | INSERT = 1, then write the value you want into the returned slot. |
185 | When inserting an entry, NULL may be returned if memory allocation |
186 | fails. */ |
187 | |
188 | inline static void ** |
189 | htab_find_slot (struct hashtab *htab, void *ptr, int insert, |
190 | int (*hash_fn)(void *), int (*eq_fn)(void *, void *)) |
191 | { |
192 | unsigned int index; |
193 | int hash, hash2; |
194 | size_t size; |
195 | void **entry; |
196 | |
197 | if (htab->size * 3 <= htab->n_elements * 4 |
198 | && htab_expand (htab, hash_fn) == 0) |
199 | return NULL; |
200 | |
201 | hash = hash_fn (ptr); |
202 | |
203 | size = htab->size; |
204 | index = hash % size; |
205 | |
206 | entry = &htab->entries[index]; |
207 | if (!*entry) |
208 | goto empty_entry; |
209 | else if (eq_fn (*entry, ptr)) |
210 | return entry; |
211 | |
212 | hash2 = 1 + hash % (size - 2); |
213 | for (;;) |
214 | { |
215 | index += hash2; |
216 | if (index >= size) |
217 | index -= size; |
218 | |
219 | entry = &htab->entries[index]; |
220 | if (!*entry) |
221 | goto empty_entry; |
222 | else if (eq_fn (*entry, ptr)) |
223 | return entry; |
224 | } |
225 | |
226 | empty_entry: |
227 | if (!insert) |
228 | return NULL; |
229 | |
230 | htab->n_elements++; |
231 | return entry; |
232 | } |
233 | |
234 | #endif /* INLINE_HASHTAB_H */ |
235 | |