include/inline-hashtab.h

   1 /* Fully-inline hash table, used mainly for managing TLS descriptors.
   2    Copyright (C) 1999-2021 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, see
  23    <https://www.gnu.org/licenses/>.  */
  24
  25 #ifndef INLINE_HASHTAB_H
  26 # define INLINE_HASHTAB_H 1
  27
  28 struct hashtab
  29 {
  30   /* Table itself.  */
  31   void **entries;
  32
  33   /* Current size (in entries) of the hash table */
  34   size_t size;
  35
  36   /* Current number of elements.  */
  37   size_t n_elements;
  38
  39   /* Free function for the entries array.  This may vary depending on
  40      how early the array was allocated.  If it is NULL, then the array
  41      can't be freed.  */
  42   void (*free) (void *ptr);
  43 };
  44
  45 inline static struct hashtab *
  46 htab_create (void)
  47 {
  48   struct hashtab *ht = malloc (sizeof (struct hashtab));
  49
  50   if (! ht)
  51     return NULL;
  52   ht->size = 3;
  53   ht->entries = malloc (sizeof (void *) * ht->size);
  54   ht->free = __rtld_free;
  55   if (! ht->entries)
  56     {
  57       free (ht);
  58       return NULL;
  59     }
  60
  61   ht->n_elements = 0;
  62
  63   memset (ht->entries, 0, sizeof (void *) * ht->size);
  64
  65   return ht;
  66 }
  67
  68 /* This is only called from _dl_unmap, so it's safe to call
  69    free().  */
  70 inline static void
  71 htab_delete (struct hashtab *htab)
  72 {
  73   int i;
  74
  75   for (i = htab->size - 1; i >= 0; i--)
  76     free (htab->entries[i]);
  77
  78   htab->free (htab->entries);
  79   free (htab);
  80 }
  81
  82 /* Similar to htab_find_slot, but without several unwanted side effects:
  83     - Does not call htab->eq_f when it finds an existing entry.
  84     - Does not change the count of elements/searches/collisions in the
  85       hash table.
  86    This function also assumes there are no deleted entries in the table.
  87    HASH is the hash value for the element to be inserted.  */
  88
  89 inline static void **
  90 find_empty_slot_for_expand (struct hashtab *htab, int hash)
  91 {
  92   size_t size = htab->size;
  93   unsigned int index = hash % size;
  94   void **slot = htab->entries + index;
  95   int hash2;
  96
  97   if (! *slot)
  98     return slot;
  99
 100   hash2 = 1 + hash % (size - 2);
 101   for (;;)
 102     {
 103       index += hash2;
 104       if (index >= size)
 105         index -= size;
 106
 107       slot = htab->entries + index;
 108       if (! *slot)
 109         return slot;
 110     }
 111 }
 112
 113 /* The following function changes size of memory allocated for the
 114    entries and repeatedly inserts the table elements.  The occupancy
 115    of the table after the call will be about 50%.  Naturally the hash
 116    table must already exist.  Remember also that the place of the
 117    table entries is changed.  If memory allocation failures are allowed,
 118    this function will return zero, indicating that the table could not be
 119    expanded.  If all goes well, it will return a non-zero value.  */
 120
 121 inline static int
 122 htab_expand (struct hashtab *htab, int (*hash_fn) (void *))
 123 {
 124   void **oentries;
 125   void **olimit;
 126   void **p;
 127   void **nentries;
 128   size_t nsize;
 129
 130   oentries = htab->entries;
 131   olimit = oentries + htab->size;
 132
 133   /* Resize only when table after removal of unused elements is either
 134      too full or too empty.  */
 135   if (htab->n_elements * 2 > htab->size)
 136     nsize = _dl_higher_prime_number (htab->n_elements * 2);
 137   else
 138     nsize = htab->size;
 139
 140   nentries = calloc (sizeof (void *), nsize);
 141   if (nentries == NULL)
 142     return 0;
 143   htab->entries = nentries;
 144   htab->size = nsize;
 145
 146   p = oentries;
 147   do
 148     {
 149       if (*p)
 150         *find_empty_slot_for_expand (htab, hash_fn (*p))
 151           = *p;
 152
 153       p++;
 154     }
 155   while (p < olimit);
 156
 157   /* Without recording the free corresponding to the malloc used to
 158      allocate the table, we couldn't tell whether this was allocated
 159      by the malloc() built into ld.so or the one in the main
 160      executable or libc.  Calling free() for something that was
 161      allocated by the early malloc(), rather than the final run-time
 162      malloc() could do Very Bad Things (TM).  We will waste memory
 163      allocated early as long as there's no corresponding free(), but
 164      this isn't so much memory as to be significant.  */
 165
 166   htab->free (oentries);
 167
 168   /* Use the free() corresponding to the malloc() above to free this
 169      up.  */
 170   htab->free = __rtld_free;
 171
 172   return 1;
 173 }
 174
 175 /* This function searches for a hash table slot containing an entry
 176    equal to the given element.  To delete an entry, call this with
 177    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 178    after doing some checks).  To insert an entry, call this with
 179    INSERT = 1, then write the value you want into the returned slot.
 180    When inserting an entry, NULL may be returned if memory allocation
 181    fails.  */
 182
 183 inline static void **
 184 htab_find_slot (struct hashtab *htab, void *ptr, int insert,
 185                 int (*hash_fn)(void *), int (*eq_fn)(void *, void *))
 186 {
 187   unsigned int index;
 188   int hash, hash2;
 189   size_t size;
 190   void **entry;
 191
 192   if (htab->size * 3 <= htab->n_elements * 4
 193       && htab_expand (htab, hash_fn) == 0)
 194     return NULL;
 195
 196   hash = hash_fn (ptr);
 197
 198   size = htab->size;
 199   index = hash % size;
 200
 201   entry = &htab->entries[index];
 202   if (!*entry)
 203     goto empty_entry;
 204   else if (eq_fn (*entry, ptr))
 205     return entry;
 206
 207   hash2 = 1 + hash % (size - 2);
 208   for (;;)
 209     {
 210       index += hash2;
 211       if (index >= size)
 212         index -= size;
 213
 214       entry = &htab->entries[index];
 215       if (!*entry)
 216         goto empty_entry;
 217       else if (eq_fn (*entry, ptr))
 218         return entry;
 219     }
 220
 221  empty_entry:
 222   if (!insert)
 223     return NULL;
 224
 225   htab->n_elements++;
 226   return entry;
 227 }
 228
 229 #endif /* INLINE_HASHTAB_H */