1 /* Fully-inline hash table, used mainly for managing TLS descriptors.
3 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2005, 2008
4 Free Software Foundation, Inc.
5 This file is part of the GNU C Library.
6 Contributed by Alexandre Oliva <aoliva@redhat.com>
8 This file is derived from a 2003's version of libiberty's
9 hashtab.c, contributed by Vladimir Makarov (vmakarov@cygnus.com),
10 but with most adaptation points and support for deleting elements
13 The GNU C Library is free software; you can redistribute it and/or
14 modify it under the terms of the GNU Lesser General Public
15 License as published by the Free Software Foundation; either
16 version 2.1 of the License, or (at your option) any later version.
18 The GNU C Library is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 Lesser General Public License for more details.
23 You should have received a copy of the GNU Lesser General Public
24 License along with the GNU C Library; if not, write to the Free
25 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
28 #ifndef INLINE_HASHTAB_H
29 # define INLINE_HASHTAB_H 1
31 extern void weak_function
free (void *ptr
);
33 inline static unsigned long
34 higher_prime_number (unsigned long n
)
36 /* These are primes that are near, but slightly smaller than, a
38 static const uint32_t primes
[] = {
66 UINT32_C (1073741789),
67 UINT32_C (2147483647),
69 UINT32_C (2147483647) + UINT32_C (2147483644)
72 const uint32_t *low
= &primes
[0];
73 const uint32_t *high
= &primes
[sizeof (primes
) / sizeof (primes
[0])];
77 const uint32_t *mid
= low
+ (high
- low
) / 2;
85 /* If we've run out of primes, abort. */
88 fprintf (stderr
, "Cannot find prime bigger than %lu\n", n
);
101 /* Current size (in entries) of the hash table */
104 /* Current number of elements. */
107 /* Free function for the entries array. This may vary depending on
108 how early the array was allocated. If it is NULL, then the array
110 void (*free
) (void *ptr
);
113 inline static struct hashtab
*
116 struct hashtab
*ht
= malloc (sizeof (struct hashtab
));
121 ht
->entries
= malloc (sizeof (void *) * ht
->size
);
132 memset (ht
->entries
, 0, sizeof (void *) * ht
->size
);
137 /* This is only called from _dl_unmap, so it's safe to call
140 htab_delete (struct hashtab
*htab
)
144 for (i
= htab
->size
- 1; i
>= 0; i
--)
145 if (htab
->entries
[i
])
146 free (htab
->entries
[i
]);
149 htab
->free (htab
->entries
);
153 /* Similar to htab_find_slot, but without several unwanted side effects:
154 - Does not call htab->eq_f when it finds an existing entry.
155 - Does not change the count of elements/searches/collisions in the
157 This function also assumes there are no deleted entries in the table.
158 HASH is the hash value for the element to be inserted. */
160 inline static void **
161 find_empty_slot_for_expand (struct hashtab
*htab
, int hash
)
163 size_t size
= htab
->size
;
164 unsigned int index
= hash
% size
;
165 void **slot
= htab
->entries
+ index
;
171 hash2
= 1 + hash
% (size
- 2);
178 slot
= htab
->entries
+ index
;
184 /* The following function changes size of memory allocated for the
185 entries and repeatedly inserts the table elements. The occupancy
186 of the table after the call will be about 50%. Naturally the hash
187 table must already exist. Remember also that the place of the
188 table entries is changed. If memory allocation failures are allowed,
189 this function will return zero, indicating that the table could not be
190 expanded. If all goes well, it will return a non-zero value. */
193 htab_expand (struct hashtab
*htab
, int (*hash_fn
) (void *))
201 oentries
= htab
->entries
;
202 olimit
= oentries
+ htab
->size
;
204 /* Resize only when table after removal of unused elements is either
205 too full or too empty. */
206 if (htab
->n_elements
* 2 > htab
->size
)
207 nsize
= higher_prime_number (htab
->n_elements
* 2);
211 nentries
= malloc (sizeof (void *) * nsize
);
212 memset (nentries
, 0, sizeof (void *) * nsize
);
213 if (nentries
== NULL
)
215 htab
->entries
= nentries
;
222 *find_empty_slot_for_expand (htab
, hash_fn (*p
))
229 /* Without recording the free corresponding to the malloc used to
230 allocate the table, we couldn't tell whether this was allocated
231 by the malloc() built into ld.so or the one in the main
232 executable or libc. Calling free() for something that was
233 allocated by the early malloc(), rather than the final run-time
234 malloc() could do Very Bad Things (TM). We will waste memory
235 allocated early as long as there's no corresponding free(), but
236 this isn't so much memory as to be significant. */
239 htab
->free (oentries
);
241 /* Use the free() corresponding to the malloc() above to free this
248 /* This function searches for a hash table slot containing an entry
249 equal to the given element. To delete an entry, call this with
250 INSERT = 0, then call htab_clear_slot on the slot returned (possibly
251 after doing some checks). To insert an entry, call this with
252 INSERT = 1, then write the value you want into the returned slot.
253 When inserting an entry, NULL may be returned if memory allocation
256 inline static void **
257 htab_find_slot (struct hashtab
*htab
, void *ptr
, int insert
,
258 int (*hash_fn
)(void *), int (*eq_fn
)(void *, void *))
265 if (htab
->size
* 3 <= htab
->n_elements
* 4
266 && htab_expand (htab
, hash_fn
) == 0)
269 hash
= hash_fn (ptr
);
274 entry
= &htab
->entries
[index
];
277 else if (eq_fn (*entry
, ptr
))
280 hash2
= 1 + hash
% (size
- 2);
287 entry
= &htab
->entries
[index
];
290 else if (eq_fn (*entry
, ptr
))
302 #endif /* INLINE_HASHTAB_H */