ovsdb/condition.c

   1 /* Copyright (c) 2009, 2010, 2011 Nicira, Inc.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "condition.h"
  19
  20 #include <limits.h>
  21
  22 #include "column.h"
  23 #include "json.h"
  24 #include "ovsdb-error.h"
  25 #include "row.h"
  26 #include "table.h"
  27
  28 struct ovsdb_error *
  29 ovsdb_function_from_string(const char *name, enum ovsdb_function *function)
  30 {
  31 #define OVSDB_FUNCTION(ENUM, NAME)              \
  32     if (!strcmp(name, NAME)) {                  \
  33         *function = ENUM;                       \
  34         return NULL;                            \
  35     }
  36     OVSDB_FUNCTIONS;
  37 #undef OVSDB_FUNCTION
  38
  39     return ovsdb_syntax_error(NULL, "unknown function",
  40                               "No function named %s.", name);
  41 }
  42
  43 const char *
  44 ovsdb_function_to_string(enum ovsdb_function function)
  45 {
  46     switch (function) {
  47 #define OVSDB_FUNCTION(ENUM, NAME) case ENUM: return NAME;
  48         OVSDB_FUNCTIONS;
  49 #undef OVSDB_FUNCTION
  50     }
  51
  52     return NULL;
  53 }
  54
  55 static WARN_UNUSED_RESULT struct ovsdb_error *
  56 ovsdb_clause_from_json(const struct ovsdb_table_schema *ts,
  57                        const struct json *json,
  58                        struct ovsdb_symbol_table *symtab,
  59                        struct ovsdb_clause *clause)
  60 {
  61     const struct json_array *array;
  62     struct ovsdb_error *error;
  63     const char *function_name;
  64     const char *column_name;
  65     struct ovsdb_type type;
  66
  67     if (json->type != JSON_ARRAY
  68         || json->u.array.n != 3
  69         || json->u.array.elems[0]->type != JSON_STRING
  70         || json->u.array.elems[1]->type != JSON_STRING) {
  71         return ovsdb_syntax_error(json, NULL, "Parse error in condition.");
  72     }
  73     array = json_array(json);
  74
  75     column_name = json_string(array->elems[0]);
  76     clause->column = ovsdb_table_schema_get_column(ts, column_name);
  77     if (!clause->column) {
  78         return ovsdb_syntax_error(json, "unknown column",
  79                                   "No column %s in table %s.",
  80                                   column_name, ts->name);
  81     }
  82     type = clause->column->type;
  83
  84     function_name = json_string(array->elems[1]);
  85     error = ovsdb_function_from_string(function_name, &clause->function);
  86     if (error) {
  87         return error;
  88     }
  89
  90     /* Type-check and relax restrictions on 'type' if appropriate.  */
  91     switch (clause->function) {
  92     case OVSDB_F_LT:
  93     case OVSDB_F_LE:
  94     case OVSDB_F_GT:
  95     case OVSDB_F_GE:
  96         /* XXX should we also allow these operators for types with n_min == 0,
  97          * n_max == 1?  (They would always be "false" if the value was
  98          * missing.) */
  99         if (!ovsdb_type_is_scalar(&type)
 100             || (type.key.type != OVSDB_TYPE_INTEGER
 101                 && type.key.type != OVSDB_TYPE_REAL)) {
 102             char *s = ovsdb_type_to_english(&type);
 103             error = ovsdb_syntax_error(
 104                 json, NULL, "Type mismatch: \"%s\" operator may not be "
 105                 "applied to column %s of type %s.",
 106                 ovsdb_function_to_string(clause->function),
 107                 clause->column->name, s);
 108             free(s);
 109             return error;
 110         }
 111         break;
 112
 113     case OVSDB_F_EQ:
 114     case OVSDB_F_NE:
 115         break;
 116
 117     case OVSDB_F_EXCLUDES:
 118         if (!ovsdb_type_is_scalar(&type)) {
 119             type.n_min = 0;
 120             type.n_max = UINT_MAX;
 121         }
 122         break;
 123
 124     case OVSDB_F_INCLUDES:
 125         if (!ovsdb_type_is_scalar(&type)) {
 126             type.n_min = 0;
 127         }
 128         break;
 129     }
 130     return ovsdb_datum_from_json(&clause->arg, &type, array->elems[2], symtab);
 131 }
 132
 133 static void
 134 ovsdb_clause_free(struct ovsdb_clause *clause)
 135 {
 136     ovsdb_datum_destroy(&clause->arg, &clause->column->type);
 137 }
 138
 139 static int
 140 compare_clauses_3way(const void *a_, const void *b_)
 141 {
 142     const struct ovsdb_clause *a = a_;
 143     const struct ovsdb_clause *b = b_;
 144
 145     if (a->function != b->function) {
 146         /* Bring functions to the front based on the fraction of table rows
 147          * that they are (heuristically) expected to leave in the query
 148          * results.  Note that "enum ovsdb_function" is intentionally ordered
 149          * to make this trivial. */
 150         return a->function < b->function ? -1 : 1;
 151     } else if (a->column->index != b->column->index) {
 152         if (a->column->index < OVSDB_N_STD_COLUMNS
 153             || b->column->index < OVSDB_N_STD_COLUMNS) {
 154             /* Bring the standard columns and in particular the UUID column
 155              * (since OVSDB_COL_UUID has value 0) to the front.  We have an
 156              * index on the UUID column, so that makes our queries cheaper. */
 157             return a->column->index < b->column->index ? -1 : 1;
 158         } else {
 159             /* Order clauses predictably to make testing easier. */
 160             return strcmp(a->column->name, b->column->name);
 161         }
 162     } else {
 163         return 0;
 164     }
 165 }
 166
 167 struct ovsdb_error *
 168 ovsdb_condition_from_json(const struct ovsdb_table_schema *ts,
 169                           const struct json *json,
 170                           struct ovsdb_symbol_table *symtab,
 171                           struct ovsdb_condition *cnd)
 172 {
 173     const struct json_array *array = json_array(json);
 174     size_t i;
 175
 176     cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses);
 177     cnd->n_clauses = 0;
 178     for (i = 0; i < array->n; i++) {
 179         struct ovsdb_error *error;
 180         error = ovsdb_clause_from_json(ts, array->elems[i], symtab,
 181                                        &cnd->clauses[i]);
 182         if (error) {
 183             ovsdb_condition_destroy(cnd);
 184             cnd->clauses = NULL;
 185             cnd->n_clauses = 0;
 186             return error;
 187         }
 188         cnd->n_clauses++;
 189     }
 190
 191     /* A real database would have a query optimizer here. */
 192     qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses,
 193           compare_clauses_3way);
 194
 195     return NULL;
 196 }
 197
 198 static struct json *
 199 ovsdb_clause_to_json(const struct ovsdb_clause *clause)
 200 {
 201     return json_array_create_3(
 202         json_string_create(clause->column->name),
 203         json_string_create(ovsdb_function_to_string(clause->function)),
 204         ovsdb_datum_to_json(&clause->arg, &clause->column->type));
 205 }
 206
 207 struct json *
 208 ovsdb_condition_to_json(const struct ovsdb_condition *cnd)
 209 {
 210     struct json **clauses;
 211     size_t i;
 212
 213     clauses = xmalloc(cnd->n_clauses * sizeof *clauses);
 214     for (i = 0; i < cnd->n_clauses; i++) {
 215         clauses[i] = ovsdb_clause_to_json(&cnd->clauses[i]);
 216     }
 217     return json_array_create(clauses, cnd->n_clauses);
 218 }
 219
 220 static bool
 221 ovsdb_clause_evaluate(const struct ovsdb_row *row,
 222                       const struct ovsdb_clause *c)
 223 {
 224     const struct ovsdb_datum *field = &row->fields[c->column->index];
 225     const struct ovsdb_datum *arg = &c->arg;
 226     const struct ovsdb_type *type = &c->column->type;
 227
 228     if (ovsdb_type_is_scalar(type)) {
 229         int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
 230                                           type->key.type);
 231         switch (c->function) {
 232         case OVSDB_F_LT:
 233             return cmp < 0;
 234         case OVSDB_F_LE:
 235             return cmp <= 0;
 236         case OVSDB_F_EQ:
 237         case OVSDB_F_INCLUDES:
 238             return cmp == 0;
 239         case OVSDB_F_NE:
 240         case OVSDB_F_EXCLUDES:
 241             return cmp != 0;
 242         case OVSDB_F_GE:
 243             return cmp >= 0;
 244         case OVSDB_F_GT:
 245             return cmp > 0;
 246         }
 247     } else {
 248         switch (c->function) {
 249         case OVSDB_F_EQ:
 250             return ovsdb_datum_equals(field, arg, type);
 251         case OVSDB_F_NE:
 252             return !ovsdb_datum_equals(field, arg, type);
 253         case OVSDB_F_INCLUDES:
 254             return ovsdb_datum_includes_all(arg, field, type);
 255         case OVSDB_F_EXCLUDES:
 256             return ovsdb_datum_excludes_all(arg, field, type);
 257         case OVSDB_F_LT:
 258         case OVSDB_F_LE:
 259         case OVSDB_F_GE:
 260         case OVSDB_F_GT:
 261             NOT_REACHED();
 262         }
 263     }
 264
 265     NOT_REACHED();
 266 }
 267
 268 bool
 269 ovsdb_condition_evaluate(const struct ovsdb_row *row,
 270                          const struct ovsdb_condition *cnd)
 271 {
 272     size_t i;
 273
 274     for (i = 0; i < cnd->n_clauses; i++) {
 275         if (!ovsdb_clause_evaluate(row, &cnd->clauses[i])) {
 276             return false;
 277         }
 278     }
 279
 280     return true;
 281 }
 282
 283 void
 284 ovsdb_condition_destroy(struct ovsdb_condition *cnd)
 285 {
 286     size_t i;
 287
 288     for (i = 0; i < cnd->n_clauses; i++) {
 289         ovsdb_clause_free(&cnd->clauses[i]);
 290     }
 291     free(cnd->clauses);
 292 }