1 /*
2 * Copyright 2005-2007, Ingo Weinhold, bonefish@users.sf.net. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
5 #ifndef KERNEL_UTIL_DOUBLY_LINKED_LIST_H
6 #define KERNEL_UTIL_DOUBLY_LINKED_LIST_H
7
8
9 #include "fssh_types.h"
10
11
12 #ifdef __cplusplus
13
14
15 namespace FSShell {
16
17
18 // DoublyLinkedListLink
19 template<typename Element>
20 class DoublyLinkedListLink {
21 public:
DoublyLinkedListLink()22 DoublyLinkedListLink() : next(NULL), previous(NULL) {}
~DoublyLinkedListLink()23 ~DoublyLinkedListLink() {}
24
25 Element *next;
26 Element *previous;
27 };
28
29 // DoublyLinkedListLinkImpl
30 template<typename Element>
31 class DoublyLinkedListLinkImpl {
32 private:
33 typedef DoublyLinkedListLink<Element> DLL_Link;
34
35 public:
DoublyLinkedListLinkImpl()36 DoublyLinkedListLinkImpl() : fDoublyLinkedListLink() {}
~DoublyLinkedListLinkImpl()37 ~DoublyLinkedListLinkImpl() {}
38
GetDoublyLinkedListLink()39 DLL_Link *GetDoublyLinkedListLink()
40 { return &fDoublyLinkedListLink; }
GetDoublyLinkedListLink()41 const DLL_Link *GetDoublyLinkedListLink() const
42 { return &fDoublyLinkedListLink; }
43
44 private:
45 DLL_Link fDoublyLinkedListLink;
46 };
47
48 // DoublyLinkedListStandardGetLink
49 template<typename Element>
50 class DoublyLinkedListStandardGetLink {
51 private:
52 typedef DoublyLinkedListLink<Element> Link;
53
54 public:
operator()55 inline Link *operator()(Element *element) const
56 {
57 return element->GetDoublyLinkedListLink();
58 }
59
operator()60 inline const Link *operator()(const Element *element) const
61 {
62 return element->GetDoublyLinkedListLink();
63 }
64 };
65
66 // DoublyLinkedListMemberGetLink
67 template<typename Element,
68 DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
69 class DoublyLinkedListMemberGetLink {
70 private:
71 typedef DoublyLinkedListLink<Element> Link;
72
73 public:
operator()74 inline Link *operator()(Element *element) const
75 {
76 return &(element->*LinkMember);
77 }
78
operator()79 inline const Link *operator()(const Element *element) const
80 {
81 return &(element->*LinkMember);
82 }
83 };
84
85 // DoublyLinkedListCLink - interface to struct list
86 template<typename Element>
87 class DoublyLinkedListCLink {
88 private:
89 typedef DoublyLinkedListLink<Element> Link;
90
91 public:
operator()92 inline Link *operator()(Element *element) const
93 {
94 return (Link *)&element->link;
95 }
96
operator()97 inline const Link *operator()(const Element *element) const
98 {
99 return (const Link *)&element->link;
100 }
101 };
102
103 // for convenience
104 #define DOUBLY_LINKED_LIST_TEMPLATE_LIST \
105 template<typename Element, typename GetLink>
106 #define DOUBLY_LINKED_LIST_CLASS_NAME DoublyLinkedList<Element, GetLink>
107
108 // DoublyLinkedList
109 template<typename Element,
110 typename GetLink = DoublyLinkedListStandardGetLink<Element> >
111 class DoublyLinkedList {
112 private:
113 typedef DoublyLinkedList<Element, GetLink> List;
114 typedef DoublyLinkedListLink<Element> Link;
115
116 public:
117 class Iterator {
118 public:
Iterator(List * list)119 Iterator(List *list)
120 :
121 fList(list)
122 {
123 Rewind();
124 }
125
Iterator(const Iterator & other)126 Iterator(const Iterator &other)
127 {
128 *this = other;
129 }
130
HasNext()131 bool HasNext() const
132 {
133 return fNext;
134 }
135
Next()136 Element *Next()
137 {
138 fCurrent = fNext;
139 if (fNext)
140 fNext = fList->GetNext(fNext);
141 return fCurrent;
142 }
143
Current()144 Element *Current()
145 {
146 return fCurrent;
147 }
148
Remove()149 Element *Remove()
150 {
151 Element *element = fCurrent;
152 if (fCurrent) {
153 fList->Remove(fCurrent);
154 fCurrent = NULL;
155 }
156 return element;
157 }
158
159 Iterator &operator=(const Iterator &other)
160 {
161 fList = other.fList;
162 fCurrent = other.fCurrent;
163 fNext = other.fNext;
164 return *this;
165 }
166
Rewind()167 void Rewind()
168 {
169 fCurrent = NULL;
170 fNext = fList->First();
171 }
172
173 private:
174 List *fList;
175 Element *fCurrent;
176 Element *fNext;
177 };
178
179 class ConstIterator {
180 public:
ConstIterator(const List * list)181 ConstIterator(const List *list)
182 :
183 fList(list)
184 {
185 Rewind();
186 }
187
ConstIterator(const ConstIterator & other)188 ConstIterator(const ConstIterator &other)
189 {
190 *this = other;
191 }
192
HasNext()193 bool HasNext() const
194 {
195 return fNext;
196 }
197
Next()198 Element *Next()
199 {
200 Element *element = fNext;
201 if (fNext)
202 fNext = fList->GetNext(fNext);
203 return element;
204 }
205
206 ConstIterator &operator=(const ConstIterator &other)
207 {
208 fList = other.fList;
209 fNext = other.fNext;
210 return *this;
211 }
212
Rewind()213 void Rewind()
214 {
215 fNext = fList->First();
216 }
217
218 private:
219 const List *fList;
220 Element *fNext;
221 };
222
223 class ReverseIterator {
224 public:
ReverseIterator(List * list)225 ReverseIterator(List *list)
226 :
227 fList(list)
228 {
229 Rewind();
230 }
231
ReverseIterator(const ReverseIterator & other)232 ReverseIterator(const ReverseIterator &other)
233 {
234 *this = other;
235 }
236
HasNext()237 bool HasNext() const
238 {
239 return fNext;
240 }
241
Next()242 Element *Next()
243 {
244 fCurrent = fNext;
245 if (fNext)
246 fNext = fList->GetPrevious(fNext);
247 return fCurrent;
248 }
249
Remove()250 Element *Remove()
251 {
252 Element *element = fCurrent;
253 if (fCurrent) {
254 fList->Remove(fCurrent);
255 fCurrent = NULL;
256 }
257 return element;
258 }
259
260 ReverseIterator &operator=(const ReverseIterator &other)
261 {
262 fList = other.fList;
263 fCurrent = other.fCurrent;
264 fNext = other.fNext;
265 return *this;
266 }
267
Rewind()268 void Rewind()
269 {
270 fCurrent = NULL;
271 fNext = fList->Last();
272 }
273
274 private:
275 List *fList;
276 Element *fCurrent;
277 Element *fNext;
278 };
279
280 class ConstReverseIterator {
281 public:
ConstReverseIterator(const List * list)282 ConstReverseIterator(const List *list)
283 :
284 fList(list)
285 {
286 Rewind();
287 }
288
ConstReverseIterator(const ConstReverseIterator & other)289 ConstReverseIterator(const ConstReverseIterator &other)
290 {
291 *this = other;
292 }
293
HasNext()294 bool HasNext() const
295 {
296 return fNext;
297 }
298
Next()299 Element *Next()
300 {
301 Element *element = fNext;
302 if (fNext)
303 fNext = fList->GetPrevious(fNext);
304 return element;
305 }
306
307 ConstReverseIterator &operator=(const ConstReverseIterator &other)
308 {
309 fList = other.fList;
310 fNext = other.fNext;
311 return *this;
312 }
313
Rewind()314 void Rewind()
315 {
316 fNext = fList->Last();
317 }
318
319 private:
320 const List *fList;
321 Element *fNext;
322 };
323
324 public:
DoublyLinkedList()325 DoublyLinkedList() : fFirst(NULL), fLast(NULL) {}
~DoublyLinkedList()326 ~DoublyLinkedList() {}
327
IsEmpty()328 inline bool IsEmpty() const { return (fFirst == NULL); }
329
330 inline void InsertBefore(Element* insertBefore, Element* element);
331 inline void InsertAfter(Element* insertAfter, Element* element);
332 inline void Insert(Element* element, bool back = true);
333 inline void Add(Element *element, bool back = true);
334 inline void Remove(Element *element);
335
336 inline void Swap(Element *a, Element *b);
337
338 inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList);
339
340 inline void RemoveAll();
MakeEmpty()341 inline void MakeEmpty() { RemoveAll(); }
342
First()343 inline Element *First() const { return fFirst; }
Last()344 inline Element *Last() const { return fLast; }
345
Head()346 inline Element *Head() const { return fFirst; }
Tail()347 inline Element *Tail() const { return fLast; }
348
349 inline Element *RemoveHead();
350
351 inline Element *GetPrevious(Element *element) const;
352 inline Element *GetNext(Element *element) const;
353
354 inline int32_t Size() const;
355 // O(n)!
356
GetIterator()357 inline Iterator GetIterator() { return Iterator(this); }
GetIterator()358 inline ConstIterator GetIterator() const { return ConstIterator(this); }
359
GetReverseIterator()360 inline ReverseIterator GetReverseIterator()
361 { return ReverseIterator(this); }
GetReverseIterator()362 inline ConstReverseIterator GetReverseIterator() const
363 { return ConstReverseIterator(this); }
364
365 private:
366 inline void Insert(Element* before, Element* element);
367 // TODO: Obsolete! Use InsertBefore() instead!
368
369 private:
370 Element *fFirst;
371 Element *fLast;
372
373 static GetLink sGetLink;
374 };
375
376
377 // inline methods
378
379 // Insert
380 DOUBLY_LINKED_LIST_TEMPLATE_LIST
381 void
Insert(Element * element,bool back)382 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *element, bool back)
383 {
384 if (element) {
385 if (back) {
386 // append
387 Link *elLink = sGetLink(element);
388 elLink->previous = fLast;
389 elLink->next = NULL;
390 if (fLast)
391 sGetLink(fLast)->next = element;
392 else
393 fFirst = element;
394 fLast = element;
395 } else {
396 // prepend
397 Link *elLink = sGetLink(element);
398 elLink->previous = NULL;
399 elLink->next = fFirst;
400 if (fFirst)
401 sGetLink(fFirst)->previous = element;
402 else
403 fLast = element;
404 fFirst = element;
405 }
406 }
407 }
408
409
410 DOUBLY_LINKED_LIST_TEMPLATE_LIST
411 void
InsertBefore(Element * before,Element * element)412 DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element)
413 {
414 if (before == NULL) {
415 Insert(element);
416 return;
417 }
418 if (element == NULL)
419 return;
420
421 Link *beforeLink = sGetLink(before);
422 Link *link = sGetLink(element);
423
424 link->next = before;
425 link->previous = beforeLink->previous;
426 if (link->previous != NULL)
427 sGetLink(link->previous)->next = element;
428 beforeLink->previous = element;
429
430 if (fFirst == before)
431 fFirst = element;
432 }
433
434
435 DOUBLY_LINKED_LIST_TEMPLATE_LIST
436 void
InsertAfter(Element * after,Element * element)437 DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* after, Element* element)
438 {
439 ASSERT(element != NULL);
440
441 if (after == NULL) {
442 Insert(element, false);
443 return;
444 }
445
446 Link* afterLink = sGetLink(after);
447 Link* link = sGetLink(element);
448
449 link->previous = after;
450 link->next = afterLink->next;
451 afterLink->next = element;
452
453 if (link->next != NULL)
454 sGetLink(link->next)->previous = element;
455 else
456 fLast = element;
457 }
458
459
460 DOUBLY_LINKED_LIST_TEMPLATE_LIST
461 void
Insert(Element * before,Element * element)462 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
463 {
464 InsertBefore(before, element);
465 }
466
467
468 // Add
469 DOUBLY_LINKED_LIST_TEMPLATE_LIST
470 void
Add(Element * element,bool back)471 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back)
472 {
473 Insert(element, back);
474 }
475
476 // Remove
477 DOUBLY_LINKED_LIST_TEMPLATE_LIST
478 void
Remove(Element * element)479 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element *element)
480 {
481 if (element) {
482 Link *elLink = sGetLink(element);
483 if (elLink->previous)
484 sGetLink(elLink->previous)->next = elLink->next;
485 else
486 fFirst = elLink->next;
487 if (elLink->next)
488 sGetLink(elLink->next)->previous = elLink->previous;
489 else
490 fLast = elLink->previous;
491 elLink->previous = NULL;
492 elLink->next = NULL;
493 }
494 }
495
496 // Swap
497 DOUBLY_LINKED_LIST_TEMPLATE_LIST
498 void
Swap(Element * a,Element * b)499 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element *a, Element *b)
500 {
501 if (a && b && a != b) {
502 Element *aNext = sGetLink(a)->next;
503 Element *bNext = sGetLink(b)->next;
504 if (a == bNext) {
505 Remove(a);
506 Insert(b, a);
507 } else if (b == aNext) {
508 Remove(b);
509 Insert(a, b);
510 } else {
511 Remove(a);
512 Remove(b);
513 Insert(aNext, b);
514 Insert(bNext, a);
515 }
516 }
517 }
518
519 // MoveFrom
520 DOUBLY_LINKED_LIST_TEMPLATE_LIST
521 void
MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME * fromList)522 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList)
523 {
524 if (fromList && fromList->fFirst) {
525 if (fFirst) {
526 sGetLink(fLast)->next = fromList->fFirst;
527 sGetLink(fromList->fFirst)->previous = fLast;
528 fLast = fromList->fLast;
529 } else {
530 fFirst = fromList->fFirst;
531 fLast = fromList->fLast;
532 }
533 fromList->fFirst = NULL;
534 fromList->fLast = NULL;
535 }
536 }
537
538 // RemoveAll
539 DOUBLY_LINKED_LIST_TEMPLATE_LIST
540 void
RemoveAll()541 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
542 {
543 Element *element = fFirst;
544 while (element) {
545 Link *elLink = sGetLink(element);
546 element = elLink->next;
547 elLink->previous = NULL;
548 elLink->next = NULL;
549 }
550 fFirst = NULL;
551 fLast = NULL;
552 }
553
554 // RemoveHead
555 DOUBLY_LINKED_LIST_TEMPLATE_LIST
556 Element *
RemoveHead()557 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
558 {
559 Element *element = Head();
560 Remove(element);
561 return element;
562 }
563
564 // GetPrevious
565 DOUBLY_LINKED_LIST_TEMPLATE_LIST
566 Element *
GetPrevious(Element * element)567 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const
568 {
569 Element *result = NULL;
570 if (element)
571 result = sGetLink(element)->previous;
572 return result;
573 }
574
575 // GetNext
576 DOUBLY_LINKED_LIST_TEMPLATE_LIST
577 Element *
GetNext(Element * element)578 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const
579 {
580 Element *result = NULL;
581 if (element)
582 result = sGetLink(element)->next;
583 return result;
584 }
585
586 // Size
587 DOUBLY_LINKED_LIST_TEMPLATE_LIST
588 int32_t
Size()589 DOUBLY_LINKED_LIST_CLASS_NAME::Size() const
590 {
591 int32_t count = 0;
592 for (Element* element = First(); element; element = GetNext(element))
593 count++;
594 return count;
595 }
596
597 // sGetLink
598 DOUBLY_LINKED_LIST_TEMPLATE_LIST
599 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
600
601
602 } // namespace FSShell
603
604 using FSShell::DoublyLinkedListLink;
605 using FSShell::DoublyLinkedListLinkImpl;
606 using FSShell::DoublyLinkedListStandardGetLink;
607 using FSShell::DoublyLinkedListMemberGetLink;
608 using FSShell::DoublyLinkedListCLink;
609 using FSShell::DoublyLinkedList;
610
611
612 #endif /* __cplusplus */
613
614 #endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
615