+/* Substrings. */
+
+/* Returns an empty substring. */
+struct substring
+ss_empty (void)
+{
+ struct substring ss;
+ ss.string = NULL;
+ ss.length = 0;
+ return ss;
+}
+
+/* Returns a substring whose contents are the given C-style
+ string CSTR. */
+struct substring
+ss_cstr (const char *cstr)
+{
+ return ss_buffer (cstr, strlen (cstr));
+}
+
+/* Returns a substring whose contents are the CNT characters in
+ BUFFER. */
+struct substring
+ss_buffer (const char *buffer, size_t cnt)
+{
+ struct substring ss;
+ ss.string = (char *) buffer;
+ ss.length = cnt;
+ return ss;
+}
+
+/* Returns a substring whose contents are the CNT characters
+ starting at the (0-based) position START in SS. */
+struct substring
+ss_substr (struct substring ss, size_t start, size_t cnt)
+{
+ if (start < ss.length)
+ return ss_buffer (ss.string + start, MIN (cnt, ss.length - start));
+ else
+ return ss_buffer (ss.string + ss.length, 0);
+}
+
+/* Returns a substring whose contents are the first CNT
+ characters in SS. */
+struct substring
+ss_head (struct substring ss, size_t cnt)
+{
+ return ss_buffer (ss.string, MIN (cnt, ss.length));
+}
+
+/* Returns a substring whose contents are the last CNT characters
+ in SS. */
+struct substring
+ss_tail (struct substring ss, size_t cnt)
+{
+ if (cnt < ss.length)
+ return ss_buffer (ss.string + (ss.length - cnt), cnt);
+ else
+ return ss;
+}
+
+/* Makes a malloc()'d copy of the contents of OLD
+ and stores it in NEW. */
+void
+ss_alloc_substring (struct substring *new, struct substring old)
+{
+ new->string = xmalloc (old.length);
+ new->length = old.length;
+ memcpy (new->string, old.string, old.length);
+}
+
+/* Allocates room for a CNT-character string in NEW. */
+void
+ss_alloc_uninit (struct substring *new, size_t cnt)
+{
+ new->string = xmalloc (cnt);
+ new->length = cnt;
+}
+
+/* Makes a pool_alloc_unaligned()'d copy of the contents of OLD
+ in POOL, and stores it in NEW. */
+void
+ss_alloc_substring_pool (struct substring *new, struct substring old,
+ struct pool *pool)
+{
+ new->string = pool_alloc_unaligned (pool, old.length);
+ new->length = old.length;
+ memcpy (new->string, old.string, old.length);
+}
+
+/* Allocates room for a CNT-character string in NEW in POOL. */
+void
+ss_alloc_uninit_pool (struct substring *new, size_t cnt, struct pool *pool)
+{
+ new->string = pool_alloc_unaligned (pool, cnt);
+ new->length = cnt;
+}
+
+/* Frees the string that SS points to. */
+void
+ss_dealloc (struct substring *ss)
+{
+ free (ss->string);
+}
+
+/* Truncates SS to at most CNT characters in length. */
+void
+ss_truncate (struct substring *ss, size_t cnt)
+{
+ if (ss->length > cnt)
+ ss->length = cnt;
+}
+
+/* Removes trailing characters in TRIM_SET from SS.
+ Returns number of characters removed. */
+size_t
+ss_rtrim (struct substring *ss, struct substring trim_set)
+{
+ size_t cnt = 0;
+ while (cnt < ss->length
+ && ss_find_char (trim_set,
+ ss->string[ss->length - cnt - 1]) != SIZE_MAX)
+ cnt++;
+ ss->length -= cnt;
+ return cnt;
+}
+
+/* Removes leading characters in TRIM_SET from SS.
+ Returns number of characters removed. */
+size_t
+ss_ltrim (struct substring *ss, struct substring trim_set)
+{
+ size_t cnt = ss_span (*ss, trim_set);
+ ss_advance (ss, cnt);
+ return cnt;
+}
+
+/* Trims leading and trailing characters in TRIM_SET from SS. */
+void
+ss_trim (struct substring *ss, struct substring trim_set)
+{
+ ss_ltrim (ss, trim_set);
+ ss_rtrim (ss, trim_set);
+}
+
+/* If the last character in SS is C, removes it and returns true.
+ Otherwise, returns false without changing the string. */
+bool
+ss_chomp (struct substring *ss, char c)
+{
+ if (ss_last (*ss) == c)
+ {
+ ss->length--;
+ return true;
+ }
+ else
+ return false;
+}
+
+/* Divides SS into tokens separated by any of the DELIMITERS.
+ Each call replaces TOKEN by the next token in SS, or by an
+ empty string if no tokens remain. Returns true if a token was
+ obtained, false otherwise.
+
+ Before the first call, initialize *SAVE_IDX to 0. Do not
+ modify *SAVE_IDX between calls.
+
+ SS divides into exactly one more tokens than it contains
+ delimiters. That is, a delimiter at the start or end of SS or
+ a pair of adjacent delimiters yields an empty token, and the
+ empty string contains a single token. */
+bool
+ss_separate (struct substring ss, struct substring delimiters,
+ size_t *save_idx, struct substring *token)
+{
+ if (*save_idx <= ss_length (ss))
+ {
+ struct substring tmp = ss_substr (ss, *save_idx, SIZE_MAX);
+ size_t length = ss_cspan (tmp, delimiters);
+ *token = ss_head (tmp, length);
+ *save_idx += length + 1;
+ return true;
+ }
+ else
+ {
+ *token = ss_empty ();
+ return false;
+ }
+}
+
+/* Divides SS into tokens separated by any of the DELIMITERS,
+ merging adjacent delimiters so that the empty string is never
+ produced as a token. Each call replaces TOKEN by the next
+ token in SS, or by an empty string if no tokens remain, and
+ then skips past the first delimiter following the token.
+ Returns true if a token was obtained, false otherwise.
+
+ Before the first call, initialize *SAVE_IDX to 0. Do not
+ modify *SAVE_IDX between calls. */
+bool
+ss_tokenize (struct substring ss, struct substring delimiters,
+ size_t *save_idx, struct substring *token)
+{
+ ss_advance (&ss, *save_idx);
+ *save_idx += ss_ltrim (&ss, delimiters);
+ ss_get_chars (&ss, ss_cspan (ss, delimiters), token);
+ *save_idx += ss_length (*token) + 1;
+ return ss_length (*token) > 0;
+}
+
+/* Removes the first CNT characters from SS. */
+void
+ss_advance (struct substring *ss, size_t cnt)
+{
+ if (cnt > ss->length)
+ cnt = ss->length;
+ ss->string += cnt;
+ ss->length -= cnt;
+}
+
+/* If the first character in SS is C, removes it and returns true.
+ Otherwise, returns false without changing the string. */
+bool
+ss_match_char (struct substring *ss, char c)
+{
+ if (ss_first (*ss) == c)
+ {
+ ss->string++;
+ ss->length--;
+ return true;
+ }
+ else
+ return false;
+}
+
+/* If the first character in SS is in MATCH, removes it and
+ returns the character that was removed.
+ Otherwise, returns EOF without changing the string. */
+int
+ss_match_char_in (struct substring *ss, struct substring match)
+{
+ int c = EOF;
+ if (ss->length > 0
+ && memchr (match.string, ss->string[0], match.length) != NULL)
+ {
+ c = ss->string[0];
+ ss->string++;
+ ss->length--;
+ }
+ return c;
+}
+
+/* If SS begins with TARGET, removes it and returns true.
+ Otherwise, returns false without changing SS. */
+bool
+ss_match_string (struct substring *ss, const struct substring target)
+{
+ size_t length = ss_length (target);
+ if (ss_equals (ss_head (*ss, length), target))
+ {
+ ss_advance (ss, length);
+ return true;
+ }
+ else
+ return false;
+}
+
+/* Removes the first character from SS and returns it.
+ If SS is empty, returns EOF without modifying SS. */
+int
+ss_get_char (struct substring *ss)
+{
+ int c = ss_first (*ss);
+ if (c != EOF)
+ {
+ ss->string++;
+ ss->length--;
+ }
+ return c;
+}
+
+/* Stores the prefix of SS up to the first DELIMITER in OUT (if
+ any). Trims those same characters from SS. DELIMITER is
+ removed from SS but not made part of OUT. Returns true if
+ DELIMITER was found (and removed), false otherwise. */
+bool
+ss_get_until (struct substring *ss, char delimiter, struct substring *out)
+{
+ ss_get_chars (ss, ss_cspan (*ss, ss_buffer (&delimiter, 1)), out);
+ return ss_match_char (ss, delimiter);
+}
+
+/* Stores the first CNT characters in SS in OUT (or fewer, if SS
+ is shorter than CNT characters). Trims the same characters
+ from the beginning of SS. Returns CNT. */
+size_t
+ss_get_chars (struct substring *ss, size_t cnt, struct substring *out)
+{
+ *out = ss_head (*ss, cnt);
+ ss_advance (ss, cnt);
+ return cnt;
+}
+
+/* Parses and removes an optionally signed decimal integer from
+ the beginning of SS. Returns 0 if an error occurred,
+ otherwise the number of characters removed from SS. Stores
+ the integer's value into *VALUE. */
+size_t
+ss_get_long (struct substring *ss, long *value)
+{
+ char tmp[64];
+ size_t length;
+
+ length = ss_span (*ss, ss_cstr ("+-"));
+ length += ss_span (ss_substr (*ss, length, SIZE_MAX), ss_cstr (CC_DIGITS));
+ if (length > 0 && length < sizeof tmp)
+ {
+ char *tail;
+
+ memcpy (tmp, ss_data (*ss), length);
+ tmp[length] = '\0';
+
+ *value = strtol (tmp, &tail, 10);
+ if (tail - tmp == length)
+ {
+ ss_advance (ss, length);
+ return length;
+ }
+ }
+ *value = 0;
+ return 0;
+}
+
+/* Returns true if SS is empty (contains no characters),
+ false otherwise. */
+bool
+ss_is_empty (struct substring ss)
+{
+ return ss.length == 0;
+}
+
+/* Returns the number of characters in SS. */
+size_t
+ss_length (struct substring ss)
+{
+ return ss.length;
+}
+
+/* Returns a pointer to the characters in SS. */
+char *
+ss_data (struct substring ss)
+{
+ return ss.string;
+}
+
+/* Returns a pointer just past the last character in SS. */
+char *
+ss_end (struct substring ss)
+{
+ return ss.string + ss.length;
+}
+
+/* Returns the character in position IDX in SS, as a value in the
+ range of unsigned char. Returns EOF if IDX is out of the
+ range of indexes for SS. */
+int
+ss_at (struct substring ss, size_t idx)
+{
+ return idx < ss.length ? (unsigned char) ss.string[idx] : EOF;
+}
+
+/* Returns the first character in SS as a value in the range of
+ unsigned char. Returns EOF if SS is the empty string. */
+int
+ss_first (struct substring ss)
+{
+ return ss_at (ss, 0);
+}
+
+/* Returns the last character in SS as a value in the range of
+ unsigned char. Returns EOF if SS is the empty string. */
+int
+ss_last (struct substring ss)
+{
+ return ss.length > 0 ? (unsigned char) ss.string[ss.length - 1] : EOF;
+}
+
+/* Returns the number of contiguous characters at the beginning
+ of SS that are in SKIP_SET. */
+size_t
+ss_span (struct substring ss, struct substring skip_set)
+{
+ size_t i;
+ for (i = 0; i < ss.length; i++)
+ if (ss_find_char (skip_set, ss.string[i]) == SIZE_MAX)
+ break;
+ return i;
+}
+
+/* Returns the number of contiguous characters at the beginning
+ of SS that are not in SKIP_SET. */
+size_t
+ss_cspan (struct substring ss, struct substring stop_set)
+{
+ size_t i;
+ for (i = 0; i < ss.length; i++)
+ if (ss_find_char (stop_set, ss.string[i]) != SIZE_MAX)
+ break;
+ return i;
+}
+
+/* Returns the offset in SS of the first instance of C,
+ or SIZE_MAX if C does not occur in SS. */
+size_t
+ss_find_char (struct substring ss, char c)
+{
+ const char *p = memchr (ss.string, c, ss.length);
+ return p != NULL ? p - ss.string : SIZE_MAX;
+}
+
+/* Compares A and B and returns a strcmp()-type comparison
+ result. */
+int
+ss_compare (struct substring a, struct substring b)
+{
+ int retval = memcmp (a.string, b.string, MIN (a.length, b.length));
+ if (retval == 0)
+ retval = a.length < b.length ? -1 : a.length > b.length;
+ return retval;
+}
+
+/* Compares A and B case-insensitively and returns a
+ strcmp()-type comparison result. */
+int
+ss_compare_case (struct substring a, struct substring b)
+{
+ int retval = memcasecmp (a.string, b.string, MIN (a.length, b.length));
+ if (retval == 0)
+ retval = a.length < b.length ? -1 : a.length > b.length;
+ return retval;
+}
+
+/* Compares A and B and returns true if their contents are
+ identical, false otherwise. */
+int
+ss_equals (struct substring a, struct substring b)
+{
+ return a.length == b.length && !memcmp (a.string, b.string, a.length);
+}
+
+/* Compares A and B and returns true if their contents are
+ identical except possibly for case differences, false
+ otherwise. */
+int
+ss_equals_case (struct substring a, struct substring b)
+{
+ return a.length == b.length && !memcasecmp (a.string, b.string, a.length);
+}
+
+/* Returns the position in SS that the character at P occupies.
+ P must point within SS or one past its end. */
+size_t
+ss_pointer_to_position (struct substring ss, const char *p)
+{
+ size_t pos = p - ss.string;
+ assert (pos <= ss.length);
+ return pos;
+}
+
+/* Allocates and returns a null-terminated string that contains
+ SS. */
+char *
+ss_xstrdup (struct substring ss)
+{
+ char *s = xmalloc (ss.length + 1);
+ memcpy (s, ss.string, ss.length);
+ s[ss.length] = '\0';
+ return s;
+}
+\f
+/* Initializes ST as an empty string. */
+void
+ds_init_empty (struct string *st)
+{
+ st->ss = ss_empty ();
+ st->capacity = 0;
+}
+