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 Insert(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::Insert(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) { 230 Link *elLink = sGetLink(element); 231 if (elLink->previous) 232 sGetLink(elLink->previous)->next = elLink->next; 233 else 234 fFirst = elLink->next; 235 if (elLink->next) 236 sGetLink(elLink->next)->previous = elLink->previous; 237 238 elLink->previous = NULL; 239 elLink->next = NULL; 240 } 241 } 242 243 // Swap 244 DOUBLY_LINKED_LIST_TEMPLATE_LIST 245 void 246 DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b) 247 { 248 if (a && b && a != b) { 249 Link *aLink = sGetLink(a); 250 Link *bLink = sGetLink(b); 251 Element *aPrev = aLink->previous; 252 Element *bPrev = bLink->previous; 253 Element *aNext = aLink->next; 254 Element *bNext = bLink->next; 255 // place a 256 if (bPrev) 257 sGetLink(bPrev)->next = a; 258 else 259 fFirst = a; 260 if (bNext) 261 sGetLink(bNext)->previous = a; 262 263 aLink->previous = bPrev; 264 aLink->next = bNext; 265 // place b 266 if (aPrev) 267 sGetLink(aPrev)->next = b; 268 else 269 fFirst = b; 270 if (aNext) 271 sGetLink(aNext)->previous = b; 272 273 bLink->previous = aPrev; 274 bLink->next = aNext; 275 } 276 } 277 278 // MoveFrom 279 DOUBLY_LINKED_LIST_TEMPLATE_LIST 280 void 281 DOUBLY_LINKED_QUEUE_CLASS_NAME::MoveFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList) 282 { 283 if (fromList && fromList->fFirst) { 284 if (fFirst) { 285 Element *element = fFirst; 286 Link *elLink; 287 while ((elLink = sGetLink(element))->next) { 288 element = elLink->next; 289 } 290 elLink->next = fromList->fFirst; 291 } else { 292 fFirst = fromList->fFirst; 293 } 294 fromList->fFirst = NULL; 295 } 296 } 297 298 // RemoveAll 299 DOUBLY_LINKED_LIST_TEMPLATE_LIST 300 void 301 DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll() 302 { 303 Element *element = fFirst; 304 while (element) { 305 Link *elLink = sGetLink(element); 306 element = elLink->next; 307 elLink->previous = NULL; 308 elLink->next = NULL; 309 } 310 fFirst = NULL; 311 } 312 313 // RemoveHead 314 DOUBLY_LINKED_LIST_TEMPLATE_LIST 315 Element * 316 DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead() 317 { 318 Element *element = Head(); 319 Remove(element); 320 return element; 321 } 322 323 // GetPrevious 324 DOUBLY_LINKED_LIST_TEMPLATE_LIST 325 Element * 326 DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const 327 { 328 Element *result = NULL; 329 if (element) 330 result = sGetLink(element)->previous; 331 return result; 332 } 333 334 // GetNext 335 DOUBLY_LINKED_LIST_TEMPLATE_LIST 336 Element * 337 DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const 338 { 339 Element *result = NULL; 340 if (element) 341 result = sGetLink(element)->next; 342 return result; 343 } 344 345 // Size 346 DOUBLY_LINKED_LIST_TEMPLATE_LIST 347 int32 348 DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const 349 { 350 int32 count = 0; 351 for (Element* element = First(); element; element = GetNext(element)) 352 count++; 353 return count; 354 } 355 356 // sGetLink 357 DOUBLY_LINKED_LIST_TEMPLATE_LIST 358 GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink; 359 360 #endif /* __cplusplus */ 361 362 #endif // _KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H 363