Loading...
Searching...
No Matches
intrusive_avl_tree.h
Go to the documentation of this file.
/******************************************************************************
The MIT License(MIT)
Embedded Template Library.
https://github.com/ETLCPP/etl
https://www.etlcpp.com
Copyright(c) 2026 Sergei Shirokov
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
******************************************************************************/
#ifndef ETL_INTRUSIVE_AVL_TREE_INCLUDED
#define ETL_INTRUSIVE_AVL_TREE_INCLUDED
#include "platform.h"
#include "error_handler.h"
#include "intrusive_links.h"
#include "iterator.h"
#include "memory.h"
#include "type_traits.h"
#include "utility.h"
#include <stddef.h>
namespace etl
{
//***************************************************************************
//***************************************************************************
class intrusive_avl_tree_exception : public exception
{
public:
intrusive_avl_tree_exception(const string_type reason_, const string_type file_name_, const numeric_type line_number_)
: exception(reason_, file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class intrusive_avl_tree_iterator_exception : public intrusive_avl_tree_exception
{
public:
intrusive_avl_tree_iterator_exception(const string_type file_name_, const numeric_type line_number_)
: intrusive_avl_tree_exception(ETL_ERROR_TEXT("intrusive_avl_tree:iterator", ETL_INTRUSIVE_AVL_TREE_FILE_ID "A"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class intrusive_avl_tree_value_is_already_linked : public intrusive_avl_tree_exception
{
public:
intrusive_avl_tree_value_is_already_linked(const string_type file_name_, const numeric_type line_number_)
: intrusive_avl_tree_exception(ETL_ERROR_TEXT("intrusive_avl_tree:value is already linked", ETL_INTRUSIVE_AVL_TREE_FILE_ID"B"), file_name_,
line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
template <size_t ID_>
class intrusive_avl_tree_base
{
public:
enum
{
ID = ID_,
};
#if ETL_USING_CPP11
intrusive_avl_tree_base(const intrusive_avl_tree_base&) = delete;
intrusive_avl_tree_base& operator=(const intrusive_avl_tree_base&) = delete;
#endif
struct link_type : private etl::tree_link<ID_>
{
private:
typedef etl::tree_link<ID_> base;
public:
link_type() ETL_NOEXCEPT
: base()
, etl_size(0)
{
}
#if ETL_USING_CPP11
//***************************************************************************
//***************************************************************************
link_type(link_type&& other) ETL_NOEXCEPT
: base()
, etl_size(0)
{
move_impl(other);
}
//***************************************************************************
//***************************************************************************
link_type& operator=(link_type&& other) ETL_NOEXCEPT
{
if (this != &other)
{
// Before move assigning `other` we have to
// make sure this item is not linked to any tree.
erase_impl(this);
move_impl(other);
}
return *this;
}
#endif
#if ETL_USING_CPP11
// Disable copy construction and assignment.
link_type(const link_type&) = delete;
link_type& operator=(const link_type&) = delete;
#endif
//***************************************************************************
//***************************************************************************
~link_type()
{
// We can't just remove item (by simple rewiring of links at parent and children)
// b/c its former "owner" tree has to be rebalanced after the removal -
// hence the full-blown erasing which might rotate the tree as necessary.
erase_impl(this);
}
private:
friend class intrusive_avl_tree_base;
union
{
int_fast8_t etl_bf;
size_t etl_size;
};
#if ETL_USING_CPP11
#else
// Disable copy construction and assignment.
link_type(const link_type&);
link_type& operator=(const link_type&);
#endif
ETL_NODISCARD
bool is_linked() const
{
return base::is_linked();
}
ETL_NODISCARD
bool is_origin() const
{
return ETL_NULLPTR == base::etl_parent;
}
#include "private/diagnostic_null_dereference_push.h"
ETL_NODISCARD
link_type* get_parent()
{
return static_cast<link_type*>(base::etl_parent);
}
#include "private/diagnostic_pop.h"
ETL_NODISCARD
const link_type* get_parent() const
{
return static_cast<const link_type*>(base::etl_parent);
}
ETL_NODISCARD
bool is_child(const bool is_right) const
{
const link_type* parent = get_parent();
return (ETL_NULLPTR != parent) && (this == parent->get_child(is_right));
}
ETL_NODISCARD
bool is_left_child() const
{
return is_child(false);
}
ETL_NODISCARD
bool is_right_child() const
{
return is_child(true);
}
ETL_NODISCARD
link_type* get_child(const bool is_right)
{
return static_cast<link_type*>(is_right ? base::etl_right : base::etl_left);
}
ETL_NODISCARD
const link_type* get_child(const bool is_right) const
{
return static_cast<const link_type*>(is_right ? base::etl_right : base::etl_left);
}
void set_child(link_type* const child, const bool is_right)
{
base*& child_ref = is_right ? base::etl_right : base::etl_left;
child_ref = child;
}
ETL_NODISCARD
link_type* get_left()
{
return static_cast<link_type*>(base::etl_left);
}
ETL_NODISCARD
const link_type* get_left() const
{
return static_cast<const link_type*>(base::etl_left);
}
ETL_NODISCARD
link_type* get_right()
{
return static_cast<link_type*>(base::etl_right);
}
ETL_NODISCARD
const link_type* get_right() const
{
return static_cast<const link_type*>(base::etl_right);
}
void move_impl(link_type& other)
{
const bool is_right = other.is_right_child();
base::etl_parent = other.etl_parent;
base::etl_left = other.etl_left;
base::etl_right = other.etl_right;
etl_size = other.etl_size;
other.clear();
other.etl_size = 0;
if (ETL_NULLPTR != base::etl_parent)
{
get_parent()->link_child(this, is_right);
}
if (ETL_NULLPTR != base::etl_left)
{
get_left()->set_parent(this);
}
if (ETL_NULLPTR != base::etl_right)
{
get_right()->set_parent(this);
}
}
void rotate(const bool is_right)
{
const bool was_right = is_right_child();
link_type* const child = get_child(!is_right);
etl::link_rotate<base>(this, child);
if (link_type* const parent = child->get_parent())
{
parent->set_child(child, was_right);
}
}
ETL_NODISCARD
link_type* adjust_balance(const bool increase)
{
const int_fast8_t new_bf = etl_bf + (increase ? +1 : -1);
if ((-1 <= new_bf) && (new_bf <= +1))
{
etl_bf = new_bf;
return this;
}
const bool is_right_rotation = new_bf < 0;
const int_fast8_t sign = is_right_rotation ? +1 : -1;
link_type* const z_leaf = get_child(!is_right_rotation);
if (z_leaf->etl_bf * sign <= 0)
{
rotate(is_right_rotation);
if (z_leaf->etl_bf == 0)
{
etl_bf = -sign;
z_leaf->etl_bf = +sign;
}
else
{
etl_bf = 0;
z_leaf->etl_bf = 0;
}
return z_leaf;
}
link_type* const y_leaf = z_leaf->get_child(is_right_rotation);
z_leaf->rotate(!is_right_rotation);
rotate(is_right_rotation);
if (y_leaf->etl_bf == 0)
{
etl_bf = 0;
z_leaf->etl_bf = 0;
}
else if (y_leaf->etl_bf == sign)
{
etl_bf = 0;
y_leaf->etl_bf = 0;
z_leaf->etl_bf = -sign;
}
else
{
etl_bf = +sign;
y_leaf->etl_bf = 0;
z_leaf->etl_bf = 0;
}
return y_leaf;
}
void link_child(link_type* child, const bool is_right)
{
if (is_right)
{
etl::link_right<base>(this, child);
}
else
{
etl::link_left<base>(this, child);
}
}
}; // link_type
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
bool empty() const ETL_NOEXCEPT
{
return ETL_NULLPTR == get_root();
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
size_t size() const ETL_NOEXCEPT
{
return get_origin().etl_size;
}
//*************************************************************************
//*************************************************************************
void clear() ETL_NOEXCEPT
{
#if ETL_USING_CPP11
auto unlinker = [](link_type& link)
{
link.clear();
link.etl_size = 0;
};
#else
struct
{
void operator()(link_type& link) const
{
link.clear();
link.etl_size = 0;
}
} unlinker;
#endif
// No need to balance b/c everything will be unlinked.
// Note that "post-order" visitation is important -
// it ensures that once a link is passed to the "visitor" functor,
// traversal won't use a pointer to this link anymore,
// so we could efficiently clear the link.
visit_post_order_impl(&origin, false, unlinker);
origin.set_left(ETL_NULLPTR);
origin.etl_size = 0;
}
//*******************************************
//*******************************************
void swap(intrusive_avl_tree_base& other) ETL_NOEXCEPT
{
if (this != &other)
{
ETL_OR_STD::swap(origin, other.origin);
}
}
//*************************************************************************
//*************************************************************************
friend void swap(intrusive_avl_tree_base& lhs, intrusive_avl_tree_base& rhs) ETL_NOEXCEPT
{
if (&lhs != &rhs)
{
lhs.swap(rhs);
}
}
protected:
//*************************************************************************
//*************************************************************************
intrusive_avl_tree_base() ETL_NOEXCEPT {}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
intrusive_avl_tree_base(intrusive_avl_tree_base&&) ETL_NOEXCEPT = default;
//*************************************************************************
//*************************************************************************
intrusive_avl_tree_base& operator=(intrusive_avl_tree_base&& other) ETL_NOEXCEPT
{
if (this != &other)
{
intrusive_avl_tree_base tmp(etl::move(other));
swap(tmp);
}
return *this;
}
#endif
//*************************************************************************
//***************************************************************************
~intrusive_avl_tree_base()
{
// It's important to clear, so that none of the former (but still alive) items
// stay linked to this tree (neither directly at the root item
// nor transitively via "parent" links from leaf items up to the origin).
clear();
}
ETL_NODISCARD
link_type* get_root() ETL_NOEXCEPT
{
return static_cast<link_type*>(origin.etl_left);
}
ETL_NODISCARD
const link_type* get_root() const ETL_NOEXCEPT
{
return static_cast<const link_type*>(origin.etl_left);
}
ETL_NODISCARD
link_type& get_origin() ETL_NOEXCEPT
{
return origin;
}
const link_type& get_origin() const ETL_NOEXCEPT
{
return origin;
}
template <typename TLink>
ETL_NODISCARD
static TLink* get_origin(TLink* link) ETL_NOEXCEPT
{
while ((ETL_NULLPTR != link) && !link->is_origin())
{
link = link->get_parent();
}
return link;
}
ETL_NODISCARD
static bool is_real_link(const link_type* link) ETL_NOEXCEPT
{
return (ETL_NULLPTR != link) && !link->is_origin();
}
template <typename TLink>
ETL_NODISCARD
static TLink* begin_impl(TLink& origin) ETL_NOEXCEPT
{
TLink* curr = &origin;
TLink* next = curr->get_child(false);
while (ETL_NULLPTR != next)
{
curr = next;
next = next->get_child(false);
}
return curr;
}
template <typename TLink>
ETL_NODISCARD
static TLink* end_impl(TLink& origin) ETL_NOEXCEPT
{
return &origin;
}
template <typename TLink>
ETL_NODISCARD
static TLink* find_extremum_impl(TLink* curr, const bool is_max) ETL_NOEXCEPT
{
if (ETL_NULLPTR != curr)
{
TLink* next = curr->get_child(is_max);
while (ETL_NULLPTR != next)
{
curr = next;
next = curr->get_child(is_max);
}
}
return curr;
}
template <typename TLink>
ETL_NODISCARD
static TLink* next_in_order_impl(TLink* curr) ETL_NOEXCEPT
{
if ((ETL_NULLPTR == curr) || curr->is_origin())
{
return curr;
}
if (TLink* const next = curr->get_child(true))
{
return find_extremum_impl(next, false);
}
while (curr->is_right_child())
{
curr = curr->get_parent();
}
return curr->get_parent();
}
template <typename TLink>
ETL_NODISCARD
static TLink* prev_in_order_impl(TLink* curr) ETL_NOEXCEPT
{
if (ETL_NULLPTR == curr)
{
return ETL_NULLPTR;
}
if (TLink* const next = curr->get_child(false))
{
return find_extremum_impl(next, true);
}
while (curr->is_left_child())
{
curr = curr->get_parent();
}
return curr->is_origin() ? curr : curr->get_parent();
}
template <typename TLink, typename Visitor>
static void visit_in_order_impl(TLink* curr, const bool is_reverse, Visitor visitor)
{
TLink* prev = ETL_NULLPTR;
while (ETL_NULLPTR != curr)
{
TLink* next = curr->get_parent();
if (prev == next)
{
if (TLink* const child1 = curr->get_child(is_reverse))
{
next = child1;
}
else
{
if (!curr->is_origin())
{
visitor(*curr);
}
if (TLink* const child2 = curr->get_child(!is_reverse))
{
next = child2;
}
}
}
else if (prev == curr->get_child(is_reverse))
{
if (!curr->is_origin())
{
visitor(*curr);
}
if (TLink* const child2 = curr->get_child(!is_reverse))
{
next = child2;
}
}
prev = etl::exchange(curr, next);
}
}
template <typename TLink, typename Visitor>
static void visit_post_order_impl(TLink* curr, const bool is_reverse, Visitor visitor)
{
TLink* prev = ETL_NULLPTR;
while (ETL_NULLPTR != curr)
{
TLink* next = curr->get_parent();
if (prev == next)
{
if (TLink* const child1 = curr->get_child(is_reverse))
{
next = child1;
}
else if (TLink* const child2 = curr->get_child(!is_reverse))
{
next = child2;
}
else if (!curr->is_origin())
{
visitor(*curr);
}
}
else if (prev == curr->get_child(is_reverse))
{
if (TLink* const child2 = curr->get_child(!is_reverse))
{
next = child2;
}
else if (!curr->is_origin())
{
visitor(*curr);
}
}
else if (!curr->is_origin())
{
visitor(*curr);
}
prev = etl::exchange(curr, next);
}
}
template <typename TLink, typename Visitor>
static void visit_pre_order_impl(TLink* curr, const bool is_reverse, Visitor visitor)
{
TLink* prev = ETL_NULLPTR;
while (ETL_NULLPTR != curr)
{
TLink* next = curr->get_parent();
if (prev == next)
{
if (!curr->is_origin())
{
visitor(*curr);
}
if (TLink* const child1 = curr->get_child(is_reverse))
{
next = child1;
}
else if (TLink* const child2 = curr->get_child(!is_reverse))
{
next = child2;
}
}
else if (prev == curr->get_child(is_reverse))
{
if (TLink* const child2 = curr->get_child(!is_reverse))
{
next = child2;
}
}
prev = etl::exchange(curr, next);
}
}
ETL_NODISCARD
static int_fast8_t get_balance_factor_impl(const link_type* const curr) ETL_NOEXCEPT
{
return (ETL_NULLPTR != curr) ? curr->etl_bf : 0;
}
template <typename TLink>
ETL_NODISCARD
static TLink* get_parent_impl(TLink* const curr) ETL_NOEXCEPT
{
if (ETL_NULLPTR == curr)
{
return ETL_NULLPTR;
}
TLink* const parent = curr->get_parent();
if ((ETL_NULLPTR == parent) || parent->is_origin())
{
return ETL_NULLPTR;
}
return parent;
}
template <typename TLink>
ETL_NODISCARD
static TLink* get_child_impl(TLink* const curr, const bool is_right) ETL_NOEXCEPT
{
if (ETL_NULLPTR == curr)
{
return ETL_NULLPTR;
}
return curr->get_child(is_right);
}
template <typename TValue, typename TIterator, typename TBinaryCompare>
void assign_impl(TIterator first, TIterator last, TBinaryCompare binary_comp)
{
#if ETL_IS_DEBUG_BUILD
const intmax_t diff = etl::distance(first, last);
ETL_ASSERT(diff >= 0, ETL_ERROR(intrusive_avl_tree_iterator_exception));
#endif
// Add all the elements.
while (first != last)
{
link_type& link = *first++;
TValue& value = static_cast<TValue&>(link);
#if ETL_USING_CPP11
find_or_insert_impl<TValue>( //
[&value, &binary_comp](const TValue& other) { return binary_comp(value, other); }, //
[&value] { return &value; });
#else
const CompareFactory<TValue, TBinaryCompare> compareFactory(value, binary_comp);
find_or_insert_impl<TValue>(compareFactory, compareFactory);
#endif
}
}
template <typename TValue, typename TLink, typename TCompare>
static TValue* find_impl(TLink* const root, TCompare comp)
{
// Try to find existing node.
TLink* curr = root;
while (ETL_NULLPTR != curr)
{
TValue* const result = static_cast<TValue*>(curr);
const int cmp = comp(*result);
if (0 == cmp)
{
// Found!
return result;
}
curr = curr->get_child(cmp > 0);
}
// Not found.
return ETL_NULLPTR;
}
template <typename TValue, typename TCompare, typename TFactory>
etl::pair<TValue*, bool> find_or_insert_impl(TCompare comp, TFactory factory)
{
// Try to find existing node.
bool is_right = false;
link_type* curr = get_root();
link_type* parent = &origin;
while (ETL_NULLPTR != curr)
{
TValue* const result = static_cast<TValue*>(curr);
const int cmp = comp(*result);
if (0 == cmp)
{
// Found! Tree was not modified.
return etl::make_pair(result, false);
}
parent = curr;
is_right = cmp > 0;
curr = curr->get_child(is_right);
}
// Try to instantiate new node.
TValue* const result = factory();
if (ETL_NULLPTR == result)
{
// Failed (or rejected)! The tree was not modified.
return etl::make_pair(ETL_NULLPTR, false);
}
link_type& result_link = static_cast<link_type&>(*result);
ETL_ASSERT(!(result_link.is_linked()), ETL_ERROR(intrusive_avl_tree_value_is_already_linked));
// Link the new node.
parent->link_child(&result_link, is_right);
get_origin(parent)->etl_size += 1;
retrace_on_insert(&result_link);
// Successfully linked, so the tree was modified.
return etl::make_pair(result, true);
}
template <bool IsUpper, typename TValue, typename TLink, typename TCompare>
static TValue* find_bound_impl(TLink* const root, TCompare comp)
{
TValue* result = ETL_NULLPTR;
TLink* next = root;
while (ETL_NULLPTR != next)
{
TValue* const next_value = static_cast<TValue*>(next);
const int cmp = comp(*next_value);
if ((cmp > 0) || (IsUpper && (cmp == 0)))
{
next = next->get_right();
}
else
{
result = next_value;
next = next->get_left();
}
}
return result;
}
static void erase_impl(link_type* const z_link) ETL_NOEXCEPT
{
// Remove only real and still-linked items.
// Tree itself uses this `link_type` for its `origin` sentinel item,
// but you can't (and there is no need to) erase it.
if ((ETL_NULLPTR == z_link) || z_link->is_origin() || !z_link->is_linked())
{
return;
}
link_type* parent = z_link->get_parent();
bool is_right = z_link->is_right_child();
if (!z_link->has_left())
{
parent->link_child(z_link->get_right(), is_right);
}
else if (!z_link->has_right())
{
parent->link_child(z_link->get_left(), is_right);
}
else
{
link_type* const y_link = next_in_order_impl(z_link);
link_type* const y_link_parent = y_link->get_parent();
y_link->etl_bf = z_link->etl_bf;
if (z_link != y_link_parent)
{
y_link_parent->link_child(y_link->get_right(), y_link->is_right_child());
link_type* const z_right = z_link->get_right();
y_link->set_right(z_right);
z_right->set_parent(y_link);
parent->link_child(y_link, is_right);
is_right = false;
parent = y_link_parent;
}
else
{
parent->link_child(y_link, is_right);
is_right = true;
parent = y_link;
}
link_type* const z_left = z_link->get_left();
y_link->set_left(z_left);
z_left->set_parent(y_link);
}
z_link->clear();
z_link->etl_size = 0;
get_origin(parent)->etl_size -= 1;
retrace_on_erase(parent, is_right);
}
private:
link_type origin;
#if ETL_USING_CPP11
#else
// Disable copy construction and assignment.
intrusive_avl_tree_base(const intrusive_avl_tree_base&);
intrusive_avl_tree_base& operator=(const intrusive_avl_tree_base&);
template <typename TValue, typename TBinaryCompare>
struct CompareFactory
{
TValue& value_ref;
TBinaryCompare binary_comp;
CompareFactory(TValue& value, TBinaryCompare comp)
: value_ref(value)
, binary_comp(comp)
{
}
ETL_NODISCARD
int operator()(const TValue& other) const
{
return binary_comp(value_ref, other);
}
ETL_NODISCARD
TValue* operator()() const
{
return &value_ref;
}
}; // CompareFactory
#endif
static void retrace_on_insert(link_type* curr)
{
link_type* parent = curr->get_parent();
while (!parent->is_origin())
{
const bool is_right = curr->is_right_child();
curr = parent->adjust_balance(is_right);
parent = curr->get_parent();
if (curr->etl_bf == 0)
{
break;
}
}
if (parent->is_origin())
{
parent->set_left(curr);
}
}
static void retrace_on_erase(link_type* parent, bool is_right)
{
while (!parent->is_origin())
{
link_type* const curr = parent->adjust_balance(!is_right);
parent = curr->get_parent();
if ((curr->etl_bf != 0) || parent->is_origin())
{
if (parent->is_origin())
{
parent->set_left(curr);
}
break;
}
is_right = curr->is_right_child();
}
}
}; // intrusive_avl_tree_base
//***************************************************************************
//***************************************************************************
template <typename TValue, size_t ID_ = 0>
class intrusive_avl_tree : public etl::intrusive_avl_tree_base<ID_>
{
typedef etl::intrusive_avl_tree_base<ID_> base;
public:
// Node typedef.
typedef typename base::link_type link_type;
// STL style typedefs.
typedef TValue value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
#if ETL_USING_CPP11
typedef value_type&& rvalue_reference;
#endif
//*************************************************************************
//*************************************************************************
class iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, value_type>
{
public:
friend class intrusive_avl_tree;
friend class const_iterator;
iterator() ETL_NOEXCEPT
: p_value(ETL_NULLPTR)
{
}
//*************************************************************************
//*************************************************************************
iterator& operator++() ETL_NOEXCEPT
{
p_value = base::next_in_order_impl(p_value);
return *this;
}
//*************************************************************************
//*************************************************************************
iterator operator++(int) ETL_NOEXCEPT
{
iterator temp(*this);
p_value = base::next_in_order_impl(p_value);
return temp;
}
//*************************************************************************
//*************************************************************************
iterator& operator--() ETL_NOEXCEPT
{
p_value = base::prev_in_order_impl(p_value);
return *this;
}
//*************************************************************************
//*************************************************************************
iterator operator--(int) ETL_NOEXCEPT
{
iterator temp(*this);
p_value = base::prev_in_order_impl(p_value);
return temp;
}
//*************************************************************************
//*************************************************************************
reference operator*() const
{
ETL_ASSERT(has_value(), ETL_ERROR(intrusive_avl_tree_iterator_exception));
#include "private/diagnostic_null_dereference_push.h"
return *static_cast<pointer>(p_value);
#include "private/diagnostic_pop.h"
}
//*************************************************************************
//*************************************************************************
pointer get() const ETL_NOEXCEPT
{
return static_cast<pointer>(has_value() ? p_value : ETL_NULLPTR);
}
//*************************************************************************
//*************************************************************************
pointer operator->() const
{
ETL_ASSERT_OR_RETURN_VALUE(has_value(), ETL_ERROR(intrusive_avl_tree_iterator_exception), ETL_NULLPTR);
return static_cast<pointer>(p_value);
}
friend bool operator==(const iterator& lhs, const iterator& rhs) ETL_NOEXCEPT
{
return lhs.p_value == rhs.p_value;
}
friend bool operator!=(const iterator& lhs, const iterator& rhs) ETL_NOEXCEPT
{
return !(lhs == rhs);
}
ETL_EXPLICIT operator bool() const ETL_NOEXCEPT
{
return has_value();
}
ETL_NODISCARD
bool has_value() const ETL_NOEXCEPT
{
return base::is_real_link(p_value);
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
int_fast8_t get_balance_factor() const ETL_NOEXCEPT
{
return base::get_balance_factor_impl(p_value);
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator get_parent() const ETL_NOEXCEPT
{
return iterator(base::get_parent_impl(p_value));
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator get_child(const bool is_right) const ETL_NOEXCEPT
{
return iterator(base::get_child_impl(p_value, is_right));
}
private:
ETL_EXPLICIT iterator(link_type* value)
: p_value(value)
{
}
link_type* p_value;
}; // iterator
//*************************************************************************
//*************************************************************************
class const_iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, const value_type>
{
public:
friend class intrusive_avl_tree;
const_iterator() ETL_NOEXCEPT
: p_value(ETL_NULLPTR)
{
}
// Implicit by design - it's always safe to make const iterator from ordinary one.
const_iterator(const typename intrusive_avl_tree::iterator& other) ETL_NOEXCEPT // NOLINT
: p_value(other.p_value)
{
}
//*************************************************************************
//*************************************************************************
const_iterator& operator++() ETL_NOEXCEPT
{
p_value = base::next_in_order_impl(p_value);
return *this;
}
//*************************************************************************
const_iterator operator++(int) ETL_NOEXCEPT
{
const_iterator temp(*this);
p_value = base::next_in_order_impl(p_value);
return temp;
}
//*************************************************************************
//*************************************************************************
const_iterator& operator--() ETL_NOEXCEPT
{
p_value = base::prev_in_order_impl(p_value);
return *this;
}
//*************************************************************************
//*************************************************************************
const_iterator operator--(int) ETL_NOEXCEPT
{
const_iterator temp(*this);
p_value = base::prev_in_order_impl(p_value);
return temp;
}
//*************************************************************************
//*************************************************************************
const_reference operator*() const
{
ETL_ASSERT(has_value(), ETL_ERROR(intrusive_avl_tree_iterator_exception));
#include "private/diagnostic_null_dereference_push.h"
return *static_cast<const_pointer>(p_value);
#include "private/diagnostic_pop.h"
}
//*************************************************************************
//*************************************************************************
const_pointer get() const ETL_NOEXCEPT
{
return static_cast<const_pointer>(has_value() ? p_value : ETL_NULLPTR);
}
//*************************************************************************
//*************************************************************************
const_pointer operator->() const
{
ETL_ASSERT_OR_RETURN_VALUE(has_value(), ETL_ERROR(intrusive_avl_tree_iterator_exception), ETL_NULLPTR);
return static_cast<const_pointer>(p_value);
}
friend bool operator==(const const_iterator& lhs, const const_iterator& rhs) ETL_NOEXCEPT
{
return lhs.p_value == rhs.p_value;
}
friend bool operator!=(const const_iterator& lhs, const const_iterator& rhs) ETL_NOEXCEPT
{
return !(lhs == rhs);
}
ETL_EXPLICIT operator bool() const ETL_NOEXCEPT
{
return has_value();
}
ETL_NODISCARD
bool has_value() const ETL_NOEXCEPT
{
return base::is_real_link(p_value);
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
int_fast8_t get_balance_factor() const ETL_NOEXCEPT
{
return base::get_balance_factor_impl(p_value);
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator get_parent() const ETL_NOEXCEPT
{
return const_iterator(base::get_parent_impl(p_value));
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator get_child(const bool is_right) const ETL_NOEXCEPT
{
return const_iterator(base::get_child_impl(p_value, is_right));
}
private:
ETL_EXPLICIT const_iterator(const link_type* value)
: p_value(value)
{
}
const link_type* p_value;
}; // const_iterator
//*************************************************************************
//*************************************************************************
intrusive_avl_tree() ETL_NOEXCEPT
: intrusive_avl_tree_base<ID_>()
{
}
//*************************************************************************
//*************************************************************************
template <typename TIterator, typename TBinaryCompare>
intrusive_avl_tree(TIterator first, TIterator last, TBinaryCompare binary_comp,
typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
{
base::template assign_impl<value_type>(first, last, binary_comp);
}
//*************************************************************************
//*************************************************************************
~intrusive_avl_tree() {}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
intrusive_avl_tree(intrusive_avl_tree&&) ETL_NOEXCEPT = default;
//*************************************************************************
//*************************************************************************
intrusive_avl_tree& operator=(intrusive_avl_tree&&) ETL_NOEXCEPT = default;
intrusive_avl_tree(const intrusive_avl_tree&) = delete;
intrusive_avl_tree& operator=(const intrusive_avl_tree&) = delete;
#endif
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator begin() ETL_NOEXCEPT
{
return iterator(base::begin_impl(base::get_origin()));
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator begin() const ETL_NOEXCEPT
{
return const_iterator(base::begin_impl(base::get_origin()));
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator cbegin() const ETL_NOEXCEPT
{
return begin();
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator end() ETL_NOEXCEPT
{
return iterator(base::end_impl(base::get_origin()));
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator end() const ETL_NOEXCEPT
{
return const_iterator(base::end_impl(base::get_origin()));
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator cend() const ETL_NOEXCEPT
{
return end();
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator max() ETL_NOEXCEPT
{
return --end();
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator max() const ETL_NOEXCEPT
{
return --end();
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator min() ETL_NOEXCEPT
{
return begin();
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator min() const ETL_NOEXCEPT
{
return begin();
}
//*************************************************************************
//*************************************************************************
template <typename TCompare>
iterator lower_bound(TCompare comp)
{
pointer ptr = base::template find_bound_impl<false, value_type>(base::get_root(), comp);
return make_iterator(ptr, end());
}
template <typename TCompare>
const_iterator lower_bound(TCompare comp) const
{
const_pointer ptr = base::template find_bound_impl<false, const value_type>(base::get_root(), comp);
return make_iterator(ptr, end());
}
//*************************************************************************
//*************************************************************************
template <typename TCompare>
iterator upper_bound(TCompare comp)
{
pointer ptr = base::template find_bound_impl<true, value_type>(base::get_root(), comp);
return make_iterator(ptr, end());
}
template <typename TCompare>
const_iterator upper_bound(TCompare comp) const
{
const_pointer ptr = base::template find_bound_impl<true, const value_type>(base::get_root(), comp);
return make_iterator(ptr, end());
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
iterator get_root() ETL_NOEXCEPT
{
return iterator(base::get_root());
}
//*************************************************************************
//*************************************************************************
ETL_NODISCARD
const_iterator get_root() const ETL_NOEXCEPT
{
return const_iterator(base::get_root());
}
//*************************************************************************
//*************************************************************************
template <typename TCompare>
iterator find(TCompare comp)
{
pointer ptr = base::template find_impl<value_type>(base::get_root(), comp);
return make_iterator(ptr, end());
}
//*************************************************************************
//*************************************************************************
template <typename TCompare>
const_iterator find(TCompare comp) const
{
const_pointer ptr = base::template find_impl<const value_type>(base::get_root(), comp);
return make_iterator(ptr, end());
}
//*************************************************************************
//*************************************************************************
template <typename TCompare, typename TFactory>
etl::pair<iterator, bool> find_or_insert(TCompare comp, TFactory factory)
{
const etl::pair<value_type*, bool> ptr_mod = base::template find_or_insert_impl<value_type>(comp, factory);
return etl::make_pair(make_iterator(ptr_mod.first, iterator()), ptr_mod.second);
}
//*************************************************************************
//*************************************************************************
iterator erase(iterator position)
{
ETL_ASSERT(position.has_value(), ETL_ERROR(intrusive_avl_tree_iterator_exception));
#if ETL_IS_DEBUG_BUILD
// Iterator must originate from the same tree instance.
// The check is still of the same O(log(N)) complexity.
ETL_ASSERT(base::get_origin(position.p_value) == &base::get_origin(), ETL_ERROR(intrusive_avl_tree_iterator_exception));
#endif
iterator next(position);
++next;
base::erase_impl(position.p_value);
return next;
}
//*************************************************************************
//*************************************************************************
iterator erase(const_iterator position)
{
// It's safe to `const_cast` b/c we just need iterator to locate corresponding link.
// Tree itself is not `const` anyway - so it's a legitimate operation, and it also matches
// with similar `std::list::erase` or `etl::intrusive_list::erase` methods.
return erase(iterator(const_cast<link_type*>(position.p_value)));
}
//*************************************************************************
//*************************************************************************
template <typename Visitor>
void visit_in_order(const bool is_reverse, Visitor visitor)
{
#if ETL_USING_CPP11
base::visit_in_order_impl( //
&base::get_origin(), is_reverse, //
[&visitor](link_type& link) { visitor(static_cast<reference>(link)); });
#else
const CastingVisitor<reference, Visitor> casting_visitor(visitor);
base::visit_in_order_impl(&base::get_origin(), is_reverse, casting_visitor);
#endif
}
//*************************************************************************
//*************************************************************************
template <typename Visitor>
void visit_in_order(const bool is_reverse, Visitor visitor) const
{
#if ETL_USING_CPP11
base::visit_in_order_impl( //
&base::get_origin(), is_reverse, //
[&visitor](const link_type& link) { visitor(static_cast<const_reference>(link)); });
#else
const CastingVisitor<const_reference, Visitor> casting_visitor(visitor);
base::visit_in_order_impl(&base::get_origin(), is_reverse, casting_visitor);
#endif
}
//*************************************************************************
//*************************************************************************
template <typename Visitor>
void visit_post_order(const bool is_reverse, Visitor visitor)
{
#if ETL_USING_CPP11
base::visit_post_order_impl( //
&base::get_origin(), is_reverse, //
[&visitor](link_type& link) { visitor(static_cast<reference>(link)); });
#else
const CastingVisitor<reference, Visitor> casting_visitor(visitor);
base::visit_post_order_impl(&base::get_origin(), is_reverse, casting_visitor);
#endif
}
//*************************************************************************
//*************************************************************************
template <typename Visitor>
void visit_post_order(const bool is_reverse, Visitor visitor) const
{
#if ETL_USING_CPP11
base::visit_post_order_impl( //
&base::get_origin(), is_reverse, //
[&visitor](const link_type& link) { visitor(static_cast<const_reference>(link)); });
#else
const CastingVisitor<const_reference, Visitor> casting_visitor(visitor);
base::visit_post_order_impl(&base::get_origin(), is_reverse, casting_visitor);
#endif
}
//*************************************************************************
//*************************************************************************
template <typename Visitor>
void visit_pre_order(const bool is_reverse, Visitor visitor)
{
#if ETL_USING_CPP11
base::visit_pre_order_impl( //
&base::get_origin(), is_reverse, //
[&visitor](link_type& link) { visitor(static_cast<reference>(link)); });
#else
const CastingVisitor<reference, Visitor> casting_visitor(visitor);
base::visit_pre_order_impl(&base::get_origin(), is_reverse, casting_visitor);
#endif
}
//*************************************************************************
//*************************************************************************
template <typename Visitor>
void visit_pre_order(const bool is_reverse, Visitor visitor) const
{
#if ETL_USING_CPP11
base::visit_pre_order_impl( //
&base::get_origin(), is_reverse, //
[&visitor](const link_type& link) { visitor(static_cast<const_reference>(link)); });
#else
const CastingVisitor<const_reference, Visitor> casting_visitor(visitor);
base::visit_pre_order_impl(&base::get_origin(), is_reverse, casting_visitor);
#endif
}
private:
#if ETL_USING_CPP11
#else
// Disable copy construction and assignment.
intrusive_avl_tree(const intrusive_avl_tree&);
intrusive_avl_tree& operator=(const intrusive_avl_tree& rhs);
template <typename T, typename Visitor>
struct CastingVisitor
{
Visitor& visitor;
ETL_EXPLICIT CastingVisitor(Visitor& visitor)
: visitor(visitor)
{
}
template <typename TLink>
void operator()(TLink& link) const
{
visitor(static_cast<T>(link));
}
};
#endif
template <typename TIterator, typename Pointer>
ETL_NODISCARD
static TIterator make_iterator(Pointer const ptr, const TIterator end)
{
return (ETL_NULLPTR != ptr) ? TIterator(ptr) : end;
}
}; // intrusive_avl_tree
} // namespace etl
#endif
etl::factory
Definition factory.h:99
etl::intrusive_avl_tree::const_iterator
Definition intrusive_avl_tree.h:1291
etl::intrusive_avl_tree::const_iterator::operator--
const_iterator operator--(int) ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1343
etl::intrusive_avl_tree::const_iterator::operator--
const_iterator & operator--() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1332
etl::intrusive_avl_tree::const_iterator::get_child
ETL_NODISCARD const_iterator get_child(const bool is_right) const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1440
etl::intrusive_avl_tree::const_iterator::get_balance_factor
ETL_NODISCARD int_fast8_t get_balance_factor() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1416
etl::intrusive_avl_tree::const_iterator::get_parent
ETL_NODISCARD const_iterator get_parent() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1428
etl::intrusive_avl_tree::const_iterator::operator++
const_iterator & operator++() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1311
etl::intrusive_avl_tree::const_iterator::get
const_pointer get() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1370
etl::intrusive_avl_tree::const_iterator::operator++
const_iterator operator++(int) ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1321
etl::intrusive_avl_tree::const_iterator::operator->
const_pointer operator->() const
Definition intrusive_avl_tree.h:1381
etl::intrusive_avl_tree::iterator
Definition intrusive_avl_tree.h:1115
etl::intrusive_avl_tree::iterator::operator--
iterator operator--(int) ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1163
etl::intrusive_avl_tree::iterator::get_balance_factor
ETL_NODISCARD int_fast8_t get_balance_factor() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1236
etl::intrusive_avl_tree::iterator::operator++
iterator & operator++() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1130
etl::intrusive_avl_tree::iterator::get_parent
ETL_NODISCARD iterator get_parent() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1248
etl::intrusive_avl_tree::iterator::get_child
ETL_NODISCARD iterator get_child(const bool is_right) const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1260
etl::intrusive_avl_tree::iterator::operator++
iterator operator++(int) ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1141
etl::intrusive_avl_tree::iterator::operator--
iterator & operator--() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1152
etl::intrusive_avl_tree::iterator::get
pointer get() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1190
etl::intrusive_avl_tree::iterator::operator->
pointer operator->() const
Definition intrusive_avl_tree.h:1201
etl::intrusive_avl_tree_base
Definition intrusive_avl_tree.h:96
etl::intrusive_avl_tree_base::swap
friend void swap(intrusive_avl_tree_base &lhs, intrusive_avl_tree_base &rhs) ETL_NOEXCEPT
Definition intrusive_avl_tree.h:483
etl::intrusive_avl_tree_base::size
ETL_NODISCARD size_t size() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:422
etl::intrusive_avl_tree_base::swap
void swap(intrusive_avl_tree_base &other) ETL_NOEXCEPT
Definition intrusive_avl_tree.h:470
etl::intrusive_avl_tree_base::~intrusive_avl_tree_base
~intrusive_avl_tree_base()
Definition intrusive_avl_tree.h:534
etl::intrusive_avl_tree_base::clear
void clear() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:436
etl::intrusive_avl_tree_base::intrusive_avl_tree_base
intrusive_avl_tree_base() ETL_NOEXCEPT
Default constructor.
Definition intrusive_avl_tree.h:496
etl::intrusive_avl_tree_base::empty
ETL_NODISCARD bool empty() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:412
etl::intrusive_avl_tree_iterator_exception
Definition intrusive_avl_tree.h:65
etl::intrusive_avl_tree
Definition intrusive_avl_tree.h:1078
etl::intrusive_avl_tree::max
ETL_NODISCARD iterator max() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1593
etl::intrusive_avl_tree::get_root
ETL_NODISCARD iterator get_root() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1688
etl::intrusive_avl_tree::min
ETL_NODISCARD iterator min() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1615
etl::intrusive_avl_tree::erase
iterator erase(iterator position)
Definition intrusive_avl_tree.h:1794
etl::intrusive_avl_tree::lower_bound
iterator lower_bound(TCompare comp)
Definition intrusive_avl_tree.h:1644
etl::intrusive_avl_tree::upper_bound
iterator upper_bound(TCompare comp)
Definition intrusive_avl_tree.h:1669
etl::intrusive_avl_tree::erase
iterator erase(const_iterator position)
Definition intrusive_avl_tree.h:1822
etl::intrusive_avl_tree::~intrusive_avl_tree
~intrusive_avl_tree()
Definition intrusive_avl_tree.h:1503
etl::intrusive_avl_tree::max
ETL_NODISCARD const_iterator max() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1604
etl::intrusive_avl_tree::visit_pre_order
void visit_pre_order(const bool is_reverse, Visitor visitor)
Definition intrusive_avl_tree.h:1940
etl::intrusive_avl_tree::visit_post_order
void visit_post_order(const bool is_reverse, Visitor visitor) const
Definition intrusive_avl_tree.h:1914
etl::intrusive_avl_tree::begin
ETL_NODISCARD const_iterator begin() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1541
etl::intrusive_avl_tree::cbegin
ETL_NODISCARD const_iterator cbegin() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1552
etl::intrusive_avl_tree::visit_post_order
void visit_post_order(const bool is_reverse, Visitor visitor)
Definition intrusive_avl_tree.h:1889
etl::intrusive_avl_tree::end
ETL_NODISCARD iterator end() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1562
etl::intrusive_avl_tree::intrusive_avl_tree
intrusive_avl_tree() ETL_NOEXCEPT
Default constructor.
Definition intrusive_avl_tree.h:1459
etl::intrusive_avl_tree::find_or_insert
etl::pair< iterator, bool > find_or_insert(TCompare comp, TFactory factory)
Definition intrusive_avl_tree.h:1777
etl::intrusive_avl_tree::find
iterator find(TCompare comp)
Definition intrusive_avl_tree.h:1719
etl::intrusive_avl_tree::visit_pre_order
void visit_pre_order(const bool is_reverse, Visitor visitor) const
Definition intrusive_avl_tree.h:1965
etl::intrusive_avl_tree::cend
ETL_NODISCARD const_iterator cend() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1582
etl::intrusive_avl_tree::min
ETL_NODISCARD const_iterator min() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1626
etl::intrusive_avl_tree::find
const_iterator find(TCompare comp) const
Definition intrusive_avl_tree.h:1739
etl::intrusive_avl_tree::begin
ETL_NODISCARD iterator begin() ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1530
etl::intrusive_avl_tree::get_root
ETL_NODISCARD const_iterator get_root() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1700
etl::intrusive_avl_tree::intrusive_avl_tree
intrusive_avl_tree(TIterator first, TIterator last, TBinaryCompare binary_comp, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Definition intrusive_avl_tree.h:1493
etl::intrusive_avl_tree::end
ETL_NODISCARD const_iterator end() const ETL_NOEXCEPT
Definition intrusive_avl_tree.h:1572
etl::intrusive_avl_tree::visit_in_order
void visit_in_order(const bool is_reverse, Visitor visitor)
Definition intrusive_avl_tree.h:1841
etl::intrusive_avl_tree::visit_in_order
void visit_in_order(const bool is_reverse, Visitor visitor) const
Definition intrusive_avl_tree.h:1863
etl::link_type
diagnostic_null_dereference_push.h
diagnostic_pop.h
error_handler.h
etl::const_iterator
ETL_ASSERT
#define ETL_ASSERT(b, e)
Definition error_handler.h:511
etl::exception::exception
ETL_EXCEPTION_CONSTEXPR exception(string_type reason_, string_type, numeric_type)
Constructor.
Definition exception.h:81
etl::visitor
Definition visitor.h:237
intrusive_links.h
iterator.h
memory.h
etl
Definition absolute.h:40
etl::make_pair
pair< T1, T2 > make_pair(T1 a, T2 b)
A convenience wrapper for creating a pair from two objects.
Definition utility.h:335
etl::exchange
T exchange(T &object, const T &new_value)
exchange (const)
Definition utility.h:498
etl::operator*
ETL_CONSTEXPR14 enable_if<!etl::is_specialization< TRep2, etl::chrono::duration >::value, etl::chrono::duration< typenameetl::common_type< TRep1, TRep2 >::type, TPeriod1 > >::type operator*(const etl::chrono::duration< TRep1, TPeriod1 > &lhs, const TRep2 &rhs) ETL_NOEXCEPT
Operator *.
Definition duration.h:541
etl::link_rotate
etl::enable_if< etl::is_same< TLink, etl::tree_link< TLink::ID > >::value, void >::type link_rotate(TLink &parent, TLink &child)
Automatically detects whether a left or right rotate is expected.
Definition intrusive_links.h:1377
platform.h
etl::intrusive_avl_tree_base::link_type
Definition intrusive_avl_tree.h:118
etl::intrusive_avl_tree_base::link_type::~link_type
~link_type()
Definition intrusive_avl_tree.h:193
etl::intrusive_avl_tree_base::link_type::etl_size
size_t etl_size
Stores total number of items in the tree (origin node only).
Definition intrusive_avl_tree.h:208
etl::intrusive_avl_tree_base::link_type::etl_bf
int_fast8_t etl_bf
Stores -1, 0, or +1 balancing factor in the real nodes.
Definition intrusive_avl_tree.h:207
etl::iterator
iterator
Definition iterator.h:482
etl::pair
pair holds two objects of arbitrary type
Definition utility.h:176
etl::pair::first
T1 first
first is a copy of the first object
Definition utility.h:180
etl::pair::second
T2 second
second is a copy of the second object
Definition utility.h:181
etl::type
etl::tree_link
A binary tree link.
Definition intrusive_links.h:984
operator==
ETL_CONSTEXPR14 bool operator==(const etl::to_arithmetic_result< T > &lhs, const etl::to_arithmetic_result< T > &rhs)
Equality test for etl::to_arithmetic_result.
Definition to_arithmetic.h:903
operator!=
ETL_CONSTEXPR14 bool operator!=(const etl::to_arithmetic_result< T > &lhs, const etl::to_arithmetic_result< T > &rhs)
Inequality test for etl::to_arithmetic_result.
Definition to_arithmetic.h:937
type_traits.h
utility.h