blob: 168885531b918f4312fef57bc6f953d47efdedbb (
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
// slang-internally-linked-list.h
#ifndef SLANG_INTERNALLY_LINKED_LIST_H
#define SLANG_INTERNALLY_LINKED_LIST_H
// This file provides support for the idiom of a linked
// list of values where the "next" pointer is stored in
// the values themselves (thus requiring no additional
// allocation for list nodes, at the price of any given
// value only being able to appear in a single list).
#include "slang-basic.h"
namespace Slang
{
/// A linked list where the elements are themselves the nodes.
///
/// The type parameter `T` should be a type that publicly
/// inherits from `InternallyLinkedList<T>::Node`.
///
template<typename T>
struct InternallyLinkedList
{
public:
struct Node
{
public:
Node() {}
private:
friend struct InternallyLinkedList<T>;
T* _next = nullptr;
};
struct Iterator
{
public:
Iterator() {}
Iterator(T* node)
: _node(node)
{
}
T* operator*() const { return _node; }
void operator++() { _node = static_cast<Node const*>(_node)->_next; }
bool operator!=(Iterator const& that) const { return _node != that._node; }
private:
T* _node = nullptr;
};
Iterator begin() { return Iterator(_first); }
Iterator end() { return Iterator(); }
T* getFirst() const { return _first; }
T* getLast() const { return _last; }
void add(T* element)
{
SLANG_ASSERT(element != nullptr);
if (!_last)
{
SLANG_ASSERT(_first == nullptr);
_first = element;
_last = element;
}
else
{
SLANG_ASSERT(_first != nullptr);
_last->_next = element;
_last = element;
}
}
void insertAfter(T* existingElement, T* newElement)
{
SLANG_ASSERT(existingElement != nullptr);
SLANG_ASSERT(newElement != nullptr);
if (existingElement == _last)
{
add(newElement);
}
else
{
newElement->_next = existingElement->_next;
existingElement->_next = newElement;
}
}
void append(InternallyLinkedList<T> const& other)
{
if (!other._first)
{
}
else if (!_last)
{
_first = other._first;
_last = other._last;
}
else
{
SLANG_ASSERT(_first != nullptr);
_last->_next = other._first;
_last = other._last;
}
}
private:
T* _first = nullptr;
T* _last = nullptr;
};
template<typename T>
using InternallyLinkedListNode = InternallyLinkedList<T>::Node;
} // namespace Slang
#endif
|
