aboutsummaryrefslogtreecommitdiff
path: root/include/inline-hashtab.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/inline-hashtab.h')
-rw-r--r--include/inline-hashtab.h302
1 files changed, 302 insertions, 0 deletions
diff --git a/include/inline-hashtab.h b/include/inline-hashtab.h
new file mode 100644
index 0000000000..1c36bd7fce
--- /dev/null
+++ b/include/inline-hashtab.h
@@ -0,0 +1,302 @@
+/* Fully-inline hash table, used mainly for managing TLS descriptors.
+
+ Copyright (C) 1999, 2000, 2001, 2002, 2003, 2005, 2008
+ Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+ Contributed by Alexandre Oliva <aoliva@redhat.com>
+
+ This file is derived from a 2003's version of libiberty's
+ hashtab.c, contributed by Vladimir Makarov (vmakarov@cygnus.com),
+ but with most adaptation points and support for deleting elements
+ removed.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, write to the Free
+ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307 USA. */
+
+#ifndef INLINE_HASHTAB_H
+# define INLINE_HASHTAB_H 1
+
+extern void weak_function free (void *ptr);
+
+inline static unsigned long
+higher_prime_number (unsigned long n)
+{
+ /* These are primes that are near, but slightly smaller than, a
+ power of two. */
+ static const uint32_t primes[] = {
+ UINT32_C (7),
+ UINT32_C (13),
+ UINT32_C (31),
+ UINT32_C (61),
+ UINT32_C (127),
+ UINT32_C (251),
+ UINT32_C (509),
+ UINT32_C (1021),
+ UINT32_C (2039),
+ UINT32_C (4093),
+ UINT32_C (8191),
+ UINT32_C (16381),
+ UINT32_C (32749),
+ UINT32_C (65521),
+ UINT32_C (131071),
+ UINT32_C (262139),
+ UINT32_C (524287),
+ UINT32_C (1048573),
+ UINT32_C (2097143),
+ UINT32_C (4194301),
+ UINT32_C (8388593),
+ UINT32_C (16777213),
+ UINT32_C (33554393),
+ UINT32_C (67108859),
+ UINT32_C (134217689),
+ UINT32_C (268435399),
+ UINT32_C (536870909),
+ UINT32_C (1073741789),
+ UINT32_C (2147483647),
+ /* 4294967291L */
+ UINT32_C (2147483647) + UINT32_C (2147483644)
+ };
+
+ const uint32_t *low = &primes[0];
+ const uint32_t *high = &primes[sizeof (primes) / sizeof (primes[0])];
+
+ while (low != high)
+ {
+ const unsigned long *mid = low + (high - low) / 2;
+ if (n > *mid)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+
+#if 0
+ /* If we've run out of primes, abort. */
+ if (n > *low)
+ {
+ fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
+ abort ();
+ }
+#endif
+
+ return *low;
+}
+
+struct hashtab
+{
+ /* Table itself. */
+ void **entries;
+
+ /* Current size (in entries) of the hash table */
+ size_t size;
+
+ /* Current number of elements. */
+ size_t n_elements;
+
+ /* Free function for the entries array. This may vary depending on
+ how early the array was allocated. If it is NULL, then the array
+ can't be freed. */
+ void (*free) (void *ptr);
+};
+
+inline static struct hashtab *
+htab_create (void)
+{
+ struct hashtab *ht = malloc (sizeof (struct hashtab));
+
+ if (! ht)
+ return NULL;
+ ht->size = 3;
+ ht->entries = malloc (sizeof (void *) * ht->size);
+ ht->free = free;
+ if (! ht->entries)
+ {
+ if (ht->free)
+ ht->free (ht);
+ return NULL;
+ }
+
+ ht->n_elements = 0;
+
+ memset (ht->entries, 0, sizeof (void *) * ht->size);
+
+ return ht;
+}
+
+/* This is only called from _dl_unmap, so it's safe to call
+ free(). */
+inline static void
+htab_delete (struct hashtab *htab)
+{
+ int i;
+
+ for (i = htab->size - 1; i >= 0; i--)
+ if (htab->entries[i])
+ free (htab->entries[i]);
+
+ if (htab->free)
+ htab->free (htab->entries);
+ free (htab);
+}
+
+/* Similar to htab_find_slot, but without several unwanted side effects:
+ - Does not call htab->eq_f when it finds an existing entry.
+ - Does not change the count of elements/searches/collisions in the
+ hash table.
+ This function also assumes there are no deleted entries in the table.
+ HASH is the hash value for the element to be inserted. */
+
+inline static void **
+find_empty_slot_for_expand (struct hashtab *htab, int hash)
+{
+ size_t size = htab->size;
+ unsigned int index = hash % size;
+ void **slot = htab->entries + index;
+ int hash2;
+
+ if (! *slot)
+ return slot;
+
+ hash2 = 1 + hash % (size - 2);
+ for (;;)
+ {
+ index += hash2;
+ if (index >= size)
+ index -= size;
+
+ slot = htab->entries + index;
+ if (! *slot)
+ return slot;
+ }
+}
+
+/* The following function changes size of memory allocated for the
+ entries and repeatedly inserts the table elements. The occupancy
+ of the table after the call will be about 50%. Naturally the hash
+ table must already exist. Remember also that the place of the
+ table entries is changed. If memory allocation failures are allowed,
+ this function will return zero, indicating that the table could not be
+ expanded. If all goes well, it will return a non-zero value. */
+
+inline static int
+htab_expand (struct hashtab *htab, int (*hash_fn) (void *))
+{
+ void **oentries;
+ void **olimit;
+ void **p;
+ void **nentries;
+ size_t nsize;
+
+ oentries = htab->entries;
+ olimit = oentries + htab->size;
+
+ /* Resize only when table after removal of unused elements is either
+ too full or too empty. */
+ if (htab->n_elements * 2 > htab->size)
+ nsize = higher_prime_number (htab->n_elements * 2);
+ else
+ nsize = htab->size;
+
+ nentries = malloc (sizeof (void *) * nsize);
+ memset (nentries, 0, sizeof (void *) * nsize);
+ if (nentries == NULL)
+ return 0;
+ htab->entries = nentries;
+ htab->size = nsize;
+
+ p = oentries;
+ do
+ {
+ if (*p)
+ *find_empty_slot_for_expand (htab, hash_fn (*p))
+ = *p;
+
+ p++;
+ }
+ while (p < olimit);
+
+ /* Without recording the free corresponding to the malloc used to
+ allocate the table, we couldn't tell whether this was allocated
+ by the malloc() built into ld.so or the one in the main
+ executable or libc. Calling free() for something that was
+ allocated by the early malloc(), rather than the final run-time
+ malloc() could do Very Bad Things (TM). We will waste memory
+ allocated early as long as there's no corresponding free(), but
+ this isn't so much memory as to be significant. */
+
+ if (htab->free)
+ htab->free (oentries);
+
+ /* Use the free() corresponding to the malloc() above to free this
+ up. */
+ htab->free = free;
+
+ return 1;
+}
+
+/* This function searches for a hash table slot containing an entry
+ equal to the given element. To delete an entry, call this with
+ INSERT = 0, then call htab_clear_slot on the slot returned (possibly
+ after doing some checks). To insert an entry, call this with
+ INSERT = 1, then write the value you want into the returned slot.
+ When inserting an entry, NULL may be returned if memory allocation
+ fails. */
+
+inline static void **
+htab_find_slot (struct hashtab *htab, void *ptr, int insert,
+ int (*hash_fn)(void *), int (*eq_fn)(void *, void *))
+{
+ unsigned int index;
+ int hash, hash2;
+ size_t size;
+ void **entry;
+
+ if (htab->size * 3 <= htab->n_elements * 4
+ && htab_expand (htab, hash_fn) == 0)
+ return NULL;
+
+ hash = hash_fn (ptr);
+
+ size = htab->size;
+ index = hash % size;
+
+ entry = &htab->entries[index];
+ if (!*entry)
+ goto empty_entry;
+ else if (eq_fn (*entry, ptr))
+ return entry;
+
+ hash2 = 1 + hash % (size - 2);
+ for (;;)
+ {
+ index += hash2;
+ if (index >= size)
+ index -= size;
+
+ entry = &htab->entries[index];
+ if (!*entry)
+ goto empty_entry;
+ else if (eq_fn (*entry, ptr))
+ return entry;
+ }
+
+ empty_entry:
+ if (!insert)
+ return NULL;
+
+ htab->n_elements++;
+ return entry;
+}
+
+#endif /* INLINE_HASHTAB_H */
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-14 07:02:24 +0000