include/am-linkedlist.h
author David Anderson <danderson@mozilla.com>
Tue Aug 27 00:55:44 2013 -0700 (2013-08-27)
changeset 13 ef6b69693bab
parent 11 cfe800908837
permissions -rw-r--r--
Added missing hashmap tests.
     1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
     2 //
     3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
     4 // All rights reserved.
     5 // 
     6 // Redistribution and use in source and binary forms, with or without
     7 // modification, are permitted provided that the following conditions are met:
     8 // 
     9 //  * Redistributions of source code must retain the above copyright notice, this
    10 //    list of conditions and the following disclaimer.
    11 //  * Redistributions in binary form must reproduce the above copyright notice,
    12 //    this list of conditions and the following disclaimer in the documentation
    13 //    and/or other materials provided with the distribution.
    14 //  * Neither the name of AlliedModders LLC nor the names of its contributors
    15 //    may be used to endorse or promote products derived from this software
    16 //    without specific prior written permission.
    17 //
    18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    28 // POSSIBILITY OF SUCH DAMAGE.
    29 
    30 #ifndef _include_amtl_linkedlist_h_
    31 #define _include_amtl_linkedlist_h_
    32 
    33 #include <new>
    34 #include <stdlib.h>
    35 #include <am-allocator-policies.h>
    36 #include <am-utility.h>
    37 #include <am-moveable.h>
    38 
    39 namespace ke {
    40 
    41 // LinkedList, analagous to std::list or SourceHook::List. Since it performs a
    42 // malloc() and free() on every contained node, it should be avoided unless
    43 // absolutely necessary, or for when allocation performance is not a factor. It
    44 // is provided here to safely port old AlliedModders code to AMTL.
    45 //
    46 // In order to use a circular chain, LinkedList's allocation size includes
    47 // exactly one T. If T is very large, LinkedList should be allocated on the
    48 // heap, to avoid using the stack.
    49 template <class T, class AllocPolicy = SystemAllocatorPolicy>
    50 class LinkedList : public AllocPolicy
    51 {
    52  public:
    53   friend class iterator;
    54 
    55   class Node
    56   {
    57    public:
    58     Node(const T &o)
    59      : obj(o)
    60     {
    61     }
    62     Node(Moveable<T> o)
    63      : obj(o)
    64     {
    65     }
    66 
    67     T obj;
    68     Node *next;
    69     Node *prev;
    70   };
    71 
    72 public:
    73   LinkedList(AllocPolicy = AllocPolicy())
    74    : length_(0)
    75   {
    76     head()->prev = head();
    77     head()->next = head();
    78   }
    79   ~LinkedList() {
    80     clear();
    81   }
    82 
    83   bool append(const T &obj) {
    84     return insertBefore(end(), obj) != end();
    85   }
    86   bool append(Moveable<T> obj) {
    87     return insertBefore(end(), obj) != end();
    88   }
    89 
    90   bool prepend(const T &obj) {
    91     return insertBefore(begin(), obj) != begin();
    92   }
    93   bool prepend(Moveable<T> obj) {
    94     return insertBefore(begin(), obj) != begin();
    95   }
    96 
    97   size_t length() const {
    98     return length_;
    99   }
   100 
   101   void clear() {
   102     Node *node = head()->next;
   103     Node *temp;
   104     head()->next = head();
   105     head()->prev = head();
   106 
   107     // Iterate through the nodes until we find the sentinel again.
   108     while (node != head()) {
   109       temp = node->next;
   110       freeNode(node);
   111       node = temp;
   112     }
   113     length_ = 0;
   114   }
   115 
   116   bool empty() const {
   117     return (length_ == 0);
   118   }
   119 
   120   T &front() {
   121     assert(!empty());
   122     return head()->next->obj;
   123   }
   124   T &back() {
   125     assert(!empty());
   126     return head()->prev->obj;
   127   }
   128 
   129  private:
   130   const Node *head() const {
   131     return sentinel_.address();
   132   }
   133   Node *head() {
   134     return sentinel_.address();
   135   }
   136 
   137   Node *allocNode(const T &obj) {
   138     Node *node = (Node *)this->malloc(sizeof(Node));
   139     if (!node)
   140       return NULL;
   141     new (node) Node(obj);
   142     return node;
   143   }
   144   Node *allocNode(Moveable<T> obj) {
   145     Node *node = (Node *)this->malloc(sizeof(Node));
   146     if (!node)
   147       return NULL;
   148     new (node) Node(obj);
   149     return node;
   150   }
   151 
   152   void freeNode(Node *node) {
   153     node->obj.~T();
   154     this->free(node);
   155   }
   156 
   157  private:
   158   StorageBuffer<Node> sentinel_;
   159   size_t length_;
   160 
   161  public:
   162   class iterator
   163   {
   164     friend class LinkedList;
   165 
   166    public:
   167     iterator()
   168      : this_(NULL)
   169     {
   170     }
   171     iterator(const LinkedList &src)
   172      : this_(src.head())
   173     {
   174     }
   175     iterator(Node *n)
   176      : this_(n)
   177     {
   178     }
   179     iterator(const iterator &where)
   180      : this_(where.this_)
   181     {
   182     }
   183 
   184     iterator &operator --() {
   185       if (this_)
   186         this_ = this_->prev;
   187       return *this;
   188     }
   189     iterator operator --(int) {
   190       iterator old(*this);
   191       if (this_)
   192         this_ = this_->prev;
   193       return old;
   194     }  
   195     iterator &operator ++() {
   196       if (this_)
   197         this_ = this_->next;
   198       return *this;
   199     }
   200     iterator operator ++(int) {
   201       iterator old(*this);
   202       if (this_)
   203         this_ = this_->next;
   204       return old;
   205     }
   206     
   207     const T &operator * () const {
   208       return this_->obj;
   209     }
   210     T &operator * () {
   211       return this_->obj;
   212     }
   213     T *operator ->() {
   214       return &this_->obj;
   215     }
   216     const T *operator ->() const {
   217       return &(this_->obj);
   218     }
   219     
   220     bool operator !=(const iterator &where) const {
   221       return (this_ != where.this_);
   222     }
   223     bool operator ==(const iterator &where) const {
   224       return (this_ == where.this_);
   225     }
   226 
   227     operator bool() {
   228       return !!this_;
   229     }
   230 
   231    private:
   232     Node *this_;
   233   };
   234 
   235  private:
   236   // Insert obj right before where.
   237   iterator insert(iterator where, Node *node) {
   238     if (!node)
   239       return where;
   240 
   241     Node *pWhereNode = where.this_;
   242     
   243     pWhereNode->prev->next = node;
   244     node->prev = pWhereNode->prev;
   245     pWhereNode->prev = node;
   246     node->next = pWhereNode;
   247 
   248     length_++;
   249     return iterator(node);
   250   }
   251 
   252  public:
   253   iterator begin() {
   254     return iterator(head()->next);
   255   }
   256   iterator end() {
   257     return iterator(head());
   258   }
   259   iterator erase(iterator where) {
   260     Node *pNode = where.this_;
   261     iterator iter(where);
   262     iter++;
   263 
   264     pNode->prev->next = pNode->next;
   265     pNode->next->prev = pNode->prev;
   266 
   267     freeNode(pNode);
   268     length_--;
   269 
   270     return iter;
   271   }
   272   iterator insertBefore(iterator where, const T &obj) {
   273     return insert(where, allocNode(obj));
   274   }
   275   iterator insertBefore(iterator where, Moveable<T> obj) {
   276     return insert(where, allocNode(obj));
   277   }
   278 
   279  public:
   280   // Removes one instance of |obj| from the list, if found.
   281   void remove(const T &obj) {
   282     for (iterator b = begin(); b != end(); b++) {
   283       if (*b == obj) {
   284         erase(b);
   285         break;
   286       }
   287     }
   288   }
   289 
   290   template <typename U>
   291   iterator find(const U &equ) {
   292     for (iterator iter = begin(); iter != end(); iter++) {
   293       if (*iter == equ)
   294         return iter;
   295     }
   296     return end();
   297   }
   298 
   299 
   300  private:
   301   // These are disallowed because they basically violate the failure handling
   302   // model for AllocPolicies and are also likely to have abysmal performance.
   303   LinkedList &operator =(const LinkedList<T> &other) KE_DELETE;
   304   LinkedList(const LinkedList<T> &other) KE_DELETE;
   305 };
   306 
   307 } // namespace ke
   308 
   309 #endif //_INCLUDE_CSDM_LIST_H