1// SLList.h 2 3#ifndef SL_LIST_H 4#define SL_LIST_H 5 6#include <SupportDefs.h> 7 8namespace UserlandFSUtil { 9 10// SLListLink 11template<typename Element> 12class SLListLink { 13public: 14 SLListLink() : next(NULL) {} 15 ~SLListLink() {} 16 17 Element *next; 18}; 19 20// SLListLinkImpl 21template<typename Element> 22class SLListLinkImpl { 23private: 24 typedef SLListLink<Element> Link; 25 26public: 27 SLListLinkImpl() : fSLListLink() {} 28 ~SLListLinkImpl() {} 29 30 Link *GetSLListLink() { return &fSLListLink; } 31 const Link *GetSLListLink() const { return &fSLListLink; } 32 33private: 34 Link fSLListLink; 35}; 36 37// SLListStandardGetLink 38template<typename Element> 39class SLListStandardGetLink { 40private: 41 typedef SLListLink<Element> Link; 42 43public: 44 inline Link *operator()(Element *element) const 45 { 46 return element->GetSLListLink(); 47 } 48 49 inline const Link *operator()(const Element *element) const 50 { 51 return element->GetSLListLink(); 52 } 53}; 54 55// for convenience 56#define SL_LIST_TEMPLATE_LIST template<typename Element, typename GetLink> 57#define SL_LIST_CLASS_NAME SLList<Element, GetLink> 58 59// SLList 60template<typename Element, typename GetLink = SLListStandardGetLink<Element> > 61class SLList { 62private: 63 typedef SLList<Element, GetLink> List; 64 typedef SLListLink<Element> Link; 65 66public: 67 class Iterator { 68 public: 69 Iterator(List *list) 70 : fList(list), 71 fPrevious(NULL), 72 fCurrent(NULL), 73 fNext(fList->GetFirst()) 74 { 75 } 76 77 Iterator(const Iterator &other) 78 { 79 *this = other; 80 } 81 82 bool HasNext() const 83 { 84 return fNext; 85 } 86 87 Element *Next() 88 { 89 if (fCurrent) 90 fPrevious = fCurrent; 91 92 fCurrent = fNext; 93 94 if (fNext) 95 fNext = fList->GetNext(fNext); 96 97 return fCurrent; 98 } 99 100 Element *Remove() 101 { 102 Element *element = fCurrent; 103 if (fCurrent) { 104 fList->_Remove(fPrevious, fCurrent); 105 fCurrent = NULL; 106 } 107 return element; 108 } 109 110 Iterator &operator=(const Iterator &other) 111 { 112 fList = other.fList; 113 fPrevious = other.fPrevious; 114 fCurrent = other.fCurrent; 115 fNext = other.fNext; 116 return *this; 117 } 118 119 private: 120 List *fList; 121 Element *fPrevious; 122 Element *fCurrent; 123 Element *fNext; 124 }; 125 126 class ConstIterator { 127 public: 128 ConstIterator(const List *list) 129 : fList(list), 130 fNext(list->GetFirst()) 131 { 132 } 133 134 ConstIterator(const ConstIterator &other) 135 { 136 *this = other; 137 } 138 139 bool HasNext() const 140 { 141 return fNext; 142 } 143 144 Element *Next() 145 { 146 Element *element = fNext; 147 if (fNext) 148 fNext = fList->GetNext(fNext); 149 return element; 150 } 151 152 ConstIterator &operator=(const ConstIterator &other) 153 { 154 fList = other.fList; 155 fNext = other.fNext; 156 return *this; 157 } 158 159 private: 160 const List *fList; 161 Element *fNext; 162 }; 163 164public: 165 SLList() : fFirst(NULL), fLast(NULL) {} 166 SLList(const GetLink &getLink) 167 : fFirst(NULL), fLast(NULL), fGetLink(getLink) {} 168 ~SLList() {} 169 170 inline bool IsEmpty() const { return (fFirst == NULL); } 171 172 inline void Insert(Element *element, bool back = true); 173 inline void InsertAfter(Element *previous, Element *element); 174 inline void Remove(Element *element); 175 // O(n)! 176 177 inline void MoveFrom(SL_LIST_CLASS_NAME *fromList); 178 179 inline void RemoveAll(); 180 181 inline Element *GetFirst() const { return fFirst; } 182 inline Element *GetLast() const { return fLast; } 183 184 inline Element *GetHead() const { return fFirst; } 185 inline Element *GetTail() const { return fLast; } 186 187 inline Element *GetNext(Element *element) const; 188 189 inline int32 Size() const; 190 // O(n)! 191 192 inline Iterator GetIterator() { return Iterator(this); } 193 inline ConstIterator GetIterator() const { return ConstIterator(this); } 194 195private: 196 friend class Iterator; 197 198 inline void _Remove(Element *previous, Element *element); 199 200private: 201 Element *fFirst; 202 Element *fLast; 203 GetLink fGetLink; 204}; 205 206} // namespace UserlandFSUtil 207 208using UserlandFSUtil::SLList; 209using UserlandFSUtil::SLListLink; 210using UserlandFSUtil::SLListLinkImpl; 211 212 213// inline methods 214 215// Insert 216SL_LIST_TEMPLATE_LIST 217void 218SL_LIST_CLASS_NAME::Insert(Element *element, bool back) 219{ 220 InsertAfter((back ? fLast : NULL), element); 221} 222 223// InsertAfter 224SL_LIST_TEMPLATE_LIST 225void 226SL_LIST_CLASS_NAME::InsertAfter(Element *previous, Element *element) 227{ 228 if (element) { 229 Link *elLink = fGetLink(element); 230 if (previous) { 231 // insert after previous element 232 Link *prevLink = fGetLink(previous); 233 elLink->next = prevLink->next; 234 prevLink->next = element; 235 } else { 236 // no previous element given: prepend 237 elLink->next = fFirst; 238 fFirst = element; 239 } 240 241 // element may be new last element 242 if (fLast == previous) 243 fLast = element; 244 } 245} 246 247// Remove 248SL_LIST_TEMPLATE_LIST 249void 250SL_LIST_CLASS_NAME::Remove(Element *element) 251{ 252 if (!element) 253 return; 254 255 for (Iterator it = GetIterator(); it.HasNext();) { 256 if (element == it.Next()) { 257 it.Remove(); 258 return; 259 } 260 } 261} 262 263// MoveFrom 264SL_LIST_TEMPLATE_LIST 265void 266SL_LIST_CLASS_NAME::MoveFrom(SL_LIST_CLASS_NAME *fromList) 267{ 268 if (fromList && fromList->fFirst) { 269 if (fFirst) { 270 fGetLink(fLast)->next = fromList->fFirst; 271 fLast = fromList->fLast; 272 } else { 273 fFirst = fromList->fFirst; 274 fLast = fromList->fLast; 275 } 276 fromList->fFirst = NULL; 277 fromList->fLast = NULL; 278 } 279} 280 281// RemoveAll 282SL_LIST_TEMPLATE_LIST 283void 284SL_LIST_CLASS_NAME::RemoveAll() 285{ 286 Element *element = fFirst; 287 while (element) { 288 Link *elLink = fGetLink(element); 289 element = elLink->next; 290 elLink->next = NULL; 291 } 292 fFirst = NULL; 293 fLast = NULL; 294} 295 296// GetNext 297SL_LIST_TEMPLATE_LIST 298Element * 299SL_LIST_CLASS_NAME::GetNext(Element *element) const 300{ 301 return (element ? fGetLink(element)->next : NULL); 302} 303 304// _Remove 305SL_LIST_TEMPLATE_LIST 306void 307SL_LIST_CLASS_NAME::_Remove(Element *previous, Element *element) 308{ 309 Link *elLink = fGetLink(element); 310 if (previous) 311 fGetLink(previous)->next = elLink->next; 312 else 313 fFirst = elLink->next; 314 315 if (element == fLast) 316 fLast = previous; 317 318 elLink->next = NULL; 319} 320 321// Size 322SL_LIST_TEMPLATE_LIST 323int32 324SL_LIST_CLASS_NAME::Size() const 325{ 326 int32 count = 0; 327 for (Element* element = GetFirst(); element; element = GetNext(element)) 328 count++; 329 return count; 330} 331 332#endif // SL_LIST_H 333