This is an automated email from the ASF dual-hosted git repository.
bnolsen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 675816d46d Add mark_bulk() method to lib/swoc to rebuild the RBTree in
one operation (#12055)
675816d46d is described below
commit 675816d46db085a51d439889ab7b73ab62c0f496
Author: edefend <[email protected]>
AuthorDate: Fri Mar 7 07:06:18 2025 -0600
Add mark_bulk() method to lib/swoc to rebuild the RBTree in one operation
(#12055)
* 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.
* Remove trailing whitespace
* - Fix issue with unsorted input to mark_bulk()
- mark_bulk() now sorts the input unless specified
- mark_bulk() now validates that it can skip updating the RBTree
* Rename isSorted -> is_sorted
* Move iostream to RBTree.cc
* Include <algorithm> for GNU 14
* Include string in RBTree.h
---------
Co-authored-by: bneradt <[email protected]>
---
lib/swoc/CMakeLists.txt | 7 +-
lib/swoc/include/swoc/DiscreteRange.h | 220 ++++++++++++++++++-------
lib/swoc/include/swoc/IPRange.h | 52 ++++++
lib/swoc/include/swoc/RBTree.h | 30 +++-
lib/swoc/src/RBTree.cc | 101 +++++++++++-
lib/swoc/unit_tests/test_ip.cc | 294 ++++++++++++++++++++++++++++++++++
6 files changed, 639 insertions(+), 65 deletions(-)
diff --git a/lib/swoc/CMakeLists.txt b/lib/swoc/CMakeLists.txt
index a60e1acf28..0a23f6506a 100644
--- a/lib/swoc/CMakeLists.txt
+++ b/lib/swoc/CMakeLists.txt
@@ -89,6 +89,11 @@ if(CMAKE_COMPILER_IS_GNUCXX)
)
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}
PUBLIC_HEADER "${HEADER_FILES}"
@@ -116,7 +121,7 @@ target_include_directories(
libswoc PUBLIC $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/include>
$<INSTALL_INTERFACE:include>
)
-# 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)
diff --git a/lib/swoc/include/swoc/DiscreteRange.h
b/lib/swoc/include/swoc/DiscreteRange.h
index 7becebf710..c223c2d9fc 100644
--- a/lib/swoc/include/swoc/DiscreteRange.h
+++ b/lib/swoc/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/lib/swoc/include/swoc/IPRange.h b/lib/swoc/include/swoc/IPRange.h
index b09b879fc2..cdcf5b7095 100644
--- a/lib/swoc/include/swoc/IPRange.h
+++ b/lib/swoc/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/lib/swoc/include/swoc/RBTree.h b/lib/swoc/include/swoc/RBTree.h
index 2594e6f425..26bc32f961 100644
--- a/lib/swoc/include/swoc/RBTree.h
+++ b/lib/swoc/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/lib/swoc/src/RBTree.cc b/lib/swoc/src/RBTree.cc
index 1697284c20..aefaf83e14 100644
--- a/lib/swoc/src/RBTree.cc
+++ b/lib/swoc/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/lib/swoc/unit_tests/test_ip.cc b/lib/swoc/unit_tests/test_ip.cc
index c25b88150e..8cfb9fe9cb 100644
--- a/lib/swoc/unit_tests/test_ip.cc
+++ b/lib/swoc/unit_tests/test_ip.cc
@@ -2183,3 +2183,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);
+ }
+}
