src/libpspp/str.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000, 2006 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 #include <config.h>
  20
  21 #include "str.h"
  22
  23 #include <ctype.h>
  24 #include <limits.h>
  25 #include <stdlib.h>
  26
  27 #include <libpspp/alloc.h>
  28 #include <libpspp/message.h>
  29 #include <libpspp/pool.h>
  30
  31 #include "minmax.h"
  32 #include "size_max.h"
  33 #include "xsize.h"
  34 \f
  35 /* Reverses the order of NBYTES bytes at address P, thus converting
  36    between little- and big-endian byte orders.  */
  37 void
  38 buf_reverse (char *p, size_t nbytes)
  39 {
  40   char *h = p, *t = &h[nbytes - 1];
  41   char temp;
  42
  43   nbytes /= 2;
  44   while (nbytes--)
  45     {
  46       temp = *h;
  47       *h++ = *t;
  48       *t-- = temp;
  49     }
  50 }
  51
  52 /* Finds the last NEEDLE of length NEEDLE_LEN in a HAYSTACK of length
  53    HAYSTACK_LEN.  Returns a pointer to the needle found. */
  54 char *
  55 buf_find_reverse (const char *haystack, size_t haystack_len,
  56                  const char *needle, size_t needle_len)
  57 {
  58   int i;
  59   for (i = haystack_len - needle_len; i >= 0; i--)
  60     if (!memcmp (needle, &haystack[i], needle_len))
  61       return (char *) &haystack[i];
  62   return 0;
  63 }
  64
  65 /* Compares the SIZE bytes in A to those in B, disregarding case,
  66    and returns a strcmp()-type result. */
  67 int
  68 buf_compare_case (const char *a_, const char *b_, size_t size)
  69 {
  70   const unsigned char *a = (unsigned char *) a_;
  71   const unsigned char *b = (unsigned char *) b_;
  72
  73   while (size-- > 0)
  74     {
  75       unsigned char ac = toupper (*a++);
  76       unsigned char bc = toupper (*b++);
  77
  78       if (ac != bc)
  79         return ac > bc ? 1 : -1;
  80     }
  81
  82   return 0;
  83 }
  84
  85 /* Compares A of length A_LEN to B of length B_LEN.  The shorter
  86    string is considered to be padded with spaces to the length of
  87    the longer. */
  88 int
  89 buf_compare_rpad (const char *a, size_t a_len, const char *b, size_t b_len)
  90 {
  91   size_t min_len;
  92   int result;
  93
  94   min_len = a_len < b_len ? a_len : b_len;
  95   result = memcmp (a, b, min_len);
  96   if (result != 0)
  97     return result;
  98   else
  99     {
 100       size_t idx;
 101
 102       if (a_len < b_len)
 103         {
 104           for (idx = min_len; idx < b_len; idx++)
 105             if (' ' != b[idx])
 106               return ' ' > b[idx] ? 1 : -1;
 107         }
 108       else
 109         {
 110           for (idx = min_len; idx < a_len; idx++)
 111             if (a[idx] != ' ')
 112               return a[idx] > ' ' ? 1 : -1;
 113         }
 114       return 0;
 115     }
 116 }
 117
 118 /* Compares strin A to string B.  The shorter string is
 119    considered to be padded with spaces to the length of the
 120    longer. */
 121 int
 122 str_compare_rpad (const char *a, const char *b)
 123 {
 124   return buf_compare_rpad (a, strlen (a), b, strlen (b));
 125 }
 126
 127 /* Copies string SRC to buffer DST, of size DST_SIZE bytes.
 128    DST is truncated to DST_SIZE bytes or padded on the right with
 129    spaces as needed. */
 130 void
 131 buf_copy_str_rpad (char *dst, size_t dst_size, const char *src)
 132 {
 133   size_t src_len = strlen (src);
 134   if (src_len >= dst_size)
 135     memcpy (dst, src, dst_size);
 136   else
 137     {
 138       memcpy (dst, src, src_len);
 139       memset (&dst[src_len], ' ', dst_size - src_len);
 140     }
 141 }
 142
 143 /* Copies string SRC to buffer DST, of size DST_SIZE bytes.
 144    DST is truncated to DST_SIZE bytes or padded on the left with
 145    spaces as needed. */
 146 void
 147 buf_copy_str_lpad (char *dst, size_t dst_size, const char *src)
 148 {
 149   size_t src_len = strlen (src);
 150   if (src_len >= dst_size)
 151     memcpy (dst, src, dst_size);
 152   else
 153     {
 154       size_t pad_cnt = dst_size - src_len;
 155       memset (&dst[0], ' ', pad_cnt);
 156       memcpy (dst + pad_cnt, src, src_len);
 157     }
 158 }
 159
 160 /* Copies buffer SRC, of SRC_SIZE bytes, to DST, of DST_SIZE bytes.
 161    DST is truncated to DST_SIZE bytes or padded on the left with
 162    spaces as needed. */
 163 void
 164 buf_copy_lpad (char *dst, size_t dst_size,
 165                const char *src, size_t src_size)
 166 {
 167   if (src_size >= dst_size)
 168     memmove (dst, src, dst_size);
 169   else
 170     {
 171       memset (dst, ' ', dst_size - src_size);
 172       memmove (&dst[dst_size - src_size], src, src_size);
 173     }
 174 }
 175
 176 /* Copies buffer SRC, of SRC_SIZE bytes, to DST, of DST_SIZE bytes.
 177    DST is truncated to DST_SIZE bytes or padded on the right with
 178    spaces as needed. */
 179 void
 180 buf_copy_rpad (char *dst, size_t dst_size,
 181                const char *src, size_t src_size)
 182 {
 183   if (src_size >= dst_size)
 184     memmove (dst, src, dst_size);
 185   else
 186     {
 187       memmove (dst, src, src_size);
 188       memset (&dst[src_size], ' ', dst_size - src_size);
 189     }
 190 }
 191
 192 /* Copies string SRC to string DST, which is in a buffer DST_SIZE
 193    bytes long.
 194    Truncates DST to DST_SIZE - 1 characters or right-pads with
 195    spaces to DST_SIZE - 1 characters if necessary. */
 196 void
 197 str_copy_rpad (char *dst, size_t dst_size, const char *src)
 198 {
 199   size_t src_len = strlen (src);
 200   if (src_len < dst_size - 1)
 201     {
 202       memcpy (dst, src, src_len);
 203       memset (&dst[src_len], ' ', dst_size - 1 - src_len);
 204     }
 205   else
 206     memcpy (dst, src, dst_size - 1);
 207   dst[dst_size - 1] = 0;
 208 }
 209
 210 /* Copies SRC to DST, which is in a buffer DST_SIZE bytes long.
 211    Truncates DST to DST_SIZE - 1 characters, if necessary. */
 212 void
 213 str_copy_trunc (char *dst, size_t dst_size, const char *src)
 214 {
 215   size_t src_len = strlen (src);
 216   assert (dst_size > 0);
 217   if (src_len + 1 < dst_size)
 218     memcpy (dst, src, src_len + 1);
 219   else
 220     {
 221       memcpy (dst, src, dst_size - 1);
 222       dst[dst_size - 1] = '\0';
 223     }
 224 }
 225
 226 /* Copies buffer SRC, of SRC_LEN bytes,
 227    to DST, which is in a buffer DST_SIZE bytes long.
 228    Truncates DST to DST_SIZE - 1 characters, if necessary. */
 229 void
 230 str_copy_buf_trunc (char *dst, size_t dst_size,
 231                     const char *src, size_t src_size)
 232 {
 233   size_t dst_len;
 234   assert (dst_size > 0);
 235
 236   dst_len = src_size < dst_size ? src_size : dst_size - 1;
 237   memcpy (dst, src, dst_len);
 238   dst[dst_len] = '\0';
 239 }
 240
 241 /* Converts each character in S to uppercase. */
 242 void
 243 str_uppercase (char *s)
 244 {
 245   for (; *s != '\0'; s++)
 246     *s = toupper ((unsigned char) *s);
 247 }
 248
 249 /* Converts each character in S to lowercase. */
 250 void
 251 str_lowercase (char *s)
 252 {
 253   for (; *s != '\0'; s++)
 254     *s = tolower ((unsigned char) *s);
 255 }
 256
 257 /* Formats FORMAT into DST, as with sprintf(), and returns the
 258    address of the terminating null written to DST. */
 259 char *
 260 spprintf (char *dst, const char *format, ...)
 261 {
 262   va_list args;
 263   int count;
 264
 265   va_start (args, format);
 266   count = vsprintf (dst, format, args);
 267   va_end (args);
 268
 269   return dst + count;
 270 }
 271
 272 /* Sets the SIZE bytes starting at BLOCK to C,
 273    and returns the byte following BLOCK. */
 274 void *
 275 mempset (void *block, int c, size_t size)
 276 {
 277   memset (block, c, size);
 278   return (char *) block + size;
 279 }
 280 \f
 281 /* Substrings. */
 282
 283 /* Returns an empty substring. */
 284 struct substring
 285 ss_empty (void)
 286 {
 287   struct substring ss;
 288   ss.string = NULL;
 289   ss.length = 0;
 290   return ss;
 291 }
 292
 293 /* Returns a substring whose contents are the given C-style
 294    string CSTR. */
 295 struct substring
 296 ss_cstr (const char *cstr)
 297 {
 298   return ss_buffer (cstr, strlen (cstr));
 299 }
 300
 301 /* Returns a substring whose contents are the CNT characters in
 302    BUFFER. */
 303 struct substring
 304 ss_buffer (const char *buffer, size_t cnt)
 305 {
 306   struct substring ss;
 307   ss.string = (char *) buffer;
 308   ss.length = cnt;
 309   return ss;
 310 }
 311
 312 /* Returns a substring whose contents are the CNT characters
 313    starting at the (0-based) position START in SS. */
 314 struct substring
 315 ss_substr (struct substring ss, size_t start, size_t cnt)
 316 {
 317   if (start < ss.length)
 318     return ss_buffer (ss.string + start, MIN (cnt, ss.length - start));
 319   else
 320     return ss_buffer (ss.string + ss.length, 0);
 321 }
 322
 323 /* Returns a substring whose contents are the first CNT
 324    characters in SS. */
 325 struct substring
 326 ss_head (struct substring ss, size_t cnt)
 327 {
 328   return ss_buffer (ss.string, MIN (cnt, ss.length));
 329 }
 330
 331 /* Returns a substring whose contents are the last CNT characters
 332    in SS. */
 333 struct substring
 334 ss_tail (struct substring ss, size_t cnt)
 335 {
 336   if (cnt < ss.length)
 337     return ss_buffer (ss.string + (ss.length - cnt), cnt);
 338   else
 339     return ss;
 340 }
 341
 342 /* Makes a malloc()'d copy of the contents of OLD
 343    and stores it in NEW. */
 344 void
 345 ss_alloc_substring (struct substring *new, struct substring old)
 346 {
 347   new->string = xmalloc (old.length);
 348   new->length = old.length;
 349   memcpy (new->string, old.string, old.length);
 350 }
 351
 352 /* Allocates room for a CNT-character string in NEW. */
 353 void
 354 ss_alloc_uninit (struct substring *new, size_t cnt)
 355 {
 356   new->string = xmalloc (cnt);
 357   new->length = cnt;
 358 }
 359
 360 /* Makes a pool_alloc_unaligned()'d copy of the contents of OLD
 361    in POOL, and stores it in NEW. */
 362 void
 363 ss_alloc_substring_pool (struct substring *new, struct substring old,
 364                          struct pool *pool)
 365 {
 366   new->string = pool_alloc_unaligned (pool, old.length);
 367   new->length = old.length;
 368   memcpy (new->string, old.string, old.length);
 369 }
 370
 371 /* Allocates room for a CNT-character string in NEW in POOL. */
 372 void
 373 ss_alloc_uninit_pool (struct substring *new, size_t cnt, struct pool *pool)
 374 {
 375   new->string = pool_alloc_unaligned (pool, cnt);
 376   new->length = cnt;
 377 }
 378
 379 /* Frees the string that SS points to. */
 380 void
 381 ss_dealloc (struct substring *ss)
 382 {
 383   free (ss->string);
 384 }
 385
 386 /* Truncates SS to at most CNT characters in length. */
 387 void
 388 ss_truncate (struct substring *ss, size_t cnt)
 389 {
 390   if (ss->length > cnt)
 391     ss->length = cnt;
 392 }
 393
 394 /* Removes trailing characters in TRIM_SET from SS.
 395    Returns number of characters removed. */
 396 size_t
 397 ss_rtrim (struct substring *ss, struct substring trim_set)
 398 {
 399   size_t cnt = 0;
 400   while (cnt < ss->length
 401          && ss_find_char (trim_set,
 402                           ss->string[ss->length - cnt - 1]) != SIZE_MAX)
 403     cnt++;
 404   ss->length -= cnt;
 405   return cnt;
 406 }
 407
 408 /* Removes leading characters in TRIM_SET from SS.
 409    Returns number of characters removed. */
 410 size_t
 411 ss_ltrim (struct substring *ss, struct substring trim_set)
 412 {
 413   size_t cnt = ss_span (*ss, trim_set);
 414   ss_advance (ss, cnt);
 415   return cnt;
 416 }
 417
 418 /* Trims leading and trailing characters in TRIM_SET from SS. */
 419 void
 420 ss_trim (struct substring *ss, struct substring trim_set)
 421 {
 422   ss_ltrim (ss, trim_set);
 423   ss_rtrim (ss, trim_set);
 424 }
 425
 426 /* If the last character in SS is C, removes it and returns true.
 427    Otherwise, returns false without changing the string. */
 428 bool
 429 ss_chomp (struct substring *ss, char c)
 430 {
 431   if (ss_last (*ss) == c)
 432     {
 433       ss->length--;
 434       return true;
 435     }
 436   else
 437     return false;
 438 }
 439
 440 /* Divides SS into tokens separated by any of the DELIMITERS.
 441    Each call replaces TOKEN by the next token in SS, or by an
 442    empty string if no tokens remain.  Returns true if a token was
 443    obtained, false otherwise.
 444
 445    Before the first call, initialize *SAVE_IDX to 0.  Do not
 446    modify *SAVE_IDX between calls.
 447
 448    SS divides into exactly one more tokens than it contains
 449    delimiters.  That is, a delimiter at the start or end of SS or
 450    a pair of adjacent delimiters yields an empty token, and the
 451    empty string contains a single token. */
 452 bool
 453 ss_separate (struct substring ss, struct substring delimiters,
 454              size_t *save_idx, struct substring *token)
 455 {
 456   if (*save_idx <= ss_length (ss))
 457     {
 458       struct substring tmp = ss_substr (ss, *save_idx, SIZE_MAX);
 459       size_t length = ss_cspan (tmp, delimiters);
 460       *token = ss_head (tmp, length);
 461       *save_idx += length + 1;
 462       return true;
 463     }
 464   else
 465     {
 466       *token = ss_empty ();
 467       return false;
 468     }
 469 }
 470
 471 /* Divides SS into tokens separated by any of the DELIMITERS,
 472    merging adjacent delimiters so that the empty string is never
 473    produced as a token.  Each call replaces TOKEN by the next
 474    token in SS, or by an empty string if no tokens remain, and
 475    then skips past the first delimiter following the token.
 476    Returns true if a token was obtained, false otherwise.
 477
 478    Before the first call, initialize *SAVE_IDX to 0.  Do not
 479    modify *SAVE_IDX between calls. */
 480 bool
 481 ss_tokenize (struct substring ss, struct substring delimiters,
 482              size_t *save_idx, struct substring *token)
 483 {
 484   ss_advance (&ss, *save_idx);
 485   *save_idx += ss_ltrim (&ss, delimiters);
 486   ss_get_chars (&ss, ss_cspan (ss, delimiters), token);
 487   *save_idx += ss_length (*token) + 1;
 488   return ss_length (*token) > 0;
 489 }
 490
 491 /* Removes the first CNT characters from SS. */
 492 void
 493 ss_advance (struct substring *ss, size_t cnt)
 494 {
 495   if (cnt > ss->length)
 496     cnt = ss->length;
 497   ss->string += cnt;
 498   ss->length -= cnt;
 499 }
 500
 501 /* If the first character in SS is C, removes it and returns true.
 502    Otherwise, returns false without changing the string. */
 503 bool
 504 ss_match_char (struct substring *ss, char c)
 505 {
 506   if (ss_first (*ss) == c)
 507     {
 508       ss->string++;
 509       ss->length--;
 510       return true;
 511     }
 512   else
 513     return false;
 514 }
 515
 516 /* If SS begins with TARGET, removes it and returns true.
 517    Otherwise, returns false without changing SS. */
 518 bool
 519 ss_match_string (struct substring *ss, const struct substring target)
 520 {
 521   size_t length = ss_length (target);
 522   if (ss_equals (ss_head (*ss, length), target))
 523     {
 524       ss_advance (ss, length);
 525       return true;
 526     }
 527   else
 528     return false;
 529 }
 530
 531 /* Removes the first character from SS and returns it.
 532    If SS is empty, returns EOF without modifying SS. */
 533 int
 534 ss_get_char (struct substring *ss)
 535 {
 536   int c = ss_first (*ss);
 537   if (c != EOF)
 538     {
 539       ss->string++;
 540       ss->length--;
 541     }
 542   return c;
 543 }
 544
 545 /* Stores the prefix of SS up to the first DELIMITER in OUT (if
 546    any).  Trims those same characters from SS.  DELIMITER is
 547    removed from SS but not made part of OUT.  Returns true if
 548    DELIMITER was found (and removed), false otherwise. */
 549 bool
 550 ss_get_until (struct substring *ss, char delimiter, struct substring *out)
 551 {
 552   ss_get_chars (ss, ss_cspan (*ss, ss_buffer (&delimiter, 1)), out);
 553   return ss_match_char (ss, delimiter);
 554 }
 555
 556 /* Stores the first CNT characters in SS in OUT (or fewer, if SS
 557    is shorter than CNT characters).  Trims the same characters
 558    from the beginning of SS.  Returns CNT. */
 559 size_t
 560 ss_get_chars (struct substring *ss, size_t cnt, struct substring *out)
 561 {
 562   *out = ss_head (*ss, cnt);
 563   ss_advance (ss, cnt);
 564   return cnt;
 565 }
 566
 567 /* Parses and removes an optionally signed decimal integer from
 568    the beginning of SS.  Returns 0 if an error occurred,
 569    otherwise the number of characters removed from SS.  Stores
 570    the integer's value into *VALUE. */
 571 size_t
 572 ss_get_long (struct substring *ss, long *value)
 573 {
 574   char tmp[64];
 575   size_t length;
 576
 577   length = ss_span (*ss, ss_cstr ("+-"));
 578   length += ss_span (ss_substr (*ss, length, SIZE_MAX), ss_cstr (CC_DIGITS));
 579   if (length > 0 && length < sizeof tmp)
 580     {
 581       char *tail;
 582
 583       memcpy (tmp, ss_data (*ss), length);
 584       tmp[length] = '\0';
 585
 586       *value = strtol (tmp, &tail, 10);
 587       if (tail - tmp == length)
 588         {
 589           ss_advance (ss, length);
 590           return length;
 591         }
 592     }
 593   *value = 0;
 594   return 0;
 595 }
 596
 597 /* Returns true if SS is empty (contains no characters),
 598    false otherwise. */
 599 bool
 600 ss_is_empty (struct substring ss)
 601 {
 602   return ss.length == 0;
 603 }
 604
 605 /* Returns the number of characters in SS. */
 606 size_t
 607 ss_length (struct substring ss)
 608 {
 609   return ss.length;
 610 }
 611
 612 /* Returns a pointer to the characters in SS. */
 613 char *
 614 ss_data (struct substring ss)
 615 {
 616   return ss.string;
 617 }
 618
 619 /* Returns a pointer just past the last character in SS. */
 620 char *
 621 ss_end (struct substring ss)
 622 {
 623   return ss.string + ss.length;
 624 }
 625
 626 /* Returns the character in position IDX in SS, as a value in the
 627    range of unsigned char.  Returns EOF if IDX is out of the
 628    range of indexes for SS. */
 629 int
 630 ss_at (struct substring ss, size_t idx)
 631 {
 632   return idx < ss.length ? (unsigned char) ss.string[idx] : EOF;
 633 }
 634
 635 /* Returns the first character in SS as a value in the range of
 636    unsigned char.  Returns EOF if SS is the empty string. */
 637 int
 638 ss_first (struct substring ss)
 639 {
 640   return ss_at (ss, 0);
 641 }
 642
 643 /* Returns the last character in SS as a value in the range of
 644    unsigned char.  Returns EOF if SS is the empty string. */
 645 int
 646 ss_last (struct substring ss)
 647 {
 648   return ss.length > 0 ? (unsigned char) ss.string[ss.length - 1] : EOF;
 649 }
 650
 651 /* Returns the number of contiguous characters at the beginning
 652    of SS that are in SKIP_SET. */
 653 size_t
 654 ss_span (struct substring ss, struct substring skip_set)
 655 {
 656   size_t i;
 657   for (i = 0; i < ss.length; i++)
 658     if (ss_find_char (skip_set, ss.string[i]) == SIZE_MAX)
 659       break;
 660   return i;
 661 }
 662
 663 /* Returns the number of contiguous characters at the beginning
 664    of SS that are not in SKIP_SET. */
 665 size_t
 666 ss_cspan (struct substring ss, struct substring stop_set)
 667 {
 668   size_t i;
 669   for (i = 0; i < ss.length; i++)
 670     if (ss_find_char (stop_set, ss.string[i]) != SIZE_MAX)
 671       break;
 672   return i;
 673 }
 674
 675 /* Returns the offset in SS of the first instance of C,
 676    or SIZE_MAX if C does not occur in SS. */
 677 size_t
 678 ss_find_char (struct substring ss, char c)
 679 {
 680   const char *p = memchr (ss.string, c, ss.length);
 681   return p != NULL ? p - ss.string : SIZE_MAX;
 682 }
 683
 684 /* Compares A and B and returns a strcmp()-type comparison
 685    result. */
 686 int
 687 ss_compare (struct substring a, struct substring b)
 688 {
 689   int retval = memcmp (a.string, b.string, MIN (a.length, b.length));
 690   if (retval == 0)
 691     retval = a.length < b.length ? -1 : a.length > b.length;
 692   return retval;
 693 }
 694
 695 /* Compares A and B case-insensitively and returns a
 696    strcmp()-type comparison result. */
 697 int
 698 ss_compare_case (struct substring a, struct substring b)
 699 {
 700   int retval = memcasecmp (a.string, b.string, MIN (a.length, b.length));
 701   if (retval == 0)
 702     retval = a.length < b.length ? -1 : a.length > b.length;
 703   return retval;
 704 }
 705
 706 /* Compares A and B and returns true if their contents are
 707    identical, false otherwise. */
 708 int
 709 ss_equals (struct substring a, struct substring b)
 710 {
 711   return a.length == b.length && !memcmp (a.string, b.string, a.length);
 712 }
 713
 714 /* Compares A and B and returns true if their contents are
 715    identical except possibly for case differences, false
 716    otherwise. */
 717 int
 718 ss_equals_case (struct substring a, struct substring b)
 719 {
 720   return a.length == b.length && !memcasecmp (a.string, b.string, a.length);
 721 }
 722
 723 /* Returns the position in SS that the character at P occupies.
 724    P must point within SS or one past its end. */
 725 size_t
 726 ss_pointer_to_position (struct substring ss, const char *p)
 727 {
 728   size_t pos = p - ss.string;
 729   assert (pos <= ss.length);
 730   return pos;
 731 }
 732
 733 /* Allocates and returns a null-terminated string that contains
 734    SS. */
 735 char *
 736 ss_xstrdup (struct substring ss)
 737 {
 738   char *s = xmalloc (ss.length + 1);
 739   memcpy (s, ss.string, ss.length);
 740   s[ss.length] = '\0';
 741   return s;
 742 }
 743 \f
 744 /* Initializes ST as an empty string. */
 745 void
 746 ds_init_empty (struct string *st)
 747 {
 748   st->ss = ss_empty ();
 749   st->capacity = 0;
 750 }
 751
 752 /* Initializes ST with initial contents S. */
 753 void
 754 ds_init_string (struct string *st, const struct string *s)
 755 {
 756   ds_init_substring (st, ds_ss (s));
 757 }
 758
 759 /* Initializes ST with initial contents SS. */
 760 void
 761 ds_init_substring (struct string *st, struct substring ss)
 762 {
 763   st->capacity = MAX (8, ss.length * 2);
 764   st->ss.string = xmalloc (st->capacity + 1);
 765   memcpy (st->ss.string, ss.string, ss.length);
 766   st->ss.length = ss.length;
 767 }
 768
 769 /* Initializes ST with initial contents S. */
 770 void
 771 ds_init_cstr (struct string *st, const char *s)
 772 {
 773   ds_init_substring (st, ss_cstr (s));
 774 }
 775
 776 /* Frees ST. */
 777 void
 778 ds_destroy (struct string *st)
 779 {
 780   if (st != NULL)
 781     {
 782       ss_dealloc (&st->ss);
 783       st->ss.string = NULL;
 784       st->ss.length = 0;
 785       st->capacity = 0;
 786     }
 787 }
 788
 789 /* Swaps the contents of strings A and B. */
 790 void
 791 ds_swap (struct string *a, struct string *b)
 792 {
 793   struct string tmp = *a;
 794   *a = *b;
 795   *b = tmp;
 796 }
 797
 798 /* Helper function for ds_register_pool. */
 799 static void
 800 free_string (void *st_)
 801 {
 802   struct string *st = st_;
 803   ds_destroy (st);
 804 }
 805
 806 /* Arranges for ST to be destroyed automatically as part of
 807    POOL. */
 808 void
 809 ds_register_pool (struct string *st, struct pool *pool)
 810 {
 811   pool_register (pool, free_string, st);
 812 }
 813
 814 /* Cancels the arrangement for ST to be destroyed automatically
 815    as part of POOL. */
 816 void
 817 ds_unregister_pool (struct string *st, struct pool *pool)
 818 {
 819   pool_unregister (pool, st);
 820 }
 821
 822 /* Copies SRC into DST.
 823    DST and SRC may be the same string. */
 824 void
 825 ds_assign_string (struct string *dst, const struct string *src)
 826 {
 827   ds_assign_substring (dst, ds_ss (src));
 828 }
 829
 830 /* Replaces DST by SS.
 831    SS may be a substring of DST. */
 832 void
 833 ds_assign_substring (struct string *dst, struct substring ss)
 834 {
 835   dst->ss.length = ss.length;
 836   ds_extend (dst, ss.length);
 837   memmove (dst->ss.string, ss.string, ss.length);
 838 }
 839
 840 /* Replaces DST by null-terminated string SRC.  SRC may overlap
 841    with DST. */
 842 void
 843 ds_assign_cstr (struct string *dst, const char *src)
 844 {
 845   ds_assign_substring (dst, ss_cstr (src));
 846 }
 847
 848 /* Truncates ST to zero length. */
 849 void
 850 ds_clear (struct string *st)
 851 {
 852   st->ss.length = 0;
 853 }
 854
 855 /* Returns a substring that contains ST. */
 856 struct substring
 857 ds_ss (const struct string *st)
 858 {
 859   return st->ss;
 860 }
 861
 862 /* Returns a substring that contains CNT characters from ST
 863    starting at position START.
 864
 865    If START is greater than or equal to the length of ST, then
 866    the substring will be the empty string.  If START + CNT
 867    exceeds the length of ST, then the substring will only be
 868    ds_length(ST) - START characters long. */
 869 struct substring
 870 ds_substr (const struct string *st, size_t start, size_t cnt)
 871 {
 872   return ss_substr (ds_ss (st), start, cnt);
 873 }
 874
 875 /* Returns a substring that contains the first CNT characters in
 876    ST.  If CNT exceeds the length of ST, then the substring will
 877    contain all of ST. */
 878 struct substring
 879 ds_head (const struct string *st, size_t cnt)
 880 {
 881   return ss_head (ds_ss (st), cnt);
 882 }
 883
 884 /* Returns a substring that contains the last CNT characters in
 885    ST.  If CNT exceeds the length of ST, then the substring will
 886    contain all of ST. */
 887 struct substring
 888 ds_tail (const struct string *st, size_t cnt)
 889 {
 890   return ss_tail (ds_ss (st), cnt);
 891 }
 892
 893 /* Ensures that ST can hold at least MIN_CAPACITY characters plus a null
 894    terminator. */
 895 void
 896 ds_extend (struct string *st, size_t min_capacity)
 897 {
 898   if (min_capacity > st->capacity)
 899     {
 900       st->capacity *= 2;
 901       if (st->capacity < min_capacity)
 902         st->capacity = 2 * min_capacity;
 903
 904       st->ss.string = xrealloc (st->ss.string, st->capacity + 1);
 905     }
 906 }
 907
 908 /* Shrink ST to the minimum capacity need to contain its content. */
 909 void
 910 ds_shrink (struct string *st)
 911 {
 912   if (st->capacity != st->ss.length)
 913     {
 914       st->capacity = st->ss.length;
 915       st->ss.string = xrealloc (st->ss.string, st->capacity + 1);
 916     }
 917 }
 918
 919 /* Truncates ST to at most LENGTH characters long. */
 920 void
 921 ds_truncate (struct string *st, size_t length)
 922 {
 923   ss_truncate (&st->ss, length);
 924 }
 925
 926 /* Removes trailing characters in TRIM_SET from ST.
 927    Returns number of characters removed. */
 928 size_t
 929 ds_rtrim (struct string *st, struct substring trim_set)
 930 {
 931   return ss_rtrim (&st->ss, trim_set);
 932 }
 933
 934 /* Removes leading characters in TRIM_SET from ST.
 935    Returns number of characters removed. */
 936 size_t
 937 ds_ltrim (struct string *st, struct substring trim_set)
 938 {
 939   size_t cnt = ds_span (st, trim_set);
 940   if (cnt > 0)
 941     ds_assign_substring (st, ds_substr (st, cnt, SIZE_MAX));
 942   return cnt;
 943 }
 944
 945 /* Trims leading and trailing characters in TRIM_SET from ST.
 946    Returns number of charactesr removed. */
 947 size_t
 948 ds_trim (struct string *st, struct substring trim_set)
 949 {
 950   size_t cnt = ds_rtrim (st, trim_set);
 951   return cnt + ds_ltrim (st, trim_set);
 952 }
 953
 954 /* If the last character in ST is C, removes it and returns true.
 955    Otherwise, returns false without modifying ST. */
 956 bool
 957 ds_chomp (struct string *st, char c)
 958 {
 959   return ss_chomp (&st->ss, c);
 960 }
 961
 962 /* Divides ST into tokens separated by any of the DELIMITERS.
 963    Each call replaces TOKEN by the next token in ST, or by an
 964    empty string if no tokens remain.  Returns true if a token was
 965    obtained, false otherwise.
 966
 967    Before the first call, initialize *SAVE_IDX to 0.  Do not
 968    modify *SAVE_IDX between calls.
 969
 970    ST divides into exactly one more tokens than it contains
 971    delimiters.  That is, a delimiter at the start or end of ST or
 972    a pair of adjacent delimiters yields an empty token, and the
 973    empty string contains a single token. */
 974 bool
 975 ds_separate (const struct string *st, struct substring delimiters,
 976              size_t *save_idx, struct substring *token)
 977 {
 978   return ss_separate (ds_ss (st), delimiters, save_idx, token);
 979 }
 980
 981 /* Divides ST into tokens separated by any of the DELIMITERS,
 982    merging adjacent delimiters so that the empty string is never
 983    produced as a token.  Each call replaces TOKEN by the next
 984    token in ST, or by an empty string if no tokens remain.
 985    Returns true if a token was obtained, false otherwise.
 986
 987    Before the first call, initialize *SAVE_IDX to 0.  Do not
 988    modify *SAVE_IDX between calls. */
 989 bool
 990 ds_tokenize (const struct string *st, struct substring delimiters,
 991              size_t *save_idx, struct substring *token)
 992 {
 993   return ss_tokenize (ds_ss (st), delimiters, save_idx, token);
 994 }
 995
 996 /* Pad ST on the right with copies of PAD until ST is at least
 997    LENGTH characters in size.  If ST is initially LENGTH
 998    characters or longer, this is a no-op. */
 999 void
