lib/dynamicsizehash.c

   1 /* Copyright (C) 2000-2010 Red Hat, Inc.
   2    This file is part of elfutils.
   3    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
   4
   5    This file is free software; you can redistribute it and/or modify
   6    it under the terms of either
   7
   8      * the GNU Lesser General Public License as published by the Free
   9        Software Foundation; either version 3 of the License, or (at
  10        your option) any later version
  11
  12    or
  13
  14      * the GNU General Public License as published by the Free
  15        Software Foundation; either version 2 of the License, or (at
  16        your option) any later version
  17
  18    or both in parallel, as here.
  19
  20    elfutils is distributed in the hope that it will be useful, but
  21    WITHOUT ANY WARRANTY; without even the implied warranty of
  22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23    General Public License for more details.
  24
  25    You should have received copies of the GNU General Public License and
  26    the GNU Lesser General Public License along with this program.  If
  27    not, see <http://www.gnu.org/licenses/>.  */
  28
  29 #include <assert.h>
  30 #include <stdlib.h>
  31 #include <system.h>
  32
  33 /* Before including this file the following macros must be defined:
  34
  35    NAME      name of the hash table structure.
  36    TYPE      data type of the hash table entries
  37    COMPARE   comparison function taking two pointers to TYPE objects
  38
  39    The following macros if present select features:
  40
  41    ITERATE   iterating over the table entries is possible
  42    REVERSE   iterate in reverse order of insert
  43  */
  44
  45
  46 static size_t
  47 lookup (htab, hval, val)
  48      NAME *htab;
  49      HASHTYPE hval;
  50      TYPE val __attribute__ ((unused));
  51 {
  52   /* First hash function: simply take the modul but prevent zero.  */
  53   size_t idx = 1 + hval % htab->size;
  54
  55   if (htab->table[idx].hashval != 0)
  56     {
  57       HASHTYPE hash;
  58
  59       if (htab->table[idx].hashval == hval
  60           && COMPARE (htab->table[idx].data, val) == 0)
  61         return idx;
  62
  63       /* Second hash function as suggested in [Knuth].  */
  64       hash = 1 + hval % (htab->size - 2);
  65
  66       do
  67         {
  68           if (idx <= hash)
  69             idx = htab->size + idx - hash;
  70           else
  71             idx -= hash;
  72
  73           /* If entry is found use it.  */
  74           if (htab->table[idx].hashval == hval
  75               && COMPARE (htab->table[idx].data, val) == 0)
  76             return idx;
  77         }
  78       while (htab->table[idx].hashval);
  79     }
  80   return idx;
  81 }
  82
  83
  84 static void
  85 insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
  86 {
  87 #ifdef ITERATE
  88   if (htab->table[idx].hashval == 0)
  89     {
  90 # ifdef REVERSE
  91       htab->table[idx].next = htab->first;
  92       htab->first = &htab->table[idx];
  93 # else
  94       /* Add the new value to the list.  */
  95       if (htab->first == NULL)
  96         htab->first = htab->table[idx].next = &htab->table[idx];
  97       else
  98         {
  99           htab->table[idx].next = htab->first->next;
 100           htab->first = htab->first->next = &htab->table[idx];
 101         }
 102 # endif
 103     }
 104 #endif
 105
 106   htab->table[idx].hashval = hval;
 107   htab->table[idx].data = data;
 108
 109   ++htab->filled;
 110   if (100 * htab->filled > 90 * htab->size)
 111     {
 112       /* Table is filled more than 90%.  Resize the table.  */
 113 #ifdef ITERATE
 114       __typeof__ (htab->first) first;
 115 # ifndef REVERSE
 116       __typeof__ (htab->first) runp;
 117 # endif
 118 #else
 119       size_t old_size = htab->size;
 120 #endif
 121 #define _TABLE(name) \
 122       name##_ent *table = htab->table
 123 #define TABLE(name) _TABLE (name)
 124       TABLE(NAME);
 125
 126       htab->size = next_prime (htab->size * 2);
 127       htab->filled = 0;
 128 #ifdef ITERATE
 129       first = htab->first;
 130       htab->first = NULL;
 131 #endif
 132       htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
 133       if (htab->table == NULL)
 134         {
 135           /* We cannot enlarge the table.  Live with what we got.  This
 136              might lead to an infinite loop at some point, though.  */
 137           htab->table = table;
 138           return;
 139         }
 140
 141       /* Add the old entries to the new table.  When iteration is
 142          supported we maintain the order.  */
 143 #ifdef ITERATE
 144 # ifdef REVERSE
 145       while (first != NULL)
 146         {
 147           insert_entry_2 (htab, first->hashval,
 148                           lookup (htab, first->hashval, first->data),
 149                           first->data);
 150
 151           first = first->next;
 152         }
 153 # else
 154       assert (first != NULL);
 155       runp = first = first->next;
 156       do
 157         insert_entry_2 (htab, runp->hashval,
 158                         lookup (htab, runp->hashval, runp->data), runp->data);
 159       while ((runp = runp->next) != first);
 160 # endif
 161 #else
 162       for (idx = 1; idx <= old_size; ++idx)
 163         if (table[idx].hashval != 0)
 164           insert_entry_2 (htab, table[idx].hashval,
 165                           lookup (htab, table[idx].hashval, table[idx].data),
 166                           table[idx].data);
 167 #endif
 168
 169       free (table);
 170     }
 171 }
 172
 173
 174 int
 175 #define INIT(name) _INIT (name)
 176 #define _INIT(name) \
 177   name##_init
 178 INIT(NAME) (htab, init_size)
 179      NAME *htab;
 180      size_t init_size;
 181 {
 182   /* We need the size to be a prime.  */
 183   init_size = next_prime (init_size);
 184
 185   /* Initialize the data structure.  */
 186   htab->size = init_size;
 187   htab->filled = 0;
 188 #ifdef ITERATE
 189   htab->first = NULL;
 190 #endif
 191   htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
 192   if (htab->table == NULL)
 193     return -1;
 194
 195   return 0;
 196 }
 197
 198
 199 int
 200 #define FREE(name) _FREE (name)
 201 #define _FREE(name) \
 202   name##_free
 203 FREE(NAME) (htab)
 204      NAME *htab;
 205 {
 206   free (htab->table);
 207   return 0;
 208 }
 209
 210
 211 int
 212 #define INSERT(name) _INSERT (name)
 213 #define _INSERT(name) \
 214   name##_insert
 215 INSERT(NAME) (htab, hval, data)
 216      NAME *htab;
 217      HASHTYPE hval;
 218      TYPE data;
 219 {
 220   size_t idx;
 221
 222   /* Make the hash value nonzero.  */
 223   hval = hval ?: 1;
 224
 225   idx = lookup (htab, hval, data);
 226
 227   if (htab->table[idx].hashval != 0)
 228     /* We don't want to overwrite the old value.  */
 229     return -1;
 230
 231   /* An empty bucket has been found.  */
 232   insert_entry_2 (htab, hval, idx, data);
 233   return 0;
 234 }
 235
 236
 237 #ifdef OVERWRITE
 238 int
 239 #define INSERT(name) _INSERT (name)
 240 #define _INSERT(name) \
 241   name##_overwrite
 242 INSERT(NAME) (htab, hval, data)
 243      NAME *htab;
 244      HASHTYPE hval;
 245      TYPE data;
 246 {
 247   size_t idx;
 248
 249   /* Make the hash value nonzero.  */
 250   hval = hval ?: 1;
 251
 252   idx = lookup (htab, hval, data);
 253
 254   /* The correct bucket has been found.  */
 255   insert_entry_2 (htab, hval, idx, data);
 256   return 0;
 257 }
 258 #endif
 259
 260
 261 TYPE
 262 #define FIND(name) _FIND (name)
 263 #define _FIND(name) \
 264   name##_find
 265 FIND(NAME) (htab, hval, val)
 266      NAME *htab;
 267      HASHTYPE hval;
 268      TYPE val;
 269 {
 270   size_t idx;
 271
 272   /* Make the hash value nonzero.  */
 273   hval = hval ?: 1;
 274
 275   idx = lookup (htab, hval, val);
 276
 277   if (htab->table[idx].hashval == 0)
 278     return NULL;
 279
 280   return htab->table[idx].data;
 281 }
 282
 283
 284 #ifdef ITERATE
 285 # define ITERATEFCT(name) _ITERATEFCT (name)
 286 # define _ITERATEFCT(name) \
 287   name##_iterate
 288 TYPE
 289 ITERATEFCT(NAME) (htab, ptr)
 290      NAME *htab;
 291      void **ptr;
 292 {
 293   void *p = *ptr;
 294
 295 # define TYPENAME(name) _TYPENAME (name)
 296 # define _TYPENAME(name) name##_ent
 297
 298 # ifdef REVERSE
 299   if (p == NULL)
 300     p = htab->first;
 301   else
 302     p = ((TYPENAME(NAME) *) p)->next;
 303
 304   if (p == NULL)
 305     {
 306       *ptr = NULL;
 307       return NULL;
 308     }
 309 # else
 310   if (p == NULL)
 311     {
 312       if (htab->first == NULL)
 313         return NULL;
 314       p = htab->first->next;
 315     }
 316   else
 317     {
 318       if (p == htab->first)
 319         return NULL;
 320
 321       p = ((TYPENAME(NAME) *) p)->next;
 322     }
 323 # endif
 324
 325   /* Prepare the next element.  If possible this will pull the data
 326      into the cache, for reading.  */
 327   __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
 328
 329   return ((TYPENAME(NAME) *) (*ptr = p))->data;
 330 }
 331 #endif