1/*
2 * Copyright 2007, 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_DOUBLY_LINKED_QUEUE_H
8#define KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
9
10
11#include <util/DoublyLinkedList.h>
12
13
14/*!
15	A doubly linked queue is like a doubly linked list, but only has a pointer
16	to the head of the list, none to its tail.
17*/
18
19
20#ifdef __cplusplus
21
22// for convenience
23#define DOUBLY_LINKED_QUEUE_CLASS_NAME DoublyLinkedQueue<Element, GetLink>
24
25
26template<typename Element,
27	typename GetLink = DoublyLinkedListStandardGetLink<Element> >
28class DoublyLinkedQueue {
29private:
30	typedef DoublyLinkedQueue<Element, GetLink>	Queue;
31	typedef DoublyLinkedListLink<Element>		Link;
32
33public:
34	class Iterator {
35		public:
36			Iterator(Queue *queue)
37				:
38				fQueue(queue)
39			{
40				Rewind();
41			}
42
43			Iterator(const Iterator &other)
44			{
45				*this = other;
46			}
47
48			bool HasNext() const
49			{
50				return fNext;
51			}
52
53			Element *Next()
54			{
55				fCurrent = fNext;
56				if (fNext)
57					fNext = fQueue->GetNext(fNext);
58				return fCurrent;
59			}
60
61			Element *Remove()
62			{
63				Element *element = fCurrent;
64				if (fCurrent) {
65					fQueue->Remove(fCurrent);
66					fCurrent = NULL;
67				}
68				return element;
69			}
70
71			Iterator &operator=(const Iterator &other)
72			{
73				fQueue = other.fQueue;
74				fCurrent = other.fCurrent;
75				fNext = other.fNext;
76				return *this;
77			}
78
79			void Rewind()
80			{
81				fCurrent = NULL;
82				fNext = fQueue->First();
83			}
84
85		private:
86			Queue	*fQueue;
87			Element	*fCurrent;
88			Element	*fNext;
89	};
90
91	class ConstIterator {
92		public:
93			ConstIterator(const Queue *queue)
94				:
95				fQueue(queue)
96			{
97				Rewind();
98			}
99
100			ConstIterator(const ConstIterator &other)
101			{
102				*this = other;
103			}
104
105			bool HasNext() const
106			{
107				return fNext;
108			}
109
110			Element *Next()
111			{
112				Element *element = fNext;
113				if (fNext)
114					fNext = fQueue->GetNext(fNext);
115				return element;
116			}
117
118			ConstIterator &operator=(const ConstIterator &other)
119			{
120				fQueue = other.fQueue;
121				fNext = other.fNext;
122				return *this;
123			}
124
125			void Rewind()
126			{
127				fNext = fQueue->First();
128			}
129
130		private:
131			const Queue	*fQueue;
132			Element		*fNext;
133	};
134
135public:
136	DoublyLinkedQueue() : fFirst(NULL) {}
137	~DoublyLinkedQueue() {}
138
139	inline bool IsEmpty() const		{ return (fFirst == NULL); }
140
141	inline void Insert(Element *element);
142	inline void InsertBefore(Element *before, Element *element);
143	inline void Add(Element *element);
144	inline void Remove(Element *element);
145
146	inline void Swap(Element *a, Element *b);
147
148	inline void MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList);
149
150	inline void RemoveAll();
151	inline void MakeEmpty()			{ RemoveAll(); }
152
153	inline Element *First() const	{ return fFirst; }
154	inline Element *Head() const	{ return fFirst; }
155
156	inline Element *RemoveHead();
157
158	inline Element *GetPrevious(Element *element) const;
159	inline Element *GetNext(Element *element) const;
160
161	inline int32 Size() const;
162		// O(n)!
163
164	inline Iterator GetIterator()				{ return Iterator(this); }
165	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
166
167private:
168	Element	*fFirst;
169
170	static GetLink	sGetLink;
171};
172
173
174// inline methods
175
176// Insert
177DOUBLY_LINKED_LIST_TEMPLATE_LIST
178void
179DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *element)
180{
181	if (element) {
182		Link *elLink = sGetLink(element);
183		elLink->previous = NULL;
184		elLink->next = fFirst;
185		if (fFirst)
186			sGetLink(fFirst)->previous = element;
187		fFirst = element;
188	}
189}
190
191// Insert
192DOUBLY_LINKED_LIST_TEMPLATE_LIST
193void
194DOUBLY_LINKED_QUEUE_CLASS_NAME::InsertBefore(Element *before, Element *element)
195{
196	if (before == NULL) {
197		Insert(element);
198		return;
199	}
200	if (element == NULL)
201		return;
202
203	Link *beforeLink = sGetLink(before);
204	Link *link = sGetLink(element);
205
206	link->next = before;
207	link->previous = beforeLink->previous;
208	if (link->previous != NULL)
209		sGetLink(link->previous)->next = element;
210	beforeLink->previous = element;
211
212	if (fFirst == before)
213		fFirst = element;
214}
215
216// Add
217DOUBLY_LINKED_LIST_TEMPLATE_LIST
218void
219DOUBLY_LINKED_QUEUE_CLASS_NAME::Add(Element *element)
220{
221	Insert(element);
222}
223
224// Remove
225DOUBLY_LINKED_LIST_TEMPLATE_LIST
226void
227DOUBLY_LINKED_QUEUE_CLASS_NAME::Remove(Element *element)
228{
229	if (element == NULL)
230		return;
231
232#if DEBUG_DOUBLY_LINKED_LIST
233	ASSERT_PRINT(fFirst != NULL,
234		"queue: %p, element: %p\n", this, element);
235#endif
236
237	Link *elLink = sGetLink(element);
238	if (element == fFirst)
239		fFirst = elLink->next;
240	else
241		sGetLink(elLink->previous)->next = elLink->next;
242
243	if (elLink->next)
244		sGetLink(elLink->next)->previous = elLink->previous;
245
246	elLink->next = elLink->previous = NULL;
247}
248
249// Swap
250DOUBLY_LINKED_LIST_TEMPLATE_LIST
251void
252DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b)
253{
254	if (a && b && a != b) {
255		Link *aLink = sGetLink(a);
256		Link *bLink = sGetLink(b);
257		Element *aPrev = aLink->previous;
258		Element *bPrev = bLink->previous;
259		Element *aNext = aLink->next;
260		Element *bNext = bLink->next;
261		// place a
262		if (bPrev)
263			sGetLink(bPrev)->next = a;
264		else
265			fFirst = a;
266		if (bNext)
267			sGetLink(bNext)->previous = a;
268
269		aLink->previous = bPrev;
270		aLink->next = bNext;
271		// place b
272		if (aPrev)
273			sGetLink(aPrev)->next = b;
274		else
275			fFirst = b;
276		if (aNext)
277			sGetLink(aNext)->previous = b;
278
279		bLink->previous = aPrev;
280		bLink->next = aNext;
281	}
282}
283
284// MoveFrom
285DOUBLY_LINKED_LIST_TEMPLATE_LIST
286void
287DOUBLY_LINKED_QUEUE_CLASS_NAME::MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList)
288{
289	if (fromList && fromList->fFirst) {
290		if (fFirst) {
291			Element *element = fFirst;
292			Link *elLink;
293			while ((elLink = sGetLink(element))->next) {
294				element = elLink->next;
295			}
296			elLink->next = fromList->fFirst;
297		} else {
298			fFirst = fromList->fFirst;
299		}
300		fromList->fFirst = NULL;
301	}
302}
303
304// RemoveAll
305DOUBLY_LINKED_LIST_TEMPLATE_LIST
306void
307DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll()
308{
309	Element *element = fFirst;
310	while (element) {
311		Link *elLink = sGetLink(element);
312		element = elLink->next;
313		elLink->previous = NULL;
314		elLink->next = NULL;
315	}
316	fFirst = NULL;
317}
318
319// RemoveHead
320DOUBLY_LINKED_LIST_TEMPLATE_LIST
321Element *
322DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead()
323{
324	Element *element = Head();
325	Remove(element);
326	return element;
327}
328
329// GetPrevious
330DOUBLY_LINKED_LIST_TEMPLATE_LIST
331Element *
332DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const
333{
334	Element *result = NULL;
335	if (element)
336		result = sGetLink(element)->previous;
337	return result;
338}
339
340// GetNext
341DOUBLY_LINKED_LIST_TEMPLATE_LIST
342Element *
343DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const
344{
345	Element *result = NULL;
346	if (element)
347		result = sGetLink(element)->next;
348	return result;
349}
350
351// Size
352DOUBLY_LINKED_LIST_TEMPLATE_LIST
353int32
354DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const
355{
356	int32 count = 0;
357	for (Element* element = First(); element; element = GetNext(element))
358		count++;
359	return count;
360}
361
362// sGetLink
363DOUBLY_LINKED_LIST_TEMPLATE_LIST
364GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink;
365
366#endif	/* __cplusplus */
367
368#endif	// _KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
369