plugin/vector.c

   1 /*
   2  * Vector handling (counted lists of char *'s).
   3  *
   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
   7  * stable size.
   8  *
   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.
  14  *
  15  * Vectors require list of strings, not arbitrary binary data, and cannot
  16  * handle data elements containing nul characters.
  17  *
  18  * Only the portions of the vector library needed by this module is
  19  * implemented.
  20  *
  21  * Written by Russ Allbery <eagle@eyrie.org>
  22  * Copyright 2013
  23  *     The Board of Trustees of the Leland Stanford Junior University
  24  *
  25  * See LICENSE for licensing terms.
  26  */
  27
  28 #include <config.h>
  29 #include <portable/system.h>
  30
  31 #include <plugin/internal.h>
  32
  33
  34 /*
  35  * Allocate a new, empty vector.  Returns NULL if memory allocation fails.
  36  */
  37 struct vector *
  38 strength_vector_new(void)
  39 {
  40     return calloc(1, sizeof(struct vector));
  41 }
  42
  43
  44 /*
  45  * Resize a vector (using realloc to resize the table).  Return false if
  46  * memory allocation fails.
  47  */
  48 static bool
  49 strength_vector_resize(struct vector *vector, size_t size)
  50 {
  51     size_t i;
  52     char **strings;
  53
  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]);
  58         vector->count = size;
  59     }
  60
  61     /* If resizing to zero, free all storage.  Otherwise, realloc. */
  62     if (size == 0) {
  63         free(vector->strings);
  64         vector->strings = NULL;
  65     } else {
  66         strings = realloc(vector->strings, size * sizeof(char *));
  67         if (strings == NULL)
  68             return false;
  69         vector->strings = strings;
  70     }
  71     vector->allocated = size;
  72     return true;
  73 }
  74
  75
  76 /*
  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.
  81  */
  82 bool
  83 strength_vector_add(struct vector *vector, const char *string)
  84 {
  85     size_t next = vector->count;
  86
  87     if (vector->count == vector->allocated)
  88         if (!strength_vector_resize(vector, vector->allocated + 1))
  89             return false;
  90     vector->strings[next] = strdup(string);
  91     if (vector->strings[next] == NULL)
  92         return false;
  93     vector->count++;
  94     return true;
  95 }
  96
  97
  98 /*
  99  * Empty a vector but keep the allocated memory for the pointer table.
 100  */
 101 static void
 102 strength_vector_clear(struct vector *vector)
 103 {
 104     size_t i;
 105
 106     for (i = 0; i < vector->count; i++)
 107         if (vector->strings[i] != NULL)
 108             free(vector->strings[i]);
 109     vector->count = 0;
 110 }
 111
 112
 113 /*
 114  * Free a vector completely.
 115  */
 116 void
 117 strength_vector_free(struct vector *vector)
 118 {
 119     if (vector == NULL)
 120         return;
 121     strength_vector_clear(vector);
 122     free(vector->strings);
 123     free(vector);
 124 }
 125
 126
 127 /*
 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.
 131  */
 132 static struct vector *
 133 strength_vector_reuse(struct vector *vector)
 134 {
 135     if (vector == NULL)
 136         return strength_vector_new();
 137     else {
 138         strength_vector_clear(vector);
 139         return vector;
 140     }
 141 }
 142
 143
 144 /*
 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
 147  * separators.
 148  */
 149 static size_t
 150 split_multi_count(const char *string, const char *seps)
 151 {
 152     const char *p;
 153     size_t count;
 154
 155     /* If the string is empty, the count of components is zero. */
 156     if (*string == '\0')
 157         return 0;
 158
 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)
 162             count++;
 163
 164     /*
 165      * If the string ends in separators, we've overestimated the number of
 166      * strings by one.
 167      */
 168     if (strchr(seps, p[-1]) != NULL)
 169         count--;
 170     return count;
 171 }
 172
 173
 174 /*
 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
 180  * partial results.
 181  */
 182 struct vector *
 183 strength_vector_split_multi(const char *string, const char *seps,
 184                         struct vector *vector)
 185 {
 186     const char *p, *start;
 187     size_t i, count;
 188     bool created = false;
 189
 190     /* Set up the vector we'll use to store the results. */
 191     if (vector == NULL)
 192         created = true;
 193     vector = strength_vector_reuse(vector);
 194     if (vector == NULL)
 195         return NULL;
 196
 197     /* Count how big a vector we need and resize accordingly. */
 198     count = split_multi_count(string, seps);
 199     if (count == 0)
 200         return vector;
 201     if (vector->allocated < count && !strength_vector_resize(vector, count))
 202         goto fail;
 203
 204     /* Now, walk the string and build the components. */
 205     vector->count = 0;
 206     for (start = string, p = string, i = 0; *p != '\0'; p++)
 207         if (strchr(seps, *p) != NULL) {
 208             if (start != p) {
 209                 vector->strings[i] = strndup(start, (size_t) (p - start));
 210                 if (vector->strings[i] == NULL)
 211                     goto fail;
 212                 i++;
 213                 vector->count++;
 214             }
 215             start = p + 1;
 216         }
 217
 218     /* If there is anything left in the string, we have one more component. */
 219     if (start != p) {
 220         vector->strings[i] = strndup(start, (size_t) (p - start));
 221         if (vector->strings[i] == NULL)
 222             goto fail;
 223         vector->count++;
 224     }
 225     return vector;
 226
 227 fail:
 228     if (created)
 229         strength_vector_free(vector);
 230     return NULL;
 231 }