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 Add(Element* element, bool back = true);
339	inline void Remove(Element* element);
340
341	inline void Swap(Element* a, Element* b);
342
343	inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList);
344
345	inline void RemoveAll();
346	inline void MakeEmpty()				{ RemoveAll(); }
347
348	inline Element* First() const		{ return fFirst; }
349	inline Element* Last() const		{ return fLast; }
350
351	inline Element* Head() const		{ return fFirst; }
352	inline Element* Tail() const		{ return fLast; }
353
354	inline Element* RemoveHead();
355	inline Element* RemoveTail();
356
357	static inline Element* GetPrevious(Element* element);
358	static inline Element* GetNext(Element* element);
359
360	inline bool Contains(Element* element) const;
361		// O(n)!
362
363	inline int32 Count() const;
364		// O(n)!
365
366	template<typename Less>
367	void Sort(const Less& less);
368		// O(n^2)
369
370	inline Iterator GetIterator()				{ return Iterator(this); }
371	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
372
373	inline ReverseIterator GetReverseIterator()
374		{ return ReverseIterator(this); }
375	inline ConstReverseIterator GetReverseIterator() const
376		{ return ConstReverseIterator(this); }
377
378private:
379	inline void Insert(Element* before, Element* element);
380		// TODO: Obsolete! Use InsertBefore() instead!
381
382private:
383	Element*		fFirst;
384	Element*		fLast;
385
386	static GetLink	sGetLink;
387};
388
389
390// inline methods
391
392// Insert
393DOUBLY_LINKED_LIST_TEMPLATE_LIST
394void
395DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* element, bool back)
396{
397	if (element) {
398#if DEBUG_DOUBLY_LINKED_LIST
399		ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
400			"list: %p\n", this);
401#endif
402
403		Link* elLink = sGetLink(element);
404		if (back) {
405			// append
406			elLink->previous = fLast;
407			elLink->next = NULL;
408			if (fLast)
409				sGetLink(fLast)->next = element;
410			else
411				fFirst = element;
412			fLast = element;
413		} else {
414			// prepend
415			elLink->previous = NULL;
416			elLink->next = fFirst;
417			if (fFirst)
418				sGetLink(fFirst)->previous = element;
419			else
420				fLast = element;
421			fFirst = element;
422		}
423	}
424}
425
426
427DOUBLY_LINKED_LIST_TEMPLATE_LIST
428void
429DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element)
430{
431	ASSERT(element != NULL);
432
433	if (before == NULL) {
434		Insert(element);
435		return;
436	}
437
438#if DEBUG_DOUBLY_LINKED_LIST
439	ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
440		"list: %p\n", this);
441#endif
442
443	Link* beforeLink = sGetLink(before);
444	Link* link = sGetLink(element);
445
446	link->next = before;
447	link->previous = beforeLink->previous;
448	beforeLink->previous = element;
449
450	if (link->previous != NULL)
451		sGetLink(link->previous)->next = element;
452	else
453		fFirst = element;
454}
455
456
457DOUBLY_LINKED_LIST_TEMPLATE_LIST
458void
459DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* after, Element* element)
460{
461	ASSERT(element != NULL);
462
463	if (after == NULL) {
464		Insert(element, false);
465		return;
466	}
467
468#if DEBUG_DOUBLY_LINKED_LIST
469	ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
470		"list: %p\n", this);
471#endif
472
473	Link* afterLink = sGetLink(after);
474	Link* link = sGetLink(element);
475
476	link->previous = after;
477	link->next = afterLink->next;
478	afterLink->next = element;
479
480	if (link->next != NULL)
481		sGetLink(link->next)->previous = element;
482	else
483		fLast = element;
484}
485
486
487DOUBLY_LINKED_LIST_TEMPLATE_LIST
488void
489DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
490{
491	InsertBefore(before, element);
492}
493
494
495// Add
496DOUBLY_LINKED_LIST_TEMPLATE_LIST
497void
498DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back)
499{
500	Insert(element, back);
501}
502
503// Remove
504DOUBLY_LINKED_LIST_TEMPLATE_LIST
505void
506DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
507{
508	if (element == NULL)
509		return;
510
511#if DEBUG_DOUBLY_LINKED_LIST
512	ASSERT_PRINT(fFirst != NULL && fLast != NULL
513		&& (fFirst != fLast || element == fFirst),
514		"list: %p, element: %p\n", this, element);
515#endif
516
517	Link* elLink = sGetLink(element);
518
519	if (element == fFirst)
520		fFirst = elLink->next;
521	else
522		sGetLink(elLink->previous)->next = elLink->next;
523
524	if (element == fLast)
525		fLast = elLink->previous;
526	else
527		sGetLink(elLink->next)->previous = elLink->previous;
528
529	elLink->next = elLink->previous = NULL;
530}
531
532// Swap
533DOUBLY_LINKED_LIST_TEMPLATE_LIST
534void
535DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b)
536{
537	if (a && b && a != b) {
538		Element* aNext = sGetLink(a)->next;
539		Element* bNext = sGetLink(b)->next;
540		if (a == bNext) {
541			Remove(a);
542			Insert(b, a);
543		} else if (b == aNext) {
544			Remove(b);
545			Insert(a, b);
546		} else {
547			Remove(a);
548			Remove(b);
549			Insert(aNext, b);
550			Insert(bNext, a);
551		}
552	}
553}
554
555// MoveFrom
556DOUBLY_LINKED_LIST_TEMPLATE_LIST
557void
558DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList)
559{
560	if (fromList && fromList->fFirst) {
561		if (fFirst) {
562			sGetLink(fLast)->next = fromList->fFirst;
563			sGetLink(fromList->fFirst)->previous = fLast;
564			fLast = fromList->fLast;
565		} else {
566			fFirst = fromList->fFirst;
567			fLast = fromList->fLast;
568		}
569		fromList->fFirst = NULL;
570		fromList->fLast = NULL;
571	}
572}
573
574// RemoveAll
575DOUBLY_LINKED_LIST_TEMPLATE_LIST
576void
577DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
578{
579	fFirst = NULL;
580	fLast = NULL;
581}
582
583// RemoveHead
584DOUBLY_LINKED_LIST_TEMPLATE_LIST
585Element*
586DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
587{
588	Element* element = Head();
589	Remove(element);
590	return element;
591}
592
593// RemoveTail
594DOUBLY_LINKED_LIST_TEMPLATE_LIST
595Element*
596DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail()
597{
598	Element* element = Tail();
599	Remove(element);
600	return element;
601}
602
603// GetPrevious
604DOUBLY_LINKED_LIST_TEMPLATE_LIST
605Element*
606DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element)
607{
608	Element* result = NULL;
609	if (element)
610		result = sGetLink(element)->previous;
611	return result;
612}
613
614// GetNext
615DOUBLY_LINKED_LIST_TEMPLATE_LIST
616Element*
617DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element)
618{
619	Element* result = NULL;
620	if (element)
621		result = sGetLink(element)->next;
622	return result;
623}
624
625
626DOUBLY_LINKED_LIST_TEMPLATE_LIST
627bool
628DOUBLY_LINKED_LIST_CLASS_NAME::Contains(Element* _element) const
629{
630	for (Element* element = First(); element; element = GetNext(element)) {
631		if (element == _element)
632			return true;
633	}
634
635	return false;
636}
637
638
639// Count
640DOUBLY_LINKED_LIST_TEMPLATE_LIST
641int32
642DOUBLY_LINKED_LIST_CLASS_NAME::Count() const
643{
644	int32 count = 0;
645	for (Element* element = First(); element; element = GetNext(element))
646		count++;
647	return count;
648}
649
650
651DOUBLY_LINKED_LIST_TEMPLATE_LIST
652template<typename Less>
653void
654DOUBLY_LINKED_LIST_CLASS_NAME::Sort(const Less& less)
655{
656	// selection sort
657	Element* tail = Head();
658	while (tail != NULL) {
659		Element* leastElement = tail;
660		Element* element = tail;
661		while ((element = GetNext(element)) != NULL) {
662			if (less(element, leastElement))
663				leastElement = element;
664		}
665
666		if (leastElement != tail) {
667			Remove(leastElement);
668			InsertBefore(tail, leastElement);
669		} else
670			tail = GetNext(tail);
671	}
672}
673
674
675// sGetLink
676DOUBLY_LINKED_LIST_TEMPLATE_LIST
677GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
678
679#endif	/* __cplusplus */
680
681#endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
682