ztree(3)

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 (&copy);

    // 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 (&copy);
    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

czmq(7)

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.