This provides a map interface to a Patricia trie, hashtable or skiplist. More...

#include <stdint.h>
#include <unistd.h>

Include dependency graph for qbmap.h:

Macros
#define	QB_MAP_NOTIFY_DELETED 1

#define	QB_MAP_NOTIFY_REPLACED 2

#define	QB_MAP_NOTIFY_INSERTED 4

#define	QB_MAP_NOTIFY_RECURSIVE 8

#define	QB_MAP_NOTIFY_FREE 16

Typedefs
typedef struct qb_map	qb_map_t
	This is an opaque data type representing an instance of a map. More...

typedef struct qb_map_iter	qb_map_iter_t
	This is an opaque data type representing an iterator instance. More...

typedef void(*	qb_map_notify_fn )(uint32_t event, char key, void old_value, void value, void user_data)

typedef int32_t(*	qb_map_transverse_fn )(const char key, void value, void *user_data)

Functions
qb_map_t *	qb_hashtable_create (size_t max_size)
	Create an unsorted map based on a hashtable. More...

qb_map_t *	qb_skiplist_create (void)
	Create a sorted map using a skiplist. More...

qb_map_t *	qb_trie_create (void)
	Create a sorted map using a Patricia trie or "Radix tree". More...

void	qb_trie_dump (qb_map_t *m)
	print out the nodes in the trie More...

int32_t	qb_map_notify_add (qb_map_t m, const char key, qb_map_notify_fn fn, int32_t events, void *user_data)
	Add a notifier to the map. More...

int32_t	qb_map_notify_del (qb_map_t m, const char key, qb_map_notify_fn fn, int32_t events)
	Delete a notifier from the map. More...

int32_t	qb_map_notify_del_2 (qb_map_t m, const char key, qb_map_notify_fn fn, int32_t events, void *user_data)
	Delete a notifier from the map (including the userdata). More...

void	qb_map_put (qb_map_t map, const char key, const void *value)
	Inserts a new key and value into a qb_map_t. More...

void *	qb_map_get (qb_map_t map, const char key)
	Gets the value corresponding to the given key. More...

int32_t	qb_map_rm (qb_map_t map, const char key)
	Removes a key/value pair from a map. More...

size_t	qb_map_count_get (qb_map_t *map)
	Get the number of items in the map. More...

void	qb_map_foreach (qb_map_t map, qb_map_transverse_fn func, void user_data)
	Calls the given function for each of the key/value pairs in the map. More...

qb_map_iter_t *	qb_map_iter_create (qb_map_t *map)
	Create an iterator. More...

qb_map_iter_t *	qb_map_pref_iter_create (qb_map_t map, const char prefix)
	Create a prefix iterator. More...

const char *	qb_map_iter_next (qb_map_iter_t i, void *value)
	Get the next item. More...

void	qb_map_iter_free (qb_map_iter_t *i)
	free the iterator More...

void	qb_map_destroy (qb_map_t *map)
	Destroy the map, removes all the items from the map. More...

Detailed Description

This provides a map interface to a Patricia trie, hashtable or skiplist.

Ordering: The hashtable is NOT ordered, but ptrie and skiplist are.

Iterating: Below is a simple example of how to iterate over a map.
const char *p;

void *data;

qb_map_iter_t *it = qb_map_iter_create(m);

for (p = qb_map_iter_next(it, &data); p; p = qb_map_iter_next(it, &data)) {

printf("%s > %s\n", p, (char*) data);

}

qb_map_iter_free(it);

Deletion of items within the iterator is supported. But note do not free the item memory in the iterator. If you need to free the data items then register for a notifier and free the memory there. This is required as the items are reference counted.

qb_map_notify_add(m, NULL, my_map_free_handler,

QB_MAP_NOTIFY_FREE, NULL);

Notifications: These allow you to get callbacks when values are inserted/removed or replaced.

Note: hashtable only supports deletion and replacement notificatins. There is also a special global callback for freeing deleted and replaced values (QB_MAP_NOTIFY_FREE).

See Also: qb_map_notify_add() qb_map_notify_del_2()

Prefix matching: The ptrie supports prefixes in the iterator:

it = qb_map_pref_iter_create(m, "aa");
while ((p = qb_map_iter_next(it, &data)) != NULL) {
    printf("%s > %s\n", p, (char*)data);
}
qb_map_iter_free(it);

