diff --git a/lib/trie.c b/lib/trie.c index 0e5dd6e..0ecef63 100644 --- a/lib/trie.c +++ b/lib/trie.c @@ -1,819 +1,819 @@ /* * Copyright (C) 2011 Red Hat, Inc. * * Author: Angus Salkeld * * 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 . */ #include #include #include #include #include #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); static void trie_destroy_node(struct trie_node *node); /* * 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) +#define TRIE_CHAR2INDEX(ch) (127 - (signed char)ch) +#define TRIE_INDEX2CHAR(idx) (127 - (signed char)idx) static int32_t trie_node_alive(struct trie_node *node) { if (node->value == NULL || node->refcount <= 0) { return QB_FALSE; } return QB_TRUE; } 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 || trie_node_alive(n)) { 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 || trie_node_alive(n)) { 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; struct qb_list_head *tmp; 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 */ tmp = split_node->notifier_head; split_node->notifier_head = cur_node->notifier_head; cur_node->notifier_head = tmp; 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) { trie_destroy_node(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) { int i; int empty = QB_FALSE; if (node->key == NULL && node->parent != NULL && qb_list_empty(node->notifier_head)) { struct trie_node *p = node->parent; if (node->num_children == 0) { empty = QB_TRUE; } else { empty = QB_TRUE; for (i = node->num_children - 1; i >= 0; i--) { if (node->children[i]) { empty = QB_FALSE; break; } } } if (!empty) { return; } /* * unlink the node from the parent */ p->children[node->idx] = NULL; trie_destroy_node(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", (char) TRIE_INDEX2CHAR(n->idx)); for (i = 0; i < n->num_segments; i++) { printf("%c", n->segment[i]); } if (n == r) { #ifndef S_SPLINT_S printf("] (%" PRIu32 ") %s\n", n->refcount, suffix); #endif /* S_SPLINT_S */ } 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 (!trie_node_alive(node)) { 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 void trie_destroy_node(struct trie_node *node) { free(node->segment); free(node->children); free(node->notifier_head); free(node); } 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->notifier_head = calloc(1, sizeof(struct qb_list_head)); if (new_node->notifier_head == NULL) { free(new_node); 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; } #ifndef S_SPLINT_S printf("nodes: %" PRIu32 ", bytes: %" PRIu32 "\n", t->num_nodes, t->mem_used); #endif /* S_SPLINT_S */ 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_deref(struct qb_map_notifier *f) { f->refcount--; if (f->refcount == 0) { qb_list_del(&f->list); free(f); } } static void trie_notify_ref(struct qb_map_notifier *f) { f->refcount++; } 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_list_head *next; struct qb_list_head *head; struct qb_map_notifier *tn; do { head = c->notifier_head; qb_list_for_each_safe(list, next, head) { tn = qb_list_entry(list, struct qb_map_notifier, list); trie_notify_ref(tn); 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); } trie_notify_deref(tn); } 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) { qb_list_for_each(list, n->notifier_head) { 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; f->refcount = 1; 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 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; } qb_list_for_each_safe(list, next, n->notifier_head) { struct qb_map_notifier *f = qb_list_entry(list, struct qb_map_notifier, list); if (f->events == events && f->callback == fn) { if (cmp_userdata && (f->user_data == user_data)) { trie_notify_deref(f); found = QB_TRUE; } else if (!cmp_userdata) { trie_notify_deref(f); found = QB_TRUE; } } } 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) { struct trie_iter *si = (struct trie_iter *)i; struct trie *t = (struct trie *)(i->m); if (si->n != NULL) { /* if free'ing the iterator before getting to the last * node make sure we de-ref the current node. */ trie_node_deref(t, si->n); } 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 e73c832..5a98f75 100644 --- a/tests/check_map.c +++ b/tests/check_map.c @@ -1,962 +1,1045 @@ /* * Copyright (c) 2011 Red Hat, Inc. * * All rights reserved. * * Author: Angus Salkeld * * 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 . */ #include "os_base.h" #include "check_common.h" #include #include #include 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, }; +const char *composers[] = { + "Béla Bartók", + "Zoltán Kodály", + "Ludwig van Beethoven", + "Wolfgang Amadeus Mozart", + "Leoš Janáček", + "Benjamin Britten", + "Josef Haydn", + "Claude Debussy", + "Charles Ives", + /* Maybe in an alien language ... but they can cause trie crashes & conflicts */ + "\x7e\x7f\x80\x81", "\x7e", "\x7e\x7f", "\x7e\x7f\x80", +}; + + 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 int32_t notified_events = 0; static void my_map_notification_iter(uint32_t event, char* key, void* old_value, void* value, void* user_data) { const char *p; void *data; qb_map_t *m = (qb_map_t *)user_data; qb_map_iter_t *it = qb_map_iter_create(m); notified_events++; for (p = qb_map_iter_next(it, &data); p; p = qb_map_iter_next(it, &data)) { printf("%s > %s\n", p, (char*) data); } qb_map_iter_free(it); } /* * create some entries * add a notifier * delete an entry * in the notifier iterate over the map. */ static void test_map_notifications_iter(qb_map_t *m) { int i; 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); notified_events = 0; i = qb_map_notify_add(m, NULL, my_map_notification_iter, (QB_MAP_NOTIFY_DELETED | QB_MAP_NOTIFY_RECURSIVE), m); ck_assert_int_eq(i, 0); qb_map_rm(m, "k12"); ck_assert_int_eq(notified_events, 1); ck_assert_int_eq(qb_map_count_get(m), 2); } 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_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_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 = random() % 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_rm(m, "aaaa"); 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); } +static void test_accents_load(qb_map_t *m, const char* test_name) +{ + int i; + int32_t res = 0; + int32_t count = 0; + int32_t count2; + void *value; + + ck_assert(m != NULL); + /* + * Load accented names + */ + for (i=0; i