regexec.c: avoid leaks on out-of-memory failure paths
[glibc.git] / include / inline-hashtab.h
blob0f6719b91c2a849e499ebe2a5447e908be555862
1 /* Fully-inline hash table, used mainly for managing TLS descriptors.
2 Copyright (C) 1999-2003, 2005, 2008, 2009 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Alexandre Oliva <aoliva@redhat.com>
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.
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.
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.
21 You should have received a copy of the GNU Lesser General Public
22 License along with the GNU C Library; if not, write to the Free
23 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
24 02111-1307 USA. */
26 #ifndef INLINE_HASHTAB_H
27 # define INLINE_HASHTAB_H 1
29 extern void weak_function free (void *ptr);
31 struct hashtab
33 /* Table itself. */
34 void **entries;
36 /* Current size (in entries) of the hash table */
37 size_t size;
39 /* Current number of elements. */
40 size_t n_elements;
42 /* Free function for the entries array. This may vary depending on
43 how early the array was allocated. If it is NULL, then the array
44 can't be freed. */
45 void (*free) (void *ptr);
48 inline static struct hashtab *
49 htab_create (void)
51 struct hashtab *ht = malloc (sizeof (struct hashtab));
53 if (! ht)
54 return NULL;
55 ht->size = 3;
56 ht->entries = malloc (sizeof (void *) * ht->size);
57 ht->free = free;
58 if (! ht->entries)
60 if (ht->free)
61 ht->free (ht);
62 return NULL;
65 ht->n_elements = 0;
67 memset (ht->entries, 0, sizeof (void *) * ht->size);
69 return ht;
72 /* This is only called from _dl_unmap, so it's safe to call
73 free(). */
74 inline static void
75 htab_delete (struct hashtab *htab)
77 int i;
79 for (i = htab->size - 1; i >= 0; i--)
80 free (htab->entries[i]);
82 if (htab->free)
83 htab->free (htab->entries);
84 free (htab);
87 /* Similar to htab_find_slot, but without several unwanted side effects:
88 - Does not call htab->eq_f when it finds an existing entry.
89 - Does not change the count of elements/searches/collisions in the
90 hash table.
91 This function also assumes there are no deleted entries in the table.
92 HASH is the hash value for the element to be inserted. */
94 inline static void **
95 find_empty_slot_for_expand (struct hashtab *htab, int hash)
97 size_t size = htab->size;
98 unsigned int index = hash % size;
99 void **slot = htab->entries + index;
100 int hash2;
102 if (! *slot)
103 return slot;
105 hash2 = 1 + hash % (size - 2);
106 for (;;)
108 index += hash2;
109 if (index >= size)
110 index -= size;
112 slot = htab->entries + index;
113 if (! *slot)
114 return slot;
118 /* The following function changes size of memory allocated for the
119 entries and repeatedly inserts the table elements. The occupancy
120 of the table after the call will be about 50%. Naturally the hash
121 table must already exist. Remember also that the place of the
122 table entries is changed. If memory allocation failures are allowed,
123 this function will return zero, indicating that the table could not be
124 expanded. If all goes well, it will return a non-zero value. */
126 inline static int
127 htab_expand (struct hashtab *htab, int (*hash_fn) (void *))
129 void **oentries;
130 void **olimit;
131 void **p;
132 void **nentries;
133 size_t nsize;
135 oentries = htab->entries;
136 olimit = oentries + htab->size;
138 /* Resize only when table after removal of unused elements is either
139 too full or too empty. */
140 if (htab->n_elements * 2 > htab->size)
141 nsize = _dl_higher_prime_number (htab->n_elements * 2);
142 else
143 nsize = htab->size;
145 nentries = calloc (sizeof (void *), nsize);
146 if (nentries == NULL)
147 return 0;
148 htab->entries = nentries;
149 htab->size = nsize;
151 p = oentries;
154 if (*p)
155 *find_empty_slot_for_expand (htab, hash_fn (*p))
156 = *p;
158 p++;
160 while (p < olimit);
162 /* Without recording the free corresponding to the malloc used to
163 allocate the table, we couldn't tell whether this was allocated
164 by the malloc() built into ld.so or the one in the main
165 executable or libc. Calling free() for something that was
166 allocated by the early malloc(), rather than the final run-time
167 malloc() could do Very Bad Things (TM). We will waste memory
168 allocated early as long as there's no corresponding free(), but
169 this isn't so much memory as to be significant. */
171 if (htab->free)
172 htab->free (oentries);
174 /* Use the free() corresponding to the malloc() above to free this
175 up. */
176 htab->free = free;
178 return 1;
181 /* This function searches for a hash table slot containing an entry
182 equal to the given element. To delete an entry, call this with
183 INSERT = 0, then call htab_clear_slot on the slot returned (possibly
184 after doing some checks). To insert an entry, call this with
185 INSERT = 1, then write the value you want into the returned slot.
186 When inserting an entry, NULL may be returned if memory allocation
187 fails. */
189 inline static void **
190 htab_find_slot (struct hashtab *htab, void *ptr, int insert,
191 int (*hash_fn)(void *), int (*eq_fn)(void *, void *))
193 unsigned int index;
194 int hash, hash2;
195 size_t size;
196 void **entry;
198 if (htab->size * 3 <= htab->n_elements * 4
199 && htab_expand (htab, hash_fn) == 0)
200 return NULL;
202 hash = hash_fn (ptr);
204 size = htab->size;
205 index = hash % size;
207 entry = &htab->entries[index];
208 if (!*entry)
209 goto empty_entry;
210 else if (eq_fn (*entry, ptr))
211 return entry;
213 hash2 = 1 + hash % (size - 2);
214 for (;;)
216 index += hash2;
217 if (index >= size)
218 index -= size;
220 entry = &htab->entries[index];
221 if (!*entry)
222 goto empty_entry;
223 else if (eq_fn (*entry, ptr))
224 return entry;
227 empty_entry:
228 if (!insert)
229 return NULL;
231 htab->n_elements++;
232 return entry;
235 #endif /* INLINE_HASHTAB_H */