ldso/include/inline-hashtab.h

   1 /*
   2  * The hashcode handling code below is heavily inspired in libiberty's
   3  * hashtab code, but with most adaptation points and support for
   4  * deleting elements removed.
   5  *
   6  * Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   7  * Contributed by Vladimir Makarov (vmakarov@cygnus.com).
   8  */
   9
  10 #ifndef INLINE_HASHTAB_H
  11 # define INLINE_HASHTAB_H 1
  12
  13 static __always_inline unsigned long
  14 higher_prime_number(unsigned long n)
  15 {
  16         /* These are primes that are near, but slightly smaller than, a power of two. */
  17         static const unsigned long primes[] = {
  18                 7,
  19                 13,
  20                 31,
  21                 61,
  22                 127,
  23                 251,
  24                 509,
  25                 1021,
  26                 2039,
  27                 4093,
  28                 8191,
  29                 16381,
  30                 32749,
  31                 65521,
  32                 131071,
  33                 262139,
  34                 524287,
  35                 1048573,
  36                 2097143,
  37                 4194301,
  38                 8388593,
  39                 16777213,
  40                 33554393,
  41                 67108859,
  42                 134217689,
  43                 268435399,
  44                 536870909,
  45                 1073741789,
  46                 /* 4294967291 */
  47                 ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
  48         };
  49         const unsigned long *low = &primes[0];
  50         const unsigned long *high = &primes[ARRAY_SIZE(primes)];
  51
  52         while (low != high) {
  53                 const unsigned long *mid = low + (high - low) / 2;
  54                 if (n > *mid)
  55                         low = mid + 1;
  56                 else
  57                         high = mid;
  58         }
  59
  60 #if 0
  61         /* If we've run out of primes, abort.  */
  62         if (n > *low) {
  63                 fprintf(stderr, "Cannot find prime bigger than %lu\n", n);
  64                 abort();
  65         }
  66 #endif
  67
  68         return *low;
  69 }
  70
  71 struct funcdesc_ht
  72 {
  73         /* Table itself */
  74         void **entries;
  75
  76         /* Current size (in entries) of the hash table */
  77         size_t size;
  78
  79         /* Current number of elements */
  80         size_t n_elements;
  81 };
  82
  83 static __always_inline struct funcdesc_ht *
  84 htab_create(void)
  85 {
  86         struct funcdesc_ht *ht = _dl_malloc(sizeof(*ht));
  87         size_t ent_size;
  88
  89         if (!ht)
  90                 return NULL;
  91         ht->size = 3;
  92         ent_size = sizeof(void *) * ht->size;
  93         ht->entries = _dl_malloc(ent_size);
  94         if (!ht->entries)
  95                 return NULL;
  96
  97         ht->n_elements = 0;
  98         _dl_memset(ht->entries, 0, ent_size);
  99
 100         return ht;
 101 }
 102
 103 /*
 104  * This is only called from _dl_loadaddr_unmap, so it's safe to call
 105  * _dl_free().  See the discussion below.
 106  */
 107 static __always_inline void
 108 htab_delete(struct funcdesc_ht *htab)
 109 {
 110         int i;
 111
 112         for (i = htab->size - 1; i >= 0; i--)
 113                 if (htab->entries[i])
 114                         _dl_free(htab->entries[i]);
 115
 116         _dl_free(htab->entries);
 117         _dl_free(htab);
 118 }
 119
 120 /*
 121  * Similar to htab_find_slot, but without several unwanted side effects:
 122  *  - Does not call htab->eq_f when it finds an existing entry.
 123  *  - Does not change the count of elements/searches/collisions in the
 124  *    hash table.
 125  * This function also assumes there are no deleted entries in the table.
 126  * HASH is the hash value for the element to be inserted.
 127  */
 128 static __always_inline void **
 129 find_empty_slot_for_expand(struct funcdesc_ht *htab, int hash)
 130 {
 131         size_t size = htab->size;
 132         unsigned int index = hash % size;
 133         void **slot = htab->entries + index;
 134         int hash2;
 135
 136         if (!*slot)
 137                 return slot;
 138
 139         hash2 = 1 + hash % (size - 2);
 140         for (;;) {
 141                 index += hash2;
 142                 if (index >= size)
 143                         index -= size;
 144
 145                 slot = htab->entries + index;
 146                 if (!*slot)
 147                         return slot;
 148         }
 149 }
 150
 151 /*
 152  * The following function changes size of memory allocated for the
 153  * entries and repeatedly inserts the table elements.  The occupancy
 154  * of the table after the call will be about 50%.  Naturally the hash
 155  * table must already exist.  Remember also that the place of the
 156  * table entries is changed.  If memory allocation failures are allowed,
 157  * this function will return zero, indicating that the table could not be
 158  * expanded.  If all goes well, it will return a non-zero value.
 159  */
 160 static __always_inline int
 161 htab_expand(struct funcdesc_ht *htab, int (*hash_fn) (void *))
 162 {
 163         void **oentries;
 164         void **olimit;
 165         void **p;
 166         void **nentries;
 167         size_t nsize;
 168
 169         oentries = htab->entries;
 170         olimit = oentries + htab->size;
 171
 172         /*
 173          * Resize only when table after removal of unused elements is either
 174          * too full or too empty.
 175          */
 176         if (htab->n_elements * 2 > htab->size)
 177                 nsize = higher_prime_number(htab->n_elements * 2);
 178         else
 179                 nsize = htab->size;
 180
 181         nentries = _dl_malloc(sizeof(*nentries) * nsize);
 182         _dl_memset(nentries, 0, sizeof(*nentries) * nsize);
 183         if (nentries == NULL)
 184                 return 0;
 185         htab->entries = nentries;
 186         htab->size = nsize;
 187
 188         p = oentries;
 189         do {
 190                 if (*p)
 191                         *find_empty_slot_for_expand(htab, hash_fn(*p)) = *p;
 192                 p++;
 193         } while (p < olimit);
 194
 195 #if 0
 196         /*
 197          * We can't tell whether this was allocated by the _dl_malloc()
 198          * built into ld.so or malloc() in the main executable or libc,
 199          * and calling free() for something that wasn't malloc()ed could
 200          * do Very Bad Things (TM).  Take the conservative approach
 201          * here, potentially wasting as much memory as actually used by
 202          * the hash table, even if multiple growths occur.  That's not
 203          * so bad as to require some overengineered solution that would
 204          * enable us to keep track of how it was allocated.
 205          */
 206         _dl_free(oentries);
 207 #endif
 208         return 1;
 209 }
 210
 211 /*
 212  * This function searches for a hash table slot containing an entry
 213  * equal to the given element.  To delete an entry, call this with
 214  * INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 215  * after doing some checks).  To insert an entry, call this with
 216  * INSERT = 1, then write the value you want into the returned slot.
 217  * When inserting an entry, NULL may be returned if memory allocation
 218  * fails.
 219  */
 220 static __always_inline void **
 221 htab_find_slot(struct funcdesc_ht *htab, void *ptr, int insert,
 222                int (*hash_fn)(void *), int (*eq_fn)(void *, void *))
 223 {
 224         unsigned int index;
 225         int hash, hash2;
 226         size_t size;
 227         void **entry;
 228
 229         if (htab->size * 3 <= htab->n_elements * 4 &&
 230             htab_expand(htab, hash_fn) == 0)
 231                 return NULL;
 232
 233         hash = hash_fn(ptr);
 234
 235         size = htab->size;
 236         index = hash % size;
 237
 238         entry = &htab->entries[index];
 239         if (!*entry)
 240                 goto empty_entry;
 241         else if (eq_fn(*entry, ptr))
 242                 return entry;
 243
 244         hash2 = 1 + hash % (size - 2);
 245         for (;;) {
 246                 index += hash2;
 247                 if (index >= size)
 248                         index -= size;
 249
 250                 entry = &htab->entries[index];
 251                 if (!*entry)
 252                         goto empty_entry;
 253                 else if (eq_fn(*entry, ptr))
 254                         return entry;
 255         }
 256
 257  empty_entry:
 258         if (!insert)
 259                 return NULL;
 260
 261         htab->n_elements++;
 262         return entry;
 263 }
 264
 265 #endif