adds ucx_avl_free_content() function and documentation in modules.md

Thu, 03 May 2018 10:44:33 +0200

author
Mike Becker <universe@uap-core.de>
date
Thu, 03 May 2018 10:44:33 +0200
changeset 287
98da78a1e69a
parent 286
85f55abea563
child 289
a5eabd407774

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   * 

mercurial