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) { 509 #if DEBUG_DOUBLY_LINKED_LIST 510 ASSERT_PRINT(fFirst != NULL && fLast != NULL 511 && (fFirst != fLast || element == fFirst), 512 "list: %p, element: %p\n", this, element); 513 #endif 514 515 Link* elLink = sGetLink(element); 516 if (elLink->previous) 517 sGetLink(elLink->previous)->next = elLink->next; 518 else 519 fFirst = elLink->next; 520 if (elLink->next) 521 sGetLink(elLink->next)->previous = elLink->previous; 522 else 523 fLast = elLink->previous; 524 525 #if DEBUG_DOUBLY_LINKED_LIST 526 elLink->next = elLink->previous = NULL; 527 #endif 528 } 529 } 530 531 // Swap 532 DOUBLY_LINKED_LIST_TEMPLATE_LIST 533 void 534 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b) 535 { 536 if (a && b && a != b) { 537 Element* aNext = sGetLink(a)->next; 538 Element* bNext = sGetLink(b)->next; 539 if (a == bNext) { 540 Remove(a); 541 Insert(b, a); 542 } else if (b == aNext) { 543 Remove(b); 544 Insert(a, b); 545 } else { 546 Remove(a); 547 Remove(b); 548 Insert(aNext, b); 549 Insert(bNext, a); 550 } 551 } 552 } 553 554 // MoveFrom 555 DOUBLY_LINKED_LIST_TEMPLATE_LIST 556 void 557 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList) 558 { 559 if (fromList && fromList->fFirst) { 560 if (fFirst) { 561 sGetLink(fLast)->next = fromList->fFirst; 562 sGetLink(fromList->fFirst)->previous = fLast; 563 fLast = fromList->fLast; 564 } else { 565 fFirst = fromList->fFirst; 566 fLast = fromList->fLast; 567 } 568 fromList->fFirst = NULL; 569 fromList->fLast = NULL; 570 } 571 } 572 573 // RemoveAll 574 DOUBLY_LINKED_LIST_TEMPLATE_LIST 575 void 576 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 577 { 578 fFirst = NULL; 579 fLast = NULL; 580 } 581 582 // RemoveHead 583 DOUBLY_LINKED_LIST_TEMPLATE_LIST 584 Element* 585 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 586 { 587 Element* element = Head(); 588 Remove(element); 589 return element; 590 } 591 592 // RemoveTail 593 DOUBLY_LINKED_LIST_TEMPLATE_LIST 594 Element* 595 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail() 596 { 597 Element* element = Tail(); 598 Remove(element); 599 return element; 600 } 601 602 // GetPrevious 603 DOUBLY_LINKED_LIST_TEMPLATE_LIST 604 Element* 605 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element) 606 { 607 Element* result = NULL; 608 if (element) 609 result = sGetLink(element)->previous; 610 return result; 611 } 612 613 // GetNext 614 DOUBLY_LINKED_LIST_TEMPLATE_LIST 615 Element* 616 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) 617 { 618 Element* result = NULL; 619 if (element) 620 result = sGetLink(element)->next; 621 return result; 622 } 623 624 625 DOUBLY_LINKED_LIST_TEMPLATE_LIST 626 bool 627 DOUBLY_LINKED_LIST_CLASS_NAME::Contains(Element* _element) const 628 { 629 for (Element* element = First(); element; element = GetNext(element)) { 630 if (element == _element) 631 return true; 632 } 633 634 return false; 635 } 636 637 638 // Count 639 DOUBLY_LINKED_LIST_TEMPLATE_LIST 640 int32 641 DOUBLY_LINKED_LIST_CLASS_NAME::Count() const 642 { 643 int32 count = 0; 644 for (Element* element = First(); element; element = GetNext(element)) 645 count++; 646 return count; 647 } 648 649 650 DOUBLY_LINKED_LIST_TEMPLATE_LIST 651 template<typename Less> 652 void 653 DOUBLY_LINKED_LIST_CLASS_NAME::Sort(const Less& less) 654 { 655 // selection sort 656 Element* tail = Head(); 657 while (tail != NULL) { 658 Element* leastElement = tail; 659 Element* element = tail; 660 while ((element = GetNext(element)) != NULL) { 661 if (less(element, leastElement)) 662 leastElement = element; 663 } 664 665 if (leastElement != tail) { 666 Remove(leastElement); 667 InsertBefore(tail, leastElement); 668 } else 669 tail = GetNext(tail); 670 } 671 } 672 673 674 // sGetLink 675 DOUBLY_LINKED_LIST_TEMPLATE_LIST 676 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 677 678 #endif /* __cplusplus */ 679 680 #endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 681