1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* File....: hash.c */
4 /* Name....: Hash Functions */
5 /* Author..: Thorsten Koch */
6 /* Copyright by Author, All rights reserved */
7 /* */
8 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
9 /*
10 * Copyright (C) 2001-2018 by Thorsten Koch <koch@zib.de>
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public License
14 * as published by the Free Software Foundation; either version 3
15 * of the License, or (at your option) any later version.
16 *
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Lesser General Public License for more details.
21 *
22 * You should have received a copy of the GNU Lesser General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
25 */
26
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <assert.h>
31
32 #include <stdbool.h>
33 #include "zimpl/mshell.h"
34 #include "zimpl/blkmem.h"
35 #include "zimpl/ratlptypes.h"
36 #include "zimpl/numb.h"
37 #include "zimpl/elem.h"
38 #include "zimpl/tuple.h"
39 #include "zimpl/mme.h"
40 #include "zimpl/set.h"
41 #include "zimpl/symbol.h"
42 #include "zimpl/entry.h"
43 #include "zimpl/mono.h"
44 #include "zimpl/hash.h"
45
46 #define HASH_SID 0x48617368
47
48 typedef struct hash_element HElem;
49 typedef struct set_elem_idx SetElemIdx;
50
51 struct set_elem_idx
52 {
53 const Elem* elem;
54 int idx;
55 };
56
57 struct hash_element
58 {
59 union
60 {
61 const Tuple* tuple;
62 const Entry* entry;
63 SetElemIdx elem_idx;
64 const Numb* numb;
65 const Mono* mono;
66 } value;
67 HElem* next;
68 };
69
70 struct hash
71 {
72 SID
73 unsigned int size;
74 int elems;
75 HashType type;
76 HElem** bucket;
77 };
78
79 static void hash_statist(FILE* fp, const Hash* hash);
80
hash_is_valid(const Hash * hash)81 static bool hash_is_valid(const Hash* hash)
82 {
83 return ((hash != NULL)
84 && (hash->type == HASH_TUPLE || hash->type == HASH_ENTRY
85 || hash->type == HASH_ELEM_IDX || hash->type == HASH_NUMB
86 || hash->type == HASH_MONO)
87 && SID_ok(hash, HASH_SID));
88 }
89
hash_new(HashType type,int size)90 Hash* hash_new(HashType type, int size)
91 {
92 static const unsigned int bucket_size[] =
93 {
94 53U, 103U, 503U, 1009U, 5003U, 10007U, 50021U, 100003U, 500009U, 1000003U,
95 5000011U, 10000019U, 50000017U, 0U
96 };
97
98 Hash* hash = calloc(1, sizeof(*hash));
99 int i;
100
101 assert(hash != NULL);
102 assert(size >= 0);
103
104 /* This is a linear search, but if the number of elements is large,
105 * it will hardly matter ;-)
106 */
107 for(i = 0; bucket_size[i] < (unsigned int)size && bucket_size[i + 1] != 0; i++)
108 ;
109
110 hash->size = bucket_size[i];
111
112 assert(hash->size > 11);
113
114 hash->elems = 0;
115 hash->type = type;
116 hash->bucket = calloc(hash->size, sizeof(*hash->bucket));
117
118 assert(hash->bucket != NULL);
119
120 SID_set(hash, HASH_SID);
121 assert(hash_is_valid(hash));
122
123 return hash;
124 }
125
hash_free(Hash * hash)126 void hash_free(Hash* hash)
127 {
128 HElem* he;
129 HElem* hq;
130 unsigned int i;
131
132 assert(hash_is_valid(hash));
133
134 if (verbose >= VERB_CHATTER)
135 hash_statist(stderr, hash);
136
137 SID_del(hash);
138
139 for(i = 0; i < hash->size; i++)
140 {
141 for(he = hash->bucket[i]; he != NULL; he = hq)
142 {
143 hq = he->next;
144 blk_free(he, sizeof(*he));
145 }
146 }
147 free(hash->bucket);
148 free(hash);
149 }
150
hash_add_tuple(Hash * hash,const Tuple * tuple)151 void hash_add_tuple(Hash* hash, const Tuple* tuple)
152 {
153 HElem* he = blk_alloc(sizeof(*he));
154 unsigned int hcode;
155
156 assert(hash_is_valid(hash));
157 assert(tuple_is_valid(tuple));
158 assert(hash->type == HASH_TUPLE);
159 assert(he != NULL);
160
161 hcode = tuple_hash(tuple) % hash->size;
162 he->value.tuple = tuple;
163 he->next = hash->bucket[hcode];
164 hash->bucket[hcode] = he;
165 hash->elems++;
166 }
167
168
hash_add_entry(Hash * hash,const Entry * entry)169 void hash_add_entry(Hash* hash, const Entry* entry)
170 {
171 HElem* he = blk_alloc(sizeof(*he));
172 const Tuple* tuple;
173 unsigned int hcode;
174
175 assert(hash_is_valid(hash));
176 assert(entry_is_valid(entry));
177 assert(hash->type == HASH_ENTRY);
178 assert(he != NULL);
179
180 tuple = entry_get_tuple(entry);
181 hcode = tuple_hash(tuple) % hash->size;
182 he->value.entry = entry;
183 he->next = hash->bucket[hcode];
184 hash->bucket[hcode] = he;
185 hash->elems++;
186 }
187
hash_add_numb(Hash * hash,const Numb * numb)188 void hash_add_numb(Hash* hash, const Numb* numb)
189 {
190 HElem* he = blk_alloc(sizeof(*he));
191 unsigned int hcode;
192
193 assert(hash_is_valid(hash));
194 assert(numb_is_valid(numb));
195 assert(hash->type == HASH_NUMB);
196 assert(he != NULL);
197
198 hcode = numb_hash(numb) % hash->size;
199 he->value.numb = numb;
200 he->next = hash->bucket[hcode];
201 hash->bucket[hcode] = he;
202 hash->elems++;
203 }
204
hash_add_mono(Hash * hash,const Mono * mono)205 void hash_add_mono(Hash* hash, const Mono* mono)
206 {
207 HElem* he = blk_alloc(sizeof(*he));
208 unsigned int hcode;
209
210 assert(hash_is_valid(hash));
211 assert(mono_is_valid(mono));
212 assert(hash->type == HASH_MONO);
213 assert(he != NULL);
214
215 hcode = mono_hash(mono) % hash->size;
216 he->value.mono = mono;
217 he->next = hash->bucket[hcode];
218 hash->bucket[hcode] = he;
219 hash->elems++;
220 }
221
hash_has_tuple(const Hash * hash,const Tuple * tuple)222 bool hash_has_tuple(const Hash* hash, const Tuple* tuple)
223 {
224 unsigned int hcode = tuple_hash(tuple) % hash->size;
225 HElem* he;
226
227 assert(hash_is_valid(hash));
228 assert(tuple_is_valid(tuple));
229
230 for(he = hash->bucket[hcode]; he != NULL; he = he->next)
231 if (!tuple_cmp(he->value.tuple, tuple))
232 break;
233
234 return he != NULL;
235 }
236
hash_has_entry(const Hash * hash,const Tuple * tuple)237 bool hash_has_entry(const Hash* hash, const Tuple* tuple)
238 {
239 unsigned int hcode = tuple_hash(tuple) % hash->size;
240 HElem* he;
241
242 assert(hash_is_valid(hash));
243 assert(tuple_is_valid(tuple));
244
245 for(he = hash->bucket[hcode]; he != NULL; he = he->next)
246 if (!entry_cmp(he->value.entry, tuple))
247 break;
248
249 return he != NULL;
250 }
251
hash_has_numb(const Hash * hash,const Numb * numb)252 bool hash_has_numb(const Hash* hash, const Numb* numb)
253 {
254 unsigned int hcode = numb_hash(numb) % hash->size;
255 HElem* he;
256
257 assert(hash_is_valid(hash));
258 assert(numb_is_valid(numb));
259
260 for(he = hash->bucket[hcode]; he != NULL; he = he->next)
261 if (numb_equal(he->value.numb, numb))
262 break;
263
264 return he != NULL;
265 }
266
267 /* Liefert NULL wenn nicht gefunden.
268 */
hash_lookup_entry(const Hash * hash,const Tuple * tuple)269 const Entry* hash_lookup_entry(const Hash* hash, const Tuple* tuple)
270 {
271 unsigned int hcode = tuple_hash(tuple) % hash->size;
272 HElem* he;
273
274 assert(hash_is_valid(hash));
275 assert(tuple_is_valid(tuple));
276
277 for(he = hash->bucket[hcode]; he != NULL; he = he->next)
278 if (!entry_cmp(he->value.entry, tuple))
279 break;
280
281 if (he == NULL)
282 return NULL;
283
284 assert(he != NULL);
285
286 assert(entry_is_valid(he->value.entry));
287
288 return he->value.entry;
289 }
290
291 /* Liefert NULL wenn nicht gefunden.
292 */
hash_lookup_mono(const Hash * hash,const Mono * mono)293 const Mono* hash_lookup_mono(const Hash* hash, const Mono* mono)
294 {
295 unsigned int hcode = mono_hash(mono) % hash->size;
296 HElem* he;
297
298 assert(hash_is_valid(hash));
299 assert(mono_is_valid(mono));
300
301 for(he = hash->bucket[hcode]; he != NULL; he = he->next)
302 if (mono_equal(he->value.mono, mono))
303 break;
304
305 if (he == NULL)
306 return NULL;
307
308 assert(he != NULL);
309
310 assert(mono_is_valid(he->value.mono));
311
312 return he->value.mono;
313 }
314
hash_add_elem_idx(Hash * hash,const Elem * elem,int idx)315 void hash_add_elem_idx(Hash* hash, const Elem* elem, int idx)
316 {
317 HElem* he = blk_alloc(sizeof(*he));
318 unsigned int hcode;
319
320 assert(hash_is_valid(hash));
321 assert(elem_is_valid(elem));
322 assert(he != NULL);
323
324 hcode = elem_hash(elem) % hash->size;
325 he->value.elem_idx.elem = elem;
326 he->value.elem_idx.idx = idx;
327 he->next = hash->bucket[hcode];
328 hash->bucket[hcode] = he;
329 hash->elems++;
330 }
331
332 /* Liefert -1 wenn nicht gefunden.
333 */
hash_lookup_elem_idx(const Hash * hash,const Elem * elem)334 int hash_lookup_elem_idx(const Hash* hash, const Elem* elem)
335 {
336 unsigned int hcode = elem_hash(elem) % hash->size;
337 HElem* he;
338
339 assert(hash_is_valid(hash));
340 assert(elem_is_valid(elem));
341
342 for(he = hash->bucket[hcode]; he != NULL; he = he->next)
343 if (!elem_cmp(he->value.elem_idx.elem, elem))
344 break;
345
346 if (he == NULL)
347 return -1;
348
349 assert(he != NULL);
350
351 return he->value.elem_idx.idx;
352 }
353
hash_statist(FILE * fp,const Hash * hash)354 static void hash_statist(FILE* fp, const Hash* hash)
355 {
356 HElem* he;
357 int min = (int)hash->size;
358 int max = 0;
359 int sum = 0;
360 int zeros = 0;
361 int filled = 0;
362 double avg = 0.0;
363 unsigned int i;
364
365 assert(fp != NULL);
366 assert(hash_is_valid(hash));
367
368 for(i = 0; i < hash->size; i++)
369 {
370 int count = 0;
371
372 for(he = hash->bucket[i]; he != NULL; he = he->next)
373 count++;
374
375 if (count == 0)
376 zeros++;
377 else
378 filled++;
379
380 if (count < min)
381 min = count;
382 if (count > max)
383 max = count;
384 sum += count;
385 }
386 assert(sum == hash->elems);
387
388 if (filled > 0)
389 avg = (double)sum / (double)filled;
390
391 fprintf(fp,
392 "HashStat: size=%8u sum=%6d min=%3d max=%3d avg=%4.1f zero=%6d filled=%6d\n",
393 hash->size, sum, min, max, avg, zeros, filled);
394 }
395
396
397