Home | History | Annotate | Download | only in lib
      1 /* Fixed size hash table with internal linking.
      2    Copyright (C) 2000, 2001, 2002, 2004, 2005 Red Hat, Inc.
      3    This file is part of Red Hat elfutils.
      4    Written by Ulrich Drepper <drepper (at) redhat.com>, 2000.
      5 
      6    Red Hat elfutils is free software; you can redistribute it and/or modify
      7    it under the terms of the GNU General Public License as published by the
      8    Free Software Foundation; version 2 of the License.
      9 
     10    Red Hat elfutils is distributed in the hope that it will be useful, but
     11    WITHOUT ANY WARRANTY; without even the implied warranty of
     12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     13    General Public License for more details.
     14 
     15    You should have received a copy of the GNU General Public License along
     16    with Red Hat elfutils; if not, write to the Free Software Foundation,
     17    Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
     18 
     19    In addition, as a special exception, Red Hat, Inc. gives You the
     20    additional right to link the code of Red Hat elfutils with code licensed
     21    under any Open Source Initiative certified open source license
     22    (http://www.opensource.org/licenses/index.php) which requires the
     23    distribution of source code with any binary distribution and to
     24    distribute linked combinations of the two.  Non-GPL Code permitted under
     25    this exception must only link to the code of Red Hat elfutils through
     26    those well defined interfaces identified in the file named EXCEPTION
     27    found in the source code files (the "Approved Interfaces").  The files
     28    of Non-GPL Code may instantiate templates or use macros or inline
     29    functions from the Approved Interfaces without causing the resulting
     30    work to be covered by the GNU General Public License.  Only Red Hat,
     31    Inc. may make changes or additions to the list of Approved Interfaces.
     32    Red Hat's grant of this exception is conditioned upon your not adding
     33    any new exceptions.  If you wish to add a new Approved Interface or
     34    exception, please contact Red Hat.  You must obey the GNU General Public
     35    License in all respects for all of the Red Hat elfutils code and other
     36    code used in conjunction with Red Hat elfutils except the Non-GPL Code
     37    covered by this exception.  If you modify this file, you may extend this
     38    exception to your version of the file, but you are not obligated to do
     39    so.  If you do not wish to provide this exception without modification,
     40    you must delete this exception statement from your version and license
     41    this file solely under the GPL without exception.
     42 
     43    Red Hat elfutils is an included package of the Open Invention Network.
     44    An included package of the Open Invention Network is a package for which
     45    Open Invention Network licensees cross-license their patents.  No patent
     46    license is granted, either expressly or impliedly, by designation as an
     47    included package.  Should you wish to participate in the Open Invention
     48    Network licensing program, please visit www.openinventionnetwork.com
     49    <http://www.openinventionnetwork.com>.  */
     50 
     51 #include <errno.h>
     52 #include <stdlib.h>
     53 #include <string.h>
     54 #include <sys/cdefs.h>
     55 #include <sys/param.h>
     56 
     57 #include <system.h>
     58 
     59 #define CONCAT(t1,t2) __CONCAT (t1,t2)
     60 
     61 /* Before including this file the following macros must be defined:
     62 
     63    TYPE           data type of the hash table entries
     64    HASHFCT        name of the hashing function to use
     65    HASHTYPE       type used for the hashing value
     66    COMPARE        comparison function taking two pointers to TYPE objects
     67    CLASS          can be defined to `static' to avoid exporting the functions
     68    PREFIX         prefix to be used for function and data type names
     69    STORE_POINTER  if defined the table stores a pointer and not an element
     70                   of type TYPE
     71    INSERT_HASH    if defined alternate insert function which takes a hash
     72                   value is defined
     73    NO_FINI_FCT    if defined the fini function is not defined
     74 */
     75 
     76 
     77 /* Defined separately.  */
     78 extern size_t next_prime (size_t seed);
     79 
     80 
     81 /* Set default values.  */
     82 #ifndef HASHTYPE
     83 # define HASHTYPE size_t
     84 #endif
     85 
     86 #ifndef CLASS
     87 # define CLASS
     88 #endif
     89 
     90 #ifndef PREFIX
     91 # define PREFIX
     92 #endif
     93 
     94 
     95 /* The data structure.  */
     96 struct CONCAT(PREFIX,fshash)
     97 {
     98   size_t nslots;
     99   struct CONCAT(PREFIX,fshashent)
    100   {
    101     HASHTYPE hval;
    102 #ifdef STORE_POINTER
    103 # define ENTRYP(el) (el).entry
    104     TYPE *entry;
    105 #else
    106 # define ENTRYP(el) &(el).entry
    107     TYPE entry;
    108 #endif
    109   } table[0];
    110 };
    111 
    112 
    113 /* Constructor for the hashing table.  */
    114 CLASS struct CONCAT(PREFIX,fshash) *
    115 CONCAT(PREFIX,fshash_init) (size_t nelems)
    116 {
    117   struct CONCAT(PREFIX,fshash) *result;
    118   /* We choose a size for the hashing table 150% over the number of
    119      entries.  This will guarantee short medium search lengths.  */
    120   const size_t max_size_t = ~((size_t) 0);
    121 
    122   if (nelems >= (max_size_t / 3) * 2)
    123     {
    124       errno = EINVAL;
    125       return NULL;
    126     }
    127 
    128   /* Adjust the size to be used for the hashing table.  */
    129   nelems = next_prime (MAX ((nelems * 3) / 2, 10));
    130 
    131   /* Allocate the data structure for the result.  */
    132   result = (struct CONCAT(PREFIX,fshash) *)
    133     xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
    134 	     + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
    135   if (result == NULL)
    136     return NULL;
    137 
    138   result->nslots = nelems;
    139 
    140   return result;
    141 }
    142 
    143 
    144 #ifndef NO_FINI_FCT
    145 CLASS void
    146 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
    147 {
    148   free (htab);
    149 }
    150 #endif
    151 
    152 
    153 static struct CONCAT(PREFIX,fshashent) *
    154 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
    155 			      HASHTYPE hval, TYPE *data)
    156 {
    157   size_t idx = 1 + hval % htab->nslots;
    158 
    159   if (htab->table[idx].hval != 0)
    160     {
    161       HASHTYPE hash;
    162 
    163       /* See whether this is the same entry.  */
    164       if (htab->table[idx].hval == hval
    165 	  && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
    166 	return &htab->table[idx];
    167 
    168       /* Second hash function as suggested in [Knuth].  */
    169       hash = 1 + hval % (htab->nslots - 2);
    170 
    171       do
    172 	{
    173 	  if (idx <= hash)
    174 	    idx = htab->nslots + idx - hash;
    175 	  else
    176 	    idx -= hash;
    177 
    178 	  if (htab->table[idx].hval == hval
    179 	      && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
    180 	    return &htab->table[idx];
    181 	}
    182       while (htab->table[idx].hval != 0);
    183     }
    184 
    185   return &htab->table[idx];
    186 }
    187 
    188 
    189 CLASS int
    190 __attribute__ ((unused))
    191 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
    192 			      const char *str,
    193 			      size_t len __attribute__ ((unused)), TYPE *data)
    194 {
    195   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
    196   struct CONCAT(PREFIX,fshashent) *slot;
    197 
    198   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
    199  if (slot->hval != 0)
    200     /* We don't want to overwrite the old value.  */
    201     return -1;
    202 
    203   slot->hval = hval;
    204 #ifdef STORE_POINTER
    205   slot->entry = data;
    206 #else
    207   slot->entry = *data;
    208 #endif
    209 
    210   return 0;
    211 }
    212 
    213 
    214 #ifdef INSERT_HASH
    215 CLASS int
    216 __attribute__ ((unused))
    217 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
    218 				   HASHTYPE hval, TYPE *data)
    219 {
    220   struct CONCAT(PREFIX,fshashent) *slot;
    221 
    222   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
    223   if (slot->hval != 0)
    224     /* We don't want to overwrite the old value.  */
    225     return -1;
    226 
    227   slot->hval = hval;
    228 #ifdef STORE_POINTER
    229   slot->entry = data;
    230 #else
    231   slot->entry = *data;
    232 #endif
    233 
    234   return 0;
    235 }
    236 #endif
    237 
    238 
    239 CLASS int
    240 __attribute__ ((unused))
    241 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
    242 				 const char *str,
    243 				 size_t len __attribute__ ((unused)),
    244 				 TYPE *data)
    245 {
    246   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
    247   struct CONCAT(PREFIX,fshashent) *slot;
    248 
    249   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
    250   slot->hval = hval;
    251 #ifdef STORE_POINTER
    252   slot->entry = data;
    253 #else
    254   slot->entry = *data;
    255 #endif
    256 
    257   return 0;
    258 }
    259 
    260 
    261 CLASS const TYPE *
    262 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
    263 			    const char *str,
    264 			    size_t len __attribute__ ((unused)), TYPE *data)
    265 {
    266   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
    267   struct CONCAT(PREFIX,fshashent) *slot;
    268 
    269   slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
    270 				       hval, data);
    271   if (slot->hval == 0)
    272     /* Not found.  */
    273     return NULL;
    274 
    275   return ENTRYP(*slot);
    276 }
    277 
    278 
    279 /* Unset the macros we expect.  */
    280 #undef TYPE
    281 #undef HASHFCT
    282 #undef HASHTYPE
    283 #undef COMPARE
    284 #undef CLASS
    285 #undef PREFIX
    286 #undef INSERT_HASH
    287 #undef STORE_POINTER
    288 #undef NO_FINI_FCT
    289