2 * Vector handling (counted lists of char *'s).
4 * A vector is a table for handling a list of strings with less overhead than
5 * linked list. The intention is for vectors, once allocated, to be reused;
6 * this saves on memory allocations once the array of char *'s reaches a
9 * This is based on the from rra-c-util util/vector.c library, but that
10 * library uses xmalloc routines to exit the program if memory allocation
11 * fails. This is a modified version of the vector library that instead
12 * returns false on failure to allocate memory, allowing the caller to do
13 * appropriate recovery.
15 * Vectors require list of strings, not arbitrary binary data, and cannot
16 * handle data elements containing nul characters.
18 * Only the portions of the vector library needed by this module is
21 * Written by Russ Allbery <eagle@eyrie.org>
23 * The Board of Trustees of the Leland Stanford Junior University
25 * SPDX-License-Identifier: MIT
29 #include <portable/system.h>
31 #include <plugin/internal.h>
35 * Allocate a new, empty vector. Returns NULL if memory allocation fails.
38 strength_vector_new(void)
40 return calloc(1, sizeof(struct vector));
45 * Resize a vector (using realloc to resize the table). Return false if
46 * memory allocation fails.
49 strength_vector_resize(struct vector *vector, size_t size)
54 /* If we're shrinking the vector, free the excess strings. */
55 if (vector->count > size) {
56 for (i = size; i < vector->count; i++)
57 free(vector->strings[i]);
61 /* If resizing to zero, free all storage. Otherwise, realloc. */
63 free(vector->strings);
64 vector->strings = NULL;
66 strings = realloc(vector->strings, size * sizeof(char *));
69 vector->strings = strings;
71 vector->allocated = size;
77 * Add a new string to the vector, resizing the vector as necessary. The
78 * vector is resized an element at a time; if a lot of resizes are expected,
79 * vector_resize should be called explicitly with a more suitable size.
80 * Return false if memory allocation fails.
83 strength_vector_add(struct vector *vector, const char *string)
85 size_t next = vector->count;
87 if (vector->count == vector->allocated)
88 if (!strength_vector_resize(vector, vector->allocated + 1))
90 vector->strings[next] = strdup(string);
91 if (vector->strings[next] == NULL)
99 * Empty a vector but keep the allocated memory for the pointer table.
102 strength_vector_clear(struct vector *vector)
106 for (i = 0; i < vector->count; i++)
107 if (vector->strings[i] != NULL)
108 free(vector->strings[i]);
114 * Free a vector completely.
117 strength_vector_free(struct vector *vector)
121 strength_vector_clear(vector);
122 free(vector->strings);
128 * Given a vector that we may be reusing, clear it out. If the first argument
129 * is NULL, allocate a new vector. Used by vector_split*. Returns NULL if
130 * memory allocation fails.
132 static struct vector *
133 strength_vector_reuse(struct vector *vector)
136 return strength_vector_new();
138 strength_vector_clear(vector);
145 * Given a string and a set of separators expressed as a string, count the
146 * number of strings that it will split into when splitting on those
150 split_multi_count(const char *string, const char *seps)
155 /* If the string is empty, the count of components is zero. */
159 /* Otherwise, walk the string looking for non-consecutive separators. */
160 for (count = 1, p = string + 1; *p != '\0'; p++)
161 if (strchr(seps, *p) != NULL && strchr(seps, p[-1]) == NULL)
165 * If the string ends in separators, we've overestimated the number of
168 if (strchr(seps, p[-1]) != NULL)
175 * Given a string, split it at any of the provided separators to form a
176 * vector, copying each string segment. If the third argument isn't NULL,
177 * reuse that vector; otherwise, allocate a new one. Any number of
178 * consecutive separators are considered a single separator. Returns NULL on
179 * memory allocation failure, after which the provided vector may only have
183 strength_vector_split_multi(const char *string, const char *seps,
184 struct vector *vector)
186 const char *p, *start;
188 bool created = false;
190 /* Set up the vector we'll use to store the results. */
193 vector = strength_vector_reuse(vector);
197 /* Count how big a vector we need and resize accordingly. */
198 count = split_multi_count(string, seps);
201 if (vector->allocated < count && !strength_vector_resize(vector, count))
204 /* Now, walk the string and build the components. */
206 for (start = string, p = string, i = 0; *p != '\0'; p++)
207 if (strchr(seps, *p) != NULL) {
209 vector->strings[i] = strndup(start, (size_t) (p - start));
210 if (vector->strings[i] == NULL)
218 /* If there is anything left in the string, we have one more component. */
220 vector->strings[i] = strndup(start, (size_t) (p - start));
221 if (vector->strings[i] == NULL)
229 strength_vector_free(vector);