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.  Small values
  53      can skip the division, which helps performance when this is common.  */
  54   size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
  55
  56   if (htab->table[idx].hashval != 0)
  57     {
  58       HASHTYPE hash;
  59
  60       if (htab->table[idx].hashval == hval
  61           && COMPARE (htab->table[idx].data, val) == 0)
  62         return idx;
  63
  64       /* Second hash function as suggested in [Knuth].  */
  65       hash = 1 + hval % (htab->size - 2);
  66
  67       do
  68         {
  69           if (idx <= hash)
  70             idx = htab->size + idx - hash;
  71           else
  72             idx -= hash;
  73
  74           /* If entry is found use it.  */
  75           if (htab->table[idx].hashval == hval
  76               && COMPARE (htab->table[idx].data, val) == 0)
  77             return idx;
  78         }
  79       while (htab->table[idx].hashval);
  80     }
  81   return idx;
  82 }
  83
  84
  85 static void
  86 insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
  87 {
  88 #ifdef ITERATE
  89   if (htab->table[idx].hashval == 0)
  90     {
  91 # ifdef REVERSE
  92       htab->table[idx].next = htab->first;
  93       htab->first = &htab->table[idx];
  94 # else
  95       /* Add the new value to the list.  */
  96       if (htab->first == NULL)
  97         htab->first = htab->table[idx].next = &htab->table[idx];
  98       else
  99         {
 100           htab->table[idx].next = htab->first->next;
 101           htab->first = htab->first->next = &htab->table[idx];
 102         }
 103 # endif
 104     }
 105 #endif
 106
 107   htab->table[idx].hashval = hval;
 108   htab->table[idx].data = data;
 109
 110   ++htab->filled;
 111   if (100 * htab->filled > 90 * htab->size)
 112     {
 113       /* Table is filled more than 90%.  Resize the table.  */
 114 #ifdef ITERATE
 115       __typeof__ (htab->first) first;
 116 # ifndef REVERSE
 117       __typeof__ (htab->first) runp;
 118 # endif
 119 #else
 120       size_t old_size = htab->size;
 121 #endif
 122 #define _TABLE(name) \
 123       name##_ent *table = htab->table
 124 #define TABLE(name) _TABLE (name)
 125       TABLE(NAME);
 126
 127       htab->size = next_prime (htab->size * 2);
 128       htab->filled = 0;
 129 #ifdef ITERATE
 130       first = htab->first;
 131       htab->first = NULL;
 132 #endif
 133       htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
 134       if (htab->table == NULL)
 135         {
 136           /* We cannot enlarge the table.  Live with what we got.  This
 137              might lead to an infinite loop at some point, though.  */
 138           htab->table = table;
 139           return;
 140         }
 141
 142       /* Add the old entries to the new table.  When iteration is
 143          supported we maintain the order.  */
 144 #ifdef ITERATE
 145 # ifdef REVERSE
 146       while (first != NULL)
 147         {
 148           insert_entry_2 (htab, first->hashval,
 149                           lookup (htab, first->hashval, first->data),
 150                           first->data);
 151
 152           first = first->next;
 153         }
 154 # else
 155       assert (first != NULL);
 156       runp = first = first->next;
 157       do
 158         insert_entry_2 (htab, runp->hashval,
 159                         lookup (htab, runp->hashval, runp->data), runp->data);
 160       while ((runp = runp->next) != first);
 161 # endif
 162 #else
 163       for (idx = 1; idx <= old_size; ++idx)
 164         if (table[idx].hashval != 0)
 165           insert_entry_2 (htab, table[idx].hashval,
 166                           lookup (htab, table[idx].hashval, table[idx].data),
 167                           table[idx].data);
 168 #endif
 169
 170       free (table);
 171     }
 172 }
 173
 174
 175 int
 176 #define INIT(name) _INIT (name)
 177 #define _INIT(name) \
 178   name##_init
 179 INIT(NAME) (htab, init_size)
 180      NAME *htab;
 181      size_t init_size;
 182 {
 183   /* We need the size to be a prime.  */
 184   init_size = next_prime (init_size);
 185
 186   /* Initialize the data structure.  */
 187   htab->size = init_size;
 188   htab->filled = 0;
 189 #ifdef ITERATE
 190   htab->first = NULL;
 191 #endif
 192   htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
 193   if (htab->table == NULL)
 194     return -1;
 195
 196   return 0;
 197 }
 198
 199
 200 int
 201 #define FREE(name) _FREE (name)
 202 #define _FREE(name) \
 203   name##_free
 204 FREE(NAME) (htab)
 205      NAME *htab;
 206 {
 207   free (htab->table);
 208   return 0;
 209 }
 210
 211
 212 int
 213 #define INSERT(name) _INSERT (name)
 214 #define _INSERT(name) \
 215   name##_insert
 216 INSERT(NAME) (htab, hval, data)
 217      NAME *htab;
 218      HASHTYPE hval;
 219      TYPE data;
 220 {
 221   size_t idx;
 222
 223   /* Make the hash value nonzero.  */
 224   hval = hval ?: 1;
 225
 226   idx = lookup (htab, hval, data);
 227
 228   if (htab->table[idx].hashval != 0)
 229     /* We don't want to overwrite the old value.  */
 230     return -1;
 231
 232   /* An empty bucket has been found.  */
 233   insert_entry_2 (htab, hval, idx, data);
 234   return 0;
 235 }
 236
 237
 238 #ifdef OVERWRITE
 239 int
 240 #define INSERT(name) _INSERT (name)
 241 #define _INSERT(name) \
 242   name##_overwrite
 243 INSERT(NAME) (htab, hval, data)
 244      NAME *htab;
 245      HASHTYPE hval;
 246      TYPE data;
 247 {
 248   size_t idx;
 249
 250   /* Make the hash value nonzero.  */
 251   hval = hval ?: 1;
 252
 253   idx = lookup (htab, hval, data);
 254
 255   /* The correct bucket has been found.  */
 256   insert_entry_2 (htab, hval, idx, data);
 257   return 0;
 258 }
 259 #endif
 260
 261
 262 TYPE
 263 #define FIND(name) _FIND (name)
 264 #define _FIND(name) \
 265   name##_find
 266 FIND(NAME) (htab, hval, val)
 267      NAME *htab;
 268      HASHTYPE hval;
 269      TYPE val;
 270 {
 271   size_t idx;
 272
 273   /* Make the hash value nonzero.  */
 274   hval = hval ?: 1;
 275
 276   idx = lookup (htab, hval, val);
 277
 278   if (htab->table[idx].hashval == 0)
 279     return NULL;
 280
 281   return htab->table[idx].data;
 282 }
 283
 284
 285 #ifdef ITERATE
 286 # define ITERATEFCT(name) _ITERATEFCT (name)
 287 # define _ITERATEFCT(name) \
 288   name##_iterate
 289 TYPE
 290 ITERATEFCT(NAME) (htab, ptr)
 291      NAME *htab;
 292      void **ptr;
 293 {
 294   void *p = *ptr;
 295
 296 # define TYPENAME(name) _TYPENAME (name)
 297 # define _TYPENAME(name) name##_ent
 298
 299 # ifdef REVERSE
 300   if (p == NULL)
 301     p = htab->first;
 302   else
 303     p = ((TYPENAME(NAME) *) p)->next;
 304
 305   if (p == NULL)
 306     {
 307       *ptr = NULL;
 308       return NULL;
 309     }
 310 # else
 311   if (p == NULL)
 312     {
 313       if (htab->first == NULL)
 314         return NULL;
 315       p = htab->first->next;
 316     }
 317   else
 318     {
 319       if (p == htab->first)
 320         return NULL;
 321
 322       p = ((TYPENAME(NAME) *) p)->next;
 323     }
 324 # endif
 325
 326   /* Prepare the next element.  If possible this will pull the data
 327      into the cache, for reading.  */
 328   __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
 329
 330   return ((TYPENAME(NAME) *) (*ptr = p))->data;
 331 }
 332 #endif