src/libpspp/str.c

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