Initial implementation of OVSDB.

1 files changed, 284 insertions, 0 deletions

diff --git a/ovsdb/condition.c b/ovsdb/condition.c
new file mode 100644
index 000000000..0342b8e89
--- /dev/null
+++ b/ovsdb/condition.c
@@ -0,0 +1,284 @@
+/* Copyright (c) 2009 Nicira Networks
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include "condition.h"
+
+#include <limits.h>
+
+#include "column.h"
+#include "json.h"
+#include "ovsdb-error.h"
+#include "row.h"
+#include "table.h"
+
+struct ovsdb_error *
+ovsdb_function_from_string(const char *name, enum ovsdb_function *function)
+{
+#define OVSDB_FUNCTION(ENUM, NAME)              \
+    if (!strcmp(name, NAME)) {                  \
+        *function = ENUM;                       \
+        return NULL;                            \
+    }
+    OVSDB_FUNCTIONS;
+#undef OVSDB_FUNCTION
+
+    return ovsdb_syntax_error(NULL, "unknown function",
+                              "No function named %s.", name);
+}
+
+const char *
+ovsdb_function_to_string(enum ovsdb_function function)
+{
+    switch (function) {
+#define OVSDB_FUNCTION(ENUM, NAME) case ENUM: return NAME;
+        OVSDB_FUNCTIONS;
+#undef OVSDB_FUNCTION
+    }
+
+    return NULL;
+}
+
+
+static WARN_UNUSED_RESULT struct ovsdb_error *
+ovsdb_clause_from_json(const struct ovsdb_table_schema *ts,
+                       const struct json *json,
+                       const struct ovsdb_symbol_table *symtab,
+                       struct ovsdb_clause *clause)
+{
+    const struct json_array *array;
+    struct ovsdb_error *error;
+    const char *function_name;
+    const char *column_name;
+    struct ovsdb_type type;
+
+    if (json->type != JSON_ARRAY
+        || json->u.array.n != 3
+        || json->u.array.elems[0]->type != JSON_STRING
+        || json->u.array.elems[1]->type != JSON_STRING) {
+        return ovsdb_syntax_error(json, NULL, "Parse error in condition.");
+    }
+    array = json_array(json);
+
+    column_name = json_string(array->elems[0]);
+    clause->column = ovsdb_table_schema_get_column(ts, column_name);
+    if (!clause->column) {
+        return ovsdb_syntax_error(json, "unknown column",
+                                  "No column %s in table %s.",
+                                  column_name, ts->name);
+    }
+    type = clause->column->type;
+
+    function_name = json_string(array->elems[1]);
+    error = ovsdb_function_from_string(function_name, &clause->function);
+    if (error) {
+        return error;
+    }
+
+    /* Type-check and relax restrictions on 'type' if appropriate.  */
+    switch (clause->function) {
+    case OVSDB_F_LT:
+    case OVSDB_F_LE:
+    case OVSDB_F_GT:
+    case OVSDB_F_GE:
+        /* XXX should we also allow these operators for types with n_min == 0,
+         * n_max == 1?  (They would always be "false" if the value was
+         * missing.) */
+        if (!ovsdb_type_is_scalar(&type)
+            || (type.key_type != OVSDB_TYPE_INTEGER
+                && type.key_type != OVSDB_TYPE_REAL)) {
+            char *s = ovsdb_type_to_english(&type);
+            error = ovsdb_syntax_error(
+                json, NULL, "Type mismatch: \"%s\" operator may not be "
+                "applied to column %s of type %s.",
+                ovsdb_function_to_string(clause->function),
+                clause->column->name, s);
+            free(s);
+            return error;
+        }
+        break;
+
+    case OVSDB_F_EQ:
+    case OVSDB_F_NE:
+        break;
+
+    case OVSDB_F_EXCLUDES:
+        if (!ovsdb_type_is_scalar(&type)) {
+            type.n_min = 0;
+            type.n_max = UINT_MAX;
+        }
+        break;
+
+    case OVSDB_F_INCLUDES:
+        if (!ovsdb_type_is_scalar(&type)) {
+            type.n_min = 0;
+        }
+        break;
+    }
+    return ovsdb_datum_from_json(&clause->arg, &type, array->elems[2], symtab);
+}
+
+static void
+ovsdb_clause_free(struct ovsdb_clause *clause)
+{
+    ovsdb_datum_destroy(&clause->arg, &clause->column->type);
+}
+
+static int
+compare_clauses_3way(const void *a_, const void *b_)
+{
+    const struct ovsdb_clause *a = a_;
+    const struct ovsdb_clause *b = b_;
+
+    if (a->function != b->function) {
+        /* Bring functions to the front based on the fraction of table rows
+         * that they are (heuristically) expected to leave in the query
+         * results.  Note that "enum ovsdb_function" is intentionally ordered
+         * to make this trivial. */
+        return a->function < b->function ? -1 : 1;
+    } else if (a->column->index != b->column->index) {
+        if (a->column->index < OVSDB_N_STD_COLUMNS
+            || b->column->index < OVSDB_N_STD_COLUMNS) {
+            /* Bring the standard columns and in particular the UUID column
+             * (since OVSDB_COL_UUID has value 0) to the front.  We have an
+             * index on the UUID column, so that makes our queries cheaper. */
+            return a->column->index < b->column->index ? -1 : 1;
+        } else {
+            /* Order clauses predictably to make testing easier. */
+            return strcmp(a->column->name, b->column->name);
+        }
+    } else {
+        return 0;
+    }
+}
+
+struct ovsdb_error *
+ovsdb_condition_from_json(const struct ovsdb_table_schema *ts,
+                          const struct json *json,
+                          const struct ovsdb_symbol_table *symtab,
+                          struct ovsdb_condition *cnd)
+{
+    const struct json_array *array = json_array(json);
+    size_t i;
+
+    cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses);
+    cnd->n_clauses = 0;
+    for (i = 0; i < array->n; i++) {
+        struct ovsdb_error *error;
+        error = ovsdb_clause_from_json(ts, array->elems[i], symtab,
+                                       &cnd->clauses[i]);
+        if (error) {
+            ovsdb_condition_destroy(cnd);
+            cnd->clauses = NULL;
+            cnd->n_clauses = 0;
+            return error;
+        }
+        cnd->n_clauses++;
+    }
+
+    /* A real database would have a query optimizer here. */
+    qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses,
+          compare_clauses_3way);
+
+    return NULL;
+}
+
+static struct json *
+ovsdb_clause_to_json(const struct ovsdb_clause *clause)
+{
+    return json_array_create_3(
+        json_string_create(clause->column->name),
+        json_string_create(ovsdb_function_to_string(clause->function)),
+        ovsdb_datum_to_json(&clause->arg, &clause->column->type));
+}
+
+struct json *
+ovsdb_condition_to_json(const struct ovsdb_condition *cnd)
+{
+    struct json **clauses;
+    size_t i;
+
+    clauses = xmalloc(cnd->n_clauses * sizeof *clauses);
+    for (i = 0; i < cnd->n_clauses; i++) {
+        clauses[i] = ovsdb_clause_to_json(&cnd->clauses[i]);
+    }
+    return json_array_create(clauses, cnd->n_clauses);
+}
+
+bool
+ovsdb_condition_evaluate(const struct ovsdb_row *row,
+                         const struct ovsdb_condition *cnd)
+{
+    size_t i;
+
+    for (i = 0; i < cnd->n_clauses; i++) {
+        const struct ovsdb_clause *c = &cnd->clauses[i];
+        const struct ovsdb_datum *field = &row->fields[c->column->index];
+        const struct ovsdb_datum *arg = &cnd->clauses[i].arg;
+        const struct ovsdb_type *type = &c->column->type;
+
+        if (ovsdb_type_is_scalar(type)) {
+            int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
+                                              type->key_type);
+            switch (c->function) {
+            case OVSDB_F_LT:
+                return cmp < 0;
+            case OVSDB_F_LE:
+                return cmp <= 0;
+            case OVSDB_F_EQ:
+            case OVSDB_F_INCLUDES:
+                return cmp == 0;
+            case OVSDB_F_NE:
+            case OVSDB_F_EXCLUDES:
+                return cmp != 0;
+            case OVSDB_F_GE:
+                return cmp >= 0;
+            case OVSDB_F_GT:
+                return cmp > 0;
+            }
+        } else {
+            switch (c->function) {
+            case OVSDB_F_EQ:
+                return ovsdb_datum_equals(field, arg, type);
+            case OVSDB_F_NE:
+                return !ovsdb_datum_equals(field, arg, type);
+            case OVSDB_F_INCLUDES:
+                return ovsdb_datum_includes_all(arg, field, type);
+            case OVSDB_F_EXCLUDES:
+                return ovsdb_datum_excludes_all(arg, field, type);
+            case OVSDB_F_LT:
+            case OVSDB_F_LE:
+            case OVSDB_F_GE:
+            case OVSDB_F_GT:
+                NOT_REACHED();
+            }
+        }
+        NOT_REACHED();
+    }
+
+    return true;
+}
+
+void
+ovsdb_condition_destroy(struct ovsdb_condition *cnd)
+{
+    size_t i;
+
+    for (i = 0; i < cnd->n_clauses; i++) {
+        ovsdb_clause_free(&cnd->clauses[i]);
+    }
+    free(cnd->clauses);
+}