1/* Copyright (C) 1993, 1995, 1996, 1997 Free Software Foundation, Inc.
2   This file is part of the GNU C Library.
3   Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
4
5   The GNU C Library is free software; you can redistribute it and/or
6   modify it under the terms of the GNU Lesser General Public License as
7   published by the Free Software Foundation; either version 2.1 of the
8   License, or (at your option) any later version.
9
10   The GNU C Library is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   Lesser General Public License for more details.
14
15   You should have received a copy of the GNU Lesser General Public
16   License along with the GNU C Library; see the file COPYING.LIB.  If not,
17   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18   Boston, MA 02111-1307, USA.  */
19
20#include <errno.h>
21#include <malloc.h>
22#include <string.h>
23
24#define __USE_GNU
25#ifndef __set_errno
26#define __set_errno(e) errno = (e)
27#endif
28#include <search.h>
29
30/* [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
31   [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
32
33
34/* The reentrant version has no static variables to maintain the state.
35   Instead the interface of all functions is extended to take an argument
36   which describes the current status.  */
37typedef struct _ENTRY
38{
39  unsigned int used;
40  ENTRY entry;
41}
42_ENTRY;
43
44
45/* For the used double hash method the table size has to be a prime. To
46   correct the user given table size we need a prime test.  This trivial
47   algorithm is adequate because
48   a)  the code is (most probably) called a few times per program run and
49   b)  the number is small because the table must fit in the core  */
50static int
51isprime (unsigned int number)
52{
53  /* no even number will be passed */
54  unsigned int div = 3;
55
56  while (div * div < number && number % div != 0)
57    div += 2;
58
59  return number % div != 0;
60}
61
62
63/* Before using the hash table we must allocate memory for it.
64   Test for an existing table are done. We allocate one element
65   more as the found prime number says. This is done for more effective
66   indexing as explained in the comment for the hsearch function.
67   The contents of the table is zeroed, especially the field used
68   becomes zero.  */
69int
70hcreate_r (nel, htab)
71     size_t nel;
72     struct hsearch_data *htab;
73{
74  /* Test for correct arguments.  */
75  if (htab == NULL)
76    {
77      __set_errno (EINVAL);
78      return 0;
79    }
80
81  /* There is still another table active. Return with error. */
82  if (htab->table != NULL)
83    return 0;
84
85  /* Change nel to the first prime number not smaller as nel. */
86  nel |= 1;      /* make odd */
87  while (!isprime (nel))
88    nel += 2;
89
90  htab->size = nel;
91  htab->filled = 0;
92
93  /* allocate memory and zero out */
94  htab->table = (_ENTRY *) calloc (htab->size + 1, sizeof (_ENTRY));
95  if (htab->table == NULL)
96    return 0;
97
98  /* everything went alright */
99  return 1;
100}
101
102
103/* After using the hash table it has to be destroyed. The used memory can
104   be freed and the local static variable can be marked as not used.  */
105void
106hdestroy_r (htab)
107     struct hsearch_data *htab;
108{
109  /* Test for correct arguments.  */
110  if (htab == NULL)
111    {
112      __set_errno (EINVAL);
113      return;
114    }
115
116  if (htab->table != NULL)
117    /* free used memory */
118    free (htab->table);
119
120  /* the sign for an existing table is an value != NULL in htable */
121  htab->table = NULL;
122}
123
124
125/* This is the search function. It uses double hashing with open addressing.
126   The argument item.key has to be a pointer to an zero terminated, most
127   probably strings of chars. The function for generating a number of the
128   strings is simple but fast. It can be replaced by a more complex function
129   like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
130
131   We use an trick to speed up the lookup. The table is created by hcreate
132   with one more element available. This enables us to use the index zero
133   special. This index will never be used because we store the first hash
134   index in the field used where zero means not used. Every other value
135   means used. The used field can be used as a first fast comparison for
136   equality of the stored and the parameter value. This helps to prevent
137   unnecessary expensive calls of strcmp.  */
138int
139hsearch_r (item, action, retval, htab)
140     ENTRY item;
141     ACTION action;
142     ENTRY **retval;
143     struct hsearch_data *htab;
144{
145  unsigned int hval;
146  unsigned int count;
147  unsigned int len = strlen (item.key);
148  unsigned int idx;
149
150  /* Compute an value for the given string. Perhaps use a better method. */
151  hval = len;
152  count = len;
153  while (count-- > 0)
154    {
155      hval <<= 4;
156      hval += item.key[count];
157    }
158
159  /* First hash function: simply take the modulo but prevent zero. */
160  hval %= htab->size;
161  if (hval == 0)
162    ++hval;
163
164  /* The first index tried. */
165  idx = hval;
166
167  if (htab->table[idx].used)
168    {
169      /* Further action might be required according to the action value. */
170      unsigned hval2;
171
172      if (htab->table[idx].used == hval
173	  && strcmp (item.key, htab->table[idx].entry.key) == 0)
174	{
175          if (action == ENTER)
176	    htab->table[idx].entry.data = item.data;
177
178	  *retval = &htab->table[idx].entry;
179	  return 1;
180	}
181
182      /* Second hash function, as suggested in [Knuth] */
183      hval2 = 1 + hval % (htab->size - 2);
184
185      do
186	{
187	  /* Because SIZE is prime this guarantees to step through all
188             available indexes.  */
189          if (idx <= hval2)
190	    idx = htab->size + idx - hval2;
191	  else
192	    idx -= hval2;
193
194	  /* If we visited all entries leave the loop unsuccessfully.  */
195	  if (idx == hval)
196	    break;
197
198            /* If entry is found use it. */
199          if (htab->table[idx].used == hval
200	      && strcmp (item.key, htab->table[idx].entry.key) == 0)
201	    {
202              if (action == ENTER)
203	        htab->table[idx].entry.data = item.data;
204
205	      *retval = &htab->table[idx].entry;
206	      return 1;
207	    }
208	}
209      while (htab->table[idx].used);
210    }
211
212  /* An empty bucket has been found. */
213  if (action == ENTER)
214    {
215      /* If table is full and another entry should be entered return
216	 with error.  */
217      if (action == ENTER && htab->filled == htab->size)
218	{
219	  __set_errno (ENOMEM);
220	  *retval = NULL;
221	  return 0;
222	}
223
224      htab->table[idx].used  = hval;
225      htab->table[idx].entry = item;
226
227      ++htab->filled;
228
229      *retval = &htab->table[idx].entry;
230      return 1;
231    }
232
233  __set_errno (ESRCH);
234  *retval = NULL;
235  return 0;
236}
237