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:29 UTC
[qpid-dispatch] branch master updated (ef80c75 -> 0853244)
This is an automated email from the ASF dual-hosted git repository.
kgiusti pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/qpid-dispatch.git.
from ef80c75 NO-JIRA Update dependency versions to fix sourceclear high and medium warnings.
new 64a84e9 DISPATCH-1682: add string based hash keys
new 0853244 DISPATCH-1682: Augment parse tree with hash table lookup
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
include/qpid/dispatch/hash.h | 9 +
include/qpid/dispatch/iterator.h | 5 +
src/hash.c | 136 ++++++-
src/iterator.c | 19 +-
src/parse_tree.c | 744 +++++++++++++++++++++++----------------
src/parse_tree.h | 2 +-
src/policy.c | 1 +
tests/CMakeLists.txt | 1 +
tests/hash_test.c | 319 +++++++++++++++++
tests/parse_tree_tests.c | 56 ++-
tests/run_unit_tests.c | 3 +
11 files changed, 959 insertions(+), 336 deletions(-)
create mode 100644 tests/hash_test.c
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org
[qpid-dispatch] 01/02: DISPATCH-1682: add string based hash keys
Posted by kg...@apache.org.
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 64a84e944837869cd8888e1006ffe188d3fd8900
Author: Kenneth Giusti <kg...@apache.org>
AuthorDate: Wed Jun 3 10:23:34 2020 -0400
DISPATCH-1682: add string based hash keys
---
include/qpid/dispatch/hash.h | 9 ++
src/hash.c | 136 ++++++++++++++++++++---
src/iterator.c | 8 +-
tests/CMakeLists.txt | 1 +
tests/hash_test.c | 257 +++++++++++++++++++++++++++++++++++++++++++
tests/run_unit_tests.c | 3 +
6 files changed, 395 insertions(+), 19 deletions(-)
diff --git a/include/qpid/dispatch/hash.h b/include/qpid/dispatch/hash.h
index 7b9b3ec..b9761c1 100644
--- a/include/qpid/dispatch/hash.h
+++ b/include/qpid/dispatch/hash.h
@@ -27,6 +27,9 @@
#include <qpid/dispatch/iterator.h>
#include <qpid/dispatch/error.h>
+#define HASH_INIT ((uint32_t) 5381)
+#define HASH_COMPUTE(HASH, OCTET) ((((HASH)<<5) + (HASH)) + (uint32_t)(OCTET)) // hash * 33 + octet
+
typedef struct qd_hash_t qd_hash_t;
typedef struct qd_hash_handle_t qd_hash_handle_t;
@@ -34,11 +37,17 @@ qd_hash_t *qd_hash(int bucket_exponent, int batch_size, int value_is_const);
void qd_hash_free(qd_hash_t *h);
size_t qd_hash_size(qd_hash_t *h);
+
qd_error_t qd_hash_insert(qd_hash_t *h, qd_iterator_t *key, void *val, qd_hash_handle_t **handle);
qd_error_t qd_hash_insert_const(qd_hash_t *h, qd_iterator_t *key, const void *val, qd_hash_handle_t **handle);
+qd_error_t qd_hash_insert_str(qd_hash_t *h, const unsigned char *key, void *val, qd_hash_handle_t **handle);
+
qd_error_t qd_hash_retrieve(qd_hash_t *h, qd_iterator_t *key, void **val);
qd_error_t qd_hash_retrieve_const(qd_hash_t *h, qd_iterator_t *key, const void **val);
+qd_error_t qd_hash_retrieve_str(qd_hash_t *h, const unsigned char *key, void **val);
+
qd_error_t qd_hash_remove(qd_hash_t *h, qd_iterator_t *key);
+qd_error_t qd_hash_remove_str(qd_hash_t *h, const unsigned char *key);
void qd_hash_handle_free(qd_hash_handle_t *handle);
const unsigned char *qd_hash_key_by_handle(const qd_hash_handle_t *handle);
diff --git a/src/hash.c b/src/hash.c
index 89c2016..35293e6 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -63,6 +63,24 @@ ALLOC_DECLARE(qd_hash_handle_t);
ALLOC_DEFINE(qd_hash_handle_t);
+static bucket_t *qd_hash_get_bucket_iter(qd_hash_t *h, qd_iterator_t *key)
+{
+ uint32_t idx = qd_iterator_hash_view(key) & h->bucket_mask;
+ return &h->buckets[idx];
+}
+
+
+static bucket_t *qd_hash_get_bucket_str(qd_hash_t *h, const unsigned char *key)
+{
+ uint32_t hash = HASH_INIT;
+ while (*key) {
+ hash = HASH_COMPUTE(hash, *key++);
+ }
+
+ return &h->buckets[(hash & h->bucket_mask)];
+}
+
+
qd_hash_t *qd_hash(int bucket_exponent, int batch_size, int value_is_const)
{
int i;
@@ -120,13 +138,13 @@ size_t qd_hash_size(qd_hash_t *h)
}
-static qd_hash_item_t *qd_hash_internal_insert(qd_hash_t *h, qd_iterator_t *key, int *exists, qd_hash_handle_t **handle)
+// ownership of key is transfered to the qd_hash_item_t
+static qd_hash_item_t *qd_hash_internal_insert(qd_hash_t *h, bucket_t *bucket, unsigned char *key, int *exists, qd_hash_handle_t **handle)
{
- unsigned long idx = qd_iterator_hash_view(key) & h->bucket_mask;
- qd_hash_item_t *item = DEQ_HEAD(h->buckets[idx].items);
+ qd_hash_item_t *item = DEQ_HEAD(bucket->items);
while (item) {
- if (qd_iterator_equal(key, item->key))
+ if (strcmp((const char *) key, (const char *) item->key) == 0)
break;
item = DEQ_NEXT(item);
}
@@ -143,9 +161,9 @@ static qd_hash_item_t *qd_hash_internal_insert(qd_hash_t *h, qd_iterator_t *key,
return 0;
DEQ_ITEM_INIT(item);
- item->key = qd_iterator_copy(key);
+ item->key = key;
- DEQ_INSERT_TAIL(h->buckets[idx].items, item);
+ DEQ_INSERT_TAIL(bucket->items, item);
h->size++;
*exists = 0;
@@ -154,7 +172,7 @@ static qd_hash_item_t *qd_hash_internal_insert(qd_hash_t *h, qd_iterator_t *key,
//
if (handle) {
*handle = new_qd_hash_handle_t();
- (*handle)->bucket = &h->buckets[idx];
+ (*handle)->bucket = bucket;
(*handle)->item = item;
}
@@ -164,14 +182,24 @@ static qd_hash_item_t *qd_hash_internal_insert(qd_hash_t *h, qd_iterator_t *key,
qd_error_t qd_hash_insert(qd_hash_t *h, qd_iterator_t *key, void *val, qd_hash_handle_t **handle)
{
- int exists = 0;
- qd_hash_item_t *item = qd_hash_internal_insert(h, key, &exists, handle);
+ int exists = 0;
+ bucket_t *bucket = qd_hash_get_bucket_iter(h, key);
+ unsigned char *k = qd_iterator_copy(key);
- if (!item)
+ if (!k)
+ return QD_ERROR_ALLOC;
+
+ qd_hash_item_t *item = qd_hash_internal_insert(h, bucket, k, &exists, handle);
+
+ if (!item) {
+ free(k);
return QD_ERROR_ALLOC;
+ }
- if (exists)
+ if (exists) {
+ free(k);
return QD_ERROR_ALREADY_EXISTS;
+ }
item->v.val = val;
@@ -183,14 +211,24 @@ qd_error_t qd_hash_insert_const(qd_hash_t *h, qd_iterator_t *key, const void *va
{
assert(h->is_const);
- int exists = 0;
- qd_hash_item_t *item = qd_hash_internal_insert(h, key, &exists, handle);
+ int exists = 0;
+ bucket_t *bucket = qd_hash_get_bucket_iter(h, key);
+ unsigned char *k = qd_iterator_copy(key);
- if (!item)
+ if (!k)
return QD_ERROR_ALLOC;
- if (exists)
+ qd_hash_item_t *item = qd_hash_internal_insert(h, bucket, k, &exists, handle);
+
+ if (!item) {
+ free(k);
+ return QD_ERROR_ALLOC;
+ }
+
+ if (exists) {
+ free(k);
return QD_ERROR_ALREADY_EXISTS;
+ }
item->v.val_const = val;
@@ -198,6 +236,33 @@ qd_error_t qd_hash_insert_const(qd_hash_t *h, qd_iterator_t *key, const void *va
}
+qd_error_t qd_hash_insert_str(qd_hash_t *h, const unsigned char *key, void *val, qd_hash_handle_t **handle)
+{
+ int exists = 0;
+ bucket_t *bucket = qd_hash_get_bucket_str(h, key);
+ unsigned char *k = (unsigned char *) strdup((const char *) key);
+
+ if (!k)
+ return QD_ERROR_ALLOC;
+
+ qd_hash_item_t *item = qd_hash_internal_insert(h, bucket, k, &exists, handle);
+
+ if (!item) {
+ free(k);
+ return QD_ERROR_ALLOC;
+ }
+
+ if (exists) {
+ free(k);
+ return QD_ERROR_ALREADY_EXISTS;
+ }
+
+ item->v.val = val;
+
+ return QD_ERROR_NONE;
+}
+
+
static qd_hash_item_t *qd_hash_internal_retrieve_with_hash(qd_hash_t *h, uint32_t hash, qd_iterator_t *key)
{
uint32_t idx = hash & h->bucket_mask;
@@ -296,6 +361,35 @@ qd_error_t qd_hash_retrieve_const(qd_hash_t *h, qd_iterator_t *key, const void *
}
+static qd_hash_item_t *qd_hash_internal_get_item_str(qd_hash_t *h, bucket_t *bucket, const unsigned char *key)
+{
+ qd_hash_item_t *item = DEQ_HEAD(bucket->items);
+
+ while (item) {
+ if (strcmp((const char *) key, (const char *) item->key) == 0) {
+ return item;
+ }
+ item = DEQ_NEXT(item);
+ }
+
+ return 0;
+}
+
+
+qd_error_t qd_hash_retrieve_str(qd_hash_t *h, const unsigned char *key, void **val)
+{
+ qd_hash_item_t *item = qd_hash_internal_get_item_str(h,
+ qd_hash_get_bucket_str(h, key),
+ key);
+ if (item) {
+ *val = item->v.val;
+ } else {
+ *val = 0;
+ }
+ return QD_ERROR_NONE;
+}
+
+
qd_error_t qd_hash_remove(qd_hash_t *h, qd_iterator_t *key)
{
//the retrieve function will re-apply the bucket_mask, but that is ok
@@ -310,6 +404,18 @@ qd_error_t qd_hash_remove(qd_hash_t *h, qd_iterator_t *key)
}
+qd_error_t qd_hash_remove_str(qd_hash_t *h, const unsigned char *key)
+{
+ bucket_t *bucket = qd_hash_get_bucket_str(h, key);
+ qd_hash_item_t *item = qd_hash_internal_get_item_str(h, bucket, key);
+ if (!item)
+ return QD_ERROR_NOT_FOUND;
+
+ qd_hash_internal_remove_item(h, bucket, item, 0);
+ return QD_ERROR_NONE;
+}
+
+
void qd_hash_handle_free(qd_hash_handle_t *handle)
{
if (handle)
diff --git a/src/iterator.c b/src/iterator.c
index 3fb2cd9..ff43a15 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -21,6 +21,7 @@
#include <qpid/dispatch/ctools.h>
#include <qpid/dispatch/alloc.h>
#include <qpid/dispatch/amqp.h>
+#include <qpid/dispatch/hash.h>
#include "message_private.h"
#include <stdio.h>
#include <string.h>
@@ -86,7 +87,6 @@ static char *my_area = "";
static char *my_router = "";
static const char *SEPARATORS = "./";
-static const uint32_t HASH_INIT = 5381;
// returns true if the current iterator view has no transformations and is
@@ -1038,7 +1038,7 @@ uint32_t qd_iterator_hash_view(qd_iterator_t *iter)
qd_iterator_reset(iter);
while (!iterator_at_end(iter))
- hash = ((hash << 5) + hash) + (uint32_t) qd_iterator_octet(iter); /* hash * 33 + c */
+ hash = HASH_COMPUTE(hash, qd_iterator_octet(iter));
return hash;
}
@@ -1048,7 +1048,7 @@ void qd_iterator_hash_view_segments(qd_iterator_t *iter)
{
if (!iter)
return;
-
+
// Reset the pointers in the iterator
qd_iterator_reset(iter);
uint32_t hash = HASH_INIT;
@@ -1066,7 +1066,7 @@ void qd_iterator_hash_view_segments(qd_iterator_t *iter)
qd_insert_hash_segment(iter, &hash, segment_length-1);
}
- hash = ((hash << 5) + hash) + octet; /* hash * 33 + c */
+ hash = HASH_COMPUTE(hash, octet);
}
// Segments should never end with a separator. see view_initialize which in turn calls
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index a12eb93..b7bd2c2 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -37,6 +37,7 @@ set(unit_test_SOURCES
proton_utils_tests.c
alloc_test.c
version_test.c
+ hash_test.c
)
add_executable(unit_tests ${unit_test_SOURCES})
diff --git a/tests/hash_test.c b/tests/hash_test.c
new file mode 100644
index 0000000..5ea8a80
--- /dev/null
+++ b/tests/hash_test.c
@@ -0,0 +1,257 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#include "test_case.h"
+#include <stdio.h>
+#include <string.h>
+#include <qpid/dispatch/iterator.h>
+#include <qpid/dispatch/hash.h>
+
+
+
+static const unsigned char *keys[] = {
+ (const unsigned char *) "/global/foo",
+ (const unsigned char *) "non-address key",
+ (const unsigned char *) "amqp://host/global/sub",
+ (const unsigned char *) "",
+};
+
+static const int key_count = sizeof(keys)/sizeof(keys[0]);
+
+
+// add using iterator key, lookup and remove using string key
+//
+static char *test_iter_keys(void *context)
+{
+
+ qd_hash_handle_t *handles[key_count];
+ qd_hash_t *hash = qd_hash(4, 10, false);
+ if (!hash)
+ return "hash table allocation failed";
+
+ //
+ // 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";
+
+ if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
+ return "hash handle key did not match";
+
+ qd_iterator_free(i_key);
+ }
+
+ if (qd_hash_size(hash) != key_count)
+ return "hash size is incorrect";
+
+ 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";
+ }
+
+ 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";
+ qd_hash_handle_free(handles[i]);
+ }
+
+ qd_hash_free(hash);
+ return 0;
+}
+
+
+// add using string key, lookup and remove using iterator key
+//
+static char *test_str_keys(void *context)
+{
+
+ qd_hash_handle_t *handles[key_count];
+ qd_hash_t *hash = qd_hash(4, 10, false);
+ if (!hash)
+ return "hash table allocation failed";
+
+ for (int i = 0; i < key_count; ++i) {
+ 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 (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
+ return "hash handle key did not match";
+ }
+
+ if (qd_hash_size(hash) != key_count)
+ return "hash size is incorrect";
+
+ for (int i = 0; i < key_count; ++i) {
+ qd_iterator_t *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";
+ qd_iterator_free(i_key);
+ }
+
+ 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";
+ qd_hash_handle_free(handles[i]);
+ qd_iterator_free(i_key);
+ }
+
+ qd_hash_free(hash);
+ return 0;
+}
+
+
+// test lookup and remove failures using iterators
+//
+static char *test_iter_bad(void *context)
+{
+
+ qd_hash_handle_t *handles[key_count];
+ qd_hash_t *hash = qd_hash(4, 10, false);
+ if (!hash)
+ return "hash table allocation failed";
+
+ 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";
+
+ if (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
+ return "hash handle key did not match";
+
+ qd_iterator_free(i_key);
+ }
+
+ if (qd_hash_size(hash) != key_count)
+ return "hash size is incorrect";
+
+ qd_iterator_t *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";
+
+ // remove should return error
+ if (qd_hash_remove(hash, i_key) != QD_ERROR_NOT_FOUND)
+ return "expected hash remove to fail (not found)";
+
+ qd_iterator_free(i_key);
+
+ // 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";
+ qd_hash_handle_free(handles[i]);
+ }
+
+ qd_hash_free(hash);
+ return 0;
+}
+
+
+// test lookup and remove failures using strings
+//
+static char *test_str_bad(void *context)
+{
+
+ qd_hash_handle_t *handles[key_count];
+ qd_hash_t *hash = qd_hash(4, 10, false);
+ if (!hash)
+ return "hash table allocation failed";
+
+ for (int i = 0; i < key_count; ++i) {
+ 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 (strcmp((const char *) qd_hash_key_by_handle(*handle), (const char *)key) != 0)
+ return "hash handle key did not match";
+ }
+
+ if (qd_hash_size(hash) != key_count)
+ return "hash size is incorrect";
+
+ 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";
+
+ // remove should return error
+ if (qd_hash_remove_str(hash, key) != QD_ERROR_NOT_FOUND)
+ return "expected hash remove to fail (not found)";
+
+ // 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";
+ qd_hash_handle_free(handles[i]);
+ }
+
+ qd_hash_free(hash);
+ return 0;
+}
+
+
+int hash_tests(void)
+{
+ int result = 0;
+ char *test_group = "hash_tests";
+
+ TEST_CASE(test_iter_keys, 0);
+ TEST_CASE(test_str_keys, 0);
+ TEST_CASE(test_iter_bad, 0);
+ TEST_CASE(test_str_bad, 0);
+
+ return result;
+}
diff --git a/tests/run_unit_tests.c b/tests/run_unit_tests.c
index 08c75e3..cbd0e3a 100644
--- a/tests/run_unit_tests.c
+++ b/tests/run_unit_tests.c
@@ -32,6 +32,8 @@ int failoverlist_tests(void);
int parse_tree_tests(void);
int proton_utils_tests(void);
int version_tests(void);
+int hash_tests(void);
+
int main(int argc, char** argv)
{
@@ -65,6 +67,7 @@ int main(int argc, char** argv)
result += proton_utils_tests();
result += core_timer_tests();
result += version_tests();
+ result += hash_tests();
qd_dispatch_free(qd); // dispatch_free last.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@qpid.apache.org
For additional commands, e-mail: commits-help@qpid.apache.org
[qpid-dispatch] 02/02: DISPATCH-1682: Augment parse tree with hash
table lookup
Posted by kg...@apache.org.
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