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