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 61551 : setlen(hashtable *h, ulong len) {
32 61551 : h->maxnb = (ulong)ceil(len * 0.65);
33 61551 : h->len = len;
34 61551 : }
35 :
36 : static int
37 56669 : get_prime_index(ulong len)
38 : {
39 : int i;
40 87625 : for (i=0; i < hashprimes_len; i++)
41 87625 : 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 1792842 : hash_link2(hashtable *h, hashentry *e, ulong hash)
49 : {
50 : ulong index;
51 1792842 : e->hash = hash; index = e->hash % h->len;
52 1792842 : e->next = h->table[index]; h->table[index] = e;
53 1792842 : }
54 : INLINE void
55 16475 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
56 :
57 : hashtable *
58 41306 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
59 : int use_stack)
60 : {
61 41306 : hashtable *h = (hashtable*)(use_stack? stack_malloc(sizeof(hashtable))
62 3825 : : pari_malloc(sizeof(hashtable)));
63 41306 : hash_init(h, minsize, hash, eq, use_stack); return h;
64 : }
65 : static ulong
66 646675 : hash_id(void *x) { return (ulong)x; }
67 : static int
68 309191 : eq_id(void *x, void *y) { return x == y; }
69 : hashtable *
70 1288 : hash_create_ulong(ulong s, long stack)
71 1288 : { return hash_create(s, &hash_id, &eq_id, stack); }
72 : hashtable *
73 259 : hash_create_INT(ulong s, long use_stack)
74 259 : { return hash_create(s, (ulong(*)(void*))&hash_GEN,
75 : (int(*)(void*,void*))&equalii, use_stack); }
76 : hashtable *
77 35262 : hash_create_GEN(ulong s, long use_stack)
78 35262 : { return hash_create(s, (ulong(*)(void*))&hash_GEN,
79 : (int(*)(void*,void*))&gidentical, use_stack); }
80 : void
81 56669 : hash_init(hashtable *h, ulong minsize, ulong (*hash)(void*),
82 : int (*eq)(void*,void*), int use_stack)
83 : {
84 56669 : int i = get_prime_index(minsize);
85 56669 : ulong len = hashprimes[i];
86 56669 : if (use_stack)
87 52844 : h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
88 : else
89 3825 : h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
90 56669 : h->use_stack = use_stack;
91 56669 : h->pindex = i;
92 56669 : h->nb = 0;
93 56669 : h->hash = hash;
94 56669 : h->eq = eq;
95 56669 : setlen(h, len);
96 56669 : }
97 :
98 : void
99 11699 : hash_init_GEN(hashtable *h, ulong minsize, int (*eq)(GEN,GEN), int use_stack)
100 11699 : { hash_init(h, minsize,(ulong (*)(void*)) hash_GEN,
101 : (int (*)(void*,void*)) eq, use_stack);
102 11699 : }
103 :
104 : void
105 3664 : hash_init_ulong(hashtable *h, ulong minsize, int use_stack)
106 3664 : { hash_init(h, minsize,hash_id, eq_id, use_stack); }
107 :
108 : void
109 1776367 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
110 : {
111 : hashentry *e;
112 : ulong index;
113 :
114 1776367 : if (h->use_stack)
115 1766944 : e = (hashentry*) stack_malloc(sizeof(hashentry));
116 : else
117 9423 : e = (hashentry*) pari_malloc(sizeof(hashentry));
118 :
119 1776367 : if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
120 : { /* double table size */
121 4882 : ulong i, newlen = hashprimes[++(h->pindex)];
122 : hashentry *E, **newtable;
123 4882 : if (h->use_stack)
124 4882 : newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
125 : else
126 0 : newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
127 1371378 : for (i = 0; i < h->len; i++)
128 2257609 : while ( (E = h->table[i]) )
129 : {
130 891113 : h->table[i] = E->next;
131 891113 : index = E->hash % newlen;
132 891113 : E->next = newtable[index];
133 891113 : newtable[index] = E;
134 : }
135 4882 : if (!h->use_stack) pari_free(h->table);
136 4882 : h->table = newtable;
137 4882 : setlen(h, newlen);
138 : }
139 1776367 : e->key = k;
140 1776367 : e->val = v; hash_link2(h, e, hash);
141 1776367 : }
142 : void
143 788238 : hash_insert(hashtable *h, void *k, void *v)
144 788238 : { hash_insert2(h,k,v,h->hash(k)); }
145 :
146 : void
147 54725 : hash_insert_long(hashtable *h, void *k, long v)
148 54725 : { 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 77 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
154 : {
155 77 : ulong hash = h->hash(k);
156 77 : hashentry *e = h->table[ hash % h->len ];
157 147 : while (e)
158 : {
159 91 : if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
160 70 : e = e->next;
161 : }
162 56 : return NULL;
163 : }
164 :
165 : GEN
166 1294 : hash_keys(hashtable *h)
167 : {
168 1294 : long k = 1;
169 : ulong i;
170 1294 : GEN v = cgetg(h->nb+1, t_VECSMALL);
171 250196 : for (i = 0; i < h->len; i++)
172 : {
173 248902 : hashentry *e = h->table[i];
174 249970 : while (e) { v[k++] = (long)e->key; e = e->next; }
175 : }
176 1294 : return v;
177 : }
178 :
179 : GEN
180 3901 : hash_keys_GEN(hashtable *h)
181 : {
182 3901 : long k = 1;
183 : ulong i;
184 3901 : GEN v = cgetg(h->nb+1, t_VEC);
185 912940 : for (i = 0; i < h->len; i++)
186 : {
187 909039 : hashentry *e = h->table[i];
188 1303332 : while (e) { gel(v,k++) = (GEN)e->key; e = e->next; }
189 : }
190 3901 : return v;
191 : }
192 :
193 : GEN
194 2030 : hash_values(hashtable *h)
195 : {
196 2030 : long k = 1;
197 : ulong i;
198 2030 : GEN v = cgetg(h->nb+1, t_VECSMALL);
199 393820 : for (i = 0; i < h->len; i++)
200 : {
201 391790 : hashentry *e = h->table[i];
202 400000 : while (e) { v[k++] = (long)e->val; e = e->next; }
203 : }
204 2030 : return v;
205 : }
206 :
207 : /* assume hash = h->hash(k) */
208 : hashentry *
209 3503520 : hash_search2(hashtable *h, void *k, ulong hash)
210 : {
211 3503520 : hashentry *e = h->table[ hash % h->len ];
212 4402711 : while (e)
213 : {
214 2857950 : if (hash == e->hash && h->eq(k, e->key)) return e;
215 899191 : e = e->next;
216 : }
217 1544761 : return NULL; /* not found */
218 : }
219 : /* returns entry attached to key k or NULL */
220 : hashentry *
221 1662910 : hash_search(hashtable *h, void *k)
222 : {
223 1662910 : if (h->nb == 0) return NULL;
224 1657407 : return hash_search2(h, k, h->hash(k));
225 : }
226 :
227 : int
228 335509 : hash_haskey_long(hashtable *h, void *k, long *v)
229 : {
230 335509 : hashentry * e = hash_search(h, k);
231 335509 : if (e) { *v = (long) e->val; return 1; }
232 48138 : else return 0;
233 : }
234 :
235 : GEN
236 147474 : hash_haskey_GEN(hashtable *h, void *k)
237 : {
238 147474 : hashentry * e = hash_search(h, k);
239 147474 : return e ? (GEN) e->val: NULL;
240 : }
241 :
242 : hashentry *
243 3010 : hash_remove_select(hashtable *h, void *k, void *E,
244 : int (*select)(void*,hashentry*))
245 : {
246 3010 : ulong hash = h->hash(k), index = hash % h->len;
247 3010 : hashentry **pE = &(h->table[index]), *e = *pE;
248 3010 : while (e)
249 : {
250 3010 : if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
251 3010 : *pE = e->next; h->nb--;
252 3010 : return e;
253 : }
254 0 : pE = &(e->next);
255 0 : e = e->next;
256 : }
257 0 : return NULL;
258 : }
259 :
260 : hashentry *
261 24 : hash_remove(hashtable *h, void *k)
262 : {
263 24 : ulong hash = h->hash(k), index = hash % h->len;
264 24 : hashentry **pE = &(h->table[index]), *e = *pE;
265 24 : while (e)
266 : {
267 24 : if (hash == e->hash && h->eq(k, e->key)) {
268 24 : *pE = e->next; h->nb--;
269 24 : return e;
270 : }
271 0 : pE = &(e->next);
272 0 : e = e->next;
273 : }
274 0 : return NULL;
275 : }
276 : void
277 3780 : hash_destroy(hashtable *h)
278 : {
279 : ulong i;
280 3780 : if (h->use_stack) return;
281 468720 : for (i = 0; i < h->len; i++)
282 : {
283 464940 : hashentry *e = h->table[i];
284 471309 : while (e) { hashentry *f = e; e = e->next; pari_free(f); }
285 : }
286 3780 : pari_free(h->table); pari_free(h);
287 : }
288 :
289 : static
290 15862 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
291 : hashtable *
292 3825 : hash_create_str(ulong s, long stack)
293 3825 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
294 :
295 : hashtable *
296 25 : hashstr_import_static(hashentry *e, ulong size)
297 : {
298 25 : hashtable *h = hash_create_str(size, 0);
299 16500 : for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
300 25 : return h;
301 : }
302 :
303 : void
304 0 : hash_dbg(hashtable *h)
305 : {
306 0 : ulong n, Total = 0, Max = 0;
307 0 : hashentry *e, **table = h->table;
308 0 : for (n=0; n < h->len; n++)
309 : {
310 0 : ulong m=0;
311 0 : for (e=table[n]; e; e=e->next) m++;
312 0 : Total += m; if (Max < m) Max = m;
313 0 : pari_printf("%4ld:%2ld ",n,m);
314 0 : if (n%9 == 8) pari_putc('\n');
315 : }
316 0 : pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
317 0 : }
318 :
319 : /********************************************************************/
320 : /* */
321 : /* HASH FUNCTIONS */
322 : /* */
323 : /********************************************************************/
324 :
325 : INLINE ulong
326 520317175 : glue(ulong h, ulong a) { return 404936533*h + a; }
327 : ulong
328 136413916 : hash_GEN(GEN x)
329 : {
330 136413916 : ulong h = x[0] & ~CLONEBIT;
331 136413916 : long tx = typ(x), lx, i;
332 136413916 : switch(tx)
333 : { /* non recursive types */
334 53406575 : case t_INT:
335 53406575 : lx = lgefint(x);
336 53406575 : h &= TYPBITS;
337 164883753 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
338 53406575 : return h;
339 64356002 : case t_REAL:
340 : case t_STR:
341 : case t_VECSMALL:
342 64356002 : lx = lg(x);
343 416543151 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
344 64356002 : return h;
345 : /* one more special case */
346 0 : case t_LIST:
347 0 : x = list_data(x);
348 0 : if (!x) return h;
349 : /* fall through */
350 : default:
351 18651339 : lx = lg(x);
352 19806929 : for(i = 1; i < lontyp[tx]; i++) h = glue(h, x[i]);
353 74055787 : for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
354 18651340 : return h;
355 : }
356 : }
357 : ulong
358 17507 : hash_zv(GEN x)
359 : {
360 17507 : long i, lx = lg(x);
361 : ulong h;
362 17507 : if (lx == 1) return 0;
363 15701 : h = x[1];
364 108514 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
365 15701 : return h;
366 : }
|
