1// SLList.h
2
3#ifndef SL_LIST_H
4#define SL_LIST_H
5
6#include <SupportDefs.h>
7
8namespace UserlandFSUtil {
9
10// SLListLink
11template<typename Element>
12class SLListLink {
13public:
14	SLListLink() : next(NULL) {}
15	~SLListLink() {}
16
17	Element	*next;
18};
19
20// SLListLinkImpl
21template<typename Element>
22class SLListLinkImpl {
23private:
24	typedef SLListLink<Element> Link;
25
26public:
27	SLListLinkImpl() : fSLListLink()	{}
28	~SLListLinkImpl()					{}
29
30	Link *GetSLListLink()				{ return &fSLListLink; }
31	const Link *GetSLListLink() const	{ return &fSLListLink; }
32
33private:
34	Link	fSLListLink;
35};
36
37// SLListStandardGetLink
38template<typename Element>
39class SLListStandardGetLink {
40private:
41	typedef SLListLink<Element> Link;
42
43public:
44	inline Link *operator()(Element *element) const
45	{
46		return element->GetSLListLink();
47	}
48
49	inline const Link *operator()(const Element *element) const
50	{
51		return element->GetSLListLink();
52	}
53};
54
55// for convenience
56#define SL_LIST_TEMPLATE_LIST template<typename Element, typename GetLink>
57#define SL_LIST_CLASS_NAME SLList<Element, GetLink>
58
59// SLList
60template<typename Element, typename GetLink = SLListStandardGetLink<Element> >
61class SLList {
62private:
63	typedef SLList<Element, GetLink>	List;
64	typedef SLListLink<Element>			Link;
65
66public:
67	class Iterator {
68	public:
69		Iterator(List *list)
70			: fList(list),
71			  fPrevious(NULL),
72			  fCurrent(NULL),
73			  fNext(fList->GetFirst())
74		{
75		}
76
77		Iterator(const Iterator &other)
78		{
79			*this = other;
80		}
81
82		bool HasNext() const
83		{
84			return fNext;
85		}
86
87		Element *Next()
88		{
89			if (fCurrent)
90				fPrevious = fCurrent;
91
92			fCurrent = fNext;
93
94			if (fNext)
95				fNext = fList->GetNext(fNext);
96
97			return fCurrent;
98		}
99
100		Element *Remove()
101		{
102			Element *element = fCurrent;
103			if (fCurrent) {
104				fList->_Remove(fPrevious, fCurrent);
105				fCurrent = NULL;
106			}
107			return element;
108		}
109
110		Iterator &operator=(const Iterator &other)
111		{
112			fList = other.fList;
113			fPrevious = other.fPrevious;
114			fCurrent = other.fCurrent;
115			fNext = other.fNext;
116			return *this;
117		}
118
119	private:
120		List	*fList;
121		Element *fPrevious;
122		Element	*fCurrent;
123		Element	*fNext;
124	};
125
126	class ConstIterator {
127	public:
128		ConstIterator(const List *list)
129			: fList(list),
130			  fNext(list->GetFirst())
131		{
132		}
133
134		ConstIterator(const ConstIterator &other)
135		{
136			*this = other;
137		}
138
139		bool HasNext() const
140		{
141			return fNext;
142		}
143
144		Element *Next()
145		{
146			Element *element = fNext;
147			if (fNext)
148				fNext = fList->GetNext(fNext);
149			return element;
150		}
151
152		ConstIterator &operator=(const ConstIterator &other)
153		{
154			fList = other.fList;
155			fNext = other.fNext;
156			return *this;
157		}
158
159	private:
160		const List	*fList;
161		Element		*fNext;
162	};
163
164public:
165	SLList() : fFirst(NULL), fLast(NULL) {}
166	SLList(const GetLink &getLink)
167		: fFirst(NULL), fLast(NULL), fGetLink(getLink) {}
168	~SLList() {}
169
170	inline bool IsEmpty() const			{ return (fFirst == NULL); }
171
172	inline void Insert(Element *element, bool back = true);
173	inline void InsertAfter(Element *previous, Element *element);
174	inline void Remove(Element *element);
175		// O(n)!
176
177	inline void MoveFrom(SL_LIST_CLASS_NAME *fromList);
178
179	inline void RemoveAll();
180
181	inline Element *GetFirst() const	{ return fFirst; }
182	inline Element *GetLast() const		{ return fLast; }
183
184	inline Element *GetHead() const		{ return fFirst; }
185	inline Element *GetTail() const		{ return fLast; }
186
187	inline Element *GetNext(Element *element) const;
188
189	inline int32 Size() const;
190		// O(n)!
191
192	inline Iterator GetIterator()				{ return Iterator(this); }
193	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
194
195private:
196	friend class Iterator;
197
198	inline void _Remove(Element *previous, Element *element);
199
200private:
201	Element	*fFirst;
202	Element	*fLast;
203	GetLink	fGetLink;
204};
205
206}	// namespace UserlandFSUtil
207
208using UserlandFSUtil::SLList;
209using UserlandFSUtil::SLListLink;
210using UserlandFSUtil::SLListLinkImpl;
211
212
213// inline methods
214
215// Insert
216SL_LIST_TEMPLATE_LIST
217void
218SL_LIST_CLASS_NAME::Insert(Element *element, bool back)
219{
220	InsertAfter((back ? fLast : NULL), element);
221}
222
223// InsertAfter
224SL_LIST_TEMPLATE_LIST
225void
226SL_LIST_CLASS_NAME::InsertAfter(Element *previous, Element *element)
227{
228	if (element) {
229		Link *elLink = fGetLink(element);
230		if (previous) {
231			// insert after previous element
232			Link *prevLink = fGetLink(previous);
233			elLink->next = prevLink->next;
234			prevLink->next = element;
235		} else {
236			// no previous element given: prepend
237			elLink->next = fFirst;
238			fFirst = element;
239		}
240
241		// element may be new last element
242		if (fLast == previous)
243			fLast = element;
244	}
245}
246
247// Remove
248SL_LIST_TEMPLATE_LIST
249void
250SL_LIST_CLASS_NAME::Remove(Element *element)
251{
252	if (!element)
253		return;
254
255	for (Iterator it = GetIterator(); it.HasNext();) {
256		if (element == it.Next()) {
257			it.Remove();
258			return;
259		}
260	}
261}
262
263// MoveFrom
264SL_LIST_TEMPLATE_LIST
265void
266SL_LIST_CLASS_NAME::MoveFrom(SL_LIST_CLASS_NAME *fromList)
267{
268	if (fromList && fromList->fFirst) {
269		if (fFirst) {
270			fGetLink(fLast)->next = fromList->fFirst;
271			fLast = fromList->fLast;
272		} else {
273			fFirst = fromList->fFirst;
274			fLast = fromList->fLast;
275		}
276		fromList->fFirst = NULL;
277		fromList->fLast = NULL;
278	}
279}
280
281// RemoveAll
282SL_LIST_TEMPLATE_LIST
283void
284SL_LIST_CLASS_NAME::RemoveAll()
285{
286	Element *element = fFirst;
287	while (element) {
288		Link *elLink = fGetLink(element);
289		element = elLink->next;
290		elLink->next = NULL;
291	}
292	fFirst = NULL;
293	fLast = NULL;
294}
295
296// GetNext
297SL_LIST_TEMPLATE_LIST
298Element *
299SL_LIST_CLASS_NAME::GetNext(Element *element) const
300{
301	return (element ? fGetLink(element)->next : NULL);
302}
303
304// _Remove
305SL_LIST_TEMPLATE_LIST
306void
307SL_LIST_CLASS_NAME::_Remove(Element *previous, Element *element)
308{
309	Link *elLink = fGetLink(element);
310	if (previous)
311		fGetLink(previous)->next = elLink->next;
312	else
313		fFirst = elLink->next;
314
315	if (element == fLast)
316		fLast = previous;
317
318	elLink->next = NULL;
319}
320
321// Size
322SL_LIST_TEMPLATE_LIST
323int32
324SL_LIST_CLASS_NAME::Size() const
325{
326	int32 count = 0;
327	for (Element* element = GetFirst(); element; element = GetNext(element))
328		count++;
329	return count;
330}
331
332#endif	// SL_LIST_H
333