xref: /haiku/headers/private/kernel/util/DoublyLinkedList.h (revision fc75f2df0c666dcc61be83c4facdd3132340c2fb) 
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 bool Contains(Element* element) const;
363 		// O(n)!
364 
365 	inline int32 Count() const;
366 		// O(n)!
367 
368 	inline Iterator GetIterator()				{ return Iterator(this); }
369 	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }
370 
371 	inline ReverseIterator GetReverseIterator()
372 		{ return ReverseIterator(this); }
373 	inline ConstReverseIterator GetReverseIterator() const
374 		{ return ConstReverseIterator(this); }
375 
376 private:
377 	Element*		fFirst;
378 	Element*		fLast;
379 
380 	static GetLink	sGetLink;
381 };
382 
383 
384 // inline methods
385 
386 // Insert
387 DOUBLY_LINKED_LIST_TEMPLATE_LIST
388 void
389 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* element, bool back)
390 {
391 	if (element) {
392 #if DEBUG_DOUBLY_LINKED_LIST
393 		ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
394 			"list: %p\n", this);
395 #endif
396 
397 		if (back) {
398 			// append
399 			Link* elLink = sGetLink(element);
400 			elLink->previous = fLast;
401 			elLink->next = NULL;
402 			if (fLast)
403 				sGetLink(fLast)->next = element;
404 			else
405 				fFirst = element;
406 			fLast = element;
407 		} else {
408 			// prepend
409 			Link* elLink = sGetLink(element);
410 			elLink->previous = NULL;
411 			elLink->next = fFirst;
412 			if (fFirst)
413 				sGetLink(fFirst)->previous = element;
414 			else
415 				fLast = element;
416 			fFirst = element;
417 		}
418 	}
419 }
420 
421 
422 DOUBLY_LINKED_LIST_TEMPLATE_LIST
423 void
424 DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element)
425 {
426 	ASSERT(element != NULL);
427 
428 	if (before == NULL) {
429 		Insert(element);
430 		return;
431 	}
432 
433 #if DEBUG_DOUBLY_LINKED_LIST
434 	ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
435 		"list: %p\n", this);
436 #endif
437 
438 	Link* beforeLink = sGetLink(before);
439 	Link* link = sGetLink(element);
440 
441 	link->next = before;
442 	link->previous = beforeLink->previous;
443 	beforeLink->previous = element;
444 
445 	if (link->previous != NULL)
446 		sGetLink(link->previous)->next = element;
447 	else
448 		fFirst = element;
449 }
450 
451 
452 DOUBLY_LINKED_LIST_TEMPLATE_LIST
453 void
454 DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* insertAfter,
455 	Element* element)
456 {
457 	ASSERT(element != NULL);
458 
459 #if DEBUG_DOUBLY_LINKED_LIST
460 	ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
461 		"list: %p\n", this);
462 #endif
463 
464 	if (insertAfter == NULL) {
465 		// insert at the head
466 		Link* elLink = sGetLink(element);
467 		elLink->previous = NULL;
468 		elLink->next = fFirst;
469 		if (fFirst != NULL)
470 			sGetLink(fFirst)->previous = element;
471 		else
472 			fLast = element;
473 		fFirst = element;
474 	} else {
475 		Link* afterLink = sGetLink(insertAfter);
476 		Link* link = sGetLink(element);
477 
478 		link->previous = insertAfter;
479 		link->next = afterLink->next;
480 		afterLink->next = element;
481 
482 		if (link->next != NULL)
483 			sGetLink(link->next)->previous = element;
484 		else
485 			fLast = element;
486 	}
487 }
488 
489 
490 DOUBLY_LINKED_LIST_TEMPLATE_LIST
491 void
492 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
493 {
494 	InsertBefore(before, element);
495 }
496 
497 
498 // Add
499 DOUBLY_LINKED_LIST_TEMPLATE_LIST
500 void
501 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back)
502 {
503 	Insert(element, back);
504 }
505 
506 // Remove
507 DOUBLY_LINKED_LIST_TEMPLATE_LIST
508 void
509 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
510 {
511 	if (element) {
512 #if DEBUG_DOUBLY_LINKED_LIST
513 		ASSERT_PRINT(fFirst != NULL && fLast != NULL
514 			&& (fFirst != fLast || element == fFirst),
515 			"list: %p, element: %p\n", this, element);
516 #endif
517 
518 		Link* elLink = sGetLink(element);
519 		if (elLink->previous)
520 			sGetLink(elLink->previous)->next = elLink->next;
521 		else
522 			fFirst = elLink->next;
523 		if (elLink->next)
524 			sGetLink(elLink->next)->previous = elLink->previous;
525 		else
526 			fLast = elLink->previous;
527 	}
528 }
529 
530 // Swap
531 DOUBLY_LINKED_LIST_TEMPLATE_LIST
532 void
533 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b)
534 {
535 	if (a && b && a != b) {
536 		Element* aNext = sGetLink(a)->next;
537 		Element* bNext = sGetLink(b)->next;
538 		if (a == bNext) {
539 			Remove(a);
540 			Insert(b, a);
541 		} else if (b == aNext) {
542 			Remove(b);
543 			Insert(a, b);
544 		} else {
545 			Remove(a);
546 			Remove(b);
547 			Insert(aNext, b);
548 			Insert(bNext, a);
549 		}
550 	}
551 }
552 
553 // MoveFrom
554 DOUBLY_LINKED_LIST_TEMPLATE_LIST
555 void
556 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList)
557 {
558 	if (fromList && fromList->fFirst) {
559 		if (fFirst) {
560 			sGetLink(fLast)->next = fromList->fFirst;
561 			sGetLink(fromList->fFirst)->previous = fLast;
562 			fLast = fromList->fLast;
563 		} else {
564 			fFirst = fromList->fFirst;
565 			fLast = fromList->fLast;
566 		}
567 		fromList->fFirst = NULL;
568 		fromList->fLast = NULL;
569 	}
570 }
571 
572 // RemoveAll
573 DOUBLY_LINKED_LIST_TEMPLATE_LIST
574 void
575 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
576 {
577 	fFirst = NULL;
578 	fLast = NULL;
579 }
580 
581 // RemoveHead
582 DOUBLY_LINKED_LIST_TEMPLATE_LIST
583 Element*
584 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
585 {
586 	Element* element = Head();
587 	Remove(element);
588 	return element;
589 }
590 
591 // RemoveTail
592 DOUBLY_LINKED_LIST_TEMPLATE_LIST
593 Element*
594 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail()
595 {
596 	Element* element = Tail();
597 	Remove(element);
598 	return element;
599 }
600 
601 // GetPrevious
602 DOUBLY_LINKED_LIST_TEMPLATE_LIST
603 Element*
604 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element) const
605 {
606 	Element* result = NULL;
607 	if (element)
608 		result = sGetLink(element)->previous;
609 	return result;
610 }
611 
612 // GetNext
613 DOUBLY_LINKED_LIST_TEMPLATE_LIST
614 Element*
615 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
616 {
617 	Element* result = NULL;
618 	if (element)
619 		result = sGetLink(element)->next;
620 	return result;
621 }
622 
623 
624 DOUBLY_LINKED_LIST_TEMPLATE_LIST
625 bool
626 DOUBLY_LINKED_LIST_CLASS_NAME::Contains(Element* _element) const
627 {
628 	for (Element* element = First(); element; element = GetNext(element)) {
629 		if (element == _element)
630 			return true;
631 	}
632 
633 	return false;
634 }
635 
636 
637 // Count
638 DOUBLY_LINKED_LIST_TEMPLATE_LIST
639 int32
640 DOUBLY_LINKED_LIST_CLASS_NAME::Count() const
641 {
642 	int32 count = 0;
643 	for (Element* element = First(); element; element = GetNext(element))
644 		count++;
645 	return count;
646 }
647 
648 // sGetLink
649 DOUBLY_LINKED_LIST_TEMPLATE_LIST
650 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
651 
652 #endif	/* __cplusplus */
653 
654 #endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
655