lib/vector.c

   1 /*  $Id: vector.c 6699 2004-04-07 06:47:44Z rra $
   2 **
   3 **  Vector handling (counted lists of char *'s).
   4 **
   5 **  Written by Russ Allbery <rra@stanford.edu>
   6 **  This work is hereby placed in the public domain by its author.
   7 **
   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
  11 **  stable size.
  12 **
  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.
  17 **
  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.
  23 */
  24
  25 #include "config.h"
  26 #include "clibrary.h"
  27 #include <ctype.h>
  28
  29 #include "inn/vector.h"
  30 #include "libinn.h"
  31
  32 /*
  33 **  Allocate a new, empty vector.
  34 */
  35 struct vector *
  36 vector_new(void)
  37 {
  38     struct vector *vector;
  39
  40     vector = xmalloc(sizeof(struct vector));
  41     vector->count = 0;
  42     vector->allocated = 0;
  43     vector->strings = NULL;
  44     return vector;
  45 }
  46
  47 struct cvector *
  48 cvector_new(void)
  49 {
  50     struct cvector *vector;
  51
  52     vector = xmalloc(sizeof(struct cvector));
  53     vector->count = 0;
  54     vector->allocated = 0;
  55     vector->strings = NULL;
  56     return vector;
  57 }
  58
  59
  60 /*
  61 **  Resize a vector (using realloc to resize the table).
  62 */
  63 void
  64 vector_resize(struct vector *vector, size_t size)
  65 {
  66     size_t i;
  67
  68     if (vector->count > size) {
  69         for (i = size; i < vector->count; i++)
  70             free(vector->strings[i]);
  71         vector->count = size;
  72     }
  73     if (size == 0) {
  74         free(vector->strings);
  75         vector->strings = NULL;
  76     } else {
  77         vector->strings = xrealloc(vector->strings, size * sizeof(char *));
  78     }
  79     vector->allocated = size;
  80 }
  81
  82 void
  83 cvector_resize(struct cvector *vector, size_t size)
  84 {
  85     if (vector->count > size)
  86         vector->count = size;
  87     if (size == 0) {
  88         free(vector->strings);
  89         vector->strings = NULL;
  90     } else {
  91         vector->strings =
  92             xrealloc(vector->strings, size * sizeof(const char *));
  93     }
  94     vector->allocated = size;
  95 }
  96
  97
  98 /*
  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.
 102 */
 103 void
 104 vector_add(struct vector *vector, const char *string)
 105 {
 106     size_t next = vector->count;
 107
 108     if (vector->count == vector->allocated)
 109         vector_resize(vector, vector->allocated + 1);
 110     vector->strings[next] = xstrdup(string);
 111     vector->count++;
 112 }
 113
 114 void
 115 cvector_add(struct cvector *vector, const char *string)
 116 {
 117     size_t next = vector->count;
 118
 119     if (vector->count == vector->allocated)
 120         cvector_resize(vector, vector->allocated + 1);
 121     vector->strings[next] = string;
 122     vector->count++;
 123 }
 124
 125
 126 /*
 127 **  Empty a vector but keep the allocated memory for the pointer table.
 128 */
 129 void
 130 vector_clear(struct vector *vector)
 131 {
 132     size_t i;
 133
 134     for (i = 0; i < vector->count; i++)
 135         free(vector->strings[i]);
 136     vector->count = 0;
 137 }
 138
 139 void
 140 cvector_clear(struct cvector *vector)
 141 {
 142     vector->count = 0;
 143 }
 144
 145
 146 /*
 147 **  Free a vector completely.
 148 */
 149 void
 150 vector_free(struct vector *vector)
 151 {
 152     vector_clear(vector);
 153     free(vector->strings);
 154     free(vector);
 155 }
 156
 157 void
 158 cvector_free(struct cvector *vector)
 159 {
 160     cvector_clear(vector);
 161     free(vector->strings);
 162     free(vector);
 163 }
 164
 165
 166 /*
 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*.
 169 */
 170 static struct vector *
 171 vector_reuse(struct vector *vector)
 172 {
 173     if (vector == NULL)
 174         return vector_new();
 175     else {
 176         vector_clear(vector);
 177         return vector;
 178     }
 179 }
 180
 181 static struct cvector *
 182 cvector_reuse(struct cvector *vector)
 183 {
 184     if (vector == NULL)
 185         return cvector_new();
 186     else {
 187         cvector_clear(vector);
 188         return vector;
 189     }
 190 }
 191
 192
 193 /*
 194 **  Given a string and a separator character, count the number of strings
 195 **  that it will split into.
 196 */
 197 static size_t
 198 split_count(const char *string, char separator)
 199 {
 200     const char *p;
 201     size_t count;
 202
 203     if (*string == '\0')
 204         return 1;
 205     for (count = 1, p = string; *p; p++)
 206         if (*p == separator)
 207             count++;
 208     return count;
 209 }
 210
 211
 212 /*
 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.
 216 */
 217 struct vector *
 218 vector_split(const char *string, char separator, struct vector *vector)
 219 {
 220     const char *p, *start;
 221     size_t i, count;
 222
 223     vector = vector_reuse(vector);
 224
 225     count = split_count(string, separator);
 226     if (vector->allocated < count)
 227         vector_resize(vector, count);
 228
 229     for (start = string, p = string, i = 0; *p; p++)
 230         if (*p == separator) {
 231             vector->strings[i++] = xstrndup(start, p - start);
 232             start = p + 1;
 233         }
 234     vector->strings[i++] = xstrndup(start, p - start);
 235     vector->count = i;
 236
 237     return vector;
 238 }
 239
 240
 241 /*
 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.
 247 */
 248 struct cvector *
 249 cvector_split(char *string, char separator, struct cvector *vector)
 250 {
 251     char *p, *start;
 252     size_t i, count;
 253
 254     vector = cvector_reuse(vector);
 255
 256     count = split_count(string, separator);
 257     if (vector->allocated < count)
 258         cvector_resize(vector, count);
 259
 260     for (start = string, p = string, i = 0; *p; p++)
 261         if (*p == separator) {
 262             *p = '\0';
 263             vector->strings[i++] = start;
 264             start = p + 1;
 265         }
 266     vector->strings[i++] = start;
 267     vector->count = i;
 268
 269     return vector;
 270 }
 271
 272
 273 /*
 274 **  Given a string, count the number of strings that it will split into when
 275 **  splitting on whitespace.
 276 */
 277 static size_t
 278 split_space_count(const char *string)
 279 {
 280     const char *p;
 281     size_t count;
 282
 283     if (*string == '\0')
 284         return 0;
 285     for (count = 1, p = string + 1; *p != '\0'; p++)
 286         if ((*p == ' ' || *p == '\t') && !(p[-1] == ' ' || p[-1] == '\t'))
 287             count++;
 288
 289     /* If the string ends in whitespace, we've overestimated the number of
 290        strings by one. */
 291     if (p[-1] == ' ' || p[-1] == '\t')
 292         count--;
 293     return count;
 294 }
 295
 296
 297 /*
 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.
 302 */
 303 struct vector *
 304 vector_split_space(const char *string, struct vector *vector)
 305 {
 306     const char *p, *start;
 307     size_t i, count;
 308
 309     vector = vector_reuse(vector);
 310
 311     count = split_space_count(string);
 312     if (vector->allocated < count)
 313         vector_resize(vector, count);
 314
 315     for (start = string, p = string, i = 0; *p; p++)
 316         if (*p == ' ' || *p == '\t') {
 317             if (start != p)
 318                 vector->strings[i++] = xstrndup(start, p - start);
 319             start = p + 1;
 320         }
 321     if (start != p)
 322         vector->strings[i++] = xstrndup(start, p - start);
 323     vector->count = i;
 324
 325     return vector;
 326 }
 327
 328
 329 /*
 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
 334 **  separator.
 335 */
 336 struct cvector *
 337 cvector_split_space(char *string, struct cvector *vector)
 338 {
 339     char *p, *start;
 340     size_t i, count;
 341
 342     vector = cvector_reuse(vector);
 343
 344     count = split_space_count(string);
 345     if (vector->allocated < count)
 346         cvector_resize(vector, count);
 347
 348     for (start = string, p = string, i = 0; *p; p++)
 349         if (*p == ' ' || *p == '\t') {
 350             if (start != p) {
 351                 *p = '\0';
 352                 vector->strings[i++] = start;
 353             }
 354             start = p + 1;
 355         }
 356     if (start != p)
 357         vector->strings[i++] = start;
 358     vector->count = i;
 359
 360     return vector;
 361 }
 362
 363
 364 /*
 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.
 368 */
 369 char *
 370 vector_join(const struct vector *vector, const char *seperator)
 371 {
 372     char *string;
 373     size_t i, size, seplen;
 374
 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;
 379
 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);
 385     }
 386
 387     return string;
 388 }
 389
 390 char *
 391 cvector_join(const struct cvector *vector, const char *seperator)
 392 {
 393     char *string;
 394     size_t i, size, seplen;
 395
 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;
 400
 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);
 406     }
 407
 408     return string;
 409 }