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