1 /* 2 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3 * Copyright 2005-2010, Ingo Weinhold, ingo_weinhold@gmx.de. 4 * 5 * Distributed under the terms of the MIT License. 6 */ 7 #ifndef KERNEL_UTIL_SINGLY_LINKED_LIST_H 8 #define KERNEL_UTIL_SINGLY_LINKED_LIST_H 9 10 11 #include <SupportDefs.h> 12 13 14 #ifdef __cplusplus 15 16 // SinglyLinkedListLink 17 template<typename Element> 18 class SinglyLinkedListLink { 19 public: 20 SinglyLinkedListLink() : next(NULL) {} 21 ~SinglyLinkedListLink() {} 22 23 Element* next; 24 }; 25 26 // SinglyLinkedListLinkImpl 27 template<typename Element> 28 class SinglyLinkedListLinkImpl { 29 private: 30 typedef SinglyLinkedListLink<Element> SLL_Link; 31 32 public: 33 SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {} 34 ~SinglyLinkedListLinkImpl() {} 35 36 SLL_Link* GetSinglyLinkedListLink() 37 { return &fSinglyLinkedListLink; } 38 const SLL_Link* GetSinglyLinkedListLink() const 39 { return &fSinglyLinkedListLink; } 40 41 private: 42 SLL_Link fSinglyLinkedListLink; 43 }; 44 45 // SinglyLinkedListStandardGetLink 46 template<typename Element> 47 class SinglyLinkedListStandardGetLink { 48 private: 49 typedef SinglyLinkedListLink<Element> Link; 50 51 public: 52 inline Link* operator()(Element* element) const 53 { 54 return element->GetSinglyLinkedListLink(); 55 } 56 57 inline const Link* operator()(const Element* element) const 58 { 59 return element->GetSinglyLinkedListLink(); 60 } 61 }; 62 63 // SinglyLinkedListMemberGetLink 64 template<typename Element, 65 SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink> 66 class SinglyLinkedListMemberGetLink { 67 private: 68 typedef SinglyLinkedListLink<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 83 // for convenience 84 #define SINGLY_LINKED_LIST_TEMPLATE_LIST \ 85 template<typename Element, typename GetLink> 86 #define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink> 87 88 89 template<typename Element, 90 typename GetLink = SinglyLinkedListStandardGetLink<Element> > 91 class SinglyLinkedList { 92 private: 93 typedef SinglyLinkedList<Element, GetLink> List; 94 typedef SinglyLinkedListLink<Element> Link; 95 96 public: 97 class ConstIterator { 98 public: 99 ConstIterator(const List* list) 100 : 101 fList(list) 102 { 103 Rewind(); 104 } 105 106 ConstIterator(const ConstIterator& other) 107 { 108 *this = other; 109 } 110 111 bool HasNext() const 112 { 113 return fNext; 114 } 115 116 Element* Next() 117 { 118 Element* element = fNext; 119 if (fNext) 120 fNext = fList->GetNext(fNext); 121 return element; 122 } 123 124 ConstIterator& operator=(const ConstIterator& other) 125 { 126 fList = other.fList; 127 fNext = other.fNext; 128 return* this; 129 } 130 131 void Rewind() 132 { 133 fNext = fList->First(); 134 } 135 136 private: 137 const List* fList; 138 Element* fNext; 139 }; 140 141 public: 142 SinglyLinkedList() : fFirst(NULL) {} 143 ~SinglyLinkedList() {} 144 145 inline bool IsEmpty() const { return (fFirst == NULL); } 146 147 inline void Add(Element* element); 148 inline bool Remove(Element* element); 149 inline void Remove(Element* previous, Element* element); 150 151 inline void MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList); 152 // O(1) if either list is empty, otherwise O(n). 153 154 inline void RemoveAll(); 155 inline void MakeEmpty() { RemoveAll(); } 156 157 inline Element* First() const { return fFirst; } 158 inline Element* Head() const { return fFirst; } 159 160 inline Element* RemoveHead(); 161 162 inline Element* GetNext(Element* element) const; 163 164 inline int32 Count() const; 165 // O(n)! 166 167 inline ConstIterator GetIterator() const { return ConstIterator(this); } 168 169 private: 170 Element *fFirst; 171 172 static GetLink sGetLink; 173 }; 174 175 176 // inline methods 177 178 // Add 179 SINGLY_LINKED_LIST_TEMPLATE_LIST 180 void 181 SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element) 182 { 183 if (element != NULL) { 184 sGetLink(element)->next = fFirst; 185 fFirst = element; 186 } 187 } 188 189 190 /*! Removes \a element from the list. 191 It is safe to call the list with a \c NULL element or an element that isn't 192 in the list. 193 \param element The element to be removed. 194 \return \c true, if the element was in the list and has been removed, 195 \c false otherwise. 196 */ 197 SINGLY_LINKED_LIST_TEMPLATE_LIST 198 bool 199 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element) 200 { 201 if (element == NULL) 202 return false; 203 204 Element* next = fFirst; 205 Element* last = NULL; 206 while (element != next) { 207 if (next == NULL) 208 return false; 209 last = next; 210 next = sGetLink(next)->next; 211 } 212 213 Link* elementLink = sGetLink(element); 214 if (last == NULL) 215 fFirst = elementLink->next; 216 else 217 sGetLink(last)->next = elementLink->next; 218 219 elementLink->next = NULL; 220 return true; 221 } 222 223 224 SINGLY_LINKED_LIST_TEMPLATE_LIST 225 void 226 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* previous, Element* element) 227 { 228 // ASSERT(previous == NULL 229 // ? fFirst == element : sGetLink(previous)->next == element); 230 231 Link* elementLink = sGetLink(element); 232 if (previous == NULL) 233 fFirst = elementLink->next; 234 else 235 sGetLink(previous)->next = elementLink->next; 236 237 elementLink->next = NULL; 238 } 239 240 241 SINGLY_LINKED_LIST_TEMPLATE_LIST 242 void 243 SINGLY_LINKED_LIST_CLASS_NAME::MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList) 244 { 245 if (fromList->fFirst == NULL) 246 return; 247 248 if (fFirst == NULL) { 249 // This list is empty -- just transfer the head. 250 fFirst = fromList->fFirst; 251 fromList->fFirst = NULL; 252 return; 253 } 254 255 // Neither list is empty -- find the tail of this list. 256 Element* tail = fFirst; 257 while (Element* next = sGetLink(tail)->next) 258 tail = next; 259 260 sGetLink(tail)->next = fromList->fFirst; 261 fromList->fFirst = NULL; 262 } 263 264 265 // RemoveAll 266 SINGLY_LINKED_LIST_TEMPLATE_LIST 267 void 268 SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll() 269 { 270 Element* element = fFirst; 271 while (element) { 272 Link* elLink = sGetLink(element); 273 element = elLink->next; 274 elLink->next = NULL; 275 } 276 fFirst = NULL; 277 } 278 279 // RemoveHead 280 SINGLY_LINKED_LIST_TEMPLATE_LIST 281 Element* 282 SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead() 283 { 284 Element* element = Head(); 285 Remove(element); 286 return element; 287 } 288 289 // GetNext 290 SINGLY_LINKED_LIST_TEMPLATE_LIST 291 Element* 292 SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const 293 { 294 Element* result = NULL; 295 if (element) 296 result = sGetLink(element)->next; 297 return result; 298 } 299 300 // Size 301 SINGLY_LINKED_LIST_TEMPLATE_LIST 302 int32 303 SINGLY_LINKED_LIST_CLASS_NAME::Count() const 304 { 305 int32 count = 0; 306 for (Element* element = First(); element; element = GetNext(element)) 307 count++; 308 return count; 309 } 310 311 // sGetLink 312 SINGLY_LINKED_LIST_TEMPLATE_LIST 313 GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink; 314 315 #endif /* __cplusplus */ 316 317 #endif // _KERNEL_UTIL_SINGLY_LINKED_LIST_H 318