about summary refs log tree commit diff
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 */