[PATCH 1/3] docs: add utils to the mainpage

[Angus Salkeld]

Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt;
---
 docs/mainpage.h |    8 +++++++-
 1 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/docs/mainpage.h b/docs/mainpage.h
index 05754d8..337b8f4 100644
--- a/docs/mainpage.h
+++ b/docs/mainpage.h
@@ -20,6 +20,7 @@
  * - @subpage qb_loop_overview
  * - @subpage qb_log_overview
  * - @subpage qb_ipc_overview
+ * - @subpage qb_util_overview
  */
 
 /**
@@ -96,9 +97,14 @@
  *
  */
 
-
 /**
  * @page qb_atomic_overview Atomic operations
  * @copydoc qbatomic.h
  * @see qbatomic.h
  */
+
+/**
+ * @page qb_util_overview Common Utilities
+ * @copydoc qbutil.h
+ * @see qbutil.h
+ */
-- 
1.7.6

[PATCH 2/3] Add a stop watch

[Angus Salkeld]

Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt;
---
 include/qb/qbutil.h |   37 ++++++++++++++++++++++++++++++++++++
 lib/util.c          |   52 +++++++++++++++++++++++++++++++++++++++++++++++++++
 tests/bench-log.c   |   48 ++++++++++++++++------------------------------
 tests/bmc.c         |   39 +++++++------------------------------
 4 files changed, 114 insertions(+), 62 deletions(-)

diff --git a/include/qb/qbutil.h b/include/qb/qbutil.h
index 0f3ef19..7757d98 100644
--- a/include/qb/qbutil.h
+++ b/include/qb/qbutil.h
@@ -125,6 +125,43 @@ void qb_util_timespec_from_epoch_get(struct timespec *ts);
  */
 char *qb_strerror_r(int errnum, char *buf, size_t buflen);
 
+
+typedef struct qb_util_stopwatch qb_util_stopwatch_t;
+
+/**
+ * Create a Stop Watch (to time operations)
+ */
+qb_util_stopwatch_t * qb_util_stopwatch_create(void);
+
+/**
+ * Free the stop watch
+ */
+void qb_util_stopwatch_free(qb_util_stopwatch_t *sw);
+
+/**
+ * Start the stop watch
+ */
+void qb_util_stopwatch_start(qb_util_stopwatch_t *sw);
+
+/**
+ * Stop the stop watch
+ */
+void qb_util_stopwatch_stop(qb_util_stopwatch_t *sw);
+
+/**
+ * Get the elapsed time in micro seconds.
+ *
+ * (it must have been started and stopped).
+ */
+uint64_t qb_util_stopwatch_us_elapsed_get(qb_util_stopwatch_t *sw);
+
+/**
+ * Get the elapsed time in seconds.
+ *
+ * (it must have been started and stopped).
+ */
+float qb_util_stopwatch_sec_elapsed_get(qb_util_stopwatch_t *sw);
+
 /* *INDENT-OFF* */
 #ifdef __cplusplus
 }
diff --git a/lib/util.c b/lib/util.c
index 48d5e9a..c55adab 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -222,6 +222,58 @@ qb_util_nano_from_epoch_get(void)
 }
 #endif
 
