lib/svec.c

   1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
   2  * Junior University
   3  *
   4  * We are making the OpenFlow specification and associated documentation
   5  * (Software) available for public use and benefit with the expectation
   6  * that others will use, modify and enhance the Software and contribute
   7  * those enhancements back to the community. However, since we would
   8  * like to make the Software available for broadest use, with as few
   9  * restrictions as possible permission is hereby granted, free of
  10  * charge, to any person obtaining a copy of this Software to deal in
  11  * the Software under the copyrights without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  *
  29  * The name and trademarks of copyright holder(s) may NOT be used in
  30  * advertising or publicity pertaining to the Software or any
  31  * derivatives without specific, written prior permission.
  32  */
  33
  34 #include <config.h>
  35 #include "svec.h"
  36 #include <assert.h>
  37 #include <ctype.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include "dynamic-string.h"
  41 #include "util.h"
  42
  43 #define THIS_MODULE VLM_svec
  44 #include "vlog.h"
  45
  46 void
  47 svec_init(struct svec *svec)
  48 {
  49     svec->names = NULL;
  50     svec->n = 0;
  51     svec->allocated = 0;
  52 }
  53
  54 void
  55 svec_destroy(struct svec *svec)
  56 {
  57     svec_clear(svec);
  58     free(svec->names);
  59 }
  60
  61 void
  62 svec_clear(struct svec *svec)
  63 {
  64     size_t i;
  65
  66     for (i = 0; i < svec->n; i++) {
  67         free(svec->names[i]);
  68     }
  69     svec->n = 0;
  70 }
  71
  72 void
  73 svec_add(struct svec *svec, const char *name)
  74 {
  75     svec_add_nocopy(svec, xstrdup(name));
  76 }
  77
  78 static void
  79 svec_expand(struct svec *svec)
  80 {
  81     if (svec->n >= svec->allocated) {
  82         svec->names = x2nrealloc(svec->names, &svec->allocated,
  83                                  sizeof *svec->names);
  84     }
  85 }
  86
  87 void
  88 svec_add_nocopy(struct svec *svec, char *name)
  89 {
  90     svec_expand(svec);
  91     svec->names[svec->n++] = name;
  92 }
  93
  94 void
  95 svec_append(struct svec *svec, const struct svec *other)
  96 {
  97     size_t i;
  98     for (i = 0; i < other->n; i++) {
  99         svec_add(svec, other->names[i]);
 100     }
 101 }
 102
 103 void
 104 svec_terminate(struct svec *svec)
 105 {
 106     svec_expand(svec);
 107     svec->names[svec->n] = NULL;
 108 }
 109
 110 static int
 111 compare_strings(const void *a_, const void *b_)
 112 {
 113     char *const *a = a_;
 114     char *const *b = b_;
 115     return strcmp(*a, *b);
 116 }
 117
 118 void
 119 svec_sort(struct svec *svec)
 120 {
 121     qsort(svec->names, svec->n, sizeof *svec->names, compare_strings);
 122 }
 123
 124 void
 125 svec_unique(struct svec *svec)
 126 {
 127     assert(svec_is_sorted(svec));
 128     if (svec->n > 1) {
 129         /* This algorithm is lazy and sub-optimal, but it's "obviously correct"
 130          * and asymptotically optimal . */
 131         struct svec tmp;
 132         size_t i;
 133
 134         svec_init(&tmp);
 135         svec_add(&tmp, svec->names[0]);
 136         for (i = 1; i < svec->n; i++) {
 137             if (strcmp(svec->names[i - 1], svec->names[i])) {
 138                 svec_add(&tmp, svec->names[i]);
 139             }
 140         }
 141         svec_swap(&tmp, svec);
 142         svec_destroy(&tmp);
 143     }
 144 }
 145
 146 void
 147 svec_diff(const struct svec *a, const struct svec *b,
 148           struct svec *a_only, struct svec *both, struct svec *b_only)
 149 {
 150     size_t i, j;
 151
 152     assert(svec_is_sorted(a));
 153     assert(svec_is_sorted(b));
 154     if (a_only) {
 155         svec_init(a_only);
 156     }
 157     if (both) {
 158         svec_init(both);
 159     }
 160     if (b_only) {
 161         svec_init(b_only);
 162     }
 163     for (i = j = 0; i < a->n && j < b->n; ) {
 164         int cmp = strcmp(a->names[i], b->names[j]);
 165         if (cmp < 0) {
 166             if (a_only) {
 167                 svec_add(a_only, a->names[i]);
 168             }
 169             i++;
 170         } else if (cmp > 0) {
 171             if (b_only) {
 172                 svec_add(b_only, b->names[j]);
 173             }
 174             j++;
 175         } else {
 176             if (both) {
 177                 svec_add(both, a->names[i]);
 178             }
 179             i++;
 180             j++;
 181         }
 182     }
 183     if (a_only) {
 184         for (; i < a->n; i++) {
 185             svec_add(a_only, a->names[i]);
 186         }
 187     }
 188     if (b_only) {
 189         for (; j < b->n; j++) {
 190             svec_add(b_only, b->names[j]);
 191         }
 192     }
 193 }
 194
 195 bool
 196 svec_contains(const struct svec *svec, const char *name)
 197 {
 198     assert(svec_is_sorted(svec));
 199     return bsearch(&name, svec->names, svec->n, sizeof *svec->names,
 200                    compare_strings) != NULL;
 201 }
 202
 203 bool
 204 svec_is_sorted(const struct svec *svec)
 205 {
 206     size_t i;
 207
 208     for (i = 1; i < svec->n; i++) {
 209         if (strcmp(svec->names[i - 1], svec->names[i]) > 0) {
 210             return false;
 211         }
 212     }
 213     return true;
 214 }
 215
 216 void
 217 svec_swap(struct svec *a, struct svec *b)
 218 {
 219     struct svec tmp = *a;
 220     *a = *b;
 221     *b = tmp;
 222 }
 223
 224 void
 225 svec_print(const struct svec *svec, const char *title)
 226 {
 227     size_t i;
 228
 229     printf("%s:\n", title);
 230     for (i = 0; i < svec->n; i++) {
 231         printf("\"%s\"\n", svec->names[i]);
 232     }
 233 }
 234
 235 /* Breaks 'words' into words at white space, respecting shell-like quoting
 236  * conventions, and appends the words to 'svec'. */
 237 void
 238 svec_parse_words(struct svec *svec, const char *words)
 239 {
 240     struct ds word = DS_EMPTY_INITIALIZER;
 241     const char *p, *q;
 242
 243     for (p = words; *p != '\0'; p = q) {
 244         int quote = 0;
 245
 246         while (isspace((unsigned char) *p)) {
 247             p++;
 248         }
 249         if (*p == '\0') {
 250             break;
 251         }
 252
 253         ds_clear(&word);
 254         for (q = p; *q != '\0'; q++) {
 255             if (*q == quote) {
 256                 quote = 0;
 257             } else if (*q == '\'' || *q == '"') {
 258                 quote = *q;
 259             } else if (*q == '\\' && (!quote || quote == '"')) {
 260                 q++;
 261                 if (*q == '\0') {
 262                     VLOG_WARN("%s: ends in trailing backslash", words);
 263                     break;
 264                 }
 265                 ds_put_char(&word, *q);
 266             } else if (isspace((unsigned char) *q) && !quote) {
 267                 q++;
 268                 break;
 269             } else {
 270                 ds_put_char(&word, *q);
 271             }
 272         }
 273         svec_add(svec, ds_cstr(&word));
 274         if (quote) {
 275             VLOG_WARN("%s: word ends inside quoted string", words);
 276         }
 277     }
 278     ds_destroy(&word);
 279 }
 280
 281 bool
 282 svec_equal(const struct svec *a, const struct svec *b)
 283 {
 284     size_t i;
 285
 286     if (a->n != b->n) {
 287         return false;
 288     }
 289     for (i = 0; i < a->n; i++) {
 290         if (strcmp(a->names[i], b->names[i])) {
 291             return false;
 292         }
 293     }
 294     return true;
 295 }