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