c_cpp/etc/calc/block.c

   1 /*
   2  * block - fixed, dynamic, fifo and circular memory blocks
   3  *
   4  * Copyright (C) 1999-2007  Landon Curt Noll and Ernest Bowen
   5  *
   6  * Primary author:  Landon Curt Noll
   7  *
   8  * Calc is open software; you can redistribute it and/or modify it under
   9  * the terms of the version 2.1 of the GNU Lesser General Public License
  10  * as published by the Free Software Foundation.
  11  *
  12  * Calc is distributed in the hope that it will be useful, but WITHOUT
  13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  15  * Public License for more details.
  16  *
  17  * A copy of version 2.1 of the GNU Lesser General Public License is
  18  * distributed with calc under the filename COPYING-LGPL.  You should have
  19  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  20  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  21  *
  22  * @(#) $Revision: 30.1 $
  23  * @(#) $Id: block.c,v 30.1 2007/03/16 11:09:46 chongo Exp $
  24  * @(#) $Source: /usr/local/src/bin/calc/RCS/block.c,v $
  25  *
  26  * Under source code control:   1997/02/27 00:29:40
  27  * File existed as early as:    1997
  28  *
  29  * chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  30  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  31  */
  32
  33
  34 #include <stdio.h>
  35 #include "value.h"
  36 #include "zmath.h"
  37 #include "config.h"
  38 #include "block.h"
  39 #include "nametype.h"
  40 #include "str.h"
  41 #include "calcerr.h"
  42
  43 #define NBLOCKCHUNK 16
  44
  45 STATIC long nblockcount = 0;
  46 STATIC long maxnblockcount = 0;
  47 STATIC STRINGHEAD nblocknames;
  48 STATIC NBLOCK **nblocks;
  49
  50
  51 /* forward declarations */
  52 S_FUNC void blkchk(BLOCK*);
  53
  54
  55 /*
  56  * blkalloc - allocate a block
  57  *
  58  * given:
  59  *      len     - initial memory length of the block
  60  *      type    - BLK_TYPE_XYZ
  61  *      chunk   - allocation chunk size
  62  *
  63  * returns:
  64  *      pointer to a newly allocated BLOCK
  65  */
  66 BLOCK *
  67 blkalloc(int len, int chunk)
  68 {
  69         BLOCK *nblk;    /* new block allocated */
  70
  71         /*
  72          * firewall
  73          */
  74         if (len < 0)
  75                 len = 0;
  76         if (chunk <= 0)
  77                 chunk = BLK_CHUNKSIZE;
  78
  79         /*
  80          * allocate BLOCK
  81          */
  82         nblk = (BLOCK *)malloc(sizeof(BLOCK));
  83         if (nblk == NULL) {
  84                 math_error("cannot allocate block");
  85                 /*NOTREACHED*/
  86         }
  87
  88         /*
  89          * initialize BLOCK
  90          */
  91         nblk->blkchunk = chunk;
  92         nblk->maxsize = ((len+chunk)/chunk)*chunk;
  93         nblk->data = (USB8*)malloc(nblk->maxsize);
  94         if (nblk->data == NULL) {
  95                 math_error("cannot allocate block data storage");
  96                 /*NOTREACHED*/
  97         }
  98         memset(nblk->data, 0, nblk->maxsize);
  99         nblk->datalen = len;
 100
 101         /*
 102          * return BLOCK
 103          */
 104         if (conf->calc_debug & CALCDBG_BLOCK) {
 105                 blkchk(nblk);
 106         }
 107         return nblk;
 108 }
 109
 110
 111 /*
 112  * blk_free - free a block
 113  *
 114  * NOTE: THIS IS NOT THE CALC blktrunc() BUILTIN FUNCTION!!  This
 115  * is what is called to free block storage.
 116  *
 117  * given:
 118  *      blk     - the block to free
 119  */
 120 void
 121 blk_free(BLOCK *blk)
 122 {
 123         /* free if non-NULL */
 124         if (blk != NULL) {
 125
 126                 /* free data storage */
 127                 if (blk->data != NULL) {
 128                         free(blk->data);
 129                 }
 130
 131                 /* free the block */
 132                 free(blk);
 133         }
 134         return;
 135 }
 136
 137
 138 /*
 139  * blkchk - check the sanity of a block
 140  *
 141  * These checks should never fail if calc is working correctly.  During
 142  * debug time, we plan to call this function often.  Once we are satisfied,
 143  * we will normally call this code only in a few places.
 144  *
 145  * If "calc_debug" has the bit corresponding to CALCDBG_BLOCK set, this
 146  * function is called during execution of the following builtins:
 147  *
 148  *      alloc(), realloc(), free()
 149  *
 150  * given:
 151  *      blk     - the BLOCK to check
 152  *
 153  * returns:
 154  *      if all is ok, otherwise math_error() is called and this
 155  *      function does not return
 156  */
 157 S_FUNC void
 158 blkchk(BLOCK *blk)
 159 {
 160
 161         /*
 162          * firewall - general sanity check
 163          */
 164         if ((conf->calc_debug & CALCDBG_BLOCK) == 0) {
 165                 /* do nothing when debugging is disabled */
 166                 return;
 167         }
 168         if (blk == NULL) {
 169                 math_error("internal: blk ptr is NULL");
 170                 /*NOTREACHED*/
 171         }
 172
 173         /*
 174          * pointers must not be NULL
 175          */
 176         if (blk->data == NULL) {
 177                 math_error("internal: blk->data ptr is NULL");
 178                 /*NOTREACHED*/
 179         }
 180
 181         /*
 182          * check data lengths
 183          */
 184         if (blk->datalen < 0) {
 185                 math_error("internal: blk->datalen < 0");
 186                 /*NOTREACHED*/
 187         }
 188
 189         /*
 190          * check the datalen and datalen2 values
 191          */
 192         if (blk->datalen < 0) {
 193                 math_error("internal: blk->datalen < 0");
 194                 /*NOTREACHED*/
 195         }
 196         return;
 197 }
 198
 199
 200 /*
 201  * blkrealloc - reallocate a block
 202  *
 203  * Reallocation of a block can change several aspects of a block.
 204  *
 205  *      It can change the much data it holds or can hold.
 206  *
 207  *      It can change the memory footprint (in terms of
 208  *      how much storage is malloced for current or future use).
 209  *
 210  *      It can change the chunk size used to grow malloced size
 211  *      as the data size grows.
 212  *
 213  * Each of the len and chunksize may be kept the same.
 214  *
 215  * given:
 216  *      blk     - old BLOCK to reallocate
 217  *      newlen  - how much data the block holds
 218  *      newchunk - allocation chunk size (<0 ==> no change, 0 == default)
 219  */
 220 BLOCK *
 221 blkrealloc(BLOCK *blk, int newlen, int newchunk)
 222 {
 223         USB8 *nblk;     /* realloced storage */
 224         int newmax;     /* new maximum stoage size */
 225
 226         /*
 227          * firewall
 228          */
 229         if (conf->calc_debug & CALCDBG_BLOCK) {
 230                 blkchk(blk);
 231         }
 232
 233         /*
 234          * process args
 235          */
 236         /* newlen < 0 means do not change the length */
 237         if (newlen < 0) {
 238                 newlen = blk->datalen;
 239         }
 240         /* newchunk <= 0 means do not change the chunk size */
 241         if (newchunk < 0) {
 242                 newchunk = blk->blkchunk;
 243         } else if (newchunk == 0) {
 244                 newchunk = BLK_CHUNKSIZE;
 245         }
 246
 247         /*
 248          * reallocate storage if we have a different allocation size
 249          */
 250         newmax = ((newlen+newchunk)/newchunk)*newchunk;
 251         if (newmax != blk->maxsize) {
 252
 253                 /* reallocate new storage */
 254                 nblk = (USB8*)realloc(blk->data, newmax);
 255                 if (nblk == NULL) {
 256                         math_error("cannot reallocate block storage");
 257                         /*NOTREACHED*/
 258                 }
 259
 260                 /* clear any new storage */
 261                 if (newmax > blk->maxsize) {
 262                         memset(nblk+blk->maxsize, 0, (newmax-blk->maxsize));
 263                 }
 264                 blk->maxsize = newmax;
 265
 266                 /* restore the data pointers */
 267                 blk->data = nblk;
 268         }
 269
 270         /*
 271          * deal the case of a newlen == 0 early and return
 272          */
 273         if (newlen == 0) {
 274
 275                 /*
 276                  * setup the empty buffer
 277                  *
 278                  * We know that newtype is not circular since we force
 279                  * newlen to be at least 1 (because circular blocks
 280                  * always have at least one unused octet).
 281                  */
 282                 if (blk->datalen < blk->maxsize) {
 283                         memset(blk->data, 0, blk->datalen);
 284                 } else {
 285                         memset(blk->data, 0, blk->maxsize);
 286                 }
 287                 blk->datalen = 0;
 288                 if (conf->calc_debug & CALCDBG_BLOCK) {
 289                         blkchk(blk);
 290                 }
 291                 return blk;
 292         }
 293
 294         /*
 295          * Set the data length
 296          *
 297          * We also know that the new block is not empty since we have
 298          * already dealth with that case above.
 299          *
 300          * After this section of code, limit and datalen will be
 301          * correct in terms of the new type.
 302          */
 303         if (newlen > blk->datalen) {
 304
 305                 /* there is new storage, clear it */
 306                 memset(blk->data + blk->datalen, 0, newlen-blk->datalen);
 307                 /* growing storage for blocks grows the data */
 308                 blk->datalen = newlen;
 309
 310         } else if (newlen <= blk->datalen) {
 311
 312                 /* the block will be full */
 313                 blk->datalen = newlen;
 314         }
 315
 316         /*
 317          * return realloced type
 318          */
 319         if (conf->calc_debug & CALCDBG_BLOCK) {
 320                 blkchk(blk);
 321         }
 322         return blk;
 323 }
 324
 325
 326 /*
 327  * blktrunc - truncate a BLOCK down to a minimal fixed block
 328  *
 329  * NOTE: THIS IS NOT THE INTERNAL CALC FREE FUNCTION!!  This
 330  * is what blktrunc() builtin calls to reduce storage of a block
 331  * down to an absolute minimum.
 332  *
 333  * This actually forms a zero length fixed block with a chunk of 1.
 334  *
 335  * given:
 336  *      blk     - the BLOCK to shrink
 337  *
 338  * returns:
 339  *      pointer to a newly allocated BLOCK
 340  */
 341 void
 342 blktrunc(BLOCK *blk)
 343 {
 344         /*
 345          * firewall
 346          */
 347         if (conf->calc_debug & CALCDBG_BLOCK) {
 348                 blkchk(blk);
 349         }
 350
 351         /*
 352          * free the old storage
 353          */
 354         free(blk->data);
 355
 356         /*
 357          * setup as a zero length fixed block
 358          */
 359         blk->blkchunk = 1;
 360         blk->maxsize = 1;
 361         blk->datalen = 0;
 362         blk->data = (USB8*)malloc(1);
 363         if (blk->data == NULL) {
 364                 math_error("cannot allocate truncated block storage");
 365                 /*NOTREACHED*/
 366         }
 367         blk->data[0] = (USB8)0;
 368         if (conf->calc_debug & CALCDBG_BLOCK) {
 369                 blkchk(blk);
 370         }
 371         return;
 372 }
 373
 374
 375 /*
 376  * blk_copy - copy a block
 377  *
 378  * given:
 379  *      blk     - the block to copy
 380  *
 381  * returns:
 382  *      pointer to copy of blk
 383  */
 384 BLOCK *
 385 blk_copy(BLOCK *blk)
 386 {
 387         BLOCK *nblk;            /* copy of blk */
 388
 389         /*
 390          * malloc new block
 391          */
 392         nblk = (BLOCK *)malloc(sizeof(BLOCK));
 393         if (nblk == NULL) {
 394                 math_error("blk_copy: cannot malloc BLOCK");
 395                 /*NOTREACHED*/
 396         }
 397
 398         /*
 399          * duplicate most of the block
 400          */
 401         *nblk = *blk;
 402
 403         /*
 404          * duplicate block data
 405          */
 406         nblk->data = (USB8 *)malloc(blk->maxsize);
 407         if (nblk->data == NULL) {
 408                 math_error("blk_copy: cannot duplicate block data");
 409                 /*NOTREACHED*/
 410         }
 411         memcpy(nblk->data, blk->data, blk->maxsize);
 412         return nblk;
 413 }
 414
 415
 416 /*
 417  * blk_cmp - compare blocks
 418  *
 419  * given:
 420  *      a       first BLOCK
 421  *      b       second BLOCK
 422  *
 423  * returns:
 424  *      TRUE => BLOCKs are different
 425  *      FALSE => BLOCKs are the same
 426  */
 427 int
 428 blk_cmp(BLOCK *a, BLOCK *b)
 429 {
 430         /*
 431          * firewall and quick check
 432          */
 433         if (a == b) {
 434                 /* pointers to the same object */
 435                 return FALSE;
 436         }
 437         if (a == NULL || b == NULL) {
 438                 /* one pointer is NULL, so they differ */
 439                 return TRUE;
 440         }
 441
 442         /*
 443          * compare lengths
 444          */
 445         if (a->datalen != b->datalen) {
 446                 /* different lengths are different */
 447                 return TRUE;
 448         }
 449
 450         /*
 451          * compare the section
 452          *
 453          * We have the same lengths and types, so compare the data sections.
 454          */
 455         if (memcmp(a->data, b->data, a->datalen) != 0) {
 456                 /* different sections are different */
 457                 return TRUE;
 458         }
 459
 460         /*
 461          * the blocks are the same
 462          */
 463         return FALSE;
 464 }
 465
 466
 467 /*
 468  * Print chunksize, maxsize, datalen on line line and if datalen > 0,
 469  * up to * 30 octets on the following line, with ... if datalen exceeds 30.
 470  */
 471 /*ARGSUSED*/
 472 void
 473 blk_print(BLOCK *blk)
 474 {
 475         long i;
 476         BOOL havetail;
 477         USB8 *ptr;
 478
 479         /* XXX - should use the config parameters for better print control */
 480
 481         printf("chunksize = %d, maxsize = %d, datalen = %d\n\t",
 482                 (int)blk->blkchunk, (int)blk->maxsize, (int)blk->datalen);
 483         i = blk->datalen;
 484         havetail = (i > 30);
 485         if (havetail)
 486                 i = 30;
 487         ptr = blk->data;
 488         while (i-- > 0)
 489                 printf("%02x", *ptr++);
 490         if (havetail)
 491                 printf("...");
 492 }
 493
 494
 495 /*
 496  * Routine to print id and name of a named block and details of its
 497  * block component.
 498  */
 499 void
 500 nblock_print(NBLOCK *nblk)
 501 {
 502         BLOCK *blk;
 503
 504         /* XXX - use the config parameters for better print control */
 505
 506         blk = nblk->blk;
 507         printf("block %d: %s\n\t", nblk->id, nblk->name);
 508         if (blk->data == NULL) {
 509                 printf("chunksize = %d, maxsize = %d, datalen = %d\n\t",
 510                 (int)blk->blkchunk, (int)blk->maxsize, (int)blk->datalen);
 511                 printf("NULL");
 512         } else {
 513                 blk_print(blk);
 514         }
 515 }
 516
 517
 518 /*
 519  * realloc a named block specified by its id.  The new datalen and
 520  * chunksize are specified by len >= 0 and chunk > 0.  If len < 0
 521  * or chunk <= 0, these values used are the current datalen and
 522  * chunksize, so there is no point in calling this unless len >= 0
 523  * and/or chunk > 0.
 524  * No reallocation occurs if the new maxsize is equal to the old maxsize.
 525  */
 526 NBLOCK *
 527 reallocnblock(int id, int len, int chunk)
 528 {
 529         BLOCK *blk;
 530         int newsize;
 531         int oldsize;
 532         USB8* newdata;
 533
 534         /* Fire wall */
 535         if (id < 0 || id >= nblockcount) {
 536                 math_error("Bad id in call to reallocnblock");
 537                 /*NOTREACHED*/
 538         }
 539
 540         blk = nblocks[id]->blk;
 541         if (len < 0)
 542                 len = blk->datalen;
 543         if (chunk < 0)
 544                 chunk = blk->blkchunk;
 545         else if (chunk == 0)
 546                 chunk = BLK_CHUNKSIZE;
 547         newsize = (1 + len/chunk) * chunk;
 548         oldsize = blk->maxsize;
 549         newdata = blk->data;
 550         if (newdata == NULL) {
 551                 newdata = malloc(newsize);
 552                 if (newdata == NULL) {
 553                         math_error("Allocation failed");
 554                         /*NOTREACHED*/
 555                 }
 556         } else if (newsize != oldsize) {
 557                 newdata = realloc(blk->data, newsize);
 558                 if (newdata == NULL) {
 559                         math_error("Reallocation failed");
 560                         /*NOTREACHED*/
 561                 }
 562         }
 563         memset(newdata + len, 0, newsize - len);
 564
 565         blk->maxsize = newsize;
 566         blk->datalen = len;
 567         blk->blkchunk = chunk;
 568         blk->data = newdata;
 569         return nblocks[id];
 570 }
 571
 572
 573 /*
 574  * Create and return a new namedblock with specified name, len and
 575  * chunksize.
 576  */
 577 NBLOCK *
 578 createnblock(char *name, int len, int chunk)
 579 {
 580         NBLOCK *res;
 581         char *newname;
 582
 583         if (nblockcount >= maxnblockcount) {
 584                 if (maxnblockcount <= 0) {
 585                         maxnblockcount = NBLOCKCHUNK;
 586                         nblocks = (NBLOCK **)malloc(NBLOCKCHUNK *
 587                                                     sizeof(NBLOCK *));
 588                         if (nblocks == NULL) {
 589                                 maxnblockcount = 0;
 590                                 math_error("unable to malloc new named blocks");
 591                                 /*NOTREACHED*/
 592                         }
 593                 } else {
 594                         maxnblockcount += NBLOCKCHUNK;
 595                         nblocks = (NBLOCK **)realloc(nblocks, maxnblockcount *
 596                                                      sizeof(NBLOCK *));
 597                         if (nblocks == NULL) {
 598                                 maxnblockcount = 0;
 599                                 math_error("cannot malloc more named blocks");
 600                                 /*NOTREACHED*/
 601                         }
 602                 }
 603         }
 604         if (nblockcount == 0)
 605                 initstr(&nblocknames);
 606         if (findstr(&nblocknames, name) >= 0) {
 607                 math_error("Named block already exists!!!");
 608                 /*NOTREACHED*/
 609         }
 610         newname = addstr(&nblocknames, name);
 611         if (newname == NULL) {
 612                 math_error("Block name allocation failed");
 613                 /*NOTREACHED*/
 614         }
 615
 616         res = (NBLOCK *) malloc(sizeof(NBLOCK));
 617         if (res == NULL) {
 618                 math_error("Named block allocation failed");
 619                 /*NOTREACHED*/
 620         }
 621
 622         nblocks[nblockcount] = res;
 623         res->name = newname;
 624         res->subtype = V_NOSUBTYPE;
 625         res->id = nblockcount++;
 626         res->blk = blkalloc(len, chunk);
 627         return res;
 628 }
 629
 630
 631 /*
 632  * find a named block
 633  */
 634 int
 635 findnblockid(char * name)
 636 {
 637         return findstr(&nblocknames, name);
 638 }
 639
 640
 641 /*
 642  * free data block for named block with specified id
 643  */
 644 int
 645 removenblock(int id)
 646 {
 647         NBLOCK *nblk;
 648
 649         if (id < 0 || id >= nblockcount)
 650                 return E_BLKFREE3;
 651         nblk = nblocks[id];
 652         if (nblk->blk->data == NULL)
 653                 return 0;
 654         if (nblk->subtype & V_NOREALLOC)
 655                 return E_BLKFREE5;
 656         free(nblk->blk->data);
 657         nblk->blk->data = NULL;
 658         nblk->blk->maxsize = 0;
 659         nblk->blk->datalen = 0;
 660         return 0;
 661 }
 662
 663
 664 /*
 665  * count number of current unfreed named blocks
 666  */
 667 int
 668 countnblocks(void)
 669 {
 670         int n;
 671         int id;
 672
 673         for (n = 0, id = 0; id < nblockcount; id++) {
 674                 if (nblocks[id]->blk->data != NULL)
 675                         n++;
 676         }
 677         return n;
 678 }
 679
 680
 681 /*
 682  * display id and name for each unfreed named block
 683  */
 684 void
 685 shownblocks(void)
 686 {
 687         int id;
 688
 689         if (countnblocks() == 0) {
 690                 printf("No unfreed named blocks\n\n");
 691                 return;
 692         }
 693         printf(" id   name\n");
 694         printf("----  -----\n");
 695         for (id = 0; id < nblockcount; id++) {
 696                 if (nblocks[id]->blk->data != NULL)
 697                         printf("%3d   %s\n", id, nblocks[id]->name);
 698         }
 699         printf("\n");
 700 }
 701
 702
 703 /*
 704  * Return pointer to nblock with specified id, NULL if never created.
 705  * The memory for the nblock found may have been freed.
 706  */
 707 NBLOCK *
 708 findnblock(int id)
 709 {
 710         if (id < 0 || id >= nblockcount)
 711                 return NULL;
 712         return nblocks[id];
 713 }
 714
 715
 716 /*
 717  * Create a new block with specified newlen and new chunksize and copy
 718  * min(newlen, oldlen) octets to the new block.  The old block is
 719  * not changed.
 720  */
 721 BLOCK *
 722 copyrealloc(BLOCK *blk, int newlen, int newchunk)
 723 {
 724         BLOCK * newblk;
 725         int oldlen;
 726
 727         oldlen = blk->datalen;
 728
 729         if (newlen < 0)                 /* retain length */
 730                 newlen = oldlen;
 731
 732         if (newchunk < 0)               /* retain chunksize */
 733                 newchunk = blk->blkchunk;
 734         else if (newchunk == 0)         /* use default chunksize */
 735                 newchunk = BLK_CHUNKSIZE;
 736
 737
 738         newblk = blkalloc(newlen, newchunk);
 739
 740         if (newlen < oldlen)
 741                 oldlen = newlen;
 742
 743         if (newlen > 0)
 744                 memcpy(newblk->data, blk->data, oldlen);
 745
 746         return newblk;
 747 }