A C++ template library for embedded applications
MIT licensed
Designed and
maintained by
John Wellbelove
Support the development
of the ETL
Intrusive Links

A set of link structures designed to be used within containers such as etl::intrusive_list.
They are parameterised by an id that allows them to be multiply inherited from when creating objects that must exist
in more than one intrusive container.

There are link and unlink functions supplied to manage connections between links. The functions will accept any
permutation of pointer and reference parameters, though reference parameters offer the best performance.
For bidirectional links, unlinking a node will automatically adjust the links of the surrounding nodes at the same level.
____________________________________________________________________________________________________
Forward link
template <const size_t ID_>
struct forward_link
____________________________________________________________________________________________________
Template parameters
const size_t ID_ A unique id for this link level.
____________________________________________________________________________________________________
Public constants
enum ID The unique id for this link level.
____________________________________________________________________________________________________
Public variables
forward_link<ID>* etl_next A pointer to the next forward link at this level.
____________________________________________________________________________________________________
Public functions
clear() Clears the pointers to nullptr.
____________________________________________________________________________________________________
Link functions
void etl::link<type>(lhs, rhs)        Links lhs to rhs.
void etl::link_splice<type>(lhs, rhs) Links lhs to rhs and rhs to what lhs pointed to. lhs must be 
                                      initialised.
void etl::unlink_after(node)          Unlinks the node after node.
void etl::unlink_after(before, lastUnlinks the nodes after before up to and including last.
                                      The range remain linked to each other.
____________________________________________________________________________________________________
Bidirectional link
template <const size_t ID_>
struct bidirectional_link
____________________________________________________________________________________________________
Template parameters
const size_t ID_ A unique id for this link level.
____________________________________________________________________________________________________
Public constants
enum ID     The unique id for this link level.
____________________________________________________________________________________________________
Public variables
bidirectional_link<ID>* etl_previous A pointer to the previous bidirectional link at this level.
bidirectional_link<ID>* etl_next     A pointer to the next bidirectional link at this level.
____________________________________________________________________________________________________
Public functions
clear()  Clears the pointers to nullptr.
reverse()Reverses the links.
____________________________________________________________________________________________________
Link functions
void etl::link<type>(lhs, rhs)
Link lhs to rhs.

void etl::link_splice<type>(lhs, rhs)
Link lhs to rhs and rhs to what lhs pointed to. If lhs is not nullptr then it must be initialised.

void etl::link_splice<type>(lhs, first, last)
Link lhs to the range first, last and last to what lhs pointed to. If lhs is not nullptr then it must be initialised.

void etl::unlink(node)                
Unlink the specified node. Elements either side are joined.

void etl::unlink(first, last)
Unlinks the range of nodes from first to last inclusive.
The range first/last remain linked to each other.
____________________________________________________________________________________________________
Tree link
template <const size_t ID_>
struct tree_link
____________________________________________________________________________________________________
Template parameters
const size_t ID_ A unique id for this link level.
____________________________________________________________________________________________________
Public constants
enum ID The unique id for this link level.
____________________________________________________________________________________________________
Public variables
tree_link<ID>* etl_parent A pointer to the parent tree link at this level.
tree_link<ID>* etl_left   A pointer to the left tree link at this level.
tree_link<ID>* etl_right  A pointer to the right tree link at this level.
____________________________________________________________________________________________________
Public functions
clear() Clears the pointers to nullptr.
____________________________________________________________________________________________________
Link functions
void etl::link_left<type>(parent, leaf)  Links leaf to the left of parent.
void etl::link_right<type>(parent, leaf) Links leaf to the right of parent.

void etl::link_rotate_left<type>(parent, leaf)  Rotates the link left making leaf the new parent.
void etl::link_rotate_right<type>(parent, leaf) Rotates the link right making leaf the new parent.

void etl::link_rotate<type>(parent, leaf) Rotates the link left or right making leaf the new parent.
                                          Chooses left or right rotate depending on the leaf connection.
____________________________________________________________________________________________________
Example 1
A simple two level intrusive list.

// The link levels
typedef etl::bidirectional_link<0> level0_t;
typedef etl::bidirectional_link<1> level1_t;

// The item stored in the lists
struct item : public level0_t, public level1_t
{
  item(int value)
    :: value(value)
  {
  }

  int value;
};

item data0(0);
item data1(1);
item data2(2);
item data3(3);

etl::intrusive_list<item, level0_t> level0_list;
etl::intrusive_list<item, level1_t> level1_list;

// Add items to level0 list
level0_list.push_back(data0);
level0_list.push_back(data1);
level0_list.push_back(data2);

// Add items to level1 list
level1_list.push_back(data3);
level1_list.push_back(data2);
level1_list.push_back(data1);
____________________________________________________________________________________________________
Example 2
Manual list manipulation.

typedef etl::bidirectional_link<0> level0_t;
typedef etl::bidirectional_link<1> level1_t;

// The item stored in the lists
struct item : public level0_t, public level1_t
{
  item(int value)
    :: value(value)
  {
  }

  int value;
};

item data0(0);
item data1(1);
item data2(2);
item data3(3);

// Set the first and last nodes links to nullptr.
data0.level0_t::clear();
data3.level0_t::clear();

// Make the links.
etl::link<level0_t>(data0, data1);
etl::link<level0_t>(data1, data2);
etl::link<level0_t>(data2, data3); // Level 0 = data0, data1, data2, data3

// Set the first and last nodes links to nullptr.
data2.level1_t::clear();
data1.level1_t::clear();

// Make the links.
etl::link<level1_t>(data2, data3);
etl::link<level1_t>(data3, data0);
etl::link<level1_t>(data0, data1); // Level 1 = data2, data3, data0, data1

// Disconnect a node.
etl::unlink<level1_t>(data3); // Level 1 = data2, data0, data1
intrusive_links.h

WYSIWYG Web Builder