src/libpspp/str.c

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