9:39 p.m.
Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
include/qb/qbmap.h | 24 +++++++++
lib/hashtable.c | 108 ++++++++++++++++++++++++++------------
lib/map.c | 32 +++++++++++-
lib/map_int.h | 11 ++++-
lib/skiplist.c | 75 +++++++++++++++++++++------
tests/check_map.c | 146 +++++++++++++++++++++++++++++++++++----------------
6 files changed, 296 insertions(+), 100 deletions(-)
diff --git a/include/qb/qbmap.h b/include/qb/qbmap.h
index 15cd981..b430d8b 100644
--- a/include/qb/qbmap.h
+++ b/include/qb/qbmap.h
@@ -38,6 +38,7 @@ extern "C" {
* This is an opaque data type representing an instance of a map.
*/
typedef struct qb_map qb_map_t;
+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);
@@ -110,6 +111,29 @@ size_t qb_map_count_get(qb_map_t *map);
void qb_map_foreach(qb_map_t *map, qb_transverse_func func, void* user_data);
/**
+ * Create an iterator
+ */
+qb_map_iter_t* qb_map_iter_create(qb_map_t *map);
+
+/**
+ * Get the next item
+ *
+ * @param i the iterator
+ * @param value (out) the next item's value
+ *
+ * @retval the next key
+ * @retval NULL - the end of the iteration
+ */
+const char* qb_map_iter_next(qb_map_iter_t* i, void** value);
+
+/**
+ * free the iterator
+ *
+ * @param i the iterator
+ */
+void qb_map_iter_free(qb_map_iter_t* i);
+
+/**
* Destroy the map, removes all the items from the map.
*/
void qb_map_destroy(qb_map_t *map);
diff --git a/lib/hashtable.c b/lib/hashtable.c
index f4fb6db..9d53c98 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -31,6 +31,7 @@ struct hash_node {
struct qb_list_head list;
void *value;
const char *key;
+ uint32_t refcount;
};
struct hash_bucket {
@@ -45,6 +46,12 @@ struct hash_table {
struct hash_bucket hash_buckets[0];
};
+struct hashtable_iter {
+ struct qb_map_iter i;
+ struct hash_node *node;
+ uint32_t bucket;
+};
+
static uint32_t
hash_fnv(const void *value, uint32_t valuelen, uint32_t order)
{
@@ -92,6 +99,23 @@ hashtable_get(struct qb_map *map, const char* key)
return NULL;
}
+static void
+hashtable_node_deref(struct qb_map *map, struct hash_node *hash_node)
+{
+ 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);
+ }
+ qb_list_del(&hash_node->list);
+ free(hash_node);
+}
+
static int32_t
hashtable_rm_with_hash(struct qb_map *map, const void* key,
uint32_t hash_entry)
@@ -106,14 +130,7 @@ hashtable_rm_with_hash(struct qb_map *map, const void* key,
hash_node = qb_list_entry(list, struct hash_node, list);
if (strcmp(hash_node->key, key) == 0) {
- 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);
- }
- qb_list_del(&hash_node->list);
- free(hash_node);
+ hashtable_node_deref(map, hash_node);
hash_table->count--;
return QB_TRUE;
}
@@ -149,6 +166,7 @@ hashtable_put(struct qb_map *map, const char* key, const void* value)
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,
@@ -163,28 +181,59 @@ hashtable_count_get(struct qb_map *map)
return hash_table->count;
}
-static void
-hashtable_foreach(struct qb_map *map, qb_transverse_func func, void* user_data)
+static qb_map_iter_t*
+hashtable_iter_create(struct qb_map * map)
{
- struct hash_table *hash_table = (struct hash_table *)map;
+ 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;
+}
+
+static const char*
+hashtable_iter_next(qb_map_iter_t* it, void** value)
+{
+ struct hashtable_iter *hi = (struct hashtable_iter*)it;
+ struct hash_table *hash_table = (struct hash_table *)hi->i.m;
struct qb_list_head *list;
struct qb_list_head *next;
- struct hash_node *hash_node;
- int32_t i;
-
- for (i = 0; i < hash_table->hash_buckets_len; i++) {
- for (list = hash_table->hash_buckets[i].list_head.next;
- list != &hash_table->hash_buckets[i].list_head;
+ struct hash_node *hash_node = NULL;
+ int b;
+
+ for (b = hi->bucket; b < hash_table->hash_buckets_len; b++) {
+ if (hi->bucket == b && hi->node) {
+ list = hi->node->list.next;
+ } else {
+ list = hash_table->hash_buckets[b].list_head.next;
+ }
+ for (;
+ list != &hash_table->hash_buckets[b].list_head;
list = next) {
next = list->next;
-
hash_node = qb_list_entry(list, struct hash_node, list);
- if (func(hash_node->key, hash_node->value, user_data)) {
- return;
- }
+ *value = hash_node->value;
+ break;
}
}
+
+ if (hi->node) {
+ hashtable_node_deref(hi->i.m, hi->node);
+ }
+ if (hash_node == NULL) {
+ return NULL;
+ }
+ hash_node->refcount++;
+ hi->node = hash_node;
+ hi->bucket = b;
+ return hash_node->key;
+}
+
+static void
+hashtable_iter_free(qb_map_iter_t* i)
+{
+ free(i);
}
static void
@@ -223,7 +272,9 @@ qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
ht->map.get = hashtable_get;
ht->map.rm = hashtable_rm;
ht->map.count_get = hashtable_count_get;
- ht->map.foreach = hashtable_foreach;
+ ht->map.iter_create = hashtable_iter_create;
+ ht->map.iter_next = hashtable_iter_next;
+ ht->map.iter_free = hashtable_iter_free;
ht->map.destroy = hashtable_destroy;
ht->count = 0;
@@ -236,16 +287,3 @@ qb_hashtable_create(qb_destroy_notifier_func key_destroy_func,
return (qb_map_t *) ht;
}
-#if 0
-int32_t qb_hash_key_context_get(qb_handle_t handle,
- const char *key, void **context)
-{
- struct hash_table *hash_table;
- int32_t res = 0;
-
- qb_hdb_handle_get(&qb_hash_handle_db, handle, (void *)&hash_table);
- qb_hdb_handle_put(&qb_hash_handle_db, handle);
- return (res);
-}
-#endif
-
diff --git a/lib/map.c b/lib/map.c
index f8df18e..2d356b4 100644
--- a/lib/map.c
+++ b/lib/map.c
@@ -50,7 +50,37 @@ qb_map_count_get(struct qb_map *map)
void
qb_map_foreach(struct qb_map *map, qb_transverse_func func, void *user_data)
{
- map->foreach(map, func, user_data);
+ 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)) {
+ if (func(key, value, user_data)) {
+ goto clean_up;
+ }
+ }
+clean_up:
+ qb_map_iter_free(i);
+}
+
+qb_map_iter_t*
+qb_map_iter_create(struct qb_map *map)
+{
+ return map->iter_create(map);
+}
+
+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)
+{
+ i->m->iter_free(i);
}
void
diff --git a/lib/map_int.h b/lib/map_int.h
index 2c21409..46bb67c 100644
--- a/lib/map_int.h
+++ b/lib/map_int.h
@@ -29,6 +29,9 @@ 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);
+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
@@ -42,8 +45,14 @@ struct qb_map {
qb_map_get_func get;
qb_map_rm_func rm;
qb_map_count_get_func count_get;
- qb_map_foreach_func foreach;
qb_map_destroy_func destroy;
+ qb_map_iter_create_func iter_create;
+ qb_map_iter_next_func iter_next;
+ qb_map_iter_free_func iter_free;
+};
+
+struct qb_map_iter {
+ struct qb_map *m;
};
#endif /* _QB_MAP_INT_H_ */
diff --git a/lib/skiplist.c b/lib/skiplist.c
index 67964e1..00adfe2 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -30,10 +30,16 @@
/* The amount of possible levels */
#define SKIPLIST_LEVEL_COUNT (SKIPLIST_LEVEL_MAX - SKIPLIST_LEVEL_MIN + 1)
+struct skiplist_iter {
+ struct qb_map_iter i;
+ struct skiplist_node *n;
+};
+
struct skiplist_node {
const char *key;
void *value;
int8_t level;
+ uint32_t refcount;
/* An array of @level + 1 node pointers */
struct skiplist_node **forward;
@@ -77,10 +83,14 @@ skiplist_level_generate(void)
return SKIPLIST_LEVEL_MAX;
}
-static inline struct skiplist_node *
+static struct skiplist_node *
skiplist_node_next(const struct skiplist_node *node)
{
- return node->forward[SKIPLIST_LEVEL_MIN];
+ const struct skiplist_node *n = node;
+ do {
+ n = n->forward[SKIPLIST_LEVEL_MIN];
+ } while (n && n->refcount == 0);
+ return (struct skiplist_node *)n;
}
/*
@@ -101,6 +111,7 @@ skiplist_node_new(const int8_t level, const char* key, const void
*value)
new_node->value = (void*)value;
new_node->key = key;
new_node->level = level;
+ new_node->refcount = 1;
/* A level 0 node still needs to hold 1 forward pointer, etc. */
new_node->forward = (struct skiplist_node **)
@@ -114,7 +125,7 @@ skiplist_node_new(const int8_t level, const char* key, const void
*value)
return NULL;
}
-static inline struct skiplist_node *
+static struct skiplist_node *
skiplist_header_node_new(void)
{
return skiplist_node_new(SKIPLIST_LEVEL_MAX, NULL, NULL);
@@ -136,6 +147,15 @@ skiplist_node_destroy(struct skiplist_node *node, struct skiplist
*list)
}
static void
+skiplist_node_deref(struct skiplist_node *node, struct skiplist *list)
+{
+ node->refcount--;
+ if (node->refcount == 0) {
+ skiplist_node_destroy(node, list);
+ }
+}
+
+static void
skiplist_destroy(struct qb_map *map)
{
struct skiplist *list = (struct skiplist *)map;
@@ -276,7 +296,7 @@ skiplist_rm(struct qb_map *map, const char *key)
if (update[level]->forward[level] == found_node)
update[level]->forward[level] = found_node->forward[level];
- skiplist_node_destroy(found_node, list);
+ 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
@@ -318,21 +338,40 @@ skiplist_get(struct qb_map *map, const char *key)
return NULL;
}
-static void
-qb_skiplist_foreach(struct qb_map * map, qb_transverse_func func,
- void *user_data)
+static qb_map_iter_t*
+skiplist_iter_create(struct qb_map * map)
{
+ struct skiplist_iter *i = malloc(sizeof(struct skiplist_iter));
struct skiplist *list = (struct skiplist *)map;
- struct skiplist_node *cur_node = skiplist_node_next(list->header);
- struct skiplist_node *fwd_node;
-
- while (cur_node) {
- fwd_node = skiplist_node_next(cur_node);
- if (func(cur_node->key, cur_node->value, user_data)) {
- return;
- }
- cur_node = fwd_node;
+ i->i.m = map;
+ i->n = list->header;
+ i->n->refcount++;
+ return (qb_map_iter_t*)i;
+}
+
+static const char*
+skiplist_iter_next(qb_map_iter_t* i, void** value)
+{
+ struct skiplist_iter *si = (struct skiplist_iter*)i;
+ struct skiplist_node *p = si->n;
+
+ if (p == NULL) {
+ return NULL;
}
+ si->n = skiplist_node_next(p);
+ skiplist_node_deref(p, (struct skiplist *)i->m);
+ if (si->n == NULL) {
+ return NULL;
+ }
+ si->n->refcount++;
+ *value = si->n->value;
+ return si->n->key;
+}
+
+static void
+skiplist_iter_free(qb_map_iter_t* i)
+{
+ free(i);
}
static size_t
@@ -357,7 +396,9 @@ qb_skiplist_create(qb_destroy_notifier_func key_destroy_func,
sl->map.get = skiplist_get;
sl->map.rm = skiplist_rm;
sl->map.count_get = skiplist_count_get;
- sl->map.foreach = qb_skiplist_foreach;
+ sl->map.iter_create = skiplist_iter_create;
+ sl->map.iter_next = skiplist_iter_next;
+ sl->map.iter_free = skiplist_iter_free;
sl->map.destroy = skiplist_destroy;
sl->level = SKIPLIST_LEVEL_MIN;
diff --git a/tests/check_map.c b/tests/check_map.c
index 65f5efd..b66497d 100644
--- a/tests/check_map.c
+++ b/tests/check_map.c
@@ -178,26 +178,26 @@ my_value_destroy(void *value)
}
static void
-test_map_remove(qb_map_t *tree)
+test_map_remove(qb_map_t *m)
{
- char * a, *b, *c, *d;
+ 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};
for (i = 0; chars[i]; i++) {
- qb_map_put(tree, chars[i], chars[i]);
+ qb_map_put(m, chars[i], chars[i]);
}
a = "0";
- qb_map_put(tree, a, a);
+ qb_map_put(m, a, a);
ck_assert(destroyed_key == chars[0]);
ck_assert(destroyed_value == chars[0]);
destroyed_key = NULL;
destroyed_value = NULL;
b = "5";
- removed = qb_map_rm(tree, b);
+ removed = qb_map_rm(m, b);
ck_assert(removed);
ck_assert(destroyed_key == chars[5]);
ck_assert(destroyed_value == chars[5]);
@@ -205,14 +205,14 @@ test_map_remove(qb_map_t *tree)
destroyed_value = NULL;
d = "1";
- qb_map_put(tree, d, d);
+ qb_map_put(m, d, d);
ck_assert(destroyed_key == chars[1]);
ck_assert(destroyed_value == chars[1]);
destroyed_key = NULL;
destroyed_value = NULL;
c = "2";
- removed = qb_map_rm(tree, c);
+ removed = qb_map_rm(m, c);
ck_assert(removed);
ck_assert(destroyed_key == chars[2]);
ck_assert(destroyed_value == chars[2]);
@@ -220,64 +220,108 @@ test_map_remove(qb_map_t *tree)
destroyed_value = NULL;
for (i = 0; remove_ch[i]; i++) {
- removed = qb_map_rm(tree, remove_ch[i]);
+ removed = qb_map_rm(m, remove_ch[i]);
ck_assert(removed);
}
- qb_map_destroy(tree);
-}
-
-static int32_t
-traverse_func(const char *key, void *value, void *data)
-{
- char *c = value;
- char **p = data;
-
- **p = *c;
- (*p)++;
-
- return QB_FALSE;
+ qb_map_destroy(m);
}
static void
-test_map_traverse_ordered(qb_map_t *tree)
+test_map_traverse_ordered(qb_map_t *m)
{
int32_t i;
- char *p, *result;
+ 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(tree, chars[i], chars[i]);
+ qb_map_put(m, chars[i], chars[i]);
}
result = calloc(sizeof(char), 26 * 2 + 10 + 1);
- p = result;
- qb_map_foreach(tree, traverse_func, &p);
+ 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(tree);
+ 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, key);
- qb_map_put(m, key + 20, key);
+ qb_map_rm(m, chars[kk]);
+ qb_map_put(m, chars[kk+30], key);
return QB_FALSE;
}
static void
-test_map_traverse_unordered(qb_map_t *tree)
+test_map_iter_safety(qb_map_t *m, int32_t ordered)
{
- int32_t i;
- for (i = 0; i < 20; i++) {
- qb_map_put(tree, chars[i], chars[i]);
+ 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_foreach(tree, traverse_and_remove_func, tree);
+ qb_map_iter_free(it);
+
+ if (ordered) {
+ ck_assert_int_eq(found_good, QB_TRUE);
+ }
+
+ 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)
{
@@ -308,7 +352,7 @@ test_map_load(qb_map_t *m, const char* test_name)
fp = fopen("/usr/share/dict/words", "r");
qb_util_stopwatch_start(sw);
count = 0;
- while (fgets(word, sizeof(word), fp)) {
+ while (fgets(word, sizeof(word), fp) && count < 100000) {
word[strlen(word) - 1] = '\0';
w = strdup(word);
qb_map_put(m, w, w);
@@ -326,10 +370,12 @@ test_map_load(qb_map_t *m, const char* test_name)
*/
fp = fopen("/usr/share/dict/words", "r");
qb_util_stopwatch_start(sw);
- while (fgets(word, sizeof(word), fp)) {
+ count2 = 0;
+ while (fgets(word, sizeof(word), fp) && count2 < 100000) {
word[strlen(word) - 1] = '\0';
value = qb_map_get(m, word);
ck_assert_str_eq(word, value);
+ count2++;
}
qb_util_stopwatch_stop(sw);
fclose(fp);
@@ -352,10 +398,12 @@ test_map_load(qb_map_t *m, const char* test_name)
*/
fp = fopen("/usr/share/dict/words", "r");
qb_util_stopwatch_start(sw);
- while (fgets(word, sizeof(word), fp)) {
+ count2 = 0;
+ while (fgets(word, sizeof(word), fp) && count2 < 100000) {
word[strlen(word) - 1] = '\0';
res = qb_map_rm(m, word);
ck_assert_int_eq(res, QB_TRUE);
+ count2++;
}
ck_assert_int_eq(qb_map_count_get(m), 0);
qb_util_stopwatch_stop(sw);
@@ -388,17 +436,17 @@ END_TEST
START_TEST(test_skiplist_remove)
{
- qb_map_t *tree = qb_skiplist_create(my_key_destroy,
- my_value_destroy);
- test_map_remove(tree);
+ qb_map_t *m = qb_skiplist_create(my_key_destroy,
+ my_value_destroy);
+ test_map_remove(m);
}
END_TEST
START_TEST(test_hashtable_remove)
{
- qb_map_t *tree = qb_hashtable_create(my_key_destroy,
- my_value_destroy, 256);
- test_map_remove(tree);
+ qb_map_t *m = qb_hashtable_create(my_key_destroy,
+ my_value_destroy, 256);
+ test_map_remove(m);
}
END_TEST
@@ -410,13 +458,19 @@ START_TEST(test_skiplist_traverse)
m = qb_skiplist_create(NULL, NULL);
test_map_traverse_unordered(m);
+
+ m = qb_skiplist_create(NULL, NULL);
+ test_map_iter_safety(m, QB_TRUE);
}
END_TEST
START_TEST(test_hashtable_traverse)
{
- qb_map_t *m = qb_hashtable_create(NULL, NULL, 256);
+ qb_map_t *m;
+ m = qb_hashtable_create(NULL, NULL, 256);
test_map_traverse_unordered(m);
+ m = qb_hashtable_create(NULL, NULL, 256);
+ test_map_iter_safety(m, QB_FALSE);
}
END_TEST
@@ -485,12 +539,12 @@ map_suite(void)
tc = tcase_create("skiplist_load");
tcase_add_test(tc, test_skiplist_load);
- tcase_set_timeout(tc, 10);
+ 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, 20);
+ tcase_set_timeout(tc, 30);
suite_add_tcase(s, tc);
return s;
--
1.7.6