Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
include/qb/qbmap.h | 9 ++++++++
lib/hashtable.c | 2 +-
lib/map.c | 8 ++++++-
lib/map_int.h | 10 ++++++--
lib/skiplist.c | 2 +-
lib/trie.c | 37 ++++++++++++++++++++++++---------
tests/check_map.c | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++
7 files changed, 109 insertions(+), 16 deletions(-)
diff --git a/include/qb/qbmap.h b/include/qb/qbmap.h
index a99ba2a..51e2212 100644
--- a/include/qb/qbmap.h
+++ b/include/qb/qbmap.h
@@ -126,6 +126,15 @@ void qb_map_foreach(qb_map_t *map, qb_transverse_func func, void*
user_data);
qb_map_iter_t* qb_map_iter_create(qb_map_t *map);
/**
+ * Create a prefix iterator.
+ *
+ * This will iterate over all items with the given
+ * prefix.
+ * @note this is only supported by the trie.
+ */
+qb_map_iter_t* qb_map_pref_iter_create(qb_map_t *map, const char* prefix);
+
+/**
* Get the next item
*
* @param i the iterator
diff --git a/lib/hashtable.c b/lib/hashtable.c
index b17e02f..d45badf 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -181,7 +181,7 @@ hashtable_count_get(struct qb_map *map)
}
static qb_map_iter_t*
-hashtable_iter_create(struct qb_map * map)
+hashtable_iter_create(struct qb_map * map, const char* prefix)
{
struct hashtable_iter *i = malloc(sizeof(struct hashtable_iter));
i->i.m = map;
diff --git a/lib/map.c b/lib/map.c
index 2d356b4..a3b9466 100644
--- a/lib/map.c
+++ b/lib/map.c
@@ -68,7 +68,13 @@ clean_up:
qb_map_iter_t*
qb_map_iter_create(struct qb_map *map)
{
- return map->iter_create(map);
+ return map->iter_create(map, NULL);
+}
+
+qb_map_iter_t*
+qb_map_pref_iter_create(qb_map_t *map, const char* prefix)
+{
+ return map->iter_create(map, prefix);
}
const char*
diff --git a/lib/map_int.h b/lib/map_int.h
index 46bb67c..f9cdd16 100644
--- a/lib/map_int.h
+++ b/lib/map_int.h
@@ -23,13 +23,17 @@
struct qb_map;
-typedef void (*qb_map_put_func)(struct qb_map *map, const char* key, const void* value);
+typedef void (*qb_map_put_func)(struct qb_map *map, const char* key,
+ const void* value);
typedef void* (*qb_map_get_func)(struct qb_map *map, const char* key);
typedef int32_t (*qb_map_rm_func)(struct qb_map *map, const char* key);
typedef size_t (*qb_map_count_get_func)(struct qb_map *map);
-typedef void (*qb_map_foreach_func)(struct qb_map *map, qb_transverse_func func, void*
user_data);
+typedef void (*qb_map_foreach_func)(struct qb_map *map,
+ qb_transverse_func func,
+ void* user_data);
typedef void (*qb_map_destroy_func)(struct qb_map *map);
-typedef qb_map_iter_t* (*qb_map_iter_create_func)(struct qb_map *map);
+typedef qb_map_iter_t* (*qb_map_iter_create_func)(struct qb_map *map,
+ const char* prefix);
typedef const char* (*qb_map_iter_next_func)(qb_map_iter_t* i, void** value);
typedef void (*qb_map_iter_free_func)(qb_map_iter_t* i);
diff --git a/lib/skiplist.c b/lib/skiplist.c
index 42c0e7f..b11d211 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -338,7 +338,7 @@ skiplist_get(struct qb_map *map, const char *key)
}
static qb_map_iter_t*
-skiplist_iter_create(struct qb_map * map)
+skiplist_iter_create(struct qb_map * map, const char* prefix)
{
struct skiplist_iter *i = malloc(sizeof(struct skiplist_iter));
struct skiplist *list = (struct skiplist *)map;
diff --git a/lib/trie.c b/lib/trie.c
index 2000953..fd50e94 100644
--- a/lib/trie.c
+++ b/lib/trie.c
@@ -27,8 +27,9 @@
struct trie_iter {
struct qb_map_iter i;
- const char *key;
+ const char *prefix;
struct trie_node *n;
+ struct trie_node *root;
};
struct trie_node {
@@ -57,7 +58,7 @@ static int32_t trie_rm(struct qb_map *list, const char *key);
#define TRIE_CHAR2INDEX(ch) (126 - ch)
static struct trie_node *
-trie_node_next(struct trie_node *node)
+trie_node_next(struct trie_node *node, struct trie_node *root)
{
struct trie_node *c = node;
struct trie_node *n;
@@ -83,7 +84,7 @@ keep_going:
}
}
// sibling/parent
- if (c->parent == NULL) {
+ if (c == root) {
return NULL;
}
p = c;
@@ -97,13 +98,13 @@ keep_going:
if (n == NULL) {
p = p->parent;
}
- } while (n == NULL && p->parent);
+ } while (n == NULL && p != root);
if (n) {
if (n->value) {
return n;
}
- if (n->parent == NULL) {
+ if (n == root) {
return NULL;
}
c = n;
@@ -260,12 +261,14 @@ trie_get(struct qb_map *map, const char *key)
}
static qb_map_iter_t*
-trie_iter_create(struct qb_map * map)
+trie_iter_create(struct qb_map * map, const char* prefix)
{
struct trie_iter *i = malloc(sizeof(struct trie_iter));
- struct trie *list = (struct trie *)map;
+ struct trie *t = (struct trie *)map;
i->i.m = map;
- i->n = list->header;
+ i->prefix = prefix;
+ i->n = t->header;
+ i->root = t->header;
i->n->refcount++;
return (qb_map_iter_t*)i;
}
@@ -275,16 +278,30 @@ trie_iter_next(qb_map_iter_t* i, void** value)
{
struct trie_iter *si = (struct trie_iter*)i;
struct trie_node *p = si->n;
+ struct trie *t = (struct trie *)(i->m);
if (p == NULL) {
return NULL;
}
- si->n = trie_node_next(p);
- trie_node_deref((struct trie *)i->m, p);
+
+ if (p->parent == NULL && si->prefix) {
+ si->root = trie_lookup(t, si->prefix, QB_FALSE);
+ if (si->root == NULL) {
+ si->n = NULL;
+ } else if (si->root->value == NULL) {
+ si->n = trie_node_next(si->root, si->root);
+ } else {
+ si->n = si->root;
+ }
+ } else {
+ si->n = trie_node_next(p, si->root);
+ }
if (si->n == NULL) {
+ trie_node_deref((struct trie *)i->m, p);
return NULL;
}
si->n->refcount++;
+ trie_node_deref((struct trie *)i->m, p);
*value = si->n->value;
return si->n->key;
}
diff --git a/tests/check_map.c b/tests/check_map.c
index e2022c3..2665622 100644
--- a/tests/check_map.c
+++ b/tests/check_map.c
@@ -325,6 +325,61 @@ test_map_iter_safety(qb_map_t *m, int32_t ordered)
qb_map_destroy(m);
}
+static void
+test_map_iter_prefix(qb_map_t *m)
+{
+ void *data;
+ const char *p;
+ qb_map_iter_t *it;
+ int count;
+
+ qb_map_put(m, "aaaa", "aye");
+ qb_map_put(m, "facc", "nope");
+ qb_map_put(m, "abbb", "bee");
+ qb_map_put(m, "a.ac", "nope");
+ qb_map_put(m, "aacc", "yip");
+ qb_map_put(m, "cacc", "nope");
+ qb_map_put(m, "c", "----");
+
+ count = 0;
+ it = qb_map_pref_iter_create(m, "aa");
+ while ((p = qb_map_iter_next(it, &data)) != NULL) {
+ printf("1: %s == %s\n", p, (char*)data);
+ count++;
+ }
+ qb_map_iter_free(it);
+ ck_assert_int_eq(count, 2);
+
+ count = 0;
+ it = qb_map_pref_iter_create(m, "a");
+ while ((p = qb_map_iter_next(it, &data)) != NULL) {
+ printf("2: %s == %s\n", p, (char*)data);
+ count++;
+ }
+ qb_map_iter_free(it);
+ ck_assert_int_eq(count, 4);
+
+ count = 0;
+ it = qb_map_pref_iter_create(m, "zz");
+ while ((p = qb_map_iter_next(it, &data)) != NULL) {
+ printf("??: %s == %s\n", p, (char*)data);
+ count++;
+ }
+ qb_map_iter_free(it);
+ ck_assert_int_eq(count, 0);
+
+ count = 0;
+ it = qb_map_pref_iter_create(m, "c");
+ while ((p = qb_map_iter_next(it, &data)) != NULL) {
+ printf("3: %s == %s\n", p, (char*)data);
+ count++;
+ }
+ qb_map_iter_free(it);
+ ck_assert_int_eq(count, 2);
+
+ qb_map_destroy(m);
+}
+
static void
test_map_traverse_unordered(qb_map_t *m)
@@ -525,6 +580,8 @@ START_TEST(test_trie_traverse)
test_map_traverse_unordered(m);
m = qb_trie_create(NULL, NULL);
test_map_iter_safety(m, QB_FALSE);
+ m = qb_trie_create(NULL, NULL);
+ test_map_iter_prefix(m);
}
END_TEST
--
1.7.6