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