1 /*
2 * assocfunc - association table routines
3 *
4 * Copyright (C) 1999-2007,2021 David I. Bell
5 *
6 * Calc is open software; you can redistribute it and/or modify it under
7 * the terms of the version 2.1 of the GNU Lesser General Public License
8 * as published by the Free Software Foundation.
9 *
10 * Calc is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 * Public License for more details.
14 *
15 * A copy of version 2.1 of the GNU Lesser General Public License is
16 * distributed with calc under the filename COPYING-LGPL. You should have
17 * received a copy with calc; if not, write to Free Software Foundation, Inc.
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 * Under source code control: 1993/07/20 23:04:27
21 * File existed as early as: 1993
22 *
23 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/
24 */
25
26 /*
27 * Association table routines.
28 * An association table is a type of value which can be "indexed" by
29 * one or more arbitrary values. Each element in the table is thus an
30 * association between a particular set of index values and a result value.
31 * The elements in an association table are stored in a hash table for
32 * quick access.
33 */
34
35
36 #include "value.h"
37
38
39 #include "banned.h" /* include after system header <> includes */
40
41
42 #define MINHASHSIZE 31 /* minimum size of hash tables */
43 #define GROWHASHSIZE 50 /* approximate growth for hash tables */
44 #define CHAINLENGTH 10 /* desired number of elements on a hash chain */
45 #define ELEMSIZE(n) (sizeof(ASSOCELEM) + (sizeof(VALUE) * ((n) - 1)))
46
47
48 S_FUNC ASSOCELEM *elemindex(ASSOC *ap, long index);
49 S_FUNC BOOL compareindices(VALUE *v1, VALUE *v2, long dim);
50 S_FUNC void resize(ASSOC *ap, long newsize);
51 S_FUNC void assoc_elemfree(ASSOCELEM *ep);
52
53
54 /*
55 * Return the address of the value specified by normal indexing of
56 * an association. The create flag is TRUE if a value is going to be
57 * assigned into the specified indexing location. If create is FALSE and
58 * the index value doesn't exist, a pointer to a NULL value is returned.
59 *
60 * given:
61 * ap association to index into
62 * create whether to create the index value
63 * dim dimension of the indexing
64 * indices table of values being indexed by
65 */
66 VALUE *
associndex(ASSOC * ap,BOOL create,long dim,VALUE * indices)67 associndex(ASSOC *ap, BOOL create, long dim, VALUE *indices)
68 {
69 ASSOCELEM **listhead;
70 ASSOCELEM *ep;
71 STATIC VALUE val;
72 QCKHASH hash;
73 int i;
74
75 if (dim < 0) {
76 math_error("Negative dimension for indexing association");
77 /*NOTREACHED*/
78 }
79
80 /*
81 * Calculate the hash value to use for this set of indices
82 * so that we can first select the correct hash chain, and
83 * also so we can quickly compare each element for a match.
84 */
85 hash = QUICKHASH_BASIS;
86 for (i = 0; i < dim; i++)
87 hash = hashvalue(&indices[i], hash);
88
89 /*
90 * Search the correct hash chain for the specified set of indices.
91 * If found, return the address of the found element's value.
92 */
93 listhead = &ap->a_table[hash % ap->a_size];
94 for (ep = *listhead; ep; ep = ep->e_next) {
95 if ((ep->e_hash != hash) || (ep->e_dim != dim))
96 continue;
97 if (compareindices(ep->e_indices, indices, dim))
98 return &ep->e_value;
99 }
100
101 /*
102 * The set of indices was not found.
103 * Either return a pointer to a NULL value for a read reference,
104 * or allocate a new element in the list for a write reference.
105 */
106 if (!create) {
107 val.v_type = V_NULL;
108 val.v_subtype = V_NOSUBTYPE;
109 return &val;
110 }
111
112 ep = (ASSOCELEM *) malloc(ELEMSIZE(dim));
113 if (ep == NULL) {
114 math_error("Cannot allocate association element");
115 /*NOTREACHED*/
116 }
117 ep->e_dim = dim;
118 ep->e_hash = hash;
119 ep->e_value.v_type = V_NULL;
120 ep->e_value.v_subtype = V_NOSUBTYPE;
121 for (i = 0; i < dim; i++)
122 copyvalue(&indices[i], &ep->e_indices[i]);
123 ep->e_next = *listhead;
124 *listhead = ep;
125 ap->a_count++;
126
127 resize(ap, ap->a_count / CHAINLENGTH);
128
129 return &ep->e_value;
130 }
131
132
133 /*
134 * Search an association for the specified value starting at the
135 * specified index. Returns 0 and stores index if value found,
136 * otherwise returns 1.
137 */
138 int
assocsearch(ASSOC * ap,VALUE * vp,long i,long j,ZVALUE * index)139 assocsearch(ASSOC *ap, VALUE *vp, long i, long j, ZVALUE *index)
140 {
141 ASSOCELEM *ep;
142
143 if (i < 0 || j > ap->a_count) {
144 math_error("This should not happen in assocsearch");
145 /*NOTREACHED*/
146 }
147 while (i < j) {
148 ep = elemindex(ap, i);
149 if (ep == NULL) {
150 math_error("This should not happen in assocsearch");
151 /*NOTREACHED*/
152 }
153 if (acceptvalue(&ep->e_value, vp)) {
154 utoz(i, index);
155 return 0;
156 }
157 i++;
158 }
159 return 1;
160 }
161
162
163 /*
164 * Search an association backwards for the specified value starting at the
165 * specified index. Returns 0 and stores the index if the value is
166 * found; otherwise returns 1.
167 */
168 int
assocrsearch(ASSOC * ap,VALUE * vp,long i,long j,ZVALUE * index)169 assocrsearch(ASSOC *ap, VALUE *vp, long i, long j, ZVALUE *index)
170 {
171 ASSOCELEM *ep;
172
173 if (i < 0 || j > ap->a_count) {
174 math_error("This should not happen in assocsearch");
175 /*NOTREACHED*/
176 }
177 j--;
178 while (j >= i) {
179 ep = elemindex(ap, j);
180 if (ep == NULL) {
181 math_error("This should not happen in assocsearch");
182 /*NOTREACHED*/
183 }
184 if (acceptvalue(&ep->e_value, vp)) {
185 utoz(j, index);
186 return 0;
187 }
188 j--;
189 }
190 return 1;
191 }
192
193
194 /*
195 * Return the address of an element of an association indexed by the
196 * double-bracket operation.
197 *
198 * given:
199 * ap association to index into
200 * index index of desired element
201 */
202 S_FUNC ASSOCELEM *
elemindex(ASSOC * ap,long index)203 elemindex(ASSOC *ap, long index)
204 {
205 ASSOCELEM *ep;
206 int i;
207
208 if ((index < 0) || (index > ap->a_count))
209 return NULL;
210
211 /*
212 * This loop should be made more efficient by remembering
213 * previously requested locations within the association.
214 */
215 for (i = 0; i < ap->a_size; i++) {
216 for (ep = ap->a_table[i]; ep; ep = ep->e_next) {
217 if (index-- == 0)
218 return ep;
219 }
220 }
221 return NULL;
222 }
223
224
225 /*
226 * Return the address of the value specified by double-bracket indexing
227 * of an association. Returns NULL if there is no such element.
228 *
229 * given:
230 * ap association to index into
231 * index index of desired element
232 */
233 VALUE *
assocfindex(ASSOC * ap,long index)234 assocfindex(ASSOC *ap, long index)
235 {
236 ASSOCELEM *ep;
237
238 ep = elemindex(ap, index);
239 if (ep == NULL)
240 return NULL;
241 return &ep->e_value;
242 }
243
244
245 /*
246 * Returns the list of indices for an association element with specified
247 * double-bracket index.
248 */
249 LIST *
associndices(ASSOC * ap,long index)250 associndices(ASSOC *ap, long index)
251 {
252 ASSOCELEM *ep;
253 LIST *lp;
254 int i;
255
256 ep = elemindex(ap, index);
257 if (ep == NULL)
258 return NULL;
259 lp = listalloc();
260 for (i = 0; i < ep->e_dim; i++)
261 insertlistlast(lp, &ep->e_indices[i]);
262 return lp;
263 }
264
265
266 /*
267 * Compare two associations to see if they are identical.
268 * Returns TRUE if they are different.
269 */
270 BOOL
assoccmp(ASSOC * ap1,ASSOC * ap2)271 assoccmp(ASSOC *ap1, ASSOC *ap2)
272 {
273 ASSOCELEM **table1;
274 ASSOCELEM *ep1;
275 ASSOCELEM *ep2;
276 long size1;
277 long size2;
278 QCKHASH hash;
279 long dim;
280
281 if (ap1 == ap2)
282 return FALSE;
283 if (ap1->a_count != ap2->a_count)
284 return TRUE;
285
286 table1 = ap1->a_table;
287 size1 = ap1->a_size;
288 size2 = ap2->a_size;
289 while (size1-- > 0) {
290 for (ep1 = *table1++; ep1; ep1 = ep1->e_next) {
291 hash = ep1->e_hash;
292 dim = ep1->e_dim;
293 for (ep2 = ap2->a_table[hash % size2]; ;
294 ep2 = ep2->e_next) {
295 if (ep2 == NULL)
296 return TRUE;
297 if (ep2->e_hash != hash)
298 continue;
299 if (ep2->e_dim != dim)
300 continue;
301 if (compareindices(ep1->e_indices,
302 ep2->e_indices, dim))
303 break;
304 }
305 if (comparevalue(&ep1->e_value, &ep2->e_value))
306 return TRUE;
307 }
308 }
309 return FALSE;
310 }
311
312
313 /*
314 * Copy an association value.
315 */
316 ASSOC *
assoccopy(ASSOC * oldap)317 assoccopy(ASSOC *oldap)
318 {
319 ASSOC *ap;
320 ASSOCELEM *oldep;
321 ASSOCELEM *ep;
322 ASSOCELEM **listhead;
323 int oldhi;
324 int i;
325
326 ap = assocalloc(oldap->a_count / CHAINLENGTH);
327 ap->a_count = oldap->a_count;
328
329 for (oldhi = 0; oldhi < oldap->a_size; oldhi++) {
330 for (oldep = oldap->a_table[oldhi]; oldep;
331 oldep = oldep->e_next) {
332 ep = (ASSOCELEM *) malloc(ELEMSIZE(oldep->e_dim));
333 if (ep == NULL) {
334 math_error("Cannot allocate "
335 "association element");
336 /*NOTREACHED*/
337 }
338 ep->e_dim = oldep->e_dim;
339 ep->e_hash = oldep->e_hash;
340 ep->e_value.v_type = V_NULL;
341 ep->e_value.v_subtype = V_NOSUBTYPE;
342 for (i = 0; i < ep->e_dim; i++)
343 copyvalue(&oldep->e_indices[i],
344 &ep->e_indices[i]);
345 copyvalue(&oldep->e_value, &ep->e_value);
346 listhead = &ap->a_table[ep->e_hash % ap->a_size];
347 ep->e_next = *listhead;
348 *listhead = ep;
349 }
350 }
351 return ap;
352 }
353
354
355 /*
356 * Resize the hash table for an association to be the specified size.
357 * This is only actually done if the growth from the previous size is
358 * enough to make this worthwhile.
359 */
360 S_FUNC void
resize(ASSOC * ap,long newsize)361 resize(ASSOC *ap, long newsize)
362 {
363 ASSOCELEM **oldtable;
364 ASSOCELEM **newtable;
365 ASSOCELEM **oldlist;
366 ASSOCELEM **newlist;
367 ASSOCELEM *ep;
368 int i;
369
370 if (newsize < ap->a_size + GROWHASHSIZE)
371 return;
372
373 newsize = (long) next_prime((FULL)newsize);
374 newtable = (ASSOCELEM **) malloc(sizeof(ASSOCELEM *) * newsize);
375 if (newtable == NULL) {
376 math_error("No memory to grow association");
377 /*NOTREACHED*/
378 }
379 for (i = 0; i < newsize; i++)
380 newtable[i] = NULL;
381
382 oldtable = ap->a_table;
383 oldlist = oldtable;
384 for (i = 0; i < ap->a_size; i++) {
385 while (*oldlist) {
386 ep = *oldlist;
387 *oldlist = ep->e_next;
388 newlist = &newtable[ep->e_hash % newsize];
389 ep->e_next = *newlist;
390 *newlist = ep;
391 }
392 oldlist++;
393 }
394
395 ap->a_table = newtable;
396 ap->a_size = newsize;
397 free((char *) oldtable);
398 }
399
400
401 /*
402 * Free an association element, along with any contained values.
403 */
404 S_FUNC void
assoc_elemfree(ASSOCELEM * ep)405 assoc_elemfree(ASSOCELEM *ep)
406 {
407 int i;
408
409 for (i = 0; i < ep->e_dim; i++)
410 freevalue(&ep->e_indices[i]);
411 freevalue(&ep->e_value);
412 ep->e_dim = 0;
413 ep->e_next = NULL;
414 free((char *) ep);
415 }
416
417
418 /*
419 * Allocate a new association value with an initial hash table.
420 * The hash table size is set at specified (but at least a minimum size).
421 */
422 ASSOC *
assocalloc(long initsize)423 assocalloc(long initsize)
424 {
425 register ASSOC *ap;
426 int i;
427
428 if (initsize < MINHASHSIZE)
429 initsize = MINHASHSIZE;
430 ap = (ASSOC *) malloc(sizeof(ASSOC));
431 if (ap == NULL) {
432 math_error("No memory for association");
433 /*NOTREACHED*/
434 }
435 ap->a_count = 0;
436 ap->a_size = initsize;
437 ap->a_table = (ASSOCELEM **) malloc(sizeof(ASSOCELEM *) * initsize);
438 if (ap->a_table == NULL) {
439 free((char *) ap);
440 math_error("No memory for association");
441 /*NOTREACHED*/
442 }
443 for (i = 0; i < initsize; i++)
444 ap->a_table[i] = NULL;
445 return ap;
446 }
447
448
449 /*
450 * Free an association value, along with all of its elements.
451 */
452 void
assocfree(ASSOC * ap)453 assocfree(ASSOC *ap)
454 {
455 ASSOCELEM **listhead;
456 ASSOCELEM *ep;
457 ASSOCELEM *nextep;
458 int i;
459
460 listhead = ap->a_table;
461 for (i = 0; i < ap->a_size; i++) {
462 nextep = *listhead;
463 *listhead = NULL;
464 while (nextep) {
465 ep = nextep;
466 nextep = ep->e_next;
467 assoc_elemfree(ep);
468 }
469 listhead++;
470 }
471 free((char *) ap->a_table);
472 ap->a_table = NULL;
473 free((char *) ap);
474 }
475
476
477 /*
478 * Print out an association along with the specified number of
479 * its elements. The elements are printed out in shortened form.
480 */
481 void
assocprint(ASSOC * ap,long max_print)482 assocprint(ASSOC *ap, long max_print)
483 {
484 ASSOCELEM *ep;
485 long index;
486 long i;
487 int savemode;
488
489 if (max_print <= 0) {
490 math_fmt("assoc (%ld element%s)", ap->a_count,
491 ((ap->a_count == 1) ? "" : "s"));
492 return;
493 }
494 math_fmt("\n assoc (%ld element%s):\n", ap->a_count,
495 ((ap->a_count == 1) ? "" : "s"));
496
497 for (index = 0; ((index < max_print) && (index < ap->a_count));
498 index++) {
499 ep = elemindex(ap, index);
500 if (ep == NULL)
501 continue;
502 math_str(" [");
503 for (i = 0; i < ep->e_dim; i++) {
504 if (i)
505 math_chr(',');
506 savemode = math_setmode(MODE_FRAC);
507 printvalue(&ep->e_indices[i],
508 (PRINT_SHORT | PRINT_UNAMBIG));
509 math_setmode(savemode);
510 }
511 math_str("] = ");
512 printvalue(&ep->e_value, PRINT_SHORT | PRINT_UNAMBIG);
513 math_chr('\n');
514 }
515 if (max_print < ap->a_count)
516 math_str(" ...\n");
517 }
518
519
520 /*
521 * Compare two lists of index values to see if they are identical.
522 * Returns TRUE if they are the same.
523 */
524 S_FUNC BOOL
compareindices(VALUE * v1,VALUE * v2,long dim)525 compareindices(VALUE *v1, VALUE *v2, long dim)
526 {
527 int i;
528
529 for (i = 0; i < dim; i++)
530 if (v1[i].v_type != v2[i].v_type)
531 return FALSE;
532
533 while (dim-- > 0)
534 if (comparevalue(v1++, v2++))
535 return FALSE;
536
537 return TRUE;
538 }
539