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