+struct qb_util_stopwatch {
+	uint64_t started;
+	uint64_t stopped;
+};
+
+qb_util_stopwatch_t*
+qb_util_stopwatch_create(void)
+{
+	struct qb_util_stopwatch *sw;
+	sw = (struct qb_util_stopwatch *)calloc(1, sizeof(struct qb_util_stopwatch));
+	return sw;
+}
+
+void
+qb_util_stopwatch_free(qb_util_stopwatch_t *sw)
+{
+	free(sw);
+}
+
+void
+qb_util_stopwatch_start(qb_util_stopwatch_t *sw)
+{
+	sw->started = qb_util_nano_current_get();
+	sw->stopped = 0;
+}
+
+void
+qb_util_stopwatch_stop(qb_util_stopwatch_t *sw)
+{
+	sw->stopped = qb_util_nano_current_get();
+}
+
+uint64_t
+qb_util_stopwatch_us_elapsed_get(qb_util_stopwatch_t *sw)
+{
+	if (sw->stopped == 0 || sw->started == 0) {
+		return 0;
+	}
+	return ((sw->stopped - sw->started) / QB_TIME_NS_IN_USEC);
+}
+
+float
+qb_util_stopwatch_sec_elapsed_get(qb_util_stopwatch_t *sw)
+{
+	uint64_t e6;
+	if (sw->stopped == 0 || sw->started == 0) {
+		return 0;
+	}
+	e6 = qb_util_stopwatch_us_elapsed_get(sw);
+	return ((float)e6 / (float)QB_TIME_US_IN_SEC);
+}
+
 static int32_t
 open_mmap_file(char *path, uint32_t file_flags)
 {
diff --git a/tests/bench-log.c b/tests/bench-log.c
index 7bb7607..236ec18 100644
--- a/tests/bench-log.c
+++ b/tests/bench-log.c
@@ -21,48 +21,34 @@
 #include "os_base.h"
 
 #include <qb/qbdefs.h>
+#include <qb/qbutil.h>
 #include <qb/qblog.h>
 
 #define ITERATIONS 50000
+static qb_util_stopwatch_t *sw;
 
 extern void log_dict_words(void);
 
-static struct timeval tv1, tv2, tv_elapsed;
-
-#ifndef timersub
-#define timersub(a, b, result)					\
-do {								\
-	(result)->tv_sec = (a)->tv_sec - (b)->tv_sec;		\
-	(result)->tv_usec = (a)->tv_usec - (b)->tv_usec;	\
-	if ((result)->tv_usec < 0) {				\
-		--(result)->tv_sec;				\
-		(result)->tv_usec += 1000000;			\
-	}							\
-} while (0)
-#endif
-
-static void bm_start (void)
-{
-        gettimeofday (&tv1, NULL);
-}
-static void bm_finish (const char *operation)
+static void
+bm_finish (const char *operation)
 {
-        gettimeofday (&tv2, NULL);
-        timersub (&tv2, &tv1, &tv_elapsed);
+	qb_util_stopwatch_stop(sw);
 
 	if (strlen (operation) > 22) {
-        	printf ("%s\t\t", operation);
+		printf ("%s\t\t", operation);
 	} else {
-        	printf ("%s\t\t\t", operation);
+		printf ("%s\t\t\t", operation);
 	}
-        printf ("%9.3f operations/sec\n",
-                ((float)ITERATIONS) /  (tv_elapsed.tv_sec + (tv_elapsed.tv_usec /
1000000.0)));
+	printf("%9.3f operations/sec\n",
+	       ((float)ITERATIONS) /  qb_util_stopwatch_sec_elapsed_get(sw));
 }
 
-int main (void)
+int
+main(void)
 {
 	int i;
 
+	sw =  qb_util_stopwatch_create();
 	qb_log_init("simple-log", LOG_USER, LOG_INFO);
 	qb_log_ctl(QB_LOG_SYSLOG, QB_LOG_CONF_THREADED, QB_TRUE);
 
@@ -76,28 +62,28 @@ int main (void)
 	for (i = 0; i < ITERATIONS; i++) {
 		qb_log(LOG_DEBUG, "hello");
 	}
-	bm_start();
+	qb_util_stopwatch_start(sw);
 	for (i = 0; i < ITERATIONS; i++) {
 		qb_log(LOG_DEBUG, "RecordA");
 	}
 	bm_finish ("qb_log 1 arguments:");
-	bm_start();
+	qb_util_stopwatch_start(sw);
 	for (i = 0; i < ITERATIONS; i++) {
 		qb_log(LOG_DEBUG, "%s%s", "RecordA", "RecordB");
 	}
 	bm_finish ("qb_log 2 args(str):");
-	bm_start();
+	qb_util_stopwatch_start(sw);
 	for (i = 0; i < ITERATIONS; i++) {
 		qb_log(LOG_DEBUG, "%s%s%s", "RecordA", "RecordB",
"RecordC");
 	}
 	bm_finish ("qb_log 3 args(str):");
-	bm_start();
+	qb_util_stopwatch_start(sw);
 	for (i = 0; i < ITERATIONS; i++) {
 		qb_log(LOG_DEBUG, "%i %u %p", -534, 4508, &i);
 	}
 	bm_finish ("qb_log 3 args(int):");
 #ifdef HAVE_DICT_WORDS
-	bm_start();
+	qb_util_stopwatch_start(sw);
 	log_dict_words();
 	bm_finish ("qb_log /usr/share/dict/words:");
 #endif /* HAVE_DICT_WORDS */
diff --git a/tests/bmc.c b/tests/bmc.c
index 85db32d..3e805ed 100644
--- a/tests/bmc.c
+++ b/tests/bmc.c
@@ -32,42 +32,18 @@ int32_t events = QB_FALSE;
 int32_t verbose = 0;
 static qb_ipcc_connection_t *conn;
 #define MAX_MSG_SIZE (8192*128)
-
-static struct timeval tv1, tv2, tv_elapsed;
-
-#ifndef QB_BSD
-#define timersub(a, b, result)					\
-do {								\
-	(result)->tv_sec = (a)->tv_sec - (b)->tv_sec;		\
-	(result)->tv_usec = (a)->tv_usec - (b)->tv_usec;	\
-	if ((result)->tv_usec < 0) {				\
-		--(result)->tv_sec;				\
-		(result)->tv_usec += 1000000;			\
-	}							\
-} while (0)
-#endif
-
-static void bm_start(void)
-{
-	gettimeofday(&tv1, NULL);
-}
+static qb_util_stopwatch_t *sw;
 
 static void bm_finish(const char *operation, int32_t size)
 {
 	float ops_per_sec;
 	float mbs_per_sec;
+	float elapsed;
 
-	gettimeofday(&tv2, NULL);
-	timersub(&tv2, &tv1, &tv_elapsed);
-
-	ops_per_sec =
-	    ((float)ITERATIONS) / (((float)tv_elapsed.tv_sec) +
-				   (((float)tv_elapsed.tv_usec) / 1000000.0));
-
-	mbs_per_sec =
-	    ((((float)ITERATIONS) * size) /
-	     (((float)tv_elapsed.tv_sec) +
-	      (((float)tv_elapsed.tv_usec) / 1000000.0))) / (1024.0 * 1024.0);
+	qb_util_stopwatch_stop(sw);
+	elapsed = qb_util_stopwatch_sec_elapsed_get(sw);
+	ops_per_sec = ((float)ITERATIONS) / elapsed;
+	mbs_per_sec = ((((float)ITERATIONS) * size) / elapsed) / (1024.0 * 1024.0);
 
 	printf("write size, %d, OPs/sec, %9.3f, ", size, ops_per_sec);
 	printf("MB/sec, %9.3f\n", mbs_per_sec);
@@ -198,11 +174,12 @@ int32_t main(int32_t argc, char *argv[])
 		exit(1);
 	}
 
+	sw =  qb_util_stopwatch_create();
 	size = QB_MAX(sizeof(struct qb_ipc_request_header), 64);
 	for (j = 0; j < 20; j++) {
 		if (size >= MAX_MSG_SIZE)
 			break;
-		bm_start();
+		qb_util_stopwatch_start(sw);
 		for (i = 0; i < ITERATIONS; i++) {
 			if (bmc_send_nozc(size) == -1) {
 				break;
-- 
1.7.6

[PATCH 3/3] Initial map using either a skiplist or a hashtable

[Angus Salkeld]

Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt;
---
 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&gt;
+ *
+ * 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&gt;
+ *
+ * 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&gt;
+ *
+ * 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&gt;
+ *
+ * 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&gt;
+ *
+ * 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&gt;
+ *
+ * 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

[PATCH 3/3] Initial map using either a skiplist or a hashtable

[Angus Salkeld]

Honza, how is this API to you?

You might want:
- a different style of iterator?
- more qb_map_destroy options 
>  destroy map, but not data
>  destroy map and data 
Create map from another type of map:
  qb_hashtable_create_from(m, ...)
  So you can have a hashtable and then sort it by
  inserting into a skiplist.

Other search options?

Regards
Angus


On Mon, Aug 22, 2011 at 01:30:50PM +1000, Angus Salkeld wrote:
>  Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt; 
[...]
>  
>  +/**
>  + * 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);
>  +

[PATCH 3/3] Initial map using either a skiplist or a hashtable

[Jan Friesse]

Angus,
I'm afraid that I antedate answer, but I will still ask.

What guarantees gives me iteration? I'm especially interested answer for:
- I have iterator 1 in the middle, and somebody will delete item right 
after iterator 1 (middle + 1), what will happen? Or more generally, 
somebody deletes items middle + n, where n = <1, no_items - middle>

- Iterator on the beginning, somebody will add item on the end. Will I 
get that item.

- I have iterator 1 and iterator 2 on the beginning. Iterator 2 makes 
some progress (lets say to the middle), and somebody will delete few 
items in interval <0, middle> and add some items in same interval. What 
iterator 1 will see?

Regards,
   Honza

Angus Salkeld napsal(a):
>  Honza, how is this API to you?
>  
>  You might want:
>  - a different style of iterator?
>  - more qb_map_destroy options 
>    > destroy map, but not data
>    > destroy map and data
>  
>  Create map from another type of map:
>    qb_hashtable_create_from(m, ...)
>    So you can have a hashtable and then sort it by
>    inserting into a skiplist.
>  
>  Other search options?
>  
>  Regards
>  Angus
>  
>  
>  On Mon, Aug 22, 2011 at 01:30:50PM +1000, Angus Salkeld wrote:
> > Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt;
>  [...]
> > +/**
> > + * 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);
> > +

[PATCH 3/3] Initial map using either a skiplist or a hashtable

[Angus Salkeld]

On Tue, Aug 23, 2011 at 12:48:07PM +0200, Jan Friesse wrote:
>  Angus,
>  I'm afraid that I antedate answer, but I will still ask.
>  
>  What guarantees gives me iteration? I'm especially interested answer for:
>  - I have iterator 1 in the middle, and somebody will delete item right 
>  after iterator 1 (middle + 1), what will happen? Or more generally, 
>  somebody deletes items middle + n, where n = <1, no_items - middle> 
The maps currently will not handle these situations well :(
I would need to reference count the nodes to support that.

>  
>  - Iterator on the beginning, somebody will add item on the end. Will I 
>  get that item. 
This should be OK (not tested though).

>  
>  - I have iterator 1 and iterator 2 on the beginning. Iterator 2 makes 
>  some progress (lets say to the middle), and somebody will delete few 
>  items in interval <0, middle> and add some items in same interval. What 
>  iterator 1 will see? 
The iterators are "live" and don't do snapshots/versioning.

What behaviour do you think we are going to need?

We could have stable and live iterators:
live: you see changes as they happen
stable: changes are queued until all stable iterators have completed

What's important to you, the stability of the iterator or that the
changes go in together (transaction-like)?

-Angus

>  
>  Regards,
>     Honza
>  
>  Angus Salkeld napsal(a):
>  > Honza, how is this API to you?
>  > 
>  > You might want:
>  > - a different style of iterator?
>  > - more qb_map_destroy options 
>  >   > destroy map, but not data
>  >   > destroy map and data
>  > 
>  > Create map from another type of map:
>  >   qb_hashtable_create_from(m, ...)
>  >   So you can have a hashtable and then sort it by
>  >   inserting into a skiplist.
>  > 
>  > Other search options?
>  > 
>  > Regards
>  > Angus
>  > 
>  > 
>  > On Mon, Aug 22, 2011 at 01:30:50PM +1000, Angus Salkeld wrote:
>  >> Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com&gt;
>  > [...]
>  >> +/**
>  >> + * 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);
>  >> +
>  
>  _______________________________________________
>  quarterback-devel mailing list
>  quarterback-devel(a)lists.fedorahosted.org
>  https://fedorahosted.org/mailman/listinfo/quarterback-devel