c_cpp/etc/calc/str.c

   1 /*
   2  * str - string list routines
   3  *
   4  * Copyright (C) 1999-2007  David I. Bell and Ernest Bowen
   5  *
   6  * Primary author:  David I. Bell
   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.2 $
  23  * @(#) $Id: str.c,v 30.2 2013/08/11 08:41:38 chongo Exp $
  24  * @(#) $Source: /usr/local/src/bin/calc/RCS/str.c,v $
  25  *
  26  * Under source code control:   1990/02/15 01:48:10
  27  * File existed as early as:    before 1990
  28  *
  29  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  30  */
  31
  32
  33 #include <stdio.h>
  34 #include "calc.h"
  35 #include "str.h"
  36
  37 #define STR_TABLECHUNK  100     /* how often to reallocate string table */
  38 #define STR_CHUNK       2000    /* size of string storage allocation */
  39 #define STR_UNIQUE      100     /* size of string to allocate separately */
  40
  41 STRING _nullstring_ = {"", 0, 1, NULL};
  42
  43 STATIC char *chartable;         /* single character string table */
  44
  45 STATIC struct {
  46         long l_count;           /* count of strings in table */
  47         long l_maxcount;        /* maximum strings storable in table */
  48         size_t l_avail;         /* characters available in current string */
  49         char *l_alloc;          /* next available string storage */
  50         char **l_table;         /* current string table */
  51 } literals;
  52
  53
  54 /*
  55  * Initialize or reinitialize a string header for use.
  56  *
  57  * given:
  58  *      hp              structure to be inited
  59  */
  60 void
  61 initstr(STRINGHEAD *hp)
  62 {
  63         if (hp->h_list == NULL) {
  64                 hp->h_list = (char *)malloc(2000);
  65                 hp->h_avail = 2000;
  66                 hp->h_used = 0;
  67         }
  68         hp->h_avail += hp->h_used;
  69         hp->h_used = 0;
  70         hp->h_count = 0;
  71         hp->h_list[0] = '\0';
  72         hp->h_list[1] = '\0';
  73 }
  74
  75
  76 /*
  77  * Copy a string to the end of a list of strings, and return the address
  78  * of the copied string.  Returns NULL if the string could not be copied.
  79  * No checks are made to see if the string is already in the list.
  80  * The string cannot be null or have imbedded nulls.
  81  *
  82  * given:
  83  *      hp              header of string storage
  84  *      str             string to be added
  85  */
  86 char *
  87 addstr(STRINGHEAD *hp, char *str)
  88 {
  89         char *retstr;           /* returned string pointer */
  90         char *list;             /* string list */
  91         long newsize;           /* new size of string list */
  92         size_t len;             /* length of current string */
  93
  94         if ((str == NULL) || (*str == '\0'))
  95                 return NULL;
  96         len = strlen(str) + 1;
  97         if (hp->h_avail <= len) {
  98                 newsize = len + 2000 + hp->h_used + hp->h_avail;
  99                 list = (char *)realloc(hp->h_list, newsize);
 100                 if (list == NULL)
 101                         return NULL;
 102                 hp->h_list = list;
 103                 hp->h_avail = newsize - hp->h_used;
 104         }
 105         retstr = hp->h_list + hp->h_used;
 106         hp->h_used += len;
 107         hp->h_avail -= len;
 108         hp->h_count++;
 109         strcpy(retstr, str);
 110         retstr[len] = '\0';
 111         return retstr;
 112 }
 113
 114
 115 /*
 116  * Return a null-terminated string which consists of a single character.
 117  * The table is initialized on the first call.
 118  */
 119 char *
 120 charstr(int ch)
 121 {
 122         char *cp;
 123         int i;
 124
 125         if (chartable == NULL) {
 126                 cp = (char *)malloc(512);
 127                 if (cp == NULL) {
 128                         math_error("Cannot allocate character table");
 129                         /*NOTREACHED*/
 130                 }
 131                 for (i = 0; i < 256; i++) {
 132                         *cp++ = (char)i;
 133                         *cp++ = '\0';
 134                 }
 135                 chartable = cp - 512;
 136         }
 137         return &chartable[(ch & 0xff) * 2];
 138 }
 139
 140
 141 /*
 142  * Find a string with the specified name and return its number in the
 143  * string list.  The first string is numbered zero.  Minus one is returned
 144  * if the string is not found.
 145  *
 146  * given:
 147  *      hp              header of string storage
 148  *      str             string to be added
 149  */
 150 int
 151 findstr(STRINGHEAD *hp, char *str)
 152 {
 153         register char *test;    /* string being tested */
 154         size_t len;             /* length of string being found */
 155         size_t testlen;         /* length of test string */
 156         int index;              /* index of string */
 157
 158         if ((hp->h_count <= 0) || (str == NULL))
 159                 return -1;
 160         len = strlen(str);
 161         test = hp->h_list;
 162         index = 0;
 163         while (*test) {
 164                 testlen = strlen(test);
 165                 if ((testlen == len) && (*test == *str) &&
 166                     (strcmp(test, str) == 0))
 167                         return index;
 168                 test += (testlen + 1);
 169                 index++;
 170         }
 171         return -1;
 172 }
 173
 174
 175 /*
 176  * Return the name of a string with the given index.
 177  * If the index is illegal, a pointer to an empty string is returned.
 178  *
 179  * given:
 180  *      hp              header of string storage
 181  *      n               string index
 182  */
 183 char *
 184 namestr(STRINGHEAD *hp, long n)
 185 {
 186         register char *str;     /* current string */
 187
 188         if (n >= hp->h_count)
 189                 return "";
 190         str = hp->h_list;
 191         while (*str) {
 192                 if (--n < 0)
 193                         return str;
 194                 str += (strlen(str) + 1);
 195         }
 196         return "";
 197 }
 198
 199
 200 /*
 201  * Useful routine to return the index of one string within another one
 202  * which has the format:  "str1\000str2\000str3\000...strn\0\0".  Index starts
 203  * at one for the first string.  Returns zero if the string being checked
 204  * is not contained in the formatted string.
 205  *
 206  * Be sure to use \000 instead of \0.  ANSI-C compilers interpret "foo\0foo..."
 207  * as "foo\017oo...".
 208  *
 209  * given:
 210  *      format          string formatted into substrings
 211  *      test            string to be found in formatted string
 212  */
 213 long
 214 stringindex(char *format, char *test)
 215 {
 216         long index;             /* found index */
 217         size_t len;             /* length of current piece of string */
 218         size_t testlen;         /* length of test string */
 219
 220         testlen = strlen(test);
 221         index = 1;
 222         while (*format) {
 223                 len = strlen(format);
 224                 if ((len == testlen) && (*format == *test) &&
 225                         (strcmp(format, test) == 0))
 226                                 return index;
 227                 format += (len + 1);
 228                 index++;
 229         }
 230         return 0;
 231 }
 232
 233
 234 /*
 235  * Add a possibly new literal string to the literal string pool.
 236  * Returns the new string address which is guaranteed to be always valid.
 237  * Duplicate strings will repeatedly return the same address.
 238  */
 239 char *
 240 addliteral(char *str)
 241 {
 242         register char **table;  /* table of strings */
 243         char *newstr;           /* newly allocated string */
 244         long count;             /* number of strings */
 245         size_t len;             /* length of string to allocate */
 246
 247         len = strlen(str);
 248         if (len <= 1)
 249                 return charstr(*str);
 250         /*
 251          * See if the string is already in the table.
 252          */
 253         table = literals.l_table;
 254         count = literals.l_count;
 255         while (count-- > 0) {
 256                 if ((str[0] == table[0][0]) && (str[1] == table[0][1]) &&
 257                         (strcmp(str, table[0]) == 0))
 258                                 return table[0];
 259                 table++;
 260         }
 261         /*
 262          * Make the table of string pointers larger if necessary.
 263          */
 264         if (literals.l_count >= literals.l_maxcount) {
 265                 count = literals.l_maxcount + STR_TABLECHUNK;
 266                 if (literals.l_maxcount)
 267                         table = (char **) realloc(literals.l_table, count *
 268                                                   sizeof(char *));
 269                 else
 270                         table = (char **) malloc(count * sizeof(char *));
 271                 if (table == NULL) {
 272                         math_error("Cannot allocate string literal table");
 273                         /*NOTREACHED*/
 274                 }
 275                 literals.l_table = table;
 276                 literals.l_maxcount = count;
 277         }
 278         table = literals.l_table;
 279         /*
 280          * If the new string is very long, allocate it manually.
 281          */
 282         len = (len + 2) & ~1;   /* add room for null and round up to word */
 283         if (len >= STR_UNIQUE) {
 284                 newstr = (char *)malloc(len);
 285                 if (newstr == NULL) {
 286                         math_error("Cannot allocate large literal string");
 287                         /*NOTREACHED*/
 288                 }
 289                 strcpy(newstr, str);
 290                 table[literals.l_count++] = newstr;
 291                 return newstr;
 292         }
 293         /*
 294          * If the remaining space in the allocate string is too small,
 295          * then allocate a new one.
 296          */
 297         if (literals.l_avail < len) {
 298                 newstr = (char *)malloc(STR_CHUNK);
 299                 if (newstr == NULL) {
 300                         math_error("Cannot allocate new literal string");
 301                         /*NOTREACHED*/
 302                 }
 303                 literals.l_alloc = newstr;
 304                 literals.l_avail = STR_CHUNK;
 305         }
 306         /*
 307          * Allocate the new string from the allocate string.
 308          */
 309         newstr = literals.l_alloc;
 310         literals.l_avail -= len;
 311         literals.l_alloc += len;
 312         table[literals.l_count++] = newstr;
 313         strcpy(newstr, str);
 314         return newstr;
 315 }
 316
 317
 318 STRING *
 319 stringadd(STRING *s1, STRING *s2)
 320 {
 321         STRING *s;
 322         char *cfrom, *c;
 323         long len;
 324
 325         len = s1->s_len + s2->s_len;
 326         s = stralloc();
 327         s->s_len = len;
 328         s->s_str = (char *) malloc(len + 1);
 329         if (s->s_str == NULL)
 330                 return NULL;
 331         len = s1->s_len;
 332         cfrom = s1->s_str;
 333         c = s->s_str;
 334         while (len-- > 0)
 335                 *c++ = *cfrom++;
 336         len = s2->s_len;
 337         cfrom = s2->s_str;
 338         while (len-- > 0)
 339                 *c++ = *cfrom++;
 340         *c = '\0';
 341         return s;
 342 }
 343
 344 /*
 345  * stringneg reverses the characters in a string, returns null if malloc fails
 346  */
 347 STRING *
 348 stringneg(STRING *str)
 349 {
 350         long len;
 351         STRING *s;
 352         char *c, *cfrom;
 353
 354         len = str->s_len;
 355         if (len <= 1)
 356                 return slink(str);
 357         c = (char *) malloc(len + 1);
 358         if (c == NULL)
 359                 return NULL;
 360         s = stralloc();
 361         s->s_len = len;
 362         s->s_str = c;
 363         cfrom = str->s_str + len;
 364         while (len-- > 0)
 365                 *c++ = *--cfrom;
 366         *c = '\0';
 367         return s;
 368 }
 369
 370 STRING *
 371 stringsub(STRING *s1, STRING *s2)
 372 {
 373         STRING *tmp, *s;
 374
 375         tmp = stringneg(s2);
 376         if (tmp == NULL)
 377                 return NULL;
 378         s = stringadd(s1, tmp);
 379         if (s != NULL)
 380                 sfree(tmp);
 381         return s;
 382 }
 383
 384 /*
 385  * stringmul: repeated concatenation, reverse if negative multiplier
 386  * returns null if malloc fails
 387  */
 388 STRING *
 389 stringmul(NUMBER *q, STRING *str)
 390 {
 391         long len;
 392         size_t j;
 393         NUMBER *tmp1, *tmp2;
 394         char *c, *c1;
 395         STRING *s;
 396         BOOL neg;
 397
 398         if (str->s_len == 0)
 399                 return slink(str);
 400         neg = qisneg(q);
 401         q = neg ? qneg(q): qlink(q);
 402         tmp1 = itoq(str->s_len);
 403         tmp2 = qmul(q, tmp1);
 404         qfree(tmp1);
 405         tmp1 = qint(tmp2);
 406         qfree(tmp2);
 407         if (zge31b(tmp1->num)) {
 408                 qfree(q);
 409                 qfree(tmp1);
 410                 return NULL;
 411         }
 412         len = qtoi(tmp1);
 413         qfree(tmp1);
 414         qfree(q);
 415         if (len == 0)
 416                 return slink(&_nullstring_);
 417         c = (char *) malloc(len + 1);
 418         if (c == NULL)
 419                 return NULL;
 420         str = neg ? stringneg(str) : slink(str);
 421         s = stralloc();
 422         s->s_str = c;
 423         s->s_len = len;
 424         j = 0;
 425         c1 = str->s_str;
 426         while (len-- > 0) {
 427                 *c++ = *c1++;
 428                 if (++j == str->s_len) {
 429                         j = 0;
 430                         c1 = str->s_str;
 431                 }
 432         }
 433         *c = '\0';
 434         sfree(str);
 435         return s;
 436 }
 437
 438 STRING *
 439 stringand(STRING *s1, STRING *s2)
 440 {
 441         STRING *s;
 442         size_t len;
 443         char *c1, *c2, *c;
 444
 445         if (s1->s_len == 0  || s2->s_len == 0)
 446                 return slink(&_nullstring_);
 447         len = s1->s_len;
 448         if (s2->s_len < len)
 449                 len = s2->s_len;
 450         s = stralloc();
 451         s->s_len = len;
 452         c = malloc(len + 1);
 453         if (c == NULL)
 454                 return NULL;
 455         s->s_str = c;
 456         c1 = s1->s_str;
 457         c2 = s2->s_str;
 458         while (len-- > 0)
 459                 *c++ = *c1++ & *c2++;
 460         return s;
 461 }
 462
 463
 464 STRING *
 465 stringor(STRING *s1, STRING *s2)
 466 {
 467         STRING *s;
 468         long len, i, j;
 469         char *c1, *c2, *c;
 470
 471         if (s1->s_len < s2->s_len) {
 472                 s = s1;
 473                 s1 = s2;
 474                 s2 = s;
 475         }               /* Now len(s1) >= len(s2) */
 476         if (s2->s_len == 0)
 477                 return slink(s1);
 478         i = s1->s_len;
 479         if (i == 0)
 480                 return slink(&_nullstring_);
 481         len = s1->s_len;
 482         s = stralloc();
 483         s->s_len = len;
 484         c = malloc(len + 1);
 485         if (c == NULL)
 486                 return NULL;
 487         s->s_str = c;
 488         c1 = s1->s_str;
 489         c2 = s2->s_str;
 490         i = s2->s_len;
 491         j = s1->s_len - i;
 492         while (i-- > 0)
 493                 *c++ = *c1++ | *c2++;
 494         while (j-- > 0)
 495                 *c++ = *c1++;
 496         return s;
 497 }
 498
 499
 500 STRING *
 501 stringxor(STRING *s1, STRING *s2)
 502 {
 503         STRING *s;
 504         long len, i, j;
 505         char *c1, *c2, *c;
 506
 507         if (s1->s_len < s2->s_len) {
 508                 s = s1;
 509                 s1 = s2;
 510                 s2 = s;
 511         }               /* Now len(s1) >= len(s2) */
 512         if (s2->s_len == 0)
 513                 return slink(s1);
 514         i = s1->s_len;
 515         if (i == 0)
 516                 return slink(&_nullstring_);
 517         len = s1->s_len;
 518         s = stralloc();
 519         s->s_len = len;
 520         c = malloc(len + 1);
 521         if (c == NULL)
 522                 return NULL;
 523         s->s_str = c;
 524         c1 = s1->s_str;
 525         c2 = s2->s_str;
 526         i = s2->s_len;
 527         j = s1->s_len - i;
 528         while (i-- > 0)
 529                 *c++ = *c1++ ^ *c2++;
 530         while (j-- > 0)
 531                 *c++ = *c1++;
 532         return s;
 533 }
 534
 535
 536 STRING *
 537 stringdiff(STRING *s1, STRING *s2)
 538 {
 539         STRING *s;
 540         size_t i;
 541         char *c2, *c;
 542
 543         i = s1->s_len;
 544         if (i == 0)
 545                 return slink(s1);
 546         s = stringcopy(s1);
 547         if (i > s2->s_len)
 548                 i = s2->s_len;
 549         c = s->s_str;
 550         c2 = s2->s_str;
 551         while (i-- > 0)
 552                 *c++ &= ~*c2++;
 553         return s;
 554 }
 555
 556 STRING *
 557 stringcomp(STRING *s1)
 558 {
 559         long len;
 560         STRING *s;
 561         char *c1, *c;
 562
 563         len = s1->s_len;
 564         if (len == 0)
 565                 return slink(&_nullstring_);
 566         c = malloc(len + 1);
 567         if (c == NULL)
 568                 return NULL;
 569         s = stralloc();
 570         s->s_len = len;
 571         s->s_str = c;
 572         c1 = s1->s_str;
 573         while (len-- > 0)
 574                 *c++ = ~*c1++;
 575         *c = '\0';
 576         return s;
 577 }
 578
 579 STRING *
 580 stringsegment(STRING *s1, long n1, long n2)
 581 {
 582         STRING *s;
 583         char *c, *c1;
 584         long len;
 585
 586         if ((n1 < 0 && n2 < 0) ||
 587             ((size_t)n1 >= s1->s_len && (size_t)n2 >= s1->s_len))
 588                 return slink(&_nullstring_);
 589         if (n1 < 0)
 590                 n1 = 0;
 591         if (n2 < 0)
 592                 n2 = 0;
 593         if ((size_t)n1 >= s1->s_len)
 594                 n1 = s1->s_len - 1;
 595         if ((size_t)n2 >= s1->s_len)
 596                 n2 = s1->s_len - 1;
 597         len = (n1 >= n2) ? n1 - n2 + 1 : n2 - n1 + 1;
 598         s = stralloc();
 599         c = malloc(len + 1);
 600         if (c == NULL)
 601                 return NULL;
 602         s->s_len = len;
 603         s->s_str = c;
 604         c1 = s1->s_str + n1;
 605         if (n1 >= n2) {
 606                 /*
 607                  * We prevent the c1 pointer from walking behind s1_s_str
 608                  * by stopping one short of the end and running the loop one
 609                  * more time.
 610                  *
 611                  * We could stop the loop with just len-- > 0, but stopping
 612                  * short and running the loop one last time manually helps make
 613                  * code checkers such as insure happy.
 614                  */
 615                 while (len-- > 1) {
 616                         *c++ = *c1--;
 617                 }
 618                 /* run the loop manually one last time */
 619                 *c++ = *c1;
 620         } else {
 621                 while (len-- > 0)
 622                         *c++ = *c1++;
 623         }
 624         *c = '\0';
 625         return s;
 626 }
 627
 628 /*
 629  * stringshift shifts s1 n bits to left if n > 0, -n to the right if n < 0;
 630  * octets in string considered to be in decreasing order of index, as in
 631  * ... a_3 a_2 a_1 a_0.  Returned string has same length as s1.
 632  * Vacated bits are filled with '\0'; bits shifted off end are lost
 633  */
 634 STRING *
 635 stringshift(STRING *s1, long n)
 636 {
 637         char *c1, *c;
 638         STRING *s;
 639         long len, i, j, k;
 640         BOOL right;
 641         char ch;
 642
 643         len = s1->s_len;
 644         if (len == 0 || n == 0)
 645                 return slink(s1);
 646         right = (n < 0);
 647         if (right) n = -n;
 648         j = n & 7;
 649         k = 8 - j;
 650         n >>= 3;
 651         c = malloc(len + 1);
 652         if (c == NULL)
 653                 return NULL;
 654         s = stralloc();
 655         s->s_len = len;
 656         s->s_str = c;
 657         c[len] = '\0';
 658         if (n > len)
 659                 n = len;
 660         ch = '\0';
 661         c1 = s1->s_str;
 662         i = n;
 663         if (right) {
 664                 c += len;
 665                 c1 += len;
 666                 while (i-- > 0)
 667                         *--c = '\0';
 668                 i = len - n;
 669                 while (i-- > 0) {
 670                         *--c = ((unsigned char) *--c1 >> j) | ch;
 671                         ch = (unsigned char) *c1 << k;
 672                 }
 673         } else {
 674                 while (i-- > 0)
 675                         *c++ = '\0';
 676                 i = len - n;
 677                 while (i-- > 0) {
 678                         *c++ = ((unsigned char) *c1 << j) | ch;
 679                         ch = (unsigned char) *c1++ >> k;
 680                 }
 681         }
 682         return s;
 683 }
 684
 685 /*
 686  * stringcpy copies as many characters as possible
 687  * from s2 to s1 and returns s1
 688  */
 689 STRING *
 690 stringcpy(STRING *s1, STRING *s2)
 691 {
 692         char *c1, *c2;
 693         size_t num;
 694
 695         if (s1->s_len > 0) {
 696                 c1 = s1->s_str;
 697                 c2 = s2->s_str;
 698                 num = s1->s_len;
 699                 if (num > s2->s_len)
 700                         num = s2->s_len;
 701                 while (num-- > 0)
 702                         *c1++ = *c2++;
 703                 *c1 = '\0';
 704         }
 705         return slink(s1);
 706 }
 707
 708 /*
 709  * stringncpy copies up to num characters from s2 to s1 and returns s1
 710  * If num > size(s2) null characters are copied until s1 is full or
 711  * a total of num characters have been copied
 712  */
 713 STRING *
 714 stringncpy(STRING *s1, STRING *s2, size_t num)
 715 {
 716         char *c1, *c2;
 717         size_t i;
 718
 719         if (num > s1->s_len)
 720                 num = s1->s_len;
 721         i = num;
 722         if (i > s2->s_len)
 723                 i = s2->s_len;
 724         c1 = s1->s_str;
 725         c2 = s2->s_str;
 726         while (i-- > 0)
 727                 *c1++ = *c2++;
 728         if (num > s2->s_len) {
 729                 memset(c1, 0, num - s2->s_len);
 730         }
 731         return slink(s1);
 732 }
 733
 734
 735 /*
 736  * stringcontent counts the number of set bits in s
 737  */
 738 long
 739 stringcontent(STRING *s)
 740 {
 741         char *c;
 742         unsigned char ch;
 743         long count;
 744         long len;
 745
 746         len = s->s_len;
 747         count = 0;
 748         c = s->s_str;
 749         while (len-- > 0) {
 750                 ch = *c++;
 751                 while (ch) {
 752                         count += (ch & 1);
 753                         ch >>= 1;
 754                 }
 755         }
 756         return count;
 757 }
 758
 759 long
 760 stringhighbit(STRING *s)
 761 {
 762         char *c;
 763         unsigned char ch;
 764         long i;
 765
 766         i = s->s_len;
 767         c = s->s_str + i;
 768         while (--i >= 0 && *--c == '\0');
 769         if (i < 0)
 770                 return -1;
 771         i <<= 3;
 772         for (ch = *c; ch >>= 1; i++);
 773         return i;
 774 }
 775
 776 long
 777 stringlowbit(STRING *s)
 778 {
 779         char *c;
 780         unsigned char ch;
 781         long i;
 782
 783         for (i = s->s_len, c = s->s_str; i > 0 && *c ==  '\0'; i--, c++);
 784         if (i == 0)
 785                 return -1;
 786         i = (s->s_len - i) << 3;
 787         for (ch = *c; !(ch & 1); ch >>= 1, i++);
 788         return i;
 789 }
 790
 791
 792 /*
 793  * stringcompare compares first len characters of strings starting at c1, c2
 794  * Returns TRUE if and only if a difference is encountered.
 795  * Essentially a local version of memcmp.
 796  */
 797 S_FUNC BOOL
 798 stringcompare(char *c1, char *c2, long len)
 799 {
 800         while (len-- > 0) {
 801                 if (*c1++ != *c2++)
 802                         return TRUE;
 803         }
 804         return FALSE;
 805 }
 806
 807 /*
 808  * stringcmp returns TRUE if strings differ, FALSE if strings equal
 809  */
 810 BOOL
 811 stringcmp(STRING *s1, STRING *s2)
 812 {
 813         if (s1->s_len != s2->s_len)
 814                 return TRUE;
 815         return stringcompare(s1->s_str, s2->s_str, s1->s_len);
 816 }
 817
 818
 819 /*
 820  * stringrel returns 0 if strings are equal; otherwise 1 or -1 according
 821  * as the greater of the first unequal characters are in the first or
 822  * second string, or in the case of unequal-length strings when the compared
 823  * characters are all equal, 1 or -1 according as the first or second string
 824  * is longer.
 825  */
 826 FLAG
 827 stringrel(STRING *s1, STRING *s2)
 828 {
 829         char *c1, *c2;
 830         long i1, i2;
 831
 832         if (s1 == s2)
 833                 return 0;
 834
 835         i1 = s1->s_len;
 836         i2 = s2->s_len;
 837         if (i2 == 0)
 838                 return (i1 > 0);
 839         if (i1 == 0)
 840                 return -1;
 841         c1 = s1->s_str;
 842         c2 = s2->s_str;
 843         while (i1 > 1 && i2 > 1 && *c1 == *c2) {
 844                 i1--;
 845                 i2--;
 846                 c1++;
 847                 c2++;
 848         }
 849         if ((unsigned char) *c1 > (unsigned char) *c2) return 1;
 850         if ((unsigned char) *c1 < (unsigned char) *c2) return -1;
 851         if (i1 < i2) return -1;
 852         return (i1 > i2);
 853 }
 854
 855
 856 /*
 857  * str with characters c0, c1, ... is considered as a bitstream, 8 bits
 858  * per character; within a character the bits ordered from low order to
 859  * high order.  For 0 <= i < 8 * length of str, stringbit returns 1 or 0
 860  * according as the bit with index i is set or not set; other values of i
 861  * return -1.
 862  */
 863 int
 864 stringbit(STRING *s, long index)
 865 {
 866         unsigned int ch;
 867         int res;
 868
 869         if (index < 0)
 870                 return -1;
 871         res = index & 7;
 872         index >>= 3;
 873         if ((size_t)index >= s->s_len)
 874                 return -1;
 875         ch = s->s_str[index];
 876         return (ch >> res) & 1;
 877 }
 878
 879
 880 BOOL
 881 stringtest(STRING *s)
 882 {
 883         long i;
 884         char *c;
 885
 886         i = s->s_len;
 887         c = s->s_str;
 888         while (i-- > 0) {
 889                 if (*c++)
 890                         return TRUE;
 891         }
 892         return FALSE;
 893 }
 894
 895 /*
 896  * If index is in acceptable range, stringsetbit sets or resets specified
 897  * bit in string s according as val is TRUE or FALSE, and returns 0.
 898  * Returns 1 if index < 0; 2 if index too large.
 899  */
 900 int
 901 stringsetbit(STRING *s, long index, BOOL val)
 902 {
 903         char *c;
 904         int bit;
 905
 906         if (index < 0)
 907                 return 1;
 908         bit = 1 << (index & 7);
 909         index >>= 3;
 910         if ((size_t)index >= s->s_len)
 911                 return 2;
 912         c = &s->s_str[index];
 913         *c &= ~bit;
 914         if (val)
 915                 *c |= bit;
 916         return 0;
 917 }
 918
 919 /*
 920  * stringsearch returns 0 and sets index = i if the first occurrence
 921  * of s2 in s1 for start <= i < end is at index i.  If no such occurrence
 922  * is found, -1 is returned.
 923  */
 924 int
 925 stringsearch(STRING *s1, STRING *s2, long start, long end, ZVALUE *index)
 926 {
 927         long len2, i, j;
 928         char *c1, *c2, *c;
 929         char ch;
 930
 931         len2 = s2->s_len;
 932         if (start < 0)
 933                 start = 0;
 934         if (end < start + len2)
 935                 return -1;
 936         if (len2 == 0) {
 937                 itoz(start, index);
 938                 return 0;
 939         }
 940         i = end - start - len2;
 941         c1 = s1->s_str + start;
 942         ch = *s2->s_str;
 943         while (i-- >= 0) {
 944                 if (*c1++ == ch) {
 945                         c = c1;
 946                         c2 = s2->s_str;
 947                         j = len2;
 948                         while (--j > 0 && *c++ == *++c2);
 949                         if (j == 0) {
 950                                 itoz(end - len2 - i - 1, index);
 951                                 return 0;
 952                         }
 953                 }
 954         }
 955         return -1;
 956 }
 957
 958 int
 959 stringrsearch(STRING *s1, STRING *s2, long start, long end, ZVALUE *index)
 960 {
 961         long len1, len2, i, j;
 962         char *c1, *c2, *c, *c2top;
 963         char ch;
 964
 965         len1 = s1->s_len;
 966         len2 = s2->s_len;
 967         if (start < 0)
 968                 start = 0;
 969         if (end > len1)
 970                 end = len1;
 971         if (end < start + len2)
 972                 return -1;
 973         if (len2 == 0) {
 974                 itoz(start, index);
 975                 return 0;
 976         }
 977         i = end - start - len2 + 1;
 978         c1 = s1->s_str + end - 1;
 979         c2top = s2->s_str + len2 - 1;
 980         ch = *c2top;
 981
 982         while (--i >= 0) {
 983                 if (*c1-- == ch) {
 984                         c = c1;
 985                         j = len2;
 986                         c2 = c2top;
 987                         while (--j > 0 && *c-- == *--c2);
 988                         if (j == 0) {
 989                                 itoz(start + i, index);
 990                                 return 0;
 991                         }
 992                 }
 993         }
 994         return -1;
 995 }
 996
 997
 998 /*
 999  * String allocation routines
1000  */
1001
1002 #define STRALLOC        100
1003
1004
1005 STATIC STRING   *freeStr = NULL;
1006 STATIC STRING   **firstStrs = NULL;
1007 STATIC long     blockcount = 0;
1008
1009
1010 STRING *
1011 stralloc(void)
1012 {
1013         STRING *temp;
1014         STRING **newfn;
1015
1016         if (freeStr == NULL) {
1017                 freeStr = (STRING *) malloc(sizeof (STRING) * STRALLOC);
1018                 if (freeStr == NULL) {
1019                         math_error("Unable to allocate memory for stralloc");
1020                         /*NOTREACHED*/
1021                 }
1022                 freeStr[STRALLOC - 1].s_next = NULL;
1023                 freeStr[STRALLOC - 1].s_links = 0;
1024
1025                 /*
1026                  * We prevent the temp pointer from walking behind freeStr
1027                  * by stopping one short of the end and running the loop one
1028                  * more time.
1029                  *
1030                  * We would stop the loop with just temp >= freeStr, but
1031                  * doing this helps make code checkers such as insure happy.
1032                  */
1033                 for (temp = freeStr + STRALLOC - 2; temp > freeStr; --temp) {
1034                         temp->s_next = temp + 1;
1035                         temp->s_links = 0;
1036                 }
1037                 /* run the loop manually one last time */
1038                 temp->s_next = temp + 1;
1039                 temp->s_links = 0;
1040
1041                 blockcount++;
1042                 if (firstStrs == NULL) {
1043                     newfn = (STRING **) malloc( blockcount * sizeof(STRING *));
1044                 } else {
1045                     newfn = (STRING **)
1046                             realloc(firstStrs, blockcount * sizeof(STRING *));
1047                 }
1048                 if (newfn == NULL) {
1049                         math_error("Cannot allocate new string block");
1050                         /*NOTREACHED*/
1051                 }
1052                 firstStrs = newfn;
1053                 firstStrs[blockcount - 1] = freeStr;
1054         }
1055         temp = freeStr;
1056         freeStr = temp->s_next;
1057         temp->s_links = 1;
1058         temp->s_str = NULL;
1059         return temp;
1060 }
1061
1062
1063 /*
1064  * makestring to be called only when str is the result of a malloc
1065  */
1066 STRING *
1067 makestring(char *str)
1068 {
1069         STRING *s;
1070         size_t len;
1071
1072         len = strlen(str);
1073         s = stralloc();
1074         s->s_str = str;
1075         s->s_len = len;
1076         return s;
1077 }
1078
1079 STRING *
1080 charstring(int ch)
1081 {
1082         STRING *s;
1083         char *c;
1084
1085         c = (char *) malloc(2);
1086         if (c == NULL) {
1087                 math_error("Allocation failure for charstring");
1088                 /*NOTREACHED*/
1089         }
1090         s = stralloc();
1091         s->s_len = 1;
1092         s->s_str = c;
1093         *c++ = (char) ch;
1094         *c = '\0';
1095         return s;
1096 }
1097
1098
1099 /*
1100  * makenewstring creates a new string by copying null-terminated str;
1101  * str is not freed
1102  */
1103 STRING *
1104 makenewstring(char *str)
1105 {
1106         STRING *s;
1107         char *c;
1108         size_t len;
1109
1110         len = strlen(str);
1111         if (len == 0)
1112                 return slink(&_nullstring_);
1113         c = (char *) malloc(len + 1);
1114         if (c == NULL) {
1115                 math_error("malloc for makenewstring failed");
1116                 /*NOTREACHED*/
1117         }
1118         s = stralloc();
1119         s->s_str = c;
1120         s->s_len = len;
1121         memcpy(c, str, len);
1122         c[len] = '\0';
1123         return s;
1124 }
1125
1126
1127 STRING *
1128 stringcopy (STRING *s1)
1129 {
1130         STRING *s;
1131         char *c;
1132         long len;
1133
1134         len = s1->s_len;
1135         if (len == 0)
1136                 return slink(s1);
1137         c = malloc(len + 1);
1138         if (c == NULL) {
1139                 math_error("Malloc failed for stringcopy");
1140                 /*NOTREACHED*/
1141         }
1142         s = stralloc();
1143         s->s_len = len;
1144         s->s_str = c;
1145         memcpy(c, s1->s_str, len);
1146         c[len] = '\0';
1147         return s;
1148 }
1149
1150
1151 STRING *
1152 slink(STRING *s)
1153 {
1154         if (s->s_links <= 0) {
1155                 math_error("Argument for slink has nonpositive links!!!");
1156                 /*NOTREACHED*/
1157         }
1158         ++s->s_links;
1159         return s;
1160 }
1161
1162
1163 void
1164 sfree(STRING *s)
1165 {
1166         if (s->s_links <= 0) {
1167                 math_error("Argument for sfree has nonpositive links!!!");
1168                 /*NOTREACHED*/
1169         }
1170         if (--s->s_links > 0 || s->s_len == 0)
1171                 return;
1172         free(s->s_str);
1173         s->s_next = freeStr;
1174         freeStr = s;
1175 }
1176
1177 STATIC long     stringconstcount = 0;
1178 STATIC long     stringconstavail = 0;
1179 STATIC STRING   **stringconsttable;
1180 #define STRCONSTALLOC 100
1181
1182 void
1183 initstrings(void)
1184 {
1185         stringconsttable = (STRING **) malloc(sizeof(STRING *) * STRCONSTALLOC);
1186         if (stringconsttable == NULL) {
1187                 math_error("Unable to allocate constant table");
1188                 /*NOTREACHED*/
1189         }
1190         stringconsttable[0] = &_nullstring_;
1191         stringconstcount = 1;
1192         stringconstavail = STRCONSTALLOC - 1;
1193 }
1194
1195 /*
1196  * addstring is called only from token.c
1197  * When called, len is length of string including '\0'
1198  */
1199 long
1200 addstring(char *str, size_t len)
1201 {
1202         STRING **sp;
1203         STRING *s;
1204         char *c;
1205         long index;             /* index into constant table */
1206         long first;             /* first non-null position found */
1207         BOOL havefirst;
1208
1209         if (len < 1) {
1210                 math_error("addstring length including trailing NUL < 1");
1211         }
1212         if (stringconstavail <= 0) {
1213                 if (stringconsttable == NULL) {
1214                         initstrings();
1215                 } else {
1216                         sp = (STRING **) realloc((char *) stringconsttable,
1217                         sizeof(STRING *) * (stringconstcount + STRCONSTALLOC));
1218                         if (sp == NULL) {
1219                                 math_error("Unable to reallocate string "
1220                                            "const table");
1221                                 /*NOTREACHED*/
1222                         }
1223                         stringconsttable = sp;
1224                         stringconstavail = STRCONSTALLOC;
1225                 }
1226         }
1227         len--;
1228         first = 0;
1229         havefirst = FALSE;
1230         sp = stringconsttable;
1231         for (index = 0; index < stringconstcount; index++, sp++) {
1232                 s = *sp;
1233                 if (s->s_links == 0) {
1234                         if (!havefirst) {
1235                                 havefirst = TRUE;
1236                                 first = index;
1237                         }
1238                         continue;
1239                 }
1240                 if (s->s_len == len && stringcompare(s->s_str, str, len) == 0) {
1241                         s->s_links++;
1242                         return index;
1243                 }
1244         }
1245         s = stralloc();
1246         c = (char *) malloc(len + 1);
1247         if (c == NULL) {
1248                 math_error("Unable to allocate string constant memory");
1249                 /*NOTREACHED*/
1250         }
1251         s->s_str = c;
1252         s->s_len = len;
1253         memcpy(s->s_str, str, len+1);
1254         if (havefirst) {
1255                 stringconsttable[first] = s;
1256                 return first;
1257         }
1258         stringconstavail--;
1259         stringconsttable[stringconstcount++] = s;
1260         return index;
1261 }
1262
1263
1264 STRING *
1265 findstring(long index)
1266 {
1267         if (index < 0 || index >= stringconstcount) {
1268                 math_error("Bad index for findstring");
1269                 /*NOTREACHED*/
1270         }
1271         return stringconsttable[index];
1272 }
1273
1274
1275 void
1276 freestringconstant(long index)
1277 {
1278         STRING *s;
1279         STRING **sp;
1280
1281         if (index >= 0) {
1282                 s = findstring(index);
1283                 sfree(s);
1284                 if (index == stringconstcount - 1) {
1285                         sp = &stringconsttable[index];
1286                         while (stringconstcount > 0 && (*sp)->s_links == 0) {
1287                                 stringconstcount--;
1288                                 stringconstavail++;
1289                                 sp--;
1290                         }
1291                 }
1292         }
1293 }
1294
1295 long
1296 printechar(char *c)
1297 {
1298         unsigned char ch, cc;
1299         unsigned char ech;      /* for escape sequence */
1300
1301         ch = *c;
1302         if (ch >= ' ' && ch < 127 && ch != '\\' && ch != '\"' && ch != '\'') {
1303                 math_chr(ch);
1304                 return 1;
1305         }
1306         math_chr('\\');
1307         ech = 0;
1308         switch (ch) {
1309         case '\n': ech = 'n'; break;
1310         case '\r': ech = 'r'; break;
1311         case '\t': ech = 't'; break;
1312         case '\b': ech = 'b'; break;
1313         case '\f': ech = 'f'; break;
1314         case '\v': ech = 'v'; break;
1315         case '\\': ech = '\\'; break;
1316         case '\"': ech = '\"'; break;
1317         case '\'': ech = '\''; break;
1318         case 0: ech = '0'; break;
1319         case 7: ech = 'a'; break;
1320         case 27: ech = 'e'; break;
1321         }
1322         if (ech == '0') {
1323                 cc = *(c + 1);
1324                 if (cc >= '0' && cc < '8') {
1325                         math_str("000");
1326                         return 4;
1327                 }
1328         }
1329         if (ech) {
1330                 math_chr(ech);
1331                 return 2;
1332         }
1333         math_chr('x');
1334         cc = ch / 16;
1335         math_chr((cc < 10) ? '0' + cc : 87 + cc);
1336         cc = ch % 16;
1337         math_chr((cc < 10) ? '0' + cc : 87 + cc);
1338         return 4;
1339 }
1340
1341
1342 void
1343 fitstring(char *str, long len, long width)
1344 {
1345         long i, j, n, max;
1346         char *c;
1347         unsigned char ch, nch;
1348
1349         max = (width - 3)/2;
1350         if (len == 0)
1351                 return;
1352         c = str;
1353         for (i = 0, n = 0; i < len && n < max; i++) {
1354                 n += printechar(c++);
1355         }
1356         if (i >= len)
1357                 return;
1358         c = str + len;
1359         nch = '\0';
1360         for (n = 0, j = len ; j > i && n < max ; --j, nch = ch) {
1361                 ch = *--c;
1362                 n++;
1363                 if (ch >= ' ' && ch <= 127 && ch != '\\' && ch != '\"')
1364                         continue;
1365                 n++;
1366                 switch (ch) {
1367                 case '\n': case '\r': case '\t': case '\b': case '\f':
1368                 case '\v': case '\\': case '\"': case 7: case 27:
1369                         continue;
1370                 }
1371                 if (ch >= 64 || (nch >= '0' && nch <= '7')) {
1372                         n += 2;
1373                         continue;
1374                 }
1375                 if (ch >= 8)
1376                         n++;
1377         }
1378         if (j > i)
1379                 math_str("...");
1380         while (j++ < len)
1381                 (void) printechar(c++);
1382 }
1383
1384 void
1385 strprint(STRING *str) {
1386         long n;
1387         char *c;
1388
1389         c = str->s_str;
1390         n = str->s_len;
1391
1392         while (n-- > 0)
1393                 (void) printechar(c++);
1394 }
1395
1396 void
1397 showstrings(void)
1398 {
1399         STRING *sp;
1400         long i, j, k;
1401         long count;
1402
1403
1404         printf("Index  Links  Length  String\n");
1405         printf("-----  -----  ------  ------\n");
1406         sp = &_nullstring_;
1407         printf("    0  %5ld        0  \"\"\n", sp->s_links);
1408         for (i = 0, k = 1, count = 1; i < blockcount; i++) {
1409                 sp = firstStrs[i];
1410                 for (j = 0; j < STRALLOC; j++, k++, sp++) {
1411                         if (sp->s_links > 0) {
1412                                 ++count;
1413                                 printf("%5ld  %5ld  %6ld  \"",
1414                                         k, sp->s_links, (long int)sp->s_len);
1415                                 fitstring(sp->s_str, sp->s_len, 50);
1416                                 printf("\"\n");
1417                         }
1418                 }
1419         }
1420         printf("\nNumber: %ld\n", count);
1421 }
1422
1423
1424 void
1425 showliterals(void)
1426 {
1427         STRING *sp;
1428         long i;
1429         long count = 0;
1430
1431
1432         printf("Index  Links  Length  String\n");
1433         printf("-----  -----  ------  ------\n");
1434         for (i = 0; i < stringconstcount; i++) {
1435                 sp = stringconsttable[i];
1436                 if (sp->s_links > 0) {
1437                         ++count;
1438                         printf("%5ld  %5ld  %6ld  \"",
1439                                 i, sp->s_links, (long int)sp->s_len);
1440                         fitstring(sp->s_str, sp->s_len, 50);
1441                         printf("\"\n");
1442                 }
1443
1444         }
1445         printf("\nNumber: %ld\n", count);
1446 }