]>
Commit | Line | Data |
---|---|---|
c9ff0187 | 1 | /* Fully-inline hash table, used mainly for managing TLS descriptors. |
04277e02 | 2 | Copyright (C) 1999-2019 Free Software Foundation, Inc. |
c9ff0187 UD |
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 | |
59ba27a6 | 22 | License along with the GNU C Library; if not, see |
5a82c748 | 23 | <https://www.gnu.org/licenses/>. */ |
c9ff0187 UD |
24 | |
25 | #ifndef INLINE_HASHTAB_H | |
26 | # define INLINE_HASHTAB_H 1 | |
27 | ||
28 | extern void weak_function free (void *ptr); | |
29 | ||
c9ff0187 UD |
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--) | |
62605cbf | 79 | free (htab->entries[i]); |
c9ff0187 UD |
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) | |
eba0994e | 140 | nsize = _dl_higher_prime_number (htab->n_elements * 2); |
c9ff0187 UD |
141 | else |
142 | nsize = htab->size; | |
143 | ||
eba0994e | 144 | nentries = calloc (sizeof (void *), nsize); |
c9ff0187 UD |
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 */ |