xref: /haiku/headers/private/kernel/util/DoublyLinkedList.h (revision b06a48ab8f30b45916a9c157b992827779182163) 
1 /*
2  * Copyright 2005-2007, 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() : next(NULL), previous(NULL) {}
27 	~DoublyLinkedListLink() {}
28 
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 	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 		Element *aNext = sGetLink(a)->next;
488 		Element *bNext = sGetLink(b)->next;
489 		if (a == bNext) {
490 			Remove(a);
491 			Insert(b, a);
492 		} else if (b == aNext) {
493 			Remove(b);
494 			Insert(a, b);
495 		} else {
496 			Remove(a);
497 			Remove(b);
498 			Insert(aNext, b);
499 			Insert(bNext, a);
500 		}
501 	}
502 }
503 
504 // MoveFrom
505 DOUBLY_LINKED_LIST_TEMPLATE_LIST
506 void
507 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList)
508 {
509 	if (fromList && fromList->fFirst) {
510 		if (fFirst) {
511 			sGetLink(fLast)->next = fromList->fFirst;
512 			sGetLink(fromList->fFirst)->previous = fLast;
513 			fLast = fromList->fLast;
514 		} else {
515 			fFirst = fromList->fFirst;
516 			fLast = fromList->fLast;
517 		}
518 		fromList->fFirst = NULL;
519 		fromList->fLast = NULL;
520 	}
521 }
522 
523 // RemoveAll
524 DOUBLY_LINKED_LIST_TEMPLATE_LIST
525 void
526 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
527 {
528 	Element *element = fFirst;
529 	while (element) {
530 		Link *elLink = sGetLink(element);
531 		element = elLink->next;
532 		elLink->previous = NULL;
533 		elLink->next = NULL;
534 	}
535 	fFirst = NULL;
536 	fLast = NULL;
537 }
538 
539 // RemoveHead
540 DOUBLY_LINKED_LIST_TEMPLATE_LIST
541 Element *
542 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
543 {
544 	Element *element = Head();
545 	Remove(element);
546 	return element;
547 }
548 
549 // GetPrevious
550 DOUBLY_LINKED_LIST_TEMPLATE_LIST
551 Element *
552 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const
553 {
554 	Element *result = NULL;
555 	if (element)
556 		result = sGetLink(element)->previous;
557 	return result;
558 }
559 
560 // GetNext
561 DOUBLY_LINKED_LIST_TEMPLATE_LIST
562 Element *
563 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const
564 {
565 	Element *result = NULL;
566 	if (element)
567 		result = sGetLink(element)->next;
568 	return result;
569 }
570 
571 // Size
572 DOUBLY_LINKED_LIST_TEMPLATE_LIST
573 int32
574 DOUBLY_LINKED_LIST_CLASS_NAME::Size() const
575 {
576 	int32 count = 0;
577 	for (Element* element = First(); element; element = GetNext(element))
578 		count++;
579 	return count;
580 }
581 
582 // sGetLink
583 DOUBLY_LINKED_LIST_TEMPLATE_LIST
584 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
585 
586 #endif	/* __cplusplus */
587 
588 #endif	// _KERNEL_UTIL_DOUBLY_LINKED_LIST_H
589