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