Merge "master" branch into "db".
[openvswitch] / 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 }