lib/svec.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
   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_terminate(struct svec *svec)
 115 {
 116     svec_expand(svec);
 117     svec->names[svec->n] = NULL;
 118 }
 119
 120 static int
 121 compare_strings(const void *a_, const void *b_)
 122 {
 123     char *const *a = a_;
 124     char *const *b = b_;
 125     return strcmp(*a, *b);
 126 }
 127
 128 void
 129 svec_sort(struct svec *svec)
 130 {
 131     qsort(svec->names, svec->n, sizeof *svec->names, compare_strings);
 132 }
 133
 134 void
 135 svec_sort_unique(struct svec *svec)
 136 {
 137     svec_sort(svec);
 138     svec_unique(svec);
 139 }
 140
 141 void
 142 svec_unique(struct svec *svec)
 143 {
 144     assert(svec_is_sorted(svec));
 145     if (svec->n > 1) {
 146         /* This algorithm is lazy and sub-optimal, but it's "obviously correct"
 147          * and asymptotically optimal . */
 148         struct svec tmp;
 149         size_t i;
 150
 151         svec_init(&tmp);
 152         svec_add(&tmp, svec->names[0]);
 153         for (i = 1; i < svec->n; i++) {
 154             if (strcmp(svec->names[i - 1], svec->names[i])) {
 155                 svec_add(&tmp, svec->names[i]);
 156             }
 157         }
 158         svec_swap(&tmp, svec);
 159         svec_destroy(&tmp);
 160     }
 161 }
 162
 163 void
 164 svec_compact(struct svec *svec)
 165 {
 166     size_t i, j;
 167
 168     for (i = j = 0; i < svec->n; i++) {
 169         if (svec->names[i] != NULL) {
 170             svec->names[j++] = svec->names[i];
 171         }
 172     }
 173     svec->n = j;
 174 }
 175
 176 void
 177 svec_diff(const struct svec *a, const struct svec *b,
 178           struct svec *a_only, struct svec *both, struct svec *b_only)
 179 {
 180     size_t i, j;
 181
 182     assert(svec_is_sorted(a));
 183     assert(svec_is_sorted(b));
 184     if (a_only) {
 185         svec_init(a_only);
 186     }
 187     if (both) {
 188         svec_init(both);
 189     }
 190     if (b_only) {
 191         svec_init(b_only);
 192     }
 193     for (i = j = 0; i < a->n && j < b->n; ) {
 194         int cmp = strcmp(a->names[i], b->names[j]);
 195         if (cmp < 0) {
 196             if (a_only) {
 197                 svec_add(a_only, a->names[i]);
 198             }
 199             i++;
 200         } else if (cmp > 0) {
 201             if (b_only) {
 202                 svec_add(b_only, b->names[j]);
 203             }
 204             j++;
 205         } else {
 206             if (both) {
 207                 svec_add(both, a->names[i]);
 208             }
 209             i++;
 210             j++;
 211         }
 212     }
 213     if (a_only) {
 214         for (; i < a->n; i++) {
 215             svec_add(a_only, a->names[i]);
 216         }
 217     }
 218     if (b_only) {
 219         for (; j < b->n; j++) {
 220             svec_add(b_only, b->names[j]);
 221         }
 222     }
 223 }
 224
 225 bool
 226 svec_contains(const struct svec *svec, const char *name)
 227 {
 228     return svec_find(svec, name) != SIZE_MAX;
 229 }
 230
 231 size_t
 232 svec_find(const struct svec *svec, const char *name)
 233 {
 234     char **p;
 235
 236     assert(svec_is_sorted(svec));
 237     p = bsearch(&name, svec->names, svec->n, sizeof *svec->names,
 238                 compare_strings);
 239     return p ? p - svec->names : SIZE_MAX;
 240 }
 241
 242 bool
 243 svec_is_sorted(const struct svec *svec)
 244 {
 245     size_t i;
 246
 247     for (i = 1; i < svec->n; i++) {
 248         if (strcmp(svec->names[i - 1], svec->names[i]) > 0) {
 249             return false;
 250         }
 251     }
 252     return true;
 253 }
 254
 255 bool
 256 svec_is_unique(const struct svec *svec)
 257 {
 258     return svec_get_duplicate(svec) == NULL;
 259 }
 260
 261 const char *
 262 svec_get_duplicate(const struct svec *svec)
 263 {
 264     assert(svec_is_sorted(svec));
 265     if (svec->n > 1) {
 266         size_t i;
 267         for (i = 1; i < svec->n; i++) {
 268             if (!strcmp(svec->names[i - 1], svec->names[i])) {
 269                 return svec->names[i];
 270             }
 271         }
 272     }
 273     return NULL;
 274 }
 275
 276 void
 277 svec_swap(struct svec *a, struct svec *b)
 278 {
 279     struct svec tmp = *a;
 280     *a = *b;
 281     *b = tmp;
 282 }
 283
 284 void
 285 svec_print(const struct svec *svec, const char *title)
 286 {
 287     size_t i;
 288
 289     printf("%s:\n", title);
 290     for (i = 0; i < svec->n; i++) {
 291         printf("\"%s\"\n", svec->names[i]);
 292     }
 293 }
 294
 295 /* Breaks 'words' into words at white space, respecting shell-like quoting
 296  * conventions, and appends the words to 'svec'. */
 297 void
 298 svec_parse_words(struct svec *svec, const char *words)
 299 {
 300     struct ds word = DS_EMPTY_INITIALIZER;
 301     const char *p, *q;
 302
 303     for (p = words; *p != '\0'; p = q) {
 304         int quote = 0;
 305
 306         while (isspace((unsigned char) *p)) {
 307             p++;
 308         }
 309         if (*p == '\0') {
 310             break;
 311         }
 312
 313         ds_clear(&word);
 314         for (q = p; *q != '\0'; q++) {
 315             if (*q == quote) {
 316                 quote = 0;
 317             } else if (*q == '\'' || *q == '"') {
 318                 quote = *q;
 319             } else if (*q == '\\' && (!quote || quote == '"')) {
 320                 q++;
 321                 if (*q == '\0') {
 322                     VLOG_WARN("%s: ends in trailing backslash", words);
 323                     break;
 324                 }
 325                 ds_put_char(&word, *q);
 326             } else if (isspace((unsigned char) *q) && !quote) {
 327                 q++;
 328                 break;
 329             } else {
 330                 ds_put_char(&word, *q);
 331             }
 332         }
 333         svec_add(svec, ds_cstr(&word));
 334         if (quote) {
 335             VLOG_WARN("%s: word ends inside quoted string", words);
 336         }
 337     }
 338     ds_destroy(&word);
 339 }
 340
 341 bool
 342 svec_equal(const struct svec *a, const struct svec *b)
 343 {
 344     size_t i;
 345
 346     if (a->n != b->n) {
 347         return false;
 348     }
 349     for (i = 0; i < a->n; i++) {
 350         if (strcmp(a->names[i], b->names[i])) {
 351             return false;
 352         }
 353     }
 354     return true;
 355 }
 356
 357 char *
 358 svec_join(const struct svec *svec,
 359           const char *delimiter, const char *terminator)
 360 {
 361     struct ds ds;
 362     size_t i;
 363
 364     ds_init(&ds);
 365     for (i = 0; i < svec->n; i++) {
 366         if (i) {
 367             ds_put_cstr(&ds, delimiter);
 368         }
 369         ds_put_cstr(&ds, svec->names[i]);
 370     }
 371     ds_put_cstr(&ds, terminator);
 372     return ds_cstr(&ds);
 373 }
 374
 375 const char *
 376 svec_back(const struct svec *svec)
 377 {
 378     assert(svec->n);
 379     return svec->names[svec->n - 1];
 380 }
 381
 382 void
 383 svec_pop_back(struct svec *svec)
 384 {
 385     assert(svec->n);
 386     free(svec->names[--svec->n]);
 387 }