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 26template<typename Element> 27class DoublyLinkedListLink { 28public: 29 Element* next; 30 Element* previous; 31}; 32 33// DoublyLinkedListLinkImpl 34template<typename Element> 35class DoublyLinkedListLinkImpl { 36private: 37 typedef DoublyLinkedListLink<Element> DLL_Link; 38 39public: 40 DLL_Link* GetDoublyLinkedListLink() 41 { return &fDoublyLinkedListLink; } 42 const DLL_Link* GetDoublyLinkedListLink() const 43 { return &fDoublyLinkedListLink; } 44 45private: 46 DLL_Link fDoublyLinkedListLink; 47}; 48 49// DoublyLinkedListStandardGetLink 50template<typename Element> 51class DoublyLinkedListStandardGetLink { 52private: 53 typedef DoublyLinkedListLink<Element> Link; 54 55public: 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 68template<typename Element, 69 DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink> 70class DoublyLinkedListMemberGetLink { 71private: 72 typedef DoublyLinkedListLink<Element> Link; 73 74public: 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 87template<typename Element> 88class 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 110template<typename Element, 111 typename GetLink = DoublyLinkedListStandardGetLink<Element> > 112class DoublyLinkedList { 113private: 114 typedef DoublyLinkedList<Element, GetLink> List; 115 typedef DoublyLinkedListLink<Element> Link; 116 117public: 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 329public: 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 376private: 377 Element* fFirst; 378 Element* fLast; 379 380 static GetLink sGetLink; 381}; 382 383 384// inline methods 385 386// Insert 387DOUBLY_LINKED_LIST_TEMPLATE_LIST 388void 389DOUBLY_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 422DOUBLY_LINKED_LIST_TEMPLATE_LIST 423void 424DOUBLY_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 452DOUBLY_LINKED_LIST_TEMPLATE_LIST 453void 454DOUBLY_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 490DOUBLY_LINKED_LIST_TEMPLATE_LIST 491void 492DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element) 493{ 494 InsertBefore(before, element); 495} 496 497 498// Add 499DOUBLY_LINKED_LIST_TEMPLATE_LIST 500void 501DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back) 502{ 503 Insert(element, back); 504} 505 506// Remove 507DOUBLY_LINKED_LIST_TEMPLATE_LIST 508void 509DOUBLY_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 531DOUBLY_LINKED_LIST_TEMPLATE_LIST 532void 533DOUBLY_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 554DOUBLY_LINKED_LIST_TEMPLATE_LIST 555void 556DOUBLY_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 573DOUBLY_LINKED_LIST_TEMPLATE_LIST 574void 575DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 576{ 577 fFirst = NULL; 578 fLast = NULL; 579} 580 581// RemoveHead 582DOUBLY_LINKED_LIST_TEMPLATE_LIST 583Element* 584DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 585{ 586 Element* element = Head(); 587 Remove(element); 588 return element; 589} 590 591// RemoveTail 592DOUBLY_LINKED_LIST_TEMPLATE_LIST 593Element* 594DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail() 595{ 596 Element* element = Tail(); 597 Remove(element); 598 return element; 599} 600 601// GetPrevious 602DOUBLY_LINKED_LIST_TEMPLATE_LIST 603Element* 604DOUBLY_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 613DOUBLY_LINKED_LIST_TEMPLATE_LIST 614Element* 615DOUBLY_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 624DOUBLY_LINKED_LIST_TEMPLATE_LIST 625bool 626DOUBLY_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 638DOUBLY_LINKED_LIST_TEMPLATE_LIST 639int32 640DOUBLY_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 649DOUBLY_LINKED_LIST_TEMPLATE_LIST 650GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 651 652#endif /* __cplusplus */ 653 654#endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 655