xref: /haiku/headers/private/kernel/util/DoublyLinkedList.h (revision d374a27286b8a52974a97dba0d5966ea026a665d) 
1 /*
2  * Copyright 2005-2009, Ingo Weinhold, bonefish@users.sf.net.
3  * Copyright 2006-2009, Axel Dörfler, axeld@pinc-software.de.
4  *
5  * Distributed under the terms of the MIT License.
6  */
7 #ifndef KERNEL_UTIL_DOUBLY_LINKED_LIST_H
8 #define KERNEL_UTIL_DOUBLY_LINKED_LIST_H
9 
10 
11 #include <SupportDefs.h>
12 
13 #ifdef _KERNEL_MODE
14 #	include <debug.h>
15 #	include <util/kernel_cpp.h>
16 
17 #	if !defined(_BOOT_MODE) && KDEBUG
18 #		define DEBUG_DOUBLY_LINKED_LIST KDEBUG
19 #	endif
20 #endif
21 
22 
23 #ifdef __cplusplus
24 
25 // DoublyLinkedListLink
26 template<typename Element>
27 class DoublyLinkedListLink {
28 public:
29 	Element*	next;
30 	Element*	previous;
31 };
32 
33 // DoublyLinkedListLinkImpl
34 template<typename Element>
35 class DoublyLinkedListLinkImpl {
36 private:
37 	typedef DoublyLinkedListLink<Element> DLL_Link;
38 
39 public:
40 	DLL_Link* GetDoublyLinkedListLink()
41 		{ return &fDoublyLinkedListLink; }
42 	const DLL_Link* GetDoublyLinkedListLink() const
43 		{ return &fDoublyLinkedListLink; }
44 
45 private:
46 	DLL_Link	fDoublyLinkedListLink;
47 };
48 
49 // DoublyLinkedListStandardGetLink
50 template<typename Element>
51 class DoublyLinkedListStandardGetLink {
52 private:
53 	typedef DoublyLinkedListLink<Element> Link;
54 
55 public:
56 	inline Link* operator()(Element* element) const
57 	{
58 		return element->GetDoublyLinkedListLink();
59 	}
60 
61 	inline const Link* operator()(const Element* element) const
62 	{
63 		return element->GetDoublyLinkedListLink();
64 	}
65 };
66 
67 // DoublyLinkedListMemberGetLink
68 template<typename Element,
69 	DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
70 class DoublyLinkedListMemberGetLink {
71 private:
72 	typedef DoublyLinkedListLink<Element> Link;
73 
74 public:
75 	inline Link* operator()(Element* element) const
76 	{
77 		return &(element->*LinkMember);
78 	}
79 
80 	inline const Link* operator()(const Element* element) const
81 	{
82 		return &(element->*LinkMember);
83 	}
84 };
85 
86 // DoublyLinkedListCLink - interface to struct list
87 template<typename Element>
88 class DoublyLinkedListCLink {
89 	private:
90 		typedef DoublyLinkedListLink<Element> Link;
91 
92 	public:
93 		inline Link* operator()(Element* element) const
94 		{
95 			return (Link*)&element->link;
96 		}
97 
98 		inline const Link* operator()(const Element* element) const
99 		{
100 			return (const Link*)&element->link;
101 		}
102 };
103 
104 // for convenience
105 #define DOUBLY_LINKED_LIST_TEMPLATE_LIST \
106 	template<typename Element, typename GetLink>
107 #define DOUBLY_LINKED_LIST_CLASS_NAME DoublyLinkedList<Element, GetLink>
108 
109 // DoublyLinkedList
110 template<typename Element,
111 	typename GetLink = DoublyLinkedListStandardGetLink<Element> >
112 class DoublyLinkedList {
113 private:
114 	typedef DoublyLinkedList<Element, GetLink>	List;
115 	typedef DoublyLinkedListLink<Element>		Link;
116 
117 public:
118 	class Iterator {
119 	public:
120 		Iterator(List* list)
121 			:
122 			fList(list)
123 		{
124 			Rewind();
125 		}
126 
127 		Iterator()
128 		{
129 		}
130 
131 		Iterator(const Iterator &other)
132 		{
133 			*this = other;
134 		}
135 
136 		bool HasNext() const
137 		{
138 			return fNext;
139 		}
140 
141 		Element* Next()
142 		{
143 			fCurrent = fNext;
144 			if (fNext)
145 				fNext = fList->GetNext(fNext);
146 			return fCurrent;
147 		}
148 
149 		Element* Current()
150 		{
151 			return fCurrent;
152 		}
153 
154 		Element* Remove()
155 		{
156 			Element* element = fCurrent;
157 			if (fCurrent) {
158 				fList->Remove(fCurrent);
159 				fCurrent = NULL;
160 			}
161 			return element;
162 		}
163 
164 		Iterator &operator=(const Iterator& other)
165 		{
166 			fList = other.fList;
167 			fCurrent = other.fCurrent;
168 			fNext = other.fNext;
169 			return *this;
170 		}
171 
172 		void Rewind()
173 		{
174 			fCurrent = NULL;
175 			fNext = fList->First();
176 		}
177 
178 	private:
179 		List*		fList;
180 		Element*	fCurrent;
181 		Element*	fNext;
182 	};
183 
184 	class ConstIterator {
185 	public:
186 		ConstIterator(const List* list)
187 			:
188 			fList(list)
189 		{
190 			Rewind();
191 		}
192 
193 		ConstIterator(const ConstIterator& other)
194 		{
195 			*this = other;
196 		}
197 
198 		bool HasNext() const
199 		{
200 			return fNext;
201 		}
202 
203 		Element* Next()
204 		{
205 			Element* element = fNext;
206 			if (fNext)
207 				fNext = fList->GetNext(fNext);
208 			return element;
209 		}
210 
211 		ConstIterator& operator=(const ConstIterator& other)
212 		{
213 			fList = other.fList;
214 			fNext = other.fNext;
215 			return *this;
216 		}
217 
218 		void Rewind()
219 		{
220 			fNext = fList->First();
221 		}
222 
223 	private:
224 		const List*	fList;
225 		Element*	fNext;
226 	};
227 
228 	class ReverseIterator {
229 	public:
230 		ReverseIterator(List* list)
231 			:
232 			fList(list)
233 		{
234 			Rewind();
235 		}
236 
237 		ReverseIterator(const ReverseIterator& other)
238 		{
239 			*this = other;
240 		}
241 
242 		bool HasNext() const
243 		{
244 			return fNext;
245 		}
246 
247 		Element* Next()
248 		{
249 			fCurrent = fNext;
250 			if (fNext)
251 				fNext = fList->GetPrevious(fNext);
252 			return fCurrent;
253 		}
254 
255 		Element* Remove()
256 		{
257 			Element* element = fCurrent;
258 			if (fCurrent) {
259 				fList->Remove(fCurrent);
260 				fCurrent = NULL;
261 			}
262 			return element;
263 		}
264 
265 		ReverseIterator &operator=(const ReverseIterator& other)
266 		{
267 			fList = other.fList;
268 			fCurrent = other.fCurrent;
269 			fNext = other.fNext;
270 			return *this;
271 		}
272 
273 		void Rewind()
274 		{
275 			fCurrent = NULL;
276 			fNext = fList->Last();
277 		}
278 
279 	private:
280 		List*		fList;
281 		Element*	fCurrent;
282 		Element*	fNext;
283 	};
284 
285 	class ConstReverseIterator {
286 	public:
287 		ConstReverseIterator(const List* list)
288 			:
289 			fList(list)
290 		{
291 			Rewind();
292 		}
293 
294 		ConstReverseIterator(const ConstReverseIterator& other)
295 		{
296 			*this = other;
297 		}
298 
299 		bool HasNext() const
300 		{
301 			return fNext;
302 		}
303 
304 		Element* Next()
305 		{
306 			Element* element = fNext;
307 			if (fNext)
308 				fNext = fList->GetPrevious(fNext);
309 			return element;
310 		}
311 
312 		ConstReverseIterator& operator=(const ConstReverseIterator& other)
313 		{
314 			fList = other.fList;
315 			fNext = other.fNext;
316 			return *this;
317 		}
318 
319 		void Rewind()
320 		{
321 			fNext = fList->Last();
322 		}
323 
324 	private:
325 		const List*	fList;
326 		Element*	fNext;
327 	};
328 
329 public:
330 	DoublyLinkedList() : fFirst(NULL), fLast(NULL) {}
331 	~DoublyLinkedList() {}
332 
333 	inline bool IsEmpty() const			{ return (fFirst == NULL); }
334 
335 	inline void InsertBefore(Element* insertBefore, Element* element);
336 	inline void InsertAfter(Element* insertAfter, Element* element);
337 	inline void Insert(Element* element, bool back = true);
338 	inline void Insert(Element* before, Element* element);
339 		// TODO: Obsolete! Use InsertBefore() instead!
340 	inline void Add(Element* element, bool back = true);
341 	inline void Remove(Element* element);
342 
343 	inline void Swap(Element* a, Element* b);
344 
345 	inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList);
346 
347 	inline void RemoveAll();
348 	inline void MakeEmpty()				{ RemoveAll(); }
349 
350 	inline Element* First() const		{ return fFirst; }
351 	inline Element* Last() const		{ return fLast; }
352 
353 	inline Element* Head() const		{ return fFirst; }
354 	inline Element* Tail() const		{ return fLast; }
355 
356 	inline Element* RemoveHead();
357 	inline Element* RemoveTail();
358 
359 	inline Element* GetPrevious(Element* element) const;
360 	inline Element* GetNext(Element* element) const;
361 
362 	inline int32 Count() const;
363 		// O(n)!
364 
365 	inline Iterator GetIterator()				{ return Iterator(this); }
366 	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
367 
368 	inline ReverseIterator GetReverseIterator()
369 		{ return ReverseIterator(this); }
370 	inline ConstReverseIterator GetReverseIterator() const
371 		{ return ConstReverseIterator(this); }
372 
373 private:
374 	Element*		fFirst;
375 	Element*		fLast;
376 
377 	static GetLink	sGetLink;
378 };
379 
380 
381 // inline methods
382 
383 // Insert
384 DOUBLY_LINKED_LIST_TEMPLATE_LIST
385 void
386 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* element, bool back)
387 {
388 	if (element) {
389 #if DEBUG_DOUBLY_LINKED_LIST
390 		ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
391 			"list: %p\n", this);
392 #endif
393 
394 		if (back) {
395 			// append
396 			Link* elLink = sGetLink(element);
397 			elLink->previous = fLast;
398 			elLink->next = NULL;
399 			if (fLast)
400 				sGetLink(fLast)->next = element;
401 			else
402 				fFirst = element;
403 			fLast = element;
404 		} else {
405 			// prepend
406 			Link* elLink = sGetLink(element);
407 			elLink->previous = NULL;
408 			elLink->next = fFirst;
409 			if (fFirst)
410 				sGetLink(fFirst)->previous = element;
411 			else
412 				fLast = element;
413 			fFirst = element;
414 		}
415 	}
416 }
417 
418 
419 DOUBLY_LINKED_LIST_TEMPLATE_LIST
420 void
421 DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element)
422 {
423 	ASSERT(element != NULL);
424 
425 	if (before == NULL) {
426 		Insert(element);
427 		return;
428 	}
429 
430 #if DEBUG_DOUBLY_LINKED_LIST
431 	ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
432 		"list: %p\n", this);
433 #endif
434 
435 	Link* beforeLink = sGetLink(before);
436 	Link* link = sGetLink(element);
437 
438 	link->next = before;
439 	link->previous = beforeLink->previous;
440 	beforeLink->previous = element;
441 
442 	if (link->previous != NULL)
443 		sGetLink(link->previous)->next = element;
444 	else
445 		fFirst = element;
446 }
447 
448 
449 DOUBLY_LINKED_LIST_TEMPLATE_LIST
450 void
451 DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* insertAfter,
452 	Element* element)
453 {
454 	ASSERT(element != NULL);
455 
456 #if DEBUG_DOUBLY_LINKED_LIST
457 	ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
458 		"list: %p\n", this);
459 #endif
460 
461 	if (insertAfter == NULL) {
462 		// insert at the head
463 		Link* elLink = sGetLink(element);
464 		elLink->previous = NULL;
465 		elLink->next = fFirst;
466 		if (fFirst != NULL)
467 			sGetLink(fFirst)->previous = element;
468 		else
469 			fLast = element;
470 		fFirst = element;
471 	} else {
472 		Link* afterLink = sGetLink(insertAfter);
473 		Link* link = sGetLink(element);
474 
475 		link->previous = insertAfter;
476 		link->next = afterLink->next;
477 		afterLink->next = element;
478 
479 		if (link->next != NULL)
480 			sGetLink(link->next)->previous = element;
481 		else
482 			fLast = element;
483 	}
484 }
485 
486 
487 DOUBLY_LINKED_LIST_TEMPLATE_LIST
488 void
489 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
490 {
491 	InsertBefore(before, element);
492 }
493 
494 
495 // Add
496 DOUBLY_LINKED_LIST_TEMPLATE_LIST
497 void
498 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back)
499 {
500 	Insert(element, back);
501 }
502 
503 // Remove
504 DOUBLY_LINKED_LIST_TEMPLATE_LIST
505 void
506 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
507 {
508 	if (element) {
509 #if DEBUG_DOUBLY_LINKED_LIST
510 		ASSERT_PRINT(fFirst != NULL && fLast != NULL
511 			&& (fFirst != fLast || element == fFirst),
512 			"list: %p, element: %p\n", this, element);
513 #endif
514 
515 		Link* elLink = sGetLink(element);
516 		if (elLink->previous)
517 			sGetLink(elLink->previous)->next = elLink->next;
518 		else
519 			fFirst = elLink->next;
520 		if (elLink->next)
521 			sGetLink(elLink->next)->previous = elLink->previous;
522 		else
523 			fLast = elLink->previous;
524 	}
525 }
526 
527 // Swap
528 DOUBLY_LINKED_LIST_TEMPLATE_LIST
529 void
530 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b)
531 {
532 	if (a && b && a != b) {
533 		Element* aNext = sGetLink(a)->next;
534 		Element* bNext = sGetLink(b)->next;
535 		if (a == bNext) {
536 			Remove(a);
537 			Insert(b, a);
538 		} else if (b == aNext) {
539 			Remove(b);
540 			Insert(a, b);
541 		} else {
542 			Remove(a);
543 			Remove(b);
544 			Insert(aNext, b);
545 			Insert(bNext, a);
546 		}
547 	}
548 }
549 
550 // MoveFrom
551 DOUBLY_LINKED_LIST_TEMPLATE_LIST
552 void
553 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList)
554 {
555 	if (fromList && fromList->fFirst) {
556 		if (fFirst) {
557 			sGetLink(fLast)->next = fromList->fFirst;
558 			sGetLink(fromList->fFirst)->previous = fLast;
559 			fLast = fromList->fLast;
560 		} else {
561 			fFirst = fromList->fFirst;
562 			fLast = fromList->fLast;
563 		}
564 		fromList->fFirst = NULL;
565 		fromList->fLast = NULL;
566 	}
567 }
568 
569 // RemoveAll
570 DOUBLY_LINKED_LIST_TEMPLATE_LIST
571 void
572 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
573 {
574 	fFirst = NULL;
575 	fLast = NULL;
576 }
577 
578 // RemoveHead
579 DOUBLY_LINKED_LIST_TEMPLATE_LIST
580 Element*
581 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
582 {
583 	Element* element = Head();
584 	Remove(element);
585 	return element;
586 }
587 
588 // RemoveTail
589 DOUBLY_LINKED_LIST_TEMPLATE_LIST
590 Element*
591 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail()
592 {
593 	Element* element = Tail();
594 	Remove(element);
595 	return element;
596 }
597 
598 // GetPrevious
599 DOUBLY_LINKED_LIST_TEMPLATE_LIST
600 Element*
601 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element) const
602 {
603 	Element* result = NULL;
604 	if (element)
605 		result = sGetLink(element)->previous;
606 	return result;
607 }
608 
609 // GetNext
610 DOUBLY_LINKED_LIST_TEMPLATE_LIST
611 Element*
612 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
613 {
614 	Element* result = NULL;
615 	if (element)
616 		result = sGetLink(element)->next;
617 	return result;
618 }
619 
620 // Count
621 DOUBLY_LINKED_LIST_TEMPLATE_LIST
622 int32
623 DOUBLY_LINKED_LIST_CLASS_NAME::Count() const
624 {
625 	int32 count = 0;
626 	for (Element* element = First(); element; element = GetNext(element))
627 		count++;
628 	return count;
629 }
630 
631 // sGetLink
632 DOUBLY_LINKED_LIST_TEMPLATE_LIST
633 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
634 
635 #endif	/* __cplusplus */
636 
637 #endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
638