lib/svec.c

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