headers/private/kernel/util/SinglyLinkedList.h

   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 #include <SupportDefs.h>
  12
  13
  14 #ifdef __cplusplus
  15
  16 // SinglyLinkedListLink
  17 template<typename Element>
  18 class SinglyLinkedListLink {
  19 public:
  20         SinglyLinkedListLink() : next(NULL) {}
  21         ~SinglyLinkedListLink() {}
  22
  23         Element* next;
  24 };
  25
  26 // SinglyLinkedListLinkImpl
  27 template<typename Element>
  28 class SinglyLinkedListLinkImpl {
  29 private:
  30         typedef SinglyLinkedListLink<Element> SLL_Link;
  31
  32 public:
  33         SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {}
  34         ~SinglyLinkedListLinkImpl() {}
  35
  36         SLL_Link* GetSinglyLinkedListLink()
  37                 { return &fSinglyLinkedListLink; }
  38         const SLL_Link* GetSinglyLinkedListLink() const
  39                 { return &fSinglyLinkedListLink; }
  40
  41 private:
  42         SLL_Link        fSinglyLinkedListLink;
  43 };
  44
  45 // SinglyLinkedListStandardGetLink
  46 template<typename Element>
  47 class SinglyLinkedListStandardGetLink {
  48 private:
  49         typedef SinglyLinkedListLink<Element> Link;
  50
  51 public:
  52         inline Link* operator()(Element* element) const
  53         {
  54                 return element->GetSinglyLinkedListLink();
  55         }
  56
  57         inline const Link* operator()(const Element* element) const
  58         {
  59                 return element->GetSinglyLinkedListLink();
  60         }
  61 };
  62
  63 // SinglyLinkedListMemberGetLink
  64 template<typename Element,
  65         SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
  66 class SinglyLinkedListMemberGetLink {
  67 private:
  68         typedef SinglyLinkedListLink<Element> Link;
  69
  70 public:
  71         inline Link* operator()(Element* element) const
  72         {
  73                 return &(element->*LinkMember);
  74         }
  75
  76         inline const Link* operator()(const Element* element) const
  77         {
  78                 return &(element->*LinkMember);
  79         }
  80 };
  81
  82
  83 // for convenience
  84 #define SINGLY_LINKED_LIST_TEMPLATE_LIST \
  85         template<typename Element, typename GetLink>
  86 #define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink>
  87
  88
  89 template<typename Element,
  90         typename GetLink = SinglyLinkedListStandardGetLink<Element> >
  91 class SinglyLinkedList {
  92         private:
  93                 typedef SinglyLinkedList<Element, GetLink> List;
  94                 typedef SinglyLinkedListLink<Element> Link;
  95
  96         public:
  97                 class Iterator {
  98                         public:
  99                                 Iterator(const List* list)
 100                                         :
 101                                         fList(list)
 102                                 {
 103                                         Rewind();
 104                                 }
 105
 106                                 Iterator(const Iterator& other)
 107                                 {
 108                                         *this = other;
 109                                 }
 110
 111                                 bool HasNext() const
 112                                 {
 113                                         return fNext;
 114                                 }
 115
 116                                 Element* Next()
 117                                 {
 118                                         Element* element = fNext;
 119                                         if (fNext)
 120                                                 fNext = fList->GetNext(fNext);
 121                                         return element;
 122                                 }
 123
 124                                 Iterator& operator=(const Iterator& other)
 125                                 {
 126                                         fList = other.fList;
 127                                         fNext = other.fNext;
 128                                         return* this;
 129                                 }
 130
 131                                 void Rewind()
 132                                 {
 133                                         fNext = fList->First();
 134                                 }
 135
 136                         private:
 137                                 const List*     fList;
 138                                 Element*        fNext;
 139                 };
 140
 141         public:
 142                 SinglyLinkedList() : fFirst(NULL) {}
 143                 ~SinglyLinkedList() {}
 144
 145                 inline bool IsEmpty() const             { return (fFirst == NULL); }
 146
 147                 inline void Add(Element* element);
 148                 inline bool Remove(Element* element);
 149                 inline void Remove(Element* previous, Element* element);
 150
 151                 inline void MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList);
 152                         // O(1) if either list is empty, otherwise O(n).
 153
 154                 inline void RemoveAll();
 155                 inline void MakeEmpty()                 { RemoveAll(); }
 156
 157                 inline Element* First() const { return fFirst; }
 158                 inline Element* Head() const { return fFirst; }
 159
 160                 inline Element* RemoveHead();
 161
 162                 inline Element* GetNext(Element* element) const;
 163
 164                 inline int32 Size() const;
 165                         // O(n)!
 166
 167                 inline Iterator GetIterator() const     { return Iterator(this); }
 168
 169         private:
 170                 Element *fFirst;
 171
 172                 static GetLink  sGetLink;
 173 };
 174
 175
 176 // inline methods
 177
 178 // Add
 179 SINGLY_LINKED_LIST_TEMPLATE_LIST
 180 void
 181 SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element)
 182 {
 183         if (element != NULL) {
 184                 sGetLink(element)->next = fFirst;
 185                 fFirst = element;
 186         }
 187 }
 188
 189
 190 /*!     Removes \a element from the list.
 191         It is safe to call the list with a \c NULL element or an element that isn't
 192         in the list.
 193         \param element The element to be removed.
 194         \return \c true, if the element was in the list and has been removed,
 195                 \c false otherwise.
 196 */
 197 SINGLY_LINKED_LIST_TEMPLATE_LIST
 198 bool
 199 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
 200 {
 201         if (element == NULL)
 202                 return false;
 203
 204         Element* next = fFirst;
 205         Element* last = NULL;
 206         while (element != next) {
 207                 if (next == NULL)
 208                         return false;
 209                 last = next;
 210                 next = sGetLink(next)->next;
 211         }
 212
 213         Link* elementLink = sGetLink(element);
 214         if (last == NULL)
 215                 fFirst = elementLink->next;
 216         else
 217                 sGetLink(last)->next = elementLink->next;
 218
 219         elementLink->next = NULL;
 220         return true;
 221 }
 222
 223
 224 SINGLY_LINKED_LIST_TEMPLATE_LIST
 225 void
 226 SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* previous, Element* element)
 227 {
 228 //      ASSERT(previous == NULL
 229 //              ? fFirst == element : sGetLink(previous)->next == element);
 230
 231         Link* elementLink = sGetLink(element);
 232         if (previous == NULL)
 233                 fFirst = elementLink->next;
 234         else
 235                 sGetLink(previous)->next = elementLink->next;
 236
 237         elementLink->next = NULL;
 238 }
 239
 240
 241 SINGLY_LINKED_LIST_TEMPLATE_LIST
 242 void
 243 SINGLY_LINKED_LIST_CLASS_NAME::MoveFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList)
 244 {
 245         if (fromList->fFirst == NULL)
 246                 return;
 247
 248         if (fFirst == NULL) {
 249                 // This list is empty -- just transfer the head.
 250                 fFirst = fromList->fFirst;
 251                 fromList->fFirst = NULL;
 252                 return;
 253         }
 254
 255         // Neither list is empty -- find the tail of this list.
 256         Element* tail = fFirst;
 257         while (Element* next = sGetLink(tail)->next)
 258                 tail = next;
 259
 260         sGetLink(tail)->next = fromList->fFirst;
 261         fromList->fFirst = NULL;
 262 }
 263
 264
 265 // RemoveAll
 266 SINGLY_LINKED_LIST_TEMPLATE_LIST
 267 void
 268 SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll()
 269 {
 270         Element* element = fFirst;
 271         while (element) {
 272                 Link* elLink = sGetLink(element);
 273                 element = elLink->next;
 274                 elLink->next = NULL;
 275         }
 276         fFirst = NULL;
 277 }
 278
 279 // RemoveHead
 280 SINGLY_LINKED_LIST_TEMPLATE_LIST
 281 Element*
 282 SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead()
 283 {
 284         Element* element = Head();
 285         Remove(element);
 286         return element;
 287 }
 288
 289 // GetNext
 290 SINGLY_LINKED_LIST_TEMPLATE_LIST
 291 Element*
 292 SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
 293 {
 294         Element* result = NULL;
 295         if (element)
 296                 result = sGetLink(element)->next;
 297         return result;
 298 }
 299
 300 // Size
 301 SINGLY_LINKED_LIST_TEMPLATE_LIST
 302 int32
 303 SINGLY_LINKED_LIST_CLASS_NAME::Size() const
 304 {
 305         int32 count = 0;
 306         for (Element* element = First(); element; element = GetNext(element))
 307                 count++;
 308         return count;
 309 }
 310
 311 // sGetLink
 312 SINGLY_LINKED_LIST_TEMPLATE_LIST
 313 GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink;
 314
 315 #endif  /* __cplusplus */
 316
 317 #endif  // _KERNEL_UTIL_SINGLY_LINKED_LIST_H