lib/fixedsizehash.h

   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 elfutils.
   4    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
   5
   6    This file is free software; you can redistribute it and/or modify
   7    it under the terms of either
   8
   9      * the GNU Lesser General Public License as published by the Free
  10        Software Foundation; either version 3 of the License, or (at
  11        your option) any later version
  12
  13    or
  14
  15      * the GNU General Public License as published by the Free
  16        Software Foundation; either version 2 of the License, or (at
  17        your option) any later version
  18
  19    or both in parallel, as here.
  20
  21    elfutils is distributed in the hope that it will be useful, but
  22    WITHOUT ANY WARRANTY; without even the implied warranty of
  23    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  24    General Public License for more details.
  25
  26    You should have received copies of the GNU General Public License and
  27    the GNU Lesser General Public License along with this program.  If
  28    not, see <http://www.gnu.org/licenses/>.  */
  29
  30 #include <errno.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <sys/cdefs.h>
  34 #include <sys/param.h>
  35
  36 #include <system.h>
  37
  38 #define CONCAT(t1,t2) __CONCAT (t1,t2)
  39
  40 /* Before including this file the following macros must be defined:
  41
  42    TYPE           data type of the hash table entries
  43    HASHFCT        name of the hashing function to use
  44    HASHTYPE       type used for the hashing value
  45    COMPARE        comparison function taking two pointers to TYPE objects
  46    CLASS          can be defined to `static' to avoid exporting the functions
  47    PREFIX         prefix to be used for function and data type names
  48    STORE_POINTER  if defined the table stores a pointer and not an element
  49                   of type TYPE
  50    INSERT_HASH    if defined alternate insert function which takes a hash
  51                   value is defined
  52    NO_FINI_FCT    if defined the fini function is not defined
  53 */
  54
  55
  56 /* Defined separately.  */
  57 extern size_t next_prime (size_t seed);
  58
  59
  60 /* Set default values.  */
  61 #ifndef HASHTYPE
  62 # define HASHTYPE size_t
  63 #endif
  64
  65 #ifndef CLASS
  66 # define CLASS
  67 #endif
  68
  69 #ifndef PREFIX
  70 # define PREFIX
  71 #endif
  72
  73
  74 /* The data structure.  */
  75 struct CONCAT(PREFIX,fshash)
  76 {
  77   size_t nslots;
  78   struct CONCAT(PREFIX,fshashent)
  79   {
  80     HASHTYPE hval;
  81 #ifdef STORE_POINTER
  82 # define ENTRYP(el) (el).entry
  83     TYPE *entry;
  84 #else
  85 # define ENTRYP(el) &(el).entry
  86     TYPE entry;
  87 #endif
  88   } table[0];
  89 };
  90
  91
  92 /* Constructor for the hashing table.  */
  93 CLASS struct CONCAT(PREFIX,fshash) *
  94 CONCAT(PREFIX,fshash_init) (size_t nelems)
  95 {
  96   struct CONCAT(PREFIX,fshash) *result;
  97   /* We choose a size for the hashing table 150% over the number of
  98      entries.  This will guarantee short medium search lengths.  */
  99   const size_t max_size_t = ~((size_t) 0);
 100
 101   if (nelems >= (max_size_t / 3) * 2)
 102     {
 103       errno = EINVAL;
 104       return NULL;
 105     }
 106
 107   /* Adjust the size to be used for the hashing table.  */
 108   nelems = next_prime (MAX ((nelems * 3) / 2, 10));
 109
 110   /* Allocate the data structure for the result.  */
 111   result = (struct CONCAT(PREFIX,fshash) *)
 112     xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
 113              + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
 114   if (result == NULL)
 115     return NULL;
 116
 117   result->nslots = nelems;
 118
 119   return result;
 120 }
 121
 122
 123 #ifndef NO_FINI_FCT
 124 CLASS void
 125 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
 126 {
 127   free (htab);
 128 }
 129 #endif
 130
 131
 132 static struct CONCAT(PREFIX,fshashent) *
 133 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
 134                               HASHTYPE hval, TYPE *data)
 135 {
 136   size_t idx = 1 + hval % htab->nslots;
 137
 138   if (htab->table[idx].hval != 0)
 139     {
 140       HASHTYPE hash;
 141
 142       /* See whether this is the same entry.  */
 143       if (htab->table[idx].hval == hval
 144           && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
 145         return &htab->table[idx];
 146
 147       /* Second hash function as suggested in [Knuth].  */
 148       hash = 1 + hval % (htab->nslots - 2);
 149
 150       do
 151         {
 152           if (idx <= hash)
 153             idx = htab->nslots + idx - hash;
 154           else
 155             idx -= hash;
 156
 157           if (htab->table[idx].hval == hval
 158               && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
 159             return &htab->table[idx];
 160         }
 161       while (htab->table[idx].hval != 0);
 162     }
 163
 164   return &htab->table[idx];
 165 }
 166
 167
 168 CLASS int
 169 __attribute__ ((unused))
 170 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
 171                               const char *str,
 172                               size_t len __attribute__ ((unused)), TYPE *data)
 173 {
 174   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
 175   struct CONCAT(PREFIX,fshashent) *slot;
 176
 177   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
 178  if (slot->hval != 0)
 179     /* We don't want to overwrite the old value.  */
 180     return -1;
 181
 182   slot->hval = hval;
 183 #ifdef STORE_POINTER
 184   slot->entry = data;
 185 #else
 186   slot->entry = *data;
 187 #endif
 188
 189   return 0;
 190 }
 191
 192
 193 #ifdef INSERT_HASH
 194 CLASS int
 195 __attribute__ ((unused))
 196 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
 197                                    HASHTYPE hval, TYPE *data)
 198 {
 199   struct CONCAT(PREFIX,fshashent) *slot;
 200
 201   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
 202   if (slot->hval != 0)
 203     /* We don't want to overwrite the old value.  */
 204     return -1;
 205
 206   slot->hval = hval;
 207 #ifdef STORE_POINTER
 208   slot->entry = data;
 209 #else
 210   slot->entry = *data;
 211 #endif
 212
 213   return 0;
 214 }
 215 #endif
 216
 217
 218 CLASS int
 219 __attribute__ ((unused))
 220 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
 221                                  const char *str,
 222                                  size_t len __attribute__ ((unused)),
 223                                  TYPE *data)
 224 {
 225   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
 226   struct CONCAT(PREFIX,fshashent) *slot;
 227
 228   slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
 229   slot->hval = hval;
 230 #ifdef STORE_POINTER
 231   slot->entry = data;
 232 #else
 233   slot->entry = *data;
 234 #endif
 235
 236   return 0;
 237 }
 238
 239
 240 CLASS const TYPE *
 241 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
 242                             const char *str,
 243                             size_t len __attribute__ ((unused)), TYPE *data)
 244 {
 245   HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
 246   struct CONCAT(PREFIX,fshashent) *slot;
 247
 248   slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
 249                                        hval, data);
 250   if (slot->hval == 0)
 251     /* Not found.  */
 252     return NULL;
 253
 254   return ENTRYP(*slot);
 255 }
 256
 257
 258 /* Unset the macros we expect.  */
 259 #undef TYPE
 260 #undef HASHFCT
 261 #undef HASHTYPE
 262 #undef COMPARE
 263 #undef CLASS
 264 #undef PREFIX
 265 #undef INSERT_HASH
 266 #undef STORE_POINTER
 267 #undef NO_FINI_FCT