summaryrefslogtreecommitdiff
path: root/lib/svec.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/svec.c')
-rw-r--r--lib/svec.c381
1 files changed, 381 insertions, 0 deletions
diff --git a/lib/svec.c b/lib/svec.c
new file mode 100644
index 000000000..4f8968d17
--- /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 <config.h>
+#include "svec.h"
+#include <assert.h>
+#include <ctype.h>
+#include <stdlib.h>
+#include <string.h>
+#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]);
+}
View Lorry Controller Status