wsutil/wmem/wmem_interval_tree.c

   1 /* wmem_interval_tree.c
   2  * Implements an augmented interval tree
   3  * Based on the red-black tree implementation in epan/wmem.*
   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
  13 #include "config.h"
  14
  15 #include <inttypes.h>
  16 #include <string.h>
  17 #include <inttypes.h>
  18 #include <stdio.h>
  19 #include <glib.h>
  20
  21 #include "wmem-int.h"
  22 #include "wmem_core.h"
  23 #include "wmem_tree-int.h"
  24 #include "wmem_strutl.h"
  25 #include "wmem_interval_tree.h"
  26 #include "wmem_user_cb.h"
  27
  28 static void
  29 print_range(const void *value)
  30 {
  31     const wmem_range_t *range = (const wmem_range_t *)value;
  32     if(!value) {
  33         return;
  34     }
  35     printf("Range: low=%" PRIu64 " high=%" PRIu64 " max_edge=%" PRIu64 "\n", range->low, range->high, range->max_edge);
  36 }
  37
  38 /**
  39  * In an augmented interval tree, each node saves the maximum edge of its child subtrees
  40  * This function compares the children max_edge with the current max_edge
  41  * and propagates any change to the parent nodes.
  42  */
  43 static void
  44 update_max_edge(wmem_tree_node_t *node)
  45 {
  46     wmem_range_t *range;
  47     const wmem_range_t *range_l;
  48     const wmem_range_t *range_r;
  49     uint64_t maxEdge = 0;
  50
  51     if(!node) {
  52         return ;
  53     }
  54
  55     range = (wmem_range_t *)node->key;
  56
  57     range_l = (node->left) ? (const wmem_range_t *) (node->left->key) : NULL;
  58     range_r = (node->right) ? (const wmem_range_t *) (node->right->key) : NULL;
  59
  60     maxEdge = range->high;
  61
  62     if(range_r) {
  63         maxEdge = MAX(maxEdge, range_r->max_edge) ;
  64     }
  65     if(range_l) {
  66         maxEdge = MAX(maxEdge, range_l->max_edge) ;
  67     }
  68
  69     /* update the parent nodes only if a change happened (optimization) */
  70     if(range->max_edge != maxEdge) {
  71         range->max_edge = maxEdge;
  72         update_max_edge(node->parent);
  73     }
  74 }
  75
  76 bool
  77 wmem_itree_range_overlap(const wmem_range_t *r1, const wmem_range_t *r2)
  78 {
  79     return (r1->low <= r2->high && r2->low <= r1->high);
  80 }
  81
  82
  83 /* after a rotation, some of the children nodes might (dis)appear, thus we need
  84  * to refresh children max_edge. Changes will propagate to parents */
  85 static void update_edges_after_rotation(wmem_tree_node_t *node) {
  86     if(node->left)  update_max_edge(node->left);
  87     if(node->right)  update_max_edge(node->right);
  88 }
  89
  90 wmem_itree_t *
  91 wmem_itree_new(wmem_allocator_t *allocator)
  92 {
  93     wmem_itree_t *tree      = wmem_tree_new(allocator);
  94     tree->post_rotation_cb  = &update_edges_after_rotation;
  95     return tree;
  96 }
  97
  98 bool
  99 wmem_itree_is_empty(wmem_itree_t *tree)
 100 {
 101     return wmem_tree_is_empty(tree);
 102 }
 103
 104 static int
 105 wmem_tree_compare_ranges(const wmem_range_t *ra, const wmem_range_t *rb)
 106 {
 107     if( ra->low == rb->low) {
 108         return 0;
 109     }
 110     else if(ra->low < rb->low) {
 111         return -1;
 112     }
 113     else {
 114         return 1;
 115     }
 116 }
 117
 118
 119 void
 120 wmem_itree_insert(wmem_itree_t *tree, const uint64_t low, const uint64_t high, void *data)
 121 {
 122     wmem_tree_node_t *node;
 123     wmem_range_t *range = (wmem_range_t *)wmem_new(tree->data_allocator, wmem_range_t);
 124
 125     ws_assert(low <= high);
 126     range->low = low;
 127     range->high = high;
 128     range->max_edge = 0;
 129
 130     node = wmem_tree_insert_node(tree, range, data, (compare_func)wmem_tree_compare_ranges);
 131
 132     /* in absence of rotation, we still need to update max_edge */
 133     update_max_edge(node);
 134 }
 135
 136
 137 static void
 138 wmem_itree_find_intervals_in_subtree(wmem_tree_node_t *node, wmem_range_t requested, wmem_list_t *results)
 139 {
 140     const wmem_range_t* current;
 141
 142     if(!node) {
 143         return;
 144     }
 145     current = (wmem_range_t*)node->key;
 146
 147     /* there is no child that can possibly match */
 148     if(requested.low > current->max_edge) {
 149         return;
 150     }
 151
 152     if(wmem_itree_range_overlap(current, &requested)) {
 153         wmem_list_prepend(results, node->data);
 154     }
 155
 156     wmem_itree_find_intervals_in_subtree(node->left, requested, results);
 157     wmem_itree_find_intervals_in_subtree(node->right, requested, results);
 158 }
 159
 160 wmem_list_t *
 161 wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, uint64_t low, uint64_t high)
 162 {
 163     wmem_list_t *results = NULL;
 164     wmem_range_t requested = { low, high, 0 };
 165     results = wmem_list_new(allocator);
 166
 167     wmem_itree_find_intervals_in_subtree(tree->root, requested, results);
 168     return results;
 169 }
 170
 171
 172 void
 173 wmem_print_itree(wmem_tree_t *tree)
 174 {
 175     wmem_print_tree(tree, &print_range, NULL);
 176 }
 177
 178 /*
 179  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 180  *
 181  * Local variables:
 182  * c-basic-offset: 4
 183  * tab-width: 8
 184  * indent-tabs-mode: nil
 185  * End:
 186  *
 187  * vi: set shiftwidth=4 tabstop=8 expandtab:
 188  * :indentSize=4:tabSize=8:noTabs=true:
 189  */