ztree(3)
CZMQ Manual - CZMQ/2.2.1
Name
ztree - generic type-free red-black tree container
Synopsis
// Callback function for ztee_walk method
typedef int (ztree_walk_fn) (const char *key, void *value, void *argument);
// Callback function for ztree_freefn method
typedef void (ztree_free_fn) (void *data);
// Comparison function for ztree ordering
// returns -1 for key1 < key2, 0 if key1 == key 2, 1 for key1 > key2
// if key's are strings okay to use strcmp as function
typedef int (ztree_compare_fn) (const char *key1, const char *key2);
// Create a new tree container
CZMQ_EXPORT ztree_t *
ztree_new (ztree_compare_fn *compare_func);
// Destroy a tree container
CZMQ_EXPORT void
ztree_destroy (ztree_t **self_p);
// Insert node into tree with specified key and value
// If key is already present returns -1 and leaves existing node unchanged
// Returns 0 on success.
CZMQ_EXPORT int
ztree_insert (ztree_t *self, const char *key, void *value);
// Update node in tree with specified key and value.
// If key is already present, destroys old value and inserts new one.
// Use free_fn method to ensure deallocator is properly called on value.
CZMQ_EXPORT void
ztree_update (ztree_t *self, const char *key, void *value);
// Remove a node specified by key from the tree. If there was no such
// node, this function does nothing.
CZMQ_EXPORT void
ztree_delete (ztree_t *self, const char *key);
// Return the value at the specified key, or null
CZMQ_EXPORT void *
ztree_lookup (ztree_t *self, const char *key);
// Set a free function for the specified tree node. When the value is
// destroyed, the free function, if any, is called on that node.
// Use this when tree values are dynamically allocated, to ensure that
// you don't have memory leaks. You can pass 'free' or NULL as a free_fn.
// Returns the item, or NULL if there is no such item.
CZMQ_EXPORT void *
ztree_freefn (ztree_t *self, const char *key, ztree_free_fn *free_fn);
// Return the number of keys/values in the tree
CZMQ_EXPORT size_t
ztree_size (ztree_t *self);
// Return keys for nodes in tree
CZMQ_EXPORT zlist_t *
ztree_keys (ztree_t *self);
// Copy the entire tree, return the copy
CZMQ_EXPORT ztree_t *
ztree_dup (ztree_t *self);
// Walk the tree depth-first, left-to-right order.
// Stops if callback function returns non-zero and returns
// final return code from callback function (zero = success).
CZMQ_EXPORT int
ztree_walk (ztree_t *self, ztree_walk_fn *callback, void *argument);
// Save tree to a text file in name=value format. Values must be
// printable strings; keys may not contain '=' character. Returns 0 if OK,
// else -1 if a file error occurred.
CZMQ_EXPORT int
ztree_save (ztree_t *self, const char *filename);
// Load tree from a text file in name=value format; tree must
// already exist. Tree values must printable strings; keys may not contain
// '=' character. Returns 0 if OK, else -1 if a file was not readable.
CZMQ_EXPORT int
ztree_load (ztree_t *self, const char *filename);
// Set tree for automatic value destruction
CZMQ_EXPORT void
ztree_autofree (ztree_t *self);
// Self test of this class
CZMQ_EXPORT void
ztree_test (int verbose);
Description
Red black tree container Derived from Emin Martianan's Red Black which is licensed for free use. http://web.mit.edu/~emin/www.old/source_code/red_black_tree/index.html
TODO: code style needs cleanup to match CLASS guideliness - poor variable names like x - indentation and if/else layouts - possibly removal of all tree code to foreign/
Example
From ztree_test method
ztree_t *tree = ztree_new (strcmp);
assert (tree);
assert (ztree_size (tree) == 0);
assert (ztree_lookup (tree, "NOTHING") == NULL);
// Insert some nodes
int rc;
rc = ztree_insert (tree, "DEADBEEF", "dead beef");
assert (rc == 0);
rc = ztree_insert (tree, "ABADCAFE", "a bad cafe");
assert (rc == 0);
rc = ztree_insert (tree, "C0DEDBAD", "coded bad");
assert (rc == 0);
rc = ztree_insert (tree, "DEADF00D", "dead food");
assert (rc == 0);
assert (ztree_size (tree) == 4);
// Look for existing nodes
char *value;
value = (char *) ztree_lookup (tree, "DEADBEEF");
assert (streq (value, "dead beef"));
value = (char *) ztree_lookup (tree, "ABADCAFE");
assert (streq (value, "a bad cafe"));
value = (char *) ztree_lookup (tree, "C0DEDBAD");
assert (streq (value, "coded bad"));
value = (char *) ztree_lookup (tree, "DEADF00D");
assert (streq (value, "dead food"));
// Look for non-existent nodes
value = (char *) ztree_lookup (tree, "foo");
assert (value == NULL);
// Try to insert duplicate nodes
rc = ztree_insert (tree, "DEADBEEF", "foo");
assert (rc == -1);
value = (char *) ztree_lookup (tree, "DEADBEEF");
assert (streq (value, "dead beef"));
// Test keys method
zlist_t *keys = ztree_keys (tree);
assert (zlist_size (keys) == 4);
// Test that keys are in order
void *key, *pred;
pred = zlist_first (keys);
assert (pred);
while ((key = zlist_next (keys))) {
assert (strcmp ((char *) key, (char *) pred) > 0);
pred = key;
}
zlist_destroy (&keys);
// Test dup method
ztree_t *copy = ztree_dup (tree);
assert (ztree_size (copy) == ztree_size (tree));
value = (char *) ztree_lookup (copy, "DEADF00D");
assert (value);
assert (streq (value, "dead food"));
ztree_destroy (©);
// Test walk
assert (0 == ztree_walk (tree, test_walk, tree));
assert (-1 == ztree_walk (tree, test_walk_error, tree));
// Test save and load
ztree_save (tree, ".cache");
copy = ztree_new (strcmp);
ztree_load (copy, ".cache");
assert (ztree_size (copy) == ztree_size (tree));
value = (char *) ztree_lookup (copy, "DEADBEEF");
assert (value);
assert (streq (value, "dead beef"));
ztree_destroy (©);
zsys_file_delete (".cache");
// Delete some nodes
assert (ztree_size (tree) == 4);
ztree_delete (tree, "DEADF00D");
value = (char *) ztree_lookup (tree, "DEADF00D");
assert (value == NULL);
assert (ztree_size (tree) == 3);
ztree_delete (tree, "C0DEDBAD");
value = (char *) ztree_lookup (tree, "C0DEDBAD");
assert (value == NULL);
assert (ztree_size (tree) == 2);
// Change value of an existing node
ztree_update (tree, "ABADCAFE", "A Bad Cafe");
value = (char *) ztree_lookup (tree, "ABADCAFE");
assert (value != NULL);
assert (streq(value, "A Bad Cafe"));
// Update with non-existant node
ztree_update (tree, "C0DEDEBAD", "Coded Bad");
value = (char *) ztree_lookup (tree, "C0DEDEBAD");
assert (value);
assert (streq(value, "Coded Bad"));
// Check that the queue is robust against random usage
struct {
char name [100];
bool exists;
} testset [200];
memset (testset, 0, sizeof (testset));
int testmax = 200, testnbr, iteration;
srandom ((unsigned) time (NULL));
for (iteration = 0; iteration < 25000; iteration++) {
testnbr = randof (testmax);
if (testset [testnbr].exists) {
value = (char *) ztree_lookup (tree, testset [testnbr].name);
assert (value);
ztree_delete (tree, testset [testnbr].name);
testset [testnbr].exists = false;
}
else {
sprintf (testset [testnbr].name, "%x-%x", rand (), rand ());
if (ztree_insert (tree, testset [testnbr].name, "") == 0)
testset [testnbr].exists = true;
}
}
// Test 10K lookups
for (iteration = 0; iteration < 10000; iteration++)
value = (char *) ztree_lookup (tree, "DEADBEEFABADCAFE");
// Destructor should be safe to call twice
ztree_destroy (&tree);
ztree_destroy (&tree); assert (tree == NULL);
See also
Authors
The CZMQ manual was written by Pieter Hintjens<moc.xitami|hp#moc.xitami|hp>.
Resources
Main web site: http://czmq.zeromq.org/
Report bugs to the ØMQ development mailing list: <gro.qmorez.stsil|ved-qmorez#gro.qmorez.stsil|ved-qmorez>
Copyright
Copyright (c) 1991-2014 iMatix and Contributors. License LGPLv3+: GNU LGPL 3 or later <http://gnu.org/licenses/lgpl.html>. This is free software: you are free to change it and redistribute it. There is NO WARRANTY, to the extent permitted by law. For details see the files COPYING and COPYING.LESSER included with the CZMQ distribution.