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
26template<typename Element>
27class DoublyLinkedListLink {
28public:
29	Element*	next;
30	Element*	previous;
31};
32
33// DoublyLinkedListLinkImpl
34template<typename Element>
35class DoublyLinkedListLinkImpl {
36private:
37	typedef DoublyLinkedListLink<Element> DLL_Link;
38
39public:
40	DLL_Link* GetDoublyLinkedListLink()
41		{ return &fDoublyLinkedListLink; }
42	const DLL_Link* GetDoublyLinkedListLink() const
43		{ return &fDoublyLinkedListLink; }
44
45private:
46	DLL_Link	fDoublyLinkedListLink;
47};
48
49// DoublyLinkedListStandardGetLink
50template<typename Element>
51class DoublyLinkedListStandardGetLink {
52private:
53	typedef DoublyLinkedListLink<Element> Link;
54
55public:
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
68template<typename Element,
69	DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
70class DoublyLinkedListMemberGetLink {
71private:
72	typedef DoublyLinkedListLink<Element> Link;
73
74public:
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
87template<typename Element>
88class 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
110template<typename Element,
111	typename GetLink = DoublyLinkedListStandardGetLink<Element> >
112class DoublyLinkedList {
113private:
114	typedef DoublyLinkedList<Element, GetLink>	List;
115	typedef DoublyLinkedListLink<Element>		Link;
116
117public:
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
329public:
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
380private:
381	Element*		fFirst;
382	Element*		fLast;
383
384	static GetLink	sGetLink;
385};
386
387
388// inline methods
389
390// Insert
391DOUBLY_LINKED_LIST_TEMPLATE_LIST
392void
393DOUBLY_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
426DOUBLY_LINKED_LIST_TEMPLATE_LIST
427void
428DOUBLY_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
456DOUBLY_LINKED_LIST_TEMPLATE_LIST
457void
458DOUBLY_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
494DOUBLY_LINKED_LIST_TEMPLATE_LIST
495void
496DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
497{
498	InsertBefore(before, element);
499}
500
501
502// Add
503DOUBLY_LINKED_LIST_TEMPLATE_LIST
504void
505DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back)
506{
507	Insert(element, back);
508}
509
510// Remove
511DOUBLY_LINKED_LIST_TEMPLATE_LIST
512void
513DOUBLY_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
535DOUBLY_LINKED_LIST_TEMPLATE_LIST
536void
537DOUBLY_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
558DOUBLY_LINKED_LIST_TEMPLATE_LIST
559void
560DOUBLY_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
577DOUBLY_LINKED_LIST_TEMPLATE_LIST
578void
579DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
580{
581	fFirst = NULL;
582	fLast = NULL;
583}
584
585// RemoveHead
586DOUBLY_LINKED_LIST_TEMPLATE_LIST
587Element*
588DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
589{
590	Element* element = Head();
591	Remove(element);
592	return element;
593}
594
595// RemoveTail
596DOUBLY_LINKED_LIST_TEMPLATE_LIST
597Element*
598DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail()
599{
600	Element* element = Tail();
601	Remove(element);
602	return element;
603}
604
605// GetPrevious
606DOUBLY_LINKED_LIST_TEMPLATE_LIST
607Element*
608DOUBLY_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
617DOUBLY_LINKED_LIST_TEMPLATE_LIST
618Element*
619DOUBLY_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
628DOUBLY_LINKED_LIST_TEMPLATE_LIST
629bool
630DOUBLY_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
642DOUBLY_LINKED_LIST_TEMPLATE_LIST
643int32
644DOUBLY_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
653DOUBLY_LINKED_LIST_TEMPLATE_LIST
654template<typename Less>
655void
656DOUBLY_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
678DOUBLY_LINKED_LIST_TEMPLATE_LIST
679GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
680
681#endif	/* __cplusplus */
682
683#endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
684