1/*
2 * Copyright 2008, Axel D��rfler, axeld@pinc-software.de. All rights reserved.
3 * Copyright 2005-2010, Ingo Weinhold, ingo_weinhold@gmx.de.
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 <SupportDefs.h>
12
13
14#ifdef __cplusplus
15
16// SinglyLinkedListLink
17template<typename Element>
18class SinglyLinkedListLink {
19public:
20	SinglyLinkedListLink() : next(NULL) {}
21	~SinglyLinkedListLink() {}
22
23	Element* next;
24};
25
26// SinglyLinkedListLinkImpl
27template<typename Element>
28class SinglyLinkedListLinkImpl {
29private:
30	typedef SinglyLinkedListLink<Element> SLL_Link;
31
32public:
33	SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {}
34	~SinglyLinkedListLinkImpl() {}
35
36	SLL_Link* GetSinglyLinkedListLink()
37		{ return &fSinglyLinkedListLink; }
38	const SLL_Link* GetSinglyLinkedListLink() const
39		{ return &fSinglyLinkedListLink; }
40
41private:
42	SLL_Link	fSinglyLinkedListLink;
43};
44
45// SinglyLinkedListStandardGetLink
46template<typename Element>
47class SinglyLinkedListStandardGetLink {
48private:
49	typedef SinglyLinkedListLink<Element> Link;
50
51public:
52	inline Link* operator()(Element* element) const
53	{
54		return element->GetSinglyLinkedListLink();
55	}
56
57	inline const Link* operator()(const Element* element) const
58	{
59		return element->GetSinglyLinkedListLink();
60	}
61};
62
63// SinglyLinkedListMemberGetLink
64template<typename Element,
65	SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
66class SinglyLinkedListMemberGetLink {
67private:
68	typedef SinglyLinkedListLink<Element> Link;
69
70public:
71	inline Link* operator()(Element* element) const
72	{
73		return &(element->*LinkMember);
74	}
75
76	inline const Link* operator()(const Element* element) const
77	{
78		return &(element->*LinkMember);
79	}
80};
81
82
83// for convenience
84#define SINGLY_LINKED_LIST_TEMPLATE_LIST \
85	template<typename Element, typename GetLink>
86#define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink>
87
88
89template<typename Element,
90	typename GetLink = SinglyLinkedListStandardGetLink<Element> >
91class SinglyLinkedList {
92	private:
93		typedef SinglyLinkedList<Element, GetLink> List;
94		typedef SinglyLinkedListLink<Element> Link;
95
96	public:
97		class Iterator {
98			public:
99				Iterator(const List* list)
100					:
101					fList(list)
102				{
103					Rewind();
104				}
105
106				Iterator(const Iterator& other)
107				{
108					*this = other;
109				}
110
111				bool HasNext() const
112				{
113					return fNext;
114				}
115
116				Element* Next()
117				{
118					Element* element = fNext;
119					if (fNext)
120						fNext = fList->GetNext(fNext);
121					return element;
122				}
123
124				Iterator& operator=(const Iterator& other)
125				{
126					fList = other.fList;
127					fNext = other.fNext;
128					return* this;
129				}
130
131				void Rewind()
132				{
133					fNext = fList->First();
134				}
135
136			private:
137				const List*	fList;
138				Element*	fNext;
139		};
140
141	public:
142		SinglyLinkedList() : fFirst(NULL) {}
143		~SinglyLinkedList() {}
144
145		inline bool IsEmpty() const		{ return (fFirst == NULL); }
146
147		inline void Add(Element* element);
148		inline bool Remove(Element* element);
149		inline void Remove(Element* previous, Element* element);
150
151		inline void MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList);
152			// O(1) if either list is empty, otherwise O(n).
153
154		inline void RemoveAll();
155		inline void MakeEmpty()			{ RemoveAll(); }
156
157		inline Element* First() const { return fFirst; }
158		inline Element* Head() const { return fFirst; }
159
160		inline Element* RemoveHead();
161
162		inline Element* GetNext(Element* element) const;
163
164		inline int32 Size() const;
165			// O(n)!
166
167		inline Iterator GetIterator() const	{ return Iterator(this); }
168
169	private:
170		Element	*fFirst;
171
172		static GetLink	sGetLink;
173};
174
175
176// inline methods
177
178// Add
179SINGLY_LINKED_LIST_TEMPLATE_LIST
180void
181SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element)
182{
183	if (element != NULL) {
184		sGetLink(element)->next = fFirst;
185		fFirst = element;
186	}
187}
188
189
190/*!	Removes \a element from the list.
191	It is safe to call the list with a \c NULL element or an element that isn't
192	in the list.
193	\param element The element to be removed.
194	\return \c true, if the element was in the list and has been removed,
195		\c false otherwise.
196*/
197SINGLY_LINKED_LIST_TEMPLATE_LIST
198bool
199SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
200{
201	if (element == NULL)
202		return false;
203
204	Element* next = fFirst;
205	Element* last = NULL;
206	while (element != next) {
207		if (next == NULL)
208			return false;
209		last = next;
210		next = sGetLink(next)->next;
211	}
212
213	Link* elementLink = sGetLink(element);
214	if (last == NULL)
215		fFirst = elementLink->next;
216	else
217		sGetLink(last)->next = elementLink->next;
218
219	elementLink->next = NULL;
220	return true;
221}
222
223
224SINGLY_LINKED_LIST_TEMPLATE_LIST
225void
226SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* previous, Element* element)
227{
228//	ASSERT(previous == NULL
229//		? fFirst == element : sGetLink(previous)->next == element);
230
231	Link* elementLink = sGetLink(element);
232	if (previous == NULL)
233		fFirst = elementLink->next;
234	else
235		sGetLink(previous)->next = elementLink->next;
236
237	elementLink->next = NULL;
238}
239
240
241SINGLY_LINKED_LIST_TEMPLATE_LIST
242void
243SINGLY_LINKED_LIST_CLASS_NAME::MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList)
244{
245	if (fromList->fFirst == NULL)
246		return;
247
248	if (fFirst == NULL) {
249		// This list is empty -- just transfer the head.
250		fFirst = fromList->fFirst;
251		fromList->fFirst = NULL;
252		return;
253	}
254
255	// Neither list is empty -- find the tail of this list.
256	Element* tail = fFirst;
257	while (Element* next = sGetLink(tail)->next)
258		tail = next;
259
260	sGetLink(tail)->next = fromList->fFirst;
261	fromList->fFirst = NULL;
262}
263
264
265// RemoveAll
266SINGLY_LINKED_LIST_TEMPLATE_LIST
267void
268SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll()
269{
270	Element* element = fFirst;
271	while (element) {
272		Link* elLink = sGetLink(element);
273		element = elLink->next;
274		elLink->next = NULL;
275	}
276	fFirst = NULL;
277}
278
279// RemoveHead
280SINGLY_LINKED_LIST_TEMPLATE_LIST
281Element*
282SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead()
283{
284	Element* element = Head();
285	Remove(element);
286	return element;
287}
288
289// GetNext
290SINGLY_LINKED_LIST_TEMPLATE_LIST
291Element*
292SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
293{
294	Element* result = NULL;
295	if (element)
296		result = sGetLink(element)->next;
297	return result;
298}
299
300// Size
301SINGLY_LINKED_LIST_TEMPLATE_LIST
302int32
303SINGLY_LINKED_LIST_CLASS_NAME::Size() const
304{
305	int32 count = 0;
306	for (Element* element = First(); element; element = GetNext(element))
307		count++;
308	return count;
309}
310
311// sGetLink
312SINGLY_LINKED_LIST_TEMPLATE_LIST
313GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink;
314
315#endif	/* __cplusplus */
316
317#endif	// _KERNEL_UTIL_SINGLY_LINKED_LIST_H
318