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 #include "fssh_types.h" 12 13 14 #ifdef __cplusplus 15 16 17 namespace FSShell { 18 19 // SinglyLinkedListLink 20 template<typename Element> 21 class SinglyLinkedListLink { 22 public: 23 SinglyLinkedListLink() : next(NULL) {} 24 ~SinglyLinkedListLink() {} 25 26 Element* next; 27 }; 28 29 // SinglyLinkedListLinkImpl 30 template<typename Element> 31 class SinglyLinkedListLinkImpl { 32 private: 33 typedef SinglyLinkedListLink<Element> SLL_Link; 34 35 public: 36 SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {} 37 ~SinglyLinkedListLinkImpl() {} 38 39 SLL_Link* GetSinglyLinkedListLink() 40 { return &fSinglyLinkedListLink; } 41 const SLL_Link* GetSinglyLinkedListLink() const 42 { return &fSinglyLinkedListLink; } 43 44 private: 45 SLL_Link fSinglyLinkedListLink; 46 }; 47 48 // SinglyLinkedListStandardGetLink 49 template<typename Element> 50 class SinglyLinkedListStandardGetLink { 51 private: 52 typedef SinglyLinkedListLink<Element> Link; 53 54 public: 55 inline Link* operator()(Element* element) const 56 { 57 return element->GetSinglyLinkedListLink(); 58 } 59 60 inline const Link* operator()(const Element* element) const 61 { 62 return element->GetSinglyLinkedListLink(); 63 } 64 }; 65 66 // SinglyLinkedListMemberGetLink 67 template<typename Element, 68 SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink> 69 class SinglyLinkedListMemberGetLink { 70 private: 71 typedef SinglyLinkedListLink<Element> Link; 72 73 public: 74 inline Link* operator()(Element* element) const 75 { 76 return &(element->*LinkMember); 77 } 78 79 inline const Link* operator()(const Element* element) const 80 { 81 return &(element->*LinkMember); 82 } 83 }; 84 85 86 // for convenience 87 #define SINGLY_LINKED_LIST_TEMPLATE_LIST \ 88 template<typename Element, typename GetLink> 89 #define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink> 90 91 92 template<typename Element, 93 typename GetLink = SinglyLinkedListStandardGetLink<Element> > 94 class SinglyLinkedList { 95 private: 96 typedef SinglyLinkedList<Element, GetLink> List; 97 typedef SinglyLinkedListLink<Element> Link; 98 99 public: 100 class ConstIterator { 101 public: 102 ConstIterator(const List* list) 103 : 104 fList(list) 105 { 106 Rewind(); 107 } 108 109 ConstIterator(const ConstIterator& other) 110 { 111 *this = other; 112 } 113 114 bool HasNext() const 115 { 116 return fNext; 117 } 118 119 Element* Next() 120 { 121 Element* element = fNext; 122 if (fNext) 123 fNext = fList->GetNext(fNext); 124 return element; 125 } 126 127 ConstIterator& operator=(const ConstIterator& other) 128 { 129 fList = other.fList; 130 fNext = other.fNext; 131 return* this; 132 } 133 134 void Rewind() 135 { 136 fNext = fList->First(); 137 } 138 139 private: 140 const List* fList; 141 Element* fNext; 142 }; 143 144 public: 145 SinglyLinkedList() : fFirst(NULL) {} 146 ~SinglyLinkedList() {} 147 148 inline bool IsEmpty() const { return (fFirst == NULL); } 149 150 inline void Add(Element* element); 151 inline void Remove(Element* element); 152 153 inline void RemoveAll(); 154 inline void MakeEmpty() { RemoveAll(); } 155 156 inline Element* First() const { return fFirst; } 157 inline Element* Head() const { return fFirst; } 158 159 inline Element* RemoveHead(); 160 161 inline Element* GetNext(Element* element) const; 162 163 inline int32_t Count() const; 164 // O(n)! 165 166 inline ConstIterator GetIterator() const { return ConstIterator(this); } 167 168 private: 169 Element *fFirst; 170 171 static GetLink sGetLink; 172 }; 173 174 175 // inline methods 176 177 // Add 178 SINGLY_LINKED_LIST_TEMPLATE_LIST 179 void 180 SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element) 181 { 182 if (element != NULL) { 183 sGetLink(element)->next = fFirst; 184 fFirst = element; 185 } 186 } 187 188 // Remove 189 SINGLY_LINKED_LIST_TEMPLATE_LIST 190 void 191 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element) 192 { 193 if (element == NULL) 194 return; 195 196 Element* next = fFirst; 197 Element* last = NULL; 198 while (next != NULL && element != next) { 199 last = next; 200 next = sGetLink(next)->next; 201 } 202 203 Link* elementLink = sGetLink(element); 204 if (last == NULL) 205 fFirst = elementLink->next; 206 else 207 sGetLink(last)->next = elementLink->next; 208 209 elementLink->next = NULL; 210 } 211 212 // RemoveAll 213 SINGLY_LINKED_LIST_TEMPLATE_LIST 214 void 215 SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll() 216 { 217 Element* element = fFirst; 218 while (element) { 219 Link* elLink = sGetLink(element); 220 element = elLink->next; 221 elLink->next = NULL; 222 } 223 fFirst = NULL; 224 } 225 226 // RemoveHead 227 SINGLY_LINKED_LIST_TEMPLATE_LIST 228 Element* 229 SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead() 230 { 231 Element* element = Head(); 232 Remove(element); 233 return element; 234 } 235 236 // GetNext 237 SINGLY_LINKED_LIST_TEMPLATE_LIST 238 Element* 239 SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const 240 { 241 Element* result = NULL; 242 if (element) 243 result = sGetLink(element)->next; 244 return result; 245 } 246 247 // Size 248 SINGLY_LINKED_LIST_TEMPLATE_LIST 249 int32_t 250 SINGLY_LINKED_LIST_CLASS_NAME::Count() const 251 { 252 int32_t count = 0; 253 for (Element* element = First(); element; element = GetNext(element)) 254 count++; 255 return count; 256 } 257 258 // sGetLink 259 SINGLY_LINKED_LIST_TEMPLATE_LIST 260 GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink; 261 262 } // namespace FSShell 263 264 using FSShell::SinglyLinkedListLink; 265 using FSShell::SinglyLinkedListLinkImpl; 266 using FSShell::SinglyLinkedListStandardGetLink; 267 using FSShell::SinglyLinkedListMemberGetLink; 268 using FSShell::SinglyLinkedList; 269 270 #endif // __cplusplus 271 272 #endif // _KERNEL_UTIL_SINGLY_LINKED_LIST_H 273