1 /* 2 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3 * Copyright 2005-2008, 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 147 inline void MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList); 148 // O(1) if either list is empty, otherwise O(n). 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* GetNext(Element* element) const; 159 160 inline int32 Size() const; 161 // O(n)! 162 163 inline Iterator GetIterator() const { return Iterator(this); } 164 165 private: 166 Element *fFirst; 167 168 static GetLink sGetLink; 169 }; 170 171 172 // inline methods 173 174 // Add 175 SINGLY_LINKED_LIST_TEMPLATE_LIST 176 void 177 SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element) 178 { 179 if (element != NULL) { 180 sGetLink(element)->next = fFirst; 181 fFirst = element; 182 } 183 } 184 185 // Remove 186 SINGLY_LINKED_LIST_TEMPLATE_LIST 187 void 188 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element) 189 { 190 if (element == NULL) 191 return; 192 193 Element* next = fFirst; 194 Element* last = NULL; 195 while (next != NULL && element != next) { 196 last = next; 197 next = sGetLink(next)->next; 198 } 199 200 Link* elementLink = sGetLink(element); 201 if (last == NULL) 202 fFirst = elementLink->next; 203 else 204 sGetLink(last)->next = elementLink->next; 205 206 elementLink->next = NULL; 207 } 208 209 210 SINGLY_LINKED_LIST_TEMPLATE_LIST 211 void 212 SINGLY_LINKED_LIST_CLASS_NAME::MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList) 213 { 214 if (fromList->fFirst == NULL) 215 return; 216 217 if (fFirst == NULL) { 218 // This list is empty -- just transfer the head. 219 fFirst = fromList->fFirst; 220 fromList->fFirst = NULL; 221 return; 222 } 223 224 // Neither list is empty -- find the tail of this list. 225 Element* tail = fFirst; 226 while (Element* next = sGetLink(tail)->next) 227 tail = next; 228 229 sGetLink(tail)->next = fromList->fFirst; 230 fromList->fFirst = NULL; 231 } 232 233 234 // RemoveAll 235 SINGLY_LINKED_LIST_TEMPLATE_LIST 236 void 237 SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll() 238 { 239 Element* element = fFirst; 240 while (element) { 241 Link* elLink = sGetLink(element); 242 element = elLink->next; 243 elLink->next = NULL; 244 } 245 fFirst = NULL; 246 } 247 248 // RemoveHead 249 SINGLY_LINKED_LIST_TEMPLATE_LIST 250 Element* 251 SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead() 252 { 253 Element* element = Head(); 254 Remove(element); 255 return element; 256 } 257 258 // GetNext 259 SINGLY_LINKED_LIST_TEMPLATE_LIST 260 Element* 261 SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const 262 { 263 Element* result = NULL; 264 if (element) 265 result = sGetLink(element)->next; 266 return result; 267 } 268 269 // Size 270 SINGLY_LINKED_LIST_TEMPLATE_LIST 271 int32 272 SINGLY_LINKED_LIST_CLASS_NAME::Size() const 273 { 274 int32 count = 0; 275 for (Element* element = First(); element; element = GetNext(element)) 276 count++; 277 return count; 278 } 279 280 // sGetLink 281 SINGLY_LINKED_LIST_TEMPLATE_LIST 282 GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink; 283 284 #endif /* __cplusplus */ 285 286 #endif // _KERNEL_UTIL_SINGLY_LINKED_LIST_H 287