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 576