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 void 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 SINGLY_LINKED_LIST_TEMPLATE_LIST 188 void 189 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element) 190 { 191 if (element == NULL) 192 return; 193 194 Element* next = fFirst; 195 Element* last = NULL; 196 while (next != NULL && element != next) { 197 last = next; 198 next = sGetLink(next)->next; 199 } 200 201 Link* elementLink = sGetLink(element); 202 if (last == NULL) 203 fFirst = elementLink->next; 204 else 205 sGetLink(last)->next = elementLink->next; 206 207 elementLink->next = NULL; 208 } 209 210 211 SINGLY_LINKED_LIST_TEMPLATE_LIST 212 void 213 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* previous, Element* element) 214 { 215 // ASSERT(previous == NULL 216 // ? fFirst == element : sGetLink(previous)->next == element); 217 218 Link* elementLink = sGetLink(element); 219 if (previous == NULL) 220 fFirst = elementLink->next; 221 else 222 sGetLink(previous)->next = elementLink->next; 223 224 elementLink->next = NULL; 225 } 226 227 228 SINGLY_LINKED_LIST_TEMPLATE_LIST 229 void 230 SINGLY_LINKED_LIST_CLASS_NAME::MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList) 231 { 232 if (fromList->fFirst == NULL) 233 return; 234 235 if (fFirst == NULL) { 236 // This list is empty -- just transfer the head. 237 fFirst = fromList->fFirst; 238 fromList->fFirst = NULL; 239 return; 240 } 241 242 // Neither list is empty -- find the tail of this list. 243 Element* tail = fFirst; 244 while (Element* next = sGetLink(tail)->next) 245 tail = next; 246 247 sGetLink(tail)->next = fromList->fFirst; 248 fromList->fFirst = NULL; 249 } 250 251 252 // RemoveAll 253 SINGLY_LINKED_LIST_TEMPLATE_LIST 254 void 255 SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll() 256 { 257 Element* element = fFirst; 258 while (element) { 259 Link* elLink = sGetLink(element); 260 element = elLink->next; 261 elLink->next = NULL; 262 } 263 fFirst = NULL; 264 } 265 266 // RemoveHead 267 SINGLY_LINKED_LIST_TEMPLATE_LIST 268 Element* 269 SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead() 270 { 271 Element* element = Head(); 272 Remove(element); 273 return element; 274 } 275 276 // GetNext 277 SINGLY_LINKED_LIST_TEMPLATE_LIST 278 Element* 279 SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const 280 { 281 Element* result = NULL; 282 if (element) 283 result = sGetLink(element)->next; 284 return result; 285 } 286 287 // Size 288 SINGLY_LINKED_LIST_TEMPLATE_LIST 289 int32 290 SINGLY_LINKED_LIST_CLASS_NAME::Size() const 291 { 292 int32 count = 0; 293 for (Element* element = First(); element; element = GetNext(element)) 294 count++; 295 return count; 296 } 297 298 // sGetLink 299 SINGLY_LINKED_LIST_TEMPLATE_LIST 300 GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink; 301 302 #endif /* __cplusplus */ 303 304 #endif // _KERNEL_UTIL_SINGLY_LINKED_LIST_H 305