1 /* 2 * Copyright 2005-2006, 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() : previous(NULL), next(NULL) {} 23 ~DoublyLinkedListLink() {} 24 25 Element *previous; 26 Element *next; 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 *Remove() 145 { 146 Element *element = fCurrent; 147 if (fCurrent) { 148 fList->Remove(fCurrent); 149 fCurrent = NULL; 150 } 151 return element; 152 } 153 154 Iterator &operator=(const Iterator &other) 155 { 156 fList = other.fList; 157 fCurrent = other.fCurrent; 158 fNext = other.fNext; 159 return *this; 160 } 161 162 void Rewind() 163 { 164 fCurrent = NULL; 165 fNext = fList->First(); 166 } 167 168 private: 169 List *fList; 170 Element *fCurrent; 171 Element *fNext; 172 }; 173 174 class ConstIterator { 175 public: 176 ConstIterator(const List *list) 177 : 178 fList(list) 179 { 180 Rewind(); 181 } 182 183 ConstIterator(const ConstIterator &other) 184 { 185 *this = other; 186 } 187 188 bool HasNext() const 189 { 190 return fNext; 191 } 192 193 Element *Next() 194 { 195 Element *element = fNext; 196 if (fNext) 197 fNext = fList->GetNext(fNext); 198 return element; 199 } 200 201 ConstIterator &operator=(const ConstIterator &other) 202 { 203 fList = other.fList; 204 fNext = other.fNext; 205 return *this; 206 } 207 208 void Rewind() 209 { 210 fNext = fList->First(); 211 } 212 213 private: 214 const List *fList; 215 Element *fNext; 216 }; 217 218 class ReverseIterator { 219 public: 220 ReverseIterator(List *list) 221 : 222 fList(list) 223 { 224 Rewind(); 225 } 226 227 ReverseIterator(const ReverseIterator &other) 228 { 229 *this = other; 230 } 231 232 bool HasNext() const 233 { 234 return fNext; 235 } 236 237 Element *Next() 238 { 239 fCurrent = fNext; 240 if (fNext) 241 fNext = fList->GetPrevious(fNext); 242 return fCurrent; 243 } 244 245 Element *Remove() 246 { 247 Element *element = fCurrent; 248 if (fCurrent) { 249 fList->Remove(fCurrent); 250 fCurrent = NULL; 251 } 252 return element; 253 } 254 255 ReverseIterator &operator=(const ReverseIterator &other) 256 { 257 fList = other.fList; 258 fCurrent = other.fCurrent; 259 fNext = other.fNext; 260 return *this; 261 } 262 263 void Rewind() 264 { 265 fCurrent = NULL; 266 fNext = fList->Last(); 267 } 268 269 private: 270 List *fList; 271 Element *fCurrent; 272 Element *fNext; 273 }; 274 275 class ConstReverseIterator { 276 public: 277 ConstReverseIterator(const List *list) 278 : 279 fList(list) 280 { 281 Rewind(); 282 } 283 284 ConstReverseIterator(const ConstReverseIterator &other) 285 { 286 *this = other; 287 } 288 289 bool HasNext() const 290 { 291 return fNext; 292 } 293 294 Element *Next() 295 { 296 Element *element = fNext; 297 if (fNext) 298 fNext = fList->GetPrevious(fNext); 299 return element; 300 } 301 302 ConstReverseIterator &operator=(const ConstReverseIterator &other) 303 { 304 fList = other.fList; 305 fNext = other.fNext; 306 return *this; 307 } 308 309 void Rewind() 310 { 311 fNext = fList->Last(); 312 } 313 314 private: 315 const List *fList; 316 Element *fNext; 317 }; 318 319 public: 320 DoublyLinkedList() : fFirst(NULL), fLast(NULL) {} 321 ~DoublyLinkedList() {} 322 323 inline bool IsEmpty() const { return (fFirst == NULL); } 324 325 inline void Insert(Element *element, bool back = true); 326 inline void Insert(Element *before, Element *element); 327 inline void Add(Element *element, bool back = true); 328 inline void Remove(Element *element); 329 330 inline void Swap(Element *a, Element *b); 331 332 inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList); 333 334 inline void RemoveAll(); 335 inline void MakeEmpty() { RemoveAll(); } 336 337 inline Element *First() const { return fFirst; } 338 inline Element *Last() const { return fLast; } 339 340 inline Element *Head() const { return fFirst; } 341 inline Element *Tail() const { return fLast; } 342 343 inline Element *RemoveHead(); 344 345 inline Element *GetPrevious(Element *element) const; 346 inline Element *GetNext(Element *element) const; 347 348 inline int32_t Size() const; 349 // O(n)! 350 351 inline Iterator GetIterator() { return Iterator(this); } 352 inline ConstIterator GetIterator() const { return ConstIterator(this); } 353 354 inline ReverseIterator GetReverseIterator() 355 { return ReverseIterator(this); } 356 inline ConstReverseIterator GetReverseIterator() const 357 { return ConstReverseIterator(this); } 358 359 private: 360 Element *fFirst; 361 Element *fLast; 362 363 static GetLink sGetLink; 364 }; 365 366 367 // inline methods 368 369 // Insert 370 DOUBLY_LINKED_LIST_TEMPLATE_LIST 371 void 372 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *element, bool back) 373 { 374 if (element) { 375 if (back) { 376 // append 377 Link *elLink = sGetLink(element); 378 elLink->previous = fLast; 379 elLink->next = NULL; 380 if (fLast) 381 sGetLink(fLast)->next = element; 382 else 383 fFirst = element; 384 fLast = element; 385 } else { 386 // prepend 387 Link *elLink = sGetLink(element); 388 elLink->previous = NULL; 389 elLink->next = fFirst; 390 if (fFirst) 391 sGetLink(fFirst)->previous = element; 392 else 393 fLast = element; 394 fFirst = element; 395 } 396 } 397 } 398 399 // Insert 400 DOUBLY_LINKED_LIST_TEMPLATE_LIST 401 void 402 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *before, Element *element) 403 { 404 if (before == NULL) { 405 Insert(element); 406 return; 407 } 408 if (element == NULL) 409 return; 410 411 Link *beforeLink = sGetLink(before); 412 Link *link = sGetLink(element); 413 414 link->next = before; 415 link->previous = beforeLink->previous; 416 if (link->previous != NULL) 417 sGetLink(link->previous)->next = element; 418 beforeLink->previous = element; 419 420 if (fFirst == before) 421 fFirst = element; 422 } 423 424 // Add 425 DOUBLY_LINKED_LIST_TEMPLATE_LIST 426 void 427 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back) 428 { 429 Insert(element, back); 430 } 431 432 // Remove 433 DOUBLY_LINKED_LIST_TEMPLATE_LIST 434 void 435 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element *element) 436 { 437 if (element) { 438 Link *elLink = sGetLink(element); 439 if (elLink->previous) 440 sGetLink(elLink->previous)->next = elLink->next; 441 else 442 fFirst = elLink->next; 443 if (elLink->next) 444 sGetLink(elLink->next)->previous = elLink->previous; 445 else 446 fLast = elLink->previous; 447 elLink->previous = NULL; 448 elLink->next = NULL; 449 } 450 } 451 452 // Swap 453 DOUBLY_LINKED_LIST_TEMPLATE_LIST 454 void 455 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element *a, Element *b) 456 { 457 if (a && b && a != b) { 458 Link *aLink = sGetLink(a); 459 Link *bLink = sGetLink(b); 460 Element *aPrev = aLink->previous; 461 Element *bPrev = bLink->previous; 462 Element *aNext = aLink->next; 463 Element *bNext = bLink->next; 464 // place a 465 if (bPrev) 466 sGetLink(bPrev)->next = a; 467 else 468 fFirst = a; 469 if (bNext) 470 sGetLink(bNext)->previous = a; 471 else 472 fLast = a; 473 aLink->previous = bPrev; 474 aLink->next = bNext; 475 // place b 476 if (aPrev) 477 sGetLink(aPrev)->next = b; 478 else 479 fFirst = b; 480 if (aNext) 481 sGetLink(aNext)->previous = b; 482 else 483 fLast = b; 484 bLink->previous = aPrev; 485 bLink->next = aNext; 486 } 487 } 488 489 // MoveFrom 490 DOUBLY_LINKED_LIST_TEMPLATE_LIST 491 void 492 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList) 493 { 494 if (fromList && fromList->fFirst) { 495 if (fFirst) { 496 sGetLink(fLast)->next = fromList->fFirst; 497 sGetLink(fFirst)->previous = fLast; 498 fLast = fromList->fLast; 499 } else { 500 fFirst = fromList->fFirst; 501 fLast = fromList->fLast; 502 } 503 fromList->fFirst = NULL; 504 fromList->fLast = NULL; 505 } 506 } 507 508 // RemoveAll 509 DOUBLY_LINKED_LIST_TEMPLATE_LIST 510 void 511 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 512 { 513 Element *element = fFirst; 514 while (element) { 515 Link *elLink = sGetLink(element); 516 element = elLink->next; 517 elLink->previous = NULL; 518 elLink->next = NULL; 519 } 520 fFirst = NULL; 521 fLast = NULL; 522 } 523 524 // RemoveHead 525 DOUBLY_LINKED_LIST_TEMPLATE_LIST 526 Element * 527 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 528 { 529 Element *element = Head(); 530 Remove(element); 531 return element; 532 } 533 534 // GetPrevious 535 DOUBLY_LINKED_LIST_TEMPLATE_LIST 536 Element * 537 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const 538 { 539 Element *result = NULL; 540 if (element) 541 result = sGetLink(element)->previous; 542 return result; 543 } 544 545 // GetNext 546 DOUBLY_LINKED_LIST_TEMPLATE_LIST 547 Element * 548 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const 549 { 550 Element *result = NULL; 551 if (element) 552 result = sGetLink(element)->next; 553 return result; 554 } 555 556 // Size 557 DOUBLY_LINKED_LIST_TEMPLATE_LIST 558 int32_t 559 DOUBLY_LINKED_LIST_CLASS_NAME::Size() const 560 { 561 int32_t count = 0; 562 for (Element* element = First(); element; element = GetNext(element)) 563 count++; 564 return count; 565 } 566 567 // sGetLink 568 DOUBLY_LINKED_LIST_TEMPLATE_LIST 569 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 570 571 572 } // namespace FSShell 573 574 using FSShell::DoublyLinkedListLink; 575 using FSShell::DoublyLinkedListLinkImpl; 576 using FSShell::DoublyLinkedListStandardGetLink; 577 using FSShell::DoublyLinkedListMemberGetLink; 578 using FSShell::DoublyLinkedListCLink; 579 using FSShell::DoublyLinkedList; 580 581 582 #endif /* __cplusplus */ 583 584 #endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 585