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 // for convenience 83 #define DOUBLY_LINKED_LIST_TEMPLATE_LIST \ 84 template<typename Element, typename GetLink> 85 #define DOUBLY_LINKED_LIST_CLASS_NAME DoublyLinkedList<Element, GetLink> 86 87 // DoublyLinkedList 88 template<typename Element, 89 typename GetLink = DoublyLinkedListStandardGetLink<Element> > 90 class DoublyLinkedList { 91 private: 92 typedef DoublyLinkedList<Element, GetLink> List; 93 typedef DoublyLinkedListLink<Element> Link; 94 95 public: 96 class Iterator { 97 public: 98 Iterator(List *list) 99 : 100 fList(list) 101 { 102 Rewind(); 103 } 104 105 Iterator(const Iterator &other) 106 { 107 *this = other; 108 } 109 110 bool HasNext() const 111 { 112 return fNext; 113 } 114 115 Element *Next() 116 { 117 fCurrent = fNext; 118 if (fNext) 119 fNext = fList->GetNext(fNext); 120 return fCurrent; 121 } 122 123 Element *Remove() 124 { 125 Element *element = fCurrent; 126 if (fCurrent) { 127 fList->Remove(fCurrent); 128 fCurrent = NULL; 129 } 130 return element; 131 } 132 133 Iterator &operator=(const Iterator &other) 134 { 135 fList = other.fList; 136 fCurrent = other.fCurrent; 137 fNext = other.fNext; 138 return *this; 139 } 140 141 void Rewind() 142 { 143 fCurrent = NULL; 144 fNext = fList->First(); 145 } 146 147 private: 148 List *fList; 149 Element *fCurrent; 150 Element *fNext; 151 }; 152 153 class ConstIterator { 154 public: 155 ConstIterator(const List *list) 156 : 157 fList(list) 158 { 159 Rewind(); 160 } 161 162 ConstIterator(const ConstIterator &other) 163 { 164 *this = other; 165 } 166 167 bool HasNext() const 168 { 169 return fNext; 170 } 171 172 Element *Next() 173 { 174 Element *element = fNext; 175 if (fNext) 176 fNext = fList->GetNext(fNext); 177 return element; 178 } 179 180 ConstIterator &operator=(const ConstIterator &other) 181 { 182 fList = other.fList; 183 fNext = other.fNext; 184 return *this; 185 } 186 187 void Rewind() 188 { 189 fNext = fList->First(); 190 } 191 192 private: 193 const List *fList; 194 Element *fNext; 195 }; 196 197 public: 198 DoublyLinkedList() : fFirst(NULL), fLast(NULL) {} 199 ~DoublyLinkedList() {} 200 201 inline bool IsEmpty() const { return (fFirst == NULL); } 202 203 inline void Insert(Element *element, bool back = true); 204 inline void Add(Element *element, bool back = true); 205 inline void Remove(Element *element); 206 207 inline void Swap(Element *a, Element *b); 208 209 inline void MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList); 210 211 inline void RemoveAll(); 212 inline void MakeEmpty() { RemoveAll(); } 213 214 inline Element *First() const { return fFirst; } 215 inline Element *Last() const { return fLast; } 216 217 inline Element *Head() const { return fFirst; } 218 inline Element *Tail() const { return fLast; } 219 220 inline Element *RemoveHead(); 221 222 inline Element *GetPrevious(Element *element) const; 223 inline Element *GetNext(Element *element) const; 224 225 inline int32 Size() const; 226 // O(n)! 227 228 inline Iterator GetIterator() { return Iterator(this); } 229 inline ConstIterator GetIterator() const { return ConstIterator(this); } 230 231 private: 232 Element *fFirst; 233 Element *fLast; 234 235 static GetLink sGetLink; 236 }; 237 238 239 // inline methods 240 241 // Insert 242 DOUBLY_LINKED_LIST_TEMPLATE_LIST 243 void 244 DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element *element, bool back) 245 { 246 if (element) { 247 if (back) { 248 // append 249 Link *elLink = sGetLink(element); 250 elLink->previous = fLast; 251 elLink->next = NULL; 252 if (fLast) 253 sGetLink(fLast)->next = element; 254 else 255 fFirst = element; 256 fLast = element; 257 } else { 258 // prepend 259 Link *elLink = sGetLink(element); 260 elLink->previous = NULL; 261 elLink->next = fFirst; 262 if (fFirst) 263 sGetLink(fFirst)->previous = element; 264 else 265 fLast = element; 266 fFirst = element; 267 } 268 } 269 } 270 271 // Add 272 DOUBLY_LINKED_LIST_TEMPLATE_LIST 273 void 274 DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element *element, bool back) 275 { 276 Insert(element, back); 277 } 278 279 // Remove 280 DOUBLY_LINKED_LIST_TEMPLATE_LIST 281 void 282 DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element *element) 283 { 284 if (element) { 285 Link *elLink = sGetLink(element); 286 if (elLink->previous) 287 sGetLink(elLink->previous)->next = elLink->next; 288 else 289 fFirst = elLink->next; 290 if (elLink->next) 291 sGetLink(elLink->next)->previous = elLink->previous; 292 else 293 fLast = elLink->previous; 294 elLink->previous = NULL; 295 elLink->next = NULL; 296 } 297 } 298 299 // Swap 300 DOUBLY_LINKED_LIST_TEMPLATE_LIST 301 void 302 DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element *a, Element *b) 303 { 304 if (a && b && a != b) { 305 Link *aLink = sGetLink(a); 306 Link *bLink = sGetLink(b); 307 Element *aPrev = aLink->previous; 308 Element *bPrev = bLink->previous; 309 Element *aNext = aLink->next; 310 Element *bNext = bLink->next; 311 // place a 312 if (bPrev) 313 sGetLink(bPrev)->next = a; 314 else 315 fFirst = a; 316 if (bNext) 317 sGetLink(bNext)->previous = a; 318 else 319 fLast = a; 320 aLink->previous = bPrev; 321 aLink->next = bNext; 322 // place b 323 if (aPrev) 324 sGetLink(aPrev)->next = b; 325 else 326 fFirst = b; 327 if (aNext) 328 sGetLink(aNext)->previous = b; 329 else 330 fLast = b; 331 bLink->previous = aPrev; 332 bLink->next = aNext; 333 } 334 } 335 336 // MoveFrom 337 DOUBLY_LINKED_LIST_TEMPLATE_LIST 338 void 339 DOUBLY_LINKED_LIST_CLASS_NAME::MoveFrom(DOUBLY_LINKED_LIST_CLASS_NAME *fromList) 340 { 341 if (fromList && fromList->fFirst) { 342 if (fFirst) { 343 sGetLink(fLast)->next = fromList->fFirst; 344 sGetLink(fFirst)->previous = fLast; 345 fLast = fromList->fLast; 346 } else { 347 fFirst = fromList->fFirst; 348 fLast = fromList->fLast; 349 } 350 fromList->fFirst = NULL; 351 fromList->fLast = NULL; 352 } 353 } 354 355 // RemoveAll 356 DOUBLY_LINKED_LIST_TEMPLATE_LIST 357 void 358 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll() 359 { 360 Element *element = fFirst; 361 while (element) { 362 Link *elLink = sGetLink(element); 363 element = elLink->next; 364 elLink->previous = NULL; 365 elLink->next = NULL; 366 } 367 fFirst = NULL; 368 fLast = NULL; 369 } 370 371 // RemoveHead 372 DOUBLY_LINKED_LIST_TEMPLATE_LIST 373 Element * 374 DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead() 375 { 376 Element *element = Head(); 377 Remove(element); 378 return element; 379 } 380 381 // GetPrevious 382 DOUBLY_LINKED_LIST_TEMPLATE_LIST 383 Element * 384 DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element *element) const 385 { 386 Element *result = NULL; 387 if (element) 388 result = sGetLink(element)->previous; 389 return result; 390 } 391 392 // GetNext 393 DOUBLY_LINKED_LIST_TEMPLATE_LIST 394 Element * 395 DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element *element) const 396 { 397 Element *result = NULL; 398 if (element) 399 result = sGetLink(element)->next; 400 return result; 401 } 402 403 // Size 404 DOUBLY_LINKED_LIST_TEMPLATE_LIST 405 int32 406 DOUBLY_LINKED_LIST_CLASS_NAME::Size() const 407 { 408 int32 count = 0; 409 for (Element* element = First(); element; element = GetNext(element)) 410 count++; 411 return count; 412 } 413 414 // sGetLink 415 DOUBLY_LINKED_LIST_TEMPLATE_LIST 416 GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink; 417 418 #endif /* __cplusplus */ 419 420 #endif // _KERNEL_UTIL_DOUBLY_LINKED_LIST_H 421