1 /* 2 * Copyright 2008, 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_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 RemoveAll(); 148 inline void MakeEmpty() { RemoveAll(); } 149 150 inline Element* First() const { return fFirst; } 151 inline Element* Head() const { return fFirst; } 152 153 inline Element* RemoveHead(); 154 155 inline Element* GetNext(Element* element) const; 156 157 inline int32 Size() const; 158 // O(n)! 159 160 inline Iterator GetIterator() const { return Iterator(this); } 161 162 private: 163 Element *fFirst; 164 165 static GetLink sGetLink; 166 }; 167 168 169 // inline methods 170 171 // Add 172 SINGLY_LINKED_LIST_TEMPLATE_LIST 173 void 174 SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element) 175 { 176 if (element != NULL) { 177 sGetLink(element)->next = fFirst; 178 fFirst = element; 179 } 180 } 181 182 // Remove 183 SINGLY_LINKED_LIST_TEMPLATE_LIST 184 void 185 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element) 186 { 187 if (element == NULL) 188 return; 189 190 Element* next = fFirst; 191 Element* last = NULL; 192 while (next != NULL && element != next) { 193 last = next; 194 next = sGetLink(next)->next; 195 } 196 197 Link* elementLink = sGetLink(element); 198 if (last == NULL) 199 fFirst = elementLink->next; 200 else 201 sGetLink(last)->next = elementLink->next; 202 203 elementLink->next = NULL; 204 } 205 206 // RemoveAll 207 SINGLY_LINKED_LIST_TEMPLATE_LIST 208 void 209 SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll() 210 { 211 Element* element = fFirst; 212 while (element) { 213 Link* elLink = sGetLink(element); 214 element = elLink->next; 215 elLink->next = NULL; 216 } 217 fFirst = NULL; 218 } 219 220 // RemoveHead 221 SINGLY_LINKED_LIST_TEMPLATE_LIST 222 Element* 223 SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead() 224 { 225 Element* element = Head(); 226 Remove(element); 227 return element; 228 } 229 230 // GetNext 231 SINGLY_LINKED_LIST_TEMPLATE_LIST 232 Element* 233 SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const 234 { 235 Element* result = NULL; 236 if (element) 237 result = sGetLink(element)->next; 238 return result; 239 } 240 241 // Size 242 SINGLY_LINKED_LIST_TEMPLATE_LIST 243 int32 244 SINGLY_LINKED_LIST_CLASS_NAME::Size() const 245 { 246 int32 count = 0; 247 for (Element* element = First(); element; element = GetNext(element)) 248 count++; 249 return count; 250 } 251 252 // sGetLink 253 SINGLY_LINKED_LIST_TEMPLATE_LIST 254 GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink; 255 256 #endif /* __cplusplus */ 257 258 #endif // _KERNEL_UTIL_SINGLY_LINKED_LIST_H 259