wsutil/wmem/wmem_interval_tree.h

   1 /** @file
   2  * Definitions for the Wireshark Memory Manager Red-Black Tree
   3  * Based on the red-black tree implementation in epan/emem.*
   4  * Copyright 2015, Matthieu coudron <matthieu.coudron@lip6.fr>
   5  *
   6  * Wireshark - Network traffic analyzer
   7  * By Gerald Combs <gerald@wireshark.org>
   8  * Copyright 1998 Gerald Combs
   9  *
  10  * SPDX-License-Identifier: GPL-2.0-or-later
  11  */
  12 #ifndef __WMEM_INTERVAL_TREE_H__
  13 #define __WMEM_INTERVAL_TREE_H__
  14
  15 #include "wmem_core.h"
  16 #include "wmem_tree.h"
  17 #include "wmem_list.h"
  18
  19
  20 #ifdef __cplusplus
  21 extern "C" {
  22 #endif /* __cplusplus */
  23
  24 /** @addtogroup wmem
  25  *  @{
  26  *    @defgroup wmem-interval-tree Interval Tree
  27  *
  28  * http://www.geeksforgeeks.org/interval-tree/
  29  * The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc ...
  30  * to maintain a set of intervals so that all operations can be done in O(Logn) time.
  31  *    @{
  32  * Following wikipedia's convention this is an augmented tree rather then an interval tree
  33  * http://www.wikiwand.com/en/Interval_tree
  34  */
  35
  36 struct _wmem_tree_t;
  37 typedef struct _wmem_tree_t wmem_itree_t;
  38
  39 struct _wmem_range_t {
  40     uint64_t low;        /* low is used as the key in the binary tree */
  41     uint64_t high;       /* Max value of the range */
  42     uint64_t max_edge;   /* max value among subtrees */
  43 };
  44
  45 WS_DLL_PUBLIC
  46 wmem_itree_t *
  47 wmem_itree_new(wmem_allocator_t *allocator)
  48 G_GNUC_MALLOC;
  49
  50
  51 /** Returns true if the tree is empty (has no nodes). */
  52 WS_DLL_PUBLIC
  53 bool
  54 wmem_itree_is_empty(wmem_itree_t *tree);
  55
  56
  57 /** Inserts a range low-high indexed by "low" in O(log(n)).
  58  * As in wmem_tree, if a key "low" already exists, it will be overwritten with the new data
  59  *
  60  */
  61 WS_DLL_PUBLIC
  62 void
  63 wmem_itree_insert(wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data);
  64
  65
  66 /*
  67  * Save results in a wmem_list with the scope passed as a parameter.
  68  * wmem_list_t is always allocated even if there is no result
  69  */
  70 WS_DLL_PUBLIC
  71 wmem_list_t *
  72 wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high);
  73
  74
  75 /**
  76  * Print ranges along the tree
  77  */
  78 void
  79 wmem_print_itree(wmem_itree_t *tree);
  80
  81 /**   @}
  82  *  @} */
  83
  84 #ifdef __cplusplus
  85 }
  86 #endif /* __cplusplus */
  87
  88 #endif /* __WMEM_INTERVAL_TREE_H__ */
  89
  90 /*
  91  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
  92  *
  93  * Local variables:
  94  * c-basic-offset: 4
  95  * tab-width: 8
  96  * indent-tabs-mode: nil
  97  * End:
  98  *
  99  * vi: set shiftwidth=4 tabstop=8 expandtab:
 100  * :indentSize=4:tabSize=8:noTabs=true:
 101  */