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 15namespace FSShell { 16 17 18// DoublyLinkedListLink 19template<typename Element> 20class DoublyLinkedListLink { 21public: 22 DoublyLinkedListLink() : next(NULL), previous(NULL) {} 23 ~DoublyLinkedListLink() {} 24 25 Element *next; 26 Element *previous; 27}; 28 29// DoublyLinkedListLinkImpl 30template<typename Element> 31class DoublyLinkedListLinkImpl { 32private: 33 typedef DoublyLinkedListLink<Element> DLL_Link; 34 35public: 36 DoublyLinkedListLinkImpl() : fDoublyLinkedListLink() {} 37 ~DoublyLinkedListLinkImpl() {} 38 39 DLL_Link *GetDoublyLinkedListLink() 40 { return &fDoublyLinkedListLink; } 41 const DLL_Link *GetDoublyLinkedListLink() const 42 { return &fDoublyLinkedListLink; } 43 44private: 45 DLL_Link fDoublyLinkedListLink; 46}; 47 48// DoublyLinkedListStandardGetLink 49template<typename Element> 50class DoublyLinkedListStandardGetLink { 51private: 52 typedef DoublyLinkedListLink<Element> Link; 53 54public: 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 67template<typename Element, 68 DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink> 69class DoublyLinkedListMemberGetLink { 70private: 71 typedef DoublyLinkedListLink<Element> Link; 72 73public: 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 86template<typename Element> 87class 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 109template<typename Element, 110 typename GetLink = DoublyLinkedListStandardGetLink<Element> > 111class DoublyLinkedList { 112private: 113 typedef DoublyLinkedList<Element, GetLink> List; 114 typedef DoublyLinkedListLink<Element> Link; 115 116public: 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 324public: 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 365private: 366 inline void Insert(Element* before, Element* element); 367 // TODO: Obsolete! Use InsertBefore() instead! 368 369private: 370 Element *fFirst; 371 Element *fLast; 372 373 static GetLink sGetLink; 374}; 375 376 377// inline methods 378 379// Insert 380DOUBLY_LINKED_LIST_TEMPLATE_LIST 381void 382DOUBLY_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 410DOUBLY_LINKED_LIST_TEMPLATE_LIST 411void 412DOUBLY_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 435DOUBLY_LINKED_LIST_TEMPLATE_LIST 436void 437DOUBLY_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 460DOUBLY_LINKED_LIST_TEMPLATE_LIST 461void 462DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element) 463{ 464 InsertBefore(before, element); 465} 466 467 468// Add 469DOUBLY_LINKED_LIST_TEMPLATE_LIST 470void 471DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back) 472{ 473 Insert(element, back); 474} 475 476// Remove 477DOUBLY_LINKED_LIST_TEMPLATE_LIST 478void 479DOUBLY_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 497DOUBLY_LINKED_LIST_TEMPLATE_LIST 498void 499DOUBLY_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 520DOUBLY_LINKED_LIST_TEMPLATE_LIST 521void 522DOUBLY_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 539DOUBLY_LINKED_LIST_TEMPLATE_LIST 540void 541DOUBLY_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 555DOUBLY_LINKED_LIST_TEMPLATE_LIST 556Element * 557DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 558{ 559 Element *element = Head(); 560 Remove(element); 561 return element; 562} 563 564// GetPrevious 565DOUBLY_LINKED_LIST_TEMPLATE_LIST 566Element * 567DOUBLY_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 576DOUBLY_LINKED_LIST_TEMPLATE_LIST 577Element * 578DOUBLY_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 587DOUBLY_LINKED_LIST_TEMPLATE_LIST 588int32_t 589DOUBLY_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 598DOUBLY_LINKED_LIST_TEMPLATE_LIST 599GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 600 601 602} // namespace FSShell 603 604using FSShell::DoublyLinkedListLink; 605using FSShell::DoublyLinkedListLinkImpl; 606using FSShell::DoublyLinkedListStandardGetLink; 607using FSShell::DoublyLinkedListMemberGetLink; 608using FSShell::DoublyLinkedListCLink; 609using FSShell::DoublyLinkedList; 610 611 612#endif /* __cplusplus */ 613 614#endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 615