1000 ds_rpad (struct string *st, size_t length, char pad)
1001 {
1002   if (length > st->ss.length)
1003     ds_put_char_multiple (st, pad, length - st->ss.length);
1004 }
1005
1006 /* Sets the length of ST to exactly NEW_LENGTH,
1007    either by truncating characters from the end,
1008    or by padding on the right with PAD. */
1009 void
1010 ds_set_length (struct string *st, size_t new_length, char pad)
1011 {
1012   if (st->ss.length < new_length)
1013     ds_rpad (st, new_length, pad);
1014   else
1015     st->ss.length = new_length;
1016 }
1017
1018 /* Returns true if ST is empty, false otherwise. */
1019 bool
1020 ds_is_empty (const struct string *st)
1021 {
1022   return ss_is_empty (st->ss);
1023 }
1024
1025 /* Returns the length of ST. */
1026 size_t
1027 ds_length (const struct string *st)
1028 {
1029   return ss_length (ds_ss (st));
1030 }
1031
1032 /* Returns the string data inside ST. */
1033 char *
1034 ds_data (const struct string *st)
1035 {
1036   return ss_data (ds_ss (st));
1037 }
1038
1039 /* Returns a pointer to the null terminator ST.
1040    This might not be an actual null character unless ds_c_str() has
1041    been called since the last modification to ST. */
1042 char *
1043 ds_end (const struct string *st)
1044 {
1045   return ss_end (ds_ss (st));
1046 }
1047
1048 /* Returns the character in position IDX in ST, as a value in the
1049    range of unsigned char.  Returns EOF if IDX is out of the
1050    range of indexes for ST. */
1051 int
1052 ds_at (const struct string *st, size_t idx)
1053 {
1054   return ss_at (ds_ss (st), idx);
1055 }
1056
1057 /* Returns the first character in ST as a value in the range of
1058    unsigned char.  Returns EOF if ST is the empty string. */
1059 int
1060 ds_first (const struct string *st)
1061 {
1062   return ss_first (ds_ss (st));
1063 }
1064
1065 /* Returns the last character in ST as a value in the range of
1066    unsigned char.  Returns EOF if ST is the empty string. */
1067 int
1068 ds_last (const struct string *st)
1069 {
1070   return ss_last (ds_ss (st));
1071 }
1072
1073 /* Returns the number of consecutive characters at the beginning
1074    of ST that are in SKIP_SET. */
1075 size_t
1076 ds_span (const struct string *st, struct substring skip_set)
1077 {
1078   return ss_span (ds_ss (st), skip_set);
1079 }
1080
1081 /* Returns the number of consecutive characters at the beginning
1082    of ST that are not in STOP_SET.  */
1083 size_t
1084 ds_cspan (const struct string *st, struct substring stop_set)
1085 {
1086   return ss_cspan (ds_ss (st), stop_set);
1087 }
1088
1089 /* Returns the position of the first occurrence of character C in
1090    ST at or after position OFS, or SIZE_MAX if there is no such
1091    occurrence. */
1092 size_t
1093 ds_find_char (const struct string *st, char c)
1094 {
1095   return ss_find_char (ds_ss (st), c);
1096 }
1097
1098 /* Compares A and B and returns a strcmp()-type comparison
1099    result. */
1100 int
1101 ds_compare (const struct string *a, const struct string *b)
1102 {
1103   return ss_compare (ds_ss (a), ds_ss (b));
1104 }
1105
1106 /* Returns the position in ST that the character at P occupies.
1107    P must point within ST or one past its end. */
1108 size_t
1109 ds_pointer_to_position (const struct string *st, const char *p)
1110 {
1111   return ss_pointer_to_position (ds_ss (st), p);
1112 }
1113
1114 /* Allocates and returns a null-terminated string that contains
1115    ST. */
1116 char *
1117 ds_xstrdup (const struct string *st)
1118 {
1119   return ss_xstrdup (ds_ss (st));
1120 }
1121
1122 /* Returns the allocation size of ST. */
1123 size_t
1124 ds_capacity (const struct string *st)
1125 {
1126   return st->capacity;
1127 }
1128
1129 /* Returns the value of ST as a null-terminated string. */
1130 char *
1131 ds_cstr (const struct string *st_)
1132 {
1133   struct string *st = (struct string *) st_;
1134   if (st->ss.string == NULL)
1135     ds_extend (st, 1);
1136   st->ss.string[st->ss.length] = '\0';
1137   return st->ss.string;
1138 }
1139
1140 /* Appends to ST a newline-terminated line read from STREAM.
1141    Newline is the last character of ST on return, unless an I/O error
1142    or end of file is encountered after reading some characters.
1143    Returns true if a line is successfully read, false if no characters at
1144    all were read before an I/O error or end of file was
1145    encountered. */
1146 bool
1147 ds_read_line (struct string *st, FILE *stream)
1148 {
1149   int c;
1150
1151   c = getc (stream);
1152   if (c == EOF)
1153     return false;
1154
1155   for (;;)
1156     {
1157       ds_put_char (st, c);
1158       if (c == '\n')
1159         return true;
1160
1161       c = getc (stream);
1162       if (c == EOF)
1163         return true;
1164     }
1165 }
1166
1167 /* Removes a comment introduced by `#' from ST,
1168    ignoring occurrences inside quoted strings. */
1169 static void
1170 remove_comment (struct string *st)
1171 {
1172   char *cp;
1173   int quote = 0;
1174
1175   for (cp = ds_data (st); cp < ds_end (st); cp++)
1176     if (quote)
1177       {
1178         if (*cp == quote)
1179           quote = 0;
1180         else if (*cp == '\\')
1181           cp++;
1182       }
1183     else if (*cp == '\'' || *cp == '"')
1184       quote = *cp;
1185     else if (*cp == '#')
1186       {
1187         ds_truncate (st, cp - ds_cstr (st));
1188         break;
1189       }
1190 }
1191
1192 /* Reads a line from STREAM into ST, then preprocesses as follows:
1193
1194    - Splices lines terminated with `\'.
1195
1196    - Deletes comments introduced by `#' outside of single or double
1197      quotes.
1198
1199    - Deletes trailing white space.
1200
1201    Returns true if a line was successfully read, false on
1202    failure.  If LINE_NUMBER is non-null, then *LINE_NUMBER is
1203    incremented by the number of lines read. */
1204 bool
1205 ds_read_config_line (struct string *st, int *line_number, FILE *stream)
1206 {
1207   ds_clear (st);
1208   do
1209     {
1210       if (!ds_read_line (st, stream))
1211         return false;
1212       (*line_number)++;
1213       ds_rtrim (st, ss_cstr (CC_SPACES));
1214     }
1215   while (ds_chomp (st, '\\'));
1216
1217   remove_comment (st);
1218   return true;
1219 }
1220
1221 /* Attempts to read SIZE * CNT bytes from STREAM and append them
1222    to ST.
1223    Returns number of bytes actually read. */
1224 size_t
1225 ds_read_stream (struct string *st, size_t size, size_t cnt, FILE *stream)
1226 {
1227   if (size != 0)
1228     {
1229       size_t try_bytes = xtimes (cnt, size);
1230       if (size_in_bounds_p (xsum (ds_length (st), try_bytes)))
1231         {
1232           char *buffer = ds_put_uninit (st, try_bytes);
1233           size_t got_bytes = fread (buffer, size, cnt, stream);
1234           ds_truncate (st, ds_length (st) - (try_bytes - got_bytes));
1235           return got_bytes;
1236         }
1237     }
1238   return 0;
1239 }
1240
1241 /* Concatenates S onto ST. */
1242 void
1243 ds_put_cstr (struct string *st, const char *s)
1244 {
1245   if (s != NULL)
1246     ds_put_substring (st, ss_cstr (s));
1247 }
1248
1249 /* Concatenates SS to ST. */
1250 void
1251 ds_put_substring (struct string *st, struct substring ss)
1252 {
1253   memcpy (ds_put_uninit (st, ss_length (ss)), ss_data (ss), ss_length (ss));
1254 }
1255
1256 /* Returns ds_end(ST) and THEN increases the length by INCR. */
1257 char *
1258 ds_put_uninit (struct string *st, size_t incr)
1259 {
1260   char *end;
1261   ds_extend (st, ds_length (st) + incr);
1262   end = ds_end (st);
1263   st->ss.length += incr;
1264   return end;
1265 }
1266
1267 /* Formats FORMAT as a printf string and appends the result to ST. */
1268 void
1269 ds_put_format (struct string *st, const char *format, ...)
1270 {
1271   va_list args;
1272
1273   va_start (args, format);
1274   ds_put_vformat (st, format, args);
1275   va_end (args);
1276 }
1277
1278 /* Formats FORMAT as a printf string and appends the result to ST. */
1279 void
1280 ds_put_vformat (struct string *st, const char *format, va_list args_)
1281 {
1282   int avail, needed;
1283   va_list args;
1284
1285   va_copy (args, args_);
1286   avail = st->ss.string != NULL ? st->capacity - st->ss.length + 1 : 0;
1287   needed = vsnprintf (st->ss.string + st->ss.length, avail, format, args);
1288   va_end (args);
1289
1290   if (needed >= avail)
1291     {
1292       va_copy (args, args_);
1293       vsprintf (ds_put_uninit (st, needed), format, args);
1294       va_end (args);
1295     }
1296   else
1297     {
1298       /* Some old libc's returned -1 when the destination string
1299          was too short. */
1300       while (needed == -1)
1301         {
1302           ds_extend (st, (st->capacity + 1) * 2);
1303           avail = st->capacity - st->ss.length + 1;
1304
1305           va_copy (args, args_);
1306           needed = vsnprintf (ds_end (st), avail, format, args);
1307           va_end (args);
1308         }
1309       st->ss.length += needed;
1310     }
1311 }
1312
1313 /* Appends character CH to ST. */
1314 void
1315 ds_put_char (struct string *st, int ch)
1316 {
1317   ds_put_uninit (st, 1)[0] = ch;
1318 }
1319
1320 /* Appends CNT copies of character CH to ST. */
1321 void
1322 ds_put_char_multiple (struct string *st, int ch, size_t cnt)
1323 {
1324   memset (ds_put_uninit (st, cnt), ch, cnt);
1325 }