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 /* Frees the string that SS points to. */
 362 void
 363 ss_dealloc (struct substring *ss)
 364 {
 365   free (ss->string);
 366 }
 367
 368 /* Truncates SS to at most CNT characters in length. */
 369 void
 370 ss_truncate (struct substring *ss, size_t cnt)
 371 {
 372   if (ss->length > cnt)
 373     ss->length = cnt;
 374 }
 375
 376 /* Removes trailing characters in TRIM_SET from SS.
 377    Returns number of characters removed. */
 378 size_t
 379 ss_rtrim (struct substring *ss, struct substring trim_set)
 380 {
 381   size_t cnt = 0;
 382   while (cnt < ss->length
 383          && ss_find_char (trim_set,
 384                           ss->string[ss->length - cnt - 1]) != SIZE_MAX)
 385     cnt++;
 386   ss->length -= cnt;
 387   return cnt;
 388 }
 389
 390 /* Removes leading characters in TRIM_SET from SS.
 391    Returns number of characters removed. */
 392 size_t
 393 ss_ltrim (struct substring *ss, struct substring trim_set)
 394 {
 395   size_t cnt = ss_span (*ss, trim_set);
 396   ss_advance (ss, cnt);
 397   return cnt;
 398 }
 399
 400 /* Trims leading and trailing characters in TRIM_SET from SS. */
 401 void
 402 ss_trim (struct substring *ss, struct substring trim_set)
 403 {
 404   ss_ltrim (ss, trim_set);
 405   ss_rtrim (ss, trim_set);
 406 }
 407
 408 /* If the last character in SS is C, removes it and returns true.
 409    Otherwise, returns false without changing the string. */
 410 bool
 411 ss_chomp (struct substring *ss, char c)
 412 {
 413   if (ss_last (*ss) == c)
 414     {
 415       ss->length--;
 416       return true;
 417     }
 418   else
 419     return false;
 420 }
 421
 422 /* Divides SS into tokens separated by any of the DELIMITERS.
 423    Each call replaces TOKEN by the next token in SS, or by an
 424    empty string if no tokens remain.  Returns true if a token was
 425    obtained, false otherwise.
 426
 427    Before the first call, initialize *SAVE_IDX to 0.  Do not
 428    modify *SAVE_IDX between calls.
 429
 430    SS divides into exactly one more tokens than it contains
 431    delimiters.  That is, a delimiter at the start or end of SS or
 432    a pair of adjacent delimiters yields an empty token, and the
 433    empty string contains a single token. */
 434 bool
 435 ss_separate (struct substring ss, struct substring delimiters,
 436              size_t *save_idx, struct substring *token)
 437 {
 438   if (*save_idx <= ss_length (ss))
 439     {
 440       struct substring tmp = ss_substr (ss, *save_idx, SIZE_MAX);
 441       size_t length = ss_cspan (tmp, delimiters);
 442       *token = ss_head (tmp, length);
 443       *save_idx += length + 1;
 444       return true;
 445     }
 446   else
 447     {
 448       *token = ss_empty ();
 449       return false;
 450     }
 451 }
 452
 453 /* Divides SS into tokens separated by any of the DELIMITERS,
 454    merging adjacent delimiters so that the empty string is never
 455    produced as a token.  Each call replaces TOKEN by the next
 456    token in SS, or by an empty string if no tokens remain.
 457    Returns true if a token was obtained, false otherwise.
 458
 459    Before the first call, initialize *SAVE_IDX to 0.  Do not
 460    modify *SAVE_IDX between calls. */
 461 bool
 462 ss_tokenize (struct substring ss, struct substring delimiters,
 463              size_t *save_idx, struct substring *token)
 464 {
 465   ss_advance (&ss, *save_idx);
 466   *save_idx += ss_ltrim (&ss, delimiters);
 467   *save_idx += ss_get_chars (&ss, ss_cspan (ss, delimiters), token);
 468   return ss_length (*token) > 0;
 469 }
 470
 471 /* Removes the first CNT characters from SS. */
 472 void
 473 ss_advance (struct substring *ss, size_t cnt)
 474 {
 475   if (cnt > ss->length)
 476     cnt = ss->length;
 477   ss->string += cnt;
 478   ss->length -= cnt;
 479 }
 480
 481 /* If the first character in SS is C, removes it and returns true.
 482    Otherwise, returns false without changing the string. */
 483 bool
 484 ss_match_char (struct substring *ss, char c)
 485 {
 486   if (ss_first (*ss) == c)
 487     {
 488       ss->string++;
 489       ss->length--;
 490       return true;
 491     }
 492   else
 493     return false;
 494 }
 495
 496 /* Removes the first character from SS and returns it.
 497    If SS is empty, returns EOF without modifying SS. */
 498 int
 499 ss_get_char (struct substring *ss)
 500 {
 501   int c = ss_first (*ss);
 502   if (c != EOF)
 503     {
 504       ss->string++;
 505       ss->length--;
 506     }
 507   return c;
 508 }
 509
 510 /* Stores the prefix of SS up to the first DELIMITER in OUT (if
 511    any).  Trims those same characters from SS.  DELIMITER is
 512    removed from SS but not made part of OUT.  Returns true if
 513    DELIMITER was found (and removed), false otherwise. */
 514 bool
 515 ss_get_until (struct substring *ss, char delimiter, struct substring *out)
 516 {
 517   ss_get_chars (ss, ss_cspan (*ss, ss_buffer (&delimiter, 1)), out);
 518   return ss_match_char (ss, delimiter);
 519 }
 520
 521 /* Stores the first CNT characters in SS in OUT (or fewer, if SS
 522    is shorter than CNT characters).  Trims the same characters
 523    from the beginning of SS.  Returns CNT. */
 524 size_t
 525 ss_get_chars (struct substring *ss, size_t cnt, struct substring *out)
 526 {
 527   *out = ss_head (*ss, cnt);
 528   ss_advance (ss, cnt);
 529   return cnt;
 530 }
 531
 532 /* Returns true if SS is empty (contains no characters),
 533    false otherwise. */
 534 bool
 535 ss_is_empty (struct substring ss)
 536 {
 537   return ss.length == 0;
 538 }
 539
 540 /* Returns the number of characters in SS. */
 541 size_t
 542 ss_length (struct substring ss)
 543 {
 544   return ss.length;
 545 }
 546
 547 /* Returns a pointer to the characters in SS. */
 548 char *
 549 ss_data (struct substring ss)
 550 {
 551   return ss.string;
 552 }
 553
 554 /* Returns a pointer just past the last character in SS. */
 555 char *
 556 ss_end (struct substring ss)
 557 {
 558   return ss.string + ss.length;
 559 }
 560
 561 /* Returns the character in position IDX in SS, as a value in the
 562    range of unsigned char.  Returns EOF if IDX is out of the
 563    range of indexes for SS. */
 564 int
 565 ss_at (struct substring ss, size_t idx)
 566 {
 567   return idx < ss.length ? (unsigned char) ss.string[idx] : EOF;
 568 }
 569
 570 /* Returns the first character in SS as a value in the range of
 571    unsigned char.  Returns EOF if SS is the empty string. */
 572 int
 573 ss_first (struct substring ss)
 574 {
 575   return ss_at (ss, 0);
 576 }
 577
 578 /* Returns the last character in SS as a value in the range of
 579    unsigned char.  Returns EOF if SS is the empty string. */
 580 int
 581 ss_last (struct substring ss)
 582 {
 583   return ss.length > 0 ? (unsigned char) ss.string[ss.length - 1] : EOF;
 584 }
 585
 586 /* Returns the number of contiguous characters at the beginning
 587    of SS that are in SKIP_SET. */
 588 size_t
 589 ss_span (struct substring ss, struct substring skip_set)
 590 {
 591   size_t i;
 592   for (i = 0; i < ss.length; i++)
 593     if (ss_find_char (skip_set, ss.string[i]) == SIZE_MAX)
 594       break;
 595   return i;
 596 }
 597
 598 /* Returns the number of contiguous characters at the beginning
 599    of SS that are not in SKIP_SET. */
 600 size_t
 601 ss_cspan (struct substring ss, struct substring stop_set)
 602 {
 603   size_t i;
 604   for (i = 0; i < ss.length; i++)
 605     if (ss_find_char (stop_set, ss.string[i]) != SIZE_MAX)
 606       break;
 607   return i;
 608 }
 609
 610 /* Returns the offset in SS of the first instance of C,
 611    or SIZE_MAX if C does not occur in SS. */
 612 size_t
 613 ss_find_char (struct substring ss, char c)
 614 {
 615   const char *p = memchr (ss.string, c, ss.length);
 616   return p != NULL ? p - ss.string : SIZE_MAX;
 617 }
 618
 619 /* Compares A and B and returns a strcmp()-type comparison
 620    result. */
 621 int
 622 ss_compare (struct substring a, struct substring b)
 623 {
 624   int retval = memcmp (a.string, b.string, MIN (a.length, b.length));
 625   if (retval == 0)
 626     retval = a.length < b.length ? -1 : a.length > b.length;
 627   return retval;
 628 }
 629
 630 /* Returns the position in SS that the character at P occupies.
 631    P must point within SS or one past its end. */
 632 size_t
 633 ss_pointer_to_position (struct substring ss, const char *p)
 634 {
 635   size_t pos = p - ss.string;
 636   assert (pos <= ss.length);
 637   return pos;
 638 }
 639
 640 /* Allocates and returns a null-terminated string that contains
 641    SS. */
 642 char *
 643 ss_xstrdup (struct substring ss)
 644 {
 645   char *s = xmalloc (ss.length + 1);
 646   memcpy (s, ss.string, ss.length);
 647   s[ss.length] = '\0';
 648   return s;
 649 }
 650 \f
 651 /* Initializes ST as an empty string. */
 652 void
 653 ds_init_empty (struct string *st)
 654 {
 655   st->ss = ss_empty ();
 656   st->capacity = 0;
 657 }
 658
 659 /* Initializes ST with initial contents S. */
 660 void
 661 ds_init_string (struct string *st, const struct string *s)
 662 {
 663   ds_init_substring (st, ds_ss (s));
 664 }
 665
 666 /* Initializes ST with initial contents SS. */
 667 void
 668 ds_init_substring (struct string *st, struct substring ss)
 669 {
 670   st->capacity = MAX (8, ss.length * 2);
 671   st->ss.string = xmalloc (st->capacity + 1);
 672   memcpy (st->ss.string, ss.string, ss.length);
 673   st->ss.length = ss.length;
 674 }
 675
 676 /* Initializes ST with initial contents S. */
 677 void
 678 ds_init_cstr (struct string *st, const char *s)
 679 {
 680   ds_init_substring (st, ss_cstr (s));
 681 }
 682
 683 /* Frees ST. */
 684 void
 685 ds_destroy (struct string *st)
 686 {
 687   if (st != NULL)
 688     {
 689       ss_dealloc (&st->ss);
 690       st->ss.string = NULL;
 691       st->ss.length = 0;
 692       st->capacity = 0;
 693     }
 694 }
 695
 696 /* Swaps the contents of strings A and B. */
 697 void
 698 ds_swap (struct string *a, struct string *b)
 699 {
 700   struct string tmp = *a;
 701   *a = *b;
 702   *b = tmp;
 703 }
 704
 705 /* Helper function for ds_register_pool. */
 706 static void
 707 free_string (void *st_)
 708 {
 709   struct string *st = st_;
 710   ds_destroy (st);
 711 }
 712
 713 /* Arranges for ST to be destroyed automatically as part of
 714    POOL. */
 715 void
 716 ds_register_pool (struct string *st, struct pool *pool)
 717 {
 718   pool_register (pool, free_string, st);
 719 }
 720
 721 /* Cancels the arrangement for ST to be destroyed automatically
 722    as part of POOL. */
 723 void
 724 ds_unregister_pool (struct string *st, struct pool *pool)
 725 {
 726   pool_unregister (pool, st);
 727 }
 728
 729 /* Copies SRC into DST.
 730    DST and SRC may be the same string. */
 731 void
 732 ds_assign_string (struct string *dst, const struct string *src)
 733 {
 734   ds_assign_substring (dst, ds_ss (src));
 735 }
 736
 737 /* Replaces DST by SS.
 738    SS may be a substring of DST. */
 739 void
 740 ds_assign_substring (struct string *dst, struct substring ss)
 741 {
 742   dst->ss.length = ss.length;
 743   ds_extend (dst, ss.length);
 744   memmove (dst->ss.string, ss.string, ss.length);
 745 }
 746
 747 /* Replaces DST by null-terminated string SRC.  SRC may overlap
 748    with DST. */
 749 void
 750 ds_assign_cstr (struct string *dst, const char *src)
 751 {
 752   ds_assign_substring (dst, ss_cstr (src));
 753 }
 754
 755 /* Truncates ST to zero length. */
 756 void
 757 ds_clear (struct string *st)
 758 {
 759   st->ss.length = 0;
 760 }
 761
 762 /* Returns a substring that contains ST. */
 763 struct substring
 764 ds_ss (const struct string *st)
 765 {
 766   return st->ss;
 767 }
 768
 769 /* Returns a substring that contains CNT characters from ST
 770    starting at position START.
 771
 772    If START is greater than or equal to the length of ST, then
 773    the substring will be the empty string.  If START + CNT
 774    exceeds the length of ST, then the substring will only be
 775    ds_length(ST) - START characters long. */
 776 struct substring
 777 ds_substr (const struct string *st, size_t start, size_t cnt)
 778 {
 779   return ss_substr (ds_ss (st), start, cnt);
 780 }
 781
 782 /* Returns a substring that contains the first CNT characters in
 783    ST.  If CNT exceeds the length of ST, then the substring will
 784    contain all of ST. */
 785 struct substring
 786 ds_head (const struct string *st, size_t cnt)
 787 {
 788   return ss_head (ds_ss (st), cnt);
 789 }
 790
 791 /* Returns a substring that contains the last CNT characters in
 792    ST.  If CNT exceeds the length of ST, then the substring will
 793    contain all of ST. */
 794 struct substring
 795 ds_tail (const struct string *st, size_t cnt)
 796 {
 797   return ss_tail (ds_ss (st), cnt);
 798 }
 799
 800 /* Ensures that ST can hold at least MIN_CAPACITY characters plus a null
 801    terminator. */
 802 void
 803 ds_extend (struct string *st, size_t min_capacity)
 804 {
 805   if (min_capacity > st->capacity)
 806     {
 807       st->capacity *= 2;
 808       if (st->capacity < min_capacity)
 809         st->capacity = 2 * min_capacity;
 810
 811       st->ss.string = xrealloc (st->ss.string, st->capacity + 1);
 812     }
 813 }
 814
 815 /* Shrink ST to the minimum capacity need to contain its content. */
 816 void
 817 ds_shrink (struct string *st)
 818 {
 819   if (st->capacity != st->ss.length)
 820     {
 821       st->capacity = st->ss.length;
 822       st->ss.string = xrealloc (st->ss.string, st->capacity + 1);
 823     }
 824 }
 825
 826 /* Truncates ST to at most LENGTH characters long. */
 827 void
 828 ds_truncate (struct string *st, size_t length)
 829 {
 830   ss_truncate (&st->ss, length);
 831 }
 832
 833 /* Removes trailing characters in TRIM_SET from ST.
 834    Returns number of characters removed. */
 835 size_t
 836 ds_rtrim (struct string *st, struct substring trim_set)
 837 {
 838   return ss_rtrim (&st->ss, trim_set);
 839 }
 840
 841 /* Removes leading characters in TRIM_SET from ST.
 842    Returns number of characters removed. */
 843 size_t
 844 ds_ltrim (struct string *st, struct substring trim_set)
 845 {
 846   size_t cnt = ds_span (st, trim_set);
 847   if (cnt > 0)
 848     ds_assign_substring (st, ds_substr (st, cnt, SIZE_MAX));
 849   return cnt;
 850 }
 851
 852 /* Trims leading and trailing characters in TRIM_SET from ST.
 853    Returns number of charactesr removed. */
 854 size_t
 855 ds_trim (struct string *st, struct substring trim_set)
 856 {
 857   size_t cnt = ds_rtrim (st, trim_set);
 858   return cnt + ds_ltrim (st, trim_set);
 859 }
 860
 861 /* If the last character in ST is C, removes it and returns true.
 862    Otherwise, returns false without modifying ST. */
 863 bool
 864 ds_chomp (struct string *st, char c)
 865 {
 866   return ss_chomp (&st->ss, c);
 867 }
 868
 869 /* Divides ST into tokens separated by any of the DELIMITERS.
 870    Each call replaces TOKEN by the next token in ST, or by an
 871    empty string if no tokens remain.  Returns true if a token was
 872    obtained, false otherwise.
 873
 874    Before the first call, initialize *SAVE_IDX to 0.  Do not
 875    modify *SAVE_IDX between calls.
 876
 877    ST divides into exactly one more tokens than it contains
 878    delimiters.  That is, a delimiter at the start or end of ST or
 879    a pair of adjacent delimiters yields an empty token, and the
 880    empty string contains a single token. */
 881 bool
 882 ds_separate (const struct string *st, struct substring delimiters,
 883              size_t *save_idx, struct substring *token)
 884 {
 885   return ss_separate (ds_ss (st), delimiters, save_idx, token);
 886 }
 887
 888 /* Divides ST into tokens separated by any of the DELIMITERS,
 889    merging adjacent delimiters so that the empty string is never
 890    produced as a token.  Each call replaces TOKEN by the next
 891    token in ST, or by an empty string if no tokens remain.
 892    Returns true if a token was obtained, false otherwise.
 893
 894    Before the first call, initialize *SAVE_IDX to 0.  Do not
 895    modify *SAVE_IDX between calls. */
 896 bool
 897 ds_tokenize (const struct string *st, struct substring delimiters,
 898              size_t *save_idx, struct substring *token)
 899 {
 900   return ss_tokenize (ds_ss (st), delimiters, save_idx, token);
 901 }
 902
 903 /* Pad ST on the right with copies of PAD until ST is at least
 904    LENGTH characters in size.  If ST is initially LENGTH
 905    characters or longer, this is a no-op. */
 906 void
 907 ds_rpad (struct string *st, size_t length, char pad)
 908 {
 909   if (length > st->ss.length)
 910     ds_put_char_multiple (st, pad, length - st->ss.length);
 911 }
 912
 913 /* Sets the length of ST to exactly NEW_LENGTH,
 914    either by truncating characters from the end,
 915    or by padding on the right with PAD. */
 916 void
 917 ds_set_length (struct string *st, size_t new_length, char pad)
 918 {
 919   if (st->ss.length < new_length)
 920     ds_rpad (st, new_length, pad);
 921   else
 922     st->ss.length = new_length;
 923 }
 924
 925 /* Returns true if ST is empty, false otherwise. */
 926 bool
 927 ds_is_empty (const struct string *st)
 928 {
 929   return ss_is_empty (st->ss);
 930 }
 931
 932 /* Returns the length of ST. */
 933 size_t
 934 ds_length (const struct string *st)
 935 {
 936   return ss_length (ds_ss (st));
 937 }
 938
 939 /* Returns the string data inside ST. */
 940 char *
 941 ds_data (const struct string *st)
 942 {
 943   return ss_data (ds_ss (st));
 944 }
 945
 946 /* Returns a pointer to the null terminator ST.
 947    This might not be an actual null character unless ds_c_str() has
 948    been called since the last modification to ST. */
 949 char *
 950 ds_end (const struct string *st)
 951 {
 952   return ss_end (ds_ss (st));
 953 }
 954
 955 /* Returns the character in position IDX in ST, as a value in the
 956    range of unsigned char.  Returns EOF if IDX is out of the
 957    range of indexes for ST. */
 958 int
 959 ds_at (const struct string *st, size_t idx)
 960 {
 961   return ss_at (ds_ss (st), idx);
 962 }
 963
 964 /* Returns the first character in ST as a value in the range of
 965    unsigned char.  Returns EOF if ST is the empty string. */
 966 int
 967 ds_first (const struct string *st)
 968 {
 969   return ss_first (ds_ss (st));
 970 }
 971
 972 /* Returns the last character in ST as a value in the range of
 973    unsigned char.  Returns EOF if ST is the empty string. */
 974 int
 975 ds_last (const struct string *st)
 976 {
 977   return ss_last (ds_ss (st));
 978 }
 979
 980 /* Returns the number of consecutive characters at the beginning
 981    of ST that are in SKIP_SET. */
 982 size_t
 983 ds_span (const struct string *st, struct substring skip_set)
 984 {
 985   return ss_span (ds_ss (st), skip_set);
 986 }
 987
 988 /* Returns the number of consecutive characters at the beginning
 989    of ST that are not in STOP_SET.  */
 990 size_t
 991 ds_cspan (const struct string *st, struct substring stop_set)
 992 {
 993   return ss_cspan (ds_ss (st), stop_set);
 994 }
 995
 996 /* Returns the position of the first occurrence of character C in
 997    ST at or after position OFS, or SIZE_MAX if there is no such
 998    occurrence. */
 999 size_t
