]> git.ipfire.org Git - thirdparty/suricata.git/commit
interval-tree: add augmentation fns to the tree
authorShivani Bhardwaj <shivani@oisf.net>
Mon, 29 Jan 2024 06:08:51 +0000 (11:38 +0530)
committerVictor Julien <victor@inliniac.net>
Fri, 24 May 2024 17:11:03 +0000 (19:11 +0200)
commite39948558a5d24fbc6dfa53228d5a7fd6368e648
tree9167baa31ed571fb52fd5620aac6a1bacf046562
parentc6b7cb98168ca46d9d9fff9b2d70466bab62f8ea
interval-tree: add augmentation fns to the tree

An interval tree uses red-black tree as its base data structure and
follows all the properties of a usual red-black tree. The additional
params are:
1. An interval such as [low, high] per node.
2. A max attribute per node. This attribute stores the maximum high
   value of any subtree rooted at this node.

At any point in time, an inorder traversal of an interval tree should
give the port ranges sorted by the low key in ascending order.

This commit modifies the IRB_AUGMENT macro and it's call sites to make
sure that on every insertion, the max attribute of the tree is properly
updated.

Ticket 6792
Bug 6414

(cherry picked from commit d36d03a4289e03b61cdd3617607bf0df1ce4d706)
src/Makefile.am
src/interval-tree.h