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@redhat.com>, 2000.
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.
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.
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.
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.
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>. */
54 #include <sys/cdefs.h>
55 #include <sys/param.h>
59 #define CONCAT(t1,t2) __CONCAT (t1,t2)
61 /* Before including this file the following macros must be defined:
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
71 INSERT_HASH if defined alternate insert function which takes a hash
73 NO_FINI_FCT if defined the fini function is not defined
77 /* Defined separately. */
78 extern size_t next_prime (size_t seed);
81 /* Set default values. */
83 # define HASHTYPE size_t
95 /* The data structure. */
96 struct CONCAT(PREFIX,fshash)
99 struct CONCAT(PREFIX,fshashent)
103 # define ENTRYP(el) (el).entry
106 # define ENTRYP(el) &(el).entry
113 /* Constructor for the hashing table. */
114 CLASS struct CONCAT(PREFIX,fshash) *
115 CONCAT(PREFIX,fshash_init) (size_t nelems)
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);
122 if (nelems >= (max_size_t / 3) * 2)
128 /* Adjust the size to be used for the hashing table. */
129 nelems = next_prime (MAX ((nelems * 3) / 2, 10));
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);
138 result->nslots = nelems;
146 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
153 static struct CONCAT(PREFIX,fshashent) *
154 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
155 HASHTYPE hval, TYPE *data)
157 size_t idx = 1 + hval % htab->nslots;
159 if (htab->table[idx].hval != 0)
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];
168 /* Second hash function as suggested in [Knuth]. */
169 hash = 1 + hval % (htab->nslots - 2);
174 idx = htab->nslots + idx - hash;
178 if (htab->table[idx].hval == hval
179 && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
180 return &htab->table[idx];
182 while (htab->table[idx].hval != 0);
185 return &htab->table[idx];
190 __attribute__ ((unused))
191 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
193 size_t len __attribute__ ((unused)), TYPE *data)
195 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
196 struct CONCAT(PREFIX,fshashent) *slot;
198 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
200 /* We don't want to overwrite the old value. */
216 __attribute__ ((unused))
217 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
218 HASHTYPE hval, TYPE *data)
220 struct CONCAT(PREFIX,fshashent) *slot;
222 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
224 /* We don't want to overwrite the old value. */
240 __attribute__ ((unused))
241 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
243 size_t len __attribute__ ((unused)),
246 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
247 struct CONCAT(PREFIX,fshashent) *slot;
249 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
262 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
264 size_t len __attribute__ ((unused)), TYPE *data)
266 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
267 struct CONCAT(PREFIX,fshashent) *slot;
269 slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
275 return ENTRYP(*slot);
279 /* Unset the macros we expect. */