From 064af42167bf4fc9aaea2702d80ce08074b889c0 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 8 Jul 2009 13:19:16 -0700 Subject: Import from old repository commit 61ef2b42a9c4ba8e1600f15bb0236765edc2ad45. --- lib/svec.c | 381 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 381 insertions(+) create mode 100644 lib/svec.c (limited to 'lib/svec.c') diff --git a/lib/svec.c b/lib/svec.c new file mode 100644 index 00000000..4f8968d1 --- /dev/null +++ b/lib/svec.c @@ -0,0 +1,381 @@ +/* + * Copyright (c) 2008, 2009 Nicira Networks. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include "svec.h" +#include +#include +#include +#include +#include "dynamic-string.h" +#include "util.h" + +#define THIS_MODULE VLM_svec +#include "vlog.h" + +void +svec_init(struct svec *svec) +{ + svec->names = NULL; + svec->n = 0; + svec->allocated = 0; +} + +void +svec_clone(struct svec *svec, const struct svec *other) +{ + svec_init(svec); + svec_append(svec, other); +} + +void +svec_destroy(struct svec *svec) +{ + svec_clear(svec); + free(svec->names); +} + +void +svec_clear(struct svec *svec) +{ + size_t i; + + for (i = 0; i < svec->n; i++) { + free(svec->names[i]); + } + svec->n = 0; +} + +void +svec_add(struct svec *svec, const char *name) +{ + svec_add_nocopy(svec, xstrdup(name)); +} + +void +svec_del(struct svec *svec, const char *name) +{ + size_t offset; + + offset = svec_find(svec, name); + if (offset != SIZE_MAX) { + free(svec->names[offset]); + memmove(&svec->names[offset], &svec->names[offset + 1], + sizeof *svec->names * (svec->n - offset - 1)); + svec->n--; + } +} + +static void +svec_expand(struct svec *svec) +{ + if (svec->n >= svec->allocated) { + svec->names = x2nrealloc(svec->names, &svec->allocated, + sizeof *svec->names); + } +} + +void +svec_add_nocopy(struct svec *svec, char *name) +{ + svec_expand(svec); + svec->names[svec->n++] = name; +} + +void +svec_append(struct svec *svec, const struct svec *other) +{ + size_t i; + for (i = 0; i < other->n; i++) { + svec_add(svec, other->names[i]); + } +} + +void +svec_terminate(struct svec *svec) +{ + svec_expand(svec); + svec->names[svec->n] = NULL; +} + +static int +compare_strings(const void *a_, const void *b_) +{ + char *const *a = a_; + char *const *b = b_; + return strcmp(*a, *b); +} + +void +svec_sort(struct svec *svec) +{ + qsort(svec->names, svec->n, sizeof *svec->names, compare_strings); +} + +void +svec_sort_unique(struct svec *svec) +{ + svec_sort(svec); + svec_unique(svec); +} + +void +svec_unique(struct svec *svec) +{ + assert(svec_is_sorted(svec)); + if (svec->n > 1) { + /* This algorithm is lazy and sub-optimal, but it's "obviously correct" + * and asymptotically optimal . */ + struct svec tmp; + size_t i; + + svec_init(&tmp); + svec_add(&tmp, svec->names[0]); + for (i = 1; i < svec->n; i++) { + if (strcmp(svec->names[i - 1], svec->names[i])) { + svec_add(&tmp, svec->names[i]); + } + } + svec_swap(&tmp, svec); + svec_destroy(&tmp); + } +} + +void +svec_compact(struct svec *svec) +{ + size_t i, j; + + for (i = j = 0; i < svec->n; i++) { + if (svec->names[i] != NULL) { + svec->names[j++] = svec->names[i]; + } + } + svec->n = j; +} + +void +svec_diff(const struct svec *a, const struct svec *b, + struct svec *a_only, struct svec *both, struct svec *b_only) +{ + size_t i, j; + + assert(svec_is_sorted(a)); + assert(svec_is_sorted(b)); + if (a_only) { + svec_init(a_only); + } + if (both) { + svec_init(both); + } + if (b_only) { + svec_init(b_only); + } + for (i = j = 0; i < a->n && j < b->n; ) { + int cmp = strcmp(a->names[i], b->names[j]); + if (cmp < 0) { + if (a_only) { + svec_add(a_only, a->names[i]); + } + i++; + } else if (cmp > 0) { + if (b_only) { + svec_add(b_only, b->names[j]); + } + j++; + } else { + if (both) { + svec_add(both, a->names[i]); + } + i++; + j++; + } + } + if (a_only) { + for (; i < a->n; i++) { + svec_add(a_only, a->names[i]); + } + } + if (b_only) { + for (; j < b->n; j++) { + svec_add(b_only, b->names[j]); + } + } +} + +bool +svec_contains(const struct svec *svec, const char *name) +{ + return svec_find(svec, name) != SIZE_MAX; +} + +size_t +svec_find(const struct svec *svec, const char *name) +{ + char **p; + + assert(svec_is_sorted(svec)); + p = bsearch(&name, svec->names, svec->n, sizeof *svec->names, + compare_strings); + return p ? p - svec->names : SIZE_MAX; +} + +bool +svec_is_sorted(const struct svec *svec) +{ + size_t i; + + for (i = 1; i < svec->n; i++) { + if (strcmp(svec->names[i - 1], svec->names[i]) > 0) { + return false; + } + } + return true; +} + +bool +svec_is_unique(const struct svec *svec) +{ + return svec_get_duplicate(svec) == NULL; +} + +const char * +svec_get_duplicate(const struct svec *svec) +{ + assert(svec_is_sorted(svec)); + if (svec->n > 1) { + size_t i; + for (i = 1; i < svec->n; i++) { + if (!strcmp(svec->names[i - 1], svec->names[i])) { + return svec->names[i]; + } + } + } + return NULL; +} + +void +svec_swap(struct svec *a, struct svec *b) +{ + struct svec tmp = *a; + *a = *b; + *b = tmp; +} + +void +svec_print(const struct svec *svec, const char *title) +{ + size_t i; + + printf("%s:\n", title); + for (i = 0; i < svec->n; i++) { + printf("\"%s\"\n", svec->names[i]); + } +} + +/* Breaks 'words' into words at white space, respecting shell-like quoting + * conventions, and appends the words to 'svec'. */ +void +svec_parse_words(struct svec *svec, const char *words) +{ + struct ds word = DS_EMPTY_INITIALIZER; + const char *p, *q; + + for (p = words; *p != '\0'; p = q) { + int quote = 0; + + while (isspace((unsigned char) *p)) { + p++; + } + if (*p == '\0') { + break; + } + + ds_clear(&word); + for (q = p; *q != '\0'; q++) { + if (*q == quote) { + quote = 0; + } else if (*q == '\'' || *q == '"') { + quote = *q; + } else if (*q == '\\' && (!quote || quote == '"')) { + q++; + if (*q == '\0') { + VLOG_WARN("%s: ends in trailing backslash", words); + break; + } + ds_put_char(&word, *q); + } else if (isspace((unsigned char) *q) && !quote) { + q++; + break; + } else { + ds_put_char(&word, *q); + } + } + svec_add(svec, ds_cstr(&word)); + if (quote) { + VLOG_WARN("%s: word ends inside quoted string", words); + } + } + ds_destroy(&word); +} + +bool +svec_equal(const struct svec *a, const struct svec *b) +{ + size_t i; + + if (a->n != b->n) { + return false; + } + for (i = 0; i < a->n; i++) { + if (strcmp(a->names[i], b->names[i])) { + return false; + } + } + return true; +} + +char * +svec_join(const struct svec *svec, + const char *delimiter, const char *terminator) +{ + struct ds ds; + size_t i; + + ds_init(&ds); + for (i = 0; i < svec->n; i++) { + if (i) { + ds_put_cstr(&ds, delimiter); + } + ds_put_cstr(&ds, svec->names[i]); + } + ds_put_cstr(&ds, terminator); + return ds_cstr(&ds); +} + +const char * +svec_back(const struct svec *svec) +{ + assert(svec->n); + return svec->names[svec->n - 1]; +} + +void +svec_pop_back(struct svec *svec) +{ + assert(svec->n); + free(svec->names[--svec->n]); +} -- cgit v1.2.3