Line data Source code
1 : /* Copyright (C) 2000 The PARI group.
2 :
3 : This file is part of the PARI/GP package.
4 :
5 : PARI/GP is free software; you can redistribute it and/or modify it under the
6 : terms of the GNU General Public License as published by the Free Software
7 : Foundation; either version 2 of the License, or (at your option) any later
8 : version. It is distributed in the hope that it will be useful, but WITHOUT
9 : ANY WARRANTY WHATSOEVER.
10 :
11 : Check the License for details. You should have received a copy of it, along
12 : with the package; see the file 'COPYING'. If not, write to the Free Software
13 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
14 : #include "pari.h"
15 : #include "paripriv.h"
16 :
17 : /********************************************************************/
18 : /* */
19 : /* GENERAL HASHTABLES */
20 : /* */
21 : /********************************************************************/
22 : /* http://planetmath.org/encyclopedia/GoodHashTablePrimes.html */
23 : static const ulong hashprimes[] = {
24 : 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613,
25 : 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
26 : 100663319, 201326611, 402653189, 805306457, 1610612741
27 : };
28 : static const int hashprimes_len = numberof(hashprimes);
29 :
30 : INLINE void
31 51411 : setlen(hashtable *h, ulong len) {
32 51411 : h->maxnb = (ulong)ceil(len * 0.65);
33 51411 : h->len = len;
34 51411 : }
35 :
36 : static int
37 47425 : get_prime_index(ulong len)
38 : {
39 : int i;
40 72831 : for (i=0; i < hashprimes_len; i++)
41 72831 : if (hashprimes[i] > len) return i;
42 0 : pari_err_OVERFLOW("hash table [too large]");
43 : return -1; /* LCOV_EXCL_LINE */
44 : }
45 :
46 : /* link hashentry e to hashtable h, setting e->hash / e->next */
47 : INLINE void
48 1407197 : hash_link2(hashtable *h, hashentry *e, ulong hash)
49 : {
50 : ulong index;
51 1407197 : e->hash = hash; index = e->hash % h->len;
52 1407197 : e->next = h->table[index]; h->table[index] = e;
53 1407197 : }
54 : INLINE void
55 10544 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
56 :
57 : hashtable *
58 34366 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
59 : int use_stack)
60 : {
61 34366 : hashtable *h = (hashtable*)(use_stack? stack_malloc(sizeof(hashtable))
62 2996 : : pari_malloc(sizeof(hashtable)));
63 34366 : hash_init(h, minsize, hash, eq, use_stack); return h;
64 : }
65 : static ulong
66 424547 : hash_id(void *x) { return (ulong)x; }
67 : static int
68 259595 : eq_id(void *x, void *y) { return x == y; }
69 : hashtable *
70 1101 : hash_create_ulong(ulong s, long stack)
71 1101 : { return hash_create(s, &hash_id, &eq_id, stack); }
72 : hashtable *
73 194 : hash_create_INT(ulong s, long use_stack)
74 194 : { return hash_create(s, (ulong(*)(void*))&hash_GEN,
75 : (int(*)(void*,void*))&equalii, use_stack); }
76 : hashtable *
77 29585 : hash_create_GEN(ulong s, long use_stack)
78 29585 : { return hash_create(s, (ulong(*)(void*))&hash_GEN,
79 : (int(*)(void*,void*))&gidentical, use_stack); }
80 : void
81 47425 : hash_init(hashtable *h, ulong minsize, ulong (*hash)(void*),
82 : int (*eq)(void*,void*), int use_stack)
83 : {
84 47425 : int i = get_prime_index(minsize);
85 47425 : ulong len = hashprimes[i];
86 47425 : if (use_stack)
87 44429 : h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
88 : else
89 2996 : h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
90 47425 : h->use_stack = use_stack;
91 47425 : h->pindex = i;
92 47425 : h->nb = 0;
93 47425 : h->hash = hash;
94 47425 : h->eq = eq;
95 47425 : setlen(h, len);
96 47425 : }
97 :
98 : void
99 10153 : hash_init_GEN(hashtable *h, ulong minsize, int (*eq)(GEN,GEN), int use_stack)
100 10153 : { hash_init(h, minsize,(ulong (*)(void*)) hash_GEN,
101 : (int (*)(void*,void*)) eq, use_stack);
102 10153 : }
103 :
104 : void
105 2906 : hash_init_ulong(hashtable *h, ulong minsize, int use_stack)
106 2906 : { hash_init(h, minsize,hash_id, eq_id, use_stack); }
107 :
108 : void
109 1396653 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
110 : {
111 : hashentry *e;
112 : ulong index;
113 :
114 1396653 : if (h->use_stack)
115 1388989 : e = (hashentry*) stack_malloc(sizeof(hashentry));
116 : else
117 7664 : e = (hashentry*) pari_malloc(sizeof(hashentry));
118 :
119 1396653 : if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
120 : { /* double table size */
121 3986 : ulong i, newlen = hashprimes[++(h->pindex)];
122 : hashentry *E, **newtable;
123 3986 : if (h->use_stack)
124 3986 : newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
125 : else
126 0 : newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
127 1061730 : for (i = 0; i < h->len; i++)
128 1747621 : while ( (E = h->table[i]) )
129 : {
130 689877 : h->table[i] = E->next;
131 689877 : index = E->hash % newlen;
132 689877 : E->next = newtable[index];
133 689877 : newtable[index] = E;
134 : }
135 3986 : if (!h->use_stack) pari_free(h->table);
136 3986 : h->table = newtable;
137 3986 : setlen(h, newlen);
138 : }
139 1396653 : e->key = k;
140 1396653 : e->val = v; hash_link2(h, e, hash);
141 1396653 : }
142 : void
143 604680 : hash_insert(hashtable *h, void *k, void *v)
144 604680 : { hash_insert2(h,k,v,h->hash(k)); }
145 :
146 : void
147 46907 : hash_insert_long(hashtable *h, void *k, long v)
148 46907 : { hash_insert2(h,k,(void*)v,h->hash(k)); }
149 :
150 : /* the key 'k' may correspond to different values in the hash, return
151 : * one satisfying the selection callback */
152 : hashentry *
153 59 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
154 : {
155 59 : ulong hash = h->hash(k);
156 59 : hashentry *e = h->table[ hash % h->len ];
157 109 : while (e)
158 : {
159 65 : if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
160 50 : e = e->next;
161 : }
162 44 : return NULL;
163 : }
164 :
165 : GEN
166 1101 : hash_keys(hashtable *h)
167 : {
168 1101 : long k = 1;
169 : ulong i;
170 1101 : GEN v = cgetg(h->nb+1, t_VECSMALL);
171 213594 : for (i = 0; i < h->len; i++)
172 : {
173 212493 : hashentry *e = h->table[i];
174 213386 : while (e) { v[k++] = (long)e->key; e = e->next; }
175 : }
176 1101 : return v;
177 : }
178 :
179 : GEN
180 3082 : hash_keys_GEN(hashtable *h)
181 : {
182 3082 : long k = 1;
183 : ulong i;
184 3082 : GEN v = cgetg(h->nb+1, t_VEC);
185 650924 : for (i = 0; i < h->len; i++)
186 : {
187 647842 : hashentry *e = h->table[i];
188 930437 : while (e) { gel(v,k++) = (GEN)e->key; e = e->next; }
189 : }
190 3082 : return v;
191 : }
192 :
193 : GEN
194 1590 : hash_values(hashtable *h)
195 : {
196 1590 : long k = 1;
197 : ulong i;
198 1590 : GEN v = cgetg(h->nb+1, t_VECSMALL);
199 308460 : for (i = 0; i < h->len; i++)
200 : {
201 306870 : hashentry *e = h->table[i];
202 313274 : while (e) { v[k++] = (long)e->val; e = e->next; }
203 : }
204 1590 : return v;
205 : }
206 :
207 : GEN
208 360 : hash_values_GEN(hashtable *h)
209 : {
210 360 : long k = 1;
211 : ulong i;
212 360 : GEN v = cgetg(h->nb+1, t_VEC);
213 20232 : for (i = 0; i < h->len; i++)
214 : {
215 19872 : hashentry *e = h->table[i];
216 23844 : while (e) { gel(v,k++) = (GEN)e->val; e = e->next; }
217 : }
218 360 : return v;
219 : }
220 :
221 : /* assume hash = h->hash(k) */
222 : hashentry *
223 2862368 : hash_search2(hashtable *h, void *k, ulong hash)
224 : {
225 2862368 : hashentry *e = h->table[ hash % h->len ];
226 3589917 : while (e)
227 : {
228 2390545 : if (hash == e->hash && h->eq(k, e->key)) return e;
229 727549 : e = e->next;
230 : }
231 1199372 : return NULL; /* not found */
232 : }
233 : /* returns entry attached to key k or NULL */
234 : hashentry *
235 1339886 : hash_search(hashtable *h, void *k)
236 : {
237 1339886 : if (h->nb == 0) return NULL;
238 1334933 : return hash_search2(h, k, h->hash(k));
239 : }
240 :
241 : int
242 287579 : hash_haskey_long(hashtable *h, void *k, long *v)
243 : {
244 287579 : hashentry * e = hash_search(h, k);
245 287579 : if (e) { *v = (long) e->val; return 1; }
246 41261 : else return 0;
247 : }
248 :
249 : GEN
250 62044 : hash_haskey_GEN(hashtable *h, void *k)
251 : {
252 62044 : hashentry * e = hash_search(h, k);
253 62044 : return e ? (GEN) e->val: NULL;
254 : }
255 :
256 : hashentry *
257 2573 : hash_remove_select(hashtable *h, void *k, void *E,
258 : int (*select)(void*,hashentry*))
259 : {
260 2573 : ulong hash = h->hash(k), index = hash % h->len;
261 2573 : hashentry **pE = &(h->table[index]), *e = *pE;
262 2573 : while (e)
263 : {
264 2573 : if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
265 2573 : *pE = e->next; h->nb--;
266 2573 : return e;
267 : }
268 0 : pE = &(e->next);
269 0 : e = e->next;
270 : }
271 0 : return NULL;
272 : }
273 :
274 : hashentry *
275 0 : hash_remove(hashtable *h, void *k)
276 : {
277 0 : ulong hash = h->hash(k), index = hash % h->len;
278 0 : hashentry **pE = &(h->table[index]), *e = *pE;
279 0 : while (e)
280 : {
281 0 : if (hash == e->hash && h->eq(k, e->key)) {
282 0 : *pE = e->next; h->nb--;
283 0 : return e;
284 : }
285 0 : pE = &(e->next);
286 0 : e = e->next;
287 : }
288 0 : return NULL;
289 : }
290 : void
291 2980 : hash_destroy(hashtable *h)
292 : {
293 : ulong i;
294 2980 : if (h->use_stack) return;
295 369520 : for (i = 0; i < h->len; i++)
296 : {
297 366540 : hashentry *e = h->table[i];
298 371631 : while (e) { hashentry *f = e; e = e->next; pari_free(f); }
299 : }
300 2980 : pari_free(h->table); pari_free(h);
301 : }
302 :
303 : static
304 3247 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
305 : hashtable *
306 2996 : hash_create_str(ulong s, long stack)
307 2996 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
308 :
309 : hashtable *
310 16 : hashstr_import_static(hashentry *e, ulong size)
311 : {
312 16 : hashtable *h = hash_create_str(size, 0);
313 10560 : for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
314 16 : return h;
315 : }
316 :
317 : void
318 0 : hash_dbg(hashtable *h)
319 : {
320 0 : ulong n, Total = 0, Max = 0;
321 0 : hashentry *e, **table = h->table;
322 0 : for (n=0; n < h->len; n++)
323 : {
324 0 : ulong m=0;
325 0 : for (e=table[n]; e; e=e->next) m++;
326 0 : Total += m; if (Max < m) Max = m;
327 0 : pari_printf("%4ld:%2ld ",n,m);
328 0 : if (n%9 == 8) pari_putc('\n');
329 : }
330 0 : pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
331 0 : }
332 :
333 : /********************************************************************/
334 : /* */
335 : /* HASH FUNCTIONS */
336 : /* */
337 : /********************************************************************/
338 :
339 : INLINE ulong
340 464866798 : glue(ulong h, ulong a) { return 404936533*h + a; }
341 :
342 : /* asume h, a >= 0 */
343 : static GEN
344 2172 : glueb(GEN h, GEN a, long b)
345 2172 : { return remi2n(addmuliu(a, h, 404936533), b); }
346 :
347 : /* asume h >= 0 */
348 : static GEN
349 2820 : glueisb(GEN h, long a, long b)
350 : {
351 2820 : GEN A = a >= 0? utoi(a): modsi(a, int2n(b));
352 2820 : return remi2n(addmuliu(A, h, 404936533), b);
353 : }
354 :
355 : static ulong
356 44972719 : hashi(GEN x)
357 : {
358 44972719 : ulong h = glue(evaltyp(t_INT), x[1]);
359 44972719 : long i, lx = lgefint(x);
360 44972719 : GEN xp = int_MSW(x);
361 97460306 : for (i = 2; i < lx; i++, xp = int_precW(xp)) h = glue(h, *xp);
362 44972719 : return h;
363 : }
364 :
365 : /* t_INT */
366 : static GEN
367 1062 : hashib(GEN x, long b)
368 : {
369 1062 : pari_sp av = avma;
370 1062 : GEN h = glueisb(utoi(t_INT), signe(x), b);
371 1062 : GEN v = binary_2k(x, b);
372 1062 : long i, l = lg(v);
373 1866 : for (i = 1; i < l; i++) h = glueb(h, gel(v,i), b);
374 1062 : return gc_INT(av, h);
375 : }
376 :
377 : /* slow but kernel/architecture independent */
378 : GEN
379 1908 : fingerprint(GEN x, long b)
380 : {
381 1908 : long i, l, tx = typ(x);
382 1908 : pari_sp av = avma;
383 : GEN h;
384 1908 : if (b <= 0) pari_err_DOMAIN("fingerprint", "b", "<=", gen_0, stoi(b));
385 1902 : if (tx == t_INT) return hashib(x, b);
386 918 : h = utoi(tx);
387 918 : switch(tx)
388 : {
389 30 : case t_REAL:
390 : {
391 : long e;
392 30 : x = mantissa_real(x, &e);
393 30 : h = glueisb(h, signe(x), b);
394 30 : h = glueisb(h, e, b);
395 30 : h = glueb(h, hashib(x, b), b); return gc_INT(av, h);
396 : }
397 126 : case t_VECSMALL:
398 126 : l = lg(x);
399 582 : for (i = 1; i < l; i++) h = glueisb(h, x[i], b);
400 126 : return gc_INT(av, h);
401 96 : case t_STR:
402 96 : return gc_INT(av, fingerprint(gtovecsmall(x), b));
403 48 : case t_FFELT:
404 : {
405 48 : pari_sp av = avma;
406 48 : h = glueisb(h, FF_var(x), b);
407 48 : h = glueb(h, hashib(FF_p(x), b), b);
408 48 : h = glueb(h, fingerprint(FF_to_FpXQ(x), b), b);
409 48 : h = glueb(h, fingerprint(FF_mod(x), b), b);
410 48 : return gc_INT(av, h);
411 : }
412 36 : case t_PADIC:
413 36 : h = glueisb(h, precp(x), b);
414 36 : h = glueisb(h, valp(x), b); break;
415 42 : case t_SER:
416 42 : h = glueisb(h, valser(x), b); /* fall through */
417 234 : case t_POL:
418 234 : h = glueisb(h, signe(x), b);
419 234 : h = glueisb(h, varn(x), b); break;
420 24 : case t_CLOSURE:
421 24 : h = glueisb(h, closure_arity(x), b);
422 24 : h = glueb(h, fingerprint(closure_get_code(x), b), b);
423 24 : h = glueb(h, fingerprint(closure_get_data(x), b), b);
424 24 : if (lg(x) > 6)
425 18 : h = glueb(h, fingerprint(closure_get_text(x), b), b);
426 24 : return gc_INT(av, h);
427 18 : case t_LIST:
428 18 : x = list_data(x);
429 18 : if (!x) return h;
430 : /* fall through */
431 : }
432 : /* recursive type with GEN entries */
433 588 : l = lg(x); h = glueisb(h, l, b);
434 1716 : for (i = lontyp[tx]; i < l; i++) h = glueb(h, fingerprint(gel(x,i), b), b);
435 588 : return gc_INT(av, h);
436 : }
437 :
438 : ulong
439 119238747 : hash_GEN(GEN x)
440 : {
441 119238747 : long tx = typ(x), lx, i;
442 : ulong h;
443 119238747 : if (tx == t_INT) return hashi(x);
444 74266028 : h = x[0] & ~CLONEBIT;
445 74266028 : switch(tx)
446 : { /* other non recursive types */
447 57637608 : case t_REAL:
448 : case t_STR:
449 : case t_VECSMALL:
450 57637608 : lx = lg(x);
451 375587968 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
452 57637608 : return h;
453 : /* one more special case */
454 0 : case t_LIST:
455 0 : x = list_data(x);
456 0 : if (!x) return h;
457 : /* fall through */
458 : default:
459 16628420 : lx = lg(x);
460 19375660 : for(i = 1; i < lontyp[tx]; i++) h = glue(h, x[i]);
461 63282232 : for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
462 16628420 : return h;
463 : }
464 : }
465 : ulong
466 12505 : hash_zv(GEN x)
467 : {
468 12505 : long i, lx = lg(x);
469 : ulong h;
470 12505 : if (lx == 1) return 0;
471 11215 : h = uel(x,1);
472 66295 : for (i = 2; i < lx; i++) h = glue(h, uel(x,i));
473 11215 : return h;
474 : }
|
