This is an automated email from the ASF dual-hosted git repository.
bneradt pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver-libswoc.git
The following commit(s) were added to refs/heads/master by this push:
new 5674930 Add mark_bulk() method to rebuild the RBTree in one operation
5674930 is described below
commit 56749309477552e7ac5543795592a689608eebc1
Author: Brian Neradt <[email protected]>
AuthorDate: Wed Mar 12 22:13:05 2025 +0000
Add mark_bulk() method to rebuild the RBTree in one operation
Improves performance when many ip ranges need to be added to IPSpace at
once.
Also results in a better-balanced RB tree whenever many append operations
happen in succession.
---
code/CMakeLists.txt | 9 +-
code/include/swoc/DiscreteRange.h | 220 ++++++++++++++++++++--------
code/include/swoc/IPRange.h | 52 +++++++
code/include/swoc/RBTree.h | 30 +++-
code/src/RBTree.cc | 101 ++++++++++++-
doc/code/ip_networking.en.rst | 6 +
unit_tests/test_ip.cc | 294 ++++++++++++++++++++++++++++++++++++++
7 files changed, 646 insertions(+), 66 deletions(-)
diff --git a/code/CMakeLists.txt b/code/CMakeLists.txt
index 3d45873..6c06bea 100644
--- a/code/CMakeLists.txt
+++ b/code/CMakeLists.txt
@@ -65,6 +65,11 @@ if (CMAKE_COMPILER_IS_GNUCXX)
target_compile_options(libswoc PRIVATE -fPIC -Wall -Wextra -Werror
-Wnon-virtual-dtor -Wpedantic -Wshadow)
endif()
+# if BUILD_TESTING, then add a cpp defines for BUILD_TESTING
+if (BUILD_TESTING)
+ target_compile_definitions(libswoc PRIVATE BUILD_TESTING)
+endif()
+
add_library(libswoc-static STATIC ${CC_FILES})
set_target_properties(libswoc-static PROPERTIES OUTPUT_NAME
swoc-static-${LIBSWOC_VERSION})
if (CMAKE_COMPILER_IS_GNUCXX)
@@ -133,10 +138,10 @@ if (LIBSWOC_INSTALL)
)
endif()
-# Alledgedly this makes the targets "importable from the build directory" but
I see no evidence of that.
+# Allegedly this makes the targets "importable from the build directory" but I
see no evidence of that.
# AFAICT the file isn't created at all even with this enabled.
#export(TARGETS libswoc FILE libswoc-config.cmake)
-set(CLANG_DIRS )
+set(CLANG_DIRS)
set_target_properties(libswoc-static PROPERTIES CLANG_FORMAT_DIRS
"${PROJECT_SOURCE_DIR}/src;${PROJECT_SOURCE_DIR}/include")
diff --git a/code/include/swoc/DiscreteRange.h
b/code/include/swoc/DiscreteRange.h
index 7becebf..c223c2d 100644
--- a/code/include/swoc/DiscreteRange.h
+++ b/code/include/swoc/DiscreteRange.h
@@ -8,6 +8,7 @@
*/
#pragma once
+#include <algorithm>
#include <limits>
#include <functional>
@@ -16,6 +17,7 @@
#include "swoc/RBTree.h"
#include "swoc/MemArena.h"
+
namespace swoc { inline namespace SWOC_VERSION_NS {
namespace detail {
@@ -717,7 +719,7 @@ protected:
using super_type = detail::RBNode; ///< Parent class.
friend class DiscreteSpace;
- range_type _range; ///< Range covered by this node.
+ range_type _range; ///< Range covered by this node (in the
IntrusiveDList).
range_type _hull; ///< Range covered by subtree rooted at this node.
PAYLOAD _payload{}; ///< Default constructor, should zero init if @c
PAYLOAD is a pointer.
@@ -756,16 +758,22 @@ protected:
}
self_type &
- assign_min(METRIC const &m) {
+ assign_min(METRIC const &m, bool update_tree = true) {
_range.assign_min(m);
- this->ripple_structure_fixup();
+ if (update_tree)
+ {
+ this->ripple_structure_fixup();
+ }
return *this;
}
self_type &
- assign_max(METRIC const &m) {
+ assign_max(METRIC const &m, bool update_tree = true) {
_range.assign_max(m);
- this->ripple_structure_fixup();
+ if (update_tree)
+ {
+ this->ripple_structure_fixup();
+ }
return *this;
}
@@ -828,15 +836,33 @@ public:
~DiscreteSpace();
+ /** Mark ranges in one operation.
+ *
+ * @param marks Vector of ranges and payloads to mark.
+ * @param is_sorted @c true if input is sorted, @c false if not. Assumes not
sorted.
+ * @return @a this
+ */
+ self_type &mark_bulk(std::vector<std::pair<range_type, PAYLOAD>> &marks,
bool is_sorted = false);
+
+ /** Mark ranges in one operation.
+ *
+ * @param start Pointer to the first range/payload pair.
+ * @param n Number of pairs.
+ * @param is_sorted @c true if input is sorted, @c false if not. Assumes
not sorted.
+ * @return @a this
+ */
+ self_type &mark_bulk(std::pair<range_type, PAYLOAD>* start, size_t n, bool
is_sorted = false);
+
/** Set the @a payload for a @a range
*
* @param range Range to mark.
* @param payload Payload to set.
+ * @param update_tree @c true to update the RBTree structure.
* @return @a this
*
* Values in @a range are set to @a payload regardless of the current state.
*/
- self_type &mark(range_type const &range, PAYLOAD const &payload);
+ self_type &mark(range_type const &range, PAYLOAD const &payload, bool
update_tree = true);
/** Erase a @a range.
*
@@ -972,37 +998,42 @@ protected:
*
* @param spot Target node.
* @param node Node to insert.
+ * @param update_tree @c true to update the RBTree structure.
*/
- void insert_before(Node *spot, Node *node);
+ void insert_before(Node *spot, Node *node, bool update_tree = true);
/** Insert @a node after @a spot.
*
* @param spot Target node.
* @param node Node to insert.
+ * @param update_tree @c true to update the RBTree structure.
*/
- void insert_after(Node *spot, Node *node);
+ void insert_after(Node *spot, Node *node, bool update_tree = true);
/** Add @a node to tree as the first element.
*
* @param node Node to prepend.
+ * @param update_tree @c true to update the RBTree structure.
*
* Invariant - @a node is first in order.
*/
- void prepend(Node *node);
+ void prepend(Node *node, bool update_tree = true);
/** Add @a node to tree as the last node.
*
* @param node Node to append.
+ * @param update_tree @c true to update the RBTree structure.
*
* Invariant - @a node is last in order.
*/
- void append(Node *node);
+ void append(Node *node, bool update_tree = true);
/** Remove node from container and update container.
*
* @param node Node to remove.
+ * @param update_tree @c true to update the RBTree structure.
*/
- void remove(Node *node);
+ void remove(Node *node, bool update_tree = true);
};
// ---
@@ -1210,65 +1241,88 @@ DiscreteSpace<METRIC,
PAYLOAD>::intersection(DiscreteSpace::range_type const &ra
template <typename METRIC, typename PAYLOAD>
void
-DiscreteSpace<METRIC, PAYLOAD>::prepend(DiscreteSpace::Node *node) {
- if (!_root) {
- _root = node;
- } else {
- _root = static_cast<Node *>(_list.head()->set_child(node,
Direction::LEFT)->rebalance_after_insert());
+DiscreteSpace<METRIC, PAYLOAD>::prepend(DiscreteSpace::Node *node, bool
update_tree) {
+
+ if (update_tree) {
+ if (!_root) {
+ _root = node;
+ } else {
+ _root = static_cast<Node *>(_list.head()->set_child(node,
Direction::LEFT)->rebalance_after_insert());
+ }
}
+
_list.prepend(node);
}
template <typename METRIC, typename PAYLOAD>
void
-DiscreteSpace<METRIC, PAYLOAD>::append(DiscreteSpace::Node *node) {
- if (!_root) {
- _root = node;
- } else {
- // The last node has no right child, or it wouldn't be the last.
- _root = static_cast<Node *>(_list.tail()->set_child(node,
Direction::RIGHT)->rebalance_after_insert());
+DiscreteSpace<METRIC, PAYLOAD>::append(DiscreteSpace::Node *node, bool
update_tree) {
+
+ if (update_tree) {
+ if (!_root) {
+ _root = node;
+ } else {
+ // The last node has no right child, or it wouldn't be the last.
+ _root = static_cast<Node *>(_list.tail()->set_child(node,
Direction::RIGHT)->rebalance_after_insert());
+ }
}
+
_list.append(node);
}
template <typename METRIC, typename PAYLOAD>
void
-DiscreteSpace<METRIC, PAYLOAD>::remove(DiscreteSpace::Node *node) {
- _root = static_cast<Node *>(node->remove());
+DiscreteSpace<METRIC, PAYLOAD>::remove(DiscreteSpace::Node *node, bool
update_tree) {
_list.erase(node);
_fa.destroy(node);
+ if (!update_tree) {
+ return;
+ }
+ _root = static_cast<Node *>(node->remove());
}
template <typename METRIC, typename PAYLOAD>
void
-DiscreteSpace<METRIC, PAYLOAD>::insert_before(DiscreteSpace::Node *spot,
DiscreteSpace::Node *node) {
- if (left(spot) == nullptr) {
- spot->set_child(node, Direction::LEFT);
- } else {
- // If there's a left child, there's a previous node, therefore spot->_prev
is valid.
- // Further, the previous node must be the rightmost descendant node of the
left subtree
- // and therefore has no current right child.
- spot->_prev->set_child(node, Direction::RIGHT);
+DiscreteSpace<METRIC, PAYLOAD>::insert_before(DiscreteSpace::Node *spot,
DiscreteSpace::Node *node, bool update_tree) {
+
+ if (update_tree) {
+ if (left(spot) == nullptr) {
+ spot->set_child(node, Direction::LEFT);
+ } else {
+ // If there's a left child, there's a previous node, therefore
spot->_prev is valid.
+ // Further, the previous node must be the rightmost descendant node of
the left subtree
+ // and therefore has no current right child.
+ spot->_prev->set_child(node, Direction::RIGHT);
+ }
}
_list.insert_before(spot, node);
- _root = static_cast<Node *>(node->rebalance_after_insert());
+
+ if (update_tree) {
+ _root = static_cast<Node *>(node->rebalance_after_insert());
+ }
}
template <typename METRIC, typename PAYLOAD>
void
-DiscreteSpace<METRIC, PAYLOAD>::insert_after(DiscreteSpace::Node *spot,
DiscreteSpace::Node *node) {
- if (right(spot) == nullptr) {
- spot->set_child(node, Direction::RIGHT);
- } else {
- // If there's a right child, there's a successor node, and therefore @a
_next is valid.
- // Further, the successor node must be the left most descendant of the
right subtree
- // therefore it doesn't have a left child.
- spot->_next->set_child(node, Direction::LEFT);
+DiscreteSpace<METRIC, PAYLOAD>::insert_after(DiscreteSpace::Node *spot,
DiscreteSpace::Node *node, bool update_tree) {
+
+ if (update_tree) {
+ if (right(spot) == nullptr) {
+ spot->set_child(node, Direction::RIGHT);
+ } else {
+ // If there's a right child, there's a successor node, and therefore @a
_next is valid.
+ // Further, the successor node must be the left most descendant of the
right subtree
+ // therefore it doesn't have a left child.
+ spot->_next->set_child(node, Direction::LEFT);
+ }
}
_list.insert_after(spot, node);
- _root = static_cast<Node *>(node->rebalance_after_insert());
+
+ if (update_tree) {
+ _root = static_cast<Node *>(node->rebalance_after_insert());
+ }
}
template <typename METRIC, typename PAYLOAD>
@@ -1304,7 +1358,47 @@ DiscreteSpace<METRIC,
PAYLOAD>::erase(DiscreteSpace::range_type const &range) {
template <typename METRIC, typename PAYLOAD>
DiscreteSpace<METRIC, PAYLOAD> &
-DiscreteSpace<METRIC, PAYLOAD>::mark(DiscreteSpace::range_type const &range,
PAYLOAD const &payload) {
+DiscreteSpace<METRIC,
PAYLOAD>::mark_bulk(std::vector<std::pair<DiscreteSpace::range_type, PAYLOAD>>
&ranges, bool is_sorted) {
+ return this->mark_bulk(ranges.data(), ranges.size(), is_sorted);
+}
+
+template <typename METRIC, typename PAYLOAD>
+DiscreteSpace<METRIC, PAYLOAD> &
+DiscreteSpace<METRIC, PAYLOAD>::mark_bulk(std::pair<range_type, PAYLOAD>*
start, size_t n, bool is_sorted)
+{
+ // Sort the input data in-place before processing, if applicable.
+ if (!is_sorted)
+ {
+ // Stable sort allows for duplicate elements.
+ std::stable_sort(start, start + n, [](const auto &lhs, const auto &rhs) {
+ if (lhs.first.min() != rhs.first.min()) {
+ return lhs.first.min() < rhs.first.min();
+ }
+ return lhs.first.max() < rhs.first.max();
+ });
+ }
+
+ // Verify that this is purely an append operation.
+ // If it's not, then we need to rebuild the entire tree each iteration
(suboptimal case).
+ bool isAppend = !_list.empty() && _list.tail()->max() < start[0].first.min();
+
+ // Mark the ranges in the input data.
+ for (size_t i = 0; i < n; ++i)
+ {
+ auto const& [range, payload] = start[i];
+ this->mark(range, payload, !isAppend);
+ }
+
+ // Rebuild the entire red-black tree.
+ detail::RBNode* temp_head = _list.head();
+ _root = static_cast<Node *>(detail::RBNode::buildTree(temp_head,
_list.count()));
+
+ return *this;
+}
+
+template <typename METRIC, typename PAYLOAD>
+DiscreteSpace<METRIC, PAYLOAD> &
+DiscreteSpace<METRIC, PAYLOAD>::mark(DiscreteSpace::range_type const &range,
PAYLOAD const &payload, bool update_tree) {
Node *n = this->lower_node(range.min()); // current node.
Node *x = nullptr; // New node, gets set if we re-use
an existing one.
Node *y = nullptr; // Temporary for removing and
advancing.
@@ -1326,7 +1420,7 @@ DiscreteSpace<METRIC,
PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAY
if (p && p->payload() == payload && p->max() == min_minus_1) {
x = p;
n = x; // need to back up n because frame of reference moved.
- x->assign_max(range.max());
+ x->assign_max(range.max(), update_tree);
} else if (n->max() <= range.max()) {
// Span will be subsumed by request span so it's available for use.
x = n;
@@ -1336,8 +1430,8 @@ DiscreteSpace<METRIC,
PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAY
} else {
// request span is covered by existing span.
x = _fa.make(range, payload); //
- n->assign_min(max_plus_1); // clip existing.
- this->insert_before(n, x);
+ n->assign_min(max_plus_1, update_tree); // clip existing.
+ this->insert_before(n, x, update_tree);
return *this;
}
} else if (n->payload() == payload && n->max() >= min_minus_1) {
@@ -1347,18 +1441,22 @@ DiscreteSpace<METRIC,
PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAY
if (x->max() >= range.max()) {
return *this;
}
- x->assign_max(range.max());
+ x->assign_max(range.max(), update_tree);
} else if (n->max() <= range.max()) {
// Can only have left skew overlap, otherwise disjoint.
// Clip if overlap.
if (n->max() >= range.min()) {
- n->assign_max(min_minus_1);
+ n->assign_max(min_minus_1, update_tree);
} else if (nullptr != (y = next(n)) && y->max() <= range.max()) {
// because @a n was selected as the minimum it must be the case that
// y->min >= min (or y would have been selected). Therefore in this
// case the request covers the next node therefore it can be reused.
x = y;
- x->assign(range).assign(payload).ripple_structure_fixup();
+ x->assign(range).assign(payload);
+ if (update_tree)
+ {
+ x->ripple_structure_fixup();
+ }
n = x; // this gets bumped again, which is correct.
}
} else {
@@ -1368,18 +1466,18 @@ DiscreteSpace<METRIC,
PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAY
Node *r;
x = _fa.make(range, payload);
r = _fa.make(range_type{max_plus_1, n->max()}, n->payload());
- n->assign_max(min_minus_1);
- this->insert_after(n, x);
- this->insert_after(x, r);
+ n->assign_max(min_minus_1, update_tree);
+ this->insert_after(n, x, update_tree);
+ this->insert_after(x, r, update_tree);
return *this; // done.
}
n = next(n); // lower bound span handled, move on.
if (!x) {
x = _fa.make(range, payload);
if (n) {
- this->insert_before(n, x);
+ this->insert_before(n, x, update_tree);
} else {
- this->append(x); // note that since n == 0 we'll just return.
+ this->append(x, update_tree); // note that since n == 0 we'll just
return.
}
}
} else if (nullptr != (n = this->head()) && // at least
one node in tree.
@@ -1389,13 +1487,13 @@ DiscreteSpace<METRIC,
PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAY
// Same payload with overlap, re-use.
x = n;
n = next(n);
- x->assign_min(range.min());
+ x->assign_min(range.min(), update_tree);
if (x->max() < range.max()) {
- x->assign_max(range.max());
+ x->assign_max(range.max(), update_tree);
}
} else {
x = _fa.make(range, payload);
- this->prepend(x);
+ this->prepend(x, update_tree);
}
// At this point, @a x has the node for this span and all existing spans of
@@ -1404,16 +1502,16 @@ DiscreteSpace<METRIC,
PAYLOAD>::mark(DiscreteSpace::range_type const &range, PAY
if (n->max() <= range.max()) { // completely covered, drop span, continue
y = n;
n = next(n);
- this->remove(y);
+ this->remove(y, update_tree);
} else if (max_plus_1 < n->min()) { // no overlap, done.
break;
} else if (n->payload() == payload) { // skew overlap or adj., same payload
- x->assign_max(n->max());
+ x->assign_max(n->max(), update_tree);
y = n;
n = next(n);
- this->remove(y);
+ this->remove(y, update_tree);
} else if (n->min() <= range.max()) { // skew overlap different payload
- n->assign_min(max_plus_1);
+ n->assign_min(max_plus_1, update_tree);
break;
} else { // n->min() > range.max(), different payloads - done.
break;
diff --git a/code/include/swoc/IPRange.h b/code/include/swoc/IPRange.h
index b09b879..cdcf5b7 100644
--- a/code/include/swoc/IPRange.h
+++ b/code/include/swoc/IPRange.h
@@ -1137,6 +1137,30 @@ public:
*/
self_type &mark(IPRange const &range, PAYLOAD const &payload);
+ /** Mark ranges of IP4Addr in the IPSpace in one operation.
+ *
+ * @param range_payloads Array of range/payload pairs.
+ * @param size Number of elements in @a range_payloads.
+ * @param is_sorted @c true if input is sorted, @c false if not. Assumes not
sorted.
+ * @return @a this
+ */
+ self_type &mark_bulk(std::pair<DiscreteRange<IP4Addr>, PAYLOAD>*
range_payloads, size_t size, bool is_sorted = false);
+
+ //! vector-based interface for the previous function.
+ self_type &mark_bulk(std::vector<std::pair<DiscreteRange<IP4Addr>,
PAYLOAD>>& range_payloads, bool is_sorted = false);
+
+ /** Mark ranges of IP6Addr in the IPSpace in one operation.
+ *
+ * @param range_payloads Array of range/payload pairs.
+ * @param size Number of elements in @a range_payloads.
+ * @param is_sorted @c true if input is sorted, @c false if not. Assumes
not sorted.
+ * @return @a this
+ */
+ self_type &mark_bulk(std::pair<DiscreteRange<IP6Addr>, PAYLOAD>*
range_payloads, size_t size, bool is_sorted = false);
+
+ //! vector-based interface for the previous function.
+ self_type &mark_bulk(std::vector<std::pair<DiscreteRange<IP6Addr>,
PAYLOAD>>& range_payloads, bool is_sorted = false);
+
/** Fill the @a range with @a payload.
*
* @param range Destination range.
@@ -2464,6 +2488,34 @@ IPRange::NetSource::operator!=(self_type const &that)
const {
// --- IPSpace
+template <typename PAYLOAD>
+auto
+IPSpace<PAYLOAD>::mark_bulk(std::pair<DiscreteRange<IP4Addr>, PAYLOAD>*
range_payloads, size_t size, bool is_sorted) -> self_type & {
+ _ip4.mark_bulk(range_payloads, size, is_sorted);
+ return *this;
+}
+
+template <typename PAYLOAD>
+auto
+IPSpace<PAYLOAD>::mark_bulk(std::pair<DiscreteRange<IP6Addr>, PAYLOAD>*
range_payloads, size_t size, bool is_sorted) -> self_type & {
+ _ip6.mark_bulk(range_payloads, size, is_sorted);
+ return *this;
+}
+
+template <typename PAYLOAD>
+auto
+IPSpace<PAYLOAD>::mark_bulk(std::vector<std::pair<DiscreteRange<IP4Addr>,
PAYLOAD>>& range_payloads, bool is_sorted) -> self_type & {
+ _ip4.mark_bulk(range_payloads, is_sorted);
+ return *this;
+}
+
+template <typename PAYLOAD>
+auto
+IPSpace<PAYLOAD>::mark_bulk(std::vector<std::pair<DiscreteRange<IP6Addr>,
PAYLOAD>>& range_payloads, bool is_sorted) -> self_type & {
+ _ip6.mark_bulk(range_payloads, is_sorted);
+ return *this;
+}
+
template <typename PAYLOAD>
auto
IPSpace<PAYLOAD>::mark(IPRange const &range, PAYLOAD const &payload) ->
self_type & {
diff --git a/code/include/swoc/RBTree.h b/code/include/swoc/RBTree.h
index 2594e6f..26bc32f 100644
--- a/code/include/swoc/RBTree.h
+++ b/code/include/swoc/RBTree.h
@@ -6,9 +6,12 @@
*/
#pragma once
+
#include "swoc/swoc_version.h"
#include "swoc/IntrusiveDList.h"
+#include <string>
+
namespace swoc { inline namespace SWOC_VERSION_NS { namespace detail {
/** A node in a red/black tree.
@@ -174,6 +177,31 @@ struct RBNode {
*/
self_type *ripple_structure_fixup();
+ /**
+ * @brief Recursively build a balanced RB tree from a sorted linked list.
+ *
+ * Constraints:
+ * - The list is sorted in ascending order.
+ * - A copy (not reference) of the head pointer is passed in.
+ *
+ * @param head Copy of the head pointer of the list.
+ * @param n Number of nodes being processed at the current level.
+ * @return self_type* The root node of the tree.
+ */
+ static self_type * buildTree(self_type*& head, int n);
+
+ //! Called by buildTree above.
+ static self_type * buildTree(self_type*& head, int n, bool isBlack);
+
+ /**
+ * @brief Recursively print the tree in a human-readable format.
+ *
+ * @param root Root node of the tree.
+ * @param indent Indentation string.
+ * @param last Flag to indicate if the node is the last node.
+ */
+ static void printTree(self_type* root, std::string indent = "", bool last =
true);
+
Color _color{Color::RED}; ///< node color
self_type *_parent{nullptr}; ///< parent node (needed for rotations)
self_type *_left{nullptr}; ///< left child
@@ -188,7 +216,7 @@ struct RBNode {
next_ptr(self_type *t) {
return swoc::ptr_ref_cast<self_type>(t->_next);
}
- /// @return Reference to the internal pointer to the previoius element.
+ /// @return Reference to the internal pointer to the previous element.
static self_type *&
prev_ptr(self_type *t) {
return swoc::ptr_ref_cast<self_type>(t->_prev);
diff --git a/code/src/RBTree.cc b/code/src/RBTree.cc
index 1697284..aefaf83 100644
--- a/code/src/RBTree.cc
+++ b/code/src/RBTree.cc
@@ -7,6 +7,8 @@
#include "swoc/RBTree.h"
+#include <iostream>
+
namespace swoc { inline namespace SWOC_VERSION_NS { namespace detail {
// These equality operators are only used in this file.
@@ -293,13 +295,108 @@ RBNode::rebalance_after_remove(Color c, //!< The
color of the removed node
return root;
}
+RBNode *
+RBNode::buildTree(RBNode*& head, int n)
+{
+ if (!head || n <= 0)
+ {
+ return head;
+ }
+ RBNode* root = buildTree(head, n, true);
+
+ // The root node is always black.
+ root->_color = Color::BLACK;
+
+ return root;
+}
+
+RBNode *
+RBNode::buildTree(RBNode*& head, int n, bool isBlack)
+{
+ if (n <= 1)
+ {
+ RBNode* currNode = head;
+ currNode->_color = isBlack ? Color::BLACK : Color::RED;
+ head = head->_next;
+ currNode->structure_fixup();
+ return currNode;
+ }
+
+ // Always handle the even number of nodes first because it is guaranteed
to contain an n == 2 case.
+ int left_n = n / 2;
+ int right_n = n - left_n - 1;
+ if (right_n % 2 == 0)
+ {
+ std::swap(left_n, right_n);
+ }
+
+ // Recursively construct the left subtree.
+ RBNode* leftBranch = buildTree(head, left_n, !isBlack);
+
+ // Assign the left branch to the current node (head).
+ RBNode* currNode = head;
+ currNode->_left = leftBranch;
+
+ // This can be nullptr if we are at the end.
+ head = head->_next;
+
+ // If this is currently processing 2 nodes, then don't make a right branch
+ // because the left branch has already been made.
+ // No need to check for head == nullptr here because n > 2 inside the
block.
+ if (n != 2)
+ {
+ // Recursively construct the right subtree.
+ currNode->_right = buildTree(head, right_n, leftBranch->_color ==
Color::BLACK);
+ }
+ // If you have an n == 2 case, there is only a left child and it must be
red.
+ else
+ {
+ currNode->_left->_color = Color::RED;
+ currNode->_color = Color::BLACK;
+ }
+
+ // If either child is red, then the current node must be black.
+ if (currNode->_left->_color == Color::RED || currNode->_right->_color ==
Color::RED)
+ {
+ currNode->_color = Color::BLACK;
+ }
+
+ // structure_fixup() needs to be called from the leaf nodes upward.
+ currNode->structure_fixup();
+
+ return currNode;
+}
+
+void
+RBNode::printTree(RBNode* root, std::string indent, bool last)
+{
+ if (root == nullptr) {
+ return;
+ }
+ std::cout << indent;
+ if (last) {
+ std::cout << "└─";
+ indent += " ";
+ } else {
+ std::cout << "├─";
+ indent += "| ";
+ }
+
+ std::string color = (root->_color == Color::RED) ? "R" : "B";
+ std::cout << color << std::endl;
+
+ last = root->_right == nullptr;
+ printTree(root->_left, indent, last);
+ printTree(root->_right, indent, true);
+}
+
/** Ensure that the local information associated with each node is
correct globally This should only be called on debug builds as it
breaks any efficiencies we have gained from our tree structure.
*/
int
RBNode::validate() {
-#if 0
+#if BUILD_TESTING
int black_ht = 0;
int black_ht1, black_ht2;
@@ -329,7 +426,7 @@ RBNode::validate() {
} else {
std::cout << "Height mismatch " << black_ht1 << " " << black_ht2 << "\n";
}
- if (black_ht > 0 && !this->structureValidate())
+ if (black_ht > 0 && !this->structure_validate())
black_ht = 0;
return black_ht;
diff --git a/doc/code/ip_networking.en.rst b/doc/code/ip_networking.en.rst
index d6a7988..683ee0a 100644
--- a/doc/code/ip_networking.en.rst
+++ b/doc/code/ip_networking.en.rst
@@ -194,6 +194,12 @@ mark
payload present. This is modeled on the "painter's algorithm" where the
most recent coloring
replaces any prior colors in the region.
+mark_bulk
+ :libswoc:`swoc::IPSpace::mark_bulk` applies multiple :arg:`payload` to the
range using the same
+ logic as :code:`mark`. This has much better performance than calling
:code:`mark` many times in
+ succession, and results in a much more balanced RBTree structure (for
faster lookups) in the case
+ where ip ranges are inserted in ascending order.
+
fill
:libswoc:`swoc::IPSpace::fill` applies the :arg:`payload` to the range but
only where there is not
already a payload. This is modeled on "backfilling" a background. This is
useful for "first match"
diff --git a/unit_tests/test_ip.cc b/unit_tests/test_ip.cc
index 35e25b1..9737aca 100644
--- a/unit_tests/test_ip.cc
+++ b/unit_tests/test_ip.cc
@@ -2182,3 +2182,297 @@ TEST_CASE("IPRangeSet", "[libswoc][iprangeset]") {
REQUIRE(n == addrs.count());
REQUIRE(valid_p);
}
+
+TEST_CASE("IPSpace mark_bulk", "[libswoc][ipspace][mark_bulk]") {
+ using PAYLOAD = unsigned;
+ using Space = swoc::IPSpace<PAYLOAD>;
+
+ Space space;
+
+ // #1 mark_bulk() onto an empty space
+ // Verify that it collapses ranges with the same payload
+ // Use (currPayload++) / 2 as the payload value in order to collapse
every-other ip range.
+
+ unsigned currPayload = 0;
+ std::vector<std::pair<swoc::DiscreteRange<IP4Addr>, PAYLOAD>> addrs4;
+ std::vector<std::pair<swoc::DiscreteRange<IP6Addr>, PAYLOAD>> addrs6;
+
+ // 1.1.1.1 - 1.1.1.254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs4.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.1." +
std::to_string(i)},
+ IP4Addr{"1.1.1." +
std::to_string(i + 1)}},
+ (currPayload++) / 2);
+ }
+
+ // ::1 - ::254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs6.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::" +
std::to_string(i)},
+ IP6Addr{"::" +
std::to_string(i + 1)}},
+ (currPayload++) / 2);
+ }
+
+ // Verify successful mark_bulk
+ space.mark_bulk(addrs4.data(), addrs4.size(), false);
+ space.mark_bulk(addrs6.data(), addrs6.size(), true);
+
+ // Verify that the count is correct
+ REQUIRE(space.count() == (addrs4.size() + addrs6.size()) / 2);
+
+ // Verify that the payloads are correct
+ for (auto const& [range, payload] : addrs4) {
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+
+ for (auto const& [range, payload] : addrs6) {
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(ip6));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+
+ // #2 mark_bulk() onto the end of the existing space
+ addrs4.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.2.1"},
+ IP4Addr{"1.1.2.255"}},
+ currPayload++);
+ addrs4.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.3.1"},
+ IP4Addr{"1.1.3.255"}},
+ currPayload++);
+
+ addrs6.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::1:1"},
+ IP6Addr{"::1:255"}},
+ currPayload++);
+ addrs6.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::2:1"},
+ IP6Addr{"::2:255"}},
+ currPayload++);
+
+ // Verify successful mark_bulk
+ space.mark_bulk(addrs4, true);
+ space.mark_bulk(addrs6, false);
+
+ // Verify that the payloads are correct
+ for (auto const& [range, payload] : addrs4) {
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+
+ for (auto const& [range, payload] : addrs6) {
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(ip6));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+
+ // #3 Insert ranges into the middle of an existing range
+
+ std::vector<std::pair<swoc::DiscreteRange<IP4Addr>, PAYLOAD>> insert4;
+ std::vector<std::pair<swoc::DiscreteRange<IP6Addr>, PAYLOAD>> insert6;
+
+ insert4.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.2.10"},
+ IP4Addr{"1.1.2.20"}},
+ currPayload++);
+
+ insert6.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::1:10"},
+ IP6Addr{"::1:20"}},
+ currPayload++);
+
+ space.mark_bulk(insert4.data(), insert4.size(), true);
+ space.mark_bulk(insert6, true);
+
+ // Verify that the ranges were split up.
+ {
+ auto [range, payload] = addrs4[addrs4.size() - 2];
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+ {
+ auto [range, payload] = insert4[0];
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+ {
+ auto [range, payload] = addrs4[addrs4.size() - 1];
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(range.min()));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+ {
+ auto [range, payload] = addrs6[addrs6.size() - 2];
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(ip6));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+ {
+ auto [range, payload] = insert6[0];
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(range.min()));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+ {
+ auto [range, payload] = addrs6[addrs6.size() - 1];
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(range.min()));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+
+}
+
+TEST_CASE("IPSpace mark_bulk randomized",
"[libswoc][ipspace][mark_bulk][randomized]") {
+ using PAYLOAD = unsigned;
+ using Space = swoc::IPSpace<PAYLOAD>;
+
+ Space space;
+
+ // #1 mark_bulk() onto an empty space
+ // Verify that it collapses ranges with the same payload
+ // Use (currPayload++) / 2 as the payload value in order to collapse
every-other ip range.
+
+ unsigned currPayload = 0;
+ std::vector<std::pair<swoc::DiscreteRange<IP4Addr>, PAYLOAD>> addrs4;
+ std::vector<std::pair<swoc::DiscreteRange<IP6Addr>, PAYLOAD>> addrs6;
+
+ // 1.1.1.1 - 1.1.1.254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs4.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.2." +
std::to_string(i)},
+ IP4Addr{"1.1.2." +
std::to_string(i + 1)}},
+ (currPayload++) / 2);
+ }
+
+ // ::1 - ::254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs6.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::1:" +
std::to_string(i)},
+ IP6Addr{"::1:" +
std::to_string(i + 1)}},
+ (currPayload++) / 2);
+ }
+
+ // Shuffle both vectors
+ std::random_device rd;
+ std::mt19937 rng(rd());
+ std::shuffle(addrs4.begin(), addrs4.end(), rng);
+ std::shuffle(addrs6.begin(), addrs6.end(), rng);
+
+ // Verify successful mark_bulk
+ space.mark_bulk(addrs4.data(), addrs4.size());
+ space.mark_bulk(addrs6.data(), addrs6.size());
+
+ // Verify that the count is correct
+ size_t size1 = (addrs4.size() + addrs6.size()) / 2;
+ REQUIRE(space.count() == size1);
+
+ // Verify that the payloads are correct
+ for (auto const& [range, payload] : addrs4) {
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+
+ for (auto const& [range, payload] : addrs6) {
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(ip6));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+
+ // Create another ip range after the previous
+ std::vector<std::pair<swoc::DiscreteRange<IP4Addr>, PAYLOAD>> addrs4_2;
+ std::vector<std::pair<swoc::DiscreteRange<IP6Addr>, PAYLOAD>> addrs6_2;
+
+ // 1.1.2.1 - 1.1.2.254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs4_2.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.3." +
std::to_string(i)},
+ IP4Addr{"1.1.3." +
std::to_string(i + 1)}},
+ (currPayload++));
+ }
+
+ // :1:1 - :1:254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs6_2.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::2:" +
std::to_string(i)},
+ IP6Addr{"::2:" +
std::to_string(i + 1)}},
+ (currPayload++));
+ }
+
+ // shuffle both
+ std::shuffle(addrs4_2.begin(), addrs4_2.end(), rng);
+ std::shuffle(addrs6_2.begin(), addrs6_2.end(), rng);
+
+ // Verify successful mark_bulk
+ space.mark_bulk(addrs4_2);
+ space.mark_bulk(addrs6_2);
+
+ // Verify that the count is correct
+ size_t size2 = addrs4_2.size() + addrs6_2.size();
+ REQUIRE(space.count() == size1 + size2);
+
+ // Verify that the payloads are correct
+ for (auto const& [range, payload] : addrs4_2) {
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+
+ for (auto const& [range, payload] : addrs6_2) {
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(ip6));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+
+ // Create another ip range before the previous two
+ std::vector<std::pair<swoc::DiscreteRange<IP4Addr>, PAYLOAD>> addrs4_3;
+ std::vector<std::pair<swoc::DiscreteRange<IP6Addr>, PAYLOAD>> addrs6_3;
+
+ // 1.1.2.1 - 1.1.2.254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs4_3.emplace_back(swoc::DiscreteRange<IP4Addr>{IP4Addr{"1.1.1." +
std::to_string(i)},
+ IP4Addr{"1.1.1." +
std::to_string(i + 1)}},
+ (currPayload++));
+ }
+
+ // :1:1 - :1:254, each range is length 1
+ for (int i = 1; i < 128; i += 2) {
+ addrs6_3.emplace_back(swoc::DiscreteRange<IP6Addr>{IP6Addr{"::" +
std::to_string(i)},
+ IP6Addr{"::" +
std::to_string(i + 1)}},
+ (currPayload++));
+ }
+
+ // shuffle both
+ std::shuffle(addrs4_3.begin(), addrs4_3.end(), rng);
+ std::shuffle(addrs6_3.begin(), addrs6_3.end(), rng);
+
+ // Verify successful mark_bulk
+ space.mark_bulk(addrs4_3);
+ space.mark_bulk(addrs6_3);
+
+ // Verify that the count is correct
+ size_t size3 = addrs4_3.size() + addrs6_3.size();
+ REQUIRE(space.count() == size1 + size2 + size3);
+
+ // Verify that the payloads are correct
+ for (auto const& [range, payload] : addrs4_3) {
+ IP4Addr ip4 = range.min();
+ auto [r, p] = *(space.find(ip4));
+ REQUIRE(r.contains(ip4));
+ REQUIRE(p == payload);
+ }
+
+ for (auto const& [range, payload] : addrs6_3) {
+ IP6Addr ip6 = range.min();
+ auto [r, p] = *(space.find(ip6));
+ REQUIRE(r.contains(ip6));
+ REQUIRE(p == payload);
+ }
+}
