Home | History | Annotate | Download | only in lib
      1 /* Copyright (C) 2000-2010 Red Hat, Inc.
      2    This file is part of Red Hat elfutils.
      3    Written by Ulrich Drepper <drepper (at) 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
    353