Page MenuHomeClusterLabs Projects
Files F3156159

No OneTemporary
Actions

View Options

diff --git a/lib/trie.c b/lib/trie.c
index 62761cf..9561b99 100644
--- a/lib/trie.c
+++ b/lib/trie.c
@@ -1,722 +1,744 @@
/*
* Copyright (C) 2011 Red Hat, Inc.
*
* Author: Angus Salkeld <asalkeld@redhat.com>
*
* This file is part of libqb.
*
* libqb is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation, either version 2.1 of the License, or
* (at your option) any later version.
*
* libqb is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with libqb. If not, see <http://www.gnu.org/licenses/>.
*/
#include <os_base.h>
#include <assert.h>
#include <qb/qbdefs.h>
#include <qb/qblist.h>
#include <qb/qbmap.h>
#include "map_int.h"
struct trie_iter {
struct qb_map_iter i;
const char *prefix;
struct trie_node *n;
struct trie_node *root;
};
struct trie_node {
uint32_t idx;
char *segment;
uint32_t num_segments;
char *key;
void *value;
struct trie_node **children;
uint32_t num_children;
uint32_t refcount;
struct trie_node *parent;
struct qb_list_head notifier_head;
};
struct trie {
struct qb_map map;
size_t length;
uint32_t num_nodes;
uint32_t mem_used;
struct trie_node *header;
};
static void trie_notify(struct trie_node *n, uint32_t event, const char *key,
void *old_value, void *value);
static struct trie_node *trie_new_node(struct trie *t, struct trie_node *parent);
/*
* characters are stored in reverse to make accessing the
* more common case (non-control chars) more space efficient.
*/
#define TRIE_CHAR2INDEX(ch) (126 - ch)
#define TRIE_INDEX2CHAR(idx) (126 - idx)
static struct trie_node *
trie_node_next(struct trie_node *node, struct trie_node *root, int all)
{
struct trie_node *c = node;
struct trie_node *n;
struct trie_node *p;
int i;
keep_going:
n = NULL;
/* child/outward
*/
for (i = c->num_children - 1; i >= 0; i--) {
if (c->children[i]) {
n = c->children[i];
break;
}
}
if (n) {
if (all || n->value) {
return n;
} else {
c = n;
goto keep_going;
}
}
/* sibling/parent
*/
if (c == root) {
return NULL;
}
p = c;
do {
for (i = p->idx - 1; i >= 0; i--) {
if (p->parent->children[i]) {
n = p->parent->children[i];
break;
}
}
if (n == NULL) {
p = p->parent;
}
} while (n == NULL && p != root);
if (n) {
if (all || n->value) {
return n;
}
if (n == root) {
return NULL;
}
c = n;
goto keep_going;
}
return n;
}
static struct trie_node *
new_child_node(struct trie *t, struct trie_node * parent, char ch)
{
struct trie_node *new_node;
int old_max_idx;
int i;
int idx = TRIE_CHAR2INDEX(ch);
if (idx >= parent->num_children) {
old_max_idx = parent->num_children;
parent->num_children = QB_MAX(idx + 1, 30);
t->mem_used += (sizeof(struct trie_node*) * (parent->num_children - old_max_idx));
parent->children = realloc(parent->children,
(parent->num_children * sizeof(struct trie_node*)));
if (parent->children == NULL) {
return NULL;
}
for (i = old_max_idx; i < parent->num_children; i++) {
parent->children[i] = NULL;
}
}
new_node = trie_new_node(t, parent);
if (new_node == NULL) {
return NULL;
}
new_node->idx = idx;
parent->children[idx] = new_node;
return new_node;
}
static struct trie_node *
trie_node_split(struct trie *t, struct trie_node *cur_node, int seg_cnt)
{
struct trie_node *split_node;
struct trie_node ** children = cur_node->children;
uint32_t num_children = cur_node->num_children;
int i;
int s;
cur_node->children = NULL;
cur_node->num_children = 0;
split_node = new_child_node(t, cur_node, cur_node->segment[seg_cnt]);
if (split_node == NULL) {
return NULL;
}
split_node->children = children;
split_node->num_children = num_children;
for (i = 0; i < split_node->num_children; i++) {
if (split_node->children[i]) {
split_node->children[i]->parent = split_node;
}
}
split_node->value = cur_node->value;
split_node->key = cur_node->key;
split_node->refcount = cur_node->refcount;
cur_node->value = NULL;
cur_node->key = NULL;
cur_node->refcount = 0;
/* move notifier list to split */
split_node->notifier_head.next = cur_node->notifier_head.next;
split_node->notifier_head.next->prev = &split_node->notifier_head;
split_node->notifier_head.prev = cur_node->notifier_head.prev;
split_node->notifier_head.prev->next = &split_node->notifier_head;
qb_list_init(&cur_node->notifier_head);
if (seg_cnt < cur_node->num_segments) {
split_node->num_segments = cur_node->num_segments - seg_cnt - 1;
split_node->segment = malloc(split_node->num_segments * sizeof(char));
if (split_node->segment == NULL) {
free(split_node);
return NULL;
}
for (i = (seg_cnt + 1); i < cur_node->num_segments; i++) {
s = i - seg_cnt - 1;
split_node->segment[s] = cur_node->segment[i];
cur_node->segment[i] = '\0';
}
cur_node->num_segments = seg_cnt;
}
return cur_node;
}
static struct trie_node *
trie_insert(struct trie *t, const char *key)
{
struct trie_node *cur_node = t->header;
struct trie_node *new_node;
char *cur = (char *)key;
int idx = TRIE_CHAR2INDEX(key[0]);
int seg_cnt = 0;
do {
new_node = NULL;
if (cur_node->num_segments > 0 &&
seg_cnt < cur_node->num_segments) {
if (cur_node->segment[seg_cnt] == *cur) {
/* we found the char in the segment */
seg_cnt++;
} else {
cur_node = trie_node_split(t, cur_node, seg_cnt);
if (cur_node == NULL) {
return NULL;
}
new_node = new_child_node(t, cur_node, *cur);
if (new_node == NULL) {
return NULL;
}
}
} else if (idx < cur_node->num_children &&
cur_node->children[idx]) {
/* the char can be found on the next node */
new_node = cur_node->children[idx];
} else if (cur_node == t->header) {
/* the root node is empty so make it on the next node */
new_node = new_child_node(t, cur_node, *cur);
if (new_node == NULL) {
return NULL;
}
} else if (cur_node->value == NULL &&
qb_list_empty(&cur_node->notifier_head) &&
cur_node->num_children == 0 &&
seg_cnt == cur_node->num_segments) {
/* we are on a leaf (with no value) so just add it as a segment */
cur_node->segment = realloc(cur_node->segment, cur_node->num_segments + 1);
cur_node->segment[cur_node->num_segments] = *cur;
t->mem_used += sizeof(char);
cur_node->num_segments++;
seg_cnt++;
} else if (seg_cnt == cur_node->num_segments) {
/* on the last segment need to make a new node */
new_node = new_child_node(t, cur_node, *cur);
if (new_node == NULL) {
return NULL;
}
} else /* need_to_split */ {
cur_node = trie_node_split(t, cur_node, seg_cnt);
if (cur_node == NULL) {
return NULL;
}
new_node = new_child_node(t, cur_node, *cur);
if (new_node == NULL) {
return NULL;
}
}
if (new_node) {
seg_cnt = 0;
cur_node = new_node;
}
cur++;
idx = TRIE_CHAR2INDEX(*cur);
} while (*cur != '\0');
if (cur_node->num_segments > 0 &&
seg_cnt < cur_node->num_segments) {
/* we need to split */
cur_node = trie_node_split(t, cur_node, seg_cnt);
if (cur_node == NULL) {
return NULL;
}
new_node = new_child_node(t, cur_node, *cur);
if (new_node == NULL) {
return NULL;
}
}
return cur_node;
}
static struct trie_node *
trie_lookup(struct trie *t, const char *key, int exact_match)
{
struct trie_node *cur_node = t->header;
char *cur = (char *)key;
int idx = TRIE_CHAR2INDEX(key[0]);
int seg_cnt = 0;
do {
if (cur_node->num_segments > 0 &&
seg_cnt < cur_node->num_segments) {
if (cur_node->segment[seg_cnt] == *cur) {
/* we found the char in the segment */
seg_cnt++;
} else {
return NULL;
}
} else if (idx < cur_node->num_children &&
cur_node->children[idx]) {
/* the char can be found on the next node */
cur_node = cur_node->children[idx];
seg_cnt = 0;
} else {
return NULL;
}
cur++;
idx = TRIE_CHAR2INDEX(*cur);
} while (*cur != '\0');
if (exact_match &&
cur_node->num_segments > 0 &&
seg_cnt < cur_node->num_segments) {
return NULL;
}
return cur_node;
}
+static void
+trie_node_release(struct trie *t, struct trie_node *node)
+{
+ if (node->num_children == 0 &&
+ node->refcount == 0 &&
+ node->parent != NULL &&
+ qb_list_empty(&node->notifier_head)) {
+ struct trie_node *p = node->parent;
+ /*
+ * unlink the node from the parent
+ */
+ p->children[node->idx] = NULL;
+ free(node);
+ t->num_nodes--;
+ t->mem_used -= sizeof(struct trie_node);
+
+ trie_node_release(t, p);
+ }
+}
+
static void
trie_node_destroy(struct trie *t, struct trie_node *n)
{
if (n->value == NULL) {
return;
}
trie_notify(n, QB_MAP_NOTIFY_DELETED, n->key, n->value, NULL);
n->key = NULL;
n->value = NULL;
+
+ trie_node_release(t, n);
}
static void
trie_print_node(struct trie_node *n, struct trie_node *r, const char *suffix)
{
int i;
if (n->parent) {
trie_print_node(n->parent, n, suffix);
}
if (n->idx == 0) {
return;
}
printf("[%c", TRIE_INDEX2CHAR(n->idx));
for (i = 0; i < n->num_segments; i++) {
printf("%c", n->segment[i]);
}
if (n == r) {
printf("] (%d) %s\n", n->refcount, suffix);
} else {
printf("] ");
}
}
-
static void
trie_node_ref(struct trie *t, struct trie_node *node)
{
if (t->header == node) {
return;
}
node->refcount++;
}
static void
trie_node_deref(struct trie *t, struct trie_node *node)
{
if (node->value == NULL) {
return;
}
node->refcount--;
if (node->refcount > 0) {
return;
}
trie_node_destroy(t, node);
}
static void
trie_destroy(struct qb_map *map)
{
struct trie *t = (struct trie *)map;
struct trie_node *cur_node = t->header;
struct trie_node *fwd_node;
do {
fwd_node = trie_node_next(cur_node, t->header, QB_FALSE);
trie_node_destroy(t, cur_node);
} while ((cur_node = fwd_node));
free(t);
}
static struct trie_node *
trie_new_node(struct trie *t, struct trie_node *parent)
{
struct trie_node *new_node = calloc(1, sizeof(struct trie_node));
if (new_node == NULL) {
return NULL;
}
new_node->parent = parent;
new_node->num_children = 0;
new_node->children = NULL;
new_node->num_segments = 0;
new_node->segment = NULL;
t->num_nodes++;
t->mem_used += sizeof(struct trie_node);
qb_list_init(&new_node->notifier_head);
return new_node;
}
void
qb_trie_dump(qb_map_t* m)
{
struct trie * t = (struct trie*)m;
struct trie_node *n;
if (t == NULL) {
return;
}
printf("nodes: %d, bytes: %d\n", t->num_nodes, t->mem_used);
n = t->header;
do {
if (n->num_children == 0) {
trie_print_node(n, n, " ");
}
n = trie_node_next(n, t->header, QB_FALSE);
} while (n);
}
static void
trie_put(struct qb_map *map, const char *key, const void *value)
{
struct trie *t = (struct trie *)map;
struct trie_node *n = trie_insert(t, key);
if (n) {
const char *old_value = n->value;
const char *old_key = n->key;
n->key = (char *)key;
n->value = (void *)value;
if (old_value == NULL) {
trie_node_ref(t, n);
t->length++;
trie_notify(n, QB_MAP_NOTIFY_INSERTED,
n->key, NULL, n->value);
} else {
trie_notify(n, QB_MAP_NOTIFY_REPLACED,
(char *)old_key, (void *)old_value,
(void *)value);
}
}
}
static int32_t
trie_rm(struct qb_map *map, const char *key)
{
struct trie *t = (struct trie *)map;
struct trie_node *n = trie_lookup(t, key, QB_TRUE);
if (n) {
trie_node_deref(t, n);
t->length--;
return QB_TRUE;
} else {
return QB_FALSE;
}
}
static void *
trie_get(struct qb_map *map, const char *key)
{
struct trie *t = (struct trie *)map;
struct trie_node *n = trie_lookup(t, key, QB_TRUE);
if (n) {
return n->value;
}
return NULL;
}
static void
trie_notify(struct trie_node *n,
uint32_t event, const char *key, void *old_value, void *value)
{
struct trie_node *c = n;
struct qb_list_head *list;
struct qb_map_notifier *tn;
do {
for (list = c->notifier_head.next;
list != &c->notifier_head; list = list->next) {
tn = qb_list_entry(list, struct qb_map_notifier, list);
if ((tn->events & event) &&
((tn->events & QB_MAP_NOTIFY_RECURSIVE) ||
(n == c))) {
tn->callback(event, (char *)key, old_value,
value, tn->user_data);
}
if (((event & QB_MAP_NOTIFY_DELETED) ||
(event & QB_MAP_NOTIFY_REPLACED)) &&
(tn->events & QB_MAP_NOTIFY_FREE)) {
tn->callback(QB_MAP_NOTIFY_FREE, (char *)key,
old_value, value, tn->user_data);
}
}
c = c->parent;
} while (c);
}
static int32_t
trie_notify_add(qb_map_t * m, const char *key,
qb_map_notify_fn fn, int32_t events, void *user_data)
{
struct trie *t = (struct trie *)m;
struct qb_map_notifier *f;
struct trie_node *n;
struct qb_list_head *list;
int add_to_tail = QB_FALSE;
if (key) {
n = trie_lookup(t, key, QB_TRUE);
if (n == NULL) {
n = trie_insert(t, key);
}
} else {
n = t->header;
}
if (n) {
for (list = n->notifier_head.next;
list != &n->notifier_head; list = list->next) {
f = qb_list_entry(list, struct qb_map_notifier, list);
if (events & QB_MAP_NOTIFY_FREE &&
f->events == events) {
/* only one free notifier */
return -EEXIST;
}
if (f->events == events &&
f->callback == fn &&
f->user_data == user_data) {
return -EEXIST;
}
}
f = malloc(sizeof(struct qb_map_notifier));
if (f == NULL) {
return -errno;
}
f->events = events;
f->user_data = user_data;
f->callback = fn;
qb_list_init(&f->list);
if (key) {
if (events & QB_MAP_NOTIFY_RECURSIVE) {
add_to_tail = QB_TRUE;
}
} else {
if (events & QB_MAP_NOTIFY_FREE) {
add_to_tail = QB_TRUE;
}
}
if (add_to_tail) {
qb_list_add_tail(&f->list, &n->notifier_head);
} else {
qb_list_add(&f->list, &n->notifier_head);
}
return 0;
}
return -EINVAL;
}
static int32_t
trie_notify_del(qb_map_t * m, const char *key,
qb_map_notify_fn fn, int32_t events,
int32_t cmp_userdata, void *user_data)
{
struct trie *t = (struct trie *)m;
struct qb_map_notifier *f;
struct trie_node *n;
struct qb_list_head *list;
struct qb_list_head *next;
int32_t found = QB_FALSE;
if (key) {
n = trie_lookup(t, key, QB_FALSE);
} else {
n = t->header;
}
if (n == NULL) {
return -ENOENT;
}
for (list = n->notifier_head.next;
list != &n->notifier_head; list = next) {
f = qb_list_entry(list, struct qb_map_notifier, list);
next = list->next;
if (f->events == events && f->callback == fn) {
if (cmp_userdata && (f->user_data == user_data)) {
found = QB_TRUE;
qb_list_del(&f->list);
free(f);
} else if (!cmp_userdata) {
found = QB_TRUE;
qb_list_del(&f->list);
free(f);
}
}
}
if (found) {
+ trie_node_release(t, n);
return 0;
} else {
return -ENOENT;
}
}
static qb_map_iter_t *
trie_iter_create(struct qb_map *map, const char *prefix)
{
struct trie_iter *i = malloc(sizeof(struct trie_iter));
struct trie *t = (struct trie *)map;
if (i == NULL) {
return NULL;
}
i->i.m = map;
i->prefix = prefix;
i->n = t->header;
i->root = t->header;
return (qb_map_iter_t *) i;
}
static const char *
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;
}
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, QB_FALSE);
} else {
si->n = si->root;
}
} else {
si->n = trie_node_next(p, si->root, QB_FALSE);
}
if (si->n == NULL) {
trie_node_deref(t, p);
return NULL;
}
trie_node_ref(t, si->n);
trie_node_deref(t, p);
*value = si->n->value;
return si->n->key;
}
static void
trie_iter_free(qb_map_iter_t * i)
{
free(i);
}
static size_t
trie_count_get(struct qb_map *map)
{
struct trie *list = (struct trie *)map;
return list->length;
}
qb_map_t *
qb_trie_create(void)
{
struct trie *t = malloc(sizeof(struct trie));
if (t == NULL) {
return NULL;
}
t->map.put = trie_put;
t->map.get = trie_get;
t->map.rm = trie_rm;
t->map.count_get = trie_count_get;
t->map.iter_create = trie_iter_create;
t->map.iter_next = trie_iter_next;
t->map.iter_free = trie_iter_free;
t->map.destroy = trie_destroy;
t->map.notify_add = trie_notify_add;
t->map.notify_del = trie_notify_del;
t->length = 0;
t->num_nodes = 0;
t->mem_used = sizeof(struct trie);
t->header = trie_new_node(t, NULL);
return (qb_map_t *) t;
}
diff --git a/tests/check_map.c b/tests/check_map.c
index 50c6317..23f005e 100644
--- a/tests/check_map.c
+++ b/tests/check_map.c
@@ -1,922 +1,925 @@
/*
* Copyright (c) 2011 Red Hat, Inc.
*
* All rights reserved.
*
* Author: Angus Salkeld <asalkeld@redhat.com>
*
* This file is part of libqb.
*
* libqb is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation, either version 2.1 of the License, or
* (at your option) any later version.
*
* libqb is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with libqb. If not, see <http://www.gnu.org/licenses/>.
*/
#include "os_base.h"
#include <check.h>
#include <qb/qbdefs.h>
#include <qb/qblog.h>
#include <qb/qbmap.h>
const char *chars[] = {
"0","1","2","3","4","5","6","7","8","9",
"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",
"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z",
NULL,
};
const char *chars2[] = {
"0","1","2","3","4","5","6","7","8","9",
"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z",
NULL,
};
static char *notified_key = NULL;
static void *notified_value = NULL;
static void *notified_new_value = NULL;
static void *notified_user_data = NULL;
static int32_t notified_event = 0;
static int32_t notified_event_prev = 0;
static void
test_map_simple(qb_map_t *m, const char *name)
{
int i;
const char *p;
void *data;
qb_map_iter_t *it;
qb_map_put(m, "k1", "one");
qb_map_put(m, "k12", "two");
qb_map_put(m, "k34", "three");
ck_assert_int_eq(qb_map_count_get(m), 3);
qb_map_put(m, "k3", "four");
ck_assert_int_eq(qb_map_count_get(m), 4);
it = qb_map_iter_create(m);
i = 0;
for (p = qb_map_iter_next(it, &data); p; p = qb_map_iter_next(it, &data)) {
printf("%25s(%d) %s > %s\n", name, i, p, (char*) data);
i++;
}
qb_map_iter_free(it);
ck_assert_int_eq(i, 4);
ck_assert_str_eq(qb_map_get(m, "k34"), "three");
ck_assert_str_eq(qb_map_get(m, "k1"), "one");
ck_assert_str_eq(qb_map_get(m, "k12"), "two");
ck_assert_str_eq(qb_map_get(m, "k3"), "four");
qb_map_rm(m, "k12");
ck_assert_int_eq(qb_map_count_get(m), 3);
qb_map_put(m, "9k", "nine");
qb_map_put(m, "k34", "not_three");
ck_assert_str_eq(qb_map_get(m, "k34"), "not_three");
ck_assert_int_eq(qb_map_count_get(m), 4);
qb_map_destroy(m);
}
static int32_t
my_traverse(const char *key, void *value, void *data)
{
ck_assert((*key) > 0);
return QB_FALSE;
}
static int32_t
check_order(const char *key, void *value, void *data)
{
int *o = (int*)data;
- ck_assert(chars[*o][0] == key[0]);
+ ck_assert_str_eq(chars[*o], key);
+ ck_assert_str_eq(chars[*o], value);
(*o)++;
return QB_FALSE;
}
+
static int32_t
check_order2(const char *key, void *value, void *data)
{
int *o = (int*)data;
- ck_assert(chars2[*o][0] == key[0]);
+ ck_assert_str_eq(chars2[*o], key);
+ ck_assert_str_eq(chars2[*o], value);
(*o)++;
return QB_FALSE;
}
static void
test_map_search(qb_map_t* m)
{
int32_t i;
int32_t removed;
int order;
char c[2];
const char *p;
for (i = 0; chars[i]; i++) {
qb_map_put(m, chars[i], chars[i]);
}
qb_map_foreach(m, my_traverse, NULL);
ck_assert_int_eq(qb_map_count_get(m), (26*2 + 10));
order = 0;
qb_map_foreach(m, check_order, &order);
for (i = 0; i < 26; i++) {
removed = qb_map_rm(m, chars[i + 10]);
ck_assert(removed);
}
c[0] = '\0';
c[1] = '\0';
removed = qb_map_rm(m, c);
ck_assert(!removed);
qb_map_foreach(m, my_traverse, NULL);
ck_assert_int_eq(qb_map_count_get(m), 26+10);
order = 0;
qb_map_foreach(m, check_order2, &order);
for (i = 25; i >= 0; i--) {
qb_map_put(m, chars[i + 10], chars[i + 10]);
}
order = 0;
qb_map_foreach(m, check_order, &order);
c[0] = '0';
p = qb_map_get(m, c);
ck_assert(p && *p == *c);
c[0] = 'A';
p = qb_map_get(m, c);
ck_assert(p && *p == *c);
c[0] = 'a';
p = qb_map_get(m, c);
ck_assert(p && *p == *c);
c[0] = 'z';
p = qb_map_get(m, c);
ck_assert(p && *p == *c);
c[0] = '!';
p = qb_map_get(m, c);
ck_assert(p == NULL);
c[0] = '=';
p = qb_map_get(m, c);
ck_assert(p == NULL);
c[0] = '|';
p = qb_map_get(m, c);
ck_assert(p == NULL);
qb_map_destroy(m);
}
static void
my_map_notification(uint32_t event,
char* key, void* old_value,
void* value, void* user_data)
{
notified_key = key;
notified_value = old_value;
notified_new_value = value;
notified_user_data = user_data;
notified_event_prev = notified_event;
notified_event = event;
}
static void
my_map_notification_2(uint32_t event,
char* key, void* old_value,
void* value, void* user_data)
{
}
static void
test_map_remove(qb_map_t *m)
{
const char * a, *b, *c, *d;
int32_t i;
int32_t removed;
const char *remove_ch[] = {"o","m","k","j","i","g","f","e","d","b","a", NULL};
i = qb_map_notify_add(m, NULL, my_map_notification,
(QB_MAP_NOTIFY_DELETED|
QB_MAP_NOTIFY_REPLACED|
QB_MAP_NOTIFY_RECURSIVE),
m);
ck_assert_int_eq(i, 0);
for (i = 0; chars[i]; i++) {
qb_map_put(m, chars[i], chars[i]);
}
a = "0";
qb_map_put(m, a, a);
ck_assert(notified_key == chars[0]);
ck_assert(notified_value == chars[0]);
ck_assert(notified_user_data == m);
notified_key = NULL;
notified_value = NULL;
notified_user_data = NULL;
b = "5";
removed = qb_map_rm(m, b);
ck_assert(removed);
ck_assert(notified_key == chars[5]);
ck_assert(notified_value == chars[5]);
ck_assert(notified_user_data == m);
notified_key = NULL;
notified_value = NULL;
notified_user_data = NULL;
d = "1";
qb_map_put(m, d, d);
ck_assert(notified_key == chars[1]);
ck_assert(notified_value == chars[1]);
ck_assert(notified_user_data == m);
notified_key = NULL;
notified_value = NULL;
c = "2";
removed = qb_map_rm(m, c);
ck_assert(removed);
ck_assert(notified_key == chars[2]);
ck_assert(notified_value == chars[2]);
notified_key = NULL;
notified_value = NULL;
for (i = 0; remove_ch[i]; i++) {
removed = qb_map_rm(m, remove_ch[i]);
ck_assert(removed);
}
qb_map_destroy(m);
}
static void
test_map_notifications_basic(qb_map_t *m)
{
int32_t i;
/* with global notifier */
i = qb_map_notify_add(m, NULL, my_map_notification,
(QB_MAP_NOTIFY_INSERTED|
QB_MAP_NOTIFY_DELETED|
QB_MAP_NOTIFY_REPLACED|
QB_MAP_NOTIFY_RECURSIVE),
m);
ck_assert_int_eq(i, 0);
notified_key = NULL;
notified_value = NULL;
notified_new_value = NULL;
/* insert */
qb_map_put(m, "garden", "grow");
ck_assert_str_eq(notified_key, "garden");
ck_assert_str_eq(notified_new_value, "grow");
ck_assert(notified_user_data == m);
/* update */
qb_map_put(m, "garden", "green");
ck_assert_str_eq(notified_key, "garden");
ck_assert_str_eq(notified_value, "grow");
ck_assert_str_eq(notified_new_value, "green");
ck_assert(notified_user_data == m);
/* delete */
qb_map_rm(m, "garden");
ck_assert_str_eq(notified_key, "garden");
ck_assert_str_eq(notified_value, "green");
ck_assert(notified_user_data == m);
/* no event with notifier removed */
i = qb_map_notify_del(m, NULL, my_map_notification,
(QB_MAP_NOTIFY_INSERTED|
QB_MAP_NOTIFY_DELETED|
QB_MAP_NOTIFY_REPLACED|
QB_MAP_NOTIFY_RECURSIVE));
ck_assert_int_eq(i, 0);
notified_key = NULL;
notified_value = NULL;
notified_new_value = NULL;
qb_map_put(m, "age", "67");
ck_assert(notified_key == NULL);
ck_assert(notified_value == NULL);
ck_assert(notified_new_value == NULL);
/* deleting a non-existing notification */
i = qb_map_notify_del(m, "a", my_map_notification,
(QB_MAP_NOTIFY_INSERTED|
QB_MAP_NOTIFY_DELETED|
QB_MAP_NOTIFY_REPLACED|
QB_MAP_NOTIFY_RECURSIVE));
ck_assert_int_eq(i, -ENOENT);
/* test uniquess */
qb_map_put(m, "fred", "null");
i = qb_map_notify_add(m, "fred", my_map_notification,
QB_MAP_NOTIFY_REPLACED, m);
ck_assert_int_eq(i, 0);
i = qb_map_notify_add(m, "fred", my_map_notification,
QB_MAP_NOTIFY_REPLACED, m);
ck_assert_int_eq(i, -EEXIST);
}
/* test free'ing notifier
*
* input:
* only one can be added
* can only be added with NULL key (global)
* output:
* is the last notifier called (after deleted or replaced)
* recursive is implicit
*/
static void
test_map_notifications_free(qb_map_t *m)
{
int32_t i;
i = qb_map_notify_add(m, "not global", my_map_notification,
QB_MAP_NOTIFY_FREE, m);
ck_assert_int_eq(i, -EINVAL);
i = qb_map_notify_add(m, NULL, my_map_notification,
QB_MAP_NOTIFY_FREE, m);
ck_assert_int_eq(i, 0);
i = qb_map_notify_add(m, NULL, my_map_notification_2,
QB_MAP_NOTIFY_FREE, m);
ck_assert_int_eq(i, -EEXIST);
i = qb_map_notify_del_2(m, NULL, my_map_notification,
QB_MAP_NOTIFY_FREE, m);
ck_assert_int_eq(i, 0);
i = qb_map_notify_add(m, NULL, my_map_notification,
(QB_MAP_NOTIFY_FREE |
QB_MAP_NOTIFY_REPLACED |
QB_MAP_NOTIFY_DELETED |
QB_MAP_NOTIFY_RECURSIVE), m);
ck_assert_int_eq(i, 0);
qb_map_put(m, "garden", "grow");
/* update */
qb_map_put(m, "garden", "green");
ck_assert_int_eq(notified_event_prev, QB_MAP_NOTIFY_REPLACED);
ck_assert_int_eq(notified_event, QB_MAP_NOTIFY_FREE);
/* delete */
qb_map_rm(m, "garden");
ck_assert_int_eq(notified_event_prev, QB_MAP_NOTIFY_DELETED);
ck_assert_int_eq(notified_event, QB_MAP_NOTIFY_FREE);
}
static void
test_map_notifications_prefix(qb_map_t *m)
{
int32_t i;
/* with prefix notifier */
i = qb_map_notify_add(m, "add", my_map_notification,
(QB_MAP_NOTIFY_INSERTED|
QB_MAP_NOTIFY_DELETED|
QB_MAP_NOTIFY_REPLACED|
QB_MAP_NOTIFY_RECURSIVE),
&i);
ck_assert_int_eq(i, 0);
/* insert */
qb_map_put(m, "adder", "snake");
ck_assert_str_eq(notified_key, "adder");
ck_assert_str_eq(notified_new_value, "snake");
ck_assert(notified_user_data == &i);
/* insert (no match) */
notified_key = NULL;
notified_value = NULL;
notified_new_value = NULL;
qb_map_put(m, "adjust", "it");
ck_assert(notified_key == NULL);
ck_assert(notified_value == NULL);
ck_assert(notified_new_value == NULL);
/* update */
qb_map_put(m, "adder", "+++");
ck_assert_str_eq(notified_key, "adder");
ck_assert_str_eq(notified_value, "snake");
ck_assert_str_eq(notified_new_value, "+++");
/* delete */
qb_map_rm(m, "adder");
ck_assert_str_eq(notified_key, "adder");
ck_assert_str_eq(notified_value, "+++");
}
static void
test_map_traverse_ordered(qb_map_t *m)
{
int32_t i;
const char *p;
char *result;
void *data;
qb_map_iter_t *it = qb_map_iter_create(m);
for (i = 0; chars[i]; i++) {
qb_map_put(m, chars[i], chars[i]);
}
result = calloc(sizeof(char), 26 * 2 + 10 + 1);
i = 0;
for (p = qb_map_iter_next(it, &data); p; p = qb_map_iter_next(it, &data)) {
result[i] = *(char*) data;
i++;
}
qb_map_iter_free(it);
ck_assert_str_eq(result,
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
qb_map_destroy(m);
}
static int32_t
traverse_and_remove_func(const char *key, void *value, void *data)
{
int kk = rand() % 30;
qb_map_t *m = (qb_map_t *)data;
qb_map_rm(m, chars[kk]);
qb_map_put(m, chars[kk+30], key);
return QB_FALSE;
}
static void
test_map_iter_safety(qb_map_t *m, int32_t ordered)
{
void *data;
void *data2;
const char *p;
const char *p2;
qb_map_iter_t *it;
qb_map_iter_t *it2;
int32_t found_good = QB_FALSE;
qb_map_put(m, "aaaa", "aye");
qb_map_put(m, "bbbb", "bee");
qb_map_put(m, "cccc", "sea");
it = qb_map_iter_create(m);
it2 = qb_map_iter_create(m);
while ((p = qb_map_iter_next(it, &data)) != NULL) {
printf("1: %s == %s\n", p, (char*)data);
if (strcmp(p, "bbbb") == 0) {
qb_map_rm(m, "bbbb");
qb_map_rm(m, "cccc");
qb_map_put(m, "fffff", "yum");
while ((p2 = qb_map_iter_next(it2, &data2)) != NULL) {
printf("2: %s == %s\n", p2, (char*)data2);
if (strcmp(p2, "fffff") == 0) {
qb_map_put(m, "ggggg", "good");
}
}
qb_map_iter_free(it2);
}
if (strcmp(p, "ggggg") == 0) {
found_good = QB_TRUE;
}
}
qb_map_iter_free(it);
if (ordered) {
ck_assert_int_eq(found_good, QB_TRUE);
}
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)
{
int32_t i;
srand(time(NULL));
for (i = 0; i < 30; i++) {
qb_map_put(m, chars[i], chars[i]);
}
qb_map_foreach(m, traverse_and_remove_func, m);
qb_map_destroy(m);
}
static int32_t
my_counter_traverse(const char *key, void *value, void *data)
{
int32_t *c = (int32_t*)data;
(*c)++;
return QB_FALSE;
}
static void
test_map_load(qb_map_t *m, const char* test_name)
{
char word[1000];
char *w;
FILE *fp;
int32_t res = 0;
int32_t count;
int32_t count2;
float ops;
float secs;
void *value;
qb_util_stopwatch_t *sw;
ck_assert(m != NULL);
sw = qb_util_stopwatch_create();
#define MAX_WORDS 100000
/*
* Load with dictionary
*/
fp = fopen("/usr/share/dict/words", "r");
qb_util_stopwatch_start(sw);
count = 0;
while (fgets(word, sizeof(word), fp) && count < MAX_WORDS) {
w = strdup(word);
qb_map_put(m, w, w);
count++;
}
qb_util_stopwatch_stop(sw);
ck_assert_int_eq(qb_map_count_get(m), count);
fclose(fp);
secs = qb_util_stopwatch_sec_elapsed_get(sw);
ops = (float)count / secs;
qb_log(LOG_INFO, "%25s %12.2f puts/sec (%d/%fs)\n", test_name, ops, count, secs);
/*
* Verify dictionary produces correct values
*/
fp = fopen("/usr/share/dict/words", "r");
qb_util_stopwatch_start(sw);
count2 = 0;
while (fgets(word, sizeof(word), fp) && count2 < MAX_WORDS) {
value = qb_map_get(m, word);
ck_assert_str_eq(word, value);
count2++;
}
qb_util_stopwatch_stop(sw);
fclose(fp);
secs = qb_util_stopwatch_sec_elapsed_get(sw);
ops = (float)count2 / secs;
qb_log(LOG_INFO, "%25s %12.2f gets/sec (%d/%fs)\n", test_name, ops, count2, secs);
/*
* time the iteration
*/
count2 = 0;
qb_util_stopwatch_start(sw);
qb_map_foreach(m, my_counter_traverse, &count2);
qb_util_stopwatch_stop(sw);
ck_assert_int_eq(qb_map_count_get(m), count2);
secs = qb_util_stopwatch_sec_elapsed_get(sw);
ops = (float)count2 / secs;
qb_log(LOG_INFO, "%25s %12.2f iters/sec (%d/%fs)\n", test_name, ops, count2, secs);
/*
* Delete all dictionary entries
*/
fp = fopen("/usr/share/dict/words", "r");
qb_util_stopwatch_start(sw);
count2 = 0;
while (fgets(word, sizeof(word), fp) && count2 < MAX_WORDS) {
res = qb_map_rm(m, word);
ck_assert_int_eq(res, QB_TRUE);
count2++;
}
qb_util_stopwatch_stop(sw);
ck_assert_int_eq(qb_map_count_get(m), 0);
fclose(fp);
secs = qb_util_stopwatch_sec_elapsed_get(sw);
ops = (float)count2 / secs;
qb_log(LOG_INFO, "%25s %12.2f dels/sec (%d/%fs)\n", test_name, ops, count2, secs);
}
START_TEST(test_skiplist_simple)
{
qb_map_t *m = qb_skiplist_create();
test_map_simple(m, __func__);
}
END_TEST
START_TEST(test_hashtable_simple)
{
qb_map_t *m = qb_hashtable_create(32);
test_map_simple(m, __func__);
}
END_TEST
START_TEST(test_trie_simple)
{
qb_map_t *m = qb_trie_create();
test_map_simple(m, __func__);
}
END_TEST
START_TEST(test_skiplist_search)
{
qb_map_t *m = qb_skiplist_create();
test_map_search(m);
}
END_TEST
START_TEST(test_trie_search)
{
qb_map_t *m = qb_trie_create();
test_map_search(m);
}
END_TEST
START_TEST(test_skiplist_remove)
{
qb_map_t *m = qb_skiplist_create();
test_map_remove(m);
}
END_TEST
START_TEST(test_hashtable_remove)
{
qb_map_t *m = qb_hashtable_create(256);
test_map_remove(m);
}
END_TEST
START_TEST(test_trie_notifications)
{
qb_map_t *m;
m = qb_trie_create();
test_map_remove(m);
m = qb_trie_create();
test_map_notifications_basic(m);
m = qb_trie_create();
test_map_notifications_prefix(m);
m = qb_trie_create();
test_map_notifications_free(m);
}
END_TEST
START_TEST(test_hash_notifications)
{
qb_map_t *m;
m = qb_hashtable_create(256);
test_map_notifications_basic(m);
m = qb_hashtable_create(256);
test_map_notifications_free(m);
}
END_TEST
START_TEST(test_skiplist_notifications)
{
qb_map_t *m;
m = qb_skiplist_create();
test_map_notifications_basic(m);
m = qb_skiplist_create();
test_map_notifications_free(m);
}
END_TEST
START_TEST(test_skiplist_traverse)
{
qb_map_t *m;
m = qb_skiplist_create();
test_map_traverse_ordered(m);
m = qb_skiplist_create();
test_map_traverse_unordered(m);
m = qb_skiplist_create();
test_map_iter_safety(m, QB_TRUE);
}
END_TEST
START_TEST(test_hashtable_traverse)
{
qb_map_t *m;
m = qb_hashtable_create(256);
test_map_traverse_unordered(m);
m = qb_hashtable_create(256);
test_map_iter_safety(m, QB_FALSE);
}
END_TEST
START_TEST(test_trie_traverse)
{
qb_map_t *m;
m = qb_trie_create();
test_map_traverse_unordered(m);
m = qb_trie_create();
test_map_iter_safety(m, QB_FALSE);
m = qb_trie_create();
test_map_iter_prefix(m);
}
END_TEST
START_TEST(test_skiplist_load)
{
qb_map_t *m;
if (access("/usr/share/dict/words", R_OK) != 0) {
printf("no dict/words - not testing\n");
return;
}
m = qb_skiplist_create();
test_map_load(m, __func__);
}
END_TEST
START_TEST(test_hashtable_load)
{
qb_map_t *m;
if (access("/usr/share/dict/words", R_OK) != 0) {
printf("no dict/words - not testing\n");
return;
}
m = qb_hashtable_create(100000);
test_map_load(m, __func__);
}
END_TEST
START_TEST(test_trie_load)
{
qb_map_t *m;
if (access("/usr/share/dict/words", R_OK) != 0) {
printf("no dict/words - not testing\n");
return;
}
m = qb_trie_create();
test_map_load(m, __func__);
}
END_TEST
static Suite *
map_suite(void)
{
TCase *tc;
Suite *s = suite_create("qb_map");
tc = tcase_create("skiplist_simple");
tcase_add_test(tc, test_skiplist_simple);
suite_add_tcase(s, tc);
tc = tcase_create("hashtable_simple");
tcase_add_test(tc, test_hashtable_simple);
suite_add_tcase(s, tc);
tc = tcase_create("trie_simple");
tcase_add_test(tc, test_trie_simple);
suite_add_tcase(s, tc);
tc = tcase_create("skiplist_remove");
tcase_add_test(tc, test_skiplist_remove);
suite_add_tcase(s, tc);
tc = tcase_create("hashtable_remove");
tcase_add_test(tc, test_hashtable_remove);
suite_add_tcase(s, tc);
tc = tcase_create("trie_notifications");
tcase_add_test(tc, test_trie_notifications);
suite_add_tcase(s, tc);
tc = tcase_create("hash_notifications");
tcase_add_test(tc, test_hash_notifications);
suite_add_tcase(s, tc);
tc = tcase_create("skiplist_notifications");
tcase_add_test(tc, test_skiplist_notifications);
suite_add_tcase(s, tc);
tc = tcase_create("skiplist_search");
tcase_add_test(tc, test_skiplist_search);
suite_add_tcase(s, tc);
/*
* No hashtable_search as it assumes an ordered
* collection
*/
tc = tcase_create("trie_search");
tcase_add_test(tc, test_trie_search);
suite_add_tcase(s, tc);
tc = tcase_create("skiplist_traverse");
tcase_add_test(tc, test_skiplist_traverse);
suite_add_tcase(s, tc);
tc = tcase_create("hashtable_traverse");
tcase_add_test(tc, test_hashtable_traverse);
suite_add_tcase(s, tc);
tc = tcase_create("trie_traverse");
tcase_add_test(tc, test_trie_traverse);
suite_add_tcase(s, tc);
tc = tcase_create("skiplist_load");
tcase_add_test(tc, test_skiplist_load);
tcase_set_timeout(tc, 30);
suite_add_tcase(s, tc);
tc = tcase_create("hashtable_load");
tcase_add_test(tc, test_hashtable_load);
tcase_set_timeout(tc, 30);
suite_add_tcase(s, tc);
tc = tcase_create("trie_load");
tcase_add_test(tc, test_trie_load);
tcase_set_timeout(tc, 30);
suite_add_tcase(s, tc);
return s;
}
int32_t
main(void)
{
int32_t number_failed;
Suite *s = map_suite();
SRunner *sr = srunner_create(s);
qb_log_init("check", LOG_USER, LOG_EMERG);
qb_log_ctl(QB_LOG_SYSLOG, QB_LOG_CONF_ENABLED, QB_FALSE);
qb_log_filter_ctl(QB_LOG_STDERR, QB_LOG_FILTER_ADD,
QB_LOG_FILTER_FILE, "*", LOG_INFO);
qb_log_format_set(QB_LOG_STDERR, "%f:%l %p %b");
qb_log_ctl(QB_LOG_STDERR, QB_LOG_CONF_ENABLED, QB_TRUE);
srunner_run_all(sr, CK_VERBOSE);
number_failed = srunner_ntests_failed(sr);
srunner_free(sr);
return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
}

File Metadata

Mime Type
text/x-diff
Expires
Thu, Feb 27, 4:18 AM (1 d, 13 h ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
1466147
Default Alt Text
(39 KB)

Event Timeline