Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
docs/Makefile.am | 3 +-
docs/mainpage.h | 7 +
include/qb/Makefile.am | 2 +-
include/qb/qbmap.h | 138 ++++++++++++
lib/Makefile.am | 4 +-
lib/hashtable.c | 277 ++++++++++++++++++++++++
lib/map.c | 60 ++++++
lib/map_int.h | 51 +++++
lib/skiplist.c | 372 +++++++++++++++++++++++++++++++++
tests/Makefile.am | 10 +-
tests/check_map.c | 545 ++++++++++++++++++++++++++++++++++++++++++++++++
11 files changed, 1463 insertions(+), 6 deletions(-)
create mode 100644 include/qb/qbmap.h
create mode 100644 lib/hashtable.c
create mode 100644 lib/map.c
create mode 100644 lib/map_int.h
create mode 100644 lib/skiplist.c
create mode 100644 tests/check_map.c
diff --git a/docs/Makefile.am b/docs/Makefile.am
index ec769c5..257ddd4 100644
--- a/docs/Makefile.am
+++ b/docs/Makefile.am
@@ -26,7 +26,8 @@ inc_dir = $(top_srcdir)/include/qb
dependant_headers = $(wildcard $(inc_dir)/qb*.h)
dist_man_MANS = man3/qbipcc.h.3 man3/qbipcs.h.3 man3/qbatomic.h.3 \
man3/qbhdb.h.3 man3/qbipc_common.h.3 man3/qblist.h.3 \
- man3/qbloop.h.3 man3/qbutil.h.3 man3/qbarray.h.3 man3/qblog.h.3
+ man3/qbloop.h.3 man3/qbutil.h.3 man3/qbarray.h.3 \
+ man3/qblog.h.3 man3/qbmap.h.3
$(dist_man_MANS): man.dox $(dependant_headers)
diff --git a/docs/mainpage.h b/docs/mainpage.h
index 337b8f4..761b383 100644
--- a/docs/mainpage.h
+++ b/docs/mainpage.h
@@ -15,6 +15,7 @@
* - @subpage qb_list_overview
* - @subpage qb_atomic_overview
* - @subpage qb_array_overview
+ * - @subpage qb_map_overview
* - @subpage qb_hdb_overview
* - @subpage qb_rb_overview
* - @subpage qb_loop_overview
@@ -41,6 +42,12 @@
* @see qbarray.h
*/
+/**
+ * @page qb_map_overview Map
+ * @copydoc qbmap.h
+ * @see qbmap.h
+ */
+
/**
* @page qb_hdb_overview Handle Database
* @copydoc qbhdb.h
diff --git a/include/qb/Makefile.am b/include/qb/Makefile.am
index 89fd769..41d7e23 100644
--- a/include/qb/Makefile.am
+++ b/include/qb/Makefile.am
@@ -23,4 +23,4 @@ instdir = $(includedir)/qb/
inst_HEADERS = qbhdb.h qblist.h qbdefs.h qbatomic.h \
qbloop.h qbrb.h qbutil.h qbarray.h \
qbipcc.h qbipcs.h qbipc_common.h qblog.h \
- qbconfig.h
+ qbconfig.h qbmap.h
diff --git a/include/qb/qbmap.h b/include/qb/qbmap.h
new file mode 100644
index 0000000..4309645
--- /dev/null
+++ b/include/qb/qbmap.h
@@ -0,0 +1,138 @@
+/*
+ * Copyright (C) 2011 Red Hat, Inc.
+ *
+ * Author: Angus Salkeld <asalkeld(a)redhat.com>
+ *
+ * This file is part of libqb.
+ *
+ * libqb is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * libqb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with libqb. If not, see <
http://www.gnu.org/licenses/>.
+ */
+#ifndef QB_MAP_H_DEFINED
+#define QB_MAP_H_DEFINED
+
+#include <stdint.h>
+
+/* *INDENT-OFF* */
+#ifdef __cplusplus
+extern "C" {
+#endif
+/* *INDENT-ON* */
+
+/**
+ * @file qbmap.h
+ * This provides a map interface to either a hashtable or a skiplist.
+ */
+
+/**
+ * This is an opaque data type representing an instance of a map.
+ */
+typedef struct qb_map qb_map_t;
+
+typedef void (*qb_destroy_notifier_func)(void* data);
+typedef int32_t (*qb_compare_func)(const void* a, const void* b, void* data);
+typedef int32_t (*qb_transverse_func)(void* key, void* value, void* data);
+
+typedef uint32_t (*qb_hash_func)(const void* key, uint32_t order);
+
+uint32_t qb_hash_string(const void *key, uint32_t order);
+uint32_t qb_hash_char(const void *key, uint32_t order);
+uint32_t qb_hash_pointer(const void *key, uint32_t order);
+
+/**
+ * Create an unsorted map based on a hashtable.
+ *
+ * @param key_compare_func a user function to compare keys
+ * @param key_compare_data a user pointer to be passed into the compare function
+ * @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
+ * @param hash_fn hash function
+ *
+ * @see qb_hash_pointer, qb_hash_char, qb_hash_string
+ *
+ * @return the map instance
+ */
+qb_map_t* qb_hashtable_create(qb_compare_func key_compare_func,
+ void *key_compare_data,
+ qb_destroy_notifier_func key_destroy_func,
+ qb_destroy_notifier_func value_destroy_func,
+ size_t max_size,
+ qb_hash_func hash_fn);
+
+/**
+ * Create a sorted map using a skiplist.
+ *
+ * @param key_compare_func a user function to compare keys
+ * @param key_compare_data a user pointer to be passed into the compare function
+ * @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_compare_func key_compare_func,
+ void* key_compare_data,
+ qb_destroy_notifier_func key_destroy_func,
+ qb_destroy_notifier_func value_destroy_func);
+
+/**
+ * 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 void* key, const void* value);
+
+/**
+ * Gets the value corresponding to the given key.
+ */
+void* qb_map_get(qb_map_t *map, const void* 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 void* key);
+
+/**
+ * Get the number of items in the map.
+ */
+size_t qb_map_count_get(qb_map_t *map);
+
+/**
+ * Calls the given function for each of the key/value pairs in the 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);
+
+/**
+ * Destroy the map, removes all the items from the map.
+ */
+void qb_map_destroy(qb_map_t *map);
+
+/* *INDENT-OFF* */
+#ifdef __cplusplus
+}
+#endif
+/* *INDENT-ON* */
+
+#endif /* QB_MAP_H_DEFINED */
diff --git a/lib/Makefile.am b/lib/Makefile.am
index b6ea3f1..a778f3c 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -42,7 +42,9 @@ source_to_lint = util.c hdb.c ringbuffer.c ringbuffer_helper.c array.c
\
loop.c loop_poll.c loop_job.c \
ipcc.c ipcs.c ipc_posix_mq.c ipc_sysv_mq.c ipc_shm.c ipc_us.c \
log.c log_thread.c log_blackbox.c log_file.c \
- log_syslog.c log_dcs.c log_format.c
+ log_syslog.c log_dcs.c log_format.c \
+ map.c skiplist.c hashtable.c
+
libqb_la_SOURCES = $(source_to_lint)
if USE_TIMERFD
else
diff --git a/lib/hashtable.c b/lib/hashtable.c
new file mode 100644
index 0000000..7fdf6b0
--- /dev/null
+++ b/lib/hashtable.c
@@ -0,0 +1,277 @@
+/*
+ * Copyright (C) 2010 Red Hat, Inc.
+ *
+ * Author: Steven Dake <sdake(a)redhat.com>
+ *
+ * This file is part of libqb.
+ *
+ * libqb is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * libqb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with libqb. If not, see <
http://www.gnu.org/licenses/>.
+ */
+#include "os_base.h"
+
+#include <qb/qbmap.h>
+#include "util_int.h"
+#include "map_int.h"
+#include <qb/qblist.h>
+
+#define FNV_32_PRIME ((uint32_t)0x01000193)
+
+struct hash_node {
+ struct qb_list_head list;
+ void *value;
+ void *key;
+};
+
+struct hash_bucket {
+ struct qb_list_head list_head;
+};
+
+struct hash_table {
+ struct qb_map map;
+ size_t count;
+ uint32_t order;
+ qb_hash_func hash_fn;
+ uint32_t hash_buckets_len;
+ struct hash_bucket hash_buckets[0];
+};
+
+static uint32_t
+hash_fnv(const void *value, uint32_t valuelen, uint32_t order)
+{
+ uint8_t *cd = (uint8_t *) value;
+ uint8_t *ed = (uint8_t *) value + valuelen;
+ uint32_t hash_result = 0x811c9dc5;
+ int32_t res;
+
+ while (cd < ed) {
+ hash_result ^= *cd;
+ hash_result *= FNV_32_PRIME;
+ cd++;
+ }
+ res = ((hash_result >> order) ^ hash_result) & ((1 << order) - 1);
+ return (res);
+}
+
+uint32_t
+qb_hash_string(const void *key, uint32_t order)
+{
+ char* str = (char*)key;
+ return hash_fnv(key, strlen(str), order);
+}
+
+uint32_t
+qb_hash_char(const void *key, uint32_t order)
+{
+ return hash_fnv(key, sizeof(char), order);
+}
+
+uint32_t
+qb_hash_pointer(const void *key, uint32_t order)
+{
+ return hash_fnv(key, sizeof(uint32_t), order);
+}
+
+static void*
+hashtable_get(struct qb_map *map, const void* 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 = hash_table->hash_fn(key, hash_table->order);
+
+ for (list = hash_table->hash_buckets[hash_entry].list_head.next;
+ list != &hash_table->hash_buckets[hash_entry].list_head;
+ list = list->next) {
+
+ hash_node = qb_list_entry(list, struct hash_node, list);
+ if (map->key_compare_func(hash_node->key, key,
+ map->key_compare_data) == 0) {
+ return hash_node->value;
+ }
+ }
+
+ return NULL;
+}
+
+static int32_t
+hashtable_rm_with_hash(struct qb_map *map, const void* key,
+ uint32_t hash_entry)
+{
+ struct hash_table *hash_table = (struct hash_table *)map;
+ struct qb_list_head *list;
+ struct hash_node *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) {
+
+ hash_node = qb_list_entry(list, struct hash_node, list);
+ if (map->key_compare_func(hash_node->key, key,
+ map->key_compare_data) == 0) {
+
+ if (map->key_destroy_func) {
+ map->key_destroy_func(hash_node->key);
+ }
+ if (map->value_destroy_func) {
+ map->value_destroy_func(hash_node->value);
+ }
+ qb_list_del(&hash_node->list);
+ free(hash_node);
+ hash_table->count--;
+ return QB_TRUE;
+ }
+ }
+
+ return QB_FALSE;
+}
+
+static int32_t
+hashtable_rm(struct qb_map *map, const void* key)
+{
+ struct hash_table *hash_table = (struct hash_table *)map;
+ uint32_t hash_entry;
+
+ hash_entry = hash_table->hash_fn(key, hash_table->order);
+ return hashtable_rm_with_hash(map, key, hash_entry);
+}
+
+static void
+hashtable_put(struct qb_map *map, const void* key, const void* value)
+{
+ struct hash_table *hash_table = (struct hash_table *)map;
+ uint32_t hash_entry;
+ struct hash_node *hash_node;
+
+ hash_entry = hash_table->hash_fn(key, hash_table->order);
+ hashtable_rm_with_hash(map, key, hash_entry);
+ hash_node = malloc(sizeof(struct hash_node));
+ if (hash_node == NULL) {
+ errno = ENOMEM;
+ return;
+ }
+
+ hash_table->count++;
+ hash_node->key = (void*)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);
+}
+
+static size_t
+hashtable_count_get(struct qb_map *map)
+{
+ struct hash_table *hash_table = (struct hash_table *)map;
+ return hash_table->count;
+}
+
+static void
+hashtable_foreach(struct qb_map *map, qb_transverse_func func, void* user_data)
+{
+ struct hash_table *hash_table = (struct hash_table *)map;
+ 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;
+ 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;
+ }
+ }
+ }
+}
+
+static void
+hashtable_destroy(struct qb_map *map)
+{
+ struct hash_table *hash_table = (struct hash_table *)map;
+
+ free(hash_table);
+}
+
+qb_map_t *
+qb_hashtable_create(qb_compare_func key_compare_func,
+ void *key_compare_data,
+ qb_destroy_notifier_func key_destroy_func,
+ qb_destroy_notifier_func value_destroy_func,
+ size_t max_size, qb_hash_func hash_fn)
+{
+ int32_t i;
+ int32_t order;
+ int32_t n = max_size;
+ uint64_t size;
+ struct hash_table *ht;
+
+ for (i = 0; n; i++) {
+ n >>= 1;
+ }
+ order = QB_MAX(i, 3);
+
+ size = sizeof(struct hash_table) +
+ (sizeof(struct hash_bucket) * (1 << order));
+
+ ht = calloc(1, size);
+
+ ht->map.key_compare_func = key_compare_func;
+ ht->map.key_compare_data = key_compare_data;
+ ht->map.key_destroy_func = key_destroy_func;
+ ht->map.value_destroy_func = value_destroy_func;
+
+ ht->map.put = hashtable_put;
+ ht->map.get = hashtable_get;
+ ht->map.rm = hashtable_rm;
+ ht->map.count_get = hashtable_count_get;
+ ht->map.foreach = hashtable_foreach;
+ ht->map.destroy = hashtable_destroy;
+
+ ht->count = 0;
+ ht->order = order;
+
+ if (hash_fn == NULL) {
+ ht->hash_fn = qb_hash_pointer;
+ } else {
+ ht->hash_fn = hash_fn;
+ }
+
+ ht->hash_buckets_len = 1 << order;
+ for (i = 0; i < ht->hash_buckets_len; i++) {
+ qb_list_init(&ht->hash_buckets[i].list_head);
+ }
+ 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
new file mode 100644
index 0000000..5487051
--- /dev/null
+++ b/lib/map.c
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2011 Red Hat, Inc.
+ *
+ * Author: Angus Salkeld <asalkeld(a)redhat.com>
+ *
+ * This file is part of libqb.
+ *
+ * libqb is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * libqb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with libqb. If not, see <
http://www.gnu.org/licenses/>.
+ */
+
+#include "os_base.h"
+#include <qb/qbmap.h>
+#include "map_int.h"
+
+void
+qb_map_put(struct qb_map *map, const void *key, const void *value)
+{
+ map->put(map, key, value);
+}
+
+void *
+qb_map_get(struct qb_map *map, const void *key)
+{
+ return map->get(map, key);
+}
+
+int32_t
+qb_map_rm(struct qb_map *map, const void *key)
+{
+ return map->rm(map, key);
+}
+
+size_t
+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)
+{
+ map->foreach(map, func, user_data);
+}
+
+void
+qb_map_destroy(struct qb_map *map)
+{
+ map->destroy(map);
+}
diff --git a/lib/map_int.h b/lib/map_int.h
new file mode 100644
index 0000000..f97ff4e
--- /dev/null
+++ b/lib/map_int.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2011 Red Hat, Inc.
+ *
+ * Author: Angus Salkeld <asalkeld(a)redhat.com>
+ *
+ * This file is part of libqb.
+ *
+ * libqb is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * libqb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with libqb. If not, see <
http://www.gnu.org/licenses/>.
+ */
+#ifndef _QB_MAP_INT_H_
+#define _QB_MAP_INT_H_
+
+struct qb_map;
+
+typedef void (*qb_map_put_func)(struct qb_map *map, const void* key, const void* value);
+typedef void* (*qb_map_get_func)(struct qb_map *map, const void* key);
+typedef int32_t (*qb_map_rm_func)(struct qb_map *map, const void* 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);
+
+struct qb_map {
+ /* user provided
+ */
+ qb_compare_func key_compare_func;
+ void* key_compare_data;
+ qb_destroy_notifier_func key_destroy_func;
+ qb_destroy_notifier_func value_destroy_func;
+
+ /* data type provided
+ */
+ qb_map_put_func put;
+ 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;
+};
+
+#endif /* _QB_MAP_INT_H_ */
diff --git a/lib/skiplist.c b/lib/skiplist.c
new file mode 100644
index 0000000..688ba1d
--- /dev/null
+++ b/lib/skiplist.c
@@ -0,0 +1,372 @@
+/*
+ * Copyright (C) 2011 Red Hat, Inc.
+ *
+ * Author: Angus Salkeld <asalkeld(a)redhat.com>
+ *
+ * This file is part of libqb.
+ *
+ * libqb is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * libqb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with libqb. If not, see <
http://www.gnu.org/licenses/>.
+ */
+#include <os_base.h>
+#include <assert.h>
+
+#include "qbdefs.h"
+#include "qbmap.h"
+#include "map_int.h"
+
+#define SKIPLIST_LEVEL_MAX 8
+#define SKIPLIST_LEVEL_MIN 0
+/* The amount of possible levels */
+#define SKIPLIST_LEVEL_COUNT (SKIPLIST_LEVEL_MAX - SKIPLIST_LEVEL_MIN + 1)
+
+struct skiplist_node {
+ void *key;
+ void *value;
+ int8_t level;
+
+ /* An array of @level + 1 node pointers */
+ struct skiplist_node **forward;
+};
+
+struct skiplist {
+ struct qb_map map;
+
+ size_t length;
+ int8_t level;
+ struct skiplist_node *header;
+};
+
+/* An array of nodes that need to be updated after an insert or delete operation
+ */
+typedef struct skiplist_node *skiplist_update_t[SKIPLIST_LEVEL_COUNT];
+
+static int32_t skiplist_rm(struct qb_map *list, const void *key);
+
+static int8_t
+skiplist_level_generate(void)
+{
+ // This constant is found by 1 / P, where P = 0.25.
+ enum { P_INVERSE = 4 };
+
+ /* The original algorithm's random number is in the range [0, 1), so
+ * max M = 1. Its ceiling C = M * P = 1 * P = P.
+ *
+ * Our random number is in the range [0, UINT16_MAX], so M = UINT16_MAX. Therefore,
+ * C = UINT16_MAX * P = UINT16_MAX / P_INVERSE.
+ */
+ enum { P_CEIL = UINT16_MAX / P_INVERSE };
+ int8_t level = SKIPLIST_LEVEL_MIN;
+
+ while ((uint16_t) (rand()) < P_CEIL)
+ level += 1;
+
+ if (level < SKIPLIST_LEVEL_MAX)
+ return level;
+
+ return SKIPLIST_LEVEL_MAX;
+}
+
+static inline struct skiplist_node *
+skiplist_node_next(const struct skiplist_node *node)
+{
+ return node->forward[SKIPLIST_LEVEL_MIN];
+}
+
+/*
+ * 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 void* key, const void *value)
+{
+ struct skiplist_node *new_node = (struct skiplist_node *)
+ (malloc(sizeof(struct skiplist_node)));
+
+ if (!new_node)
+ return NULL;
+
+ new_node->value = (void*)value;
+ new_node->key = (void*)key;
+ new_node->level = level;
+
+ /* A level 0 node still needs to hold 1 forward pointer, etc. */
+ new_node->forward = (struct skiplist_node **)
+ (calloc(level + 1, sizeof(struct skiplist_node *)));
+
+ if (new_node->forward)
+ return new_node;
+
+ free(new_node);
+
+ return NULL;
+}
+
+static inline struct skiplist_node *
+skiplist_header_node_new(void)
+{
+ return skiplist_node_new(SKIPLIST_LEVEL_MAX, NULL, NULL);
+}
+
+static void
+skiplist_node_destroy(struct skiplist_node *node, struct skiplist *list)
+{
+ if (list->map.key_destroy_func && node != list->header) {
+ list->map.key_destroy_func(node->key);
+ }
+ if (list->map.value_destroy_func && node != list->header) {
+ list->map.value_destroy_func(node->value);
+ }
+ free(node->forward);
+ free(node);
+}
+
+static void
+skiplist_destroy(struct qb_map *map)
+{
+ struct skiplist *list = (struct skiplist *)map;
+ struct skiplist_node *cur_node = list->header;
+ struct skiplist_node *fwd_node;
+
+ do {
+ fwd_node = skiplist_node_next(cur_node);
+ skiplist_node_destroy(cur_node, list);
+ } while ((cur_node = fwd_node));
+ 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 = list->map.key_compare_func(fwd_node->key, search,
list->map.key_compare_data);
+ 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 void *key, const void *value)
+{
+ struct skiplist *list = (struct skiplist *)map;
+ struct skiplist_node *cur_node = list->header;
+ struct skiplist_node *new_node;
+ int8_t level = list->level;
+ skiplist_update_t update;
+ int8_t update_level;
+ int8_t new_node_level;
+
+ 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(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;
+ return;
+
+ case OP_GOTO_NEXT_NODE:
+ cur_node = fwd_node;
+ break;
+ case OP_GOTO_NEXT_LEVEL:
+ level -= 1;
+ }
+
+ update[update_level] = cur_node;
+ }
+
+ new_node_level = skiplist_level_generate();
+
+ if (new_node_level > list->level) {
+ for (level = list->level + 1; level <= new_node_level;
+ level += 1)
+ update[level] = list->header;
+
+ list->level = new_node_level;
+ }
+
+ new_node = skiplist_node_new(new_node_level, key, value);
+
+ assert(new_node != NULL);
+
+ /* Drop @new_node into @list. */
+ for (level = SKIPLIST_LEVEL_MIN; level <= new_node_level; level += 1) {
+ new_node->forward[level] = update[level]->forward[level];
+ update[level]->forward[level] = new_node;
+ }
+
+ list->length += 1;
+}
+
+static int32_t
+skiplist_rm(struct qb_map *map, const void *key)
+{
+ struct skiplist *list = (struct skiplist *)map;
+ struct skiplist_node *found_node;
+ struct skiplist_node *cur_node = list->header;
+ int8_t level = list->level;
+ int8_t update_level;
+ skiplist_update_t update;
+
+ 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_GOTO_NEXT_NODE:
+ cur_node = fwd_node;
+ break;
+ case OP_GOTO_NEXT_LEVEL:
+ default:
+ level -= 1;
+ break;
+ }
+
+ update[update_level] = cur_node;
+ }
+
+ /* The immediate forward node should be the matching node... */
+ found_node = skiplist_node_next(cur_node);
+
+ /* ...unless we're at the end of the list or the value doesn't exist. */
+ if (!found_node
+ || list->map.key_compare_func(found_node->key, key,
list->map.key_compare_data) != 0) {
+ return QB_FALSE;
+ }
+
+ /* Splice found_node out of list. */
+ for (level = SKIPLIST_LEVEL_MIN; level <= list->level; level += 1)
+ if (update[level]->forward[level] == found_node)
+ update[level]->forward[level] = found_node->forward[level];
+
+ skiplist_node_destroy(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
+ * highest level.
+ */
+ for (level = list->level; level >= SKIPLIST_LEVEL_MIN; level -= 1) {
+ if (list->header->forward[level])
+ break;
+
+ list->level -= 1;
+ }
+
+ list->length -= 1;
+
+ return QB_TRUE;
+}
+
+static void *
+skiplist_get(struct qb_map *map, const void *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 -= 1;
+ }
+ }
+
+ return NULL;
+}
+
+static void
+qb_skiplist_foreach(struct qb_map * map, qb_transverse_func func,
+ void *user_data)
+{
+ 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;
+ }
+}
+
+static size_t
+skiplist_count_get(struct qb_map * map)
+{
+ struct skiplist *list = (struct skiplist *)map;
+ return list->length;
+}
+
+qb_map_t *
+qb_skiplist_create(qb_compare_func key_compare_func,
+ void *key_compare_data,
+ qb_destroy_notifier_func key_destroy_func,
+ qb_destroy_notifier_func value_destroy_func)
+{
+ struct skiplist *sl = calloc(1, sizeof(struct skiplist));
+
+ srand(time(NULL));
+
+ sl->map.key_compare_func = key_compare_func;
+ sl->map.key_compare_data = key_compare_data;
+ sl->map.key_destroy_func = key_destroy_func;
+ sl->map.value_destroy_func = value_destroy_func;
+
+ sl->map.put = skiplist_put;
+ 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.destroy = skiplist_destroy;
+
+ sl->level = SKIPLIST_LEVEL_MIN;
+ sl->length = 0;
+ sl->header = skiplist_header_node_new();
+
+ return (qb_map_t *) sl;
+}
+
diff --git a/tests/Makefile.am b/tests/Makefile.am
index dff3410..a89bf26 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -76,17 +76,21 @@ bench_log_LDADD = -lrt $(top_builddir)/lib/libqb.la
if HAVE_CHECK
EXTRA_DIST += resources.test
-TESTS = array.test rb.test log.test loop.test ipc.test resources.test
+TESTS = array.test map.test rb.test log.test loop.test ipc.test resources.test map.test
-resources.log: array.log rb.log log.log loop.log ipc.log
+resources.log: rb.log log.log ipc.log
-check_PROGRAMS = array.test rb.test log.test loop.test ipc.test
+check_PROGRAMS = array.test map.test rb.test log.test loop.test ipc.test
check_SCRIPTS = resources.test
array_test_SOURCES = check_array.c $(top_builddir)/include/qb/qbarray.h
array_test_CFLAGS = @CHECK_CFLAGS@ -I$(top_srcdir)/include
array_test_LDADD = $(top_builddir)/lib/libqb.la -lrt @CHECK_LIBS@
+map_test_SOURCES = check_map.c $(top_builddir)/include/qb/qbmap.h
+map_test_CFLAGS = @CHECK_CFLAGS@ -I$(top_srcdir)/include
+map_test_LDADD = $(top_builddir)/lib/libqb.la -lrt @CHECK_LIBS@
+
rb_test_SOURCES = check_rb.c $(top_builddir)/include/qb/qbrb.h
rb_test_CFLAGS = @CHECK_CFLAGS@ -I$(top_srcdir)/include
rb_test_LDADD = $(top_builddir)/lib/libqb.la -lrt @CHECK_LIBS@
diff --git a/tests/check_map.c b/tests/check_map.c
new file mode 100644
index 0000000..23a0d86
--- /dev/null
+++ b/tests/check_map.c
@@ -0,0 +1,545 @@
+/*
+ * Copyright (c) 2011 Red Hat, Inc.
+ *
+ * All rights reserved.
+ *
+ * Author: Angus Salkeld <asalkeld(a)redhat.com>
+ *
+ * This file is part of libqb.
+ *
+ * libqb is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation, either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * libqb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with libqb. If not, see <
http://www.gnu.org/licenses/>.
+ */
+#include "os_base.h"
+#include <check.h>
+#include "qbdefs.h"
+#include "qblog.h"
+#include "qbmap.h"
+
+char chars[] =
+ "0123456789" "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
+
+char chars2[] = "0123456789" "abcdefghijklmnopqrstuvwxyz";
+
+static void *destroyed_key = NULL;
+static void *destroyed_value = NULL;
+static int global_data = 123;
+
+static int32_t
+my_char_compare(const void *a, const void *b, void* data)
+{
+ const char *cha = a;
+ const char *chb = b;
+
+ return *cha - *chb;
+}
+
+static int32_t
+my_str_compare(const void *a, const void *b, void* data)
+{
+ const char *cha = a;
+ const char *chb = b;
+
+ return strcmp(cha, chb);
+}
+
+static void
+test_map_simple(qb_map_t *m)
+{
+ qb_map_put(m, "k1", "one");
+ qb_map_put(m, "k2", "two");
+ qb_map_put(m, "k3", "three");
+ ck_assert_int_eq(qb_map_count_get(m), 3);
+ qb_map_put(m, "k4", "four");
+
+ ck_assert_int_eq(qb_map_count_get(m), 4);
+
+ ck_assert_str_eq(qb_map_get(m, "k3"), "three");
+ ck_assert_str_eq(qb_map_get(m, "k1"), "one");
+ ck_assert_str_eq(qb_map_get(m, "k4"), "four");
+
+ qb_map_rm(m, "k2");
+ ck_assert_int_eq(qb_map_count_get(m), 3);
+ qb_map_put(m, "9k", "nine");
+
+ qb_map_put(m, "k3", "not_three");
+ ck_assert_str_eq(qb_map_get(m, "k3"), "not_three");
+ ck_assert_int_eq(qb_map_count_get(m), 4);
+
+ qb_map_destroy(m);
+}
+
+static int32_t
+my_compare_with_data(const void *a, const void *b, void *user_data)
+{
+ const char *cha = a;
+ const char *chb = b;
+ int * dp = (int*)user_data;
+
+ /* just check that we got the right data */
+ ck_assert_int_eq(*dp, 123);
+
+ return *cha - *chb;
+}
+
+static int32_t
+my_traverse(void *key, void *value, void *data)
+{
+ char *ch = key;
+ ck_assert((*ch) > 0);
+ return QB_FALSE;
+}
+
+static int32_t
+check_order(void *key, void *value, void *data)
+{
+ char **p = data;
+ char *ch = key;
+
+ ck_assert(**p == *ch);
+
+ (*p)++;
+
+ return QB_FALSE;
+}
+
+static void
+test_map_search(qb_map_t* m)
+{
+ int32_t i;
+ int32_t removed;
+ char c;
+ 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), strlen(chars));
+
+ p = chars;
+ qb_map_foreach(m, check_order, &p);
+
+ for (i = 0; i < 26; i++) {
+ removed = qb_map_rm(m, &chars[i + 10]);
+ ck_assert(removed);
+ }
+
+ c = '\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), strlen(chars2));
+
+ p = chars2;
+ qb_map_foreach(m, check_order, &p);
+
+ for (i = 25; i >= 0; i--) {
+ qb_map_put(m, &chars[i + 10], &chars[i + 10]);
+ }
+ p = chars;
+ qb_map_foreach(m, check_order, &p);
+
+ c = '0';
+ p = qb_map_get(m, &c);
+ ck_assert(p && *p == c);
+
+ c = 'A';
+ p = qb_map_get(m, &c);
+ ck_assert(p && *p == c);
+
+ c = 'a';
+ p = qb_map_get(m, &c);
+ ck_assert(p && *p == c);
+
+ c = 'z';
+ p = qb_map_get(m, &c);
+ ck_assert(p && *p == c);
+
+ c = '!';
+ p = qb_map_get(m, &c);
+ ck_assert(p == NULL);
+
+ c = '=';
+ p = qb_map_get(m, &c);
+ ck_assert(p == NULL);
+
+ c = '|';
+ p = qb_map_get(m, &c);
+ ck_assert(p == NULL);
+
+ qb_map_destroy(m);
+}
+
+static void
+my_key_destroy(void *key)
+{
+ destroyed_key = key;
+}
+
+static void
+my_value_destroy(void *value)
+{
+ destroyed_value = value;
+}
+
+static void
+test_map_remove(qb_map_t *tree)
+{
+ char a, b, c, d;
+ int32_t i;
+ int32_t removed;
+ const char *remove_ch;
+
+ for (i = 0; chars[i]; i++) {
+ qb_map_put(tree, &chars[i], &chars[i]);
+ }
+
+ a = '0';
+ qb_map_put(tree, &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);
+ ck_assert(removed);
+ ck_assert(destroyed_key == &chars[5]);
+ ck_assert(destroyed_value == &chars[5]);
+ destroyed_key = NULL;
+ destroyed_value = NULL;
+
+ d = '1';
+ qb_map_put(tree, &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);
+ ck_assert(removed);
+ ck_assert(destroyed_key == &chars[2]);
+ ck_assert(destroyed_value == &chars[2]);
+ destroyed_key = NULL;
+ destroyed_value = NULL;
+
+ remove_ch = "omkjigfedba";
+ for (i = 0; remove_ch[i]; i++) {
+ removed = qb_map_rm(tree, &remove_ch[i]);
+ ck_assert(removed);
+ }
+
+ qb_map_destroy(tree);
+}
+
+static int32_t
+traverse_func(void *key, void *value, void *data)
+{
+ char *c = value;
+ char **p = data;
+
+ **p = *c;
+ (*p)++;
+
+ return QB_FALSE;
+}
+
+static void
+test_map_traverse_ordered(qb_map_t *tree)
+{
+ int32_t i;
+ char *p, *result;
+
+ for (i = 0; chars[i]; i++) {
+ qb_map_put(tree, &chars[i], &chars[i]);
+ }
+ result = calloc(sizeof(char), strlen(chars) + 1);
+
+ p = result;
+ qb_map_foreach(tree, traverse_func, &p);
+ ck_assert_str_eq(result,
+ "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
+
+ qb_map_destroy(tree);
+}
+
+static int32_t
+traverse_and_remove_func(void *key, void *value, void *data)
+{
+ qb_map_t *m = (qb_map_t *)data;
+ qb_map_rm(m, key);
+ qb_map_put(m, (char*)key + 20, key);
+ return QB_FALSE;
+}
+
+static void
+test_map_traverse_unordered(qb_map_t *tree)
+{
+ int32_t i;
+ for (i = 0; i < 20; i++) {
+ qb_map_put(tree, &chars[i], &chars[i]);
+ }
+ qb_map_foreach(tree, traverse_and_remove_func, tree);
+}
+
+
+static int32_t
+my_counter_traverse(void *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;
+ void *value;
+ qb_util_stopwatch_t *sw;
+
+ ck_assert(m != NULL);
+ sw = qb_util_stopwatch_create();
+
+ /*
+ * Load with dictionary
+ */
+ fp = fopen("/usr/share/dict/words", "r");
+ qb_util_stopwatch_start(sw);
+ count = 0;
+ while (fgets(word, sizeof(word), fp)) {
+ word[strlen(word) - 1] = '\0';
+ 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);
+
+ ops = count / qb_util_stopwatch_sec_elapsed_get(sw);
+ qb_log(LOG_INFO, "%s %9.3f puts/sec\n", test_name, ops);
+
+ /*
+ * Verify dictionary produces correct values
+ */
+ fp = fopen("/usr/share/dict/words", "r");
+ qb_util_stopwatch_start(sw);
+ while (fgets(word, sizeof(word), fp)) {
+ word[strlen(word) - 1] = '\0';
+ value = qb_map_get(m, word);
+ ck_assert_str_eq(word, value);
+ }
+ qb_util_stopwatch_stop(sw);
+ fclose(fp);
+
+ ops = count / qb_util_stopwatch_sec_elapsed_get(sw);
+ qb_log(LOG_INFO, "%s %9.3f gets/sec\n", test_name, ops);
+
+ /*
+ * time the iteration
+ */
+ count2 = 0;
+ qb_util_stopwatch_start(sw);
+ qb_map_foreach(m, my_counter_traverse, &count2);
+ qb_util_stopwatch_stop(sw);
+ ops = count2 / qb_util_stopwatch_sec_elapsed_get(sw);
+ qb_log(LOG_INFO, "%s %9.3f iterations/sec\n", test_name, ops);
+
+ /*
+ * Delete all dictionary entries
+ */
+ fp = fopen("/usr/share/dict/words", "r");
+ qb_util_stopwatch_start(sw);
+ while (fgets(word, sizeof(word), fp)) {
+ word[strlen(word) - 1] = '\0';
+ res = qb_map_rm(m, word);
+ ck_assert_int_eq(res, QB_TRUE);
+ }
+ ck_assert_int_eq(qb_map_count_get(m), 0);
+ qb_util_stopwatch_stop(sw);
+ fclose(fp);
+
+ ops = count / qb_util_stopwatch_sec_elapsed_get(sw);
+ qb_log(LOG_INFO, "%s %9.3f deletes/sec\n", test_name, ops);
+}
+
+START_TEST(test_skiplist_simple)
+{
+ qb_map_t *m = qb_skiplist_create(my_str_compare, NULL, NULL, NULL);
+ test_map_simple(m);
+}
+END_TEST
+
+START_TEST(test_hashtable_simple)
+{
+ qb_map_t *m = qb_hashtable_create(my_str_compare, NULL, NULL, NULL,
+ 32, qb_hash_string);
+ test_map_simple(m);
+}
+END_TEST
+
+START_TEST(test_skiplist_search)
+{
+ qb_map_t *m = qb_skiplist_create(my_compare_with_data,
+ &global_data, NULL, NULL);
+ test_map_search(m);
+}
+END_TEST
+
+START_TEST(test_skiplist_remove)
+{
+ qb_map_t *tree = qb_skiplist_create(my_char_compare, NULL,
+ my_key_destroy,
+ my_value_destroy);
+ test_map_remove(tree);
+}
+END_TEST
+
+START_TEST(test_hashtable_remove)
+{
+ qb_map_t *tree = qb_hashtable_create(my_char_compare, NULL,
+ my_key_destroy,
+ my_value_destroy,
+ 256, qb_hash_char);
+ test_map_remove(tree);
+}
+END_TEST
+
+START_TEST(test_skiplist_traverse)
+{
+ qb_map_t *m;
+ m = qb_skiplist_create(my_char_compare, NULL, NULL, NULL);
+ test_map_traverse_ordered(m);
+
+ m = qb_skiplist_create(my_char_compare, NULL, NULL, NULL);
+ test_map_traverse_unordered(m);
+}
+END_TEST
+
+START_TEST(test_hashtable_traverse)
+{
+ qb_map_t *m = qb_hashtable_create(my_char_compare, NULL, NULL, NULL,
+ 256, qb_hash_char);
+ test_map_traverse_unordered(m);
+}
+END_TEST
+
+START_TEST(test_skiplist_load)
+{
+ qb_map_t *m;
+ if (access("/usr/share/dict/words", R_OK) != 0) {
+ printf("no dict/words - not testing\n");
+ return;
+ }
+ m = qb_skiplist_create(my_str_compare, NULL, NULL, NULL);
+ test_map_load(m, __func__);
+}
+END_TEST
+
+START_TEST(test_hashtable_load)
+{
+ qb_map_t *m;
+ if (access("/usr/share/dict/words", R_OK) != 0) {
+ printf("no dict/words - not testing\n");
+ return;
+ }
+ m = qb_hashtable_create(my_str_compare, NULL, NULL, NULL,
+ 100000, qb_hash_string);
+ test_map_load(m, __func__);
+}
+END_TEST
+
+static Suite *
+map_suite(void)
+{
+ TCase *tc;
+ Suite *s = suite_create("qb_map");
+
+ tc = tcase_create("skiplist_simple");
+ tcase_add_test(tc, test_skiplist_simple);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("hashtable_simple");
+ tcase_add_test(tc, test_hashtable_simple);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("skiplist_remove");
+ tcase_add_test(tc, test_skiplist_remove);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("hashtable_remove");
+ tcase_add_test(tc, test_hashtable_remove);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("skiplist_search");
+ tcase_add_test(tc, test_skiplist_search);
+ suite_add_tcase(s, tc);
+
+/*
+ * No hashtable_search as it assumes an ordered
+ * collection
+ */
+
+ tc = tcase_create("skiplist_traverse");
+ tcase_add_test(tc, test_skiplist_traverse);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("hashtable_traverse");
+ tcase_add_test(tc, test_hashtable_traverse);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("skiplist_load");
+ tcase_add_test(tc, test_skiplist_load);
+ tcase_set_timeout(tc, 10);
+ suite_add_tcase(s, tc);
+
+ tc = tcase_create("hashtable_load");
+ tcase_add_test(tc, test_hashtable_load);
+ tcase_set_timeout(tc, 20);
+ suite_add_tcase(s, tc);
+
+ return s;
+}
+
+int32_t
+main(void)
+{
+ int32_t number_failed;
+
+ Suite *s = map_suite();
+ SRunner *sr = srunner_create(s);
+
+ qb_log_init("check", LOG_USER, LOG_EMERG);
+ qb_log_ctl(QB_LOG_SYSLOG, QB_LOG_CONF_ENABLED, QB_FALSE);
+ qb_log_filter_ctl(QB_LOG_STDERR, QB_LOG_FILTER_ADD,
+ QB_LOG_FILTER_FILE, "*", LOG_INFO);
+ qb_log_format_set(QB_LOG_STDERR, "%f:%l %p %b");
+ qb_log_ctl(QB_LOG_STDERR, QB_LOG_CONF_ENABLED, QB_TRUE);
+
+ srunner_run_all(sr, CK_VERBOSE);
+ number_failed = srunner_ntests_failed(sr);
+ srunner_free(sr);
+ return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
--
1.7.6