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