Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
include/qb/qbmap.h | 80 ++++++++++++------
lib/hashtable.c | 235 ++++++++++++++++++++++++++++++++++++++++----------
lib/map.c | 49 ++++++++---
lib/map_int.h | 26 ++++--
lib/skiplist.c | 239 ++++++++++++++++++++++++++++++++++------------------
lib/trie.c | 240 +++++++++++++++++++++++++++++++++++-----------------
tests/check_map.c | 206 +++++++++++++++++++++++++++++++--------------
7 files changed, 758 insertions(+), 317 deletions(-)
diff --git a/include/qb/qbmap.h b/include/qb/qbmap.h
index 51e2212..9ebd2c0 100644
--- a/include/qb/qbmap.h
+++ b/include/qb/qbmap.h
@@ -31,61 +31,94 @@ extern "C" {
/**
* @file qbmap.h
- * This provides a map interface to either a hashtable or a skiplist.
+ * This provides a map interface to a trie, hashtable or skiplist.
*/
/**
* This is an opaque data type representing an instance of a map.
*/
typedef struct qb_map qb_map_t;
+
+/**
+ * This is an opaque data type representing an iterator instance.
+ */
typedef struct qb_map_iter qb_map_iter_t;
-typedef void (*qb_destroy_notifier_func)(void* data);
-typedef int32_t (*qb_transverse_func)(const char* key, void* value, void* data);
+#define QB_MAP_NOTIFY_DELETED 1
+#define QB_MAP_NOTIFY_REPLACED 2
+#define QB_MAP_NOTIFY_INSERTED 4
+#define QB_MAP_NOTIFY_RECURSIVE 8
+typedef void (*qb_map_notify_fn)(uint32_t event,
+ char* key,
+ void* old_value,
+ void* value,
+ void* user_data);
+
+typedef int32_t (*qb_map_transverse_fn)(const char* key,
+ void* value,
+ void* user_data);
/**
* Create an unsorted map based on a hashtable.
*
- * @param key_destroy_func function to free the key
- * @param value_destroy_func function to free the data
* @param max_size maximum size of the hashtable
*
* @return the map instance
*/
-qb_map_t* qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
- qb_destroy_notifier_func value_destroy_func,
- size_t max_size);
+qb_map_t* qb_hashtable_create(size_t max_size);
/**
* Create a sorted map using a skiplist.
*
- * @param key_destroy_func function to free the key
- * @param value_destroy_func function to free the data
- *
* @return the map instance
*/
-qb_map_t* qb_skiplist_create(qb_destroy_notifier_func key_destroy_func,
- qb_destroy_notifier_func value_destroy_func);
+qb_map_t* qb_skiplist_create(void);
/**
* Create a sorted map using a trie or "Prefix list".
*
* @see
en.wikipedia.org/wiki/Trie
*/
-qb_map_t*
-qb_trie_create(qb_destroy_notifier_func key_destroy_func,
- qb_destroy_notifier_func value_destroy_func);
+qb_map_t* qb_trie_create(void);
+/**
+ * Add a notifier to the map.
+ *
+ * @param m the map instance
+ * @param key the key (or prefix) to attach the notification to.
+ * @param fn the callback
+ * @param events the type of events to register for.
+ *
+ * @note QB_MAP_NOTIFY_INSERTED is only valid on tries.
+ * @note you can use key prefixes with trie maps.
+ *
+ * @retval 0 success
+ * @retval -errno failure
+ */
+int32_t qb_map_notify_add(qb_map_t* m, const char* key,
+ qb_map_notify_fn fn, int32_t events);
+
+/**
+ * Delete a notifier from the map.
+ *
+ * @note the key,fn and events must match those you added.
+ *
+ * @param m the map instance
+ * @param key the key (or prefix) to attach the notification to.
+ * @param fn the callback
+ * @param events the type of events to register for.
+ *
+ * @retval 0 success
+ * @retval -errno failure
+ */
+int32_t qb_map_notify_del(qb_map_t* m, const char* key,
+ qb_map_notify_fn fn, int32_t events);
/**
* Inserts a new key and value into a qb_map_t.
*
* If the key already exists in the qb_map_t, it gets replaced by the new key.
- * If you supplied a value_destroy_func when creating the qb_map_t,
- * the old value is freed using that function. If you supplied a
- * key_destroy_func when creating the qb_map_t, the old key is freed using
- * that function.
*/
void qb_map_put(qb_map_t *map, const char* key, const void* value);
@@ -99,11 +132,6 @@ void* qb_map_get(qb_map_t *map, const char* key);
/**
* Removes a key/value pair from a map.
- *
- * The key and value are freed using the supplied destroy functions,
- * otherwise you have to make sure that any dynamically allocated
- * values are freed yourself. If the key does not exist in the map,
- * the function does nothing.
*/
int32_t qb_map_rm(qb_map_t *map, const char* key);
@@ -118,7 +146,7 @@ size_t qb_map_count_get(qb_map_t *map);
* The function is passed the key and value of each pair, and the given data
* parameter. The map is traversed in sorted order.
*/
-void qb_map_foreach(qb_map_t *map, qb_transverse_func func, void* user_data);
+void qb_map_foreach(qb_map_t *map, qb_map_transverse_fn func, void* user_data);
/**
* Create an iterator
diff --git a/lib/hashtable.c b/lib/hashtable.c
index d45badf..3f83c37 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -32,6 +32,7 @@ struct hash_node {
void *value;
const char *key;
uint32_t refcount;
+ struct qb_list_head notifier_head;
};
struct hash_bucket {
@@ -44,6 +45,7 @@ struct hash_table {
uint32_t order;
uint32_t hash_buckets_len;
struct hash_bucket hash_buckets[0];
+ struct qb_list_head notifier_head;
};
struct hashtable_iter {
@@ -52,6 +54,10 @@ struct hashtable_iter {
uint32_t bucket;
};
+static void hashtable_notify(struct hash_table *t, struct hash_node *n,
+ uint32_t event, const char *key,
+ void *old_value, void *value, void *user_data);
+
static uint32_t
hash_fnv(const void *value, uint32_t valuelen, uint32_t order)
{
@@ -72,53 +78,61 @@ hash_fnv(const void *value, uint32_t valuelen, uint32_t order)
static uint32_t
qb_hash_string(const void *key, uint32_t order)
{
- char* str = (char*)key;
+ char *str = (char *)key;
return hash_fnv(key, strlen(str), order);
}
-static void*
-hashtable_get(struct qb_map *map, const char* key)
+static struct hash_node *
+hashtable_lookup(struct hash_table *t, const char *key)
{
- struct hash_table *hash_table = (struct hash_table *)map;
uint32_t hash_entry;
struct qb_list_head *list;
struct hash_node *hash_node;
- hash_entry = qb_hash_string(key, hash_table->order);
+ hash_entry = qb_hash_string(key, t->order);
- for (list = hash_table->hash_buckets[hash_entry].list_head.next;
- list != &hash_table->hash_buckets[hash_entry].list_head;
+ for (list = t->hash_buckets[hash_entry].list_head.next;
+ list != &t->hash_buckets[hash_entry].list_head;
list = list->next) {
hash_node = qb_list_entry(list, struct hash_node, list);
if (strcmp(hash_node->key, key) == 0) {
- return hash_node->value;
+ return hash_node;
}
}
return NULL;
}
+static void *
+hashtable_get(struct qb_map *map, const char *key)
+{
+ struct hash_table *t = (struct hash_table *)map;
+ struct hash_node *n = hashtable_lookup(t, key);
+ if (n) {
+ return n->value;
+ }
+ return NULL;
+}
+
static void
hashtable_node_deref(struct qb_map *map, struct hash_node *hash_node)
{
+ struct hash_table *t = (struct hash_table *)map;
+
hash_node->refcount--;
if (hash_node->refcount > 0) {
return;
}
- if (map->key_destroy_func) {
- map->key_destroy_func((void*)hash_node->key);
- }
- if (map->value_destroy_func) {
- map->value_destroy_func(hash_node->value);
- }
+ hashtable_notify(t, hash_node,
+ QB_MAP_NOTIFY_DELETED,
+ hash_node->key, hash_node->value, NULL, NULL);
qb_list_del(&hash_node->list);
free(hash_node);
}
static int32_t
-hashtable_rm_with_hash(struct qb_map *map, const char* key,
- uint32_t hash_entry)
+hashtable_rm_with_hash(struct qb_map *map, const char *key, uint32_t hash_entry)
{
struct hash_table *hash_table = (struct hash_table *)map;
struct qb_list_head *list;
@@ -140,7 +154,7 @@ hashtable_rm_with_hash(struct qb_map *map, const char* key,
}
static int32_t
-hashtable_rm(struct qb_map *map, const char* key)
+hashtable_rm(struct qb_map *map, const char *key)
{
struct hash_table *hash_table = (struct hash_table *)map;
uint32_t hash_entry;
@@ -150,27 +164,156 @@ hashtable_rm(struct qb_map *map, const char* key)
}
static void
-hashtable_put(struct qb_map *map, const char* key, const void* value)
+hashtable_put(struct qb_map *map, const char *key, const void *value)
{
struct hash_table *hash_table = (struct hash_table *)map;
uint32_t hash_entry;
- struct hash_node *hash_node;
+ struct hash_node *hash_node = NULL;
+ struct hash_node *node_try;
+ struct qb_list_head *list;
hash_entry = qb_hash_string(key, hash_table->order);
- (void)hashtable_rm_with_hash(map, key, hash_entry);
- hash_node = calloc(1, sizeof(struct hash_node));
+
+ for (list = hash_table->hash_buckets[hash_entry].list_head.next;
+ list != &hash_table->hash_buckets[hash_entry].list_head;
+ list = list->next) {
+
+ node_try = qb_list_entry(list, struct hash_node, list);
+ if (strcmp(node_try->key, key) == 0) {
+ hash_node = node_try;
+ break;
+ }
+ }
+
if (hash_node == NULL) {
- errno = ENOMEM;
- return;
+ hash_node = calloc(1, sizeof(struct hash_node));
+ if (hash_node == NULL) {
+ errno = ENOMEM;
+ return;
+ }
+
+ hash_table->count++;
+ hash_node->refcount = 1;
+ hash_node->key = key;
+ hash_node->value = (void *)value;
+ qb_list_init(&hash_node->list);
+ qb_list_add_tail(&hash_node->list,
+ &hash_table->hash_buckets[hash_entry].
+ list_head);
+ qb_list_init(&hash_node->notifier_head);
+
+ hashtable_notify(hash_table, hash_node,
+ QB_MAP_NOTIFY_INSERTED,
+ hash_node->key, hash_node->value, NULL, NULL);
+ } else {
+ char *old_k = (char *)hash_node->key;
+ char *old_v = (void *)hash_node->value;
+ hash_node->key = key;
+ hash_node->value = (void *)value;
+
+ hashtable_notify(hash_table, hash_node,
+ QB_MAP_NOTIFY_REPLACED,
+ old_k, old_v, hash_node->value, NULL);
}
+}
+
+static void
+hashtable_notify(struct hash_table *t, struct hash_node *n,
+ uint32_t event, const char *key,
+ void *old_value, void *value, void *user_data)
+{
+ struct qb_list_head *list;
+ struct qb_map_notifier *tn;
+
+ for (list = n->notifier_head.next;
+ list != &n->notifier_head; list = list->next) {
+ tn = qb_list_entry(list, struct qb_map_notifier, list);
- hash_table->count++;
- hash_node->key = key;
- hash_node->refcount = 1;
- hash_node->value = (void*)value;
- qb_list_init(&hash_node->list);
- qb_list_add_tail(&hash_node->list,
- &hash_table->hash_buckets[hash_entry].list_head);
+ if (tn->events & event) {
+ tn->callback(event, (char *)key, old_value, value,
+ user_data);
+ }
+ }
+ for (list = t->notifier_head.next;
+ list != &t->notifier_head; list = list->next) {
+ tn = qb_list_entry(list, struct qb_map_notifier, list);
+
+ if (tn->events & event) {
+ tn->callback(event, (char *)key, old_value, value,
+ user_data);
+ }
+ }
+}
+
+static int32_t
+hashtable_notify_add(qb_map_t * m, const char *key,
+ qb_map_notify_fn fn, int32_t events)
+{
+ struct hash_table *t = (struct hash_table *)m;
+ struct qb_map_notifier *f;
+ struct hash_node *n;
+ struct qb_list_head *head = NULL;
+ struct qb_list_head *list;
+
+ if (key) {
+ n = hashtable_lookup(t, key);
+ if (n) {
+ head = &n->notifier_head;
+ }
+ } else {
+ head = &t->notifier_head;
+ }
+ if (head == NULL) {
+ return -ENOENT;
+ }
+ for (list = head->next; list != head; list = list->next) {
+ f = qb_list_entry(list, struct qb_map_notifier, list);
+
+ if (f->events == events && f->callback == fn) {
+ return -EEXIST;
+ }
+ }
+
+ f = malloc(sizeof(struct qb_map_notifier));
+ f->events = events;
+ f->callback = fn;
+ qb_list_init(&f->list);
+ qb_list_add(&f->list, head);
+ return 0;
+}
+
+static int32_t
+hashtable_notify_del(qb_map_t * m, const char *key,
+ qb_map_notify_fn fn, int32_t events)
+{
+ struct hash_table *t = (struct hash_table *)m;
+ struct qb_map_notifier *f;
+ struct hash_node *n;
+ struct qb_list_head *head = NULL;
+ struct qb_list_head *list;
+
+ if (key) {
+ n = hashtable_lookup(t, key);
+ if (n) {
+ head = &n->notifier_head;
+ }
+ } else {
+ head = &t->notifier_head;
+ }
+ if (head == NULL) {
+ return -ENOENT;
+ }
+
+ for (list = head->next; list != head; list = list->next) {
+ f = qb_list_entry(list, struct qb_map_notifier, list);
+
+ if (f->events == events && f->callback == fn) {
+ qb_list_del(&f->list);
+ free(f);
+ return 0;
+ }
+ }
+ return -ENOENT;
}
static size_t
@@ -180,20 +323,20 @@ hashtable_count_get(struct qb_map *map)
return hash_table->count;
}
-static qb_map_iter_t*
-hashtable_iter_create(struct qb_map * map, const char* prefix)
+static qb_map_iter_t *
+hashtable_iter_create(struct qb_map *map, const char *prefix)
{
struct hashtable_iter *i = malloc(sizeof(struct hashtable_iter));
i->i.m = map;
i->node = NULL;
i->bucket = 0;
- return (qb_map_iter_t*)i;
+ return (qb_map_iter_t *) i;
}
-static const char*
-hashtable_iter_next(qb_map_iter_t* it, void** value)
+static const char *
+hashtable_iter_next(qb_map_iter_t * it, void **value)
{
- struct hashtable_iter *hi = (struct hashtable_iter*)it;
+ struct hashtable_iter *hi = (struct hashtable_iter *)it;
struct hash_table *hash_table = (struct hash_table *)hi->i.m;
struct qb_list_head *ln;
struct hash_node *hash_node = NULL;
@@ -204,8 +347,7 @@ hashtable_iter_next(qb_map_iter_t* it, void** value)
if (hi->node == NULL) {
cont = QB_FALSE;
}
- for (b = hi->bucket;
- b < hash_table->hash_buckets_len && !found; b++) {
+ for (b = hi->bucket; b < hash_table->hash_buckets_len && !found; b++)
{
if (cont) {
ln = hi->node->list.next;
cont = QB_FALSE;
@@ -236,7 +378,7 @@ hashtable_iter_next(qb_map_iter_t* it, void** value)
}
static void
-hashtable_iter_free(qb_map_iter_t* i)
+hashtable_iter_free(qb_map_iter_t * i)
{
free(i);
}
@@ -250,9 +392,7 @@ hashtable_destroy(struct qb_map *map)
}
qb_map_t *
-qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
- qb_destroy_notifier_func value_destroy_func,
- size_t max_size)
+qb_hashtable_create(size_t max_size)
{
int32_t i;
int32_t order;
@@ -269,9 +409,9 @@ qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
(sizeof(struct hash_bucket) * (1 << order));
ht = calloc(1, size);
-
- ht->map.key_destroy_func = key_destroy_func;
- ht->map.value_destroy_func = value_destroy_func;
+ if (ht == NULL) {
+ return NULL;
+ }
ht->map.put = hashtable_put;
ht->map.get = hashtable_get;
@@ -281,9 +421,11 @@ qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
ht->map.iter_next = hashtable_iter_next;
ht->map.iter_free = hashtable_iter_free;
ht->map.destroy = hashtable_destroy;
-
+ ht->map.notify_add = hashtable_notify_add;
+ ht->map.notify_del = hashtable_notify_del;
ht->count = 0;
ht->order = order;
+ qb_list_init(&ht->notifier_head);
ht->hash_buckets_len = 1 << order;
for (i = 0; i < ht->hash_buckets_len; i++) {
@@ -291,4 +433,3 @@ qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
}
return (qb_map_t *) ht;
}
-
diff --git a/lib/map.c b/lib/map.c
index a3b9466..5e92906 100644
--- a/lib/map.c
+++ b/lib/map.c
@@ -36,27 +36,26 @@ qb_map_get(struct qb_map *map, const char *key)
}
int32_t
-qb_map_rm(struct qb_map *map, const char *key)
+qb_map_rm(struct qb_map * map, const char *key)
{
return map->rm(map, key);
}
size_t
-qb_map_count_get(struct qb_map *map)
+qb_map_count_get(struct qb_map * map)
{
return map->count_get(map);
}
void
-qb_map_foreach(struct qb_map *map, qb_transverse_func func, void *user_data)
+qb_map_foreach(struct qb_map *map, qb_map_transverse_fn func, void *user_data)
{
- const char* key;
- void* value;
- qb_map_iter_t* i = qb_map_iter_create(map);
+ const char *key;
+ void *value;
+ qb_map_iter_t *i = qb_map_iter_create(map);
for (key = qb_map_iter_next(i, &value);
- key;
- key = qb_map_iter_next(i, &value)) {
+ key; key = qb_map_iter_next(i, &value)) {
if (func(key, value, user_data)) {
goto clean_up;
}
@@ -65,30 +64,52 @@ clean_up:
qb_map_iter_free(i);
}
-qb_map_iter_t*
+qb_map_iter_t *
qb_map_iter_create(struct qb_map *map)
{
return map->iter_create(map, NULL);
}
-qb_map_iter_t*
-qb_map_pref_iter_create(qb_map_t *map, const char* prefix)
+qb_map_iter_t *
+qb_map_pref_iter_create(qb_map_t * map, const char *prefix)
{
return map->iter_create(map, prefix);
}
-const char*
-qb_map_iter_next(struct qb_map_iter* i, void** value)
+const char *
+qb_map_iter_next(struct qb_map_iter *i, void **value)
{
return i->m->iter_next(i, value);
}
void
-qb_map_iter_free(qb_map_iter_t* i)
+qb_map_iter_free(qb_map_iter_t * i)
{
i->m->iter_free(i);
}
+int32_t
+qb_map_notify_add(qb_map_t * m, const char *key, qb_map_notify_fn fn,
+ int32_t events)
+{
+ if (m->notify_add) {
+ return m->notify_add(m, key, fn, events);
+ } else {
+ return -ENOSYS;
+ }
+}
+
+int32_t
+qb_map_notify_del(qb_map_t * m, const char *key, qb_map_notify_fn fn,
+ int32_t events)
+{
+ if (m->notify_del) {
+ return m->notify_del(m, key, fn, events);
+ } else {
+ return -ENOSYS;
+ }
+}
+
void
qb_map_destroy(struct qb_map *map)
{
diff --git a/lib/map_int.h b/lib/map_int.h
index f9cdd16..5e670e2 100644
--- a/lib/map_int.h
+++ b/lib/map_int.h
@@ -21,6 +21,8 @@
#ifndef _QB_MAP_INT_H_
#define _QB_MAP_INT_H_
+#include <qb/qblist.h>
+
struct qb_map;
typedef void (*qb_map_put_func)(struct qb_map *map, const char* key,
@@ -28,23 +30,18 @@ typedef void (*qb_map_put_func)(struct qb_map *map, const char* key,
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_destroy_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);
-struct qb_map {
- /* user provided
- */
- qb_destroy_notifier_func key_destroy_func;
- qb_destroy_notifier_func value_destroy_func;
+typedef int32_t (*qb_map_notify_add_func)(qb_map_t* m, const char* key,
+ qb_map_notify_fn fn, int32_t events);
+typedef int32_t (*qb_map_notify_del_func)(qb_map_t* m, const char* key,
+ qb_map_notify_fn fn, int32_t events);
- /* data type provided
- */
+struct qb_map {
qb_map_put_func put;
qb_map_get_func get;
qb_map_rm_func rm;
@@ -53,10 +50,19 @@ struct qb_map {
qb_map_iter_create_func iter_create;
qb_map_iter_next_func iter_next;
qb_map_iter_free_func iter_free;
+ qb_map_notify_add_func notify_add;
+ qb_map_notify_del_func notify_del;
};
struct qb_map_iter {
struct qb_map *m;
};
+struct qb_map_notifier {
+ struct qb_list_head list;
+ qb_map_notify_fn callback;
+ int32_t events;
+};
+
+
#endif /* _QB_MAP_INT_H_ */
diff --git a/lib/skiplist.c b/lib/skiplist.c
index b11d211..bf1c567 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -40,6 +40,7 @@ struct skiplist_node {
void *value;
int8_t level;
uint32_t refcount;
+ struct qb_list_head notifier_head;
/* An array of @level + 1 node pointers */
struct skiplist_node **forward;
@@ -57,8 +58,6 @@ struct skiplist {
*/
typedef struct skiplist_node *skiplist_update_t[SKIPLIST_LEVEL_COUNT];
-static int32_t skiplist_rm(struct qb_map *list, const char *key);
-
static int8_t
skiplist_level_generate(void)
{
@@ -96,11 +95,11 @@ skiplist_node_next(const struct skiplist_node *node)
/*
* Create a new level @level node with value @value. The node should eventually
* be destroyed with @skiplist_node_destroy.
- *
+ *
* return: a new node on success and NULL otherwise.
*/
static struct skiplist_node *
-skiplist_node_new(const int8_t level, const char* key, const void *value)
+skiplist_node_new(const int8_t level, const char *key, const void *value)
{
struct skiplist_node *new_node = (struct skiplist_node *)
(malloc(sizeof(struct skiplist_node)));
@@ -108,10 +107,11 @@ skiplist_node_new(const int8_t level, const char* key, const void
*value)
if (!new_node)
return NULL;
- new_node->value = (void*)value;
+ new_node->value = (void *)value;
new_node->key = key;
new_node->level = level;
new_node->refcount = 1;
+ qb_list_init(&new_node->notifier_head);
/* A level 0 node still needs to hold 1 forward pointer, etc. */
new_node->forward = (struct skiplist_node **)
@@ -131,17 +131,95 @@ skiplist_header_node_new(void)
return skiplist_node_new(SKIPLIST_LEVEL_MAX, NULL, NULL);
}
+/* An operation to perform after comparing a user value or search with a
+ * node's value
+ */
+typedef enum {
+ OP_GOTO_NEXT_LEVEL,
+ OP_GOTO_NEXT_NODE,
+ OP_FINISH,
+} op_t;
+
+static op_t
+op_search(const struct skiplist *list,
+ const struct skiplist_node *fwd_node, const void *search)
+{
+ int32_t cmp;
+
+ if (!fwd_node)
+ return OP_GOTO_NEXT_LEVEL;
+
+ cmp = strcmp(fwd_node->key, search);
+ if (cmp < 0) {
+ return OP_GOTO_NEXT_NODE;
+ } else if (cmp == 0) {
+ return OP_FINISH;
+ }
+
+ return OP_GOTO_NEXT_LEVEL;
+}
+
+static struct skiplist_node *
+skiplist_lookup(struct skiplist *list, const char *key)
+{
+ struct skiplist_node *cur_node = list->header;
+ int8_t level = list->level;
+
+ while (level >= SKIPLIST_LEVEL_MIN) {
+ struct skiplist_node *fwd_node = cur_node->forward[level];
+
+ switch (op_search(list, fwd_node, key)) {
+ case OP_FINISH:
+ return fwd_node;
+ case OP_GOTO_NEXT_NODE:
+ cur_node = fwd_node;
+ break;
+ case OP_GOTO_NEXT_LEVEL:
+ level--;
+ }
+ }
+
+ return NULL;
+}
+
static void
-skiplist_node_destroy(struct skiplist_node *node, struct skiplist *list)
+skiplist_notify(struct skiplist *l, struct skiplist_node *n,
+ uint32_t event,
+ char *key, void *old_value, void *value, void *user_data)
{
- if (list->map.value_destroy_func && node != list->header) {
- list->map.value_destroy_func(node->value);
+ struct qb_list_head *list;
+ struct qb_map_notifier *tn;
+
+ /* node callbacks
+ */
+ for (list = n->notifier_head.next;
+ list != &n->notifier_head; list = list->next) {
+ tn = qb_list_entry(list, struct qb_map_notifier, list);
+
+ if (tn->events & event) {
+ tn->callback(event, key, old_value, value, user_data);
+ }
}
+ /* global callbacks
+ */
+ for (list = l->header->notifier_head.next;
+ list != &l->header->notifier_head; list = list->next) {
+ tn = qb_list_entry(list, struct qb_map_notifier, list);
- if (list->map.key_destroy_func && node != list->header) {
- list->map.key_destroy_func((void*)node->key);
+ if (tn->events & event) {
+ tn->callback(event, key, old_value, value, user_data);
+ }
}
+}
+
+static void
+skiplist_node_destroy(struct skiplist_node *node, struct skiplist *list)
+{
+ skiplist_notify(list, node,
+ QB_MAP_NOTIFY_DELETED,
+ (char *)node->key, node->value, NULL, NULL);
+
free(node->forward);
free(node);
}
@@ -155,6 +233,43 @@ skiplist_node_deref(struct skiplist_node *node, struct skiplist
*list)
}
}
+static int32_t
+skiplist_notify_add(qb_map_t * m, const char *key,
+ qb_map_notify_fn fn, int32_t events)
+{
+ struct skiplist *t = (struct skiplist *)m;
+ struct qb_map_notifier *f;
+ struct skiplist_node *n;
+
+ if (key) {
+ n = skiplist_lookup(t, key);
+ } else {
+ n = t->header;
+ }
+ if (n) {
+ f = malloc(sizeof(struct qb_map_notifier));
+ f->events = events;
+ f->callback = fn;
+ qb_list_init(&f->list);
+ qb_list_add(&f->list, &n->notifier_head);
+ return 0;
+ }
+ return -EINVAL;
+}
+
+static int32_t
+skiplist_notify_del(qb_map_t * m, const char *key,
+ qb_map_notify_fn fn, int32_t events)
+{
+ struct skiplist *t = (struct skiplist *)m;
+ struct skiplist_node *n = skiplist_lookup(t, key);
+
+ if (n) {
+ return 0;
+ }
+ return -ENOENT;
+}
+
static void
skiplist_destroy(struct qb_map *map)
{
@@ -169,36 +284,8 @@ skiplist_destroy(struct qb_map *map)
free(list);
}
-/* An operation to perform after comparing a user value or search with a
- * node's value
- */
-typedef enum {
- OP_GOTO_NEXT_LEVEL,
- OP_GOTO_NEXT_NODE,
- OP_FINISH,
-} op_t;
-
-static op_t
-op_search(const struct skiplist *list,
- const struct skiplist_node *fwd_node, const void *search)
-{
- int32_t cmp;
-
- if (!fwd_node)
- return OP_GOTO_NEXT_LEVEL;
-
- cmp = strcmp(fwd_node->key, search);
- if (cmp < 0) {
- return OP_GOTO_NEXT_NODE;
- } else if (cmp == 0) {
- return OP_FINISH;
- }
-
- return OP_GOTO_NEXT_LEVEL;
-}
-
static void
-skiplist_put(struct qb_map * map, const char *key, const void *value)
+skiplist_put(struct qb_map *map, const char *key, const void *value)
{
struct skiplist *list = (struct skiplist *)map;
struct skiplist_node *new_node;
@@ -207,21 +294,21 @@ skiplist_put(struct qb_map * map, const char *key, const void
*value)
int8_t update_level;
int8_t new_node_level;
struct skiplist_node *cur_node = list->header;
+ char *old_k;
+ char *old_v;
while ((update_level = level) >= SKIPLIST_LEVEL_MIN) {
struct skiplist_node *fwd_node = cur_node->forward[level];
switch (op_search(list, fwd_node, key)) {
case OP_FINISH:
- if (map->key_destroy_func && fwd_node != list->header) {
- map->key_destroy_func((void*)fwd_node->key);
- }
- if (map->value_destroy_func && fwd_node != list->header) {
- map->value_destroy_func(fwd_node->value);
- }
-
- fwd_node->value = (void*)value;
- fwd_node->key = (void*)key;
+ old_k = (char *)fwd_node->key;
+ old_v = (char *)fwd_node->value;
+ fwd_node->value = (void *)value;
+ fwd_node->key = (void *)key;
+ skiplist_notify(list, fwd_node,
+ QB_MAP_NOTIFY_REPLACED,
+ old_k, old_v, fwd_node->value, NULL);
return;
case OP_GOTO_NEXT_NODE:
@@ -293,12 +380,13 @@ skiplist_rm(struct qb_map *map, const char *key)
/* Splice found_node out of list. */
for (level = SKIPLIST_LEVEL_MIN; level <= list->level; level++)
if (update[level]->forward[level] == found_node)
- update[level]->forward[level] = found_node->forward[level];
+ update[level]->forward[level] =
+ found_node->forward[level];
skiplist_node_deref(found_node, list);
/* Remove unused levels from @list -- stop removing levels as soon as a
- * used level is found. Unused levels can occur if @found_node had the
+ * used level is found. Unused levels can occur if @found_node had the
* highest level.
*/
for (level = list->level; level >= SKIPLIST_LEVEL_MIN; level--) {
@@ -317,41 +405,29 @@ static void *
skiplist_get(struct qb_map *map, const char *key)
{
struct skiplist *list = (struct skiplist *)map;
- struct skiplist_node *cur_node = list->header;
- int8_t level = list->level;
-
- while (level >= SKIPLIST_LEVEL_MIN) {
- struct skiplist_node *fwd_node = cur_node->forward[level];
-
- switch (op_search(list, fwd_node, key)) {
- case OP_FINISH:
- return fwd_node->value;
- case OP_GOTO_NEXT_NODE:
- cur_node = fwd_node;
- break;
- case OP_GOTO_NEXT_LEVEL:
- level--;
- }
+ struct skiplist_node *n = skiplist_lookup(list, key);
+ if (n) {
+ return n->value;
}
return NULL;
}
-static qb_map_iter_t*
-skiplist_iter_create(struct qb_map * map, const char* prefix)
+static qb_map_iter_t *
+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;
i->i.m = map;
i->n = list->header;
i->n->refcount++;
- return (qb_map_iter_t*)i;
+ return (qb_map_iter_t *) i;
}
-static const char*
-skiplist_iter_next(qb_map_iter_t* i, void** value)
+static const char *
+skiplist_iter_next(qb_map_iter_t * i, void **value)
{
- struct skiplist_iter *si = (struct skiplist_iter*)i;
+ struct skiplist_iter *si = (struct skiplist_iter *)i;
struct skiplist_node *p = si->n;
if (p == NULL) {
@@ -369,28 +445,27 @@ skiplist_iter_next(qb_map_iter_t* i, void** value)
}
static void
-skiplist_iter_free(qb_map_iter_t* i)
+skiplist_iter_free(qb_map_iter_t * i)
{
free(i);
}
static size_t
-skiplist_count_get(struct qb_map * map)
+skiplist_count_get(struct qb_map *map)
{
struct skiplist *list = (struct skiplist *)map;
return list->length;
}
qb_map_t *
-qb_skiplist_create(qb_destroy_notifier_func key_destroy_func,
- qb_destroy_notifier_func value_destroy_func)
+qb_skiplist_create(void)
{
- struct skiplist *sl = calloc(1, sizeof(struct skiplist));
-
- srand(time(NULL));
+ struct skiplist *sl = malloc(sizeof(struct skiplist));
+ if (sl == NULL) {
+ return NULL;
+ }
- sl->map.key_destroy_func = key_destroy_func;
- sl->map.value_destroy_func = value_destroy_func;
+ srand(time(NULL));
sl->map.put = skiplist_put;
sl->map.get = skiplist_get;
@@ -400,11 +475,11 @@ qb_skiplist_create(qb_destroy_notifier_func key_destroy_func,
sl->map.iter_next = skiplist_iter_next;
sl->map.iter_free = skiplist_iter_free;
sl->map.destroy = skiplist_destroy;
-
+ sl->map.notify_add = skiplist_notify_add;
+ sl->map.notify_del = skiplist_notify_del;
sl->level = SKIPLIST_LEVEL_MIN;
sl->length = 0;
sl->header = skiplist_header_node_new();
return (qb_map_t *) sl;
}
-
diff --git a/lib/trie.c b/lib/trie.c
index fd50e94..888f3bc 100644
--- a/lib/trie.c
+++ b/lib/trie.c
@@ -22,6 +22,7 @@
#include <assert.h>
#include <qb/qbdefs.h>
+#include <qb/qblist.h>
#include <qb/qbmap.h>
#include "map_int.h"
@@ -38,8 +39,9 @@ struct trie_node {
void *value;
struct trie_node **children;
uint32_t num_children;
- int32_t refcount;
+ uint32_t refcount;
struct trie_node *parent;
+ struct qb_list_head notifier_head;
};
struct trie {
@@ -49,7 +51,8 @@ struct trie {
struct trie_node *header;
};
-static int32_t trie_rm(struct qb_map *list, const char *key);
+static void trie_notify(struct trie_node *n, uint32_t event, const char *key,
+ void *old_value, void *value, void *user_data);
/*
* characters are stored in reverse to make accessing the
@@ -68,7 +71,8 @@ trie_node_next(struct trie_node *node, struct trie_node *root)
keep_going:
n = NULL;
- // child/outward
+ /* child/outward
+ */
for (i = c->num_children - 1; i >= 0; i--) {
if (c->children[i]) {
n = c->children[i];
@@ -83,7 +87,8 @@ keep_going:
goto keep_going;
}
}
- // sibling/parent
+ /* sibling/parent
+ */
if (c == root) {
return NULL;
}
@@ -115,65 +120,62 @@ keep_going:
}
static void
-trie_node_destroy(struct trie *t, struct trie_node *node)
+trie_node_destroy(struct trie *t, struct trie_node *n)
{
- if (t->map.value_destroy_func && node != t->header) {
- t->map.value_destroy_func(node->value);
- }
+ trie_notify(n, QB_MAP_NOTIFY_DELETED, n->key, n->value, NULL, NULL);
- if (t->map.key_destroy_func && node != t->header) {
- t->map.key_destroy_func((void*)node->key);
- }
- node->key = NULL;
- node->value = NULL;
+ n->key = NULL;
+ n->value = NULL;
}
static void
trie_node_deref(struct trie *t, struct trie_node *node)
{
node->refcount--;
- if (node->refcount == 0) {
- trie_node_destroy(t, node);
+ if (node->refcount > 0) {
+ return;
}
+ trie_node_destroy(t, node);
}
static void
trie_destroy(struct qb_map *map)
{
- struct trie *list = (struct trie *)map;
-#if 0
- struct trie_node *cur_node = list->header;
+ 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);
- trie_node_destroy(cur_node, list);
+ fwd_node = trie_node_next(cur_node, t->header);
+ trie_node_destroy(t, cur_node);
} while ((cur_node = fwd_node));
-#endif
- free(list);
+
+ free(t);
}
-static struct trie_node*
-trie_new_node(struct trie * t, struct trie_node* parent)
+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));
+ struct trie_node *new_node = calloc(1, sizeof(struct trie_node));
new_node->parent = parent;
new_node->num_children = 30;
new_node->children = calloc(new_node->num_children,
- sizeof(struct trie_node*));
+ sizeof(struct trie_node *));
+ qb_list_init(&new_node->notifier_head);
return new_node;
}
-static struct trie_node*
-trie_lookup(struct trie * t, const char *key, int32_t create_path)
+static struct trie_node *
+trie_lookup(struct trie *t, const char *key, int32_t create_path)
{
- struct trie_node* cur_node = t->header;
- struct trie_node* new_node;
+ struct trie_node *cur_node = t->header;
+ struct trie_node *new_node;
int old_max_idx;
int i;
- char *cur = (char*)key;
+ char *cur = (char *)key;
int idx = TRIE_CHAR2INDEX(key[0]);
do {
@@ -182,15 +184,19 @@ trie_lookup(struct trie * t, const char *key, int32_t create_path)
return NULL;
}
if (cur_node->num_children == 0) {
- old_max_idx = 0;
+ old_max_idx = 0;
} else {
old_max_idx = cur_node->num_children;
}
cur_node->num_children = idx + 1;
cur_node->children = realloc(cur_node->children,
(cur_node->num_children *
- sizeof(struct trie_node*)));
- //printf("%s(%d) %d %d\n", __func__, idx, old_max_idx,
cur_node->num_children);
+ sizeof(struct trie_node
+ *)));
+ /*
+ printf("%s(%d) %d %d\n", __func__, idx,
+ old_max_idx, cur_node->num_children);
+ */
for (i = old_max_idx; i < cur_node->num_children; i++) {
cur_node->children[i] = NULL;
}
@@ -212,25 +218,27 @@ trie_lookup(struct trie * t, const char *key, int32_t create_path)
}
static void
-trie_put(struct qb_map * map, const char *key, const void *value)
+trie_put(struct qb_map *map, const char *key, const void *value)
{
struct trie *t = (struct trie *)map;
struct trie_node *n = trie_lookup(t, key, QB_TRUE);
if (n) {
- if (n->value == NULL) {
+ const char *old_value = n->value;
+ const char *old_key = n->key;
+
+ n->key = (char *)key;
+ n->value = (void *)value;
+
+ if (old_value == NULL) {
+ n->refcount++;
t->length++;
+ trie_notify(n, QB_MAP_NOTIFY_INSERTED,
+ n->key, NULL, n->value, NULL);
} else {
- if (t->map.value_destroy_func && n != t->header) {
- t->map.value_destroy_func(n->value);
- }
-
- if (t->map.key_destroy_func && n != t->header) {
- t->map.key_destroy_func((void*)n->key);
- }
+ trie_notify(n, QB_MAP_NOTIFY_REPLACED,
+ (char *)old_key, (void *)old_value,
+ (void *)value, NULL);
}
- n->key = (char*)key;
- n->value = (void*)value;
- n->refcount++;
}
}
@@ -260,8 +268,91 @@ trie_get(struct qb_map *map, const char *key)
return NULL;
}
-static qb_map_iter_t*
-trie_iter_create(struct qb_map * map, const char* prefix)
+static void
+trie_notify(struct trie_node *n,
+ uint32_t event,
+ const char *key, void *old_value, void *value, void *user_data)
+{
+ 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, 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)
+{
+ struct trie *t = (struct trie *)m;
+ struct qb_map_notifier *f;
+ struct trie_node *n;
+
+ if (key) {
+ n = trie_lookup(t, key, QB_TRUE);
+ } else {
+ n = t->header;
+ }
+ if (n) {
+ f = malloc(sizeof(struct qb_map_notifier));
+ f->events = events;
+ f->callback = fn;
+ qb_list_init(&f->list);
+ if (events & QB_MAP_NOTIFY_RECURSIVE) {
+ qb_list_add(&f->list, &n->notifier_head);
+ } else {
+ qb_list_add_tail(&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)
+{
+ struct trie *t = (struct trie *)m;
+ struct qb_map_notifier *f;
+ struct trie_node *n;
+ struct qb_list_head *list;
+
+ if (key) {
+ n = trie_lookup(t, key, QB_TRUE);
+ } else {
+ n = t->header;
+ }
+ if (n == NULL) {
+ return -ENOENT;
+ }
+ for (list = n->notifier_head.next;
+ list != &n->notifier_head; list = list->next) {
+ f = qb_list_entry(list, struct qb_map_notifier, list);
+
+ if (f->events == events && f->callback == fn) {
+ qb_list_del(&f->list);
+ free(f);
+ return 0;
+ }
+ }
+ 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;
@@ -270,13 +361,13 @@ trie_iter_create(struct qb_map * map, const char* prefix)
i->n = t->header;
i->root = t->header;
i->n->refcount++;
- return (qb_map_iter_t*)i;
+ return (qb_map_iter_t *) i;
}
-static const char*
-trie_iter_next(qb_map_iter_t* i, void** value)
+static const char *
+trie_iter_next(qb_map_iter_t * i, void **value)
{
- struct trie_iter *si = (struct trie_iter*)i;
+ struct trie_iter *si = (struct trie_iter *)i;
struct trie_node *p = si->n;
struct trie *t = (struct trie *)(i->m);
@@ -307,41 +398,38 @@ trie_iter_next(qb_map_iter_t* i, void** value)
}
static void
-trie_iter_free(qb_map_iter_t* i)
+trie_iter_free(qb_map_iter_t * i)
{
free(i);
}
static size_t
-trie_count_get(struct qb_map * map)
+trie_count_get(struct qb_map *map)
{
struct trie *list = (struct trie *)map;
return list->length;
}
qb_map_t *
-qb_trie_create(qb_destroy_notifier_func key_destroy_func,
- qb_destroy_notifier_func value_destroy_func)
+qb_trie_create(void)
{
- struct trie *sl = calloc(1, sizeof(struct trie));
-
- srand(time(NULL));
-
- sl->map.key_destroy_func = key_destroy_func;
- sl->map.value_destroy_func = value_destroy_func;
-
- sl->map.put = trie_put;
- sl->map.get = trie_get;
- sl->map.rm = trie_rm;
- sl->map.count_get = trie_count_get;
- sl->map.iter_create = trie_iter_create;
- sl->map.iter_next = trie_iter_next;
- sl->map.iter_free = trie_iter_free;
- sl->map.destroy = trie_destroy;
-
- sl->length = 0;
- sl->header = trie_new_node(sl, NULL);
+ struct trie *t = malloc(sizeof(struct trie));
+ if (t == NULL) {
+ return NULL;
+ }
- return (qb_map_t *) sl;
+ 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->header = trie_new_node(t, NULL);
+
+ return (qb_map_t *) t;
}
-
diff --git a/tests/check_map.c b/tests/check_map.c
index 2665622..d3ea622 100644
--- a/tests/check_map.c
+++ b/tests/check_map.c
@@ -39,14 +39,15 @@ const char *chars2[] = {
NULL,
};
-static void *destroyed_key = NULL;
-static void *destroyed_value = NULL;
+static char *notified_key = NULL;
+static void *notified_value = NULL;
+static void *notified_new_value = NULL;
static void
test_map_simple(qb_map_t *m, const char *name)
{
int i;
- char *p;
+ const char *p;
void *data;
qb_map_iter_t *it;
@@ -59,10 +60,8 @@ test_map_simple(qb_map_t *m, const char *name)
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);
+ 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);
@@ -182,15 +181,13 @@ test_map_search(qb_map_t* m)
}
static void
-my_key_destroy(void *key)
-{
- destroyed_key = key;
-}
-
-static void
-my_value_destroy(void *value)
+my_map_notification(uint32_t event,
+ char* key, void* old_value,
+ void* value, void* user_data)
{
- destroyed_value = value;
+ notified_key = key;
+ notified_value = old_value;
+ notified_new_value = value;
}
static void
@@ -201,39 +198,45 @@ test_map_remove(qb_map_t *m)
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));
+ 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(destroyed_key == chars[0]);
- ck_assert(destroyed_value == chars[0]);
- destroyed_key = NULL;
- destroyed_value = NULL;
+ ck_assert(notified_key == chars[0]);
+ ck_assert(notified_value == chars[0]);
+ notified_key = NULL;
+ notified_value = NULL;
b = "5";
removed = qb_map_rm(m, b);
ck_assert(removed);
- ck_assert(destroyed_key == chars[5]);
- ck_assert(destroyed_value == chars[5]);
- destroyed_key = NULL;
- destroyed_value = NULL;
+ ck_assert(notified_key == chars[5]);
+ ck_assert(notified_value == chars[5]);
+ notified_key = NULL;
+ notified_value = NULL;
d = "1";
qb_map_put(m, d, d);
- ck_assert(destroyed_key == chars[1]);
- ck_assert(destroyed_value == chars[1]);
- destroyed_key = NULL;
- destroyed_value = NULL;
+ ck_assert(notified_key == chars[1]);
+ ck_assert(notified_value == chars[1]);
+ notified_key = NULL;
+ notified_value = NULL;
c = "2";
removed = qb_map_rm(m, c);
ck_assert(removed);
- ck_assert(destroyed_key == chars[2]);
- ck_assert(destroyed_value == chars[2]);
- destroyed_key = NULL;
- destroyed_value = NULL;
+ 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]);
@@ -243,6 +246,88 @@ test_map_remove(qb_map_t *m)
qb_map_destroy(m);
}
+
+static void
+test_map_notifications(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));
+ ck_assert_int_eq(i, 0);
+
+/* insert */
+ qb_map_put(m, "garden", "grow");
+ ck_assert_str_eq(notified_key, "garden");
+ ck_assert_str_eq(notified_new_value, "grow");
+
+/* 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");
+
+/* delete */
+ qb_map_rm(m, "garden");
+ ck_assert_str_eq(notified_key, "garden");
+ ck_assert_str_eq(notified_value, "green");
+
+/* 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);
+
+
+/* with prefic 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));
+ 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");
+
+/* 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)
{
@@ -258,10 +343,8 @@ test_map_traverse_ordered(qb_map_t *m)
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;
+ 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);
@@ -416,7 +499,7 @@ test_map_load(qb_map_t *m, const char* test_name)
qb_util_stopwatch_t *sw;
ck_assert(m != NULL);
- sw = qb_util_stopwatch_create();
+ sw = qb_util_stopwatch_create();
/*
* Load with dictionary
@@ -492,73 +575,72 @@ test_map_load(qb_map_t *m, const char* test_name)
START_TEST(test_skiplist_simple)
{
- qb_map_t *m = qb_skiplist_create(NULL, NULL);
+ 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(NULL, NULL, 32);
+ 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(NULL, NULL);
+ 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(NULL, NULL);
+ 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(NULL, NULL);
+ 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(my_key_destroy,
- my_value_destroy);
+ 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(my_key_destroy,
- my_value_destroy, 256);
+ qb_map_t *m = qb_hashtable_create(256);
test_map_remove(m);
}
END_TEST
-START_TEST(test_trie_remove)
+START_TEST(test_trie_notifications)
{
- qb_map_t *m = qb_trie_create(my_key_destroy,
- my_value_destroy);
+ qb_map_t *m;
+ m = qb_trie_create();
test_map_remove(m);
+ m = qb_trie_create();
+ test_map_notifications(m);
}
END_TEST
START_TEST(test_skiplist_traverse)
{
qb_map_t *m;
- m = qb_skiplist_create(NULL, NULL);
+ m = qb_skiplist_create();
test_map_traverse_ordered(m);
- m = qb_skiplist_create(NULL, NULL);
+ m = qb_skiplist_create();
test_map_traverse_unordered(m);
-
- m = qb_skiplist_create(NULL, NULL);
+ m = qb_skiplist_create();
test_map_iter_safety(m, QB_TRUE);
}
END_TEST
@@ -566,9 +648,9 @@ END_TEST
START_TEST(test_hashtable_traverse)
{
qb_map_t *m;
- m = qb_hashtable_create(NULL, NULL, 256);
+ m = qb_hashtable_create(256);
test_map_traverse_unordered(m);
- m = qb_hashtable_create(NULL, NULL, 256);
+ m = qb_hashtable_create(256);
test_map_iter_safety(m, QB_FALSE);
}
END_TEST
@@ -576,11 +658,11 @@ END_TEST
START_TEST(test_trie_traverse)
{
qb_map_t *m;
- m = qb_trie_create(NULL, NULL);
+ m = qb_trie_create();
test_map_traverse_unordered(m);
- m = qb_trie_create(NULL, NULL);
+ m = qb_trie_create();
test_map_iter_safety(m, QB_FALSE);
- m = qb_trie_create(NULL, NULL);
+ m = qb_trie_create();
test_map_iter_prefix(m);
}
END_TEST
@@ -592,7 +674,7 @@ START_TEST(test_skiplist_load)
printf("no dict/words - not testing\n");
return;
}
- m = qb_skiplist_create(NULL, NULL);
+ m = qb_skiplist_create();
test_map_load(m, __func__);
}
END_TEST
@@ -604,7 +686,7 @@ START_TEST(test_hashtable_load)
printf("no dict/words - not testing\n");
return;
}
- m = qb_hashtable_create(NULL, NULL, 100000);
+ m = qb_hashtable_create(100000);
test_map_load(m, __func__);
}
END_TEST
@@ -616,7 +698,7 @@ START_TEST(test_trie_load)
printf("no dict/words - not testing\n");
return;
}
- m = qb_trie_create(NULL, NULL);
+ m = qb_trie_create();
test_map_load(m, __func__);
}
END_TEST
@@ -647,8 +729,8 @@ map_suite(void)
tcase_add_test(tc, test_hashtable_remove);
suite_add_tcase(s, tc);
- tc = tcase_create("trie_remove");
- tcase_add_test(tc, test_trie_remove);
+ tc = tcase_create("trie_notifications");
+ tcase_add_test(tc, test_trie_notifications);
suite_add_tcase(s, tc);
tc = tcase_create("skiplist_search");
--
1.7.6