blob: 1a029024330f5c7a43de39fb3c8b8ba9b779825b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#ifndef INTRUSIVE_LIST_H
#define INTRUSIVE_LIST_H
// TODO: Make this noncopyable.
template <typename T>
class ListHandle {
private:
ListHandle* prev;
ListHandle* next;
void insert_between(ListHandle& new_prev, ListHandle& new_next) {
if(new_prev.p == p || new_next.p == p) {
return;
}
// Remove this element from any previous position first.
prev->next = next;
next->prev = prev;
// Insert this element into new position.
prev = &new_prev;
next = &new_next;
prev->next = this;
next->prev = this;
}
public:
T* const p;
ListHandle(T* ptr) : prev(this), next(this), p(ptr) {}
ListHandle* get_prev() {
return prev;
}
ListHandle* get_next() {
return next;
}
void insert_before(ListHandle& node) {
insert_between(*node.prev, node);
}
void insert_after(ListHandle& node) {
insert_between(node, *node.next);
}
};
template <typename T>
class List {
private:
ListHandle<T> root;
public:
class Iterator {
private:
ListHandle<T>* h;
public:
Iterator(ListHandle<T>* handle) : h(handle) {}
ListHandle<T>* operator*() {
return h;
}
ListHandle<T>* operator->() {
return h;
}
bool operator==(const Iterator& i) {
return h == i.h;
}
bool operator!=(const Iterator& i) {
return h != i.h;
}
Iterator& operator++() {
h = h->get_next();
return *this;
}
};
List() : root(nullptr) {}
Iterator begin() {
return {root.get_next()};
}
Iterator end() {
return {&root};
}
bool empty() {
return begin() == end();
}
void append(ListHandle<T>& handle) {
//root.insert_before(&handle);
handle.insert_before(root);
}
};
#endif
|
