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
15namespace FSShell {
16
17
18// DoublyLinkedListLink
19template<typename Element>
20class DoublyLinkedListLink {
21public:
22	DoublyLinkedListLink() : next(NULL), previous(NULL) {}
23	~DoublyLinkedListLink() {}
24
25	Element	*next;
26	Element	*previous;
27};
28
29// DoublyLinkedListLinkImpl
30template<typename Element>
31class DoublyLinkedListLinkImpl {
32private:
33	typedef DoublyLinkedListLink<Element> DLL_Link;
34
35public:
36	DoublyLinkedListLinkImpl() : fDoublyLinkedListLink() {}
37	~DoublyLinkedListLinkImpl() {}
38
39	DLL_Link *GetDoublyLinkedListLink()
40		{ return &fDoublyLinkedListLink; }
41	const DLL_Link *GetDoublyLinkedListLink() const
42		{ return &fDoublyLinkedListLink; }
43
44private:
45	DLL_Link	fDoublyLinkedListLink;
46};
47
48// DoublyLinkedListStandardGetLink
49template<typename Element>
50class DoublyLinkedListStandardGetLink {
51private:
52	typedef DoublyLinkedListLink<Element> Link;
53
54public:
55	inline Link *operator()(Element *element) const
56	{
57		return element->GetDoublyLinkedListLink();
58	}
59
60	inline const Link *operator()(const Element *element) const
61	{
62		return element->GetDoublyLinkedListLink();
63	}
64};
65
66// DoublyLinkedListMemberGetLink
67template<typename Element,
68	DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
69class DoublyLinkedListMemberGetLink {
70private:
71	typedef DoublyLinkedListLink<Element> Link;
72
73public:
74	inline Link *operator()(Element *element) const
75	{
76		return &(element->*LinkMember);
77	}
78
79	inline const Link *operator()(const Element *element) const
80	{
81		return &(element->*LinkMember);
82	}
83};
84
85// DoublyLinkedListCLink - interface to struct list
86template<typename Element>
87class DoublyLinkedListCLink {
88	private:
89		typedef DoublyLinkedListLink<Element> Link;
90
91	public:
92		inline Link *operator()(Element *element) const
93		{
94			return (Link *)&element->link;
95		}
96
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
109template<typename Element,
110	typename GetLink = DoublyLinkedListStandardGetLink<Element> >
111class DoublyLinkedList {
112private:
113	typedef DoublyLinkedList<Element, GetLink>	List;
114	typedef DoublyLinkedListLink<Element>		Link;
115
116public:
117	class Iterator {
118	public:
119		Iterator(List *list)
120			:
121			fList(list)
122		{
123			Rewind();
124		}
125
126		Iterator(const Iterator &other)
127		{
128			*this = other;
129		}
130
131		bool HasNext() const
132		{
133			return fNext;
134		}
135
136		Element *Next()
137		{
138			fCurrent = fNext;
139			if (fNext)
140				fNext = fList->GetNext(fNext);
141			return fCurrent;
142		}
143
144		Element *Current()
145		{
146			return fCurrent;
147		}
148
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
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:
181		ConstIterator(const List *list)
182			:
183			fList(list)
184		{
185			Rewind();
186		}
187
188		ConstIterator(const ConstIterator &other)
189		{
190			*this = other;
191		}
192
193		bool HasNext() const
194		{
195			return fNext;
196		}
197
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
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:
225		ReverseIterator(List *list)
226			:
227			fList(list)
228		{
229			Rewind();
230		}
231
232		ReverseIterator(const ReverseIterator &other)
233		{
234			*this = other;
235		}
236
237		bool HasNext() const
238		{
239			return fNext;
240		}
241
242		Element *Next()
243		{
244			fCurrent = fNext;
245			if (fNext)
246				fNext = fList->GetPrevious(fNext);
247			return fCurrent;
248		}
249
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
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:
282		ConstReverseIterator(const List *list)
283			:
284			fList(list)
285		{
286			Rewind();
287		}
288
289		ConstReverseIterator(const ConstReverseIterator &other)
290		{
291			*this = other;
292		}
293
294		bool HasNext() const
295		{
296			return fNext;
297		}
298
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
314		void Rewind()
315		{
316			fNext = fList->Last();
317		}
318
319	private:
320		const List	*fList;
321		Element		*fNext;
322	};
323
324public:
325	DoublyLinkedList() : fFirst(NULL), fLast(NULL) {}
326	~DoublyLinkedList() {}
327
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();
341	inline void MakeEmpty()				{ RemoveAll(); }
342
343	inline Element *First() const		{ return fFirst; }
344	inline Element *Last() const		{ return fLast; }
345
346	inline Element *Head() const		{ return fFirst; }
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
357	inline Iterator GetIterator()				{ return Iterator(this); }
358	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
359
360	inline ReverseIterator GetReverseIterator()
361		{ return ReverseIterator(this); }
362	inline ConstReverseIterator GetReverseIterator() const
363		{ return ConstReverseIterator(this); }
364
365private:
366	inline void Insert(Element* before, Element* element);
367		// TODO: Obsolete! Use InsertBefore() instead!
368
369private:
370	Element	*fFirst;
371	Element	*fLast;
372
373	static GetLink	sGetLink;
374};
375
376
377// inline methods
378
379// Insert
380DOUBLY_LINKED_LIST_TEMPLATE_LIST
381void
382DOUBLY_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
410DOUBLY_LINKED_LIST_TEMPLATE_LIST
411void
412DOUBLY_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
435DOUBLY_LINKED_LIST_TEMPLATE_LIST
436void
437DOUBLY_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
460DOUBLY_LINKED_LIST_TEMPLATE_LIST
461void
462DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
463{
464	InsertBefore(before, element);
465}
466
467
468// Add
469DOUBLY_LINKED_LIST_TEMPLATE_LIST
470void
471DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back)
472{
473	Insert(element, back);
474}
475
476// Remove
477DOUBLY_LINKED_LIST_TEMPLATE_LIST
478void
479DOUBLY_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
497DOUBLY_LINKED_LIST_TEMPLATE_LIST
498void
499DOUBLY_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
520DOUBLY_LINKED_LIST_TEMPLATE_LIST
521void
522DOUBLY_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
539DOUBLY_LINKED_LIST_TEMPLATE_LIST
540void
541DOUBLY_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
555DOUBLY_LINKED_LIST_TEMPLATE_LIST
556Element *
557DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
558{
559	Element *element = Head();
560	Remove(element);
561	return element;
562}
563
564// GetPrevious
565DOUBLY_LINKED_LIST_TEMPLATE_LIST
566Element *
567DOUBLY_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
576DOUBLY_LINKED_LIST_TEMPLATE_LIST
577Element *
578DOUBLY_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
587DOUBLY_LINKED_LIST_TEMPLATE_LIST
588int32_t
589DOUBLY_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
598DOUBLY_LINKED_LIST_TEMPLATE_LIST
599GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
600
601
602}	// namespace FSShell
603
604using FSShell::DoublyLinkedListLink;
605using FSShell::DoublyLinkedListLinkImpl;
606using FSShell::DoublyLinkedListStandardGetLink;
607using FSShell::DoublyLinkedListMemberGetLink;
608using FSShell::DoublyLinkedListCLink;
609using FSShell::DoublyLinkedList;
610
611
612#endif	/* __cplusplus */
613
614#endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
615