include/inline-hashtab.h

   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>
   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
  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.  */
  25
  26 #ifndef INLINE_HASHTAB_H
  27 # define INLINE_HASHTAB_H 1
  28
  29 extern void weak_function free (void *ptr);
  30
  31 struct hashtab
  32 {
  33   /* Table itself.  */
  34   void **entries;
  35
  36   /* Current size (in entries) of the hash table */
  37   size_t size;
  38
  39   /* Current number of elements.  */
  40   size_t n_elements;
  41
  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);
  46 };
  47
  48 inline static struct hashtab *
  49 htab_create (void)
  50 {
  51   struct hashtab *ht = malloc (sizeof (struct hashtab));
  52
  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)
  59     {
  60       if (ht->free)
  61         ht->free (ht);
  62       return NULL;
  63     }
  64
  65   ht->n_elements = 0;
  66
  67   memset (ht->entries, 0, sizeof (void *) * ht->size);
  68
  69   return ht;
  70 }
  71
  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)
  76 {
  77   int i;
  78
  79   for (i = htab->size - 1; i >= 0; i--)
  80     free (htab->entries[i]);
  81
  82   if (htab->free)
  83     htab->free (htab->entries);
  84   free (htab);
  85 }
  86
  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.  */
  93
  94 inline static void **
  95 find_empty_slot_for_expand (struct hashtab *htab, int hash)
  96 {
  97   size_t size = htab->size;
  98   unsigned int index = hash % size;
  99   void **slot = htab->entries + index;
 100   int hash2;
 101
 102   if (! *slot)
 103     return slot;
 104
 105   hash2 = 1 + hash % (size - 2);
 106   for (;;)
 107     {
 108       index += hash2;
 109       if (index >= size)
 110         index -= size;
 111
 112       slot = htab->entries + index;
 113       if (! *slot)
 114         return slot;
 115     }
 116 }
 117
 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.  */
 125
 126 inline static int
 127 htab_expand (struct hashtab *htab, int (*hash_fn) (void *))
 128 {
 129   void **oentries;
 130   void **olimit;
 131   void **p;
 132   void **nentries;
 133   size_t nsize;
 134
 135   oentries = htab->entries;
 136   olimit = oentries + htab->size;
 137
 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;
 144
 145   nentries = calloc (sizeof (void *), nsize);
 146   if (nentries == NULL)
 147     return 0;
 148   htab->entries = nentries;
 149   htab->size = nsize;
 150
 151   p = oentries;
 152   do
 153     {
 154       if (*p)
 155         *find_empty_slot_for_expand (htab, hash_fn (*p))
 156           = *p;
 157
 158       p++;
 159     }
 160   while (p < olimit);
 161
 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.  */
 170
 171   if (htab->free)
 172     htab->free (oentries);
 173
 174   /* Use the free() corresponding to the malloc() above to free this
 175      up.  */
 176   htab->free = free;
 177
 178   return 1;
 179 }
 180
 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.  */
 188
 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 *))
 192 {
 193   unsigned int index;
 194   int hash, hash2;
 195   size_t size;
 196   void **entry;
 197
 198   if (htab->size * 3 <= htab->n_elements * 4
 199       && htab_expand (htab, hash_fn) == 0)
 200     return NULL;
 201
 202   hash = hash_fn (ptr);
 203
 204   size = htab->size;
 205   index = hash % size;
 206
 207   entry = &htab->entries[index];
 208   if (!*entry)
 209     goto empty_entry;
 210   else if (eq_fn (*entry, ptr))
 211     return entry;
 212
 213   hash2 = 1 + hash % (size - 2);
 214   for (;;)
 215     {
 216       index += hash2;
 217       if (index >= size)
 218         index -= size;
 219
 220       entry = &htab->entries[index];
 221       if (!*entry)
 222         goto empty_entry;
 223       else if (eq_fn (*entry, ptr))
 224         return entry;
 225     }
 226
 227  empty_entry:
 228   if (!insert)
 229     return NULL;
 230
 231   htab->n_elements++;
 232   return entry;
 233 }
 234
 235 #endif /* INLINE_HASHTAB_H */