inline-hashtab.h 5.9 KB

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