include/am-inlinelist.h
author David Anderson <dvander@alliedmods.net>
Fri Sep 06 13:54:31 2013 -0700 (2013-09-06)
changeset 18 9b30f80f6e49
parent 17 563aea5eba06
permissions -rw-r--r--
Eliminate Newborn/NoAddRef (bug 5907, r=ds).
     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_inline_list_h_
    31 #define _include_amtl_inline_list_h_
    32 
    33 #include <stddef.h>
    34 #include <assert.h>
    35 
    36 namespace ke {
    37 
    38 template <typename T> class InlineList;
    39 
    40 // Objects can recursively inherit from InlineListNode in order to have
    41 // membership in an InlineList<T>.
    42 template <typename T>
    43 class InlineListNode
    44 {
    45   friend class InlineList<T>;
    46 
    47   public:
    48   InlineListNode()
    49    : next_(NULL),
    50      prev_(NULL)
    51   {
    52   }
    53 
    54   InlineListNode(InlineListNode *next, InlineListNode *prev)
    55    : next_(next),
    56      prev_(prev)
    57   {
    58   }
    59 
    60   protected:
    61   InlineListNode *next_;
    62   InlineListNode *prev_;
    63 };
    64 
    65 // An InlineList is a linked list that threads link pointers through objects,
    66 // rather than allocating node memory. A node can be in at most one list at
    67 // any time.
    68 //
    69 // Since InlineLists are designed to be very cheap, there is no requirement
    70 // that elements be removed from a list once the list is destructed. However,
    71 // for as long as the list is alive, all of its contained nodes must also
    72 // be alive.
    73 template <typename T>
    74 class InlineList
    75 {
    76   typedef InlineListNode<T> Node;
    77 
    78   Node head_;
    79 
    80   // Work around a clang bug where we can't initialize with &head_ in the ctor.
    81   inline Node *head() {
    82     return &head_;
    83   }
    84 
    85  public:
    86   InlineList()
    87     : head_(head(), head())
    88   {
    89   }
    90 
    91   ~InlineList()
    92   {
    93 #if !defined(NDEBUG)
    94     // Remove all items to clear their next/prev fields.
    95     while (begin() != end())
    96       remove(*begin());
    97 #endif
    98   }
    99 
   100  public:
   101   class iterator
   102   {
   103     friend class InlineList;
   104     Node *iter_;
   105 
   106    public:
   107     iterator(Node *iter)
   108       : iter_(iter)
   109     {
   110     }
   111 
   112     iterator & operator ++() {
   113       iter_ = iter_->next;
   114       return *this;
   115     }
   116     iterator operator ++(int) {
   117       iterator old(*this);
   118       iter_ = iter_->next_;
   119       return old;
   120     }
   121     T * operator *() {
   122       return static_cast<T *>(iter_);
   123     }
   124     T * operator ->() {
   125       return static_cast<T *>(iter_);
   126     }
   127     bool operator !=(const iterator &where) const {
   128       return iter_ != where.iter_;
   129     }
   130     bool operator ==(const iterator &where) const {
   131       return iter_ == where.iter_;
   132     }
   133   };
   134 
   135   iterator begin() {
   136     return iterator(head_.next_);
   137   }
   138 
   139   iterator end() {
   140     return iterator(&head_);
   141   }
   142 
   143   iterator erase(iterator &at) {
   144     iterator next = at;
   145     next++;
   146 
   147     remove(at.iter_);
   148 
   149     // Iterator is no longer valid.
   150     at.iter_ = NULL;
   151 
   152     return next;
   153   }
   154 
   155   bool empty() const {
   156     return head_.next_ == &head_;
   157   }
   158 
   159   void remove(Node *t) {
   160     t->prev_->next_ = t->next_;
   161     t->next_->prev_ = t->prev_;
   162 
   163 #if !defined(NDEBUG)
   164     t->next_ = NULL;
   165     t->prev_ = NULL;
   166 #endif
   167   }
   168 
   169   void append(Node *t) {
   170     assert(!t->next_);
   171     assert(!t->prev_);
   172 
   173     t->prev_ = head_.prev_;
   174     t->next_ = &head_;
   175     head_.prev_->next_ = t;
   176     head_.prev_ = t;
   177   }
   178 };
   179 
   180 }
   181 
   182 #endif // _include_amtl_inline_list_h_
   183