Merge "next" branch into "master".
[openvswitch] / ovsdb / condition.c
1 /* Copyright (c) 2009, 2010 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 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 bool
221 ovsdb_condition_evaluate(const struct ovsdb_row *row,
222                          const struct ovsdb_condition *cnd)
223 {
224     size_t i;
225
226     for (i = 0; i < cnd->n_clauses; i++) {
227         const struct ovsdb_clause *c = &cnd->clauses[i];
228         const struct ovsdb_datum *field = &row->fields[c->column->index];
229         const struct ovsdb_datum *arg = &cnd->clauses[i].arg;
230         const struct ovsdb_type *type = &c->column->type;
231
232         if (ovsdb_type_is_scalar(type)) {
233             int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
234                                               type->key.type);
235             switch (c->function) {
236             case OVSDB_F_LT:
237                 return cmp < 0;
238             case OVSDB_F_LE:
239                 return cmp <= 0;
240             case OVSDB_F_EQ:
241             case OVSDB_F_INCLUDES:
242                 return cmp == 0;
243             case OVSDB_F_NE:
244             case OVSDB_F_EXCLUDES:
245                 return cmp != 0;
246             case OVSDB_F_GE:
247                 return cmp >= 0;
248             case OVSDB_F_GT:
249                 return cmp > 0;
250             }
251         } else {
252             switch (c->function) {
253             case OVSDB_F_EQ:
254                 return ovsdb_datum_equals(field, arg, type);
255             case OVSDB_F_NE:
256                 return !ovsdb_datum_equals(field, arg, type);
257             case OVSDB_F_INCLUDES:
258                 return ovsdb_datum_includes_all(arg, field, type);
259             case OVSDB_F_EXCLUDES:
260                 return ovsdb_datum_excludes_all(arg, field, type);
261             case OVSDB_F_LT:
262             case OVSDB_F_LE:
263             case OVSDB_F_GE:
264             case OVSDB_F_GT:
265                 NOT_REACHED();
266             }
267         }
268         NOT_REACHED();
269     }
270
271     return true;
272 }
273
274 void
275 ovsdb_condition_destroy(struct ovsdb_condition *cnd)
276 {
277     size_t i;
278
279     for (i = 0; i < cnd->n_clauses; i++) {
280         ovsdb_clause_free(&cnd->clauses[i]);
281     }
282     free(cnd->clauses);
283 }