1000 ds_find_char (const struct string *st, char c)
1001 {
1002   return ss_find_char (ds_ss (st), c);
1003 }
1004
1005 /* Compares A and B and returns a strcmp()-type comparison
1006    result. */
1007 int
1008 ds_compare (const struct string *a, const struct string *b)
1009 {
1010   return ss_compare (ds_ss (a), ds_ss (b));
1011 }
1012
1013 /* Returns the position in ST that the character at P occupies.
1014    P must point within ST or one past its end. */
1015 size_t
1016 ds_pointer_to_position (const struct string *st, const char *p)
1017 {
1018   return ss_pointer_to_position (ds_ss (st), p);
1019 }
1020
1021 /* Allocates and returns a null-terminated string that contains
1022    ST. */
1023 char *
1024 ds_xstrdup (const struct string *st)
1025 {
1026   return ss_xstrdup (ds_ss (st));
1027 }
1028
1029 /* Returns the allocation size of ST. */
1030 size_t
1031 ds_capacity (const struct string *st)
1032 {
1033   return st->capacity;
1034 }
1035
1036 /* Returns the value of ST as a null-terminated string. */
1037 char *
1038 ds_cstr (const struct string *st_)
1039 {
1040   struct string *st = (struct string *) st_;
1041   if (st->ss.string == NULL)
1042     ds_extend (st, 1);
1043   st->ss.string[st->ss.length] = '\0';
1044   return st->ss.string;
1045 }
1046
1047 /* Appends to ST a newline-terminated line read from STREAM.
1048    Newline is the last character of ST on return, unless an I/O error
1049    or end of file is encountered after reading some characters.
1050    Returns true if a line is successfully read, false if no characters at
1051    all were read before an I/O error or end of file was
1052    encountered. */
1053 bool
1054 ds_read_line (struct string *st, FILE *stream)
1055 {
1056   int c;
1057
1058   c = getc (stream);
1059   if (c == EOF)
1060     return false;
1061
1062   for (;;)
1063     {
1064       ds_put_char (st, c);
1065       if (c == '\n')
1066         return true;
1067
1068       c = getc (stream);
1069       if (c == EOF)
1070         return true;
1071     }
1072 }
1073
1074 /* Removes a comment introduced by `#' from ST,
1075    ignoring occurrences inside quoted strings. */
1076 static void
1077 remove_comment (struct string *st)
1078 {
1079   char *cp;
1080   int quote = 0;
1081
1082   for (cp = ds_data (st); cp < ds_end (st); cp++)
1083     if (quote)
1084       {
1085         if (*cp == quote)
1086           quote = 0;
1087         else if (*cp == '\\')
1088           cp++;
1089       }
1090     else if (*cp == '\'' || *cp == '"')
1091       quote = *cp;
1092     else if (*cp == '#')
1093       {
1094         ds_truncate (st, cp - ds_cstr (st));
1095         break;
1096       }
1097 }
1098
1099 /* Reads a line from STREAM into ST, then preprocesses as follows:
1100
1101    - Splices lines terminated with `\'.
1102
1103    - Deletes comments introduced by `#' outside of single or double
1104      quotes.
1105
1106    - Deletes trailing white space.
1107
1108    Returns true if a line was successfully read, false on
1109    failure.  If LINE_NUMBER is non-null, then *LINE_NUMBER is
1110    incremented by the number of lines read. */
1111 bool
1112 ds_read_config_line (struct string *st, int *line_number, FILE *stream)
1113 {
1114   ds_clear (st);
1115   do
1116     {
1117       if (!ds_read_line (st, stream))
1118         return false;
1119       (*line_number)++;
1120       ds_rtrim (st, ss_cstr (CC_SPACES));
1121     }
1122   while (ds_chomp (st, '\\'));
1123
1124   remove_comment (st);
1125   return true;
1126 }
1127
1128 /* Attempts to read SIZE * CNT bytes from STREAM and append them
1129    to ST.
1130    Returns number of bytes actually read. */
1131 size_t
1132 ds_read_stream (struct string *st, size_t size, size_t cnt, FILE *stream)
1133 {
1134   if (size != 0)
1135     {
1136       size_t try_bytes = xtimes (cnt, size);
1137       if (size_in_bounds_p (xsum (ds_length (st), try_bytes)))
1138         {
1139           char *buffer = ds_put_uninit (st, try_bytes);
1140           size_t got_bytes = fread (buffer, size, cnt, stream);
1141           ds_truncate (st, ds_length (st) - (try_bytes - got_bytes));
1142           return got_bytes;
1143         }
1144     }
1145   return 0;
1146 }
1147
1148 /* Concatenates S onto ST. */
1149 void
1150 ds_put_cstr (struct string *st, const char *s)
1151 {
1152   if (s != NULL)
1153     ds_put_substring (st, ss_cstr (s));
1154 }
1155
1156 /* Concatenates SS to ST. */
1157 void
1158 ds_put_substring (struct string *st, struct substring ss)
1159 {
1160   memcpy (ds_put_uninit (st, ss_length (ss)), ss_data (ss), ss_length (ss));
1161 }
1162
1163 /* Returns ds_end(ST) and THEN increases the length by INCR. */
1164 char *
1165 ds_put_uninit (struct string *st, size_t incr)
1166 {
1167   char *end;
1168   ds_extend (st, ds_length (st) + incr);
1169   end = ds_end (st);
1170   st->ss.length += incr;
1171   return end;
1172 }
1173
1174 /* Formats FORMAT as a printf string and appends the result to ST. */
1175 void
1176 ds_put_format (struct string *st, const char *format, ...)
1177 {
1178   va_list args;
1179
1180   va_start (args, format);
1181   ds_put_vformat (st, format, args);
1182   va_end (args);
1183 }
1184
1185 /* Formats FORMAT as a printf string and appends the result to ST. */
1186 void
1187 ds_put_vformat (struct string *st, const char *format, va_list args_)
1188 {
1189   int avail, needed;
1190   va_list args;
1191
1192   va_copy (args, args_);
1193   avail = st->ss.string != NULL ? st->capacity - st->ss.length + 1 : 0;
1194   needed = vsnprintf (st->ss.string + st->ss.length, avail, format, args);
1195   va_end (args);
1196
1197   if (needed >= avail)
1198     {
1199       va_copy (args, args_);
1200       vsprintf (ds_put_uninit (st, needed), format, args);
1201       va_end (args);
1202     }
1203   else
1204     {
1205       /* Some old libc's returned -1 when the destination string
1206          was too short. */
1207       while (needed == -1)
1208         {
1209           ds_extend (st, (st->capacity + 1) * 2);
1210           avail = st->capacity - st->ss.length + 1;
1211
1212           va_copy (args, args_);
1213           needed = vsnprintf (ds_end (st), avail, format, args);
1214           va_end (args);
1215         }
1216       st->ss.length += needed;
1217     }
1218 }
1219
1220 /* Appends character CH to ST. */
1221 void
1222 ds_put_char (struct string *st, int ch)
1223 {
1224   ds_put_uninit (st, 1)[0] = ch;
1225 }
1226
1227 /* Appends CNT copies of character CH to ST. */
1228 void
1229 ds_put_char_multiple (struct string *st, int ch, size_t cnt)
1230 {
1231   memset (ds_put_uninit (st, cnt), ch, cnt);
1232 }