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 Add(Element* element, bool back = true); 339 inline void Remove(Element* element); 340 341 inline void Swap(Element* a, Element* b); 342 343 inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList); 344 345 inline void RemoveAll(); 346 inline void MakeEmpty() { RemoveAll(); } 347 348 inline Element* First() const { return fFirst; } 349 inline Element* Last() const { return fLast; } 350 351 inline Element* Head() const { return fFirst; } 352 inline Element* Tail() const { return fLast; } 353 354 inline Element* RemoveHead(); 355 inline Element* RemoveTail(); 356 357 static inline Element* GetPrevious(Element* element); 358 static inline Element* GetNext(Element* element); 359 360 inline bool Contains(Element* element) const; 361 // O(n)! 362 363 inline int32 Count() const; 364 // O(n)! 365 366 template<typename Less> 367 void Sort(const Less& less); 368 // O(n^2) 369 370 inline Iterator GetIterator() { return Iterator(this); } 371 inline ConstIterator GetIterator() const { return ConstIterator(this); } 372 373 inline ReverseIterator GetReverseIterator() 374 { return ReverseIterator(this); } 375 inline ConstReverseIterator GetReverseIterator() const 376 { return ConstReverseIterator(this); } 377 378 private: 379 inline void Insert(Element* before, Element* element); 380 // TODO: Obsolete! Use InsertBefore() instead! 381 382 private: 383 Element* fFirst; 384 Element* fLast; 385 386 static GetLink sGetLink; 387 }; 388 389 390 // inline methods 391 392 // Insert 393 DOUBLY_LINKED_LIST_TEMPLATE_LIST 394 void 395 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* element, bool back) 396 { 397 if (element) { 398 #if DEBUG_DOUBLY_LINKED_LIST 399 ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL, 400 "list: %p\n", this); 401 #endif 402 403 Link* elLink = sGetLink(element); 404 if (back) { 405 // append 406 elLink->previous = fLast; 407 elLink->next = NULL; 408 if (fLast) 409 sGetLink(fLast)->next = element; 410 else 411 fFirst = element; 412 fLast = element; 413 } else { 414 // prepend 415 elLink->previous = NULL; 416 elLink->next = fFirst; 417 if (fFirst) 418 sGetLink(fFirst)->previous = element; 419 else 420 fLast = element; 421 fFirst = element; 422 } 423 } 424 } 425 426 427 DOUBLY_LINKED_LIST_TEMPLATE_LIST 428 void 429 DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element) 430 { 431 ASSERT(element != NULL); 432 433 if (before == NULL) { 434 Insert(element); 435 return; 436 } 437 438 #if DEBUG_DOUBLY_LINKED_LIST 439 ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL, 440 "list: %p\n", this); 441 #endif 442 443 Link* beforeLink = sGetLink(before); 444 Link* link = sGetLink(element); 445 446 link->next = before; 447 link->previous = beforeLink->previous; 448 beforeLink->previous = element; 449 450 if (link->previous != NULL) 451 sGetLink(link->previous)->next = element; 452 else 453 fFirst = element; 454 } 455 456 457 DOUBLY_LINKED_LIST_TEMPLATE_LIST 458 void 459 DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* after, Element* element) 460 { 461 ASSERT(element != NULL); 462 463 if (after == NULL) { 464 Insert(element, false); 465 return; 466 } 467 468 #if DEBUG_DOUBLY_LINKED_LIST 469 ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL, 470 "list: %p\n", this); 471 #endif 472 473 Link* afterLink = sGetLink(after); 474 Link* link = sGetLink(element); 475 476 link->previous = after; 477 link->next = afterLink->next; 478 afterLink->next = element; 479 480 if (link->next != NULL) 481 sGetLink(link->next)->previous = element; 482 else 483 fLast = element; 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 == NULL) 509 return; 510 511 #if DEBUG_DOUBLY_LINKED_LIST 512 ASSERT_PRINT(fFirst != NULL && fLast != NULL 513 && (fFirst != fLast || element == fFirst), 514 "list: %p, element: %p\n", this, element); 515 #endif 516 517 Link* elLink = sGetLink(element); 518 519 if (element == fFirst) 520 fFirst = elLink->next; 521 else 522 sGetLink(elLink->previous)->next = elLink->next; 523 524 if (element == fLast) 525 fLast = elLink->previous; 526 else 527 sGetLink(elLink->next)->previous = elLink->previous; 528 529 elLink->next = elLink->previous = NULL; 530 } 531 532 // Swap 533 DOUBLY_LINKED_LIST_TEMPLATE_LIST 534 void 535 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b) 536 { 537 if (a && b && a != b) { 538 Element* aNext = sGetLink(a)->next; 539 Element* bNext = sGetLink(b)->next; 540 if (a == bNext) { 541 Remove(a); 542 Insert(b, a); 543 } else if (b == aNext) { 544 Remove(b); 545 Insert(a, b); 546 } else { 547 Remove(a); 548 Remove(b); 549 Insert(aNext, b); 550 Insert(bNext, a); 551 } 552 } 553 } 554 555 // MoveFrom 556 DOUBLY_LINKED_LIST_TEMPLATE_LIST 557 void 558 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList) 559 { 560 if (fromList && fromList->fFirst) { 561 if (fFirst) { 562 sGetLink(fLast)->next = fromList->fFirst; 563 sGetLink(fromList->fFirst)->previous = fLast; 564 fLast = fromList->fLast; 565 } else { 566 fFirst = fromList->fFirst; 567 fLast = fromList->fLast; 568 } 569 fromList->fFirst = NULL; 570 fromList->fLast = NULL; 571 } 572 } 573 574 // RemoveAll 575 DOUBLY_LINKED_LIST_TEMPLATE_LIST 576 void 577 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 578 { 579 fFirst = NULL; 580 fLast = NULL; 581 } 582 583 // RemoveHead 584 DOUBLY_LINKED_LIST_TEMPLATE_LIST 585 Element* 586 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 587 { 588 Element* element = Head(); 589 Remove(element); 590 return element; 591 } 592 593 // RemoveTail 594 DOUBLY_LINKED_LIST_TEMPLATE_LIST 595 Element* 596 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail() 597 { 598 Element* element = Tail(); 599 Remove(element); 600 return element; 601 } 602 603 // GetPrevious 604 DOUBLY_LINKED_LIST_TEMPLATE_LIST 605 Element* 606 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element) 607 { 608 Element* result = NULL; 609 if (element) 610 result = sGetLink(element)->previous; 611 return result; 612 } 613 614 // GetNext 615 DOUBLY_LINKED_LIST_TEMPLATE_LIST 616 Element* 617 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) 618 { 619 Element* result = NULL; 620 if (element) 621 result = sGetLink(element)->next; 622 return result; 623 } 624 625 626 DOUBLY_LINKED_LIST_TEMPLATE_LIST 627 bool 628 DOUBLY_LINKED_LIST_CLASS_NAME::Contains(Element* _element) const 629 { 630 for (Element* element = First(); element; element = GetNext(element)) { 631 if (element == _element) 632 return true; 633 } 634 635 return false; 636 } 637 638 639 // Count 640 DOUBLY_LINKED_LIST_TEMPLATE_LIST 641 int32 642 DOUBLY_LINKED_LIST_CLASS_NAME::Count() const 643 { 644 int32 count = 0; 645 for (Element* element = First(); element; element = GetNext(element)) 646 count++; 647 return count; 648 } 649 650 651 DOUBLY_LINKED_LIST_TEMPLATE_LIST 652 template<typename Less> 653 void 654 DOUBLY_LINKED_LIST_CLASS_NAME::Sort(const Less& less) 655 { 656 // selection sort 657 Element* tail = Head(); 658 while (tail != NULL) { 659 Element* leastElement = tail; 660 Element* element = tail; 661 while ((element = GetNext(element)) != NULL) { 662 if (less(element, leastElement)) 663 leastElement = element; 664 } 665 666 if (leastElement != tail) { 667 Remove(leastElement); 668 InsertBefore(tail, leastElement); 669 } else 670 tail = GetNext(tail); 671 } 672 } 673 674 675 // sGetLink 676 DOUBLY_LINKED_LIST_TEMPLATE_LIST 677 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 678 679 #endif /* __cplusplus */ 680 681 #endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 682