The ptrie also supports prefixes in notifications: (remember to pass QB_MAP_NOTIFY_RECURSIVE into the notify_add.

qb_map_notify_add(m, "root", my_map_notification,
            (QB_MAP_NOTIFY_INSERTED|
             QB_MAP_NOTIFY_DELETED|
             QB_MAP_NOTIFY_REPLACED|
             QB_MAP_NOTIFY_RECURSIVE),
            NULL);

Macro Definition Documentation

#define QB_MAP_NOTIFY_DELETED 1

#define QB_MAP_NOTIFY_FREE 16

#define QB_MAP_NOTIFY_INSERTED 4

#define QB_MAP_NOTIFY_RECURSIVE 8

#define QB_MAP_NOTIFY_REPLACED 2

Typedef Documentation

typedef struct qb_map_iter qb_map_iter_t

This is an opaque data type representing an iterator instance.

typedef void(* qb_map_notify_fn)(uint32_t event, char *key, void *old_value, void *value, void *user_data)

typedef struct qb_map qb_map_t

This is an opaque data type representing an instance of a map.

typedef int32_t(* qb_map_transverse_fn)(const char *key, void *value, void *user_data)

Function Documentation

qb_map_t* qb_hashtable_create ( size_t max_size )

Create an unsorted map based on a hashtable.

Parameters

max_size maximum size of the hashtable

Returns: the map instance

size_t qb_map_count_get ( qb_map_t * map )

Get the number of items in the map.

void qb_map_destroy ( qb_map_t * map )

Destroy the map, removes all the items from the map.

void qb_map_foreach	(	qb_map_t *	map,
		qb_map_transverse_fn	func,
		void *	user_data
	)

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_get	(	qb_map_t *	map,
		const char *	key
	)

Gets the value corresponding to the given key.

Return values

NULL	(if the key does not exist)
a	pointer to the value

qb_map_iter_t* qb_map_iter_create ( qb_map_t * map )

Create an iterator.

void qb_map_iter_free ( qb_map_iter_t * i )

free the iterator

Parameters

i	the iterator

const char* qb_map_iter_next	(	qb_map_iter_t *	i,
		void **	value
	)

Get the next item.

Parameters

i	the iterator
value	(out) the next item's value

Return values

the	next key
NULL	- the end of the iteration

int32_t qb_map_notify_add	(	qb_map_t *	m,
		const char *	key,
		qb_map_notify_fn	fn,
		int32_t	events,
		void *	user_data
	)

Add a notifier to the map.

Parameters

m	the map instance
key	the key (or prefix) to attach the notification to.
fn	the callback
events	the type of events to register for.
user_data	a pointer to be passed into the callback

Note: QB_MAP_NOTIFY_INSERTED is only valid on tries.; you can use key prefixes with trie maps.

Return values

0	success
-errno	failure

int32_t qb_map_notify_del	(	qb_map_t *	m,
		const char *	key,
		qb_map_notify_fn	fn,
		int32_t	events
	)

Delete a notifier from the map.

Note: the key,fn and events must match those you added.

Parameters

m	the map instance
key	the key (or prefix) to attach the notification to.
fn	the callback
events	the type of events to register for.

Return values

0	success
-errno	failure

int32_t qb_map_notify_del_2	(	qb_map_t *	m,
		const char *	key,
		qb_map_notify_fn	fn,
		int32_t	events,
		void *	user_data
	)

Delete a notifier from the map (including the userdata).

Note: the key, fn, events and userdata must match those you added.

Parameters

m	the map instance
key	the key (or prefix) to attach the notification to.
fn	the callback
events	the type of events to register for.
user_data	a pointer to be passed into the callback

Return values

0	success
-errno	failure

qb_map_iter_t* qb_map_pref_iter_create	(	qb_map_t *	map,
		const char *	prefix
	)

Create a prefix iterator.

This will iterate over all items with the given prefix.

Note: this is only supported by the trie.

void qb_map_put	(	qb_map_t *	map,
		const char *	key,
		const void *	value
	)

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.

int32_t qb_map_rm	(	qb_map_t *	map,
		const char *	key
	)

Removes a key/value pair from a map.

qb_map_t* qb_skiplist_create ( void )

Create a sorted map using a skiplist.

Returns: the map instance

qb_map_t* qb_trie_create ( void )

Create a sorted map using a Patricia trie or "Radix tree".

See the wikipedia Radix_tree and Trie pages.

void qb_trie_dump ( qb_map_t * m )

print out the nodes in the trie

(for debug purposes)

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation