Extended Brace ExpansionsThe enclosed code implements an extended version of the Bash brace expansion.
The main objectives are:
* Allow plain text and sequences to be used together in a brace expression,
e.g. file.{7,14,22..30,56,80..84}
* Generalize sequences so they are not limited to integers
and single letters.
Unix utilities such as split generate files with multiple letter suffixes. It would be useful to be able to respresent these with beace expansions. Moreover, there are many other useful applications of extended sequences. Extending
sequences to arbitrary strings is not difficult. Incrementing Arbitrary StringsConsider the process of incrementing an integer. The last digit is incremented until it reaches 9. At that point it wraps around to 0 and we carry the 1: if there is only one digit in the integer, we prefix a 1; otherwise we increment the next digit to the left, following the same procedure until there are no more
carries left to perform.Letters of the alphabet have a definite sequence just as digits do. So we can increment them in much the same way: we increment the last letter until we reach "z", then we wrap around to "a" and carry the 1. The difference is that letters have no equivalent to zero, so when we perform a carry by prefixing a letter, we prefix the first letter ("a") instead of the second ("b"), whereas with digits we would skip the first digit (0) and prefix the second (1) since leading zeros
have no value.I choose to distinguish between uppercase and lowercase letters, since brace expansions are often used to generate file names and Unix distinguishes between case in file names. But uppercase letters are incremented in the same way as
lowercase letters.Characters other than letters and digits have no unique ordering. So we just don't increment them. Instead, we always carry the 1. If we need to prefix a character, we just copy the current character. So "-" would be followed by
"--", and so on.When we expand a range, the lower and upper bounds are specified. Normally, the upper bound will be a string as long as, or longer than, the lower bound. So when we need to perform a carry by prefixing a character, we determine what position it is in (how many columns from the right it is), and then look at the upper bound and see what character it has in that position. If the upper bound has a digit in that position we prefix a 1, if the upper bound has a letter in that position we prefix an "a", and if neither case is true we copy the character from the upper bound. But if the upper bound has no character in that position, we look at the leftmost character in the current value instead.
For example, suppose that we want to expand {8..b-5}. We generate "8" and "9", and then we have to carry. Since there is only one character in our current value, we have to prefix a character, which will be placed in the second column from the right. Looking at the upper bound, we see that it has a "-" in that position. This is neither a digit nor a letter, so we copy it and continue on, generating "-0", "-1", "-2", "-3", "-4", "-5", "-6", "-7", "-8", and "-9". Now we have to prefix another character, this time in the third column from the right. The upper bound has a "b" in this position, which is a letter, so we prefix an "a". We generate "a-0", "a-1", "a-2", "a-3", "a-4", "a-5", "a-6", "a-7", "a-8", and "a-9". This time, when we carry we can increment the leftmost character. So we generate "b-0", "b-1", "b-2", "b-3", "b-4", and "b-5". Now
we've hit the upper bound, so we're finished. Comparing StringsLeading zeros have no value. So when we compare two strings we start out by scanning past any leading zeros, then compare the remaining strings. That way, numeric sequences will work as expected, e.g. "00" is less than "9" even though
"00" is a longer string.If one string is longer than another it is deemed to be greater. But if the two strings are of equal length, we compare them lexically, e.g. via strcmp(),
strcoll(), or some other such.
Examples
{0.1..2.3} generates the sequence
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4
1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3
{q..af} generates the sequence
q r s t u v w x y z aa ab ac ad ae af
/usr/{ucb/{ex,edit},lib/{ex?.?*,how_ex}} still generates
the expected result:
/usr/ucb/ex /usr/ucb/edit /usr/lib/ex?.?* /usr/lib/how_ex
data.{4,7..10,22,23,35..37} generates the sequence
data.4 data.7 data.8 data.9 data.10 data.22 data.23
data.35 data.36 data.37
--- Brian
#include <ctype.h>
#include <stdlib.h>
#include "brace_expander.h"
#include "errors.h"
#include "expansion_data.h"
#include "stack.h"
#include "symbols.h"
// #define DEBUG
#ifdef DEBUG
#include <stdio.h>
#define REPORT(...) printf(__VA_ARGS__)
#else
#define REPORT(...)
#endif
/*------------------------------------------------------------------------------
Expand brace expressions within a token.
A token may contain one or more embedded brace expressions.
Each brace expression consists of zero or more components, separated by a
LIST_SEPARATOR character. Each component can be a range of values, or a
string that may include another brace expression.
Version 1.0 2014-12-16 Brian B. McGuinness
------------------------------------------------------------------------------*/
#ifdef DEBUG
/*------------------------------------------------------------------------------
list_stack_contents - Display the contents of a stack
------------------------------------------------------------------------------*/
void list_stack_contents (expansion_stack *stack) {
int i, j;
for (i = 0; i <= stack->top; i++) {
expansion_data *expansions = stack->data[i];
printf (
" Stack level %d, length = %d, current component starts at %d:\n ",
i, expansions->expansions->length, expansions->part_starts_at
);
for (j = 0; j < expansions->expansions->length; j++) {
printf (" '%s'", expansions->expansions->list[j]->text);
}
printf ("\n");
}
}
#else
#define list_stack_contents(stack)
#endif
/*------------------------------------------------------------------------------
append_string_to_tokens - Append a string to the current set of tokens, or add it
as a separate token if there are no current tokens yet.
list = The list of tokens containing the current set at the end
start_at = The index where the current set of tokens begins in the list
suffix = The string to append
We return the updated list of tokens.
------------------------------------------------------------------------------*/
static void append_string_to_tokens (string_list **list, int start_at, string *suffix) {
int length = (*list)->length;
if (length > start_at) {
for (int n = start_at; n < length; n++) {
REPORT (" -- append_string_to_tokens: append '%s' to '%s'\n", &(*list)->list[n]->text, suffix->text);
append_string (&(*list)->list[n], suffix);
}
}
else append_string_to_list (list, suffix);
}
/*------------------------------------------------------------------------------
compare_strings - Compare two strings
First, we scan past leading zeros, if any, in each string. Then we compare
the remainder of the strings. If one string is longer, it is deemed greater.
Otherwise, we do a lexical comparison.
string1 = The first string to be compared
string2 = The second string to be compared
We return an integer value that is < 0 if string1 < string2,
0 if string1 = string2, or > 0 if string1 > string2.
------------------------------------------------------------------------------*/
int compare_strings (character *string1, character *string2) {
if (string1 == NULL) return (string2 == NULL) ? 0 : -1;
else if (string2 == NULL) return 1;
// Scan past leading zeros, as they have no value
while (*string1 == '0') string1++;
while (*string2 == '0') string2++;
// Note: size_t is unsigned
size_t length1 = STRLEN (string1);
size_t length2 = STRLEN (string2);
// A longer string is deemed greater
if (length1 < length2) return -1;
if (length1 > length2) return 1;
return STRCOMP (string1, string2);
}
/*------------------------------------------------------------------------------
convert_list_to_array - Convert a string list to an array of character arrays
------------------------------------------------------------------------------*/
character **convert_list_to_array (string_list *strlist) {
character **tokens = malloc ((strlist->length + 1) * sizeof (character *));
int i;
for (i = 0; i < strlist->length; i++) {
REPORT ("Copying token %d\n", i);
tokens[i] = get_character_array (strlist->list[i]);
REPORT ("Got '%s'\n", tokens[i]);
}
tokens[strlist->length] = NULL;
return tokens;
}
/*------------------------------------------------------------------------------
expand_braces - Expand brace expressions within a token.
token = The token to be expanded
We return the list of brace expansions of the token.
A NULL pointer follows the last expansion in the list.
------------------------------------------------------------------------------*/
#define UNQUOTED ' '
character **expand_braces (character *token) {
if (token[0] == BRACE_BEGIN && token[1] == '\0') {
// Ignore isolated braces; these open blocks
character **result = malloc (2 * sizeof (character *));
result[0] = token;
result[0] = NULL;
}
else {
string *buffer = new_string ();
character previous_char = ' ';
character previous_state = UNQUOTED;
int range_break = 0;
string_list *result = new_string_list ();
expansion_stack *stack = new_stack ();
character state = UNQUOTED;
push (&stack, new_expansion_data (0));
#ifdef DEBUG
printf (" Initialized stack:\n");
list_stack_contents (stack); // DEBUG
#endif
for (character *cp = token; *cp != '\0'; cp++) {
character c = *cp;
switch (state) {
case UNQUOTED: // Looking for the next brace expression
switch (c) {
case BRACE_BEGIN:
REPORT ("UNQUOTED BRACE_BEGIN: %c\n", c);
if (range_break != 0) {
report_error ("Braces are not allowed in a range: %s", token);
continue;
}
REPORT ("push %d\n", stack->data[stack->top]->expansions->length);
push (&stack, new_expansion_data (stack->data[stack->top]->expansions->length));
if (buffer->length > 0) {
append_string_to_tokens (
&stack->data[stack->top - 1]->expansions,
stack->data[stack->top - 1]->part_starts_at, buffer
);
list_stack_contents (stack); // DEBUG
}
clear_string (buffer);
previous_char = ' ';
break;
case BRACE_END:
REPORT ("UNQUOTED BRACE_END: %c\n", c);
if (stack->top < 1) {
report_error ("Unpaired closing brace: %s", token);
continue;
}
// fall through
case LIST_SEPARATOR: // End of a component: expand it
REPORT ("UNQUOTED LIST_SEPARATOR: %c\n", c);
if (stack->top < 1) {
append_char (&buffer, c);
break;
}
if (range_break != 0) {
// This component is a range
string *start = substring (buffer, 0, range_break);
string *end = substring (buffer, range_break + 2, buffer->length);
REPORT (" range: '%s' to '%s'\n", start->text, end->text);
for (string *value = start; compare_strings (value->text, end->text) <= 0; value = increment_string (value, end)) {
REPORT (" next value = '%s'\n", value->text);
append_string_to_list (&stack->data[stack->top]->expansions, value);
}
list_stack_contents (stack); // DEBUG
delete_string (end);
delete_string (start);
range_break = 0;
}
else {
// This component is a simple string
REPORT (" simple string: '%s'\n", buffer->text);
append_string_to_tokens (
&stack->data[stack->top]->expansions,
stack->data[stack->top]->part_starts_at, buffer
);
list_stack_contents (stack); // DEBUG
}
clear_string (buffer);
stack->data[stack->top]->part_starts_at = stack->data[stack->top]->expansions->length;
if (c == BRACE_END) {
REPORT ("UNQUOTED LIST_SEPARATOR: process BRACE_END\n");
// Apply this brace level's expansions to the previous brace level
int start = stack->data[stack->top - 1]->part_starts_at;
int length = stack->data[stack->top - 1]->expansions->length;
REPORT (" # expansions = %d, start at %d, stack top = %d\n", length, start, stack->top);
if (length > start) {
REPORT (" Create new list\n");
string_list *new_list = new_string_list ();
for (int n = 0; n < start; n++) {
REPORT (" [%2d]: '%s'\n", n, stack->data[stack->top - 1]->expansions->list[n]->text);
append_string_to_list (&new_list, stack->data[stack->top - 1]->expansions->list[n]);
}
for (int n = start; n < length; n++) {
for (int m = 0; m < stack->data[stack->top]->expansions->length; m++) {
REPORT (" Create new string\n");
string *new = clone_string (stack->data[stack->top - 1]->expansions->list[n]);
append_char_array (&new, stack->data[stack->top]->expansions->list[m]->text);
REPORT (" [%2d]: '%s'\n", m, new->text);
append_string_to_list (&new_list, new);
delete_string (new);
}
}
delete_string_list (stack->data[stack->top - 1]->expansions);
stack->data[stack->top - 1]->expansions = new_list;
list_stack_contents (stack); // DEBUG
}
else {
REPORT (" Append expansions to list; # expansions = %d\n", stack->data[stack->top]->expansions->length);
for (int m = 0; m < stack->data[stack->top]->expansions->length; m++) {
REPORT (" [%2d]: '%s'\n", m, stack->data[stack->top]->expansions->list[m]);
append_string_to_list (
&stack->data[stack->top - 1]->expansions,
stack->data[stack->top]->expansions->list[m]
);
}
list_stack_contents (stack); // DEBUG
}
pop (&stack);
}
break;
case RANGE: // Unquoted, unescaped range character
REPORT ("RANGE: c = %c\n", c);
append_char (&buffer, c);
if (previous_char == c && range_break == 0) range_break = buffer->length - 2;
break;
case ESCAPE:
REPORT ("ESCAPE: c = %c\n", c);
append_char (&buffer, c);
previous_state = UNQUOTED;
state = ESCAPE;
break;
case STRONG_QUOTE:
case WEAK_QUOTE:
REPORT ("QUOTE: c = %c\n", c);
state = c;
append_char (&buffer, c);
break;
default: append_char (&buffer, c);
break;
}
break;
case ESCAPE: // The last character was an escape character
REPORT ("ESCAPE: c = %c\n", c);
append_char (&buffer, c);
state = previous_state;
break;
case STRONG_QUOTE: // No brace expansion is done inside quotes
case WEAK_QUOTE:
REPORT ("QUOTE: c = %c\n", c);
append_char (&buffer, c);
if (c == ESCAPE) {
previous_state = state;
state = ESCAPE;
}
else if (c == state) state = UNQUOTED;
break;
}
previous_char = c;
}
// end of token
REPORT ("At end of token\n");
if (stack->top > 0) {
report_error ("Unpaired opening brace: %s", token);
}
// Handle leftover text at the end of a token
if (buffer->length > 0) {
REPORT ("Processing leftover text at end of token\n");
if (stack->data[0]->expansions->length > 0) { // It's a suffix for a brace expansion
for (int i = 0; i < stack->data[0]->expansions->length; i++) {
append_string (&stack->data[0]->expansions->list[i], buffer);
append_string_to_list (&result, stack->data[0]->expansions->list[i]);
}
}
else append_string_to_list (&result, buffer); // It's a token with no brace expansions
}
// There's no leftover text to append, so just save the expansions for this token
else for (int i = 0; i < stack->data[0]->expansions->length; i++) {
REPORT ("Appending expansion %d to result: '%s'\n", i, stack->data[0]->expansions->list[i]->text);
append_string_to_list (&result, stack->data[0]->expansions->list[i]);
}
delete_stack (stack);
REPORT ("Copying %d token(s) to array\n", result->length);
character **tokens = convert_list_to_array (result);
delete_string_list (result);
return tokens;
}
}
/*------------------------------------------------------------------------------
increment_string - Increment an arbitrary character string by 1, with carry
Starting with the rightmost character, we increment the character by 1 (replace it with its
successor in the collating sequence). When we reach '9' (for a digit character) or 'z' or 'Z'
(for an alphabetic character) we wrap around (to '0', 'a', or 'A') and implement carry by
incrementing the next character to the left in the same way. The incrementing process skips
over characters that are neither digits not letters, leaving them unaltered.
When a carry results in our prefixing a new character, we check the pattern to determine
whether to prefix a digit, a letter, or something else. The upper bound of a sequence of
strings is often used as the pattern. That way, we build a character sequence that matches the
final result. Alternatively, NULL can be used if no pattern is desired. In that case we prefix
a character of the same type as the leftmost character in the current value.
string = The string to be incremented
pattern = The pattern to copy, or NULL
buffer = A buffer to place the incremented string in
buflen = The length of the buffer, in characters
We return NULL on error, otherwise we return a pointer to the incremented
string.
------------------------------------------------------------------------------*/
character SUCCESSOR[] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
49, 50, 51, 52, 53, 54, 55, 56, 57, 48, 58, 59, 60, 61, 62, 63,
64, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 65, 91, 92, 93, 94, 95,
96, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112,
113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 97, 123, 124, 125, 126, 127
};
string *increment_string (string *str, string *pattern) {
if (str == NULL) return NULL;
character *current;
character last;
for (current = &str->text[str->length - 1]; current >= str->text; current--) {
last = *current;
*current = (*current < 128) ? SUCCESSOR[*current] : *current;
if (*current > last) break;
}
if (current < str->text) {
// We need to prefix a character
character prefix = *str->text;
if (pattern != NULL) {
int position = str->text + str->length - current;
if (pattern->length >= position) {
prefix = pattern->text[pattern->length - position];
}
}
if (isdigit (prefix)) prefix = '1';
else if (islower (prefix)) prefix = 'a';
else if (isupper (prefix)) prefix = 'A';
prefix_char (&str, prefix);
}
return str;
}
/*------------------------------------------------------------------------------ Expand brace expressions within each token in a list. Each brace expression consists of zero or more components, separated by a LIST_SEPARATOR character. Each component can be a range of values or a string that may include another brace expression. Version 1.0 2014-12-16 Brian B. McGuinness ------------------------------------------------------------------------------*/ #ifndef brace_expander_h #define brace_expander_h #include "string.h" #include "string_list.h" #include "types.h" int compare_strings (char *string1, char *string2); char **expand_braces (char *token); string *increment_string (string *str, string *pattern); #endif // ! brace_expander_h
build
Description: Binary data
/*------------------------------------------------------------------------------
errors.c - Definition of an error reporting function
------------------------------------------------------------------------------*/
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include "errors.h"
void report_error (const char *format, ...) {
if (format != NULL) {
va_list args;
va_start (args, format);
vfprintf (stderr, format, args);
va_end (args);
fprintf (stderr, "\n");
}
exit (255);
}
/*------------------------------------------------------------------------------ errors.h - Declaration of an error reporting function ------------------------------------------------------------------------------*/ #ifndef errors_h #define errors_h void report_error (const char *format, ...); #endif // ! errors_h
/*------------------------------------------------------------------------------
expansion_data.c - Operations on an expansion data record
Version 1.0 2014-12-16 Brian B. McGuinness
------------------------------------------------------------------------------*/
#include <stdlib.h>
#include "expansion_data.h"
/*------------------------------------------------------------------------------
delete_expansion_data - Delete an expansion data record
------------------------------------------------------------------------------*/
void delete_expansion_data (expansion_data *record) {
if (record != NULL) {
if (record->expansions != NULL) delete_string_list (record->expansions);
free (record);
}
}
/*------------------------------------------------------------------------------
new_expansion_data - Create a new expansion data record
start = Initial index in the expansion list where the current component starts
The string must be deallocated with delete_expansion_data() when you are
finished with it.
------------------------------------------------------------------------------*/
expansion_data *new_expansion_data (int start) {
expansion_data *result = (expansion_data *) malloc (sizeof (expansion_data));
if (result != NULL) {
result->part_starts_at = start;
result->expansions = new_string_list ();
if (result->expansions == NULL) {
free (result);
result = NULL;
}
}
return result;
}
/*------------------------------------------------------------------------------
expansion_data.h - Declaration of an expansion data record
This holds tokens generated during the expansion of the list of comma-
separated items in a brace expression. For example, in the expression
"{htm{,l},txt,q..bc}" the items are "html{,l}", "txt", and "q..bc".
The field "part_starts_at" is the index into the expansion list of the first
token generated by the current list item. If this item contains a nested
brace expression, "part_starts_at" indicates where to start appending text
generated by the expansion of that expression.
Version 1.0 2014-12-16 Brian B. McGuinness
------------------------------------------------------------------------------*/
#ifndef expansion_data_h
#define expansion_data_h
#include "string_list.h"
typedef struct expansion_data {
int part_starts_at; // Index in the expansion list where the current list item starts
string_list *expansions; // Tokens generated by expansions
} expansion_data;
void delete_expansion_data (expansion_data *record);
expansion_data *new_expansion_data (int start);
#endif // ! expansion_data_h
run_test
Description: Binary data
/*------------------------------------------------------------------------------
stack.c - Operations on an expansion data stack
Create the stack with new_stack().
When you are finished with the stack, it must be deallocated with
delete_stack().
Other functions are:
is_empty() - Determine if a stack is empty
pop() - Pop an expansion data record from the stack
push() - Push an expansion data record onto the stack
------------------------------------------------------------------------------*/
#include <stdlib.h>
#include "stack.h"
#define INITIAL_CAPACITY 16
/*------------------------------------------------------------------------------
delete_stack - Deallocate an expansion data stack
stack = A pointer to the stack to be deallocated
------------------------------------------------------------------------------*/
void delete_stack (expansion_stack *stack) {
if (stack != NULL) {
for (int i = 0; i <= stack->top; i++) free (stack->data[i]);
free (stack);
}
}
/*------------------------------------------------------------------------------
is_empty - Determine if a stack is empty
------------------------------------------------------------------------------*/
int is_empty (expansion_stack *stack) {
if (stack == NULL) return 1;
return stack->top < 0;
}
/*------------------------------------------------------------------------------
new_stack - Create an expansion data stack
------------------------------------------------------------------------------*/
expansion_stack *new_stack () {
expansion_stack *result = malloc (sizeof (expansion_stack) + sizeof (expansion_data *) * INITIAL_CAPACITY);
if (result != NULL) {
result->capacity = INITIAL_CAPACITY;
result->top = -1;
}
return result;
}
/*------------------------------------------------------------------------------
pop - Pop an expansion data record from the stack
------------------------------------------------------------------------------*/
void pop (expansion_stack **stack) {
if (stack != NULL && (*stack)->top >= 0 && (*stack)->top < (*stack)->capacity) {
delete_expansion_data ((*stack)->data[(*stack)->top]);
(*stack)->data[(*stack)->top] = NULL;
(*stack)->top--;
if ((*stack)->capacity > INITIAL_CAPACITY && (*stack)->top < (*stack)->capacity >> 2) {
int newsize = (*stack)->capacity >> 1;
if (newsize < INITIAL_CAPACITY) newsize = INITIAL_CAPACITY;
expansion_stack *new = malloc (sizeof (expansion_stack) + sizeof (expansion_data *) * newsize);
if (new != NULL) {
*stack = new;
(*stack)->capacity = newsize;
}
}
}
}
/*------------------------------------------------------------------------------
push - Push an expansion data record onto the stack
------------------------------------------------------------------------------*/
int push (expansion_stack **stack, expansion_data *data) {
int i, newtop;
if ((*stack)->top + 1 >= (*stack)->capacity) {
int newsize = sizeof (expansion_stack) + sizeof (expansion_data *) * ((*stack)->capacity << 1);
expansion_stack *new = realloc (*stack, newsize);
if (new == NULL) return FALSE;
*stack = new;
(*stack)->capacity <<= 1;
}
newtop = (*stack)->top + 1;
(*stack)->data[newtop] = new_expansion_data (data->part_starts_at);
if ((*stack)->data[newtop] == NULL) return FALSE;
for (i = 0; i < data->expansions->length; i++) {
append_string_to_list (&(*stack)->data[newtop]->expansions, data->expansions->list[i]);
}
(*stack)->top = newtop;
return TRUE;
}
/*------------------------------------------------------------------------------
stack.h - Declaration of an expansion data stack
------------------------------------------------------------------------------*/
#ifndef expansion_stack_h
#define expansion_stack_h
#include "expansion_data.h"
typedef struct expansion_stack {
int capacity;
int top;
expansion_data *data[];
} expansion_stack;
void delete_stack (expansion_stack *stack);
int is_empty (expansion_stack *stack);
expansion_stack *new_stack ();
void pop (expansion_stack **stack);
int push (expansion_stack **stack, expansion_data *data);
#endif // ! expansion_stack_h
/*------------------------------------------------------------------------------
string_list.c - Utilities for managing a variable length string list type
Create the list with new_string_list().
When you are finished with the list, you must deallocate it with
delete_string_list().
Other functions are:
append_string_to_list() - Append a string to the string list
Version 1.0 2015-01-30 Brian B. McGuinness
------------------------------------------------------------------------------*/
#include <stdlib.h>
#include "string_list.h"
#define INITIAL_CAPACITY 16
/*------------------------------------------------------------------------------
append_string_to_list - Append a string to the string list
------------------------------------------------------------------------------*/
int append_string_to_list (string_list **strlist, string *str) {
if ((*strlist)->length + 1 >= (*strlist)->capacity) {
int newsize = sizeof (string_list) + sizeof (string *) * ((*strlist)->capacity << 1);
string_list *new = realloc (*strlist, newsize);
if (new == NULL) return FALSE;
*strlist = new;
(*strlist)->capacity <<= 1;
}
(*strlist)->list[(*strlist)->length++] = clone_string (str);
return TRUE;
}
/*------------------------------------------------------------------------------
delete_string_list - Delete a string list
------------------------------------------------------------------------------*/
void delete_string_list (string_list *strlist) {
if (strlist != NULL) {
for (int i = 0; i < strlist->length; i++) delete_string (strlist->list[i]);
free (strlist);
}
}
/*------------------------------------------------------------------------------
new_string_list - Create a new string list
The string list must be deallocated with delete_string_list() when you are
finished with it.
------------------------------------------------------------------------------*/
string_list *new_string_list () {
string_list *result = malloc (sizeof (string_list) + sizeof (string *) * INITIAL_CAPACITY);
if (result != NULL) {
result->capacity = INITIAL_CAPACITY;
result->length = 0;
}
return result;
}
/*------------------------------------------------------------------------------
string_list.h - Declaration of a variable length string list type
Version 1.0 2015-01-30 Brian B. McGuinness
------------------------------------------------------------------------------*/
#ifndef string_list_h
#define string_list_h
#include "strings.h"
typedef struct string_list {
int capacity;
int length;
string *list[0];
} string_list;
int append_string_to_list (string_list **strlist, string *str);
void delete_string_list (string_list *strlist);
string_list *new_string_list ();
int size (string *strlist);
#endif // ! string_list_h
/*------------------------------------------------------------------------------
strings.c - Utilities for managing a variable length string type
Create the string with new_string() or new_string_from_array().
When you are finished with the string, it must be deallocated with
delete_string().
Other functions are:
append_char() - Append a single character to a string
append_char_array() - Append a character array to a string
append_string() - Append a string to another string
clear_string() - Remove the contents of the string
clone_string() - Make a copy of a string
get_character_array() - Return the contents of the string as a character array
prefix_char() - Prefix a single character to a string
substring() - Return a new string created from a portion of an existing string
Version 1.0 2015-01-30 Brian B. McGuinness
------------------------------------------------------------------------------*/
#include <stdlib.h>
#include <string.h>
#include "strings.h"
#define INITIAL_CAPACITY 16
/*------------------------------------------------------------------------------
append_char - Append a single character to a string
str = A pointer to the string to be extended
c = The character to append
------------------------------------------------------------------------------*/
int append_char (string **str, character c) {
if (((*str)->length + 1) >= (*str)->capacity) {
int newsize = sizeof (string) + sizeof (character) * ((*str)->capacity << 1);
string *new = realloc (*str, newsize);
if (new == NULL) return FALSE;
*str = new;
(*str)->capacity <<= 1;
}
(*str)->text[(*str)->length++] = c;
(*str)->text[(*str)->length] = '\0';
return TRUE;
}
/*------------------------------------------------------------------------------
append_char_array - Append a character array to a string
str = A pointer to a pointer to the string to be extended
s = The array to append
------------------------------------------------------------------------------*/
int append_char_array (string **str, character *s) {
int length = STRLEN (s);
int required = length + (*str)->length + 1;
if ((*str)->capacity < required) {
int newsize;
for (newsize = (*str)->capacity << 1; newsize < required; newsize <<= 1);
string *new = realloc (*str, sizeof (string) + sizeof (character) * newsize);
if (new == NULL) return FALSE;
*str = new;
(*str)->capacity = newsize;
}
STRCOPY ((*str)->text + (*str)->length, s);
(*str)->length += length;
return TRUE;
}
/*------------------------------------------------------------------------------
append_string - Append a string to another string
str = A pointer to a pointer to the string to be extended
s = A pointer to the string to append
------------------------------------------------------------------------------*/
int append_string (string **str, string *s) {
return append_char_array (str, s->text);
}
/*------------------------------------------------------------------------------
clear_string - Remove the contents of the string
str = A pointer to the string to be cleared
------------------------------------------------------------------------------*/
void clear_string (string *str) {
str->length = 0;
str->text[0] = 0;
}
/*------------------------------------------------------------------------------
clone_string - Make a copy of a string
str = A pointer to a pointer to the string to be cloned
------------------------------------------------------------------------------*/
string *clone_string (string *str) {
string *result = NULL;
if (str != NULL) {
result = malloc (sizeof (string) + sizeof (character) * str->capacity);
if (result != NULL) {
result->capacity = str->capacity;
result->length = str->length;
STRCOPY (result->text, str->text);
}
}
return result;
}
/*------------------------------------------------------------------------------
delete_string - Release the memory used by a string
str = A pointer to the string to be deallocated
------------------------------------------------------------------------------*/
void delete_string (string *str) {
if (str != NULL) free (str);
}
/*------------------------------------------------------------------------------
get_character_array - Return the contents of the string as a character array
str = A pointer to the string to be cleared
------------------------------------------------------------------------------*/
character *get_character_array (string *str) {
int length;
character *text;
if (str == NULL) {
length = 0;
text = "";
}
else {
length = str->length;
text = str->text;
}
character *result = malloc (sizeof (character) * (length + 1));
STRCOPY (result, str->text);
return result;
}
/*------------------------------------------------------------------------------
new_string - Create a new string
The string must be deallocated with delete_string() when you are finished with it.
------------------------------------------------------------------------------*/
string *new_string () {
string *result = malloc (sizeof (string) + sizeof (character) * INITIAL_CAPACITY);
if (result != NULL) {
result->capacity = INITIAL_CAPACITY;
result->length = 0;
result->text[0] = 0;
}
return result;
}
/*------------------------------------------------------------------------------
new_string_from_array - Create a new string from a character array
s = The character array to be placed in a string
The string must be deallocated with delete_string() when you are finished
with it.
------------------------------------------------------------------------------*/
string *new_string_from_array (character *s) {
int textlen = STRLEN (s);
int capacity = textlen + 1;
capacity += INITIAL_CAPACITY - capacity % INITIAL_CAPACITY;
string *result = malloc (sizeof (string) + sizeof (character) * capacity);
if (result != NULL) {
result->capacity = capacity;
result->length = textlen;
STRCOPY (result->text, s);
}
return result;
}
/*------------------------------------------------------------------------------
prefix_char - Prefix a single character to a string
str = A pointer to the string to be extended
c = The character to prefix
------------------------------------------------------------------------------*/
int prefix_char (string **str, character c) {
int i;
if (((*str)->length + 1) >= (*str)->capacity) {
int newsize = sizeof (string) + sizeof (character) * ((*str)->capacity << 1);
string *new = realloc (*str, newsize);
if (new == NULL) return FALSE;
*str = new;
(*str)->capacity <<= 1;
}
for (i = (*str)->length; i >= 0; i--) (*str)->text[i + 1] = (*str)->text[i];
(*str)->text[0] = c;
(*str)->length++;
return TRUE;
}
/*------------------------------------------------------------------------------
substring - Return a new string created from a portion of an existing string
str = A pointer to the string to be deallocated
start = The index where the copy is to begin (starting at 0)
end = The index just past the end of the desired substring
------------------------------------------------------------------------------*/
string *substring (string *str, int start, int end) {
int textlen = end - start;
if (textlen < 1 || str == NULL) return new_string ();
else {
character temp[textlen + 1];
STRNCOPY (temp, str->text + start, textlen);
temp[textlen] = '\0';
return new_string_from_array (temp);
}
}
/*------------------------------------------------------------------------------
strings.h - Declaration of a variable length string type
Version 1.0 2015-01-30 Brian B. McGuinness
------------------------------------------------------------------------------*/
#ifndef strings_h
#define strings_h
#include "types.h"
typedef struct string {
int capacity; // Number of characters allocated
int length; // Number of characters currently used, omitting the '\0' at the end
character text[0]; // The character string, with '\0' at the end
} string;
int append_char (string **str, character c);
int append_char_array (string **str, character *s);
int append_string (string **str, string *s);
void clear_string (string *str);
string *clone_string (string *str);
void delete_string (string *str);
character *get_character_array (string *str);
string *new_string ();
string *new_string_from_array (character *s);
int prefix_char (string **str, character c);
int string_size (string *str);
string *substring (string *str, int start, int end);
#endif // ! strings_h
/*------------------------------------------------------------------------------
Define special symbols
Version 1.0 2014-12-16 Brian B. McGuinness
------------------------------------------------------------------------------*/
#ifndef symbols_h
#define symbols_h
#define BRACE_BEGIN '{' // Begins a brace expression
#define BRACE_END '}' // Ends a brace expression
#define ESCAPE '\\' // Quotes the following char
#define LIST_SEPARATOR ',' // Separates components of a brace expansion
#define RANGE '.' // Indicates a range of values when it appears twice in succession
#define STRONG_QUOTE '\'' // Quotes everything except the escape char
#define WEAK_QUOTE '"' // Quotes everything except escape and variable chars
#endif // ! symbols_h
#include <stdio.h>
#include "brace_expander.h"
int main (int argc, char **argv) {
for (++argv; --argc; ++argv) {
printf ("\n--------------------------------------------------------------------------------\n\n");
printf ("%s:\n", *argv);
char **expansions = expand_braces (*argv);
for (int i = 0; expansions[i] != NULL; i++) printf (" '%s'", expansions[i]);
printf ("\n");
}
}
/*------------------------------------------------------------------------------ Rename basic types and related functions so we can change them easily Version 1.0 2014-12-16 Brian B. McGuinness ------------------------------------------------------------------------------*/ #ifndef types_h #define types_h #include <string.h> #define TRUE 1 #define FALSE 0 typedef char character; #define STRCOMP strcmp #define STRCOPY strcpy #define STRLEN strlen #define STRNCOPY strncpy #endif // ! types_h
