1/*
2 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Copyright 2005-2006, Ingo Weinhold, bonefish@users.sf.net. All rights reserved.
4 *
5 * Distributed under the terms of the MIT License.
6 */
7#ifndef KERNEL_UTIL_SINGLY_LINKED_LIST_H
8#define KERNEL_UTIL_SINGLY_LINKED_LIST_H
9
10
11#include "fssh_types.h"
12
13
14#ifdef __cplusplus
15
16
17namespace FSShell {
18
19// SinglyLinkedListLink
20template<typename Element>
21class SinglyLinkedListLink {
22public:
23	SinglyLinkedListLink() : next(NULL) {}
24	~SinglyLinkedListLink() {}
25
26	Element* next;
27};
28
29// SinglyLinkedListLinkImpl
30template<typename Element>
31class SinglyLinkedListLinkImpl {
32private:
33	typedef SinglyLinkedListLink<Element> SLL_Link;
34
35public:
36	SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {}
37	~SinglyLinkedListLinkImpl() {}
38
39	SLL_Link* GetSinglyLinkedListLink()
40		{ return &fSinglyLinkedListLink; }
41	const SLL_Link* GetSinglyLinkedListLink() const
42		{ return &fSinglyLinkedListLink; }
43
44private:
45	SLL_Link	fSinglyLinkedListLink;
46};
47
48// SinglyLinkedListStandardGetLink
49template<typename Element>
50class SinglyLinkedListStandardGetLink {
51private:
52	typedef SinglyLinkedListLink<Element> Link;
53
54public:
55	inline Link* operator()(Element* element) const
56	{
57		return element->GetSinglyLinkedListLink();
58	}
59
60	inline const Link* operator()(const Element* element) const
61	{
62		return element->GetSinglyLinkedListLink();
63	}
64};
65
66// SinglyLinkedListMemberGetLink
67template<typename Element,
68	SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
69class SinglyLinkedListMemberGetLink {
70private:
71	typedef SinglyLinkedListLink<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
86// for convenience
87#define SINGLY_LINKED_LIST_TEMPLATE_LIST \
88	template<typename Element, typename GetLink>
89#define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink>
90
91
92template<typename Element,
93	typename GetLink = SinglyLinkedListStandardGetLink<Element> >
94class SinglyLinkedList {
95	private:
96		typedef SinglyLinkedList<Element, GetLink> List;
97		typedef SinglyLinkedListLink<Element> Link;
98
99	public:
100		class Iterator {
101			public:
102				Iterator(const List* list)
103					:
104					fList(list)
105				{
106					Rewind();
107				}
108
109				Iterator(const Iterator& other)
110				{
111					*this = other;
112				}
113
114				bool HasNext() const
115				{
116					return fNext;
117				}
118
119				Element* Next()
120				{
121					Element* element = fNext;
122					if (fNext)
123						fNext = fList->GetNext(fNext);
124					return element;
125				}
126
127				Iterator& operator=(const Iterator& other)
128				{
129					fList = other.fList;
130					fNext = other.fNext;
131					return* this;
132				}
133
134				void Rewind()
135				{
136					fNext = fList->First();
137				}
138
139			private:
140				const List*	fList;
141				Element*	fNext;
142		};
143
144	public:
145		SinglyLinkedList() : fFirst(NULL) {}
146		~SinglyLinkedList() {}
147
148		inline bool IsEmpty() const		{ return (fFirst == NULL); }
149
150		inline void Add(Element* element);
151		inline void Remove(Element* element);
152
153		inline void RemoveAll();
154		inline void MakeEmpty()			{ RemoveAll(); }
155
156		inline Element* First() const { return fFirst; }
157		inline Element* Head() const { return fFirst; }
158
159		inline Element* RemoveHead();
160
161		inline Element* GetNext(Element* element) const;
162
163		inline int32_t Size() const;
164			// O(n)!
165
166		inline Iterator GetIterator() const	{ return Iterator(this); }
167
168	private:
169		Element	*fFirst;
170
171		static GetLink	sGetLink;
172};
173
174
175// inline methods
176
177// Add
178SINGLY_LINKED_LIST_TEMPLATE_LIST
179void
180SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element)
181{
182	if (element != NULL) {
183		sGetLink(element)->next = fFirst;
184		fFirst = element;
185	}
186}
187
188// Remove
189SINGLY_LINKED_LIST_TEMPLATE_LIST
190void
191SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
192{
193	if (element == NULL)
194		return;
195
196	Element* next = fFirst;
197	Element* last = NULL;
198	while (next != NULL && element != next) {
199		last = next;
200		next = sGetLink(next)->next;
201	}
202
203	Link* elementLink = sGetLink(element);
204	if (last == NULL)
205		fFirst = elementLink->next;
206	else
207		sGetLink(last)->next = elementLink->next;
208
209	elementLink->next = NULL;
210}
211
212// RemoveAll
213SINGLY_LINKED_LIST_TEMPLATE_LIST
214void
215SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll()
216{
217	Element* element = fFirst;
218	while (element) {
219		Link* elLink = sGetLink(element);
220		element = elLink->next;
221		elLink->next = NULL;
222	}
223	fFirst = NULL;
224}
225
226// RemoveHead
227SINGLY_LINKED_LIST_TEMPLATE_LIST
228Element*
229SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead()
230{
231	Element* element = Head();
232	Remove(element);
233	return element;
234}
235
236// GetNext
237SINGLY_LINKED_LIST_TEMPLATE_LIST
238Element*
239SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
240{
241	Element* result = NULL;
242	if (element)
243		result = sGetLink(element)->next;
244	return result;
245}
246
247// Size
248SINGLY_LINKED_LIST_TEMPLATE_LIST
249int32_t
250SINGLY_LINKED_LIST_CLASS_NAME::Size() const
251{
252	int32_t count = 0;
253	for (Element* element = First(); element; element = GetNext(element))
254		count++;
255	return count;
256}
257
258// sGetLink
259SINGLY_LINKED_LIST_TEMPLATE_LIST
260GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink;
261
262}	// namespace FSShell
263
264using FSShell::SinglyLinkedListLink;
265using FSShell::SinglyLinkedListLinkImpl;
266using FSShell::SinglyLinkedListStandardGetLink;
267using FSShell::SinglyLinkedListMemberGetLink;
268using FSShell::SinglyLinkedList;
269
270#endif	// __cplusplus
271
272#endif	// _KERNEL_UTIL_SINGLY_LINKED_LIST_H
273