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