1 /* Copyright (c) 2009, 2010, 2011 Nicira, Inc.
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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "condition.h"
23 #include "openvswitch/json.h"
24 #include "ovsdb-error.h"
33 ovsdb_function_from_string(const char *name, enum ovsdb_function *function)
35 #define OVSDB_FUNCTION(ENUM, NAME) \
36 if (!strcmp(name, NAME)) { \
43 return ovsdb_syntax_error(NULL, "unknown function",
44 "No function named %s.", name);
48 ovsdb_function_to_string(enum ovsdb_function function)
51 #define OVSDB_FUNCTION(ENUM, NAME) case ENUM: return NAME;
59 static struct ovsdb_error *
60 ovsdb_clause_from_json(const struct ovsdb_table_schema *ts,
61 const struct json *json,
62 struct ovsdb_symbol_table *symtab,
63 struct ovsdb_clause *clause)
65 const struct json_array *array;
66 struct ovsdb_error *error;
67 const char *function_name;
68 const char *column_name;
69 struct ovsdb_type type;
71 if (json->type == JSON_TRUE || json->type == JSON_FALSE) {
73 json->type == JSON_TRUE ? OVSDB_F_TRUE : OVSDB_F_FALSE;
75 /* Column and arg fields are not being used with boolean functions.
77 clause->column = ovsdb_table_schema_get_column(ts, "_uuid");
78 clause->index = clause->column->index;
79 ovsdb_datum_init_default(&clause->arg, &clause->column->type);
83 if (json->type != JSON_ARRAY
84 || json->u.array.n != 3
85 || json->u.array.elems[0]->type != JSON_STRING
86 || json->u.array.elems[1]->type != JSON_STRING) {
87 return ovsdb_syntax_error(json, NULL, "Parse error in condition.");
89 array = json_array(json);
91 column_name = json_string(array->elems[0]);
92 clause->column = ovsdb_table_schema_get_column(ts, column_name);
93 if (!clause->column) {
94 return ovsdb_syntax_error(json, "unknown column",
95 "No column %s in table %s.",
96 column_name, ts->name);
98 clause->index = clause->column->index;
99 type = clause->column->type;
101 function_name = json_string(array->elems[1]);
102 error = ovsdb_function_from_string(function_name, &clause->function);
107 /* Type-check and relax restrictions on 'type' if appropriate. */
108 switch (clause->function) {
113 /* Allow these operators for types with n_min == 0, n_max == 1.
114 * (They will always be "false" if the value is missing.) */
115 if (!(ovsdb_type_is_scalar(&type)
116 || ovsdb_type_is_optional_scalar(&type))
117 || (type.key.type != OVSDB_TYPE_INTEGER
118 && type.key.type != OVSDB_TYPE_REAL)) {
119 char *s = ovsdb_type_to_english(&type);
120 error = ovsdb_syntax_error(
121 json, NULL, "Type mismatch: \"%s\" operator may not be "
122 "applied to column %s of type %s.",
123 ovsdb_function_to_string(clause->function),
124 clause->column->name, s);
133 case OVSDB_F_EXCLUDES:
134 if (!ovsdb_type_is_scalar(&type)) {
136 type.n_max = UINT_MAX;
140 case OVSDB_F_INCLUDES:
141 if (!ovsdb_type_is_scalar(&type)) {
149 return ovsdb_datum_from_json(&clause->arg, &type, array->elems[2], symtab);
153 ovsdb_clause_free(struct ovsdb_clause *clause)
155 ovsdb_datum_destroy(&clause->arg, &clause->column->type);
159 compare_clauses_3way(const void *a_, const void *b_)
161 const struct ovsdb_clause *a = a_;
162 const struct ovsdb_clause *b = b_;
164 if (a->function != b->function) {
165 /* Bring functions to the front based on the fraction of table rows
166 * that they are (heuristically) expected to leave in the query
167 * results. Note that "enum ovsdb_function" is intentionally ordered
168 * to make this trivial. */
169 return a->function < b->function ? -1 : 1;
170 } else if (a->column->index != b->column->index) {
171 if (a->column->index < OVSDB_N_STD_COLUMNS
172 || b->column->index < OVSDB_N_STD_COLUMNS) {
173 /* Bring the standard columns and in particular the UUID column
174 * (since OVSDB_COL_UUID has value 0) to the front. We have an
175 * index on the UUID column, so that makes our queries cheaper. */
176 return a->column->index < b->column->index ? -1 : 1;
178 /* Order clauses predictably to make testing easier. */
179 return strcmp(a->column->name, b->column->name);
187 compare_clauses_3way_with_data(const void *a_, const void *b_)
189 const struct ovsdb_clause *a = a_;
190 const struct ovsdb_clause *b = b_;
193 res = compare_clauses_3way(a, b);
194 return res ? res : ovsdb_datum_compare_3way(&a->arg,
199 struct ovsdb_o_column {
200 const struct ovsdb_column *column;
201 struct hmap o_clauses;
204 struct ovsdb_o_clause {
205 struct ovsdb_datum *arg;
206 struct hmap_node hmap_node;
210 ovsdb_condition_optimize(struct ovsdb_condition *cnd)
215 if (!cnd->optimized) {
219 for(i = 0; i < cnd->n_clauses; i++) {
220 struct ovsdb_clause *clause = &cnd->clauses[i];
222 if (clause->function != OVSDB_F_EQ) {
226 struct ovsdb_o_clause *o_clause = xzalloc(sizeof *o_clause);
227 struct ovsdb_o_column *o_column =
228 shash_find_data(&cnd->o_columns, clause->column->name);
231 o_column = xzalloc(sizeof *o_column);
232 o_column->column = clause->column;
233 hmap_init(&o_column->o_clauses);
234 shash_add(&cnd->o_columns, clause->column->name, o_column);
236 o_clause->arg = &clause->arg;
237 hash = ovsdb_datum_hash(&clause->arg, &clause->column->type, 0);
238 hmap_insert(&o_column->o_clauses, &o_clause->hmap_node, hash);
243 ovsdb_condition_optimize_destroy(struct ovsdb_condition *cnd)
245 struct shash_node *node, *next;
247 SHASH_FOR_EACH_SAFE (node, next, &cnd->o_columns) {
248 struct ovsdb_o_column *o_column = node->data;
249 struct ovsdb_o_clause *c, *c_next;
251 HMAP_FOR_EACH_SAFE(c, c_next, hmap_node, &o_column->o_clauses) {
252 hmap_remove(&o_column->o_clauses, &c->hmap_node);
255 hmap_destroy(&o_column->o_clauses);
256 shash_delete(&cnd->o_columns, node);
259 shash_destroy(&cnd->o_columns);
263 ovsdb_condition_from_json(const struct ovsdb_table_schema *ts,
264 const struct json *json,
265 struct ovsdb_symbol_table *symtab,
266 struct ovsdb_condition *cnd)
268 const struct json_array *array = json_array(json);
271 ovsdb_condition_init(cnd);
272 cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses);
274 for (i = 0; i < array->n; i++) {
275 struct ovsdb_error *error;
276 error = ovsdb_clause_from_json(ts, array->elems[i], symtab,
279 ovsdb_condition_destroy(cnd);
285 if (cnd->clauses[i].function > OVSDB_F_EQ) {
286 cnd->optimized = false;
290 /* A real database would have a query optimizer here. */
291 qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses,
292 compare_clauses_3way_with_data);
294 ovsdb_condition_optimize(cnd);
300 ovsdb_clause_to_json(const struct ovsdb_clause *clause)
302 if (clause->function != OVSDB_F_TRUE &&
303 clause->function != OVSDB_F_FALSE) {
304 return json_array_create_3(
305 json_string_create(clause->column->name),
306 json_string_create(ovsdb_function_to_string(clause->function)),
307 ovsdb_datum_to_json(&clause->arg, &clause->column->type));
310 return json_boolean_create(clause->function == OVSDB_F_TRUE);
314 ovsdb_condition_to_json(const struct ovsdb_condition *cnd)
316 struct json **clauses;
319 clauses = xmalloc(cnd->n_clauses * sizeof *clauses);
320 for (i = 0; i < cnd->n_clauses; i++) {
321 clauses[i] = ovsdb_clause_to_json(&cnd->clauses[i]);
323 return json_array_create(clauses, cnd->n_clauses);
327 ovsdb_clause_evaluate(const struct ovsdb_datum *fields,
328 const struct ovsdb_clause *c,
329 unsigned int index_map[])
331 const struct ovsdb_datum *field = &fields[index_map ?
332 index_map[c->column->index] :
334 const struct ovsdb_datum *arg = &c->arg;
335 const struct ovsdb_type *type = &c->column->type;
337 if (c->function == OVSDB_F_TRUE ||
338 c->function == OVSDB_F_FALSE) {
339 return c->function == OVSDB_F_TRUE;
341 if (ovsdb_type_is_optional_scalar(type) && field->n == 0) {
342 switch (c->function) {
348 case OVSDB_F_INCLUDES:
351 case OVSDB_F_EXCLUDES:
357 } else if (ovsdb_type_is_scalar(type)
358 || ovsdb_type_is_optional_scalar(type)) {
359 int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
361 switch (c->function) {
367 case OVSDB_F_INCLUDES:
370 case OVSDB_F_EXCLUDES:
381 switch (c->function) {
383 return ovsdb_datum_equals(field, arg, type);
385 return !ovsdb_datum_equals(field, arg, type);
386 case OVSDB_F_INCLUDES:
387 return ovsdb_datum_includes_all(arg, field, type);
388 case OVSDB_F_EXCLUDES:
389 return ovsdb_datum_excludes_all(arg, field, type);
404 ovsdb_clause_clone(struct ovsdb_clause *new, struct ovsdb_clause *old)
406 new->function = old->function;
407 new->column = old->column;
408 ovsdb_datum_clone(&new->arg,
414 ovsdb_condition_match_every_clause(const struct ovsdb_row *row,
415 const struct ovsdb_condition *cnd)
419 for (i = 0; i < cnd->n_clauses; i++) {
420 if (!ovsdb_clause_evaluate(row->fields, &cnd->clauses[i], NULL)) {
429 ovsdb_condition_match_any_clause_optimized(const struct ovsdb_datum *row_datum,
430 const struct ovsdb_condition *cnd,
431 unsigned int index_map[])
433 if (ovsdb_condition_is_true(cnd)) {
437 struct shash_node *node;
438 SHASH_FOR_EACH (node, &cnd->o_columns) {
439 struct ovsdb_o_column *o_column = node->data;
440 const struct ovsdb_column *column = o_column->column;
441 const struct ovsdb_datum *arg = &row_datum[index_map ?
442 index_map[column->index] :
444 uint32_t hash = ovsdb_datum_hash(arg, &column->type, 0);
445 struct ovsdb_o_clause *o_clause;
447 HMAP_FOR_EACH_WITH_HASH(o_clause, hmap_node, hash, &o_column->o_clauses) {
448 if (ovsdb_datum_equals(arg, o_clause->arg, &column->type)) {
456 /* Returns true if condition evaluation of one of the clauses is
457 * true. index_map[] is an optional array that if exists indicates a mapping
458 * between indexing row_datum to the indexes in ovsdb_column */
460 ovsdb_condition_match_any_clause(const struct ovsdb_datum *row_datum,
461 const struct ovsdb_condition *cnd,
462 unsigned int index_map[])
466 if (cnd->optimized) {
467 return ovsdb_condition_match_any_clause_optimized(row_datum, cnd,
471 for (i = 0; i < cnd->n_clauses; i++) {
472 if (ovsdb_clause_evaluate(row_datum, &cnd->clauses[i], index_map)) {
481 ovsdb_condition_destroy(struct ovsdb_condition *cnd)
485 for (i = 0; i < cnd->n_clauses; i++) {
486 ovsdb_clause_free(&cnd->clauses[i]);
491 ovsdb_condition_optimize_destroy(cnd);
495 ovsdb_condition_init(struct ovsdb_condition *cnd)
499 cnd->optimized = true;
500 shash_init(&cnd->o_columns);
504 ovsdb_condition_empty(const struct ovsdb_condition *cnd)
506 return cnd->n_clauses == 0;
510 ovsdb_condition_cmp_3way(const struct ovsdb_condition *a,
511 const struct ovsdb_condition *b)
516 if (a->n_clauses != b->n_clauses) {
517 return a->n_clauses < b->n_clauses ? -1 : 1;
520 /* We assume clauses are sorted */
521 for (i = 0; i < a->n_clauses; i++) {
522 res = (compare_clauses_3way_with_data(&a->clauses[i], &b->clauses[i]));
532 ovsdb_condition_clone(struct ovsdb_condition *to,
533 const struct ovsdb_condition *from)
537 ovsdb_condition_init(to);
539 to->clauses = xzalloc(from->n_clauses * sizeof *to->clauses);
541 for (i = 0; i < from->n_clauses; i++) {
542 ovsdb_clause_clone(&to->clauses[i], &from->clauses[i]);
544 to->n_clauses = from->n_clauses;
545 to->optimized = from->optimized;
547 ovsdb_condition_optimize(to);
551 /* Return true if ovsdb_condition_match_any_clause() will return true on
554 ovsdb_condition_is_true(const struct ovsdb_condition *cond)
556 return (!cond->n_clauses ||
557 (cond->n_clauses >= 1 && (cond->clauses[0].function == OVSDB_F_TRUE)) ||
558 (cond->n_clauses >= 2 && (cond->clauses[1].function == OVSDB_F_TRUE)));
562 ovsdb_condition_is_false(const struct ovsdb_condition *cond)
564 return ((cond->n_clauses == 1) &&
565 (cond->clauses[0].function == OVSDB_F_FALSE));
568 const struct ovsdb_column **
569 ovsdb_condition_get_columns(const struct ovsdb_condition *cond,
572 const struct ovsdb_column **columns;
575 columns = xmalloc(cond->n_clauses * sizeof *columns);
576 for (i = 0; i < cond->n_clauses; i++) {
577 columns[i] = cond->clauses[i].column;