1 /* $Id: vector.c 6699 2004-04-07 06:47:44Z rra $
3 ** Vector handling (counted lists of char *'s).
5 ** Written by Russ Allbery <rra@stanford.edu>
6 ** This work is hereby placed in the public domain by its author.
8 ** A vector is a table for handling a list of strings with less overhead than
9 ** linked list. The intention is for vectors, once allocated, to be reused;
10 ** this saves on memory allocations once the array of char *'s reaches a
13 ** There are two types of vectors. Standard vectors copy strings when
14 ** they're inserted into the vector, whereas cvectors just accept pointers
15 ** to external strings to store. There are therefore two entry points for
16 ** every vector function, one for vectors and one for cvectors.
18 ** There's a whole bunch of code duplication here. This would be a lot
19 ** cleaner with C++ features (either inheritance or templates would
20 ** probably help). One could probably in some places just cast a cvector
21 ** to a vector and perform the same operations, but I'm leery of doing that
22 ** as I'm not sure if it's a violation of the C type aliasing rules.
29 #include "inn/vector.h"
33 ** Allocate a new, empty vector.
38 struct vector *vector;
40 vector = xmalloc(sizeof(struct vector));
42 vector->allocated = 0;
43 vector->strings = NULL;
50 struct cvector *vector;
52 vector = xmalloc(sizeof(struct cvector));
54 vector->allocated = 0;
55 vector->strings = NULL;
61 ** Resize a vector (using realloc to resize the table).
64 vector_resize(struct vector *vector, size_t size)
68 if (vector->count > size) {
69 for (i = size; i < vector->count; i++)
70 free(vector->strings[i]);
74 free(vector->strings);
75 vector->strings = NULL;
77 vector->strings = xrealloc(vector->strings, size * sizeof(char *));
79 vector->allocated = size;
83 cvector_resize(struct cvector *vector, size_t size)
85 if (vector->count > size)
88 free(vector->strings);
89 vector->strings = NULL;
92 xrealloc(vector->strings, size * sizeof(const char *));
94 vector->allocated = size;
99 ** Add a new string to the vector, resizing the vector as necessary. The
100 ** vector is resized an element at a time; if a lot of resizes are expected,
101 ** vector_resize should be called explicitly with a more suitable size.
104 vector_add(struct vector *vector, const char *string)
106 size_t next = vector->count;
108 if (vector->count == vector->allocated)
109 vector_resize(vector, vector->allocated + 1);
110 vector->strings[next] = xstrdup(string);
115 cvector_add(struct cvector *vector, const char *string)
117 size_t next = vector->count;
119 if (vector->count == vector->allocated)
120 cvector_resize(vector, vector->allocated + 1);
121 vector->strings[next] = string;
127 ** Empty a vector but keep the allocated memory for the pointer table.
130 vector_clear(struct vector *vector)
134 for (i = 0; i < vector->count; i++)
135 free(vector->strings[i]);
140 cvector_clear(struct cvector *vector)
147 ** Free a vector completely.
150 vector_free(struct vector *vector)
152 vector_clear(vector);
153 free(vector->strings);
158 cvector_free(struct cvector *vector)
160 cvector_clear(vector);
161 free(vector->strings);
167 ** Given a vector that we may be reusing, clear it out. If the first
168 ** argument is NULL, allocate a new vector. Used by vector_split*.
170 static struct vector *
171 vector_reuse(struct vector *vector)
176 vector_clear(vector);
181 static struct cvector *
182 cvector_reuse(struct cvector *vector)
185 return cvector_new();
187 cvector_clear(vector);
194 ** Given a string and a separator character, count the number of strings
195 ** that it will split into.
198 split_count(const char *string, char separator)
205 for (count = 1, p = string; *p; p++)
213 ** Given a string and a separator character, form a vector by splitting the
214 ** string at those separators. Do a first pass to size the vector, and if
215 ** the third argument isn't NULL, reuse it. Otherwise, allocate a new one.
218 vector_split(const char *string, char separator, struct vector *vector)
220 const char *p, *start;
223 vector = vector_reuse(vector);
225 count = split_count(string, separator);
226 if (vector->allocated < count)
227 vector_resize(vector, count);
229 for (start = string, p = string, i = 0; *p; p++)
230 if (*p == separator) {
231 vector->strings[i++] = xstrndup(start, p - start);
234 vector->strings[i++] = xstrndup(start, p - start);
242 ** Given a modifiable string and a separator character, form a cvector by
243 ** modifying the string in-place to add nuls at the separators and then
244 ** building a vector of pointers into the string. Do a first pass to size
245 ** the vector, and if the third argument isn't NULL, reuse it. Otherwise,
246 ** allocate a new one.
249 cvector_split(char *string, char separator, struct cvector *vector)
254 vector = cvector_reuse(vector);
256 count = split_count(string, separator);
257 if (vector->allocated < count)
258 cvector_resize(vector, count);
260 for (start = string, p = string, i = 0; *p; p++)
261 if (*p == separator) {
263 vector->strings[i++] = start;
266 vector->strings[i++] = start;
274 ** Given a string, count the number of strings that it will split into when
275 ** splitting on whitespace.
278 split_space_count(const char *string)
285 for (count = 1, p = string + 1; *p != '\0'; p++)
286 if ((*p == ' ' || *p == '\t') && !(p[-1] == ' ' || p[-1] == '\t'))
289 /* If the string ends in whitespace, we've overestimated the number of
291 if (p[-1] == ' ' || p[-1] == '\t')
298 ** Given a string, split it at whitespace to form a vector, copying each
299 ** string segment. If the fourth argument isn't NULL, reuse that vector;
300 ** otherwise, allocate a new one. Any number of consecutive whitespace
301 ** characters is considered a single separator.
304 vector_split_space(const char *string, struct vector *vector)
306 const char *p, *start;
309 vector = vector_reuse(vector);
311 count = split_space_count(string);
312 if (vector->allocated < count)
313 vector_resize(vector, count);
315 for (start = string, p = string, i = 0; *p; p++)
316 if (*p == ' ' || *p == '\t') {
318 vector->strings[i++] = xstrndup(start, p - start);
322 vector->strings[i++] = xstrndup(start, p - start);
330 ** Given a string, split it at whitespace to form a vector, destructively
331 ** modifying the string to nul-terminate each segment. If the fourth
332 ** argument isn't NULL, reuse that vector; otherwise, allocate a new one.
333 ** Any number of consecutive whitespace characters is considered a single
337 cvector_split_space(char *string, struct cvector *vector)
342 vector = cvector_reuse(vector);
344 count = split_space_count(string);
345 if (vector->allocated < count)
346 cvector_resize(vector, count);
348 for (start = string, p = string, i = 0; *p; p++)
349 if (*p == ' ' || *p == '\t') {
352 vector->strings[i++] = start;
357 vector->strings[i++] = start;
365 ** Given a vector and a separator string, allocate and build a new string
366 ** composed of all the strings in the vector separated from each other by the
367 ** seperator string. Caller is responsible for freeing.
370 vector_join(const struct vector *vector, const char *seperator)
373 size_t i, size, seplen;
375 seplen = strlen(seperator);
376 for (size = 0, i = 0; i < vector->count; i++)
377 size += strlen(vector->strings[i]);
378 size += (vector->count - 1) * seplen + 1;
380 string = xmalloc(size);
381 strlcpy(string, vector->strings[0], size);
382 for (i = 1; i < vector->count; i++) {
383 strlcat(string, seperator, size);
384 strlcat(string, vector->strings[i], size);
391 cvector_join(const struct cvector *vector, const char *seperator)
394 size_t i, size, seplen;
396 seplen = strlen(seperator);
397 for (size = 0, i = 0; i < vector->count; i++)
398 size += strlen(vector->strings[i]);
399 size += (vector->count - 1) * seplen + 1;
401 string = xmalloc(size);
402 strlcpy(string, vector->strings[0], size);
403 for (i = 1; i < vector->count; i++) {
404 strlcat(string, seperator, size);
405 strlcat(string, vector->strings[i], size);