ztree(3) ======== 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 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, 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 -------- linkczmq:czmq[7]