headers/private/fs_shell/DoublyLinkedList.h

   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 Insert(Element *element, bool back = true);
 331         inline void Insert(Element *before, Element *element);
 332         inline void Add(Element *element, bool back = true);
 333         inline void Remove(Element *element);
 334
 335         inline void Swap(Element *a, Element *b);
 336
 337         inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList);
 338
 339         inline void RemoveAll();
 340         inline void MakeEmpty()                         { RemoveAll(); }
 341
 342         inline Element *First() const           { return fFirst; }
 343         inline Element *Last() const            { return fLast; }
 344
 345         inline Element *Head() const            { return fFirst; }
 346         inline Element *Tail() const            { return fLast; }
 347
 348         inline Element *RemoveHead();
 349
 350         inline Element *GetPrevious(Element *element) const;
 351         inline Element *GetNext(Element *element) const;
 352
 353         inline int32_t Size() const;
 354                 // O(n)!
 355
 356         inline Iterator GetIterator()                           { return Iterator(this); }
 357         inline ConstIterator GetIterator() const        { return ConstIterator(this); }
 358
 359         inline ReverseIterator GetReverseIterator()
 360                 { return ReverseIterator(this); }
 361         inline ConstReverseIterator GetReverseIterator() const
 362                 { return ConstReverseIterator(this); }
 363
 364 private:
 365         Element *fFirst;
 366         Element *fLast;
 367
 368         static GetLink  sGetLink;
 369 };
 370
 371
 372 // inline methods
 373
 374 // Insert
 375 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 376 void
 377 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *element, bool back)
 378 {
 379         if (element) {
 380                 if (back) {
 381                         // append
 382                         Link *elLink = sGetLink(element);
 383                         elLink->previous = fLast;
 384                         elLink->next = NULL;
 385                         if (fLast)
 386                                 sGetLink(fLast)->next = element;
 387                         else
 388                                 fFirst = element;
 389                         fLast = element;
 390                 } else {
 391                         // prepend
 392                         Link *elLink = sGetLink(element);
 393                         elLink->previous = NULL;
 394                         elLink->next = fFirst;
 395                         if (fFirst)
 396                                 sGetLink(fFirst)->previous = element;
 397                         else
 398                                 fLast = element;
 399                         fFirst = element;
 400                 }
 401         }
 402 }
 403
 404 // Insert
 405 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 406 void
 407 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *before, Element *element)
 408 {
 409         if (before == NULL) {
 410                 Insert(element);
 411                 return;
 412         }
 413         if (element == NULL)
 414                 return;
 415
 416         Link *beforeLink = sGetLink(before);
 417         Link *link = sGetLink(element);
 418
 419         link->next = before;
 420         link->previous = beforeLink->previous;
 421         if (link->previous != NULL)
 422                 sGetLink(link->previous)->next = element;
 423         beforeLink->previous = element;
 424
 425         if (fFirst == before)
 426                 fFirst = element;
 427 }
 428
 429 // Add
 430 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 431 void
 432 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back)
 433 {
 434         Insert(element, back);
 435 }
 436
 437 // Remove
 438 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 439 void
 440 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element *element)
 441 {
 442         if (element) {
 443                 Link *elLink = sGetLink(element);
 444                 if (elLink->previous)
 445                         sGetLink(elLink->previous)->next = elLink->next;
 446                 else
 447                         fFirst = elLink->next;
 448                 if (elLink->next)
 449                         sGetLink(elLink->next)->previous = elLink->previous;
 450                 else
 451                         fLast = elLink->previous;
 452                 elLink->previous = NULL;
 453                 elLink->next = NULL;
 454         }
 455 }
 456
 457 // Swap
 458 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 459 void
 460 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element *a, Element *b)
 461 {
 462         if (a && b && a != b) {
 463                 Element *aNext = sGetLink(a)->next;
 464                 Element *bNext = sGetLink(b)->next;
 465                 if (a == bNext) {
 466                         Remove(a);
 467                         Insert(b, a);
 468                 } else if (b == aNext) {
 469                         Remove(b);
 470                         Insert(a, b);
 471                 } else {
 472                         Remove(a);
 473                         Remove(b);
 474                         Insert(aNext, b);
 475                         Insert(bNext, a);
 476                 }
 477         }
 478 }
 479
 480 // MoveFrom
 481 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 482 void
 483 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList)
 484 {
 485         if (fromList && fromList->fFirst) {
 486                 if (fFirst) {
 487                         sGetLink(fLast)->next = fromList->fFirst;
 488                         sGetLink(fromList->fFirst)->previous = fLast;
 489                         fLast = fromList->fLast;
 490                 } else {
 491                         fFirst = fromList->fFirst;
 492                         fLast = fromList->fLast;
 493                 }
 494                 fromList->fFirst = NULL;
 495                 fromList->fLast = NULL;
 496         }
 497 }
 498
 499 // RemoveAll
 500 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 501 void
 502 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
 503 {
 504         Element *element = fFirst;
 505         while (element) {
 506                 Link *elLink = sGetLink(element);
 507                 element = elLink->next;
 508                 elLink->previous = NULL;
 509                 elLink->next = NULL;
 510         }
 511         fFirst = NULL;
 512         fLast = NULL;
 513 }
 514
 515 // RemoveHead
 516 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 517 Element *
 518 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
 519 {
 520         Element *element = Head();
 521         Remove(element);
 522         return element;
 523 }
 524
 525 // GetPrevious
 526 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 527 Element *
 528 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const
 529 {
 530         Element *result = NULL;
 531         if (element)
 532                 result = sGetLink(element)->previous;
 533         return result;
 534 }
 535
 536 // GetNext
 537 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 538 Element *
 539 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const
 540 {
 541         Element *result = NULL;
 542         if (element)
 543                 result = sGetLink(element)->next;
 544         return result;
 545 }
 546
 547 // Size
 548 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 549 int32_t
 550 DOUBLY_LINKED_LIST_CLASS_NAME::Size() const
 551 {
 552         int32_t count = 0;
 553         for (Element* element = First(); element; element = GetNext(element))
 554                 count++;
 555         return count;
 556 }
 557
 558 // sGetLink
 559 DOUBLY_LINKED_LIST_TEMPLATE_LIST
 560 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
 561
 562
 563 }       // namespace FSShell
 564
 565 using FSShell::DoublyLinkedListLink;
 566 using FSShell::DoublyLinkedListLinkImpl;
 567 using FSShell::DoublyLinkedListStandardGetLink;
 568 using FSShell::DoublyLinkedListMemberGetLink;
 569 using FSShell::DoublyLinkedListCLink;
 570 using FSShell::DoublyLinkedList;
 571
 572
 573 #endif  /* __cplusplus */
 574
 575 #endif  // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H