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