Thu, 03 May 2018 10:44:33 +0200
adds ucx_avl_free_content() function and documentation in modules.md
docs/src/modules.md | file | annotate | diff | comparison | revisions | |
src/avl.c | file | annotate | diff | comparison | revisions | |
src/map.c | file | annotate | diff | comparison | revisions | |
src/ucx/avl.h | file | annotate | diff | comparison | revisions |
1.1 --- a/docs/src/modules.md Thu May 03 10:09:49 2018 +0200 1.2 +++ b/docs/src/modules.md Thu May 03 10:44:33 2018 +0200 1.3 @@ -51,6 +51,47 @@ 1.4 All common binary tree operations are implemented. Furthermore, this module 1.5 provides search functions via lower and upper bounds. 1.6 1.7 +### Filtering items with a time window 1.8 + 1.9 +Suppose you have a list of items which contain a `time_t` value and your task 1.10 +is to find all items within a time window `[t_start, t_end]`. 1.11 +With AVL Trees this is easy: 1.12 +```C 1.13 +/* --------------------- 1.14 + * Somewhere in a header 1.15 + */ 1.16 +typedef struct { 1.17 + time_t ts; 1.18 + // other important data 1.19 +} MyObject; 1.20 + 1.21 +/* ----------- 1.22 + * Source code 1.23 + */ 1.24 + 1.25 +UcxAVLTree* tree = ucx_avl_new(ucx_longintcmp); 1.26 +// ... populate tree with objects, use '& MyObject.ts' as key ... 1.27 + 1.28 + 1.29 +// Now find every item, with 30 <= ts <= 70 1.30 +time_t ts_start = 30; 1.31 +time_t ts_end = 70; 1.32 + 1.33 +printf("Values in range:\n"); 1.34 +for ( 1.35 + UcxAVLNode* node = ucx_avl_find_node( 1.36 + tree, (intptr_t) &ts_start, 1.37 + ucx_longintdist, UCX_AVL_FIND_LOWER_BOUNDED); 1.38 + node && (*(time_t*)node->key) <= ts_end; 1.39 + node = ucx_avl_succ(node) 1.40 + ) { 1.41 + printf(" ts: %ld\n", ((MyObject*)node->value)->ts); 1.42 +} 1.43 + 1.44 +ucx_avl_free_content(tree, free); 1.45 +ucx_avl_free(tree); 1.46 +``` 1.47 + 1.48 ## Buffer 1.49 1.50 *Header file:* [buffer.h](api/buffer_8h.html)
2.1 --- a/src/avl.c Thu May 03 10:09:49 2018 +0200 2.2 +++ b/src/avl.c Thu May 03 10:44:33 2018 +0200 2.3 @@ -136,6 +136,23 @@ 2.4 alfree(al, tree); 2.5 } 2.6 2.7 +static void ucx_avl_free_content_node(UcxAllocator *al, UcxAVLNode *node, 2.8 + ucx_destructor destr) { 2.9 + if (node) { 2.10 + ucx_avl_free_content_node(al, node->left, destr); 2.11 + ucx_avl_free_content_node(al, node->right, destr); 2.12 + if (destr) { 2.13 + destr(node->value); 2.14 + } else { 2.15 + alfree(al, node->value); 2.16 + } 2.17 + } 2.18 +} 2.19 + 2.20 +void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr) { 2.21 + ucx_avl_free_content_node(tree->allocator, tree->root, destr); 2.22 +} 2.23 + 2.24 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { 2.25 UcxAVLNode *n = tree->root; 2.26 int cmpresult;
3.1 --- a/src/map.c Thu May 03 10:09:49 2018 +0200 3.2 +++ b/src/map.c Thu May 03 10:44:33 2018 +0200 3.3 @@ -89,7 +89,7 @@ 3.4 if (destr) { 3.5 destr(val); 3.6 } else { 3.7 - map->allocator->free(val, NULL); 3.8 + alfree(map->allocator, val); 3.9 } 3.10 } 3.11 }
4.1 --- a/src/ucx/avl.h Thu May 03 10:09:49 2018 +0200 4.2 +++ b/src/ucx/avl.h Thu May 03 10:44:33 2018 +0200 4.3 @@ -135,11 +135,36 @@ 4.4 4.5 /** 4.6 * Destroys a UcxAVLTree. 4.7 + * 4.8 + * Note, that the contents are not automatically freed. 4.9 + * Use may use #ucx_avl_free_content() before calling this function. 4.10 + * 4.11 * @param tree the tree to destroy 4.12 + * @see ucx_avl_free_content() 4.13 */ 4.14 void ucx_avl_free(UcxAVLTree *tree); 4.15 4.16 /** 4.17 + * Frees the contents of a UcxAVLTree. 4.18 + * 4.19 + * This is a convenience function that iterates over the tree and passes all 4.20 + * values to the specified destructor function. 4.21 + * 4.22 + * If no destructor is specified (<code>NULL</code>), the free() function of 4.23 + * the tree's own allocator is used. 4.24 + * 4.25 + * You must ensure, that it is valid to pass each value in the map to the same 4.26 + * destructor function. 4.27 + * 4.28 + * You should free the entire tree afterwards, as the contents will be invalid. 4.29 + * 4.30 + * @param tree for which the contents shall be freed 4.31 + * @param destr optional pointer to a destructor function 4.32 + * @see ucx_avl_free() 4.33 + */ 4.34 +void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr); 4.35 + 4.36 +/** 4.37 * Macro for initializing a new UcxAVLTree with the default allocator and a 4.38 * ucx_ptrcmp() compare function. 4.39 *