libqb  2.0.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Macros | Typedefs | Functions
qbmap.h File Reference

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_tqb_hashtable_create (size_t max_size)
 Create an unsorted map based on a hashtable. More...
 
qb_map_tqb_skiplist_create (void)
 Create a sorted map using a skiplist. More...
 
qb_map_tqb_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_tqb_map_iter_create (qb_map_t *map)
 Create an iterator. More...
 
qb_map_iter_tqb_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;
for (p = qb_map_iter_next(it, &data); p; p = qb_map_iter_next(it, &data)) {
printf("%s > %s\n", p, (char*) data);
}

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,
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:
while ((p = qb_map_iter_next(it, &data)) != NULL) {
printf("%s > %s\n", p, (char*)data);
}

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

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_sizemaximum 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)
apointer 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
ithe iterator
const char* qb_map_iter_next ( qb_map_iter_t i,
void **  value 
)

Get the next item.

Parameters
ithe iterator
value(out) the next item's value
Return values
thenext 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
mthe map instance
keythe key (or prefix) to attach the notification to.
fnthe callback
eventsthe type of events to register for.
user_dataa 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
0success
-errnofailure
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
mthe map instance
keythe key (or prefix) to attach the notification to.
fnthe callback
eventsthe type of events to register for.
Return values
0success
-errnofailure
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
mthe map instance
keythe key (or prefix) to attach the notification to.
fnthe callback
eventsthe type of events to register for.
user_dataa pointer to be passed into the callback
Return values
0success
-errnofailure
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)