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