Created
December 8, 2015 01:34
-
-
Save sjswitzer/1f04d385e838bf1a4fb2 to your computer and use it in GitHub Desktop.
Intrusive list templates
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* LinkedList.h | |
*/ | |
#include <assert.h> | |
template <class C, int N=0> | |
class Linked | |
{ | |
Linked* m_next; | |
public: | |
Linked() : m_next(0) {} | |
class List | |
{ | |
Linked* m_head; | |
public: | |
List() : m_head(0) {} | |
class Range { | |
Linked* m_item; | |
public: | |
Range(const List& list) : m_item(list.m_head) {} | |
C* front() const { return static_cast<C*>(m_item); } | |
bool empty() const { return m_item == 0; } | |
void popFront() { m_item = m_item->m_next; } | |
}; | |
List& addFront(C *item_) { | |
Linked *item = item_; | |
assert(item->m_next == 0); | |
item->m_next = m_head; | |
m_head = item; | |
return *this; | |
} | |
C* removeFront() { | |
if (m_head == 0) | |
return 0; | |
Linked *item = m_head; | |
m_head = item->m_next; | |
return static_cast<C*>(item); | |
} | |
void remove(C *item_) { | |
Linked* item = item_; | |
for (Linked** p = &m_head; *p; p = &((*p)->m_next)) { | |
if (*p == item) { | |
*p = item->m_next; | |
item->m_next = 0; | |
return; | |
} | |
} | |
assert(!"item not in list"); | |
} | |
}; | |
}; | |
template <class C, int N=0> | |
class DblLinked | |
{ | |
DblLinked* m_next; | |
DblLinked* m_prev; | |
public: | |
DblLinked() : m_next(0), m_prev(0) {} | |
class List | |
{ | |
DblLinked* m_head; | |
DblLinked* m_tail; | |
public: | |
List() : m_head(0), m_tail(0) {} | |
class Range | |
{ | |
DblLinked* m_front; | |
DblLinked* m_back; | |
public: | |
Range(const List& list) : m_front(list.m_head), m_back(list.m_tail) {} | |
bool empty() const { return m_front == 0; } | |
C* front() const { return static_cast<C*>(m_front); } | |
void popFront() { m_front = m_front->m_next; if (!m_front) m_back = 0; } | |
C* back() const { return static_cast<C*>(m_back); } | |
void popBack() { m_back = m_back->m_prev; if (!m_back) m_front = 0; } | |
}; | |
List& addFront(C *item_) { | |
DblLinked *item = item_; | |
assert(item->m_next == 0 && item->m_prev == 0); | |
item->m_next = m_head; | |
if (m_head) | |
m_head->m_prev = item; | |
else | |
m_tail = item; | |
m_head = item; | |
return *this; | |
} | |
C* removeFront() { | |
if (m_head == 0) | |
return 0; | |
DblLinked *item = m_head; | |
m_head = item->m_next; | |
if (m_head) | |
m_head->m_prev = 0; | |
else | |
m_tail = 0; | |
return static_cast<C*>(item); | |
} | |
List& addBack(C *item_) { | |
DblLinked *item = item_; | |
assert(item->m_next == 0 && item->m_prev == 0); | |
item->m_prev = m_tail; | |
if (m_tail) | |
m_tail->m_next = item; | |
else | |
m_head = item; | |
m_tail = item; | |
return *this; | |
} | |
C* removeBack() { | |
if (m_tail == 0) | |
return 0; | |
DblLinked *item = m_tail; | |
m_tail = item->m_prev; | |
if (m_tail) | |
m_tail->m_next = 0; | |
else | |
m_head = 0; | |
return static_cast<C*>(item); | |
} | |
void remove(C *item_) { | |
DblLinked *item = item_; | |
assert((item->m_prev == 0) == (m_head == item)); | |
assert((item->m_next == 0) == (m_tail == item)); | |
if (item == m_head) { | |
m_head = item->m_next; | |
if (m_head) | |
m_head->m_prev = 0; | |
else | |
m_tail = 0; | |
} | |
else if (item == m_tail) { | |
m_tail = item->m_prev; | |
if (m_tail) | |
m_tail->m_next = 0; | |
else | |
m_head = 0; | |
} | |
else { | |
item->m_next->m_prev = item->m_prev; | |
item->m_prev->m_next = item->m_next; | |
} | |
item->m_next = item->m_prev = 0; | |
} | |
}; | |
}; | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include "LinkedList.h" | |
using namespace std; | |
struct Foo: public Linked<Foo>, public Linked<Foo,1>, public DblLinked<Foo>, public DblLinked<Foo,1> | |
{ | |
public: | |
Foo(const char *s) : s(s) {} | |
const char * const s; | |
}; | |
int main (int argc, char * const argv[]) { | |
Foo a("a"), b("b"), c("c"), d("d"); | |
Linked<Foo>::List list1; | |
Linked<Foo,1>::List list2; | |
DblLinked<Foo>::List list3; | |
DblLinked<Foo,1>::List list4; | |
list1.addFront(&a).addFront(&b).addFront(&c).addFront(&d); | |
list2.addFront(&a).addFront(&c).addFront(&b).addFront(&d); | |
list3.addFront(&a).addBack(&b).addFront(&c).addBack(&d); | |
list4.addFront(&a).addBack(&c).addFront(&b).addBack(&d); | |
cout << "list1:"; | |
for (Linked<Foo>::List::Range r(list1); !r.empty(); r.popFront()) | |
cout << " " << r.front()->s; | |
cout << endl; | |
cout << "removing \"c\"" << endl; | |
list1.remove(&c); | |
cout << "removing list1:"; | |
while (Foo* item = list1.removeFront()) | |
cout << " " << item->s; | |
cout << endl; | |
cout << "list2:"; | |
for (Linked<Foo,1>::List::Range r(list2); !r.empty(); r.popFront()) | |
cout << " " << r.front()->s; | |
cout << endl; | |
cout << "removing \"c\"" << endl; | |
list2.remove(&c); | |
cout << "removing list2:"; | |
while (Foo* item = list2.removeFront()) | |
cout << " " << item->s; | |
cout << endl; | |
cout << "list3:"; | |
for (DblLinked<Foo>::List::Range r(list3); !r.empty(); r.popFront()) | |
cout << " " << r.front()->s; | |
cout << endl; | |
cout << "list3 backward:"; | |
for (DblLinked<Foo>::List::Range r(list3); !r.empty(); r.popBack()) | |
cout << " " << r.back()->s; | |
cout << endl; | |
cout << "removing \"c\"" << endl; | |
list3.remove(&c); | |
cout << "removing list3:"; | |
while (Foo* item = list3.removeFront()) | |
cout << " " << item->s; | |
cout << endl; | |
cout << "list4:"; | |
for (DblLinked<Foo,1>::List::Range r(list4); !r.empty(); r.popFront()) | |
cout << " " << r.front()->s; | |
cout << endl; | |
cout << "list4 backward:"; | |
for (DblLinked<Foo,1>::List::Range r(list4); !r.empty(); r.popBack()) | |
cout << " " << r.back()->s; | |
cout << endl; | |
cout << "removing \"c\"" << endl; | |
list4.remove(&c); | |
cout << "removing list4 backward:"; | |
while (Foo* item = list4.removeBack()) | |
cout << " " << item->s; | |
cout << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Jiri Soukup wrote a whole book on how to implement intrusive lists in C++. In the end he resorted to writing a preprocessor to massage an augmented syntax into C++ because he didn't know about the CRTP.
This little doodle shows how to do it using plain old C++.