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