You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@qpid.apache.org by kg...@apache.org on 2020/06/10 14:21:31 UTC
[qpid-dispatch] 02/02: DISPATCH-1682: Augment parse tree with hash
table lookup
This is an automated email from the ASF dual-hosted git repository.
kgiusti pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/qpid-dispatch.git
commit 0853244e59aa2f71a9cba0a171701c2b04c28bb1
Author: Kenneth Giusti <kg...@apache.org>
AuthorDate: Wed Jun 3 10:24:17 2020 -0400
DISPATCH-1682: Augment parse tree with hash table lookup
This closes #755
---
include/qpid/dispatch/iterator.h | 5 +
src/iterator.c | 11 +
src/parse_tree.c | 744 +++++++++++++++++++++++----------------
src/parse_tree.h | 2 +-
src/policy.c | 1 +
tests/hash_test.c | 188 ++++++----
tests/parse_tree_tests.c | 56 ++-
7 files changed, 627 insertions(+), 380 deletions(-)
diff --git a/include/qpid/dispatch/iterator.h b/include/qpid/dispatch/iterator.h
index 80fd383..343573c 100644
--- a/include/qpid/dispatch/iterator.h
+++ b/include/qpid/dispatch/iterator.h
@@ -329,6 +329,11 @@ int qd_iterator_ncopy(qd_iterator_t *iter, unsigned char* buffer, int n);
*/
unsigned char *qd_iterator_copy(qd_iterator_t *iter);
+/**
+ * A version of qd_iterator_copy that does NOT modify the iterator
+ */
+unsigned char *qd_iterator_copy_const(const qd_iterator_t *iter);
+
uint8_t qd_iterator_uint8(qd_iterator_t *iter);
/**
diff --git a/src/iterator.c b/src/iterator.c
index ff43a15..427c8f1 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -988,6 +988,17 @@ unsigned char *qd_iterator_copy(qd_iterator_t *iter)
}
+unsigned char *qd_iterator_copy_const(const qd_iterator_t *iter)
+{
+ if (!iter)
+ return 0;
+
+ qd_iterator_t temp = *iter;
+ DEQ_INIT(temp.hash_segments);
+ return qd_iterator_copy(&temp);
+}
+
+
qd_iterator_t *qd_iterator_dup(const qd_iterator_t *iter)
{
if (!iter)
diff --git a/src/parse_tree.c b/src/parse_tree.c
index bf5b695..416f98b 100644
--- a/src/parse_tree.c
+++ b/src/parse_tree.c
@@ -21,6 +21,10 @@
#include "parse_tree.h"
#include <qpid/dispatch/log.h>
#include <qpid/dispatch/alloc.h>
+#include <qpid/dispatch/hash.h>
+
+#include <stdio.h>
+#include <inttypes.h>
// token parsing
@@ -40,11 +44,11 @@ typedef struct token {
// for iterating over a string of tokens:
typedef struct token_iterator {
- char match_1; // match any 1 token
- char match_glob; // match 0 or more tokens
const char *separators;
- token_t token; // token at head of string
const char *terminator; // end of entire string
+ token_t token; // token at head of string
+ char match_1; // match any 1 token
+ char match_glob; // match 0 or more tokens
} token_iterator_t;
@@ -96,7 +100,8 @@ static void token_iterator_next(token_iterator_t *t)
const char address_token_sep[] = "./";
-const char *qd_parse_address_token_sep() {
+const char *qd_parse_address_token_sep()
+{
return address_token_sep;
}
@@ -205,49 +210,60 @@ static bool normalize_pattern(qd_parse_tree_type_t type, char *pattern)
// | +-->d-->...
// +-->x-->y-->...
//
+
+
typedef struct qd_parse_node qd_parse_node_t;
+
+struct qd_parse_tree {
+ qd_parse_node_t *root;
+ qd_log_source_t *log_source;
+ qd_hash_t *hash;
+ qd_parse_tree_type_t type;
+ uint32_t next_hkey_prefix; // next # for hash key prefix
+};
+ALLOC_DECLARE(qd_parse_tree_t);
+ALLOC_DEFINE(qd_parse_tree_t);
+
+
+typedef enum {
+ QD_PARSE_NODE_ROOT,
+ QD_PARSE_NODE_TOKEN,
+ QD_PARSE_NODE_MATCH_ONE,
+ QD_PARSE_NODE_MATCH_GLOB,
+} qd_parse_node_type_t;
+
DEQ_DECLARE(qd_parse_node_t, qd_parse_node_list_t);
struct qd_parse_node {
DEQ_LINKS(qd_parse_node_t); // siblings
- qd_parse_tree_type_t type; // match algorithm
- bool is_match_1; // this node is match one wildcard
- bool is_match_glob; // this node is match zero or more wildcard
- char *token; // portion of pattern represented by this node
- char *pattern; // entire normalized pattern matching this node
+ char *token; // portion of pattern represented by this node
+ char *pattern; // entire normalized pattern matching this node
+
// sub-trees of this node:
- qd_parse_node_list_t children; // all that start with a non-wildcard token
- struct qd_parse_node *match_1_child; // starts with a match 1 wildcard
- struct qd_parse_node *match_glob_child; // starts with 0 or more wildcard
- // data returned on match against this node:
- void *payload;
- qd_log_source_t *log_source;
+ qd_parse_node_t *match_1_child; // starts with a match 1 wildcard
+ qd_parse_node_t *match_glob_child; // starts with 0 or more wildcard
+ qd_parse_node_list_t children; // all that start with a non-wildcard token
+
+ qd_parse_node_t *parent; // NULL if root node
+ qd_hash_handle_t *handle;
+ void *payload;
+
+ // prefix for hash keys of this node's children
+ uint32_t hkey_prefix;
+ qd_parse_node_type_t match_type;
};
ALLOC_DECLARE(qd_parse_node_t);
ALLOC_DEFINE(qd_parse_node_t);
-static qd_parse_node_t *new_parse_node(const token_t *t, qd_parse_tree_type_t type)
+// Hash key for a token node is in the following format:
+// "<parent node hkey-prefix in hex>/<token>
+//
+#define HKEY_PREFIX_LEN (8 + 1) // 8 hex chars (32 bit integer) + '/'
+static inline void generate_hkey(char *hkey, size_t buf_len, uint32_t pprefix, const token_t *t)
{
- qd_parse_node_t *n = new_qd_parse_node_t();
- if (n) {
- ZERO(n);
- DEQ_ITEM_INIT(n);
- DEQ_INIT(n->children);
- n->type = type;
- n->log_source = qd_log_source("DEFAULT");
-
- if (t) { // non-root node
- const size_t tlen = TOKEN_LEN(*t);
- n->token = malloc(tlen + 1);
- strncpy(n->token, t->begin, tlen);
- n->token[tlen] = 0;
- token_iterator_t tmp;
- token_iterator_init(&tmp, type, n->token);
- n->is_match_1 = token_iterator_is_match_1(&tmp);
- n->is_match_glob = token_iterator_is_match_glob(&tmp);
- }
- }
- return n;
+ int rc = snprintf(hkey, buf_len, "%"PRIX32"/%.*s", pprefix, (int)TOKEN_LEN(*t), t->begin);
+ assert(rc > 0 && rc < buf_len);
+ (void)rc; // prevent warnings for unused var
}
@@ -260,184 +276,248 @@ static int parse_node_child_count(const qd_parse_node_t *n)
}
-static void free_parse_node(qd_parse_node_t *n)
+// Free a parse node
+static void free_parse_node(qd_parse_tree_t *tree, qd_parse_node_t *n)
{
- assert(parse_node_child_count(n) == 0);
- free(n->token);
- free(n->pattern);
- free_qd_parse_node_t(n);
+ if (n) {
+ assert(parse_node_child_count(n) == 0);
+ free(n->token);
+ free(n->pattern);
+ if (n->handle) {
+ qd_hash_remove_by_handle(tree->hash, n->handle);
+ qd_hash_handle_free(n->handle);
+ }
+ free_qd_parse_node_t(n);
+ }
+}
+
+
+// Allocate a new parse tree node.
+//
+// Allocate a new hash node. If a token is given the hash key for this node is
+// generated by concatenating the parent prefix with the token.
+//
+static qd_parse_node_t *new_parse_node(qd_parse_tree_t *tree,
+ qd_parse_node_type_t match_type,
+ const token_t *t,
+ qd_parse_node_t *parent)
+{
+ qd_parse_node_t *n = new_qd_parse_node_t();
+ if (n) {
+ ZERO(n);
+ DEQ_ITEM_INIT(n);
+ DEQ_INIT(n->children);
+ n->match_type = match_type;
+ // generate a new hash key prefix for this node's children
+ n->hkey_prefix = tree->next_hkey_prefix++;
+
+ if (match_type == QD_PARSE_NODE_TOKEN) {
+ assert(t);
+ assert(parent);
+ const size_t tlen = TOKEN_LEN(*t);
+ n->token = malloc(tlen + 1);
+ if (!n->token) {
+ free_qd_parse_node_t(n);
+ return 0;
+ }
+ strncpy(n->token, t->begin, tlen);
+ n->token[tlen] = 0;
+ {
+ const size_t hkey_size = HKEY_PREFIX_LEN + tlen + 1;
+ char hkey[hkey_size];
+ generate_hkey(hkey, hkey_size, parent->hkey_prefix, t);
+
+ if (qd_hash_insert_str(tree->hash, (unsigned char *)hkey, (void *)n, &n->handle) != QD_ERROR_NONE) {
+ free_parse_node(tree, n);
+ return 0;
+ }
+
+ n->parent = parent;
+ }
+ }
+ }
+
+ return n;
}
// find immediate child node matching token
-static qd_parse_node_t *parse_node_find_child(const qd_parse_node_t *node, const token_t *token)
+static qd_parse_node_t *parse_node_find_child(qd_parse_tree_t *tree, const qd_parse_node_t *node, const token_t *token)
{
- qd_parse_node_t *child = DEQ_HEAD(node->children);
- while (child && !token_match_str(token, child->token))
- child = DEQ_NEXT(child);
+ qd_parse_node_t *child = 0;
+ const size_t tlen = TOKEN_LEN(*token);
+ const size_t hkey_size = HKEY_PREFIX_LEN + tlen + 1;
+ char hkey[hkey_size];
+
+ generate_hkey(hkey, hkey_size, node->hkey_prefix, token);
+ qd_hash_retrieve_str(tree->hash, (const unsigned char *)hkey, (void **)&child);
+ if (child) {
+ assert(child->parent == node);
+ }
return child;
}
// Add a new pattern and associated data to the tree.
// Return QD_ERROR_ALREADY_EXISTS if the pattern is already in the tree.
+// caller transfers ownership of "pattern"
//
-static qd_error_t parse_node_add_pattern(qd_parse_node_t *node,
- token_iterator_t *key,
- const char *pattern,
- void *payload)
+static qd_error_t parse_node_add_pattern(qd_parse_tree_t *tree, char *pattern, void *payload)
{
- if (token_iterator_done(key)) { // empty leaf node?
+ qd_parse_node_t *node = tree->root;
+ qd_error_t result = QD_ERROR_NONE;
+ token_iterator_t iterator;
- if (node->pattern) {
- // this node is not empty
- return QD_ERROR_ALREADY_EXISTS;
- }
+ normalize_pattern(tree->type, pattern);
- node->pattern = strdup(pattern);
- node->payload = payload;
- return QD_ERROR_NONE;
+ // worst case maximum for hash key if pattern is a single token
+ const size_t buf_size = HKEY_PREFIX_LEN + strlen(pattern) + 1;
+ char *hkey = malloc(buf_size);
+ if (!hkey) {
+ result = qd_error(QD_ERROR_ALLOC, "Pattern '%s' not added to parse tree", pattern);
+ free(pattern);
+ return result;
}
- if (token_iterator_is_match_1(key)) {
- if (!node->match_1_child) {
- node->match_1_child = new_parse_node(&key->token,
- node->type);
- }
- token_iterator_next(key);
- return parse_node_add_pattern(node->match_1_child,
- key,
- pattern,
- payload);
- } else if (token_iterator_is_match_glob(key)) {
- if (!node->match_glob_child) {
- node->match_glob_child = new_parse_node(&key->token,
- node->type);
+ token_iterator_init(&iterator, tree->type, pattern);
+
+ //
+ // walk the iterator through the tree adding nodes for each token/wildcard as needed
+ //
+ while (!token_iterator_done(&iterator)) {
+
+ if (token_iterator_is_match_1(&iterator)) {
+ if (!node->match_1_child) {
+ node->match_1_child = new_parse_node(tree, QD_PARSE_NODE_MATCH_ONE, 0, node);
+ if (!node->match_1_child) {
+ result = qd_error(QD_ERROR_ALLOC, "Pattern '%s' not added to parse tree", pattern);
+ break;
+ }
+ node->match_1_child->parent = node;
+ }
+ node = node->match_1_child;
+ token_iterator_next(&iterator);
+
+ } else if (token_iterator_is_match_glob(&iterator)) {
+ if (!node->match_glob_child) {
+ node->match_glob_child = new_parse_node(tree, QD_PARSE_NODE_MATCH_GLOB, 0, node);
+ if (!node->match_glob_child) {
+ result = qd_error(QD_ERROR_ALLOC, "Pattern '%s' not added to parse tree", pattern);
+ break;
+ }
+ node->match_glob_child->parent = node;
+ }
+ node = node->match_glob_child;
+ token_iterator_next(&iterator);
+
+ } else { // non-wildcard token
+ token_t new_token;
+ token_iterator_pop(&iterator, &new_token);
+ generate_hkey(hkey, buf_size, node->hkey_prefix, &new_token);
+
+ qd_parse_node_t *child = 0;
+ qd_hash_retrieve_str(tree->hash, (const unsigned char *)hkey, (void **)&child);
+
+ if (child) {
+ assert(child->parent == node);
+ node = child;
+ } else {
+ // add new node for new_token
+ child = new_parse_node(tree, QD_PARSE_NODE_TOKEN, &new_token, node);
+ if (!child) {
+ result = qd_error(QD_ERROR_ALLOC, "Pattern '%s' not added to parse tree", pattern);
+ break;
+ }
+ DEQ_INSERT_TAIL(node->children, child);
+ node = child;
+ }
}
- token_iterator_next(key);
- return parse_node_add_pattern(node->match_glob_child,
- key,
- pattern,
- payload);
- } else {
- // check the children nodes
- token_t current;
- token_iterator_pop(key, ¤t);
-
- qd_parse_node_t *child = parse_node_find_child(node, ¤t);
- if (child) {
- return parse_node_add_pattern(child,
- key,
- pattern,
- payload);
+ }
+
+ // done iterating over pattern.
+
+ if (result == QD_ERROR_NONE) {
+ if (node == tree->root) {
+ result = qd_error(QD_ERROR_VALUE, "Invalid pattern '%s' not added to parse tree", pattern);
+ } else if (node->pattern) {
+ result = qd_error(QD_ERROR_ALREADY_EXISTS, "Duplicate pattern '%s' not added to parse tree", pattern);
} else {
- child = new_parse_node(¤t, node->type);
- DEQ_INSERT_TAIL(node->children, child);
- return parse_node_add_pattern(child,
- key,
- pattern,
- payload);
+ node->pattern = pattern;
+ pattern = 0;
+ node->payload = payload;
+ qd_log(tree->log_source, QD_LOG_TRACE, "Parse tree add pattern '%s'", node->pattern);
}
}
+
+ free(pattern);
+ free(hkey);
+
+ return result;
}
-// remove pattern from the tree.
-// return the payload of the removed pattern
-static void *parse_node_remove_pattern(qd_parse_node_t *node,
- token_iterator_t *key,
- const char *pattern)
+
+// Find the leaf node matching the pattern. Returns 0 if pattern is not in the tree
+//
+static qd_parse_node_t *parse_node_get_pattern(qd_parse_tree_t *tree, char *pattern)
{
- void *old = NULL;
- if (token_iterator_done(key)) {
- // this node's pattern
- if (node->pattern) {
- assert(strcmp(node->pattern, pattern) == 0);
- free(node->pattern);
- node->pattern = NULL;
- }
- old = node->payload;
- node->payload = NULL;
- } else if (token_iterator_is_match_1(key)) {
- assert(node->match_1_child);
- token_iterator_next(key);
- old = parse_node_remove_pattern(node->match_1_child, key, pattern);
- if (node->match_1_child->pattern == NULL
- && parse_node_child_count(node->match_1_child) == 0) {
- free_parse_node(node->match_1_child);
- node->match_1_child = NULL;
- }
- } else if (token_iterator_is_match_glob(key)) {
- assert(node->match_glob_child);
- token_iterator_next(key);
- old = parse_node_remove_pattern(node->match_glob_child, key, pattern);
- if (node->match_glob_child->pattern == NULL
- && parse_node_child_count(node->match_glob_child) == 0) {
- free_parse_node(node->match_glob_child);
- node->match_glob_child = NULL;
- }
- } else {
- token_t current;
- token_iterator_pop(key, ¤t);
- qd_parse_node_t *child = parse_node_find_child(node, ¤t);
- if (child) {
- old = parse_node_remove_pattern(child, key, pattern);
- if (child->pattern == NULL
- && parse_node_child_count(child) == 0) {
- DEQ_REMOVE(node->children, child);
- free_parse_node(child);
- }
- }
+ qd_parse_node_t *node = tree->root;
+ token_iterator_t iterator;
+
+ normalize_pattern(tree->type, pattern);
+
+ // worst case maximum for hash key if pattern is a single token
+ const size_t buf_size = HKEY_PREFIX_LEN + strlen(pattern) + 1;
+ char *hkey = malloc(buf_size);
+ if (!hkey) {
+ return 0;
}
- return old;
-}
+ token_iterator_init(&iterator, tree->type, pattern);
-// Find the pattern in the tree, return the payload pointer or NULL if pattern
-// is not in the tree
-static qd_parse_node_t *parse_node_get_pattern(qd_parse_node_t *node,
- token_iterator_t *key,
- const char *pattern)
-{
- if (!node)
- return NULL;
+ while (node && !token_iterator_done(&iterator)) {
- if (token_iterator_done(key))
- return node;
+ if (token_iterator_is_match_1(&iterator)) {
+ node = node->match_1_child;
+ token_iterator_next(&iterator);
- if (token_iterator_is_match_1(key)) {
- token_iterator_next(key);
- return parse_node_get_pattern(node->match_1_child,
- key,
- pattern);
- } else if (token_iterator_is_match_glob(key)) {
- token_iterator_next(key);
- return parse_node_get_pattern(node->match_glob_child,
- key,
- pattern);
- } else {
- // check the children nodes
- token_t current;
- token_iterator_pop(key, ¤t);
-
- qd_parse_node_t *child = parse_node_find_child(node, ¤t);
- if (child) {
- return parse_node_get_pattern(child,
- key,
- pattern);
+ } else if (token_iterator_is_match_glob(&iterator)) {
+ node = node->match_glob_child;
+ token_iterator_next(&iterator);
+
+ } else {
+ token_t new_token;
+ token_iterator_pop(&iterator, &new_token);
+
+ // search for new_token child
+ assert(node->hkey_prefix);
+ generate_hkey(hkey, buf_size, node->hkey_prefix, &new_token);
+
+ qd_parse_node_t *child = 0;
+ qd_hash_retrieve_str(tree->hash, (const unsigned char *)hkey, (void **)&child);
+
+ assert(!child || child->parent == node);
+ node = child;
}
}
- return NULL; // not found
+ free(hkey);
+
+ if (node && node->pattern) {
+ assert(strcmp(node->pattern, pattern) == 0);
+ return node;
+ }
+
+ return 0;
}
-static bool parse_node_find(qd_parse_node_t *, token_iterator_t *,
+static bool parse_node_find(qd_parse_tree_t *, qd_parse_node_t *, token_iterator_t *,
qd_parse_tree_visit_t *, void *);
// search the sub-trees of this node.
// This function returns false to stop the search
-static bool parse_node_find_children(qd_parse_node_t *node, token_iterator_t *value,
+static bool parse_node_find_children(qd_parse_tree_t *tree, qd_parse_node_t *node, token_iterator_t *value,
qd_parse_tree_visit_t *callback, void *handle)
{
if (!token_iterator_done(value)) {
@@ -448,16 +528,16 @@ static bool parse_node_find_children(qd_parse_node_t *node, token_iterator_t *va
token_t child_token;
token_iterator_pop(&tmp, &child_token);
- qd_parse_node_t *child = parse_node_find_child(node, &child_token);
+ qd_parse_node_t *child = parse_node_find_child(tree, node, &child_token);
if (child) {
- if (!parse_node_find(child, &tmp, callback, handle))
+ if (!parse_node_find(tree, child, &tmp, callback, handle))
return false;
}
}
if (node->match_1_child) {
token_iterator_t tmp = *value;
- if (!parse_node_find(node->match_1_child, &tmp, callback, handle))
+ if (!parse_node_find(tree, node->match_1_child, &tmp, callback, handle))
return false;
}
}
@@ -465,7 +545,7 @@ static bool parse_node_find_children(qd_parse_node_t *node, token_iterator_t *va
// always try glob - even if empty (it can match empty keys)
if (node->match_glob_child) {
token_iterator_t tmp = *value;
- if (!parse_node_find(node->match_glob_child, &tmp, callback, handle))
+ if (!parse_node_find(tree, node->match_glob_child, &tmp, callback, handle))
return false;
}
@@ -475,7 +555,7 @@ static bool parse_node_find_children(qd_parse_node_t *node, token_iterator_t *va
// This node matched the last token.
// This function returns false to stop the search
-static bool parse_node_find_token(qd_parse_node_t *node, token_iterator_t *value,
+static bool parse_node_find_token(qd_parse_tree_t *tree, qd_parse_node_t *node, token_iterator_t *value,
qd_parse_tree_visit_t *callback, void *handle)
{
if (token_iterator_done(value) && node->pattern) {
@@ -486,13 +566,13 @@ static bool parse_node_find_token(qd_parse_node_t *node, token_iterator_t *value
// no payload or more tokens. Continue to lower sub-trees. Even if no more
// tokens (may have a # match)
- return parse_node_find_children(node, value, callback, handle);
+ return parse_node_find_children(tree, node, value, callback, handle);
}
// this node matches any one token
// returns false to stop the search
-static bool parse_node_match_1(qd_parse_node_t *node, token_iterator_t *value,
+static bool parse_node_match_1(qd_parse_tree_t *tree, qd_parse_node_t *node, token_iterator_t *value,
qd_parse_tree_visit_t *callback, void *handle)
{
// must match exactly one token:
@@ -509,19 +589,19 @@ static bool parse_node_match_1(qd_parse_node_t *node, token_iterator_t *value,
}
// no payload or more tokens: continue to lower sub-trees
- return parse_node_find_children(node, value, callback, handle);
+ return parse_node_find_children(tree, node, value, callback, handle);
}
// current node is hash, match the remainder of the string
// return false to stop search
-static bool parse_node_match_glob(qd_parse_node_t *node, token_iterator_t *value,
+static bool parse_node_match_glob(qd_parse_tree_t *tree, qd_parse_node_t *node, token_iterator_t *value,
qd_parse_tree_visit_t *callback, void *handle)
{
// consume each token and look for a match on the
// remaining key.
while (!token_iterator_done(value)) {
- if (!parse_node_find_children(node, value, callback, handle))
+ if (!parse_node_find_children(tree, node, value, callback, handle))
return false;
token_iterator_next(value);
}
@@ -535,38 +615,63 @@ static bool parse_node_match_glob(qd_parse_node_t *node, token_iterator_t *value
// find the payload associated with the input string 'value'
-static bool parse_node_find(qd_parse_node_t *node, token_iterator_t *value,
+static bool parse_node_find(qd_parse_tree_t *tree, qd_parse_node_t *node, token_iterator_t *value,
qd_parse_tree_visit_t *callback, void *handle)
{
- if (node->is_match_1)
- return parse_node_match_1(node, value, callback, handle);
- else if (node->is_match_glob)
- return parse_node_match_glob(node, value, callback, handle);
- else
- return parse_node_find_token(node, value, callback, handle);
+ switch (node->match_type) {
+ case QD_PARSE_NODE_MATCH_ONE:
+ return parse_node_match_1(tree, node, value, callback, handle);
+ case QD_PARSE_NODE_MATCH_GLOB:
+ return parse_node_match_glob(tree, node, value, callback, handle);
+ case QD_PARSE_NODE_TOKEN:
+ return parse_node_find_token(tree, node, value, callback, handle);
+ case QD_PARSE_NODE_ROOT:
+ return parse_node_find_children(tree, node, value, callback, handle);
+ }
+ return true;
}
-static void parse_node_free(qd_parse_node_t *node)
+static void parse_node_free(qd_parse_tree_t *tree, qd_parse_node_t *node)
{
if (node) {
- if (node->match_1_child) parse_node_free(node->match_1_child);
- if (node->match_glob_child) parse_node_free(node->match_glob_child);
+ if (node->match_1_child) parse_node_free(tree, node->match_1_child);
+ if (node->match_glob_child) parse_node_free(tree, node->match_glob_child);
node->match_1_child = node->match_glob_child = NULL;
while (!DEQ_IS_EMPTY(node->children)) {
qd_parse_node_t *child = DEQ_HEAD(node->children);
DEQ_REMOVE_HEAD(node->children);
- parse_node_free(child);
+ parse_node_free(tree, child);
}
- free_parse_node(node);
+ free_parse_node(tree, node);
}
}
qd_parse_tree_t *qd_parse_tree_new(qd_parse_tree_type_t type)
{
- return new_parse_node(NULL, type);
+
+ qd_parse_tree_t *tree = new_qd_parse_tree_t();
+ if (tree) {
+ ZERO(tree);
+ tree->type = type;
+ tree->log_source = qd_log_source("DEFAULT");
+ tree->next_hkey_prefix = 1;
+ tree->root = new_parse_node(tree, QD_PARSE_NODE_ROOT, 0, 0);
+ if (!tree->root) {
+ free_qd_parse_tree_t(tree);
+ return 0;
+ }
+ tree->hash = qd_hash(10, 32, false);
+ if (!tree->hash) {
+ parse_node_free(tree, tree->root);
+ free_qd_parse_tree_t(tree);
+ return 0;
+ }
+ }
+
+ return tree;
}
@@ -578,106 +683,122 @@ static bool get_first(void *handle, const char *pattern, void *payload)
return false;
}
-bool qd_parse_tree_retrieve_match(qd_parse_tree_t *node,
+bool qd_parse_tree_retrieve_match(qd_parse_tree_t *tree,
const qd_iterator_t *value,
void **payload)
{
*payload = NULL;
- qd_parse_tree_search(node, value, get_first, payload);
+ qd_parse_tree_search(tree, value, get_first, payload);
if (*payload == NULL)
- qd_log(node->log_source, QD_LOG_TRACE, "Parse tree match not found");
+ qd_log(tree->log_source, QD_LOG_TRACE, "Parse tree match not found");
return *payload != NULL;
}
// Invoke callback for each pattern that matches 'value'
-void qd_parse_tree_search(qd_parse_tree_t *node,
+void qd_parse_tree_search(qd_parse_tree_t *tree,
const qd_iterator_t *value,
qd_parse_tree_visit_t *callback, void *handle)
{
token_iterator_t t_iter;
- // @TODO(kgiusti) for now:
- qd_iterator_t *dup = qd_iterator_dup(value);
- char *str = (char *)qd_iterator_copy(dup);
- qd_log(node->log_source, QD_LOG_TRACE, "Parse tree search for '%s'", str);
+ char *str = (char *)qd_iterator_copy_const(value);
+ qd_log(tree->log_source, QD_LOG_TRACE, "Parse tree search for '%s'", str);
- token_iterator_init(&t_iter, node->type, str);
- parse_node_find(node, &t_iter, callback, handle);
+ token_iterator_init(&t_iter, tree->type, str);
+ parse_node_find(tree, tree->root, &t_iter, callback, handle);
free(str);
- qd_iterator_free(dup);
}
-// Add match pattern to tree
-qd_error_t qd_parse_tree_add_pattern(qd_parse_tree_t *node,
+qd_error_t qd_parse_tree_add_pattern(qd_parse_tree_t *tree,
const qd_iterator_t *pattern,
void *payload)
{
- token_iterator_t key;
- // @TODO(kgiusti) for now:
- qd_iterator_t *dup = qd_iterator_dup(pattern);
- char *str = (char *)qd_iterator_copy(dup);
+ char *str = (char *)qd_iterator_copy_const(pattern);
+ if (!str)
+ return QD_ERROR_ALLOC;
- normalize_pattern(node->type, str);
- qd_log(node->log_source, QD_LOG_TRACE,
- "Parse tree add address pattern '%s'", str);
-
- token_iterator_init(&key, node->type, str);
- qd_error_t rc = parse_node_add_pattern(node, &key, str, payload);
- free(str);
- qd_iterator_free(dup);
- return rc;
+ return parse_node_add_pattern(tree, str, payload);
}
// returns true if pattern exists in tree
-bool qd_parse_tree_get_pattern(qd_parse_tree_t *node,
+bool qd_parse_tree_get_pattern(qd_parse_tree_t *tree,
const qd_iterator_t *pattern,
void **payload)
{
- token_iterator_t key;
- qd_parse_node_t *found = NULL;
- // @TODO(kgiusti) for now:
- qd_iterator_t *dup = qd_iterator_dup(pattern);
- char *str = (char *)qd_iterator_copy(dup);
+ char *str = (char *)qd_iterator_copy_const(pattern);
+ if (!str)
+ return false;
- normalize_pattern(node->type, (char *)str);
- qd_log(node->log_source, QD_LOG_TRACE,
- "Parse tree get address pattern '%s'", str);
-
- token_iterator_init(&key, node->type, str);
- found = parse_node_get_pattern(node, &key, str);
+ qd_parse_node_t *found = parse_node_get_pattern(tree, str);
free(str);
- qd_iterator_free(dup);
*payload = found ? found->payload : NULL;
- return *payload != NULL;
+ return !!found;
}
// returns the payload void *
-void *qd_parse_tree_remove_pattern(qd_parse_tree_t *node,
+void *qd_parse_tree_remove_pattern(qd_parse_tree_t *tree,
const qd_iterator_t *pattern)
{
- token_iterator_t key;
- void *rc = NULL;
- // @TODO(kgiusti) for now:
- qd_iterator_t *dup = qd_iterator_dup(pattern);
- char *str = (char *)qd_iterator_copy(dup);
+ char *str = (char *)qd_iterator_copy_const(pattern);
+ if (!str)
+ return 0;
- normalize_pattern(node->type, str);
- qd_log(node->log_source, QD_LOG_TRACE,
- "Parse tree remove address pattern '%s'", str);
+ qd_parse_node_t *node = parse_node_get_pattern(tree, str);
+ if (!node) {
+ free(str);
+ return 0;
+ }
- token_iterator_init(&key, node->type, str);
- rc = parse_node_remove_pattern(node, &key, str);
+ assert(strcmp(node->pattern, str) == 0);
free(str);
- qd_iterator_free(dup);
- return rc;
+
+ void *value = node->payload;
+
+ // now clean up this node. Be aware we can only free the entire node if it does not have children.
+ // If it has children just zero out the pattern field indicates it is no longer a terminal node.
+ // The fun happens if it has no children: in this case free the node then
+ // see if the parent node is now childless and NOT a terminal node. If so
+ // clean it up as well. Repeat.
+
+ free(node->pattern);
+ node->pattern = 0;
+ node->payload = 0;
+ qd_parse_node_t *parent = node->parent;
+
+ while (node && node->pattern == 0 && parse_node_child_count(node) == 0 && parent) {
+
+ switch (node->match_type) {
+ case QD_PARSE_NODE_MATCH_ONE:
+ assert(parent->match_1_child == node);
+ parent->match_1_child = 0;
+ break;
+ case QD_PARSE_NODE_MATCH_GLOB:
+ assert(parent->match_glob_child == node);
+ parent->match_glob_child = 0;
+ break;
+ case QD_PARSE_NODE_TOKEN:
+ DEQ_REMOVE(parent->children, node);
+ break;
+ case QD_PARSE_NODE_ROOT:
+ default:
+ // cannot get here
+ assert(false);
+ break;
+ }
+ free_parse_node(tree, node);
+ node = parent;
+ parent = node->parent;
+ }
+
+ return value;
}
-bool qd_parse_tree_walk(qd_parse_tree_t *node, qd_parse_tree_visit_t *callback, void *handle)
+static bool parse_tree_walk(qd_parse_node_t *node, qd_parse_tree_visit_t *callback, void *handle)
{
if (node->pattern) { // terminal node for pattern
if (!callback(handle, node->pattern, node->payload))
@@ -686,36 +807,48 @@ bool qd_parse_tree_walk(qd_parse_tree_t *node, qd_parse_tree_visit_t *callback,
qd_parse_node_t *child = DEQ_HEAD(node->children);
while (child) {
- if (!qd_parse_tree_walk(child, callback, handle))
+ if (!parse_tree_walk(child, callback, handle))
return false;
child = DEQ_NEXT(child);
}
if (node->match_1_child)
- if (!qd_parse_tree_walk(node->match_1_child, callback, handle))
+ if (!parse_tree_walk(node->match_1_child, callback, handle))
return false;
if (node->match_glob_child)
- if (!qd_parse_tree_walk(node->match_glob_child, callback, handle))
+ if (!parse_tree_walk(node->match_glob_child, callback, handle))
return false;
return true;
}
+bool qd_parse_tree_walk(qd_parse_tree_t *tree, qd_parse_tree_visit_t *callback, void *handle)
+{
+ return parse_tree_walk(tree->root, callback, handle);
+}
+
+
bool qd_parse_tree_validate_pattern(const qd_parse_tree_t *tree,
const qd_iterator_t *pattern)
{
- switch (tree->type) {
- case QD_PARSE_TREE_MQTT: {
+ char *str = (char *)qd_iterator_copy_const(pattern);
+ if (!str)
+ return false;
+
+ token_iterator_t ti;
+ token_iterator_init(&ti, tree->type, str);
+ if (token_iterator_done(&ti)) {
+ // empty iterator
+ free(str);
+ return false;
+ }
+
+ if (tree->type == QD_PARSE_TREE_MQTT) {
// simply ensure that if a '#' is present it is the last token in the
// pattern
- token_iterator_t ti;
bool valid = true;
- qd_iterator_t *dup = qd_iterator_dup(pattern);
- char *str = (char *)qd_iterator_copy(dup);
- qd_iterator_free(dup);
- token_iterator_init(&ti, QD_PARSE_TREE_MQTT, str);
while (!token_iterator_done(&ti)) {
token_t head;
token_iterator_pop(&ti, &head);
@@ -728,12 +861,8 @@ bool qd_parse_tree_validate_pattern(const qd_parse_tree_t *tree,
return valid;
}
- case QD_PARSE_TREE_ADDRESS:
- case QD_PARSE_TREE_AMQP_0_10:
- default:
- // never validated these before...
- return true;
- }
+ free(str);
+ return true;
}
@@ -743,39 +872,67 @@ qd_parse_tree_type_t qd_parse_tree_type(const qd_parse_tree_t *tree)
}
+static void _parse_tree_free(qd_parse_tree_t *tree)
+{
+ if (tree) {
+ parse_node_free(tree, tree->root);
+ qd_hash_free(tree->hash);
+ free_qd_parse_tree_t(tree);
+ }
+}
+
#if 0
-#include <stdio.h>
-void qd_parse_tree_dump(qd_parse_node_t *node, int depth)
+
+static void _node_dump(const qd_parse_node_t *node, const int depth)
{
for (int i = 0; i < depth; i++)
fprintf(stdout, " ");
- fprintf(stdout, "token: %s pattern: %s is match 1: %s is glob: %s # childs: %d\n",
+ char *type = (node->match_type == QD_PARSE_NODE_ROOT
+ ? "ROOT"
+ : (node->match_type == QD_PARSE_NODE_TOKEN
+ ? "TOKEN"
+ : (node->match_type == QD_PARSE_NODE_MATCH_ONE
+ ? "STAR"
+ : "GLOB")));
+ fprintf(stdout, "token: %s pattern: %s type: %s # childs: %d hkey: %s hprefix %"PRIX32" payload: %p\n",
node->token ? node->token : "*NONE*",
node->pattern ? node->pattern: "*NONE*",
- node->is_match_1 ? "yes" : "no",
- node->is_match_glob ? "yes" : "no",
- parse_node_child_count(node));
- if (node->match_1_child) qd_parse_tree_dump(node->match_1_child, depth + 1);
- if (node->match_glob_child) qd_parse_tree_dump(node->match_glob_child, depth + 1);
+ type,
+ parse_node_child_count(node),
+ (node->handle ? (const char *)qd_hash_key_by_handle(node->handle) : "*NONE*"),
+ node->hkey_prefix,
+ node->payload);
+
+ if (node->match_1_child) _node_dump(node->match_1_child, depth + 1);
+ if (node->match_glob_child) _node_dump(node->match_glob_child, depth + 1);
qd_parse_node_t *child = DEQ_HEAD(node->children);
while (child) {
- qd_parse_tree_dump(child, depth + 1);
+ _node_dump(child, depth + 1);
child = DEQ_NEXT(child);
}
}
-void qd_parse_tree_free(qd_parse_node_t *node)
+void qd_parse_tree_dump(const qd_parse_tree_t *tree)
+{
+ if (tree && tree->root) {
+ _node_dump(tree->root, 0);
+ fflush(stdout);
+ }
+}
+
+void qd_parse_tree_free(qd_parse_tree_t *tree)
{
fprintf(stdout, "PARSE TREE DUMP\n");
- qd_parse_tree_dump(node, 4);
- parse_node_free(node);
+ fprintf(stdout, "===============\n");
+ qd_parse_tree_dump(tree);
+ _parse_tree_free(tree);
}
#else
-void qd_parse_tree_free(qd_parse_node_t *node)
+void qd_parse_tree_free(qd_parse_tree_t *tree)
{
- parse_node_free(node);
+ _parse_tree_free(tree);
}
#endif
@@ -783,38 +940,31 @@ void qd_parse_tree_free(qd_parse_node_t *node)
// parse tree functions using string interface
//
-// returns old payload or NULL if new
-qd_error_t qd_parse_tree_add_pattern_str(qd_parse_tree_t *node,
+qd_error_t qd_parse_tree_add_pattern_str(qd_parse_tree_t *tree,
const char *pattern,
void *payload)
{
- token_iterator_t key;
char *str = strdup(pattern);
+ if (!str)
+ return QD_ERROR_ALLOC;
- normalize_pattern(node->type, str);
- qd_log(node->log_source, QD_LOG_TRACE,
- "Parse tree(str) add address pattern '%s'", str);
-
- token_iterator_init(&key, node->type, str);
- qd_error_t rc = parse_node_add_pattern(node, &key, str, payload);
- free(str);
- return rc;
+ return parse_node_add_pattern(tree, str, payload);
}
// visit each matching pattern that matches value in the order based on the
// precedence rules
-void qd_parse_tree_search_str(qd_parse_tree_t *node,
+void qd_parse_tree_search_str(qd_parse_tree_t *tree,
const char *value,
qd_parse_tree_visit_t *callback, void *handle)
{
token_iterator_t t_iter;
// @TODO(kgiusti) for now:
char *str = strdup(value);
- qd_log(node->log_source, QD_LOG_TRACE, "Parse tree(str) search for '%s'", str);
+ qd_log(tree->log_source, QD_LOG_TRACE, "Parse tree(str) search for '%s'", str);
- token_iterator_init(&t_iter, node->type, str);
- parse_node_find(node, &t_iter, callback, handle);
+ token_iterator_init(&t_iter, tree->type, str);
+ parse_node_find(tree, tree->root, &t_iter, callback, handle);
free(str);
}
@@ -833,11 +983,11 @@ bool qd_parse_tree_retrieve_match_str(qd_parse_tree_t *tree,
}
// returns old payload or NULL if not present
-void *qd_parse_tree_remove_pattern_str(qd_parse_tree_t *node,
+void *qd_parse_tree_remove_pattern_str(qd_parse_tree_t *tree,
const char *pattern)
{
qd_iterator_t *piter = qd_iterator_string(pattern, ITER_VIEW_ALL);
- void *result = qd_parse_tree_remove_pattern(node, piter);
+ void *result = qd_parse_tree_remove_pattern(tree, piter);
qd_iterator_free(piter);
return result;
}
diff --git a/src/parse_tree.h b/src/parse_tree.h
index e01f606..d33821f 100644
--- a/src/parse_tree.h
+++ b/src/parse_tree.h
@@ -24,7 +24,7 @@
#include <qpid/dispatch/iterator.h>
-typedef struct qd_parse_node qd_parse_tree_t;
+typedef struct qd_parse_tree qd_parse_tree_t;
// Pattern matching algorithms
// ADDRESS - configured address prefix/pattern matching
diff --git a/src/policy.c b/src/policy.c
index 8534065..7378243 100644
--- a/src/policy.c
+++ b/src/policy.c
@@ -1360,6 +1360,7 @@ bool qd_policy_host_pattern_add(qd_policy_t *policy, const char *hostPattern)
QD_LOG_WARNING,
"vhost hostname pattern '%s' add failed: %s",
hostPattern, err ? err : "unknown error");
+ qd_error_clear(); // allow policy agent to raise PolicyError
}
return rc == QD_ERROR_NONE;
}
diff --git a/tests/hash_test.c b/tests/hash_test.c
index 5ea8a80..5bf7fe0 100644
--- a/tests/hash_test.c
+++ b/tests/hash_test.c
@@ -40,7 +40,9 @@ static const int key_count = sizeof(keys)/sizeof(keys[0]);
static char *test_iter_keys(void *context)
{
+ char *result = 0;
qd_hash_handle_t *handles[key_count];
+ qd_iterator_t *i_key = 0;
qd_hash_t *hash = qd_hash(4, 10, false);
if (!hash)
return "hash table allocation failed";
@@ -49,43 +51,57 @@ static char *test_iter_keys(void *context)
// add using iterator, lookup and remove using string
//
-
for (int i = 0; i < key_count; ++i) {
const unsigned char *key = keys[i];
qd_hash_handle_t **handle = &handles[i];
- qd_iterator_t *i_key = qd_iterator_string((const char *)key, ITER_VIEW_ALL);
- if (qd_hash_insert(hash, i_key, (void *)key, handle) != QD_ERROR_NONE)
- return "hash table insert failed";
+ i_key = qd_iterator_string((const char *)key, ITER_VIEW_ALL);
+ if (qd_hash_insert(hash, i_key, (void *)key, handle) != QD_ERROR_NONE) {
+ result = "hash table insert failed";
+ goto done;
+ }
- if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
- return "hash handle key did not match";
+ if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0) {
+ result = "hash handle key did not match";
+ goto done;
+ }
qd_iterator_free(i_key);
+ i_key = 0;
}
- if (qd_hash_size(hash) != key_count)
- return "hash size is incorrect";
+ if (qd_hash_size(hash) != key_count) {
+ result = "hash size is incorrect";
+ goto done;
+ }
for (int i = 0; i < key_count; ++i) {
const unsigned char *key = keys[i];
unsigned char *value;
- if (qd_hash_retrieve_str(hash, key, (void **)&value) != QD_ERROR_NONE)
- return "Key lookup failed";
- if (strcmp((const char *)value, (const char *)key) != 0)
- return "key value mismatch";
+ if (qd_hash_retrieve_str(hash, key, (void **)&value) != QD_ERROR_NONE) {
+ result = "Key lookup failed";
+ goto done;
+ }
+ if (strcmp((const char *)value, (const char *)key) != 0) {
+ result= "key value mismatch";
+ goto done;
+ }
}
for (int i = 0; i < key_count; ++i) {
const unsigned char *key = keys[i];
- if (qd_hash_remove_str(hash, key) != QD_ERROR_NONE)
- return "str key remove failed";
+ if (qd_hash_remove_str(hash, key) != QD_ERROR_NONE) {
+ result = "str key remove failed";
+ goto done;
+ }
qd_hash_handle_free(handles[i]);
}
+done:
+ qd_iterator_free(i_key);
qd_hash_free(hash);
- return 0;
+ return result;
}
@@ -93,7 +109,8 @@ static char *test_iter_keys(void *context)
//
static char *test_str_keys(void *context)
{
-
+ char *result = 0;
+ qd_iterator_t *i_key = 0;
qd_hash_handle_t *handles[key_count];
qd_hash_t *hash = qd_hash(4, 10, false);
if (!hash)
@@ -103,36 +120,53 @@ static char *test_str_keys(void *context)
const unsigned char *key = keys[i];
qd_hash_handle_t **handle = &handles[i];
- if (qd_hash_insert_str(hash, key, (void *)key, handle) != QD_ERROR_NONE)
- return "hash table insert failed";
+ if (qd_hash_insert_str(hash, key, (void *)key, handle) != QD_ERROR_NONE) {
+ result = "hash table insert failed";
+ goto done;
+ }
- if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
- return "hash handle key did not match";
+ if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0) {
+ result = "hash handle key did not match";
+ goto done;
+ }
}
- if (qd_hash_size(hash) != key_count)
- return "hash size is incorrect";
+ if (qd_hash_size(hash) != key_count) {
+ result = "hash size is incorrect";
+ goto done;
+ }
for (int i = 0; i < key_count; ++i) {
- qd_iterator_t *i_key = qd_iterator_string((const char *)keys[i], ITER_VIEW_ALL);
+ i_key = qd_iterator_string((const char *)keys[i], ITER_VIEW_ALL);
unsigned char *value;
- if (qd_hash_retrieve(hash, i_key, (void **)&value) != QD_ERROR_NONE)
- return "Iterator key lookup failed";
- if (strcmp((const char *)value, (const char *)keys[i]) != 0)
- return "key value mismatch";
+ if (qd_hash_retrieve(hash, i_key, (void **)&value) != QD_ERROR_NONE) {
+ result = "Iterator key lookup failed";
+ goto done;
+ }
+
+ if (strcmp((const char *)value, (const char *)keys[i]) != 0) {
+ result = "key value mismatch";
+ goto done;
+ }
qd_iterator_free(i_key);
+ i_key = 0;
}
for (int i = 0; i < key_count; ++i) {
- qd_iterator_t *i_key = qd_iterator_string((const char *)keys[i], ITER_VIEW_ALL);
- if (qd_hash_remove(hash, i_key) != QD_ERROR_NONE)
- return "str key remove failed";
+ i_key = qd_iterator_string((const char *)keys[i], ITER_VIEW_ALL);
+ if (qd_hash_remove(hash, i_key) != QD_ERROR_NONE) {
+ result = "str key remove failed";
+ goto done;
+ }
qd_hash_handle_free(handles[i]);
qd_iterator_free(i_key);
+ i_key = 0;
}
+done:
+ qd_iterator_free(i_key);
qd_hash_free(hash);
- return 0;
+ return result;
}
@@ -140,7 +174,8 @@ static char *test_str_keys(void *context)
//
static char *test_iter_bad(void *context)
{
-
+ char *result = 0;
+ qd_iterator_t *i_key = 0;
qd_hash_handle_t *handles[key_count];
qd_hash_t *hash = qd_hash(4, 10, false);
if (!hash)
@@ -150,45 +185,59 @@ static char *test_iter_bad(void *context)
const unsigned char *key = keys[i];
qd_hash_handle_t **handle = &handles[i];
- qd_iterator_t *i_key = qd_iterator_string((const char *)key, ITER_VIEW_ALL);
- if (qd_hash_insert(hash, i_key, (void *)key, handle) != QD_ERROR_NONE)
- return "hash table insert failed";
-
- if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
- return "hash handle key did not match";
+ i_key = qd_iterator_string((const char *)key, ITER_VIEW_ALL);
+ if (qd_hash_insert(hash, i_key, (void *)key, handle) != QD_ERROR_NONE) {
+ result = "hash table insert failed";
+ goto done;
+ }
+ if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0) {
+ result = "hash handle key did not match";
+ goto done;
+ }
qd_iterator_free(i_key);
+ i_key = 0;
}
- if (qd_hash_size(hash) != key_count)
- return "hash size is incorrect";
+ if (qd_hash_size(hash) != key_count) {
+ result = "hash size is incorrect";
+ goto done;
+ }
- qd_iterator_t *i_key = qd_iterator_string((const char *)"I DO NOT EXIST", ITER_VIEW_ALL);
+ i_key = qd_iterator_string((const char *)"I DO NOT EXIST", ITER_VIEW_ALL);
void *value = (void *)i_key; // just a non-zero value
// key not found
qd_hash_retrieve(hash, i_key, &value); // does not return error code, but sets value to 0
- if (value != 0)
- return "expected hash retrieve to find nothing";
+ if (value != 0) {
+ result = "expected hash retrieve to find nothing";
+ goto done;
+ }
// remove should return error
- if (qd_hash_remove(hash, i_key) != QD_ERROR_NOT_FOUND)
- return "expected hash remove to fail (not found)";
+ if (qd_hash_remove(hash, i_key) != QD_ERROR_NOT_FOUND) {
+ result = "expected hash remove to fail (not found)";
+ goto done;
+ }
qd_iterator_free(i_key);
+ i_key = 0;
// cleanup
for (int i = 0; i < key_count; ++i) {
const unsigned char *key = keys[i];
-
- if (qd_hash_remove_str(hash, key) != QD_ERROR_NONE)
- return "str key remove failed";
+ if (qd_hash_remove_str(hash, key) != QD_ERROR_NONE) {
+ result = "str key remove failed";
+ goto done;
+ }
qd_hash_handle_free(handles[i]);
}
+done:
+ qd_iterator_free(i_key);
qd_hash_free(hash);
- return 0;
+ return result;
}
@@ -196,7 +245,7 @@ static char *test_iter_bad(void *context)
//
static char *test_str_bad(void *context)
{
-
+ char *result = 0;
qd_hash_handle_t *handles[key_count];
qd_hash_t *hash = qd_hash(4, 10, false);
if (!hash)
@@ -206,40 +255,53 @@ static char *test_str_bad(void *context)
const unsigned char *key = keys[i];
qd_hash_handle_t **handle = &handles[i];
- if (qd_hash_insert_str(hash, key, (void *)key, handle) != QD_ERROR_NONE)
- return "hash table insert failed";
+ if (qd_hash_insert_str(hash, key, (void *)key, handle) != QD_ERROR_NONE) {
+ result = "hash table insert failed";
+ goto done;
+ }
- if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
- return "hash handle key did not match";
+ if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0) {
+ result = "hash handle key did not match";
+ goto done;
+ }
}
- if (qd_hash_size(hash) != key_count)
- return "hash size is incorrect";
+ if (qd_hash_size(hash) != key_count) {
+ result = "hash size is incorrect";
+ goto done;
+ }
const unsigned char *key = (const unsigned char *) "I DO NOT EXIST";
void *value = (void *)key; // just a non-zero value
// key not found
qd_hash_retrieve_str(hash, key, &value); // does not return error code, but sets value to 0
- if (value != 0)
- return "expected hash retrieve to find nothing";
+ if (value != 0) {
+ result = "expected hash retrieve to find nothing";
+ goto done;
+ }
// remove should return error
- if (qd_hash_remove_str(hash, key) != QD_ERROR_NOT_FOUND)
- return "expected hash remove to fail (not found)";
+ if (qd_hash_remove_str(hash, key) != QD_ERROR_NOT_FOUND) {
+ result = "expected hash remove to fail (not found)";
+ goto done;
+ }
// cleanup
for (int i = 0; i < key_count; ++i) {
key = keys[i];
- if (qd_hash_remove_str(hash, key) != QD_ERROR_NONE)
- return "str key remove failed";
+ if (qd_hash_remove_str(hash, key) != QD_ERROR_NONE) {
+ result = "str key remove failed";
+ goto done;
+ }
qd_hash_handle_free(handles[i]);
}
+done:
qd_hash_free(hash);
- return 0;
+ return result;
}
diff --git a/tests/parse_tree_tests.c b/tests/parse_tree_tests.c
index 50b1741..123e76b 100644
--- a/tests/parse_tree_tests.c
+++ b/tests/parse_tree_tests.c
@@ -133,6 +133,12 @@ static char *test_add_and_match_str(void *context)
return "Failed to get expected match (2)";
}
+ if (qd_parse_tree_retrieve_match_str(node, "I", &payload) ||
+ qd_parse_tree_retrieve_match_str(node, "I.am", &payload)) {
+ qd_parse_tree_free(node);
+ return "Should not match part of a pattern";
+ }
+
if (qd_parse_tree_retrieve_match_str(node, "notSoFast", &payload)) {
qd_parse_tree_free(node);
return "Match pattern should not match but did match";
@@ -354,7 +360,6 @@ static char *test_normalization(void *context)
char *rc = NULL;
char *patterns[][2] = {
// normalized raw
- {"", ""},
{"a.b.c", "a.b.c"},
{"a.*.c", "a.*.c"},
{"#", "#"},
@@ -390,7 +395,7 @@ static char *match_test(qd_parse_tree_type_t type,
if (qd_parse_tree_add_pattern(node, piter, payload)) {
qd_parse_tree_free(node);
qd_iterator_free(piter);
- return "Unexpected payload when adding pattern";
+ return "Unexpected error when adding pattern";
}
for (int i = 0; tests[i].address && !rc; i++) {
@@ -429,20 +434,6 @@ static char *test_matches(void *context)
char *rc = match_test(QD_PARSE_TREE_ADDRESS, "ab.cd.e", test1);
if (rc) return rc;
- match_test_t test2[] = {
- {"", true},
- {NULL, false},
- };
- rc = match_test(QD_PARSE_TREE_ADDRESS, "", test2);
- if (rc) return rc;
-
- match_test_t test3[] = {
- {".", true},
- {NULL, false},
- };
- rc = match_test(QD_PARSE_TREE_ADDRESS, ".", test3);
- if (rc) return rc;
-
match_test_t test4[] = {
{"a.xx.b", true},
{"a.b", false},
@@ -795,7 +786,10 @@ static char *test_validation(void *context)
{
qd_iterator_t *iter = qd_iterator_string("sam.*.am.#", ITER_VIEW_ALL);
qd_iterator_t *iter_good = qd_iterator_string("sam/+/a.#.m/#", ITER_VIEW_ALL);
- qd_iterator_t *iter_bad = qd_iterator_string("sam/#/am/+", ITER_VIEW_ALL);
+ qd_iterator_t *iter_bad = qd_iterator_string("", ITER_VIEW_ALL); // no tokens
+ qd_iterator_t *iter_bad_slash = qd_iterator_string("/", ITER_VIEW_ALL); // just separators
+ qd_iterator_t *iter_bad_dot = qd_iterator_string(".", ITER_VIEW_ALL); // just separators
+ qd_iterator_t *iter_bad_mqtt = qd_iterator_string("sam/#/am/+", ITER_VIEW_ALL); // glob must be last
qd_iterator_t *iter_const = qd_iterator_string("sam/I/am", ITER_VIEW_ALL);
qd_parse_tree_t *mqtt_tree = qd_parse_tree_new(QD_PARSE_TREE_MQTT);
qd_parse_tree_t *addr_tree = qd_parse_tree_new(QD_PARSE_TREE_ADDRESS);
@@ -805,7 +799,28 @@ static char *test_validation(void *context)
if (!qd_parse_tree_validate_pattern(addr_tree, iter) ||
!qd_parse_tree_validate_pattern(amqp_tree, iter)) {
- error = "expected to skip validation";
+ error = "expected valid pattern";
+ goto cleanup;
+ }
+
+
+ if (qd_parse_tree_validate_pattern(addr_tree, iter_bad) ||
+ qd_parse_tree_validate_pattern(mqtt_tree, iter_bad) ||
+ qd_parse_tree_validate_pattern(amqp_tree, iter_bad)) {
+ error = "expected null pattern to be invalid";
+ goto cleanup;
+ }
+
+
+ if (qd_parse_tree_validate_pattern(addr_tree, iter_bad_dot) ||
+ qd_parse_tree_validate_pattern(amqp_tree, iter_bad_dot)) {
+ error = "expected separator dot pattern to be invalid";
+ goto cleanup;
+ }
+
+ if (qd_parse_tree_validate_pattern(addr_tree, iter_bad_slash) ||
+ qd_parse_tree_validate_pattern(mqtt_tree, iter_bad_slash)) {
+ error = "expected separator slash pattern to be invalid";
goto cleanup;
}
@@ -814,7 +829,7 @@ static char *test_validation(void *context)
goto cleanup;
}
- if (qd_parse_tree_validate_pattern(mqtt_tree, iter_bad)) {
+ if (qd_parse_tree_validate_pattern(mqtt_tree, iter_bad_mqtt)) {
error = "expected to fail mqtt validation";
goto cleanup;
}
@@ -828,6 +843,9 @@ cleanup:
qd_iterator_free(iter);
qd_iterator_free(iter_good);
qd_iterator_free(iter_bad);
+ qd_iterator_free(iter_bad_slash);
+ qd_iterator_free(iter_bad_dot);
+ qd_iterator_free(iter_bad_mqtt);
qd_iterator_free(iter_const);
qd_parse_tree_free(mqtt_tree);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org