/*
* Vector handling (counted lists of char *'s).
*
* A vector is a table for handling a list of strings with less overhead than
* linked list. The intention is for vectors, once allocated, to be reused;
* this saves on memory allocations once the array of char *'s reaches a
* stable size.
*
* There are two types of vectors. Standard vectors copy strings when they're
* inserted into the vector, whereas cvectors just accept pointers to external
* strings to store. There are therefore two entry points for every vector
* function, one for vectors and one for cvectors.
*
* Vectors require list of strings, not arbitrary binary data, and cannot
* handle data elements containing nul characters.
*
* There's a whole bunch of code duplication here. This would be a lot
* cleaner with C++ features (either inheritance or templates would probably
* help). One could probably in some places just cast a cvector to a vector
* and perform the same operations, but I'm leery of doing that as I'm not
* sure if it's a violation of the C type aliasing rules.
*
* The canonical version of this file is maintained in the rra-c-util package,
* which can be found at <https://www.eyrie.org/~eagle/software/rra-c-util/>.
*
* Written by Russ Allbery <eagle@eyrie.org>
* Copyright 2001-2006, 2016, 2020 Russ Allbery <eagle@eyrie.org>
* Copyright 2005-2006, 2008-2011, 2013-2014
* The Board of Trustees of the Leland Stanford Junior University
*
* Copying and distribution of this file, with or without modification, are
* permitted in any medium without royalty provided the copyright notice and
* this notice are preserved. This file is offered as-is, without any
* warranty.
*
* SPDX-License-Identifier: FSFAP
*/
#include "config.h"
#include "portable/system.h"
#include <assert.h>
#include "inn/vector.h"
#include "inn/xmalloc.h"
/*
* Allocate a new, empty vector.
*/
struct vector *
vector_new(void)
{
struct vector *vector;
vector = xcalloc(1, sizeof(struct vector));
vector->allocated = 1;
vector->strings = xcalloc(1, sizeof(char *));
return vector;
}
struct cvector *
cvector_new(void)
{
struct cvector *vector;
vector = xcalloc(1, sizeof(struct cvector));
vector->allocated = 1;
vector->strings = xcalloc(1, sizeof(const char *));
return vector;
}
/*
* Resize a vector (using reallocarray to resize the table). Maintain a
* minimum allocated size of 1 so that the strings data element is never NULL.
* This simplifies other code.
*/
void
vector_resize(struct vector *vector, size_t size)
{
size_t i;
assert(vector != NULL);
if (vector->count > size) {
for (i = size; i < vector->count; i++)
free(vector->strings[i]);
vector->count = size;
}
if (size == 0)
size = 1;
vector->strings = xreallocarray(vector->strings, size, sizeof(char *));
vector->allocated = size;
}
void
cvector_resize(struct cvector *vector, size_t size)
{
assert(vector != NULL);
if (vector->count > size)
vector->count = size;
if (size == 0)
size = 1;
vector->strings =
xreallocarray(vector->strings, size, sizeof(const char *));
vector->allocated = size;
}
/*
* Add a new string to the vector, resizing the vector as necessary. The
* vector is resized an element at a time; if a lot of resizes are expected,
* vector_resize should be called explicitly with a more suitable size.
*/
void
vector_add(struct vector *vector, const char *string)
{
assert(vector != NULL);
if (vector->count == vector->allocated)
vector_resize(vector, vector->allocated + 1);
vector->strings[vector->count] = xstrdup(string);
vector->count++;
}
void
cvector_add(struct cvector *vector, const char *string)
{
assert(vector != NULL);
if (vector->count == vector->allocated)
cvector_resize(vector, vector->allocated + 1);
vector->strings[vector->count] = string;
vector->count++;
}
/*
* Add a new string to the vector, copying at most length characters of the
* string, resizing the vector as necessary the same as with vector_add. This
* function is only available for vectors, not cvectors, since it requires the
* duplication of the input string to be sure it's nul-terminated.
*/
void
vector_addn(struct vector *vector, const char *string, size_t length)
{
assert(vector != NULL);
if (vector->count == vector->allocated)
vector_resize(vector, vector->allocated + 1);
vector->strings[vector->count] = xstrndup(string, length);
vector->count++;
}
/*
* Empty a vector but keep the allocated memory for the pointer table.
*/
void
vector_clear(struct vector *vector)
{
size_t i;
assert(vector != NULL);
for (i = 0; i < vector->count; i++)
free(vector->strings[i]);
vector->count = 0;
}
void
cvector_clear(struct cvector *vector)
{
assert(vector != NULL);
vector->count = 0;
}
/*
* Free a vector completely.
*/
void
vector_free(struct vector *vector)
{
if (vector == NULL)
return;
vector_clear(vector);
free(vector->strings);
free(vector);
}
void
cvector_free(struct cvector *vector)
{
if (vector == NULL)
return;
cvector_clear(vector);
free(vector->strings);
free(vector);
}
/*
* Given a vector that we may be reusing, clear it out. If the argument is
* NULL, allocate a new vector. Helper function for vector_split*.
*/
static struct vector *
vector_reuse(struct vector *vector)
{
if (vector == NULL)
return vector_new();
else {
vector_clear(vector);
return vector;
}
}
static struct cvector *
cvector_reuse(struct cvector *vector)
{
if (vector == NULL)
return cvector_new();
else {
cvector_clear(vector);
return vector;
}
}
/*
* Given a string and a separator character, count the number of strings that
* it will split into.
*/
static size_t
split_count(const char *string, char separator)
{
const char *p;
size_t count;
if (*string == '\0')
return 1;
for (count = 1, p = string; *p != '\0'; p++)
if (*p == separator)
count++;
return count;
}
/*
* Given a string and a separator character, form a vector by splitting the
* string at occurrences of that separator. Consecutive occurrences of the
* character will result in empty strings added to the vector. Reuse the
* provided vector if non-NULL.
*/
struct vector *
vector_split(const char *string, char separator, struct vector *vector)
{
const char *p, *start;
size_t i, count;
/* If the vector argument isn't NULL, reuse it. */
vector = vector_reuse(vector);
/* Do a first pass to size the vector. */
count = split_count(string, separator);
if (vector->allocated < count)
vector_resize(vector, count);
/* Walk the string and create the new strings with xstrndup. */
for (start = string, p = string, i = 0; *p != '\0'; p++)
if (*p == separator) {
vector->strings[i++] = xstrndup(start, p - start);
start = p + 1;
}
vector->strings[i++] = xstrndup(start, p - start);
vector->count = i;
return vector;
}
/*
* Given a modifiable string and a separator character, form a cvector by
* modifying the string in-place to add nuls at the separators and then
* building a vector of pointers into the string. Reuse the provided vector
* if non-NULL.
*/
struct cvector *
cvector_split(char *string, char separator, struct cvector *vector)
{
char *p, *start;
size_t i, count;
/* If the vector argument isn't NULL, reuse it. */
vector = cvector_reuse(vector);
/* Do a first pass to size the vector. */
count = split_count(string, separator);
if (vector->allocated < count)
cvector_resize(vector, count);
/*
* Walk the string and replace separators with nul, and store the pointers
* to the start of each string segment.
*/
for (start = string, p = string, i = 0; *p; p++)
if (*p == separator) {
*p = '\0';
vector->strings[i++] = start;
start = p + 1;
}
vector->strings[i++] = start;
vector->count = i;
return vector;
}
/*
* Given a string and a set of separators expressed as a string, count the
* number of strings that it will split into when splitting on those
* separators. Unlike with split_count, multiple consecutive separator
* characters will be treated the same as a single separator.
*/
static size_t
split_multi_count(const char *string, const char *seps)
{
const char *p;
size_t count;
/* The empty string produces no substrings. */
if (*string == '\0')
return 0;
/*
* Walk the string looking for the first separator not preceded by
* another separator (and ignore a separator at the start of the string).
*/
for (count = 1, p = string + 1; *p != '\0'; p++)
if (strchr(seps, *p) != NULL && strchr(seps, p[-1]) == NULL)
count++;
/*
* If the string ends in separators, we've overestimated the number of
* strings by one.
*/
if (strchr(seps, p[-1]) != NULL)
count--;
return count;
}
/*
* Given a string, split it at any of the provided separators to form a
* vector, copying each string segment. Any number of consecutive separators
* are considered a single separator. Reuse the provided vector if non-NULL.
*/
struct vector *
vector_split_multi(const char *string, const char *seps, struct vector *vector)
{
const char *p, *start;
size_t i, count;
/* If the vector argument isn't NULL, reuse it. */
vector = vector_reuse(vector);
/* Count the number of strings we'll create and size the vector. */
count = split_multi_count(string, seps);
if (vector->allocated < count)
vector_resize(vector, count);
/*
* Walk the string and look for separators. start tracks the
* non-separator that starts a new string, so as long as start == p, we're
* tracking a sequence of separators.
*/
for (start = string, p = string, i = 0; *p != '\0'; p++)
if (strchr(seps, *p) != NULL) {
if (start != p)
vector->strings[i++] = xstrndup(start, p - start);
start = p + 1;
}
if (start != p)
vector->strings[i++] = xstrndup(start, p - start);
vector->count = i;
return vector;
}
/*
* Given a string, split it at any of the provided separators to form a
* vector, destructively modifying the string to nul-terminate each segment.
* Any number of consecutive separators are considered a single separator.
* Reuse the provided vector if non-NULL.
*/
struct cvector *
cvector_split_multi(char *string, const char *seps, struct cvector *vector)
{
char *p, *start;
size_t i, count;
/* If the vector argument isn't NULL, reuse it. */
vector = cvector_reuse(vector);
/* Count the number of strings we'll create and size the vector. */
count = split_multi_count(string, seps);
if (vector->allocated < count)
cvector_resize(vector, count);
/*
* Walk the string and look for separators, replacing the ones that
* terminate a substring with a nul. start tracks the non-separator that
* starts a new string, so as long as start == p, we're tracking a
* sequence of separators.
*/
for (start = string, p = string, i = 0; *p != '\0'; p++)
if (strchr(seps, *p) != NULL) {
if (start != p) {
*p = '\0';
vector->strings[i++] = start;
}
start = p + 1;
}
if (start != p)
vector->strings[i++] = start;
vector->count = i;
return vector;
}
/*
* Given a string, split it at whitespace to form a vector, copying each
* string segment. Any number of consecutive whitespace characters are
* considered a single separator. Reuse the provided vector if non-NULL.
* This is just a special case of vector_split_multi.
*/
struct vector *
vector_split_space(const char *string, struct vector *vector)
{
return vector_split_multi(string, " \t", vector);
}
/*
* Given a string, split it at whitespace to form a vector, destructively
* modifying the string to nul-terminate each segment. Any number of
* consecutive whitespace characters are considered a single separator. Reuse
* the provided vector if non-NULL. This is just a special case of
* cvector_split_multi.
*/
struct cvector *
cvector_split_space(char *string, struct cvector *vector)
{
return cvector_split_multi(string, " \t", vector);
}
/*
* Given a vector and a separator string, allocate and build a new string
* composed of all the strings in the vector separated from each other by the
* separator string. Caller is responsible for freeing.
*/
char *
vector_join(const struct vector *vector, const char *separator)
{
char *string;
size_t i, length, offset, size, seplen;
/* If the vector is empty, this is trivial. */
assert(vector != NULL);
if (vector->count == 0)
return xstrdup("");
/*
* Determine the total size of the resulting string. Be careful of
* integer overflow while doing so.
*/
seplen = strlen(separator);
for (size = 0, i = 0; i < vector->count; i++) {
assert(SIZE_MAX - size >= strlen(vector->strings[i]) + seplen + 1);
size += strlen(vector->strings[i]);
}
assert(SIZE_MAX - size >= (vector->count - 1) * seplen + 1);
size += (vector->count - 1) * seplen + 1;
/* Allocate the memory and build up the string. */
string = xmalloc(size);
offset = 0;
for (i = 0; i < vector->count; i++) {
if (i != 0) {
memcpy(string + offset, separator, seplen);
offset += seplen;
}
length = strlen(vector->strings[i]);
memcpy(string + offset, vector->strings[i], length);
offset += length;
assert(offset < size);
}
string[offset] = '\0';
return string;
}
char *
cvector_join(const struct cvector *vector, const char *separator)
{
char *string;
size_t i, length, offset, size, seplen;
/* If the vector is empty, this is trivial. */
assert(vector != NULL);
if (vector->count == 0)
return xstrdup("");
/*
* Determine the total size of the resulting string. Be careful of
* integer overflow while doing so.
*/
seplen = strlen(separator);
for (size = 0, i = 0; i < vector->count; i++) {
assert(SIZE_MAX - size >= strlen(vector->strings[i]));
size += strlen(vector->strings[i]);
}
assert(SIZE_MAX - size >= (vector->count - 1) * seplen + 1);
size += (vector->count - 1) * seplen + 1;
/* Allocate the memory and build up the string. */
string = xmalloc(size);
offset = 0;
for (i = 0; i < vector->count; i++) {
if (i != 0) {
memcpy(string + offset, separator, seplen);
offset += seplen;
}
length = strlen(vector->strings[i]);
memcpy(string + offset, vector->strings[i], length);
offset += length;
assert(offset < size);
}
string[offset] = '\0';
return string;
}
/*
* Given a vector and a path to a program, exec that program with the vector
* as its arguments. This requires adding a NULL terminator to the vector
* (which we do not add to count, so it will be invisible to other users of
* the vector) and casting it appropriately.
*/
int
vector_exec(const char *path, struct vector *vector)
{
assert(vector != NULL);
if (vector->allocated == vector->count)
vector_resize(vector, vector->count + 1);
vector->strings[vector->count] = NULL;
return execv(path, (char *const *) vector->strings);
}
int
cvector_exec(const char *path, struct cvector *vector)
{
assert(vector != NULL);
if (vector->allocated == vector->count)
cvector_resize(vector, vector->count + 1);
vector->strings[vector->count] = NULL;
return execv(path, (char *const *) vector->strings);
}