Back to index

glibc  2.9
inline-hashtab.h
Go to the documentation of this file.
00001 /* Fully-inline hash table, used mainly for managing TLS descriptors.
00002 
00003    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2005, 2008
00004      Free Software Foundation, Inc.
00005    This file is part of the GNU C Library.
00006    Contributed by Alexandre Oliva  <aoliva@redhat.com>
00007 
00008    This file is derived from a 2003's version of libiberty's
00009    hashtab.c, contributed by Vladimir Makarov (vmakarov@cygnus.com),
00010    but with most adaptation points and support for deleting elements
00011    removed.
00012 
00013    The GNU C Library is free software; you can redistribute it and/or
00014    modify it under the terms of the GNU Lesser General Public
00015    License as published by the Free Software Foundation; either
00016    version 2.1 of the License, or (at your option) any later version.
00017 
00018    The GNU C Library is distributed in the hope that it will be useful,
00019    but WITHOUT ANY WARRANTY; without even the implied warranty of
00020    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00021    Lesser General Public License for more details.
00022 
00023    You should have received a copy of the GNU Lesser General Public
00024    License along with the GNU C Library; if not, write to the Free
00025    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00026    02111-1307 USA.  */
00027 
00028 #ifndef INLINE_HASHTAB_H
00029 # define INLINE_HASHTAB_H 1
00030 
00031 extern void weak_function free (void *ptr);
00032 
00033 inline static unsigned long
00034 higher_prime_number (unsigned long n)
00035 {
00036   /* These are primes that are near, but slightly smaller than, a
00037      power of two.  */
00038   static const uint32_t primes[] = {
00039     UINT32_C (7),
00040     UINT32_C (13),
00041     UINT32_C (31),
00042     UINT32_C (61),
00043     UINT32_C (127),
00044     UINT32_C (251),
00045     UINT32_C (509),
00046     UINT32_C (1021),
00047     UINT32_C (2039),
00048     UINT32_C (4093),
00049     UINT32_C (8191),
00050     UINT32_C (16381),
00051     UINT32_C (32749),
00052     UINT32_C (65521),
00053     UINT32_C (131071),
00054     UINT32_C (262139),
00055     UINT32_C (524287),
00056     UINT32_C (1048573),
00057     UINT32_C (2097143),
00058     UINT32_C (4194301),
00059     UINT32_C (8388593),
00060     UINT32_C (16777213),
00061     UINT32_C (33554393),
00062     UINT32_C (67108859),
00063     UINT32_C (134217689),
00064     UINT32_C (268435399),
00065     UINT32_C (536870909),
00066     UINT32_C (1073741789),
00067     UINT32_C (2147483647),
00068                                    /* 4294967291L */
00069     UINT32_C (2147483647) + UINT32_C (2147483644)
00070   };
00071 
00072   const uint32_t *low = &primes[0];
00073   const uint32_t *high = &primes[sizeof (primes) / sizeof (primes[0])];
00074 
00075   while (low != high)
00076     {
00077       const uint32_t *mid = low + (high - low) / 2;
00078       if (n > *mid)
00079        low = mid + 1;
00080       else
00081        high = mid;
00082     }
00083 
00084 #if 0
00085   /* If we've run out of primes, abort.  */
00086   if (n > *low)
00087     {
00088       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
00089       abort ();
00090     }
00091 #endif
00092 
00093   return *low;
00094 }
00095 
00096 struct hashtab
00097 {
00098   /* Table itself.  */
00099   void **entries;
00100 
00101   /* Current size (in entries) of the hash table */
00102   size_t size;
00103 
00104   /* Current number of elements.  */
00105   size_t n_elements;
00106 
00107   /* Free function for the entries array.  This may vary depending on
00108      how early the array was allocated.  If it is NULL, then the array
00109      can't be freed.  */
00110   void (*free) (void *ptr);
00111 };
00112 
00113 inline static struct hashtab *
00114 htab_create (void)
00115 {
00116   struct hashtab *ht = malloc (sizeof (struct hashtab));
00117 
00118   if (! ht)
00119     return NULL;
00120   ht->size = 3;
00121   ht->entries = malloc (sizeof (void *) * ht->size);
00122   ht->free = free;
00123   if (! ht->entries)
00124     {
00125       if (ht->free)
00126        ht->free (ht);
00127       return NULL;
00128     }
00129 
00130   ht->n_elements = 0;
00131 
00132   memset (ht->entries, 0, sizeof (void *) * ht->size);
00133 
00134   return ht;
00135 }
00136 
00137 /* This is only called from _dl_unmap, so it's safe to call
00138    free().  */
00139 inline static void
00140 htab_delete (struct hashtab *htab)
00141 {
00142   int i;
00143 
00144   for (i = htab->size - 1; i >= 0; i--)
00145     free (htab->entries[i]);
00146 
00147   if (htab->free)
00148     htab->free (htab->entries);
00149   free (htab);
00150 }
00151 
00152 /* Similar to htab_find_slot, but without several unwanted side effects:
00153     - Does not call htab->eq_f when it finds an existing entry.
00154     - Does not change the count of elements/searches/collisions in the
00155       hash table.
00156    This function also assumes there are no deleted entries in the table.
00157    HASH is the hash value for the element to be inserted.  */
00158 
00159 inline static void **
00160 find_empty_slot_for_expand (struct hashtab *htab, int hash)
00161 {
00162   size_t size = htab->size;
00163   unsigned int index = hash % size;
00164   void **slot = htab->entries + index;
00165   int hash2;
00166 
00167   if (! *slot)
00168     return slot;
00169 
00170   hash2 = 1 + hash % (size - 2);
00171   for (;;)
00172     {
00173       index += hash2;
00174       if (index >= size)
00175        index -= size;
00176 
00177       slot = htab->entries + index;
00178       if (! *slot)
00179        return slot;
00180     }
00181 }
00182 
00183 /* The following function changes size of memory allocated for the
00184    entries and repeatedly inserts the table elements.  The occupancy
00185    of the table after the call will be about 50%.  Naturally the hash
00186    table must already exist.  Remember also that the place of the
00187    table entries is changed.  If memory allocation failures are allowed,
00188    this function will return zero, indicating that the table could not be
00189    expanded.  If all goes well, it will return a non-zero value.  */
00190 
00191 inline static int
00192 htab_expand (struct hashtab *htab, int (*hash_fn) (void *))
00193 {
00194   void **oentries;
00195   void **olimit;
00196   void **p;
00197   void **nentries;
00198   size_t nsize;
00199 
00200   oentries = htab->entries;
00201   olimit = oentries + htab->size;
00202 
00203   /* Resize only when table after removal of unused elements is either
00204      too full or too empty.  */
00205   if (htab->n_elements * 2 > htab->size)
00206     nsize = higher_prime_number (htab->n_elements * 2);
00207   else
00208     nsize = htab->size;
00209 
00210   nentries = malloc (sizeof (void *) * nsize);
00211   memset (nentries, 0, sizeof (void *) * nsize);
00212   if (nentries == NULL)
00213     return 0;
00214   htab->entries = nentries;
00215   htab->size = nsize;
00216 
00217   p = oentries;
00218   do
00219     {
00220       if (*p)
00221        *find_empty_slot_for_expand (htab, hash_fn (*p))
00222          = *p;
00223 
00224       p++;
00225     }
00226   while (p < olimit);
00227 
00228   /* Without recording the free corresponding to the malloc used to
00229      allocate the table, we couldn't tell whether this was allocated
00230      by the malloc() built into ld.so or the one in the main
00231      executable or libc.  Calling free() for something that was
00232      allocated by the early malloc(), rather than the final run-time
00233      malloc() could do Very Bad Things (TM).  We will waste memory
00234      allocated early as long as there's no corresponding free(), but
00235      this isn't so much memory as to be significant.  */
00236 
00237   if (htab->free)
00238     htab->free (oentries);
00239 
00240   /* Use the free() corresponding to the malloc() above to free this
00241      up.  */
00242   htab->free = free;
00243 
00244   return 1;
00245 }
00246 
00247 /* This function searches for a hash table slot containing an entry
00248    equal to the given element.  To delete an entry, call this with
00249    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
00250    after doing some checks).  To insert an entry, call this with
00251    INSERT = 1, then write the value you want into the returned slot.
00252    When inserting an entry, NULL may be returned if memory allocation
00253    fails.  */
00254 
00255 inline static void **
00256 htab_find_slot (struct hashtab *htab, void *ptr, int insert,
00257               int (*hash_fn)(void *), int (*eq_fn)(void *, void *))
00258 {
00259   unsigned int index;
00260   int hash, hash2;
00261   size_t size;
00262   void **entry;
00263 
00264   if (htab->size * 3 <= htab->n_elements * 4
00265       && htab_expand (htab, hash_fn) == 0)
00266     return NULL;
00267 
00268   hash = hash_fn (ptr);
00269 
00270   size = htab->size;
00271   index = hash % size;
00272 
00273   entry = &htab->entries[index];
00274   if (!*entry)
00275     goto empty_entry;
00276   else if (eq_fn (*entry, ptr))
00277     return entry;
00278 
00279   hash2 = 1 + hash % (size - 2);
00280   for (;;)
00281     {
00282       index += hash2;
00283       if (index >= size)
00284        index -= size;
00285 
00286       entry = &htab->entries[index];
00287       if (!*entry)
00288        goto empty_entry;
00289       else if (eq_fn (*entry, ptr))
00290        return entry;
00291     }
00292 
00293  empty_entry:
00294   if (!insert)
00295     return NULL;
00296 
00297   htab->n_elements++;
00298   return entry;
00299 }
00300 
00301 #endif /* INLINE_HASHTAB_H */