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 Insert(Element *element, bool back = true);
331	inline void Insert(Element *before, Element *element);
332	inline void Add(Element *element, bool back = true);
333	inline void Remove(Element *element);
334
335	inline void Swap(Element *a, Element *b);
336
337	inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList);
338
339	inline void RemoveAll();
340	inline void MakeEmpty()				{ RemoveAll(); }
341
342	inline Element *First() const		{ return fFirst; }
343	inline Element *Last() const		{ return fLast; }
344
345	inline Element *Head() const		{ return fFirst; }
346	inline Element *Tail() const		{ return fLast; }
347
348	inline Element *RemoveHead();
349
350	inline Element *GetPrevious(Element *element) const;
351	inline Element *GetNext(Element *element) const;
352
353	inline int32_t Size() const;
354		// O(n)!
355
356	inline Iterator GetIterator()				{ return Iterator(this); }
357	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
358
359	inline ReverseIterator GetReverseIterator()
360		{ return ReverseIterator(this); }
361	inline ConstReverseIterator GetReverseIterator() const
362		{ return ConstReverseIterator(this); }
363
364private:
365	Element	*fFirst;
366	Element	*fLast;
367
368	static GetLink	sGetLink;
369};
370
371
372// inline methods
373
374// Insert
375DOUBLY_LINKED_LIST_TEMPLATE_LIST
376void
377DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *element, bool back)
378{
379	if (element) {
380		if (back) {
381			// append
382			Link *elLink = sGetLink(element);
383			elLink->previous = fLast;
384			elLink->next = NULL;
385			if (fLast)
386				sGetLink(fLast)->next = element;
387			else
388				fFirst = element;
389			fLast = element;
390		} else {
391			// prepend
392			Link *elLink = sGetLink(element);
393			elLink->previous = NULL;
394			elLink->next = fFirst;
395			if (fFirst)
396				sGetLink(fFirst)->previous = element;
397			else
398				fLast = element;
399			fFirst = element;
400		}
401	}
402}
403
404// Insert
405DOUBLY_LINKED_LIST_TEMPLATE_LIST
406void
407DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *before, Element *element)
408{
409	if (before == NULL) {
410		Insert(element);
411		return;
412	}
413	if (element == NULL)
414		return;
415
416	Link *beforeLink = sGetLink(before);
417	Link *link = sGetLink(element);
418
419	link->next = before;
420	link->previous = beforeLink->previous;
421	if (link->previous != NULL)
422		sGetLink(link->previous)->next = element;
423	beforeLink->previous = element;
424
425	if (fFirst == before)
426		fFirst = element;
427}
428
429// Add
430DOUBLY_LINKED_LIST_TEMPLATE_LIST
431void
432DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back)
433{
434	Insert(element, back);
435}
436
437// Remove
438DOUBLY_LINKED_LIST_TEMPLATE_LIST
439void
440DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element *element)
441{
442	if (element) {
443		Link *elLink = sGetLink(element);
444		if (elLink->previous)
445			sGetLink(elLink->previous)->next = elLink->next;
446		else
447			fFirst = elLink->next;
448		if (elLink->next)
449			sGetLink(elLink->next)->previous = elLink->previous;
450		else
451			fLast = elLink->previous;
452		elLink->previous = NULL;
453		elLink->next = NULL;
454	}
455}
456
457// Swap
458DOUBLY_LINKED_LIST_TEMPLATE_LIST
459void
460DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element *a, Element *b)
461{
462	if (a && b && a != b) {
463		Element *aNext = sGetLink(a)->next;
464		Element *bNext = sGetLink(b)->next;
465		if (a == bNext) {
466			Remove(a);
467			Insert(b, a);
468		} else if (b == aNext) {
469			Remove(b);
470			Insert(a, b);
471		} else {
472			Remove(a);
473			Remove(b);
474			Insert(aNext, b);
475			Insert(bNext, a);
476		}
477	}
478}
479
480// MoveFrom
481DOUBLY_LINKED_LIST_TEMPLATE_LIST
482void
483DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList)
484{
485	if (fromList && fromList->fFirst) {
486		if (fFirst) {
487			sGetLink(fLast)->next = fromList->fFirst;
488			sGetLink(fromList->fFirst)->previous = fLast;
489			fLast = fromList->fLast;
490		} else {
491			fFirst = fromList->fFirst;
492			fLast = fromList->fLast;
493		}
494		fromList->fFirst = NULL;
495		fromList->fLast = NULL;
496	}
497}
498
499// RemoveAll
500DOUBLY_LINKED_LIST_TEMPLATE_LIST
501void
502DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
503{
504	Element *element = fFirst;
505	while (element) {
506		Link *elLink = sGetLink(element);
507		element = elLink->next;
508		elLink->previous = NULL;
509		elLink->next = NULL;
510	}
511	fFirst = NULL;
512	fLast = NULL;
513}
514
515// RemoveHead
516DOUBLY_LINKED_LIST_TEMPLATE_LIST
517Element *
518DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
519{
520	Element *element = Head();
521	Remove(element);
522	return element;
523}
524
525// GetPrevious
526DOUBLY_LINKED_LIST_TEMPLATE_LIST
527Element *
528DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const
529{
530	Element *result = NULL;
531	if (element)
532		result = sGetLink(element)->previous;
533	return result;
534}
535
536// GetNext
537DOUBLY_LINKED_LIST_TEMPLATE_LIST
538Element *
539DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const
540{
541	Element *result = NULL;
542	if (element)
543		result = sGetLink(element)->next;
544	return result;
545}
546
547// Size
548DOUBLY_LINKED_LIST_TEMPLATE_LIST
549int32_t
550DOUBLY_LINKED_LIST_CLASS_NAME::Size() const
551{
552	int32_t count = 0;
553	for (Element* element = First(); element; element = GetNext(element))
554		count++;
555	return count;
556}
557
558// sGetLink
559DOUBLY_LINKED_LIST_TEMPLATE_LIST
560GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
561
562
563}	// namespace FSShell
564
565using FSShell::DoublyLinkedListLink;
566using FSShell::DoublyLinkedListLinkImpl;
567using FSShell::DoublyLinkedListStandardGetLink;
568using FSShell::DoublyLinkedListMemberGetLink;
569using FSShell::DoublyLinkedListCLink;
570using FSShell::DoublyLinkedList;
571
572
573#endif	/* __cplusplus */
574
575#endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
576