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 60561 : setlen(hashtable *h, ulong len) {
32 60561 : h->maxnb = (ulong)ceil(len * 0.65);
33 60561 : h->len = len;
34 60561 : }
35 :
36 : static int
37 55857 : get_prime_index(ulong len)
38 : {
39 : int i;
40 86391 : for (i=0; i < hashprimes_len; i++)
41 86391 : 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 1784329 : hash_link2(hashtable *h, hashentry *e, ulong hash)
49 : {
50 : ulong index;
51 1784329 : e->hash = hash; index = e->hash % h->len;
52 1784329 : e->next = h->table[index]; h->table[index] = e;
53 1784329 : }
54 : INLINE void
55 16475 : hash_link(hashtable *h, hashentry *e) { hash_link2(h,e,h->hash(e->key));}
56 :
57 : hashtable *
58 40472 : hash_create(ulong minsize, ulong (*hash)(void*), int (*eq)(void*,void*),
59 : int use_stack)
60 : {
61 40472 : int i = get_prime_index(minsize);
62 40472 : ulong len = hashprimes[i];
63 : hashtable *h;
64 :
65 40472 : if (use_stack)
66 : {
67 36731 : h = (hashtable*)stack_malloc(sizeof(hashtable));
68 36731 : h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
69 36731 : h->use_stack = 1;
70 : }
71 : else
72 : {
73 3741 : h = (hashtable*)pari_malloc(sizeof(hashtable));
74 3741 : h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
75 3741 : h->use_stack = 0;
76 : }
77 40472 : h->pindex = i;
78 40472 : h->nb = 0;
79 40472 : h->hash = hash;
80 40472 : h->eq = eq;
81 40472 : setlen(h, len); return h;
82 : }
83 : static ulong
84 640340 : hash_id(void *x) { return (ulong)x; }
85 : static int
86 303066 : eq_id(void *x, void *y) { return x == y; }
87 : hashtable *
88 1064 : hash_create_ulong(ulong s, long stack)
89 1064 : { return hash_create(s, &hash_id, &eq_id, stack); }
90 :
91 : void
92 15385 : hash_init(hashtable *h, ulong minsize, ulong (*hash)(void*),
93 : int (*eq)(void*,void*), int use_stack)
94 : {
95 15385 : int i = get_prime_index(minsize);
96 15385 : ulong len = hashprimes[i];
97 15385 : if (use_stack)
98 15385 : h->table = (hashentry**)stack_calloc(len * sizeof(hashentry*));
99 : else
100 0 : h->table = (hashentry**)pari_calloc(len * sizeof(hashentry*));
101 15385 : h->use_stack = use_stack;
102 15385 : h->pindex = i;
103 15385 : h->nb = 0;
104 15385 : h->hash = hash;
105 15385 : h->eq = eq;
106 15385 : setlen(h, len);
107 15385 : }
108 :
109 : void
110 11710 : hash_init_GEN(hashtable *h, ulong minsize, int (*eq)(GEN,GEN), int use_stack)
111 11710 : { hash_init(h, minsize,(ulong (*)(void*)) hash_GEN,
112 : (int (*)(void*,void*)) eq, use_stack);
113 11710 : }
114 :
115 : void
116 3675 : hash_init_ulong(hashtable *h, ulong minsize, int use_stack)
117 3675 : { hash_init(h, minsize,hash_id, eq_id, use_stack); }
118 :
119 : void
120 1767854 : hash_insert2(hashtable *h, void *k, void *v, ulong hash)
121 : {
122 : hashentry *e;
123 : ulong index;
124 :
125 1767854 : if (h->use_stack)
126 1758704 : e = (hashentry*) stack_malloc(sizeof(hashentry));
127 : else
128 9150 : e = (hashentry*) pari_malloc(sizeof(hashentry));
129 :
130 1767854 : if (++(h->nb) > h->maxnb && h->pindex < hashprimes_len-1)
131 : { /* double table size */
132 4704 : ulong i, newlen = hashprimes[++(h->pindex)];
133 : hashentry *E, **newtable;
134 4704 : if (h->use_stack)
135 4704 : newtable = (hashentry**)stack_calloc(newlen*sizeof(hashentry*));
136 : else
137 0 : newtable = (hashentry**)pari_calloc(newlen*sizeof(hashentry*));
138 1365890 : for (i = 0; i < h->len; i++)
139 2248726 : while ( (E = h->table[i]) )
140 : {
141 887540 : h->table[i] = E->next;
142 887540 : index = E->hash % newlen;
143 887540 : E->next = newtable[index];
144 887540 : newtable[index] = E;
145 : }
146 4704 : if (!h->use_stack) pari_free(h->table);
147 4704 : h->table = newtable;
148 4704 : setlen(h, newlen);
149 : }
150 1767854 : e->key = k;
151 1767854 : e->val = v; hash_link2(h, e, hash);
152 1767854 : }
153 : void
154 783089 : hash_insert(hashtable *h, void *k, void *v)
155 783089 : { hash_insert2(h,k,v,h->hash(k)); }
156 :
157 : void
158 54725 : hash_insert_long(hashtable *h, void *k, long v)
159 54725 : { hash_insert2(h,k,(void*)v,h->hash(k)); }
160 :
161 : /* the key 'k' may correspond to different values in the hash, return
162 : * one satisfying the selection callback */
163 : hashentry *
164 77 : hash_select(hashtable *h, void *k, void *E,int(*select)(void *,hashentry *))
165 : {
166 77 : ulong hash = h->hash(k);
167 77 : hashentry *e = h->table[ hash % h->len ];
168 147 : while (e)
169 : {
170 91 : if (hash == e->hash && h->eq(k, e->key) && select(E,e)) return e;
171 70 : e = e->next;
172 : }
173 56 : return NULL;
174 : }
175 :
176 : GEN
177 1070 : hash_keys(hashtable *h)
178 : {
179 1070 : long k = 1;
180 : ulong i;
181 1070 : GEN v = cgetg(h->nb+1, t_VECSMALL);
182 206740 : for (i = 0; i < h->len; i++)
183 : {
184 205670 : hashentry *e = h->table[i];
185 206528 : while (e) { v[k++] = (long)e->key; e = e->next; }
186 : }
187 1070 : return v;
188 : }
189 :
190 : GEN
191 3905 : hash_keys_GEN(hashtable *h)
192 : {
193 3905 : long k = 1;
194 : ulong i;
195 3905 : GEN v = cgetg(h->nb+1, t_VEC);
196 924684 : for (i = 0; i < h->len; i++)
197 : {
198 920779 : hashentry *e = h->table[i];
199 1318982 : while (e) { gel(v,k++) = (GEN)e->key; e = e->next; }
200 : }
201 3905 : return v;
202 : }
203 :
204 : GEN
205 1988 : hash_values(hashtable *h)
206 : {
207 1988 : long k = 1;
208 : ulong i;
209 1988 : GEN v = cgetg(h->nb+1, t_VECSMALL);
210 385672 : for (i = 0; i < h->len; i++)
211 : {
212 383684 : hashentry *e = h->table[i];
213 391621 : while (e) { v[k++] = (long)e->val; e = e->next; }
214 : }
215 1988 : return v;
216 : }
217 :
218 : /* assume hash = h->hash(k) */
219 : hashentry *
220 3485627 : hash_search2(hashtable *h, void *k, ulong hash)
221 : {
222 3485627 : hashentry *e = h->table[ hash % h->len ];
223 4383605 : while (e)
224 : {
225 2846565 : if (hash == e->hash && h->eq(k, e->key)) return e;
226 897978 : e = e->next;
227 : }
228 1537040 : return NULL; /* not found */
229 : }
230 : /* returns entry attached to key k or NULL */
231 : hashentry *
232 1652070 : hash_search(hashtable *h, void *k)
233 : {
234 1652070 : if (h->nb == 0) return NULL;
235 1646777 : return hash_search2(h, k, h->hash(k));
236 : }
237 :
238 : int
239 335509 : hash_haskey_long(hashtable *h, void *k, long *v)
240 : {
241 335509 : hashentry * e = hash_search(h, k);
242 335509 : if (e) { *v = (long) e->val; return 1; }
243 48138 : else return 0;
244 : }
245 :
246 : GEN
247 147474 : hash_haskey_GEN(hashtable *h, void *k)
248 : {
249 147474 : hashentry * e = hash_search(h, k);
250 147474 : return e ? (GEN) e->val: NULL;
251 : }
252 :
253 : hashentry *
254 3010 : hash_remove_select(hashtable *h, void *k, void *E,
255 : int (*select)(void*,hashentry*))
256 : {
257 3010 : ulong hash = h->hash(k), index = hash % h->len;
258 3010 : hashentry **pE = &(h->table[index]), *e = *pE;
259 3010 : while (e)
260 : {
261 3010 : if (hash == e->hash && h->eq(k, e->key) && select(E,e)) {
262 3010 : *pE = e->next; h->nb--;
263 3010 : return e;
264 : }
265 0 : pE = &(e->next);
266 0 : e = e->next;
267 : }
268 0 : return NULL;
269 : }
270 :
271 : hashentry *
272 24 : hash_remove(hashtable *h, void *k)
273 : {
274 24 : ulong hash = h->hash(k), index = hash % h->len;
275 24 : hashentry **pE = &(h->table[index]), *e = *pE;
276 24 : while (e)
277 : {
278 24 : if (hash == e->hash && h->eq(k, e->key)) {
279 24 : *pE = e->next; h->nb--;
280 24 : return e;
281 : }
282 0 : pE = &(e->next);
283 0 : e = e->next;
284 : }
285 0 : return NULL;
286 : }
287 : void
288 3696 : hash_destroy(hashtable *h)
289 : {
290 : ulong i;
291 3696 : if (h->use_stack) return;
292 458304 : for (i = 0; i < h->len; i++)
293 : {
294 454608 : hashentry *e = h->table[i];
295 460704 : while (e) { hashentry *f = e; e = e->next; pari_free(f); }
296 : }
297 3696 : pari_free(h->table); pari_free(h);
298 : }
299 :
300 : static
301 15862 : int strequal(void *a, void *b) { return !strcmp((char*)a,(char*)b); }
302 : hashtable *
303 3741 : hash_create_str(ulong s, long stack)
304 3741 : { return hash_create(s, (ulong (*)(void *))&hash_str, strequal, stack); }
305 :
306 : hashtable *
307 25 : hashstr_import_static(hashentry *e, ulong size)
308 : {
309 25 : hashtable *h = hash_create_str(size, 0);
310 16500 : for ( ; e->key; e++) { hash_link(h, e); h->nb++; }
311 25 : return h;
312 : }
313 :
314 : void
315 0 : hash_dbg(hashtable *h)
316 : {
317 0 : ulong n, Total = 0, Max = 0;
318 0 : hashentry *e, **table = h->table;
319 0 : for (n=0; n < h->len; n++)
320 : {
321 0 : ulong m=0;
322 0 : for (e=table[n]; e; e=e->next) m++;
323 0 : Total += m; if (Max < m) Max = m;
324 0 : pari_printf("%4ld:%2ld ",n,m);
325 0 : if (n%9 == 8) pari_putc('\n');
326 : }
327 0 : pari_printf("\nTotal = %ld, Max = %ld\n", Total, Max);
328 0 : }
329 :
330 : /********************************************************************/
331 : /* */
332 : /* HASH FUNCTIONS */
333 : /* */
334 : /********************************************************************/
335 :
336 : INLINE ulong
337 552877060 : glue(ulong h, ulong a) { return 404936533*h + a; }
338 : ulong
339 141569835 : hash_GEN(GEN x)
340 : {
341 141569835 : ulong h = x[0] & ~CLONEBIT;
342 141569835 : long tx = typ(x), lx, i;
343 141569835 : switch(tx)
344 : { /* non recursive types */
345 50356865 : case t_INT:
346 50356865 : lx = lgefint(x);
347 50356865 : h &= TYPBITS;
348 155124369 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
349 50356867 : return h;
350 73875784 : case t_REAL:
351 : case t_STR:
352 : case t_VECSMALL:
353 73875784 : lx = lg(x);
354 469143693 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
355 73875784 : return h;
356 : /* one more special case */
357 0 : case t_LIST:
358 0 : x = list_data(x);
359 0 : if (!x) return h;
360 : /* fall through */
361 : default:
362 17337186 : if (lontyp[tx] == 2) { h = glue(h, x[1]); i = 2; } else i = 1;
363 17337186 : lx = lg(x);
364 69280908 : for (; i < lx; i++) h = glue(h, hash_GEN(gel(x,i)));
365 17337188 : return h;
366 : }
367 : }
368 : ulong
369 17507 : hash_zv(GEN x)
370 : {
371 17507 : long i, lx = lg(x);
372 : ulong h;
373 17507 : if (lx == 1) return 0;
374 15701 : h = x[1];
375 108514 : for (i = 1; i < lx; i++) h = glue(h, uel(x,i));
376 15701 : return h;
377 : }
|
