Files CCore/inc/List.h CCore/src/List.cpp
There are several kinds of lists in C++. List can be a container (non-intrusive list). List can also be a set of elements, where each element contains links to neighbor elements. List can be single linked or double linked, linear or circular. Linear list controller can contain a pointer to the top of the list or two pointers to the first and the last elements.
CCore provides implementation of algorithms of intrusive lists. Intrusive lists are mandatory for many tasks, including system core tasks, because they don't require a memory allocation, they extremely efficient and can be used in such contexts where memory allocation is impossible or not desirable.
Non-intrusive lists can be built atop on these algorithms. Container lists looks like:
Lists are built using links:
/* struct SLink<T> */ template <class T> struct SLink { T *next; template <SLink<T> T::* LinkMember> struct LinearAlgo; template <SLink<T> T::* LinkMember> struct CircularAlgo; }; /* struct DLink<T> */ template <class T> struct DLink { T *next; T *prev; template <DLink<T> T::* LinkMember> struct LinearAlgo; template <DLink<T> T::* LinkMember> struct CircularAlgo; };
It's a very simple classes, SLink contains the next pointer for a single linked lists, DLink contains two pointers: next and prev, for a double linked lists.
To make a list you define a list node as following:
struct Node
{
SLink<Node> link;
....
};
Then you can use list algorithms:
using Algo = SLink<Node>::LinearAlgo<&Node::link> ;
One node can include several links of different types. It allows include such node in several lists simultaneously. We use the term "element" for the linked list node, and "object" for unlinked list node.
Linear list has a top element and terminated with a null pointer.
template <SLink<T> T::* LinkMember>
struct LinearAlgo
{
static SLink<T> & Link(T *obj) { return obj->*LinkMember; }
// obj -> null
static void Init(T *obj); // obj!=0 unlinked
// place -> obj -> next -> ... -> null
static void InsNext(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
static T * DelNext(T *place); // place!=0 linked, return obj
Link() returns the reference to the link from the node pointer.
Init() makes the single element list from the given object.
InsNext() inserts the given object after the given element in the list.
DelNext() deletes the element after the given place in the list. The pointer to the object is returned (it can be null).
There are three inner types: Cur, Top and FirstLast.
// ptr -> next -> ... -> null
struct Cur
{
T *ptr;
// constructors
explicit Cur(T *ptr_) : ptr(ptr_) {}
// object ptr
T * operator + () const { return ptr; }
bool operator ! () const { return !ptr; }
T & operator * () const { return *ptr; }
T * operator -> () const { return ptr; }
// cursor
void operator ++ () { ptr=Link(ptr).next; }
};
Cur is a list Cursor. Its constructor takes the pointer to the top element of the list. In fact, it may be any element or null pointer.
// top -> next -> ... -> null
struct Top
{
T *top;
// constructors
Top() { init(); }
// methods
void init() { top=0; }
T * operator + () const { return top; }
bool operator ! () const { return !top; }
Cur start() const { return Cur(top); }
// insert object
void ins(T *obj); // obj!=0 unlinked
void ins_after(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void ins_after(Cur cur,T *obj); // +cur, obj!=0 unlinked
// delete object
T * del();
};
Top is a list controller. It contains the pointer to the top element of the list.
init() initialize the list as the empty list.
operator + and operator ! can be used to determine if the list is empty.
start() returns a cursor on the full list.
ins() inserts the given object to the list, as the top element.
ins_after() inserts the given object to the list after the given position.
del() deletes the top element from the list, the pointer to the object is returned (it can be null).
// first -> next -> ... -> last -> null
struct FirstLast
{
T *first;
T *last;
// constructors
FirstLast() { init(); }
// methods
void init();
T * operator + () const { return first; }
bool operator ! () const { return !first; }
Cur start() const { return Cur(first); }
// insert object
void ins_first(T *obj); // obj!=0 unlinked
void ins_last(T *obj); // obj!=0 unlinked
void ins_after(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void ins_after(Cur cur,T *obj); // +cur, obj!=0 unlinked
// delete object
T * del_first();
};
};
FirstLast is another list controller. It contains two pointers: one to the first element of the list, and the second to the last. We call the top element first in this case.
init() initialize the list as the empty list.
operator + and operator ! can be used to determine if the list is empty.
start() returns a cursor on the full list.
ins_first() inserts the given object to the list, as the first element.
ins_last() inserts the given object to the list, as the last element.
ins_after() inserts the given object to the list after the given position.
del_first() deletes the first element from the list, the pointer to the object is returned (it can be null).
Circular list has a top element, the bottom element points to the top. We call the last element bottom in this case.
template <SLink<T> T::* LinkMember>
struct CircularAlgo
{
static SLink<T> & Link(T *obj) { return obj->*LinkMember; }
// obj -> obj
static void Init(T *obj); // obj!=0 unlinked
// place -> obj -> next -> ... -> place
static void InsNext(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
static T * DelNext(T *place); // place!=0 linked
Link() returns the reference to the link from the node pointer.
Init() makes the single element list from the given object.
InsNext() inserts the given object after the given element in the list.
DelNext() deletes the element after the given place in the list. The pointer to the object is returned (it will be null, if the list has only one element).
These methods are logically the same as for linear lists, except they operate on circular ones.
There are two inner types: Cur and Top.
// ptr -> next -> ... -> bottom
struct Cur
{
T *ptr;
T *bottom;
// constructors
explicit Cur(T *bottom);
// object ptr
T * operator + () const { return ptr; }
bool operator ! () const { return !ptr; }
T & operator * () const { return *ptr; }
T * operator -> () const { return ptr; }
// cursor
void operator ++ ();
};
Cur is a list Cursor. Its constructor takes the pointer to the bottom element of the list.
// bottom -> top -> next -> ... -> bottom
struct Top
{
T *bottom;
// constructors
Top() { init(); }
// methods
void init() { bottom=0; }
T * operator + () const { return bottom; }
bool operator ! () const { return !bottom; }
Cur start() const { return Cur(bottom); }
// insert object
void ins(T *obj); // obj!=0 unlinked
void ins_after(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void ins_after(Cur &cur,T *obj); // +cur, obj!=0 unlinked
// delete object
T * del();
// rotate
T * rotate() // return top element moved to bottom
};
};
Top is a list controller. It contains the pointer to the bottom element of the list.
init() initialize the list as the empty list.
operator + and operator ! can be used to determine if the list is empty.
start() returns a cursor on the full list.
ins() inserts the given object to the list, as the top element.
ins_after() inserts the given object to the list after the given position. If the place is given by the cursor, then the cursor is also updated, so you can continue use it.
del() deletes the top element from the list, the pointer to the object is returned (it can be null).
The last method rotate() is specific for circular lists. It rotates the list. The top element moves to bottom. Pointer to this element is returned.
Linear list has a top element and terminated with null pointers. Double link allows to move forward and backward.
template <DLink<T> T::* LinkMember>
struct LinearAlgo
{
static DLink<T> & Link(T *obj) { return obj->*LinkMember; }
// Connect...()
static void Connect(T *a,T *b);
static void Connect_null(T *a,T *b); // a,b may == 0
static void Connect_nulla(T *a,T *b); // a may == 0
static void Connect_nullb(T *a,T *b); // b may == 0
static void Connect_nulla(T *a,T *b,T *c); // a may == 0
static void Connect_nullc(T *a,T *b,T *c); // c may == 0
static void Connect_nullac(T *a,T *b,T *c); // a,c may == 0
// null <- obj -> null
static void Init(T *obj); // obj!=0 unlinked
// place -> obj -> next -> ... -> null
static void InsNext(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
// null <- ... <- prev <- obj <- place
static void InsPrev(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
// null <- ... <- prev <- obj -> next -> ... -> null
static void Del(T *obj); // obj!=0 linked
// place -> obj -> next -> ... -> null
static T * DelNext(T *place); // place!=0 linked
// null <- ... <- prev <- obj <- place
static T * DelPrev(T *place); // place!=0 linked
// null <- top -> next -> ... -> null
static T * /* top */ InsTop(T *top,T *obj); // obj!=0 unlinked
// null <- top -> ... -> obj -> ... -> null
static T * /* top */ DelTop(T *top,T *obj); // obj!=0 linked
// null <- ... <- place -> ... -> null
static void ReplaceNode(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
Connect...() is a family of functions, they connect its arguments in a row. Functions with the suffix null... accept null value for correspondent arguments.
Init() makes the single element list from the given object.
InsNext() inserts the given object after the given element in the list.
InsPrev() inserts the given object before the given element in the list.
Del() deletes the given element from the list.
DelNext() deletes the element after the given place in the list. The pointer to the object is returned (it can be null).
DelPrev() deletes the element before the given place in the list. The pointer to the object is returned (it can be null).
InsTop() inserts the given object as the top element of the list. The new top element is returned.
DelTop() deletes the given element from the list. The new top element is returned. The element may be any element from the list. The name of this function may be misleading, it does not delete the top element.
ReplaceNode() replaces the given list element with the given object. The object becomes a member of the list, the element becomes unlinked.
There are four inner types: Cur, RevCur, Top and FirstLast.
// ptr -> next -> ... -> null
struct Cur
{
T *ptr;
// constructors
explicit Cur(T *ptr_) : ptr(ptr_) {}
// object ptr
T * operator + () const { return ptr; }
bool operator ! () const { return !ptr; }
T & operator * () const { return *ptr; }
T * operator -> () const { return ptr; }
// cursor
void operator ++ () { ptr=Link(ptr).next; }
void operator -- () { ptr=Link(ptr).prev; }
};
Cur is a list forward Cursor. Its constructor takes the pointer to the first element of the list. In fact, it may be any element or null pointer.
// null <- ... <- prev <- ptr
struct RevCur
{
T *ptr;
// constructors
explicit RevCur(T *ptr_) : ptr(ptr_) {}
// object ptr
T * operator + () const { return ptr; }
bool operator ! () const { return !ptr; }
T & operator * () const { return *ptr; }
T * operator -> () const { return ptr; }
// cursor
void operator ++ () { ptr=Link(ptr).prev; }
void operator -- () { ptr=Link(ptr).next; }
};
RevCur is a list backward Cursor. Its constructor takes the pointer to the last element of the list. In fact, it may be any element or null pointer.
// null <- top -> next -> ... -> null
struct Top
{
T *top;
// constructors
Top() { init(); }
// methods
void init() { top=0; }
T * operator + () const { return top; }
bool operator ! () const { return !top; }
Cur start() const { return Cur(top); }
// insert object
void ins(T *obj); // obj!=0 unlinked
void ins_before(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void ins_after(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void replace(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
void ins_before(Cur cur,T *obj); // +cur, obj!=0 unlinked
void ins_after(Cur cur,T *obj); // +cur, obj!=0 unlinked
void replace(Cur &cur,T *obj); // +cur, obj!=0 unlinked
// delete object
void del(T *obj); // obj!=0 from the list
T * del();
T * del_and_move(Cur &cur); // +cur
};
Top is a list controller. It contains the pointer to the top element of the list.
init() initialize the list as the empty list.
operator + and operator ! can be used to determine if the list is empty.
start() returns a forward cursor on the full list.
ins() inserts the given object to the list, as the top element.
ins_before() inserts the given object to the list before the given position.
ins_after() inserts the given object to the list after the given position.
replace() replaces the given list element with the given object. The object becomes a member of the list, the element becomes unlinked.
replace(<cursor>) replaces the list element at the current cursor position with the given object. The object becomes a member of the list, the element becomes unlinked. Cursor is updated properly (it will point to the object).
del(T *obj) deletes the given element from the list.
del() deletes the top element from the list, the pointer to the object is returned (it can be null).
del_and_move() deletes the element from the list at the current cursor position and moves the cursor to the next element. The pointer to the object is returned.
// null <- first -> next -> ... -> last -> null
struct FirstLast
{
T *first;
T *last;
// constructors
FirstLast() { init(); }
// methods
void init();
T * operator + () const { return first; }
bool operator ! () const { return !first; }
Cur start() const { return Cur(first); }
RevCur start_rev() const { return RevCur(last); }
// insert object
void ins_first(T *obj); // obj!=0 unlinked
void ins_last(T *obj); // obj!=0 unlinked
void ins_before(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void ins_after(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void replace(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
void ins_before(Cur cur,T *obj); // +cur, obj!=0 unlinked
void ins_before(RevCur cur,T *obj); // +cur, obj!=0 unlinked
void ins_after(Cur cur,T *obj); // +cur, obj!=0 unlinked
void ins_after(RevCur cur,T *obj); // +cur, obj!=0 unlinked
void replace(Cur &cur,T *obj); // +cur, obj!=0 unlinked
void replace(RevCur &cur,T *obj); // +cur, obj!=0 unlinked
// delete object
void del(T *obj); // obj!=0 from the list
T * del_first();
T * del_last();
T * del_and_move(Cur &cur); // +cur
T * del_and_move(RevCur &cur); // +cur
};
};
FirstLast is another list controller. It contains two pointers: one to the first element of the list, and the second to the last. We call the top element first in this case.
init() initialize the list as the empty list.
operator + and operator ! can be used to determine if the list is empty.
start() returns a forward cursor on the full list.
start_rev() returns a backward cursor on the full list (i.e. it points to the last element).
ins_first() inserts the given object to the list, as the first element.
ins_last() inserts the given object to the list, as the last element.
ins_before() inserts the given object to the list before the given position.
ins_after() inserts the given object to the list after the given position.
replace() replaces the given list element with the given object. The object becomes a member of the list, the element becomes unlinked.
replace(<cursor>) replaces the list element at the current cursor position with the given object. The object becomes a member of the list, the element becomes unlinked. Cursor is updated properly (it will point to the object).
del(T *obj) deletes the given element from the list.
del_first() deletes the first element from the list, the pointer to the object is returned.
del_last() deletes the last element from the list, the pointer to the object is returned.
del_and_move() deletes the element from the list at the current cursor position and moves the cursor. The pointer to the object is returned. If the cursor is forward, it moves to the next element. If the cursor is backward, it moves to the previous element. I.e. each cursor type moves to the next position in respect to the cursor movement direction.
Circular list has a top element, the last element is linked to the top. Double link allows to move forward and backward.
template <DLink<T> T::* LinkMember>
struct CircularAlgo
{
static DLink<T> & Link(T *obj) { return obj->*LinkMember; }
// Connect()
static void Connect(T *a,T *b);
static void Connect(T *a,T *b,T *c);
// obj <- obj -> obj
static void Init(T *obj); // obj!=0 unlinked
// place -> obj -> next -> ... -> place
static void InsNext(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
// place <- ... <- prev <- obj <- place
static void InsPrev(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
// ... <- prev <- obj -> next -> ...
static void Del(T *obj); // obj!=0 linked
// place -> obj -> next -> ... -> place
static T * DelNext(T *place); // place!=0 linked
// place <- ... <- prev <- obj <- place
static T * DelPrev(T *place); // place!=0 linked
// top -> next -> ... -> last -> top
static T * /* top */ InsTopFirst(T *top,T *obj); // obj!=0 unlinked
// top -> next -> ... -> last -> top
static T * /* top */ InsTopLast(T *top,T *obj); // obj!=0 unlinked
// top -> ... -> obj -> ... -> last -> top
static T * /* top */ DelTop(T *top,T *obj); // obj!=0 linked
// top <- ... <- place -> ... -> top
static void ReplaceNode(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
Connect...() is a family of functions, they connect its arguments in a row.
Init() makes the single element list from the given object.
InsNext() inserts the given object after the given element in the list.
InsPrev() inserts the given object before the given element in the list.
Del() deletes the given element from the list.
DelNext() deletes the element after the given place in the list. The pointer to the object is returned (it will be null, if the list has only one element).
DelPrev() deletes the element before the given place in the list. The pointer to the object is returned (it will be null, if the list has only one element).
InsTopFirst() inserts the given object as the first element of the list. The new top element is returned.
InsTopLast() inserts the given object as the last element of the list. The new top element is returned.
DelTop() deletes the given element from the list. The new top element is returned. The element may be any element from the list. The name of this function may be misleading, it does not delete the top element.
ReplaceNode() replaces the given list element with the given object. The object becomes a member of the list, the element becomes unlinked.
There are three inner types: Cur, RevCur, Top.
// ptr -> next -> ... -> last
struct Cur
{
T *ptr;
T *last;
// constructors
explicit Cur(T *ptr);
// object ptr
T * operator + () const { return ptr; }
bool operator ! () const { return !ptr; }
T & operator * () const { return *ptr; }
T * operator -> () const { return ptr; }
// cursor
void operator ++ ();
void operator -- ();
// insert object
void ins_after(T *obj); // +, obj!=0 unlinked
};
Cur is a list forward Cursor. Its constructor takes the pointer to the first element of the list.
There is the additional method ins_after(). This method inserts the given object into the list after the current (non-null) position.
// first <- ... <- prev <- ptr
struct RevCur
{
T *ptr;
T *first;
// constructors
explicit RevCur(T *first);
// object ptr
T * operator + () const { return ptr; }
bool operator ! () const { return !ptr; }
T & operator * () const { return *ptr; }
T * operator -> () const { return ptr; }
// cursor
void operator ++ ();
void operator -- ();
// insert object
void ins_after(T *obj); // +, obj!=0 unlinked
};
RevCur is a list backward Cursor. Its constructor takes the pointer to the first element of the list.
There is the additional method ins_after(). This method inserts the given object into the list after (before with respect to the cursor direction) the current (non-null) position.
// top -> ... -> obj -> ... -> last -> top
struct Top
{
T *top;
// constructors
Top() { init(); }
// methods
void init() { top=0; }
T * operator + () const { return top; }
bool operator ! () const { return !top; }
Cur start() const { return Cur(top); }
RevCur start_rev() const { return RevCur(top); }
// insert object
void ins_first(T *obj); // obj!=0 unlinked
void ins_last(T *obj); // obj!=0 unlinked
void ins_before(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void ins_after(T *pos,T *obj); // pos!=0, obj!=0 unlinked
void replace(T *place,T *obj); // place!=0 linked, obj!=0 unlinked
void ins_before(Cur cur,T *obj); // +cur, obj!=0 unlinked
void ins_after(Cur &cur,T *obj); // +cur, obj!=0 unlinked
void ins_before(RevCur &cur,T *obj); // +cur, obj!=0 unlinked
void ins_after(RevCur cur,T *obj); // +cur, obj!=0 unlinked
void replace(Cur &cur,T *obj); // +cur, obj!=0 unlinked
void replace(RevCur &cur,T *obj); // +cur, obj!=0 unlinked
// delete object
void del(T *obj); // obj!=0 from the list
T * del_first();
T * del_last();
T * del_and_move(Cur &cur); // +cur
T * del_and_move(RevCur &cur); // +cur
// rotate
T * rotate_forward(); // return top element moved to bottom
T * rotate_backward(); // return bottom element moved to top
};
};
Top is a list controller. It contains the pointer to the top element of the list.
init() initialize the list as the empty list.
operator + and operator ! can be used to determine if the list is empty.
start() returns a forward cursor on the full list.
start_rev() returns a backward cursor on the full list (i.e. it points to the last element).
ins_first() inserts the given object to the list, as the first element.
ins_last() inserts the given object to the list, as the last element.
ins_before() inserts the given object to the list before the given position. ins_before(RevCur &cur,T *obj) modifies the cursor to keep one valid.
ins_after() inserts the given object to the list after the given position. ins_after(Cur &cur,T *obj) modifies the cursor to keep one valid.
replace() replaces the given list element with the given object. The object becomes a member of the list, the element becomes unlinked.
replace(<cursor>) replaces the list element at the current cursor position with the given object. The object becomes a member of the list, the element becomes unlinked. Cursor is updated properly (it will point to the object).
del() deletes the given element from the list.
del_first() deletes the first element from the list, the pointer to the object is returned.
del_last() deletes the last element from the list, the pointer to the object is returned.
del_and_move() deletes the element from the list at the current cursor position and moves the cursor. The pointer to the object is returned. If the cursor is forward, it moves to the next element. If the cursor is backward, it moves to the previous element. I.g. each cursor type moves to the next position in respect to the cursor movement direction.
The last two methods rotate...() are specific for circular lists. They rotate the list.
rotate_forward() rotates the list forward. The top element moves to bottom. Pointer to this element is returned.
rotate_backward() rotates the list backward. The bottom element moves to top. Pointer to this element is returned.