1 // SLList.h
2
3 #ifndef SL_LIST_H
4 #define SL_LIST_H
5
6 #include <SupportDefs.h>
7
8 namespace UserlandFSUtil {
9
10 // SLListLink
11 template<typename Element>
12 class SLListLink {
13 public:
SLListLink()14 SLListLink() : next(NULL) {}
~SLListLink()15 ~SLListLink() {}
16
17 Element *next;
18 };
19
20 // SLListLinkImpl
21 template<typename Element>
22 class SLListLinkImpl {
23 private:
24 typedef SLListLink<Element> Link;
25
26 public:
SLListLinkImpl()27 SLListLinkImpl() : fSLListLink() {}
~SLListLinkImpl()28 ~SLListLinkImpl() {}
29
GetSLListLink()30 Link *GetSLListLink() { return &fSLListLink; }
GetSLListLink()31 const Link *GetSLListLink() const { return &fSLListLink; }
32
33 private:
34 Link fSLListLink;
35 };
36
37 // SLListStandardGetLink
38 template<typename Element>
39 class SLListStandardGetLink {
40 private:
41 typedef SLListLink<Element> Link;
42
43 public:
operator()44 inline Link *operator()(Element *element) const
45 {
46 return element->GetSLListLink();
47 }
48
operator()49 inline const Link *operator()(const Element *element) const
50 {
51 return element->GetSLListLink();
52 }
53 };
54
55 // for convenience
56 #define SL_LIST_TEMPLATE_LIST template<typename Element, typename GetLink>
57 #define SL_LIST_CLASS_NAME SLList<Element, GetLink>
58
59 // SLList
60 template<typename Element, typename GetLink = SLListStandardGetLink<Element> >
61 class SLList {
62 private:
63 typedef SLList<Element, GetLink> List;
64 typedef SLListLink<Element> Link;
65
66 public:
67 class Iterator {
68 public:
Iterator(List * list)69 Iterator(List *list)
70 : fList(list),
71 fPrevious(NULL),
72 fCurrent(NULL),
73 fNext(fList->GetFirst())
74 {
75 }
76
Iterator(const Iterator & other)77 Iterator(const Iterator &other)
78 {
79 *this = other;
80 }
81
HasNext()82 bool HasNext() const
83 {
84 return fNext;
85 }
86
Next()87 Element *Next()
88 {
89 if (fCurrent)
90 fPrevious = fCurrent;
91
92 fCurrent = fNext;
93
94 if (fNext)
95 fNext = fList->GetNext(fNext);
96
97 return fCurrent;
98 }
99
Remove()100 Element *Remove()
101 {
102 Element *element = fCurrent;
103 if (fCurrent) {
104 fList->_Remove(fPrevious, fCurrent);
105 fCurrent = NULL;
106 }
107 return element;
108 }
109
110 Iterator &operator=(const Iterator &other)
111 {
112 fList = other.fList;
113 fPrevious = other.fPrevious;
114 fCurrent = other.fCurrent;
115 fNext = other.fNext;
116 return *this;
117 }
118
119 private:
120 List *fList;
121 Element *fPrevious;
122 Element *fCurrent;
123 Element *fNext;
124 };
125
126 class ConstIterator {
127 public:
ConstIterator(const List * list)128 ConstIterator(const List *list)
129 : fList(list),
130 fNext(list->GetFirst())
131 {
132 }
133
ConstIterator(const ConstIterator & other)134 ConstIterator(const ConstIterator &other)
135 {
136 *this = other;
137 }
138
HasNext()139 bool HasNext() const
140 {
141 return fNext;
142 }
143
Next()144 Element *Next()
145 {
146 Element *element = fNext;
147 if (fNext)
148 fNext = fList->GetNext(fNext);
149 return element;
150 }
151
152 ConstIterator &operator=(const ConstIterator &other)
153 {
154 fList = other.fList;
155 fNext = other.fNext;
156 return *this;
157 }
158
159 private:
160 const List *fList;
161 Element *fNext;
162 };
163
164 public:
SLList()165 SLList() : fFirst(NULL), fLast(NULL) {}
SLList(const GetLink & getLink)166 SLList(const GetLink &getLink)
167 : fFirst(NULL), fLast(NULL), fGetLink(getLink) {}
~SLList()168 ~SLList() {}
169
IsEmpty()170 inline bool IsEmpty() const { return (fFirst == NULL); }
171
172 inline void Insert(Element *element, bool back = true);
173 inline void InsertAfter(Element *previous, Element *element);
174 inline void Remove(Element *element);
175 // O(n)!
176
177 inline void MoveFrom(SL_LIST_CLASS_NAME *fromList);
178
179 inline void RemoveAll();
180
GetFirst()181 inline Element *GetFirst() const { return fFirst; }
GetLast()182 inline Element *GetLast() const { return fLast; }
183
GetHead()184 inline Element *GetHead() const { return fFirst; }
GetTail()185 inline Element *GetTail() const { return fLast; }
186
187 inline Element *GetNext(Element *element) const;
188
189 inline int32 Size() const;
190 // O(n)!
191
GetIterator()192 inline Iterator GetIterator() { return Iterator(this); }
GetIterator()193 inline ConstIterator GetIterator() const { return ConstIterator(this); }
194
195 private:
196 friend class Iterator;
197
198 inline void _Remove(Element *previous, Element *element);
199
200 private:
201 Element *fFirst;
202 Element *fLast;
203 GetLink fGetLink;
204 };
205
206 } // namespace UserlandFSUtil
207
208 using UserlandFSUtil::SLList;
209 using UserlandFSUtil::SLListLink;
210 using UserlandFSUtil::SLListLinkImpl;
211
212
213 // inline methods
214
215 // Insert
216 SL_LIST_TEMPLATE_LIST
217 void
Insert(Element * element,bool back)218 SL_LIST_CLASS_NAME::Insert(Element *element, bool back)
219 {
220 InsertAfter((back ? fLast : NULL), element);
221 }
222
223 // InsertAfter
224 SL_LIST_TEMPLATE_LIST
225 void
InsertAfter(Element * previous,Element * element)226 SL_LIST_CLASS_NAME::InsertAfter(Element *previous, Element *element)
227 {
228 if (element) {
229 Link *elLink = fGetLink(element);
230 if (previous) {
231 // insert after previous element
232 Link *prevLink = fGetLink(previous);
233 elLink->next = prevLink->next;
234 prevLink->next = element;
235 } else {
236 // no previous element given: prepend
237 elLink->next = fFirst;
238 fFirst = element;
239 }
240
241 // element may be new last element
242 if (fLast == previous)
243 fLast = element;
244 }
245 }
246
247 // Remove
248 SL_LIST_TEMPLATE_LIST
249 void
Remove(Element * element)250 SL_LIST_CLASS_NAME::Remove(Element *element)
251 {
252 if (!element)
253 return;
254
255 for (Iterator it = GetIterator(); it.HasNext();) {
256 if (element == it.Next()) {
257 it.Remove();
258 return;
259 }
260 }
261 }
262
263 // MoveFrom
264 SL_LIST_TEMPLATE_LIST
265 void
MoveFrom(SL_LIST_CLASS_NAME * fromList)266 SL_LIST_CLASS_NAME::MoveFrom(SL_LIST_CLASS_NAME *fromList)
267 {
268 if (fromList && fromList->fFirst) {
269 if (fFirst) {
270 fGetLink(fLast)->next = fromList->fFirst;
271 fLast = fromList->fLast;
272 } else {
273 fFirst = fromList->fFirst;
274 fLast = fromList->fLast;
275 }
276 fromList->fFirst = NULL;
277 fromList->fLast = NULL;
278 }
279 }
280
281 // RemoveAll
282 SL_LIST_TEMPLATE_LIST
283 void
RemoveAll()284 SL_LIST_CLASS_NAME::RemoveAll()
285 {
286 Element *element = fFirst;
287 while (element) {
288 Link *elLink = fGetLink(element);
289 element = elLink->next;
290 elLink->next = NULL;
291 }
292 fFirst = NULL;
293 fLast = NULL;
294 }
295
296 // GetNext
297 SL_LIST_TEMPLATE_LIST
298 Element *
GetNext(Element * element)299 SL_LIST_CLASS_NAME::GetNext(Element *element) const
300 {
301 return (element ? fGetLink(element)->next : NULL);
302 }
303
304 // _Remove
305 SL_LIST_TEMPLATE_LIST
306 void
_Remove(Element * previous,Element * element)307 SL_LIST_CLASS_NAME::_Remove(Element *previous, Element *element)
308 {
309 Link *elLink = fGetLink(element);
310 if (previous)
311 fGetLink(previous)->next = elLink->next;
312 else
313 fFirst = elLink->next;
314
315 if (element == fLast)
316 fLast = previous;
317
318 elLink->next = NULL;
319 }
320
321 // Size
322 SL_LIST_TEMPLATE_LIST
323 int32
Size()324 SL_LIST_CLASS_NAME::Size() const
325 {
326 int32 count = 0;
327 for (Element* element = GetFirst(); element; element = GetNext(element))
328 count++;
329 return count;
330 }
331
332 #endif // SL_LIST_H
333