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

diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c
index 46298cb4..65fd43e6 100644
--- a/lib/ovsdb-data.c
+++ b/lib/ovsdb-data.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2009 Nicira Networks
+/* Copyright (c) 2009, 2010 Nicira Networks
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -18,6 +18,7 @@
 #include "ovsdb-data.h"
 
 #include <assert.h>
+#include <limits.h>
 
 #include "hash.h"
 #include "ovsdb-error.h"
@@ -64,6 +65,35 @@ ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
     }
 }
 
+bool
+ovsdb_atom_is_default(const union ovsdb_atom *atom,
+                      enum ovsdb_atomic_type type)
+{
+    switch (type) {
+    case OVSDB_TYPE_VOID:
+        NOT_REACHED();
+
+    case OVSDB_TYPE_INTEGER:
+        return atom->integer == 0;
+
+    case OVSDB_TYPE_REAL:
+        return atom->real == 0.0;
+
+    case OVSDB_TYPE_BOOLEAN:
+        return atom->boolean == false;
+
+    case OVSDB_TYPE_STRING:
+        return atom->string[0] == '\0';
+
+    case OVSDB_TYPE_UUID:
+        return uuid_is_zero(&atom->uuid);
+
+    case OVSDB_N_TYPES:
+    default:
+        NOT_REACHED();
+    }
+}
+
 void
 ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
                  enum ovsdb_atomic_type type)
@@ -219,13 +249,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,
@@ -350,6 +380,28 @@ ovsdb_datum_init_default(struct ovsdb_datum *datum,
     datum->values = alloc_default_atoms(type->value_type, datum->n);
 }
 
+bool
+ovsdb_datum_is_default(const struct ovsdb_datum *datum,
+                       const struct ovsdb_type *type)
+{
+    size_t i;
+
+    if (datum->n != type->n_min) {
+        return false;
+    }
+    for (i = 0; i < datum->n; i++) {
+        if (!ovsdb_atom_is_default(&datum->keys[i], type->key_type)) {
+            return false;
+        }
+        if (type->value_type != OVSDB_TYPE_VOID
+            && !ovsdb_atom_is_default(&datum->values[i], type->value_type)) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
 static union ovsdb_atom *
 clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
 {
@@ -433,7 +485,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 +706,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 +744,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 +760,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 +869,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 +878,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 +887,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);
 }