lib/dynamicsizehash.c

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