X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Fecoli_node_subset.c;h=bfd7e71187156d3588dac84ce8fed712a18b7abe;hb=51028779e0a8772091aec5ab96bcf2519cf2f1ad;hp=21506565452b5b07e1131dd2e0455baddad58344;hpb=90d09f5806b457e758ac7f4fadf485d24162d38f;p=protos%2Flibecoli.git diff --git a/lib/ecoli_node_subset.c b/lib/ecoli_node_subset.c index 2150656..bfd7e71 100644 --- a/lib/ecoli_node_subset.c +++ b/lib/ecoli_node_subset.c @@ -1,28 +1,5 @@ -/* - * Copyright (c) 2016-2017, Olivier MATZ - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * * Neither the name of the University of California, Berkeley nor the - * names of its contributors may be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED - * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY - * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES - * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright 2016, Olivier MATZ */ #include @@ -37,13 +14,15 @@ #include #include #include -#include -#include +#include +#include #include #include #include #include +EC_LOG_TYPE_REGISTER(node_subset); + struct ec_node_subset { struct ec_node gen; struct ec_node **table; @@ -51,30 +30,28 @@ struct ec_node_subset { }; struct parse_result { - struct ec_parsed **parsed_table; /* list of parsed node */ - size_t parsed_table_len; /* number of parsed node */ - size_t len; /* consumed strings */ + size_t parse_len; /* number of parsed nodes */ + size_t len; /* consumed strings */ }; -static int __ec_node_subset_parse(struct ec_node **table, size_t table_len, - const struct ec_strvec *strvec, - struct parse_result *out) +/* recursively find the longest list of nodes that matches: the state is + * updated accordingly. */ +static int +__ec_node_subset_parse(struct parse_result *out, struct ec_node **table, + size_t table_len, struct ec_parse *state, + const struct ec_strvec *strvec) { struct ec_node **child_table; - struct ec_parsed *child_parsed = NULL; struct ec_strvec *childvec = NULL; size_t i, j, len = 0; struct parse_result best_result, result; + struct ec_parse *best_parse = NULL; int ret; if (table_len == 0) return 0; memset(&best_result, 0, sizeof(best_result)); - best_result.parsed_table = - ec_calloc(table_len, sizeof(*best_result.parsed_table[0])); - if (best_result.parsed_table == NULL) - goto fail; child_table = ec_calloc(table_len - 1, sizeof(*child_table)); if (child_table == NULL) @@ -82,15 +59,12 @@ static int __ec_node_subset_parse(struct ec_node **table, size_t table_len, for (i = 0; i < table_len; i++) { /* try to parse elt i */ - child_parsed = ec_node_parse_strvec(table[i], strvec); - if (child_parsed == NULL) + ret = ec_node_parse_child(table[i], state, strvec); + if (ret < 0) goto fail; - if (!ec_parsed_matches(child_parsed)) { - ec_parsed_free(child_parsed); - child_parsed = NULL; + if (ret == EC_PARSE_NOMATCH) continue; - } /* build a new table without elt i */ for (j = 0; j < table_len; j++) { @@ -100,125 +74,91 @@ static int __ec_node_subset_parse(struct ec_node **table, size_t table_len, child_table[j - 1] = table[j]; } - /* build a new strvec */ - len = ec_parsed_len(child_parsed); + /* build a new strvec (ret is the len of matched strvec) */ + len = ret; childvec = ec_strvec_ndup(strvec, len, ec_strvec_len(strvec) - len); if (childvec == NULL) goto fail; memset(&result, 0, sizeof(result)); - - ret = __ec_node_subset_parse(child_table, table_len - 1, - childvec, &result); + ret = __ec_node_subset_parse(&result, child_table, + table_len - 1, state, childvec); ec_strvec_free(childvec); childvec = NULL; if (ret < 0) goto fail; /* if result is not the best, ignore */ - if (result.parsed_table_len + 1 <= - best_result.parsed_table_len) { - ec_parsed_free(child_parsed); - child_parsed = NULL; - for (j = 0; j < result.parsed_table_len; j++) - ec_parsed_free(result.parsed_table[j]); - ec_free(result.parsed_table); + if (result.parse_len < best_result.parse_len) { memset(&result, 0, sizeof(result)); + ec_parse_del_last_child(state); continue; } /* replace the previous best result */ - for (j = 0; j < best_result.parsed_table_len; j++) - ec_parsed_free(best_result.parsed_table[j]); - best_result.parsed_table[0] = child_parsed; - child_parsed = NULL; - for (j = 0; j < result.parsed_table_len; j++) - best_result.parsed_table[j+1] = result.parsed_table[j]; - best_result.parsed_table_len = result.parsed_table_len + 1; + ec_parse_free(best_parse); + best_parse = ec_parse_get_last_child(state); + ec_parse_unlink_child(state, best_parse); + + best_result.parse_len = result.parse_len + 1; best_result.len = len + result.len; - ec_free(result.parsed_table); + + memset(&result, 0, sizeof(result)); } *out = best_result; ec_free(child_table); + if (best_parse != NULL) + ec_parse_link_child(state, best_parse); return 0; fail: - ec_parsed_free(child_parsed); + ec_parse_free(best_parse); ec_strvec_free(childvec); - for (j = 0; j < best_result.parsed_table_len; j++) - ec_parsed_free(best_result.parsed_table[j]); - ec_free(best_result.parsed_table); ec_free(child_table); return -1; } -static struct ec_parsed *ec_node_subset_parse(const struct ec_node *gen_node, - const struct ec_strvec *strvec) +static int +ec_node_subset_parse(const struct ec_node *gen_node, + struct ec_parse *state, + const struct ec_strvec *strvec) { struct ec_node_subset *node = (struct ec_node_subset *)gen_node; - struct ec_parsed *parsed = NULL; + struct ec_parse *parse = NULL; struct parse_result result; - struct ec_strvec *match_strvec; - size_t i; int ret; memset(&result, 0, sizeof(result)); - parsed = ec_parsed(); - if (parsed == NULL) - goto fail; - - ret = __ec_node_subset_parse(node->table, node->len, strvec, &result); + ret = __ec_node_subset_parse(&result, node->table, + node->len, state, strvec); if (ret < 0) goto fail; /* if no child node matches, return a matching empty strvec */ - if (result.parsed_table_len == 0) { - ec_free(result.parsed_table); - match_strvec = ec_strvec(); - if (match_strvec == NULL) - goto fail; - ec_parsed_set_match(parsed, gen_node, match_strvec); - return parsed; - } - - for (i = 0; i < result.parsed_table_len; i++) { - ec_parsed_add_child(parsed, result.parsed_table[i]); - result.parsed_table[i] = NULL; - } - ec_free(result.parsed_table); - result.parsed_table = NULL; - - match_strvec = ec_strvec_ndup(strvec, 0, result.len); - if (match_strvec == NULL) - goto fail; - - ec_parsed_set_match(parsed, gen_node, match_strvec); + if (result.parse_len == 0) + return 0; - return parsed; + return result.len; fail: - for (i = 0; i < result.parsed_table_len; i++) - ec_parsed_free(result.parsed_table[i]); - ec_free(result.parsed_table); - ec_parsed_free(parsed); - - return NULL; + ec_parse_free(parse); + return ret; } -static struct ec_completed * +static int __ec_node_subset_complete(struct ec_node **table, size_t table_len, - const struct ec_strvec *strvec) + struct ec_comp *comp, + const struct ec_strvec *strvec) { - struct ec_completed *completed = NULL; - struct ec_completed *child_completed = NULL; + struct ec_parse *parse = ec_comp_get_state(comp); struct ec_strvec *childvec = NULL; - struct ec_parsed *parsed = NULL; struct ec_node *save; size_t i, len; + int ret; /* * example with table = [a, b, c] @@ -229,23 +169,15 @@ __ec_node_subset_complete(struct ec_node **table, size_t table_len, * + __subset_complete([a, b], childvec) if c matches */ - completed = ec_completed(); - if (completed == NULL) - goto fail; - /* first, try to complete with each node of the table */ for (i = 0; i < table_len; i++) { if (table[i] == NULL) continue; - child_completed = ec_node_complete_strvec(table[i], - strvec); - - if (child_completed == NULL) + ret = ec_node_complete_child(table[i], + comp, strvec); + if (ret < 0) goto fail; - - ec_completed_merge(completed, child_completed); - child_completed = NULL; } /* then, if a node matches, advance in strvec and try to complete with @@ -254,78 +186,108 @@ __ec_node_subset_complete(struct ec_node **table, size_t table_len, if (table[i] == NULL) continue; - parsed = ec_node_parse_strvec(table[i], strvec); - if (parsed == NULL) + ret = ec_node_parse_child(table[i], parse, strvec); + if (ret < 0) goto fail; - if (!ec_parsed_matches(parsed)) { - ec_parsed_free(parsed); - parsed = NULL; + if (ret == EC_PARSE_NOMATCH) continue; - } - len = ec_parsed_len(parsed); + len = ret; childvec = ec_strvec_ndup(strvec, len, ec_strvec_len(strvec) - len); - if (childvec == NULL) + if (childvec == NULL) { + ec_parse_del_last_child(parse); goto fail; + } save = table[i]; table[i] = NULL; - child_completed = __ec_node_subset_complete(table, - table_len, childvec); + ret = __ec_node_subset_complete(table, table_len, + comp, childvec); table[i] = save; ec_strvec_free(childvec); childvec = NULL; + ec_parse_del_last_child(parse); - if (child_completed == NULL) + if (ret < 0) goto fail; - - ec_completed_merge(completed, child_completed); - child_completed = NULL; - - ec_parsed_free(parsed); - parsed = NULL; } - return completed; -fail: - ec_parsed_free(parsed); - ec_completed_free(child_completed); - ec_completed_free(completed); + return 0; - return NULL; +fail: + return -1; } -static struct ec_completed *ec_node_subset_complete(const struct ec_node *gen_node, - const struct ec_strvec *strvec) +static int +ec_node_subset_complete(const struct ec_node *gen_node, + struct ec_comp *comp, + const struct ec_strvec *strvec) { struct ec_node_subset *node = (struct ec_node_subset *)gen_node; - return __ec_node_subset_complete(node->table, node->len, strvec); + return __ec_node_subset_complete(node->table, node->len, comp, + strvec); } static void ec_node_subset_free_priv(struct ec_node *gen_node) { struct ec_node_subset *node = (struct ec_node_subset *)gen_node; - unsigned int i; + size_t i; for (i = 0; i < node->len; i++) ec_node_free(node->table[i]); ec_free(node->table); } +static size_t +ec_node_subset_get_children_count(const struct ec_node *gen_node) +{ + struct ec_node_subset *node = (struct ec_node_subset *)gen_node; + return node->len; +} + +static int +ec_node_subset_get_child(const struct ec_node *gen_node, size_t i, + struct ec_node **child, unsigned int *refs) +{ + struct ec_node_subset *node = (struct ec_node_subset *)gen_node; + + if (i >= node->len) + return -1; + + *child = node->table[i]; + *refs = 1; + return 0; +} + +static struct ec_node_type ec_node_subset_type = { + .name = "subset", + .parse = ec_node_subset_parse, + .complete = ec_node_subset_complete, + .size = sizeof(struct ec_node_subset), + .free_priv = ec_node_subset_free_priv, + .get_children_count = ec_node_subset_get_children_count, + .get_child = ec_node_subset_get_child, +}; + +EC_NODE_TYPE_REGISTER(ec_node_subset_type); + int ec_node_subset_add(struct ec_node *gen_node, struct ec_node *child) { struct ec_node_subset *node = (struct ec_node_subset *)gen_node; struct ec_node **table; - assert(node != NULL); + assert(node != NULL); // XXX specific assert for it, like in libyang - if (child == NULL) - return -EINVAL; + if (child == NULL) { + errno = EINVAL; + goto fail; + } - gen_node->flags &= ~EC_NODE_F_BUILT; + if (ec_node_check_type(gen_node, &ec_node_subset_type) < 0) + goto fail; table = ec_realloc(node->table, (node->len + 1) * sizeof(*node->table)); if (table == NULL) { @@ -337,21 +299,12 @@ int ec_node_subset_add(struct ec_node *gen_node, struct ec_node *child) table[node->len] = child; node->len++; - child->parent = gen_node; - TAILQ_INSERT_TAIL(&gen_node->children, child, next); - return 0; -} - -static struct ec_node_type ec_node_subset_type = { - .name = "subset", - .parse = ec_node_subset_parse, - .complete = ec_node_subset_complete, - .size = sizeof(struct ec_node_subset), - .free_priv = ec_node_subset_free_priv, -}; -EC_NODE_TYPE_REGISTER(ec_node_subset_type); +fail: + ec_node_free(child); + return -1; +} struct ec_node *__ec_node_subset(const char *id, ...) { @@ -392,86 +345,82 @@ fail: return NULL; } +/* LCOV_EXCL_START */ static int ec_node_subset_testcase(void) { struct ec_node *node; - int ret = 0; - - node = EC_NODE_SUBSET(NULL, - EC_NODE_OR(NULL, - ec_node_str(NULL, "foo"), - ec_node_str(NULL, "bar")), - ec_node_str(NULL, "bar"), - ec_node_str(NULL, "toto") + int testres = 0; + + node = EC_NODE_SUBSET(EC_NO_ID, + EC_NODE_OR(EC_NO_ID, + ec_node_str(EC_NO_ID, "foo"), + ec_node_str(EC_NO_ID, "bar")), + ec_node_str(EC_NO_ID, "bar"), + ec_node_str(EC_NO_ID, "toto") ); if (node == NULL) { - ec_log(EC_LOG_ERR, "cannot create node\n"); + EC_LOG(EC_LOG_ERR, "cannot create node\n"); return -1; } - ret |= EC_TEST_CHECK_PARSE(node, 0); - ret |= EC_TEST_CHECK_PARSE(node, 1, "foo"); - ret |= EC_TEST_CHECK_PARSE(node, 1, "bar"); - ret |= EC_TEST_CHECK_PARSE(node, 2, "foo", "bar", "titi"); - ret |= EC_TEST_CHECK_PARSE(node, 3, "bar", "foo", "toto"); - ret |= EC_TEST_CHECK_PARSE(node, 1, "foo", "foo"); - ret |= EC_TEST_CHECK_PARSE(node, 2, "bar", "bar"); - ret |= EC_TEST_CHECK_PARSE(node, 2, "bar", "foo"); - ret |= EC_TEST_CHECK_PARSE(node, 0, " "); - ret |= EC_TEST_CHECK_PARSE(node, 0, "foox"); + testres |= EC_TEST_CHECK_PARSE(node, 0); + testres |= EC_TEST_CHECK_PARSE(node, 1, "foo"); + testres |= EC_TEST_CHECK_PARSE(node, 1, "bar"); + testres |= EC_TEST_CHECK_PARSE(node, 2, "foo", "bar", "titi"); + testres |= EC_TEST_CHECK_PARSE(node, 3, "bar", "foo", "toto"); + testres |= EC_TEST_CHECK_PARSE(node, 1, "foo", "foo"); + testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "bar"); + testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "foo"); + testres |= EC_TEST_CHECK_PARSE(node, 0, " "); + testres |= EC_TEST_CHECK_PARSE(node, 0, "foox"); ec_node_free(node); /* test completion */ - node = EC_NODE_SUBSET(NULL, - ec_node_str(NULL, "foo"), - ec_node_str(NULL, "bar"), - ec_node_str(NULL, "bar2"), - ec_node_str(NULL, "toto"), - ec_node_str(NULL, "titi") + node = EC_NODE_SUBSET(EC_NO_ID, + ec_node_str(EC_NO_ID, "foo"), + ec_node_str(EC_NO_ID, "bar"), + ec_node_str(EC_NO_ID, "bar2"), + ec_node_str(EC_NO_ID, "toto"), + ec_node_str(EC_NO_ID, "titi") ); if (node == NULL) { - ec_log(EC_LOG_ERR, "cannot create node\n"); + EC_LOG(EC_LOG_ERR, "cannot create node\n"); return -1; } - ret |= EC_TEST_CHECK_COMPLETE(node, + testres |= EC_TEST_CHECK_COMPLETE(node, + "", EC_NODE_ENDLIST, + "foo", "bar", "bar2", "toto", "titi", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "", EC_NODE_ENDLIST, - "foo", "bar", "bar2", "toto", "titi", EC_NODE_ENDLIST, - ""); - ret |= EC_TEST_CHECK_COMPLETE(node, + "bar2", "bar", "foo", "toto", "titi", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "bar", "bar2", "", EC_NODE_ENDLIST, - "foo", "toto", "titi", EC_NODE_ENDLIST, - ""); - ret |= EC_TEST_CHECK_COMPLETE(node, + "foo", "toto", "titi", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "f", EC_NODE_ENDLIST, - "oo", EC_NODE_ENDLIST, - "oo"); - ret |= EC_TEST_CHECK_COMPLETE(node, + "foo", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "b", EC_NODE_ENDLIST, - "ar", "ar2", EC_NODE_ENDLIST, - "ar"); - ret |= EC_TEST_CHECK_COMPLETE(node, + "bar", "bar2", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "bar", EC_NODE_ENDLIST, - "", "2", EC_NODE_ENDLIST, - ""); - ret |= EC_TEST_CHECK_COMPLETE(node, + "bar", "bar2", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "bar", "b", EC_NODE_ENDLIST, - "ar2", EC_NODE_ENDLIST, - "ar2"); - ret |= EC_TEST_CHECK_COMPLETE(node, + "bar2", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "t", EC_NODE_ENDLIST, - "oto", "iti", EC_NODE_ENDLIST, - ""); - ret |= EC_TEST_CHECK_COMPLETE(node, + "toto", "titi", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "to", EC_NODE_ENDLIST, - "to", EC_NODE_ENDLIST, - "to"); - ret |= EC_TEST_CHECK_COMPLETE(node, + "toto", EC_NODE_ENDLIST); + testres |= EC_TEST_CHECK_COMPLETE(node, "x", EC_NODE_ENDLIST, - EC_NODE_ENDLIST, - ""); + EC_NODE_ENDLIST); ec_node_free(node); - return ret; + return testres; } +/* LCOV_EXCL_STOP */ static struct ec_test ec_node_subset_test = { .name = "node_subset",