#ifndef ETL_INTRUSIVE_LINKS_INCLUDED
#define ETL_INTRUSIVE_LINKS_INCLUDED
#include <assert.h>
#include "platform.h"
#include "nullptr.h"
#include "type_traits.h"
#include "exception.h"
#include "error_handler.h"
#include "stl/utility.h"
#undef ETL_FILE
#define ETL_FILE "22"
namespace etl
{
class link_exception : public etl::exception
{
public:
link_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
: exception(reason_, file_name_, line_number_)
{
}
};
class not_unlinked_exception : public etl::link_exception
{
public:
not_unlinked_exception(string_type file_name_, numeric_type line_number_)
: link_exception(ETL_ERROR_TEXT("link:still linked", ETL_FILE"A"), file_name_, line_number_)
{
}
};
template <const size_t ID_>
struct forward_link
{
enum
{
ID = ID_,
};
void clear()
{
etl_next = nullptr;
}
bool is_linked() const
{
return etl_next != nullptr;
}
forward_link* etl_next;
};
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link(TLink& lhs, TLink& rhs)
{
lhs.etl_next = &rhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link_splice(TLink& lhs, TLink& rhs)
{
rhs.etl_next = lhs.etl_next;
lhs.etl_next = &rhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link(TLink* lhs, TLink* rhs)
{
if (lhs != nullptr)
{
lhs->etl_next = rhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link_splice(TLink* lhs, TLink* rhs)
{
if (lhs != nullptr)
{
if (rhs != nullptr)
{
rhs->etl_next = lhs->etl_next;
}
lhs->etl_next = rhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link(TLink& lhs, TLink* rhs)
{
lhs.etl_next = rhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link_splice(TLink& lhs, TLink* rhs)
{
if (rhs != nullptr)
{
rhs->etl_next = lhs.etl_next;
}
lhs.etl_next = rhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link(TLink* lhs, TLink& rhs)
{
if (lhs != nullptr)
{
lhs->etl_next = &rhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link_splice(TLink* lhs, TLink& rhs)
{
if (lhs != nullptr)
{
rhs.etl_next = lhs->etl_next;
lhs->etl_next = &rhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link_splice(TLink& lhs, TLink& first, TLink& last)
{
last.etl_next = lhs.etl_next;
lhs.etl_next = &first;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
link_splice(TLink* lhs, TLink& first, TLink& last)
{
if (lhs != nullptr)
{
last.etl_next = lhs->etl_next;
lhs->etl_next = &first;
}
else
{
last.etl_next = nullptr;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
unlink_after(TLink& node)
{
if (node.etl_next != nullptr)
{
TLink* unlinked_node = node.etl_next;
node.etl_next = unlinked_node->etl_next;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::forward_link<TLink::ID> >::value, void>::type
unlink_after(TLink& before, TLink& last)
{
before.etl_next = last.etl_next;
}
template <const size_t ID_>
struct bidirectional_link
{
enum
{
ID = ID_,
};
void clear()
{
etl_previous = nullptr;
etl_next = nullptr;
}
bool is_linked() const
{
return (etl_previous != nullptr) || (etl_next != nullptr);
}
void reverse()
{
std::swap(etl_previous, etl_next);
}
bidirectional_link* etl_previous;
bidirectional_link* etl_next;
void unlink()
{
if (etl_previous != nullptr)
{
etl_previous->etl_next = etl_next;
}
if (etl_next != nullptr)
{
etl_next->etl_previous = etl_previous;
}
}
};
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link(TLink& lhs, TLink& rhs)
{
lhs.etl_next = &rhs;
rhs.etl_previous = &lhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link_splice(TLink& lhs, TLink& rhs)
{
rhs.etl_next = lhs.etl_next;
rhs.etl_previous = &lhs;
if (lhs.etl_next != nullptr)
{
lhs.etl_next->etl_previous = &rhs;
}
lhs.etl_next = &rhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link(TLink* lhs, TLink* rhs)
{
if (lhs != nullptr)
{
lhs->etl_next = rhs;
}
if (rhs != nullptr)
{
rhs->etl_previous = lhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link_splice(TLink* lhs, TLink* rhs)
{
if (rhs != nullptr)
{
if (lhs != nullptr)
{
rhs->etl_next = lhs->etl_next;
}
rhs->etl_previous = lhs;
}
if (lhs != nullptr)
{
if (lhs->etl_next != nullptr)
{
lhs->etl_next->etl_previous = rhs;
}
lhs->etl_next = rhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link(TLink& lhs, TLink* rhs)
{
lhs.etl_next = rhs;
if (rhs != nullptr)
{
rhs->etl_previous = &lhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link_splice(TLink& lhs, TLink* rhs)
{
if (rhs != nullptr)
{
rhs->etl_next = lhs.etl_next;
rhs->etl_previous = &lhs;
}
if (lhs.etl_next != nullptr)
{
lhs.etl_next->etl_previous = rhs;
}
lhs.etl_next = rhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link(TLink* lhs, TLink& rhs)
{
if (lhs != nullptr)
{
lhs->etl_next = &rhs;
}
rhs.etl_previous = lhs;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link_splice(TLink* lhs, TLink& rhs)
{
if (lhs != nullptr)
{
rhs.etl_next = lhs->etl_next;
}
rhs.etl_previous = lhs;
if (lhs != nullptr)
{
if (lhs->etl_next != nullptr)
{
lhs->etl_next->etl_previous = &rhs;
}
lhs->etl_next = &rhs;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link_splice(TLink& lhs, TLink& first, TLink& last)
{
last.etl_next = lhs.etl_next;
first.etl_previous = &lhs;
if (last.etl_next != nullptr)
{
last.etl_next->etl_previous = &last;
}
lhs.etl_next = &first;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
link_splice(TLink* lhs, TLink& first, TLink& last)
{
if (lhs != nullptr)
{
last.etl_next = lhs->etl_next;
}
else
{
last.etl_next = nullptr;
}
first.etl_previous = lhs;
if (last.etl_next != nullptr)
{
last.etl_next->etl_previous = &last;
}
if (lhs != nullptr)
{
lhs->etl_next = &first;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
unlink(TLink& node)
{
node.unlink();
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::bidirectional_link<TLink::ID> >::value, void>::type
unlink(TLink& first, TLink& last)
{
if (&first == &last)
{
first.unlink();
}
else
{
if (last.etl_next != nullptr)
{
last.etl_next->etl_previous = first.etl_previous;
}
if (first.etl_previous != nullptr)
{
first.etl_previous->etl_next = last.etl_next;
}
}
}
template <const size_t ID_>
struct tree_link
{
enum
{
ID = ID_,
};
void clear()
{
etl_parent = nullptr;
etl_left = nullptr;
etl_right = nullptr;
}
bool is_linked() const
{
return (etl_parent != nullptr) || (etl_left != nullptr) || (etl_right != nullptr);
}
tree_link* etl_parent;
tree_link* etl_left;
tree_link* etl_right;
};
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_left(TLink& parent, TLink& leaf)
{
parent.etl_left = &leaf;
leaf.etl_parent = &parent;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_right(TLink& parent, TLink& leaf)
{
parent.etl_right = &leaf;
leaf.etl_parent = &parent;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_left(TLink* parent, TLink* leaf)
{
if (parent != nullptr)
{
parent->etl_left = leaf;
}
if (leaf != nullptr)
{
leaf->etl_parent = parent;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_right(TLink* parent, TLink* leaf)
{
if (parent != nullptr)
{
parent->etl_right = leaf;
}
if (leaf != nullptr)
{
leaf->etl_parent = parent;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_left(TLink& parent, TLink* leaf)
{
parent.etl_left = leaf;
if (leaf != nullptr)
{
leaf->etl_parent = &parent;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_right(TLink& parent, TLink* leaf)
{
parent.etl_right = leaf;
if (leaf != nullptr)
{
leaf->etl_parent = &parent;
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_left(TLink* parent, TLink& leaf)
{
if (parent != nullptr)
{
parent->etl_left = &leaf;
}
leaf.etl_parent = parent;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_right(TLink* parent, TLink& leaf)
{
if (parent != nullptr)
{
parent->etl_right = &leaf;
}
leaf.etl_parent = parent;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_left(TLink& parent, TLink& leaf)
{
parent.etl_right = leaf.etl_left;
if (parent.etl_right != nullptr)
{
parent.etl_right->etl_parent = &parent;
}
leaf.etl_parent = parent.etl_parent;
parent.etl_parent = &leaf;
leaf.etl_left = &parent;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_right(TLink& parent, TLink& leaf)
{
parent.etl_left = leaf.etl_right;
if (parent.etl_left != nullptr)
{
parent.etl_left->etl_parent = &parent;
}
leaf.etl_parent = parent.etl_parent;
parent.etl_parent = &leaf;
leaf.etl_right = &parent;
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_left(TLink* parent, TLink* leaf)
{
if ((parent != nullptr) && (leaf != nullptr))
{
link_rotate_left(*parent, *leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_right(TLink* parent, TLink* leaf)
{
if ((parent != nullptr) && (leaf != nullptr))
{
link_rotate_right(*parent, *leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_left(TLink& parent, TLink* leaf)
{
if (leaf != nullptr)
{
link_rotate_left(parent, *leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_right(TLink& parent, TLink* leaf)
{
if (leaf != nullptr)
{
link_rotate_right(parent, *leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_left(TLink* parent, TLink& leaf)
{
if (parent != nullptr)
{
link_rotate_left(*parent, leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate_right(TLink* parent, TLink& leaf)
{
if (parent != nullptr)
{
link_rotate_right(*parent, leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate(TLink& parent, TLink& leaf)
{
if (parent.etl_left == &leaf)
{
etl::link_rotate_right(parent, leaf);
}
else
{
etl::link_rotate_left(parent, leaf);
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate(TLink* parent, TLink* leaf)
{
if ((parent != nullptr) && (leaf != nullptr))
{
if (parent->etl_left == leaf)
{
etl::link_rotate_right(*parent, *leaf);
}
else
{
etl::link_rotate_left(*parent, *leaf);
}
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate(TLink& parent, TLink* leaf)
{
if (leaf != nullptr)
{
if (parent.etl_left == leaf)
{
etl::link_rotate_right(parent, *leaf);
}
else
{
etl::link_rotate_left(parent, *leaf);
}
}
}
template <typename TLink>
typename etl::enable_if<etl::is_same<TLink, etl::tree_link<TLink::ID> >::value, void>::type
link_rotate(TLink* parent, TLink& leaf)
{
if (parent != nullptr)
{
if (parent->etl_left == &leaf)
{
etl::link_rotate_right(*parent, leaf);
}
else
{
etl::link_rotate_left(*parent, leaf);
}
}
}
}
#undef ETL_FILE
#endif