src/add-ons/kernel/file_systems/ramfs/SLList.h

   1 // SLList.h
   2 //
   3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining a
   6 // copy of this software and associated documentation files (the "Software"),
   7 // to deal in the Software without restriction, including without limitation
   8 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9 // and/or sell copies of the Software, and to permit persons to whom the
  10 // Software is furnished to do so, subject to the following conditions:
  11 //
  12 // The above copyright notice and this permission notice shall be included in
  13 // all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21 // DEALINGS IN THE SOFTWARE.
  22 //
  23 // Except as contained in this notice, the name of a copyright holder shall
  24 // not be used in advertising or otherwise to promote the sale, use or other
  25 // dealings in this Software without prior written authorization of the
  26 // copyright holder.
  27
  28 #ifndef SL_LIST_H
  29 #define SL_LIST_H
  30
  31 #include <new>
  32
  33 // SLListStandardNode
  34 template<typename Value>
  35 struct SLListStandardNode {
  36         SLListStandardNode(const Value &a)
  37                 : value(a),
  38                   next(NULL)
  39         {
  40         }
  41
  42         Value                                           value;
  43         SLListStandardNode<Value>       *next;
  44 };
  45
  46 // SLListStandardNodeAllocator
  47 template<typename Value, typename Node>
  48 class SLListStandardNodeAllocator
  49 {
  50 public:
  51         inline Node *Allocate(const Value &a) const
  52         {
  53                 return new(nothrow) SLListStandardNode<Value>(a);
  54         }
  55
  56         inline void Free(Node *node) const
  57         {
  58                 delete node;
  59         }
  60 };
  61
  62 // SLListValueNodeAllocator
  63 template<typename Value, typename Node>
  64 class SLListValueNodeAllocator
  65 {
  66 public:
  67         inline Node *Allocate(const Value &a) const
  68         {
  69                 return a;
  70         }
  71
  72         inline void Free(Node *node) const
  73         {
  74         }
  75 };
  76
  77 // SLListStandardGetValue
  78 template<typename Value, typename Node>
  79 class SLListStandardGetValue
  80 {
  81 public:
  82         inline Value &operator()(Node *node) const
  83         {
  84                 return node->value;
  85         }
  86 };
  87
  88 // SLListValueNodeGetValue
  89 template<typename Value, typename Node>
  90 class SLListValueNodeGetValue
  91 {
  92 public:
  93         inline Value &operator()(Node *node) const
  94         {
  95                 return *node;
  96         }
  97 };
  98
  99 // for convenience
 100 #define SL_LIST_TEMPLATE_LIST template<typename Value, typename Node, \
 101         typename NodeAllocator, typename GetValue>
 102 #define SL_LIST_CLASS_NAME SLList<Value, Node, NodeAllocator, GetValue>
 103
 104 // SLList
 105 template<typename Value, typename Node = SLListStandardNode<Value>,
 106                  typename NodeAllocator = SLListStandardNodeAllocator<Value, Node>,
 107                  typename GetValue = SLListStandardGetValue<Value, Node> >
 108 class SLList {
 109 public:
 110         class Iterator;
 111
 112 public:
 113         SLList();
 114         SLList(const NodeAllocator &nodeAllocator, const GetValue &getValue);
 115         ~SLList();
 116
 117         bool Insert(const Value &value, Iterator *iterator = NULL);
 118         bool Remove(const Value &value);
 119         void Remove(Iterator &iterator);
 120         void RemoveAll();
 121
 122         bool Find(const Value &value, Iterator *iterator = NULL) const;
 123         void GetIterator(Iterator *iterator) const;
 124
 125 private:
 126         friend class Iterator;
 127
 128         Node                    *fHead;
 129         NodeAllocator   fNodeAllocator;
 130         GetValue                fGetValue;
 131 };
 132
 133 // Iterator
 134 SL_LIST_TEMPLATE_LIST
 135 class SL_LIST_CLASS_NAME::Iterator {
 136 public:
 137         Iterator() : fList(NULL), fCurrent(NULL)        {}
 138         ~Iterator()     {}
 139
 140         inline Value *GetCurrent()
 141         {
 142                 return (fList && fCurrent ? &fList->fGetValue(fCurrent) : NULL);
 143         }
 144
 145         inline Value *GetNext()
 146         {
 147                 if (fCurrent)
 148                         fCurrent = fCurrent->next;
 149                 return GetCurrent();
 150         }
 151
 152         inline void Remove()
 153         {
 154                 if (fList)
 155                         fList->Remove(*this);
 156         }
 157
 158 private:
 159         friend class SL_LIST_CLASS_NAME;
 160
 161         inline void _SetTo(SL_LIST_CLASS_NAME *list, Node *previous, Node *node)
 162         {
 163                 fList = list;
 164                 fPrevious = previous;
 165                 fCurrent = node;
 166         }
 167
 168         inline SL_LIST_CLASS_NAME *_GetList() const     { return fList; }
 169         inline Node *_GetPreviousNode() const           { return fPrevious; }
 170         inline Node *_GetCurrentNode() const            { return fCurrent; }
 171
 172 private:
 173         SL_LIST_CLASS_NAME      *fList;
 174         Node                            *fPrevious;
 175         Node                            *fCurrent;
 176 };
 177
 178 // constructor
 179 SL_LIST_TEMPLATE_LIST
 180 SL_LIST_CLASS_NAME::SLList()
 181         : fHead(NULL)/*,
 182           fNodeAllocator(),
 183           fGetValue()*/
 184 {
 185 }
 186
 187 // constructor
 188 SL_LIST_TEMPLATE_LIST
 189 SL_LIST_CLASS_NAME::SLList(const NodeAllocator &nodeAllocator,
 190                                                    const GetValue &getValue)
 191         : fHead(NULL),
 192           fNodeAllocator(nodeAllocator),
 193           fGetValue(getValue)
 194 {
 195 }
 196
 197 // destructor
 198 SL_LIST_TEMPLATE_LIST
 199 SL_LIST_CLASS_NAME::~SLList()
 200 {
 201         RemoveAll();
 202 }
 203
 204 // Insert
 205 SL_LIST_TEMPLATE_LIST
 206 bool
 207 SL_LIST_CLASS_NAME::Insert(const Value &value, Iterator *iterator)
 208 {
 209         Node *node = fNodeAllocator.Allocate(value);
 210         if (node) {
 211                 node->next = fHead;
 212                 fHead = node;
 213                 if (iterator)
 214                         iterator->_SetTo(this, NULL, node);
 215         }
 216         return node;
 217 }
 218
 219 // Remove
 220 SL_LIST_TEMPLATE_LIST
 221 bool
 222 SL_LIST_CLASS_NAME::Remove(const Value &value)
 223 {
 224         Iterator iterator;
 225         bool result = Find(value, &iterator);
 226         if (result)
 227                 iterator.Remove();
 228         return result;
 229 }
 230
 231 // Remove
 232 SL_LIST_TEMPLATE_LIST
 233 void
 234 SL_LIST_CLASS_NAME::Remove(Iterator &iterator)
 235 {
 236         Node *node = iterator._GetCurrentNode();
 237         if (iterator._GetList() == this && node) {
 238                 Node *previous = iterator._GetPreviousNode();
 239                 iterator._SetTo(this, previous, node->next);
 240                 if (previous)
 241                         previous->next = node->next;
 242                 else
 243                         fHead = node->next;
 244                 fNodeAllocator.Free(node);
 245         }
 246 }
 247
 248 // RemoveAll
 249 SL_LIST_TEMPLATE_LIST
 250 void
 251 SL_LIST_CLASS_NAME::RemoveAll()
 252 {
 253         for (Node *node = fHead; node; ) {
 254                 Node *next = node->next;
 255                 fNodeAllocator.Free(node);
 256                 node = next;
 257         }
 258         fHead = NULL;
 259 }
 260
 261 // Find
 262 SL_LIST_TEMPLATE_LIST
 263 bool
 264 SL_LIST_CLASS_NAME::Find(const Value &value, Iterator *iterator) const
 265 {
 266         Node *node = fHead;
 267         Node *previous = NULL;
 268         while (node && fGetValue(node) != value) {
 269                 previous = node;
 270                 node = node->next;
 271         }
 272         if (node && iterator) {
 273                 iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), previous,
 274                                                  node);
 275         }
 276         return node;
 277 }
 278
 279 // GetIterator
 280 SL_LIST_TEMPLATE_LIST
 281 void
 282 SL_LIST_CLASS_NAME::GetIterator(Iterator *iterator) const
 283 {
 284         if (iterator)
 285                 iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), NULL, fHead);
 286 }
 287
 288 #endif  // SL_LIST_H