1 /* 2 * Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3 * Copyright 2005-2006, Ingo Weinhold, bonefish@users.sf.net. All rights reserved. 4 * 5 * Distributed under the terms of the MIT License. 6 */ 7 #ifndef KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H 8 #define KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H 9 10 11 #include <util/DoublyLinkedList.h> 12 13 14 /*! 15 A doubly linked queue is like a doubly linked list, but only has a pointer 16 to the head of the list, none to its tail. 17 */ 18 19 20 #ifdef __cplusplus 21 22 // for convenience 23 #define DOUBLY_LINKED_QUEUE_CLASS_NAME DoublyLinkedQueue<Element, GetLink> 24 25 26 template<typename Element, 27 typename GetLink = DoublyLinkedListStandardGetLink<Element> > 28 class DoublyLinkedQueue { 29 private: 30 typedef DoublyLinkedQueue<Element, GetLink> Queue; 31 typedef DoublyLinkedListLink<Element> Link; 32 33 public: 34 class Iterator { 35 public: 36 Iterator(Queue *queue) 37 : 38 fQueue(queue) 39 { 40 Rewind(); 41 } 42 43 Iterator(const Iterator &other) 44 { 45 *this = other; 46 } 47 48 bool HasNext() const 49 { 50 return fNext; 51 } 52 53 Element *Next() 54 { 55 fCurrent = fNext; 56 if (fNext) 57 fNext = fQueue->GetNext(fNext); 58 return fCurrent; 59 } 60 61 Element *Remove() 62 { 63 Element *element = fCurrent; 64 if (fCurrent) { 65 fQueue->Remove(fCurrent); 66 fCurrent = NULL; 67 } 68 return element; 69 } 70 71 Iterator &operator=(const Iterator &other) 72 { 73 fQueue = other.fQueue; 74 fCurrent = other.fCurrent; 75 fNext = other.fNext; 76 return *this; 77 } 78 79 void Rewind() 80 { 81 fCurrent = NULL; 82 fNext = fQueue->First(); 83 } 84 85 private: 86 Queue *fQueue; 87 Element *fCurrent; 88 Element *fNext; 89 }; 90 91 class ConstIterator { 92 public: 93 ConstIterator(const Queue *queue) 94 : 95 fQueue(queue) 96 { 97 Rewind(); 98 } 99 100 ConstIterator(const ConstIterator &other) 101 { 102 *this = other; 103 } 104 105 bool HasNext() const 106 { 107 return fNext; 108 } 109 110 Element *Next() 111 { 112 Element *element = fNext; 113 if (fNext) 114 fNext = fQueue->GetNext(fNext); 115 return element; 116 } 117 118 ConstIterator &operator=(const ConstIterator &other) 119 { 120 fQueue = other.fQueue; 121 fNext = other.fNext; 122 return *this; 123 } 124 125 void Rewind() 126 { 127 fNext = fQueue->First(); 128 } 129 130 private: 131 const Queue *fQueue; 132 Element *fNext; 133 }; 134 135 public: 136 DoublyLinkedQueue() : fFirst(NULL) {} 137 ~DoublyLinkedQueue() {} 138 139 inline bool IsEmpty() const { return (fFirst == NULL); } 140 141 inline void Insert(Element *element); 142 inline void InsertBefore(Element *before, Element *element); 143 inline void Add(Element *element); 144 inline void Remove(Element *element); 145 146 inline void Swap(Element *a, Element *b); 147 148 inline void MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList); 149 150 inline void RemoveAll(); 151 inline void MakeEmpty() { RemoveAll(); } 152 153 inline Element *First() const { return fFirst; } 154 inline Element *Head() const { return fFirst; } 155 156 inline Element *RemoveHead(); 157 158 inline Element *GetPrevious(Element *element) const; 159 inline Element *GetNext(Element *element) const; 160 161 inline int32 Size() const; 162 // O(n)! 163 164 inline Iterator GetIterator() { return Iterator(this); } 165 inline ConstIterator GetIterator() const { return ConstIterator(this); } 166 167 private: 168 Element *fFirst; 169 170 static GetLink sGetLink; 171 }; 172 173 174 // inline methods 175 176 // Insert 177 DOUBLY_LINKED_LIST_TEMPLATE_LIST 178 void 179 DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *element) 180 { 181 if (element) { 182 Link *elLink = sGetLink(element); 183 elLink->previous = NULL; 184 elLink->next = fFirst; 185 if (fFirst) 186 sGetLink(fFirst)->previous = element; 187 fFirst = element; 188 } 189 } 190 191 // Insert 192 DOUBLY_LINKED_LIST_TEMPLATE_LIST 193 void 194 DOUBLY_LINKED_QUEUE_CLASS_NAME::InsertBefore(Element *before, Element *element) 195 { 196 if (before == NULL) { 197 Insert(element); 198 return; 199 } 200 if (element == NULL) 201 return; 202 203 Link *beforeLink = sGetLink(before); 204 Link *link = sGetLink(element); 205 206 link->next = before; 207 link->previous = beforeLink->previous; 208 if (link->previous != NULL) 209 sGetLink(link->previous)->next = element; 210 beforeLink->previous = element; 211 212 if (fFirst == before) 213 fFirst = element; 214 } 215 216 // Add 217 DOUBLY_LINKED_LIST_TEMPLATE_LIST 218 void 219 DOUBLY_LINKED_QUEUE_CLASS_NAME::Add(Element *element) 220 { 221 Insert(element); 222 } 223 224 // Remove 225 DOUBLY_LINKED_LIST_TEMPLATE_LIST 226 void 227 DOUBLY_LINKED_QUEUE_CLASS_NAME::Remove(Element *element) 228 { 229 if (element == NULL) 230 return; 231 232 #if DEBUG_DOUBLY_LINKED_LIST 233 ASSERT_PRINT(fFirst != NULL, 234 "queue: %p, element: %p\n", this, element); 235 #endif 236 237 Link *elLink = sGetLink(element); 238 if (element == fFirst) 239 fFirst = elLink->next; 240 else 241 sGetLink(elLink->previous)->next = elLink->next; 242 243 if (elLink->next) 244 sGetLink(elLink->next)->previous = elLink->previous; 245 246 elLink->next = elLink->previous = NULL; 247 } 248 249 // Swap 250 DOUBLY_LINKED_LIST_TEMPLATE_LIST 251 void 252 DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b) 253 { 254 if (a && b && a != b) { 255 Link *aLink = sGetLink(a); 256 Link *bLink = sGetLink(b); 257 Element *aPrev = aLink->previous; 258 Element *bPrev = bLink->previous; 259 Element *aNext = aLink->next; 260 Element *bNext = bLink->next; 261 // place a 262 if (bPrev) 263 sGetLink(bPrev)->next = a; 264 else 265 fFirst = a; 266 if (bNext) 267 sGetLink(bNext)->previous = a; 268 269 aLink->previous = bPrev; 270 aLink->next = bNext; 271 // place b 272 if (aPrev) 273 sGetLink(aPrev)->next = b; 274 else 275 fFirst = b; 276 if (aNext) 277 sGetLink(aNext)->previous = b; 278 279 bLink->previous = aPrev; 280 bLink->next = aNext; 281 } 282 } 283 284 // MoveFrom 285 DOUBLY_LINKED_LIST_TEMPLATE_LIST 286 void 287 DOUBLY_LINKED_QUEUE_CLASS_NAME::MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList) 288 { 289 if (fromList && fromList->fFirst) { 290 if (fFirst) { 291 Element *element = fFirst; 292 Link *elLink; 293 while ((elLink = sGetLink(element))->next) { 294 element = elLink->next; 295 } 296 elLink->next = fromList->fFirst; 297 } else { 298 fFirst = fromList->fFirst; 299 } 300 fromList->fFirst = NULL; 301 } 302 } 303 304 // RemoveAll 305 DOUBLY_LINKED_LIST_TEMPLATE_LIST 306 void 307 DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll() 308 { 309 Element *element = fFirst; 310 while (element) { 311 Link *elLink = sGetLink(element); 312 element = elLink->next; 313 elLink->previous = NULL; 314 elLink->next = NULL; 315 } 316 fFirst = NULL; 317 } 318 319 // RemoveHead 320 DOUBLY_LINKED_LIST_TEMPLATE_LIST 321 Element * 322 DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead() 323 { 324 Element *element = Head(); 325 Remove(element); 326 return element; 327 } 328 329 // GetPrevious 330 DOUBLY_LINKED_LIST_TEMPLATE_LIST 331 Element * 332 DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const 333 { 334 Element *result = NULL; 335 if (element) 336 result = sGetLink(element)->previous; 337 return result; 338 } 339 340 // GetNext 341 DOUBLY_LINKED_LIST_TEMPLATE_LIST 342 Element * 343 DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const 344 { 345 Element *result = NULL; 346 if (element) 347 result = sGetLink(element)->next; 348 return result; 349 } 350 351 // Size 352 DOUBLY_LINKED_LIST_TEMPLATE_LIST 353 int32 354 DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const 355 { 356 int32 count = 0; 357 for (Element* element = First(); element; element = GetNext(element)) 358 count++; 359 return count; 360 } 361 362 // sGetLink 363 DOUBLY_LINKED_LIST_TEMPLATE_LIST 364 GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink; 365 366 #endif /* __cplusplus */ 367 368 #endif // _KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H 369