c_cpp/etc/calc/assocfunc.c

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