diff options
| -rw-r--r-- | ovsdb/condition.c | 114 | ||||
| -rw-r--r-- | ovsdb/condition.h | 5 | ||||
| -rw-r--r-- | ovsdb/execution.c | 10 | ||||
| -rw-r--r-- | ovsdb/monitor.c | 2 | ||||
| -rw-r--r-- | ovsdb/replication.c | 4 |
5 files changed, 125 insertions, 10 deletions
diff --git a/ovsdb/condition.c b/ovsdb/condition.c index 7bd8ee269..39a097752 100644 --- a/ovsdb/condition.c +++ b/ovsdb/condition.c @@ -192,6 +192,69 @@ compare_clauses_3way_with_data(const void *a_, const void *b_) &a->column->type); } +struct ovsdb_o_column { + const struct ovsdb_column *column; + struct hmap o_clauses; +}; + +struct ovsdb_o_clause { + struct ovsdb_datum *arg; + struct hmap_node hmap_node; +}; + +static void +ovsdb_condition_optimize(struct ovsdb_condition *cnd) +{ + size_t i; + uint32_t hash; + + if (!cnd->optimized) { + return; + } + + for(i = 0; i < cnd->n_clauses; i++) { + struct ovsdb_clause *clause = &cnd->clauses[i]; + + if (clause->function != OVSDB_F_EQ) { + continue; + } + + struct ovsdb_o_clause *o_clause = xzalloc(sizeof *o_clause); + struct ovsdb_o_column *o_column = + shash_find_data(&cnd->o_columns, clause->column->name); + + if (!o_column) { + o_column = xzalloc(sizeof *o_column); + o_column->column = clause->column; + hmap_init(&o_column->o_clauses); + shash_add(&cnd->o_columns, clause->column->name, o_column); + } + o_clause->arg = &clause->arg; + hash = ovsdb_datum_hash(&clause->arg, &clause->column->type, 0); + hmap_insert(&o_column->o_clauses, &o_clause->hmap_node, hash); + } +} + +static void +ovsdb_condition_optimize_destroy(struct ovsdb_condition *cnd) +{ + struct shash_node *node, *next; + + SHASH_FOR_EACH_SAFE (node, next, &cnd->o_columns) { + struct ovsdb_o_column *o_column = node->data; + struct ovsdb_o_clause *c, *c_next; + + HMAP_FOR_EACH_SAFE(c, c_next, hmap_node, &o_column->o_clauses) { + hmap_remove(&o_column->o_clauses, &c->hmap_node); + free(c); + } + hmap_destroy(&o_column->o_clauses); + shash_delete(&cnd->o_columns, node); + free(o_column); + } + shash_destroy(&cnd->o_columns); +} + struct ovsdb_error * ovsdb_condition_from_json(const struct ovsdb_table_schema *ts, const struct json *json, @@ -201,8 +264,9 @@ ovsdb_condition_from_json(const struct ovsdb_table_schema *ts, const struct json_array *array = json_array(json); size_t i; + ovsdb_condition_init(cnd); cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses); - cnd->n_clauses = 0; + for (i = 0; i < array->n; i++) { struct ovsdb_error *error; error = ovsdb_clause_from_json(ts, array->elems[i], symtab, @@ -214,12 +278,17 @@ ovsdb_condition_from_json(const struct ovsdb_table_schema *ts, return error; } cnd->n_clauses++; + if (cnd->clauses[i].function > OVSDB_F_EQ) { + cnd->optimized = false; + } } /* A real database would have a query optimizer here. */ qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses, compare_clauses_3way_with_data); + ovsdb_condition_optimize(cnd); + return NULL; } @@ -352,6 +421,34 @@ ovsdb_condition_match_every_clause(const struct ovsdb_row *row, return true; } +static bool +ovsdb_condition_match_any_clause_optimized(const struct ovsdb_datum *row_datum, + const struct ovsdb_condition *cnd, + unsigned int index_map[]) +{ + if (ovsdb_condition_is_true(cnd)) { + return true; + } + + struct shash_node *node; + SHASH_FOR_EACH (node, &cnd->o_columns) { + struct ovsdb_o_column *o_column = node->data; + const struct ovsdb_column *column = o_column->column; + const struct ovsdb_datum *arg = &row_datum[index_map ? + index_map[column->index] : + column->index]; + uint32_t hash = ovsdb_datum_hash(arg, &column->type, 0); + struct ovsdb_o_clause *o_clause; + + HMAP_FOR_EACH_WITH_HASH(o_clause, hmap_node, hash, &o_column->o_clauses) { + if (ovsdb_datum_equals(arg, o_clause->arg, &column->type)) { + return true; + } + } + } + return false; +} + /* Returns true if condition evaluation of one of the clauses is * true. index_map[] is an optional array that if exists indicates a mapping * between indexing row_datum to the indexes in ovsdb_column */ @@ -362,6 +459,11 @@ ovsdb_condition_match_any_clause(const struct ovsdb_datum *row_datum, { size_t i; + if (cnd->optimized) { + return ovsdb_condition_match_any_clause_optimized(row_datum, cnd, + index_map); + } + for (i = 0; i < cnd->n_clauses; i++) { if (ovsdb_clause_evaluate(row_datum, &cnd->clauses[i], index_map)) { return true; @@ -381,6 +483,8 @@ ovsdb_condition_destroy(struct ovsdb_condition *cnd) } free(cnd->clauses); cnd->n_clauses = 0; + + ovsdb_condition_optimize_destroy(cnd); } void @@ -388,6 +492,8 @@ ovsdb_condition_init(struct ovsdb_condition *cnd) { cnd->clauses = NULL; cnd->n_clauses = 0; + cnd->optimized = true; + shash_init(&cnd->o_columns); } bool @@ -424,12 +530,18 @@ ovsdb_condition_clone(struct ovsdb_condition *to, { size_t i; + ovsdb_condition_init(to); + to->clauses = xzalloc(from->n_clauses * sizeof *to->clauses); for (i = 0; i < from->n_clauses; i++) { ovsdb_clause_clone(&to->clauses[i], &from->clauses[i]); } to->n_clauses = from->n_clauses; + to->optimized = from->optimized; + if (to->optimized) { + ovsdb_condition_optimize(to); + } } /* Return true if ovsdb_condition_match_any_clause() will return true on diff --git a/ovsdb/condition.h b/ovsdb/condition.h index 443c8eeca..2ddc811dd 100644 --- a/ovsdb/condition.h +++ b/ovsdb/condition.h @@ -62,9 +62,12 @@ struct ovsdb_clause { struct ovsdb_condition { struct ovsdb_clause *clauses; size_t n_clauses; + bool optimized; + struct shash o_columns; }; -#define OVSDB_CONDITION_INITIALIZER { NULL, 0} +#define OVSDB_CONDITION_INITIALIZER(COND) \ + { NULL, 0, true, SHASH_INITIALIZER(&(COND)->o_columns)} void ovsdb_condition_init(struct ovsdb_condition *); bool ovsdb_condition_empty(const struct ovsdb_condition *); diff --git a/ovsdb/execution.c b/ovsdb/execution.c index de25a8797..d3fc8b914 100644 --- a/ovsdb/execution.c +++ b/ovsdb/execution.c @@ -352,7 +352,7 @@ ovsdb_execute_select(struct ovsdb_execution *x, struct ovsdb_parser *parser, { struct ovsdb_table *table; const struct json *where, *columns_json, *sort_json; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); struct ovsdb_column_set columns = OVSDB_COLUMN_SET_INITIALIZER; struct ovsdb_column_set sort = OVSDB_COLUMN_SET_INITIALIZER; struct ovsdb_error *error; @@ -420,7 +420,7 @@ ovsdb_execute_update(struct ovsdb_execution *x, struct ovsdb_parser *parser, { struct ovsdb_table *table; const struct json *where, *row_json; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); struct ovsdb_column_set columns = OVSDB_COLUMN_SET_INITIALIZER; struct ovsdb_row *row = NULL; struct update_row_cbdata ur; @@ -494,7 +494,7 @@ ovsdb_execute_mutate(struct ovsdb_execution *x, struct ovsdb_parser *parser, struct ovsdb_table *table; const struct json *where; const struct json *mutations_json; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); struct ovsdb_mutation_set mutations = OVSDB_MUTATION_SET_INITIALIZER; struct ovsdb_row *row = NULL; struct mutate_row_cbdata mr; @@ -551,7 +551,7 @@ ovsdb_execute_delete(struct ovsdb_execution *x, struct ovsdb_parser *parser, { struct ovsdb_table *table; const struct json *where; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); struct ovsdb_error *error; where = ovsdb_parser_member(parser, "where", OP_ARRAY); @@ -606,7 +606,7 @@ ovsdb_execute_wait(struct ovsdb_execution *x, struct ovsdb_parser *parser, { struct ovsdb_table *table; const struct json *timeout, *where, *columns_json, *until, *rows; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); struct ovsdb_column_set columns = OVSDB_COLUMN_SET_INITIALIZER; struct ovsdb_row_hash expected = OVSDB_ROW_HASH_INITIALIZER(expected); struct ovsdb_row_hash actual = OVSDB_ROW_HASH_INITIALIZER(actual); diff --git a/ovsdb/monitor.c b/ovsdb/monitor.c index 9a07bffaf..54c27c448 100644 --- a/ovsdb/monitor.c +++ b/ovsdb/monitor.c @@ -688,7 +688,7 @@ ovsdb_monitor_table_condition_update( struct ovsdb_monitor_table_condition *mtc = shash_find_data(&condition->tables, table->schema->name); struct ovsdb_error *error; - struct ovsdb_condition cond = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition cond = OVSDB_CONDITION_INITIALIZER(&cond); if (!condition) { return NULL; diff --git a/ovsdb/replication.c b/ovsdb/replication.c index dd8f64246..f734ae2ac 100644 --- a/ovsdb/replication.c +++ b/ovsdb/replication.c @@ -535,7 +535,7 @@ execute_delete(struct ovsdb_txn *txn, const char *uuid, { const struct json *where; struct ovsdb_error *error; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); char where_string[UUID_LEN+29]; if (!table) { @@ -586,7 +586,7 @@ execute_update(struct ovsdb_txn *txn, const char *uuid, struct ovsdb_table *table, struct json *json_row) { struct ovsdb_column_set columns = OVSDB_COLUMN_SET_INITIALIZER; - struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER; + struct ovsdb_condition condition = OVSDB_CONDITION_INITIALIZER(&condition); struct update_row_cbdata ur; struct ovsdb_row *row; struct ovsdb_error *error; |