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 "fssh_types.h" 10 11 12 #ifdef __cplusplus 13 14 15 namespace FSShell { 16 17 18 // DoublyLinkedListLink 19 template<typename Element> 20 class DoublyLinkedListLink { 21 public: 22 DoublyLinkedListLink() : next(NULL), previous(NULL) {} 23 ~DoublyLinkedListLink() {} 24 25 Element *next; 26 Element *previous; 27 }; 28 29 // DoublyLinkedListLinkImpl 30 template<typename Element> 31 class DoublyLinkedListLinkImpl { 32 private: 33 typedef DoublyLinkedListLink<Element> DLL_Link; 34 35 public: 36 DoublyLinkedListLinkImpl() : fDoublyLinkedListLink() {} 37 ~DoublyLinkedListLinkImpl() {} 38 39 DLL_Link *GetDoublyLinkedListLink() 40 { return &fDoublyLinkedListLink; } 41 const DLL_Link *GetDoublyLinkedListLink() const 42 { return &fDoublyLinkedListLink; } 43 44 private: 45 DLL_Link fDoublyLinkedListLink; 46 }; 47 48 // DoublyLinkedListStandardGetLink 49 template<typename Element> 50 class DoublyLinkedListStandardGetLink { 51 private: 52 typedef DoublyLinkedListLink<Element> Link; 53 54 public: 55 inline Link *operator()(Element *element) const 56 { 57 return element->GetDoublyLinkedListLink(); 58 } 59 60 inline const Link *operator()(const Element *element) const 61 { 62 return element->GetDoublyLinkedListLink(); 63 } 64 }; 65 66 // DoublyLinkedListMemberGetLink 67 template<typename Element, 68 DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink> 69 class DoublyLinkedListMemberGetLink { 70 private: 71 typedef DoublyLinkedListLink<Element> Link; 72 73 public: 74 inline Link *operator()(Element *element) const 75 { 76 return &(element->*LinkMember); 77 } 78 79 inline const Link *operator()(const Element *element) const 80 { 81 return &(element->*LinkMember); 82 } 83 }; 84 85 // DoublyLinkedListCLink - interface to struct list 86 template<typename Element> 87 class DoublyLinkedListCLink { 88 private: 89 typedef DoublyLinkedListLink<Element> Link; 90 91 public: 92 inline Link *operator()(Element *element) const 93 { 94 return (Link *)&element->link; 95 } 96 97 inline const Link *operator()(const Element *element) const 98 { 99 return (const Link *)&element->link; 100 } 101 }; 102 103 // for convenience 104 #define DOUBLY_LINKED_LIST_TEMPLATE_LIST \ 105 template<typename Element, typename GetLink> 106 #define DOUBLY_LINKED_LIST_CLASS_NAME DoublyLinkedList<Element, GetLink> 107 108 // DoublyLinkedList 109 template<typename Element, 110 typename GetLink = DoublyLinkedListStandardGetLink<Element> > 111 class DoublyLinkedList { 112 private: 113 typedef DoublyLinkedList<Element, GetLink> List; 114 typedef DoublyLinkedListLink<Element> Link; 115 116 public: 117 class Iterator { 118 public: 119 Iterator(List *list) 120 : 121 fList(list) 122 { 123 Rewind(); 124 } 125 126 Iterator(const Iterator &other) 127 { 128 *this = other; 129 } 130 131 bool HasNext() const 132 { 133 return fNext; 134 } 135 136 Element *Next() 137 { 138 fCurrent = fNext; 139 if (fNext) 140 fNext = fList->GetNext(fNext); 141 return fCurrent; 142 } 143 144 Element *Current() 145 { 146 return fCurrent; 147 } 148 149 Element *Remove() 150 { 151 Element *element = fCurrent; 152 if (fCurrent) { 153 fList->Remove(fCurrent); 154 fCurrent = NULL; 155 } 156 return element; 157 } 158 159 Iterator &operator=(const Iterator &other) 160 { 161 fList = other.fList; 162 fCurrent = other.fCurrent; 163 fNext = other.fNext; 164 return *this; 165 } 166 167 void Rewind() 168 { 169 fCurrent = NULL; 170 fNext = fList->First(); 171 } 172 173 private: 174 List *fList; 175 Element *fCurrent; 176 Element *fNext; 177 }; 178 179 class ConstIterator { 180 public: 181 ConstIterator(const List *list) 182 : 183 fList(list) 184 { 185 Rewind(); 186 } 187 188 ConstIterator(const ConstIterator &other) 189 { 190 *this = other; 191 } 192 193 bool HasNext() const 194 { 195 return fNext; 196 } 197 198 Element *Next() 199 { 200 Element *element = fNext; 201 if (fNext) 202 fNext = fList->GetNext(fNext); 203 return element; 204 } 205 206 ConstIterator &operator=(const ConstIterator &other) 207 { 208 fList = other.fList; 209 fNext = other.fNext; 210 return *this; 211 } 212 213 void Rewind() 214 { 215 fNext = fList->First(); 216 } 217 218 private: 219 const List *fList; 220 Element *fNext; 221 }; 222 223 class ReverseIterator { 224 public: 225 ReverseIterator(List *list) 226 : 227 fList(list) 228 { 229 Rewind(); 230 } 231 232 ReverseIterator(const ReverseIterator &other) 233 { 234 *this = other; 235 } 236 237 bool HasNext() const 238 { 239 return fNext; 240 } 241 242 Element *Next() 243 { 244 fCurrent = fNext; 245 if (fNext) 246 fNext = fList->GetPrevious(fNext); 247 return fCurrent; 248 } 249 250 Element *Remove() 251 { 252 Element *element = fCurrent; 253 if (fCurrent) { 254 fList->Remove(fCurrent); 255 fCurrent = NULL; 256 } 257 return element; 258 } 259 260 ReverseIterator &operator=(const ReverseIterator &other) 261 { 262 fList = other.fList; 263 fCurrent = other.fCurrent; 264 fNext = other.fNext; 265 return *this; 266 } 267 268 void Rewind() 269 { 270 fCurrent = NULL; 271 fNext = fList->Last(); 272 } 273 274 private: 275 List *fList; 276 Element *fCurrent; 277 Element *fNext; 278 }; 279 280 class ConstReverseIterator { 281 public: 282 ConstReverseIterator(const List *list) 283 : 284 fList(list) 285 { 286 Rewind(); 287 } 288 289 ConstReverseIterator(const ConstReverseIterator &other) 290 { 291 *this = other; 292 } 293 294 bool HasNext() const 295 { 296 return fNext; 297 } 298 299 Element *Next() 300 { 301 Element *element = fNext; 302 if (fNext) 303 fNext = fList->GetPrevious(fNext); 304 return element; 305 } 306 307 ConstReverseIterator &operator=(const ConstReverseIterator &other) 308 { 309 fList = other.fList; 310 fNext = other.fNext; 311 return *this; 312 } 313 314 void Rewind() 315 { 316 fNext = fList->Last(); 317 } 318 319 private: 320 const List *fList; 321 Element *fNext; 322 }; 323 324 public: 325 DoublyLinkedList() : fFirst(NULL), fLast(NULL) {} 326 ~DoublyLinkedList() {} 327 328 inline bool IsEmpty() const { return (fFirst == NULL); } 329 330 inline void InsertBefore(Element* insertBefore, Element* element); 331 inline void InsertAfter(Element* insertAfter, Element* element); 332 inline void Insert(Element* element, bool back = true); 333 inline void Add(Element *element, bool back = true); 334 inline void Remove(Element *element); 335 336 inline void Swap(Element *a, Element *b); 337 338 inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList); 339 340 inline void RemoveAll(); 341 inline void MakeEmpty() { RemoveAll(); } 342 343 inline Element *First() const { return fFirst; } 344 inline Element *Last() const { return fLast; } 345 346 inline Element *Head() const { return fFirst; } 347 inline Element *Tail() const { return fLast; } 348 349 inline Element *RemoveHead(); 350 351 inline Element *GetPrevious(Element *element) const; 352 inline Element *GetNext(Element *element) const; 353 354 inline int32_t Size() const; 355 // O(n)! 356 357 inline Iterator GetIterator() { return Iterator(this); } 358 inline ConstIterator GetIterator() const { return ConstIterator(this); } 359 360 inline ReverseIterator GetReverseIterator() 361 { return ReverseIterator(this); } 362 inline ConstReverseIterator GetReverseIterator() const 363 { return ConstReverseIterator(this); } 364 365 private: 366 inline void Insert(Element* before, Element* element); 367 // TODO: Obsolete! Use InsertBefore() instead! 368 369 private: 370 Element *fFirst; 371 Element *fLast; 372 373 static GetLink sGetLink; 374 }; 375 376 377 // inline methods 378 379 // Insert 380 DOUBLY_LINKED_LIST_TEMPLATE_LIST 381 void 382 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *element, bool back) 383 { 384 if (element) { 385 if (back) { 386 // append 387 Link *elLink = sGetLink(element); 388 elLink->previous = fLast; 389 elLink->next = NULL; 390 if (fLast) 391 sGetLink(fLast)->next = element; 392 else 393 fFirst = element; 394 fLast = element; 395 } else { 396 // prepend 397 Link *elLink = sGetLink(element); 398 elLink->previous = NULL; 399 elLink->next = fFirst; 400 if (fFirst) 401 sGetLink(fFirst)->previous = element; 402 else 403 fLast = element; 404 fFirst = element; 405 } 406 } 407 } 408 409 410 DOUBLY_LINKED_LIST_TEMPLATE_LIST 411 void 412 DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element) 413 { 414 if (before == NULL) { 415 Insert(element); 416 return; 417 } 418 if (element == NULL) 419 return; 420 421 Link *beforeLink = sGetLink(before); 422 Link *link = sGetLink(element); 423 424 link->next = before; 425 link->previous = beforeLink->previous; 426 if (link->previous != NULL) 427 sGetLink(link->previous)->next = element; 428 beforeLink->previous = element; 429 430 if (fFirst == before) 431 fFirst = element; 432 } 433 434 435 DOUBLY_LINKED_LIST_TEMPLATE_LIST 436 void 437 DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* after, Element* element) 438 { 439 ASSERT(element != NULL); 440 441 if (after == NULL) { 442 Insert(element, false); 443 return; 444 } 445 446 Link* afterLink = sGetLink(after); 447 Link* link = sGetLink(element); 448 449 link->previous = after; 450 link->next = afterLink->next; 451 afterLink->next = element; 452 453 if (link->next != NULL) 454 sGetLink(link->next)->previous = element; 455 else 456 fLast = element; 457 } 458 459 460 DOUBLY_LINKED_LIST_TEMPLATE_LIST 461 void 462 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element) 463 { 464 InsertBefore(before, element); 465 } 466 467 468 // Add 469 DOUBLY_LINKED_LIST_TEMPLATE_LIST 470 void 471 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back) 472 { 473 Insert(element, back); 474 } 475 476 // Remove 477 DOUBLY_LINKED_LIST_TEMPLATE_LIST 478 void 479 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element *element) 480 { 481 if (element) { 482 Link *elLink = sGetLink(element); 483 if (elLink->previous) 484 sGetLink(elLink->previous)->next = elLink->next; 485 else 486 fFirst = elLink->next; 487 if (elLink->next) 488 sGetLink(elLink->next)->previous = elLink->previous; 489 else 490 fLast = elLink->previous; 491 elLink->previous = NULL; 492 elLink->next = NULL; 493 } 494 } 495 496 // Swap 497 DOUBLY_LINKED_LIST_TEMPLATE_LIST 498 void 499 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element *a, Element *b) 500 { 501 if (a && b && a != b) { 502 Element *aNext = sGetLink(a)->next; 503 Element *bNext = sGetLink(b)->next; 504 if (a == bNext) { 505 Remove(a); 506 Insert(b, a); 507 } else if (b == aNext) { 508 Remove(b); 509 Insert(a, b); 510 } else { 511 Remove(a); 512 Remove(b); 513 Insert(aNext, b); 514 Insert(bNext, a); 515 } 516 } 517 } 518 519 // MoveFrom 520 DOUBLY_LINKED_LIST_TEMPLATE_LIST 521 void 522 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList) 523 { 524 if (fromList && fromList->fFirst) { 525 if (fFirst) { 526 sGetLink(fLast)->next = fromList->fFirst; 527 sGetLink(fromList->fFirst)->previous = fLast; 528 fLast = fromList->fLast; 529 } else { 530 fFirst = fromList->fFirst; 531 fLast = fromList->fLast; 532 } 533 fromList->fFirst = NULL; 534 fromList->fLast = NULL; 535 } 536 } 537 538 // RemoveAll 539 DOUBLY_LINKED_LIST_TEMPLATE_LIST 540 void 541 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 542 { 543 Element *element = fFirst; 544 while (element) { 545 Link *elLink = sGetLink(element); 546 element = elLink->next; 547 elLink->previous = NULL; 548 elLink->next = NULL; 549 } 550 fFirst = NULL; 551 fLast = NULL; 552 } 553 554 // RemoveHead 555 DOUBLY_LINKED_LIST_TEMPLATE_LIST 556 Element * 557 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 558 { 559 Element *element = Head(); 560 Remove(element); 561 return element; 562 } 563 564 // GetPrevious 565 DOUBLY_LINKED_LIST_TEMPLATE_LIST 566 Element * 567 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const 568 { 569 Element *result = NULL; 570 if (element) 571 result = sGetLink(element)->previous; 572 return result; 573 } 574 575 // GetNext 576 DOUBLY_LINKED_LIST_TEMPLATE_LIST 577 Element * 578 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const 579 { 580 Element *result = NULL; 581 if (element) 582 result = sGetLink(element)->next; 583 return result; 584 } 585 586 // Size 587 DOUBLY_LINKED_LIST_TEMPLATE_LIST 588 int32_t 589 DOUBLY_LINKED_LIST_CLASS_NAME::Size() const 590 { 591 int32_t count = 0; 592 for (Element* element = First(); element; element = GetNext(element)) 593 count++; 594 return count; 595 } 596 597 // sGetLink 598 DOUBLY_LINKED_LIST_TEMPLATE_LIST 599 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 600 601 602 } // namespace FSShell 603 604 using FSShell::DoublyLinkedListLink; 605 using FSShell::DoublyLinkedListLinkImpl; 606 using FSShell::DoublyLinkedListStandardGetLink; 607 using FSShell::DoublyLinkedListMemberGetLink; 608 using FSShell::DoublyLinkedListCLink; 609 using FSShell::DoublyLinkedList; 610 611 612 #endif /* __cplusplus */ 613 614 #endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 615