lib/svec.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "svec.h"
  19 #include <assert.h>
  20 #include <ctype.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include "dynamic-string.h"
  24 #include "util.h"
  25 #include "vlog.h"
  26
  27 VLOG_DEFINE_THIS_MODULE(svec)
  28
  29 void
  30 svec_init(struct svec *svec)
  31 {
  32     svec->names = NULL;
  33     svec->n = 0;
  34     svec->allocated = 0;
  35 }
  36
  37 void
  38 svec_clone(struct svec *svec, const struct svec *other)
  39 {
  40     svec_init(svec);
  41     svec_append(svec, other);
  42 }
  43
  44 void
  45 svec_destroy(struct svec *svec)
  46 {
  47     svec_clear(svec);
  48     free(svec->names);
  49 }
  50
  51 void
  52 svec_clear(struct svec *svec)
  53 {
  54     size_t i;
  55
  56     for (i = 0; i < svec->n; i++) {
  57         free(svec->names[i]);
  58     }
  59     svec->n = 0;
  60 }
  61
  62 bool
  63 svec_is_empty(const struct svec *svec)
  64 {
  65     return svec->n == 0;
  66 }
  67
  68 void
  69 svec_add(struct svec *svec, const char *name)
  70 {
  71     svec_add_nocopy(svec, xstrdup(name));
  72 }
  73
  74 void
  75 svec_del(struct svec *svec, const char *name)
  76 {
  77     size_t offset;
  78
  79     offset = svec_find(svec, name);
  80     if (offset != SIZE_MAX) {
  81         free(svec->names[offset]);
  82         memmove(&svec->names[offset], &svec->names[offset + 1],
  83                 sizeof *svec->names * (svec->n - offset - 1));
  84         svec->n--;
  85     }
  86 }
  87
  88 static void
  89 svec_expand(struct svec *svec)
  90 {
  91     if (svec->n >= svec->allocated) {
  92         svec->names = x2nrealloc(svec->names, &svec->allocated,
  93                                  sizeof *svec->names);
  94     }
  95 }
  96
  97 void
  98 svec_add_nocopy(struct svec *svec, char *name)
  99 {
 100     svec_expand(svec);
 101     svec->names[svec->n++] = name;
 102 }
 103
 104 void
 105 svec_append(struct svec *svec, const struct svec *other)
 106 {
 107     size_t i;
 108     for (i = 0; i < other->n; i++) {
 109         svec_add(svec, other->names[i]);
 110     }
 111 }
 112
 113 void
 114 svec_move(struct svec *svec, struct svec *other)
 115 {
 116     size_t i;
 117     for (i = 0; i < other->n; i++) {
 118         svec_add_nocopy(svec, other->names[i]);
 119     }
 120     other->n = 0;
 121 }
 122
 123 void
 124 svec_terminate(struct svec *svec)
 125 {
 126     svec_expand(svec);
 127     svec->names[svec->n] = NULL;
 128 }
 129
 130 static int
 131 compare_strings(const void *a_, const void *b_)
 132 {
 133     char *const *a = a_;
 134     char *const *b = b_;
 135     return strcmp(*a, *b);
 136 }
 137
 138 void
 139 svec_sort(struct svec *svec)
 140 {
 141     qsort(svec->names, svec->n, sizeof *svec->names, compare_strings);
 142 }
 143
 144 void
 145 svec_sort_unique(struct svec *svec)
 146 {
 147     svec_sort(svec);
 148     svec_unique(svec);
 149 }
 150
 151 void
 152 svec_unique(struct svec *svec)
 153 {
 154     assert(svec_is_sorted(svec));
 155     if (svec->n > 1) {
 156         /* This algorithm is lazy and sub-optimal, but it's "obviously correct"
 157          * and asymptotically optimal . */
 158         struct svec tmp;
 159         size_t i;
 160
 161         svec_init(&tmp);
 162         svec_add(&tmp, svec->names[0]);
 163         for (i = 1; i < svec->n; i++) {
 164             if (strcmp(svec->names[i - 1], svec->names[i])) {
 165                 svec_add(&tmp, svec->names[i]);
 166             }
 167         }
 168         svec_swap(&tmp, svec);
 169         svec_destroy(&tmp);
 170     }
 171 }
 172
 173 void
 174 svec_compact(struct svec *svec)
 175 {
 176     size_t i, j;
 177
 178     for (i = j = 0; i < svec->n; i++) {
 179         if (svec->names[i] != NULL) {
 180             svec->names[j++] = svec->names[i];
 181         }
 182     }
 183     svec->n = j;
 184 }
 185
 186 void
 187 svec_diff(const struct svec *a, const struct svec *b,
 188           struct svec *a_only, struct svec *both, struct svec *b_only)
 189 {
 190     size_t i, j;
 191
 192     assert(svec_is_sorted(a));
 193     assert(svec_is_sorted(b));
 194     if (a_only) {
 195         svec_init(a_only);
 196     }
 197     if (both) {
 198         svec_init(both);
 199     }
 200     if (b_only) {
 201         svec_init(b_only);
 202     }
 203     for (i = j = 0; i < a->n && j < b->n; ) {
 204         int cmp = strcmp(a->names[i], b->names[j]);
 205         if (cmp < 0) {
 206             if (a_only) {
 207                 svec_add(a_only, a->names[i]);
 208             }
 209             i++;
 210         } else if (cmp > 0) {
 211             if (b_only) {
 212                 svec_add(b_only, b->names[j]);
 213             }
 214             j++;
 215         } else {
 216             if (both) {
 217                 svec_add(both, a->names[i]);
 218             }
 219             i++;
 220             j++;
 221         }
 222     }
 223     if (a_only) {
 224         for (; i < a->n; i++) {
 225             svec_add(a_only, a->names[i]);
 226         }
 227     }
 228     if (b_only) {
 229         for (; j < b->n; j++) {
 230             svec_add(b_only, b->names[j]);
 231         }
 232     }
 233 }
 234
 235 bool
 236 svec_contains(const struct svec *svec, const char *name)
 237 {
 238     return svec_find(svec, name) != SIZE_MAX;
 239 }
 240
 241 size_t
 242 svec_find(const struct svec *svec, const char *name)
 243 {
 244     char **p;
 245
 246     assert(svec_is_sorted(svec));
 247     p = bsearch(&name, svec->names, svec->n, sizeof *svec->names,
 248                 compare_strings);
 249     return p ? p - svec->names : SIZE_MAX;
 250 }
 251
 252 bool
 253 svec_is_sorted(const struct svec *svec)
 254 {
 255     size_t i;
 256
 257     for (i = 1; i < svec->n; i++) {
 258         if (strcmp(svec->names[i - 1], svec->names[i]) > 0) {
 259             return false;
 260         }
 261     }
 262     return true;
 263 }
 264
 265 bool
 266 svec_is_unique(const struct svec *svec)
 267 {
 268     return svec_get_duplicate(svec) == NULL;
 269 }
 270
 271 const char *
 272 svec_get_duplicate(const struct svec *svec)
 273 {
 274     assert(svec_is_sorted(svec));
 275     if (svec->n > 1) {
 276         size_t i;
 277         for (i = 1; i < svec->n; i++) {
 278             if (!strcmp(svec->names[i - 1], svec->names[i])) {
 279                 return svec->names[i];
 280             }
 281         }
 282     }
 283     return NULL;
 284 }
 285
 286 void
 287 svec_swap(struct svec *a, struct svec *b)
 288 {
 289     struct svec tmp = *a;
 290     *a = *b;
 291     *b = tmp;
 292 }
 293
 294 void
 295 svec_print(const struct svec *svec, const char *title)
 296 {
 297     size_t i;
 298
 299     printf("%s:\n", title);
 300     for (i = 0; i < svec->n; i++) {
 301         printf("\"%s\"\n", svec->names[i]);
 302     }
 303 }
 304
 305 /* Breaks 'words' into words at white space, respecting shell-like quoting
 306  * conventions, and appends the words to 'svec'. */
 307 void
 308 svec_parse_words(struct svec *svec, const char *words)
 309 {
 310     struct ds word = DS_EMPTY_INITIALIZER;
 311     const char *p, *q;
 312
 313     for (p = words; *p != '\0'; p = q) {
 314         int quote = 0;
 315
 316         while (isspace((unsigned char) *p)) {
 317             p++;
 318         }
 319         if (*p == '\0') {
 320             break;
 321         }
 322
 323         ds_clear(&word);
 324         for (q = p; *q != '\0'; q++) {
 325             if (*q == quote) {
 326                 quote = 0;
 327             } else if (*q == '\'' || *q == '"') {
 328                 quote = *q;
 329             } else if (*q == '\\' && (!quote || quote == '"')) {
 330                 q++;
 331                 if (*q == '\0') {
 332                     VLOG_WARN("%s: ends in trailing backslash", words);
 333                     break;
 334                 }
 335                 ds_put_char(&word, *q);
 336             } else if (isspace((unsigned char) *q) && !quote) {
 337                 q++;
 338                 break;
 339             } else {
 340                 ds_put_char(&word, *q);
 341             }
 342         }
 343         svec_add(svec, ds_cstr(&word));
 344         if (quote) {
 345             VLOG_WARN("%s: word ends inside quoted string", words);
 346         }
 347     }
 348     ds_destroy(&word);
 349 }
 350
 351 bool
 352 svec_equal(const struct svec *a, const struct svec *b)
 353 {
 354     size_t i;
 355
 356     if (a->n != b->n) {
 357         return false;
 358     }
 359     for (i = 0; i < a->n; i++) {
 360         if (strcmp(a->names[i], b->names[i])) {
 361             return false;
 362         }
 363     }
 364     return true;
 365 }
 366
 367 char *
 368 svec_join(const struct svec *svec,
 369           const char *delimiter, const char *terminator)
 370 {
 371     struct ds ds;
 372     size_t i;
 373
 374     ds_init(&ds);
 375     for (i = 0; i < svec->n; i++) {
 376         if (i) {
 377             ds_put_cstr(&ds, delimiter);
 378         }
 379         ds_put_cstr(&ds, svec->names[i]);
 380     }
 381     ds_put_cstr(&ds, terminator);
 382     return ds_cstr(&ds);
 383 }
 384
 385 /* Breaks 's' into tokens at any character in 'delimiters', and appends each
 386  * token to 'svec'.  Empty tokens are not added. */
 387 void
 388 svec_split(struct svec *svec, const char *s_, const char *delimiters)
 389 {
 390     char *s = xstrdup(s_);
 391     char *save_ptr = NULL;
 392     char *token;
 393
 394     for (token = strtok_r(s, delimiters, &save_ptr); token != NULL;
 395          token = strtok_r(NULL, delimiters, &save_ptr)) {
 396         svec_add(svec, token);
 397     }
 398     free(s);
 399 }
 400
 401 const char *
 402 svec_back(const struct svec *svec)
 403 {
 404     assert(svec->n);
 405     return svec->names[svec->n - 1];
 406 }
 407
 408 void
 409 svec_pop_back(struct svec *svec)
 410 {
 411     assert(svec->n);
 412     free(svec->names[--svec->n]);
 413 }