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 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 378private: 379 inline void Insert(Element* before, Element* element); 380 // TODO: Obsolete! Use InsertBefore() instead! 381 382private: 383 Element* fFirst; 384 Element* fLast; 385 386 static GetLink sGetLink; 387}; 388 389 390// inline methods 391 392// Insert 393DOUBLY_LINKED_LIST_TEMPLATE_LIST 394void 395DOUBLY_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 427DOUBLY_LINKED_LIST_TEMPLATE_LIST 428void 429DOUBLY_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 457DOUBLY_LINKED_LIST_TEMPLATE_LIST 458void 459DOUBLY_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 487DOUBLY_LINKED_LIST_TEMPLATE_LIST 488void 489DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element) 490{ 491 InsertBefore(before, element); 492} 493 494 495// Add 496DOUBLY_LINKED_LIST_TEMPLATE_LIST 497void 498DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back) 499{ 500 Insert(element, back); 501} 502 503// Remove 504DOUBLY_LINKED_LIST_TEMPLATE_LIST 505void 506DOUBLY_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 533DOUBLY_LINKED_LIST_TEMPLATE_LIST 534void 535DOUBLY_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 556DOUBLY_LINKED_LIST_TEMPLATE_LIST 557void 558DOUBLY_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 575DOUBLY_LINKED_LIST_TEMPLATE_LIST 576void 577DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 578{ 579 fFirst = NULL; 580 fLast = NULL; 581} 582 583// RemoveHead 584DOUBLY_LINKED_LIST_TEMPLATE_LIST 585Element* 586DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 587{ 588 Element* element = Head(); 589 Remove(element); 590 return element; 591} 592 593// RemoveTail 594DOUBLY_LINKED_LIST_TEMPLATE_LIST 595Element* 596DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail() 597{ 598 Element* element = Tail(); 599 Remove(element); 600 return element; 601} 602 603// GetPrevious 604DOUBLY_LINKED_LIST_TEMPLATE_LIST 605Element* 606DOUBLY_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 615DOUBLY_LINKED_LIST_TEMPLATE_LIST 616Element* 617DOUBLY_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 626DOUBLY_LINKED_LIST_TEMPLATE_LIST 627bool 628DOUBLY_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 640DOUBLY_LINKED_LIST_TEMPLATE_LIST 641int32 642DOUBLY_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 651DOUBLY_LINKED_LIST_TEMPLATE_LIST 652template<typename Less> 653void 654DOUBLY_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 676DOUBLY_LINKED_LIST_TEMPLATE_LIST 677GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 678 679#endif /* __cplusplus */ 680 681#endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 682