include/am-linkedlist.h
changeset 0 ba3d4abaf3f1
child 11 cfe800908837
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/include/am-linkedlist.h	Fri Aug 23 20:34:17 2013 -0700
     1.3 @@ -0,0 +1,290 @@
     1.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     1.5 +//
     1.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     1.7 +// All rights reserved.
     1.8 +// 
     1.9 +// Redistribution and use in source and binary forms, with or without
    1.10 +// modification, are permitted provided that the following conditions are met:
    1.11 +// 
    1.12 +//  * Redistributions of source code must retain the above copyright notice, this
    1.13 +//    list of conditions and the following disclaimer.
    1.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    1.15 +//    this list of conditions and the following disclaimer in the documentation
    1.16 +//    and/or other materials provided with the distribution.
    1.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    1.18 +//    may be used to endorse or promote products derived from this software
    1.19 +//    without specific prior written permission.
    1.20 +//
    1.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    1.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    1.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    1.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    1.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    1.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    1.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    1.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    1.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    1.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    1.31 +// POSSIBILITY OF SUCH DAMAGE.
    1.32 +
    1.33 +#ifndef _include_amtl_linkedlist_h_
    1.34 +#define _include_amtl_linkedlist_h_
    1.35 +
    1.36 +#include <new>
    1.37 +#include <stdlib.h>
    1.38 +#include <am-allocator-policies.h>
    1.39 +#include <am-utility.h>
    1.40 +
    1.41 +namespace ke {
    1.42 +
    1.43 +// LinkedList, analagous to std::list or SourceHook::List. Since it performs a
    1.44 +// malloc() and free() on every contained node, it should be avoided unless
    1.45 +// absolutely necessary, or for when allocation performance is not a factor. It
    1.46 +// is provided here to safely port old AlliedModders code to AMTL.
    1.47 +//
    1.48 +// In order to use a circular chain, LinkedList's allocation size includes
    1.49 +// exactly one T. If T is very large, LinkedList should be allocated on the
    1.50 +// heap, to avoid using the stack.
    1.51 +template <class T, class AllocPolicy = SystemAllocatorPolicy>
    1.52 +class LinkedList : public AllocPolicy
    1.53 +{
    1.54 + public:
    1.55 +  friend class iterator;
    1.56 +
    1.57 +  class Node
    1.58 +  {
    1.59 +   public:
    1.60 +    Node(const T &o)
    1.61 +     : obj(o)
    1.62 +    {
    1.63 +    }
    1.64 +
    1.65 +    T obj;
    1.66 +    Node *next;
    1.67 +    Node *prev;
    1.68 +  };
    1.69 +
    1.70 +public:
    1.71 +  LinkedList(AllocPolicy = AllocPolicy())
    1.72 +   : length_(0)
    1.73 +  {
    1.74 +  }
    1.75 +  ~LinkedList() {
    1.76 +    clear();
    1.77 +  }
    1.78 +
    1.79 +  bool append(const T &obj) {
    1.80 +    Node *node = allocNode(obj);
    1.81 +    if (!node)
    1.82 +      return false;
    1.83 +
    1.84 +    node->prev = head()->prev;
    1.85 +    node->next = head();
    1.86 +    head()->prev->next = node;
    1.87 +    head()->prev = node;
    1.88 +
    1.89 +    length_++;
    1.90 +  }
    1.91 +
    1.92 +  bool prepend(const T &obj) {
    1.93 +    return insert(begin(), obj);
    1.94 +  }
    1.95 +
    1.96 +  size_t size() const {
    1.97 +    return length_;
    1.98 +  }
    1.99 +
   1.100 +  void clear() {
   1.101 +    Node *node = head()->next;
   1.102 +    Node *temp;
   1.103 +    head()->next = head();
   1.104 +    head()->prev = head();
   1.105 +
   1.106 +    // Iterate through the nodes until we find the sentinel again.
   1.107 +    while (node != head()) {
   1.108 +      temp = node->next;
   1.109 +      freeNode(node);
   1.110 +      node = temp;
   1.111 +    }
   1.112 +    length_ = 0;
   1.113 +  }
   1.114 +
   1.115 +  bool empty() const {
   1.116 +    return (length_ == 0);
   1.117 +  }
   1.118 +
   1.119 +  T &front() {
   1.120 +    assert(!empty());
   1.121 +    return head()->next->obj;
   1.122 +  }
   1.123 +  T &back() {
   1.124 +    assert(!empty());
   1.125 +    return head()->prev->obj;
   1.126 +  }
   1.127 +
   1.128 + private:
   1.129 +  const Node *head() const {
   1.130 +    return sentinel_.address();
   1.131 +  }
   1.132 +  Node *head() {
   1.133 +    return sentinel_.address();
   1.134 +  }
   1.135 +
   1.136 +  Node *allocNode(const T &obj) {
   1.137 +    Node *node = (Node *)this->malloc(sizeof(Node));
   1.138 +    if (!node)
   1.139 +      return NULL;
   1.140 +    new (node) Node(obj);
   1.141 +    return node;
   1.142 +  }
   1.143 +
   1.144 +  void freeNode(Node *node) {
   1.145 +    node->obj.~T();
   1.146 +    this->free(node);
   1.147 +  }
   1.148 +
   1.149 + private:
   1.150 +  StorageBuffer<Node> sentinel_;
   1.151 +  size_t length_;
   1.152 +
   1.153 + public:
   1.154 +  class iterator
   1.155 +  {
   1.156 +    friend class LinkedList;
   1.157 +
   1.158 +   public:
   1.159 +    iterator()
   1.160 +     : this_(NULL)
   1.161 +    {
   1.162 +    }
   1.163 +    iterator(const LinkedList &src)
   1.164 +     : this_(src.head())
   1.165 +    {
   1.166 +    }
   1.167 +    iterator(Node *n)
   1.168 +     : this_(n)
   1.169 +    {
   1.170 +    }
   1.171 +    iterator(const iterator &where)
   1.172 +     : this_(where.this_)
   1.173 +    {
   1.174 +    }
   1.175 +
   1.176 +    iterator &operator --() {
   1.177 +      if (this_)
   1.178 +        this_ = this_->prev;
   1.179 +      return *this;
   1.180 +    }
   1.181 +    iterator operator --(int) {
   1.182 +      iterator old(*this);
   1.183 +      if (this_)
   1.184 +        this_ = this_->prev;
   1.185 +      return old;
   1.186 +    }  
   1.187 +    iterator &operator ++() {
   1.188 +      if (this_)
   1.189 +        this_ = this_->next;
   1.190 +      return *this;
   1.191 +    }
   1.192 +    iterator operator ++(int) {
   1.193 +      iterator old(*this);
   1.194 +      if (this_)
   1.195 +        this_ = this_->next;
   1.196 +      return old;
   1.197 +    }
   1.198 +    
   1.199 +    const T &operator * () const {
   1.200 +      return this_->obj;
   1.201 +    }
   1.202 +    T &operator * () {
   1.203 +      return this_->obj;
   1.204 +    }
   1.205 +    T *operator ->() {
   1.206 +      return &this_->obj;
   1.207 +    }
   1.208 +    const T *operator ->() const {
   1.209 +      return &(this_->obj);
   1.210 +    }
   1.211 +    
   1.212 +    bool operator !=(const iterator &where) const {
   1.213 +      return (this_ != where.this_);
   1.214 +    }
   1.215 +    bool operator ==(const iterator &where) const {
   1.216 +      return (this_ == where.this_);
   1.217 +    }
   1.218 +
   1.219 +    operator bool() {
   1.220 +      return !!this_;
   1.221 +    }
   1.222 +
   1.223 +   private:
   1.224 +    Node *this_;
   1.225 +  };
   1.226 +
   1.227 + public:
   1.228 +  iterator begin() const {
   1.229 +    return iterator(head()->next);
   1.230 +  }
   1.231 +  iterator end() const {
   1.232 +    return iterator(head());
   1.233 +  }
   1.234 +  iterator erase(iterator &where) {
   1.235 +    Node *pNode = where.this_;
   1.236 +    iterator iter(where);
   1.237 +    iter++;
   1.238 +
   1.239 +    pNode->prev->next = pNode->next;
   1.240 +    pNode->next->prev = pNode->prev;
   1.241 +
   1.242 +    freeNode(pNode);
   1.243 +    length_--;
   1.244 +
   1.245 +    return iter;
   1.246 +  }
   1.247 +  iterator insert(iterator where, const T &obj) {
   1.248 +    // Insert obj right before where
   1.249 +    Node *node = allocNode(obj);
   1.250 +    if (!node)
   1.251 +      return where;
   1.252 +
   1.253 +    Node *pWhereNode = where.this_;
   1.254 +    
   1.255 +    pWhereNode->prev->next = node;
   1.256 +    node->prev = pWhereNode->prev;
   1.257 +    pWhereNode->prev = node;
   1.258 +    node->next = pWhereNode;
   1.259 +
   1.260 +    length_++;
   1.261 +    return iterator(node);
   1.262 +  }
   1.263 +
   1.264 + public:
   1.265 +  void remove(const T &obj) {
   1.266 +    for (iterator b = begin(); b != end(); b++) {
   1.267 +      if (*b == obj) {
   1.268 +        erase(b);
   1.269 +        break;
   1.270 +      }
   1.271 +    }
   1.272 +  }
   1.273 +
   1.274 +  template <typename U>
   1.275 +  iterator find(const U &equ) const {
   1.276 +    for (iterator iter = begin(); iter != end(); iter++) {
   1.277 +      if (*iter == equ)
   1.278 +        return iter;
   1.279 +    }
   1.280 +    return end();
   1.281 +  }
   1.282 +
   1.283 +
   1.284 + private:
   1.285 +  // These are disallowed because they basically violate the failure handling
   1.286 +  // model for AllocPolicies and are also likely to have abysmal performance.
   1.287 +  LinkedList &operator =(const LinkedList<T> &other) KE_DELETE;
   1.288 +  LinkedList(const LinkedList<T> &other) KE_DELETE;
   1.289 +};
   1.290 +
   1.291 +} // namespace ke
   1.292 +
   1.293 +#endif //_INCLUDE_CSDM_LIST_H