Mercurial > hg > ucx / changeset

--- a/docs/src/modules.md	Thu May 03 10:09:49 2018 +0200
+++ b/docs/src/modules.md	Thu May 03 10:44:33 2018 +0200
@@ -51,6 +51,47 @@
 All common binary tree operations are implemented. Furthermore, this module
 provides search functions via lower and upper bounds.
 
+### Filtering items with a time window
+
+Suppose you have a list of items which contain a `time_t` value and your task
+is to find all items within a time window `[t_start, t_end]`.
+With AVL Trees this is easy:
+```C
+/* ---------------------
+ * Somewhere in a header
+ */
+typedef struct {
+    time_t ts;
+    // other important data
+} MyObject;
+
+/* -----------
+ * Source code
+ */
+
+UcxAVLTree* tree = ucx_avl_new(ucx_longintcmp);
+// ... populate tree with objects, use '& MyObject.ts' as key ...
+
+
+// Now find every item, with 30 <= ts <= 70
+time_t ts_start = 30;
+time_t ts_end = 70;
+
+printf("Values in range:\n");
+for (
+        UcxAVLNode* node = ucx_avl_find_node(
+            tree, (intptr_t) &ts_start,
+            ucx_longintdist, UCX_AVL_FIND_LOWER_BOUNDED);
+        node && (*(time_t*)node->key) <= ts_end;
+        node = ucx_avl_succ(node)
+    ) {
+    printf(" ts: %ld\n", ((MyObject*)node->value)->ts);
+}
+
+ucx_avl_free_content(tree, free);
+ucx_avl_free(tree);
+```
+
 ## Buffer
 
 *Header file:* [buffer.h](api/buffer_8h.html)  

--- a/src/avl.c	Thu May 03 10:09:49 2018 +0200
+++ b/src/avl.c	Thu May 03 10:44:33 2018 +0200
@@ -136,6 +136,23 @@
     alfree(al, tree);
 }
 
+static void ucx_avl_free_content_node(UcxAllocator *al, UcxAVLNode *node,
+        ucx_destructor destr) {
+    if (node) {
+        ucx_avl_free_content_node(al, node->left, destr);
+        ucx_avl_free_content_node(al, node->right, destr);
+        if (destr) {
+            destr(node->value);
+        } else {
+            alfree(al, node->value);
+        }
+    }
+}
+
+void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr) {
+    ucx_avl_free_content_node(tree->allocator, tree->root, destr);
+}
+
 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {
     UcxAVLNode *n = tree->root;
     int cmpresult;

--- a/src/map.c	Thu May 03 10:09:49 2018 +0200
+++ b/src/map.c	Thu May 03 10:44:33 2018 +0200
@@ -89,7 +89,7 @@
         if (destr) {
             destr(val);
         } else {
-            map->allocator->free(val, NULL);
+            alfree(map->allocator, val);
         }
     }
 }

--- a/src/ucx/avl.h	Thu May 03 10:09:49 2018 +0200
+++ b/src/ucx/avl.h	Thu May 03 10:44:33 2018 +0200
@@ -135,11 +135,36 @@
 
 /**
  * Destroys a UcxAVLTree.
+ * 
+ * Note, that the contents are not automatically freed.
+ * Use may use #ucx_avl_free_content() before calling this function.
+ * 
  * @param tree the tree to destroy
+ * @see ucx_avl_free_content()
  */
 void ucx_avl_free(UcxAVLTree *tree);
 
 /**
+ * Frees the contents of a UcxAVLTree.
+ * 
+ * This is a convenience function that iterates over the tree and passes all
+ * values to the specified destructor function.
+ * 
+ * If no destructor is specified (<code>NULL</code>), the free() function of
+ * the tree's own allocator is used.
+ * 
+ * You must ensure, that it is valid to pass each value in the map to the same
+ * destructor function.
+ * 
+ * You should free the entire tree afterwards, as the contents will be invalid.
+ * 
+ * @param tree for which the contents shall be freed
+ * @param destr optional pointer to a destructor function
+ * @see ucx_avl_free()
+ */
+void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr);
+
+/**
  * Macro for initializing a new UcxAVLTree with the default allocator and a
  * ucx_ptrcmp() compare function.
  *