X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=lib%2Fovsdb-data.c;h=0d7749b17fc3912606128384c781d250e32212ee;hb=fe55ad159d8fd396a9e4914a03eea93d096d03b1;hp=46298cb47694c2ae662b738b3df311c59112b998;hpb=f85f8ebbfac946c19b3c6eb0f4170f579d0a4d25;p=openvswitch

diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c
index 46298cb4..0d7749b1 100644
--- a/lib/ovsdb-data.c
+++ b/lib/ovsdb-data.c
@@ -18,6 +18,7 @@
 #include "ovsdb-data.h"
 
 #include <assert.h>
+#include <limits.h>
 
 #include "hash.h"
 #include "ovsdb-error.h"
@@ -219,13 +220,13 @@ ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
         error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
         if (!error1) {
             const char *name = json_string(value);
-            const struct uuid *named_uuid;
+            const struct ovsdb_symbol *symbol;
 
             ovsdb_error_destroy(error0);
 
-            named_uuid = ovsdb_symbol_table_get(symtab, name);
-            if (named_uuid) {
-                *uuid = *named_uuid;
+            symbol = ovsdb_symbol_table_get(symtab, name);
+            if (symbol) {
+                *uuid = symbol->uuid;
                 return NULL;
             } else {
                 return ovsdb_syntax_error(json, NULL,
@@ -433,7 +434,7 @@ ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
     }
 }
 
-static struct ovsdb_error *
+struct ovsdb_error *
 ovsdb_datum_sort(struct ovsdb_datum *datum, const struct ovsdb_type *type)
 {
     if (datum->n < 2) {
@@ -654,27 +655,33 @@ ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
                                        a->n));
 }
 
-static bool
-ovsdb_datum_contains(const struct ovsdb_datum *a, int i,
-                     const struct ovsdb_datum *b,
-                     const struct ovsdb_type *type)
+/* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
+ * UINT_MAX.  'type' must be the type of 'a' and 'b', except that
+ * type->value_type may be set to OVSDB_TYPE_VOID to compare keys but not
+ * values. */
+static unsigned int
+ovsdb_datum_find(const struct ovsdb_datum *a, int i,
+                 const struct ovsdb_datum *b,
+                 const struct ovsdb_type *type)
 {
     int low = 0;
     int high = b->n;
     while (low < high) {
         int j = (low + high) / 2;
-        int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j], type->key_type);
+        int cmp = ovsdb_atom_compare_3way(&a->keys[i], &b->keys[j],
+                                          type->key_type);
         if (cmp < 0) {
             high = j;
         } else if (cmp > 0) {
             low = j + 1;
         } else {
-            return (type->value_type == OVSDB_TYPE_VOID
-                    || ovsdb_atom_equals(&a->values[i], &b->values[j],
-                                         type->value_type));
+            bool eq_value = (type->value_type == OVSDB_TYPE_VOID
+                             || ovsdb_atom_equals(&a->values[i], &b->values[j],
+                                                  type->value_type));
+            return eq_value ? j : UINT_MAX;
         }
     }
-    return false;
+    return UINT_MAX;
 }
 
 /* Returns true if every element in 'a' is also in 'b', false otherwise. */
@@ -686,7 +693,7 @@ ovsdb_datum_includes_all(const struct ovsdb_datum *a,
     size_t i;
 
     for (i = 0; i < a->n; i++) {
-        if (!ovsdb_datum_contains(a, i, b, type)) {
+        if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
             return false;
         }
     }
@@ -702,12 +709,95 @@ ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
     size_t i;
 
     for (i = 0; i < a->n; i++) {
-        if (ovsdb_datum_contains(a, i, b, type)) {
+        if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
             return false;
         }
     }
     return true;
 }
+
+static void
+ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
+                       unsigned int capacity)
+{
+    a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
+    if (type->value_type != OVSDB_TYPE_VOID) {
+        a->values = xrealloc(a->values, capacity * sizeof *a->values);
+    }
+}
+
+static void
+ovsdb_datum_remove(struct ovsdb_datum *a, size_t i,
+                   const struct ovsdb_type *type)
+{
+    ovsdb_atom_destroy(&a->keys[i], type->key_type);
+    a->keys[i] = a->keys[a->n - 1];
+    if (type->value_type != OVSDB_TYPE_VOID) {
+        ovsdb_atom_destroy(&a->values[i], type->value_type);
+        a->values[i] = a->values[a->n - 1];
+    }
+    a->n--;
+}
+
+void
+ovsdb_datum_union(struct ovsdb_datum *a,
+                  const struct ovsdb_datum *b, const struct ovsdb_type *type)
+{
+    struct ovsdb_type type_without_value;
+    unsigned int n;
+    size_t i;
+
+    type_without_value = *type;
+    type_without_value.value_type = OVSDB_TYPE_VOID;
+    n = a->n;
+    for (i = 0; i < b->n; i++) {
+        if (ovsdb_datum_find(b, i, a, &type_without_value) == UINT_MAX) {
+            if (n == a->n) {
+                ovsdb_datum_reallocate(a, type, a->n + (b->n - i));
+            }
+            ovsdb_atom_clone(&a->keys[n], &b->keys[i], type->key_type);
+            if (type->value_type != OVSDB_TYPE_VOID) {
+                ovsdb_atom_clone(&a->values[n], &b->values[i],
+                                 type->value_type);
+            }
+            n++;
+        }
+    }
+    if (n != a->n) {
+        struct ovsdb_error *error;
+        a->n = n;
+        error = ovsdb_datum_sort(a, type);
+        assert(!error);
+    }
+}
+
+void
+ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
+                     const struct ovsdb_datum *b,
+                     const struct ovsdb_type *b_type)
+{
+    bool changed = false;
+    size_t i;
+
+    assert(a_type->key_type == b_type->key_type);
+    assert(a_type->value_type == b_type->value_type
+           || b_type->value_type == OVSDB_TYPE_VOID);
+
+    /* XXX The big-O of this could easily be improved. */
+    for (i = 0; i < a->n; ) {
+        unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
+        if (idx != UINT_MAX) {
+            changed = true;
+            ovsdb_datum_remove(a, i, a_type);
+        } else {
+            i++;
+        }
+    }
+    if (changed) {
+        struct ovsdb_error *error = ovsdb_datum_sort(a, a_type);
+        assert(!error);
+    }
+}
 
 struct ovsdb_symbol_table {
     struct shash sh;
@@ -728,7 +818,8 @@ ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
         struct shash_node *node, *next;
 
         SHASH_FOR_EACH_SAFE (node, next, &symtab->sh) {
-            free(node->data);
+            struct ovsdb_symbol *symbol = node->data;
+            free(symbol);
             shash_delete(&symtab->sh, node);
         }
         shash_destroy(&symtab->sh);
@@ -736,7 +827,7 @@ ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
     }
 }
 
-const struct uuid *
+struct ovsdb_symbol *
 ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
                        const char *name)
 {
@@ -745,12 +836,13 @@ ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
 
 void
 ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
-                       const struct uuid *uuid)
+                       const struct uuid *uuid, bool used)
 {
-    struct uuid *entry = shash_find_data(&symtab->sh, name);
-    if (!entry) {
-        shash_add(&symtab->sh, name, xmemdup(uuid, sizeof *uuid));
-    } else {
-        *entry = *uuid;
-    }
+    struct ovsdb_symbol *symbol;
+
+    assert(!ovsdb_symbol_table_get(symtab, name));
+    symbol = xmalloc(sizeof *symbol);
+    symbol->uuid = *uuid;
+    symbol->used = used;
+    shash_add(&symtab->sh, name, symbol);
 }