ovsdb/condition.c

   1 /* Copyright (c) 2009 Nicira Networks
   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
  56 static WARN_UNUSED_RESULT struct ovsdb_error *
  57 ovsdb_clause_from_json(const struct ovsdb_table_schema *ts,
  58                        const struct json *json,
  59                        const struct ovsdb_symbol_table *symtab,
  60                        struct ovsdb_clause *clause)
  61 {
  62     const struct json_array *array;
  63     struct ovsdb_error *error;
  64     const char *function_name;
  65     const char *column_name;
  66     struct ovsdb_type type;
  67
  68     if (json->type != JSON_ARRAY
  69         || json->u.array.n != 3
  70         || json->u.array.elems[0]->type != JSON_STRING
  71         || json->u.array.elems[1]->type != JSON_STRING) {
  72         return ovsdb_syntax_error(json, NULL, "Parse error in condition.");
  73     }
  74     array = json_array(json);
  75
  76     column_name = json_string(array->elems[0]);
  77     clause->column = ovsdb_table_schema_get_column(ts, column_name);
  78     if (!clause->column) {
  79         return ovsdb_syntax_error(json, "unknown column",
  80                                   "No column %s in table %s.",
  81                                   column_name, ts->name);
  82     }
  83     type = clause->column->type;
  84
  85     function_name = json_string(array->elems[1]);
  86     error = ovsdb_function_from_string(function_name, &clause->function);
  87     if (error) {
  88         return error;
  89     }
  90
  91     /* Type-check and relax restrictions on 'type' if appropriate.  */
  92     switch (clause->function) {
  93     case OVSDB_F_LT:
  94     case OVSDB_F_LE:
  95     case OVSDB_F_GT:
  96     case OVSDB_F_GE:
  97         /* XXX should we also allow these operators for types with n_min == 0,
  98          * n_max == 1?  (They would always be "false" if the value was
  99          * missing.) */
 100         if (!ovsdb_type_is_scalar(&type)
 101             || (type.key_type != OVSDB_TYPE_INTEGER
 102                 && type.key_type != OVSDB_TYPE_REAL)) {
 103             char *s = ovsdb_type_to_english(&type);
 104             error = ovsdb_syntax_error(
 105                 json, NULL, "Type mismatch: \"%s\" operator may not be "
 106                 "applied to column %s of type %s.",
 107                 ovsdb_function_to_string(clause->function),
 108                 clause->column->name, s);
 109             free(s);
 110             return error;
 111         }
 112         break;
 113
 114     case OVSDB_F_EQ:
 115     case OVSDB_F_NE:
 116         break;
 117
 118     case OVSDB_F_EXCLUDES:
 119         if (!ovsdb_type_is_scalar(&type)) {
 120             type.n_min = 0;
 121             type.n_max = UINT_MAX;
 122         }
 123         break;
 124
 125     case OVSDB_F_INCLUDES:
 126         if (!ovsdb_type_is_scalar(&type)) {
 127             type.n_min = 0;
 128         }
 129         break;
 130     }
 131     return ovsdb_datum_from_json(&clause->arg, &type, array->elems[2], symtab);
 132 }
 133
 134 static void
 135 ovsdb_clause_free(struct ovsdb_clause *clause)
 136 {
 137     ovsdb_datum_destroy(&clause->arg, &clause->column->type);
 138 }
 139
 140 static int
 141 compare_clauses_3way(const void *a_, const void *b_)
 142 {
 143     const struct ovsdb_clause *a = a_;
 144     const struct ovsdb_clause *b = b_;
 145
 146     if (a->function != b->function) {
 147         /* Bring functions to the front based on the fraction of table rows
 148          * that they are (heuristically) expected to leave in the query
 149          * results.  Note that "enum ovsdb_function" is intentionally ordered
 150          * to make this trivial. */
 151         return a->function < b->function ? -1 : 1;
 152     } else if (a->column->index != b->column->index) {
 153         if (a->column->index < OVSDB_N_STD_COLUMNS
 154             || b->column->index < OVSDB_N_STD_COLUMNS) {
 155             /* Bring the standard columns and in particular the UUID column
 156              * (since OVSDB_COL_UUID has value 0) to the front.  We have an
 157              * index on the UUID column, so that makes our queries cheaper. */
 158             return a->column->index < b->column->index ? -1 : 1;
 159         } else {
 160             /* Order clauses predictably to make testing easier. */
 161             return strcmp(a->column->name, b->column->name);
 162         }
 163     } else {
 164         return 0;
 165     }
 166 }
 167
 168 struct ovsdb_error *
 169 ovsdb_condition_from_json(const struct ovsdb_table_schema *ts,
 170                           const struct json *json,
 171                           const struct ovsdb_symbol_table *symtab,
 172                           struct ovsdb_condition *cnd)
 173 {
 174     const struct json_array *array = json_array(json);
 175     size_t i;
 176
 177     cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses);
 178     cnd->n_clauses = 0;
 179     for (i = 0; i < array->n; i++) {
 180         struct ovsdb_error *error;
 181         error = ovsdb_clause_from_json(ts, array->elems[i], symtab,
 182                                        &cnd->clauses[i]);
 183         if (error) {
 184             ovsdb_condition_destroy(cnd);
 185             cnd->clauses = NULL;
 186             cnd->n_clauses = 0;
 187             return error;
 188         }
 189         cnd->n_clauses++;
 190     }
 191
 192     /* A real database would have a query optimizer here. */
 193     qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses,
 194           compare_clauses_3way);
 195
 196     return NULL;
 197 }
 198
 199 static struct json *
 200 ovsdb_clause_to_json(const struct ovsdb_clause *clause)
 201 {
 202     return json_array_create_3(
 203         json_string_create(clause->column->name),
 204         json_string_create(ovsdb_function_to_string(clause->function)),
 205         ovsdb_datum_to_json(&clause->arg, &clause->column->type));
 206 }
 207
 208 struct json *
 209 ovsdb_condition_to_json(const struct ovsdb_condition *cnd)
 210 {
 211     struct json **clauses;
 212     size_t i;
 213
 214     clauses = xmalloc(cnd->n_clauses * sizeof *clauses);
 215     for (i = 0; i < cnd->n_clauses; i++) {
 216         clauses[i] = ovsdb_clause_to_json(&cnd->clauses[i]);
 217     }
 218     return json_array_create(clauses, cnd->n_clauses);
 219 }
 220
 221 bool
 222 ovsdb_condition_evaluate(const struct ovsdb_row *row,
 223                          const struct ovsdb_condition *cnd)
 224 {
 225     size_t i;
 226
 227     for (i = 0; i < cnd->n_clauses; i++) {
 228         const struct ovsdb_clause *c = &cnd->clauses[i];
 229         const struct ovsdb_datum *field = &row->fields[c->column->index];
 230         const struct ovsdb_datum *arg = &cnd->clauses[i].arg;
 231         const struct ovsdb_type *type = &c->column->type;
 232
 233         if (ovsdb_type_is_scalar(type)) {
 234             int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
 235                                               type->key_type);
 236             switch (c->function) {
 237             case OVSDB_F_LT:
 238                 return cmp < 0;
 239             case OVSDB_F_LE:
 240                 return cmp <= 0;
 241             case OVSDB_F_EQ:
 242             case OVSDB_F_INCLUDES:
 243                 return cmp == 0;
 244             case OVSDB_F_NE:
 245             case OVSDB_F_EXCLUDES:
 246                 return cmp != 0;
 247             case OVSDB_F_GE:
 248                 return cmp >= 0;
 249             case OVSDB_F_GT:
 250                 return cmp > 0;
 251             }
 252         } else {
 253             switch (c->function) {
 254             case OVSDB_F_EQ:
 255                 return ovsdb_datum_equals(field, arg, type);
 256             case OVSDB_F_NE:
 257                 return !ovsdb_datum_equals(field, arg, type);
 258             case OVSDB_F_INCLUDES:
 259                 return ovsdb_datum_includes_all(arg, field, type);
 260             case OVSDB_F_EXCLUDES:
 261                 return ovsdb_datum_excludes_all(arg, field, type);
 262             case OVSDB_F_LT:
 263             case OVSDB_F_LE:
 264             case OVSDB_F_GE:
 265             case OVSDB_F_GT:
 266                 NOT_REACHED();
 267             }
 268         }
 269         NOT_REACHED();
 270     }
 271
 272     return true;
 273 }
 274
 275 void
 276 ovsdb_condition_destroy(struct ovsdb_condition *cnd)
 277 {
 278     size_t i;
 279
 280     for (i = 0; i < cnd->n_clauses; i++) {
 281         ovsdb_clause_free(&cnd->clauses[i]);
 282     }
 283     free(cnd->clauses);
 284 }