headers/private/fs_shell/SinglyLinkedList.h

   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 Iterator {
 101                         public:
 102                                 Iterator(const List* list)
 103                                         :
 104                                         fList(list)
 105                                 {
 106                                         Rewind();
 107                                 }
 108
 109                                 Iterator(const Iterator& 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                                 Iterator& operator=(const Iterator& 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 Size() const;
 164                         // O(n)!
 165
 166                 inline Iterator GetIterator() const     { return Iterator(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::Size() 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