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