danderson@0: // vim: set sts=8 ts=2 sw=2 tw=99 et: danderson@0: // danderson@0: // Copyright (C) 2013, David Anderson and AlliedModders LLC danderson@0: // All rights reserved. danderson@0: // danderson@0: // Redistribution and use in source and binary forms, with or without danderson@0: // modification, are permitted provided that the following conditions are met: danderson@0: // danderson@0: // * Redistributions of source code must retain the above copyright notice, this danderson@0: // list of conditions and the following disclaimer. danderson@0: // * Redistributions in binary form must reproduce the above copyright notice, danderson@0: // this list of conditions and the following disclaimer in the documentation danderson@0: // and/or other materials provided with the distribution. danderson@0: // * Neither the name of AlliedModders LLC nor the names of its contributors danderson@0: // may be used to endorse or promote products derived from this software danderson@0: // without specific prior written permission. danderson@0: // danderson@0: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" danderson@0: // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE danderson@0: // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE danderson@0: // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE danderson@0: // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR danderson@0: // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF danderson@0: // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS danderson@0: // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN danderson@0: // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) danderson@0: // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE danderson@0: // POSSIBILITY OF SUCH DAMAGE. danderson@0: danderson@0: #ifndef _include_amtl_linkedlist_h_ danderson@0: #define _include_amtl_linkedlist_h_ danderson@0: danderson@0: #include danderson@0: #include danderson@0: #include danderson@0: #include danderson@11: #include danderson@0: danderson@0: namespace ke { danderson@0: danderson@0: // LinkedList, analagous to std::list or SourceHook::List. Since it performs a danderson@0: // malloc() and free() on every contained node, it should be avoided unless danderson@0: // absolutely necessary, or for when allocation performance is not a factor. It danderson@0: // is provided here to safely port old AlliedModders code to AMTL. danderson@0: // danderson@0: // In order to use a circular chain, LinkedList's allocation size includes danderson@0: // exactly one T. If T is very large, LinkedList should be allocated on the danderson@0: // heap, to avoid using the stack. danderson@0: template danderson@0: class LinkedList : public AllocPolicy danderson@0: { danderson@0: public: danderson@0: friend class iterator; danderson@0: danderson@0: class Node danderson@0: { danderson@0: public: danderson@0: Node(const T &o) danderson@0: : obj(o) danderson@0: { danderson@0: } danderson@11: Node(Moveable o) danderson@11: : obj(o) danderson@11: { danderson@11: } danderson@0: danderson@0: T obj; danderson@0: Node *next; danderson@0: Node *prev; danderson@0: }; danderson@0: danderson@0: public: danderson@0: LinkedList(AllocPolicy = AllocPolicy()) danderson@0: : length_(0) danderson@0: { danderson@11: head()->prev = head(); danderson@11: head()->next = head(); danderson@0: } danderson@0: ~LinkedList() { danderson@0: clear(); danderson@0: } danderson@0: danderson@0: bool append(const T &obj) { danderson@11: return insertBefore(end(), obj) != end(); danderson@11: } danderson@11: bool append(Moveable obj) { danderson@11: return insertBefore(end(), obj) != end(); danderson@0: } danderson@0: danderson@0: bool prepend(const T &obj) { danderson@11: return insertBefore(begin(), obj) != begin(); danderson@11: } danderson@11: bool prepend(Moveable obj) { danderson@11: return insertBefore(begin(), obj) != begin(); danderson@0: } danderson@0: danderson@11: size_t length() const { danderson@0: return length_; danderson@0: } danderson@0: danderson@0: void clear() { danderson@0: Node *node = head()->next; danderson@0: Node *temp; danderson@0: head()->next = head(); danderson@0: head()->prev = head(); danderson@0: danderson@0: // Iterate through the nodes until we find the sentinel again. danderson@0: while (node != head()) { danderson@0: temp = node->next; danderson@0: freeNode(node); danderson@0: node = temp; danderson@0: } danderson@0: length_ = 0; danderson@0: } danderson@0: danderson@0: bool empty() const { danderson@0: return (length_ == 0); danderson@0: } danderson@0: danderson@0: T &front() { danderson@0: assert(!empty()); danderson@0: return head()->next->obj; danderson@0: } danderson@0: T &back() { danderson@0: assert(!empty()); danderson@0: return head()->prev->obj; danderson@0: } danderson@0: danderson@0: private: danderson@0: const Node *head() const { danderson@0: return sentinel_.address(); danderson@0: } danderson@0: Node *head() { danderson@0: return sentinel_.address(); danderson@0: } danderson@0: danderson@0: Node *allocNode(const T &obj) { danderson@0: Node *node = (Node *)this->malloc(sizeof(Node)); danderson@0: if (!node) danderson@0: return NULL; danderson@0: new (node) Node(obj); danderson@0: return node; danderson@0: } danderson@11: Node *allocNode(Moveable obj) { danderson@11: Node *node = (Node *)this->malloc(sizeof(Node)); danderson@11: if (!node) danderson@11: return NULL; danderson@11: new (node) Node(obj); danderson@11: return node; danderson@11: } danderson@0: danderson@0: void freeNode(Node *node) { danderson@0: node->obj.~T(); danderson@0: this->free(node); danderson@0: } danderson@0: danderson@0: private: danderson@0: StorageBuffer sentinel_; danderson@0: size_t length_; danderson@0: danderson@0: public: danderson@0: class iterator danderson@0: { danderson@0: friend class LinkedList; danderson@0: danderson@0: public: danderson@0: iterator() danderson@0: : this_(NULL) danderson@0: { danderson@0: } danderson@0: iterator(const LinkedList &src) danderson@0: : this_(src.head()) danderson@0: { danderson@0: } danderson@0: iterator(Node *n) danderson@0: : this_(n) danderson@0: { danderson@0: } danderson@0: iterator(const iterator &where) danderson@0: : this_(where.this_) danderson@0: { danderson@0: } danderson@0: danderson@0: iterator &operator --() { danderson@0: if (this_) danderson@0: this_ = this_->prev; danderson@0: return *this; danderson@0: } danderson@0: iterator operator --(int) { danderson@0: iterator old(*this); danderson@0: if (this_) danderson@0: this_ = this_->prev; danderson@0: return old; danderson@0: } danderson@0: iterator &operator ++() { danderson@0: if (this_) danderson@0: this_ = this_->next; danderson@0: return *this; danderson@0: } danderson@0: iterator operator ++(int) { danderson@0: iterator old(*this); danderson@0: if (this_) danderson@0: this_ = this_->next; danderson@0: return old; danderson@0: } danderson@0: danderson@0: const T &operator * () const { danderson@0: return this_->obj; danderson@0: } danderson@0: T &operator * () { danderson@0: return this_->obj; danderson@0: } danderson@0: T *operator ->() { danderson@0: return &this_->obj; danderson@0: } danderson@0: const T *operator ->() const { danderson@0: return &(this_->obj); danderson@0: } danderson@0: danderson@0: bool operator !=(const iterator &where) const { danderson@0: return (this_ != where.this_); danderson@0: } danderson@0: bool operator ==(const iterator &where) const { danderson@0: return (this_ == where.this_); danderson@0: } danderson@0: danderson@0: operator bool() { danderson@0: return !!this_; danderson@0: } danderson@0: danderson@0: private: danderson@0: Node *this_; danderson@0: }; danderson@0: danderson@11: private: danderson@11: // Insert obj right before where. danderson@11: iterator insert(iterator where, Node *node) { danderson@0: if (!node) danderson@0: return where; danderson@0: danderson@0: Node *pWhereNode = where.this_; danderson@0: danderson@0: pWhereNode->prev->next = node; danderson@0: node->prev = pWhereNode->prev; danderson@0: pWhereNode->prev = node; danderson@0: node->next = pWhereNode; danderson@0: danderson@0: length_++; danderson@0: return iterator(node); danderson@0: } danderson@0: danderson@0: public: danderson@11: iterator begin() { danderson@11: return iterator(head()->next); danderson@11: } danderson@11: iterator end() { danderson@11: return iterator(head()); danderson@11: } danderson@11: iterator erase(iterator where) { danderson@11: Node *pNode = where.this_; danderson@11: iterator iter(where); danderson@11: iter++; danderson@11: danderson@11: pNode->prev->next = pNode->next; danderson@11: pNode->next->prev = pNode->prev; danderson@11: danderson@11: freeNode(pNode); danderson@11: length_--; danderson@11: danderson@11: return iter; danderson@11: } danderson@11: iterator insertBefore(iterator where, const T &obj) { danderson@11: return insert(where, allocNode(obj)); danderson@11: } danderson@11: iterator insertBefore(iterator where, Moveable obj) { danderson@11: return insert(where, allocNode(obj)); danderson@11: } danderson@11: danderson@11: public: danderson@11: // Removes one instance of |obj| from the list, if found. danderson@0: void remove(const T &obj) { danderson@0: for (iterator b = begin(); b != end(); b++) { danderson@0: if (*b == obj) { danderson@0: erase(b); danderson@0: break; danderson@0: } danderson@0: } danderson@0: } danderson@0: danderson@0: template danderson@11: iterator find(const U &equ) { danderson@0: for (iterator iter = begin(); iter != end(); iter++) { danderson@0: if (*iter == equ) danderson@0: return iter; danderson@0: } danderson@0: return end(); danderson@0: } danderson@0: danderson@0: danderson@0: private: danderson@0: // These are disallowed because they basically violate the failure handling danderson@0: // model for AllocPolicies and are also likely to have abysmal performance. danderson@0: LinkedList &operator =(const LinkedList &other) KE_DELETE; danderson@0: LinkedList(const LinkedList &other) KE_DELETE; danderson@0: }; danderson@0: danderson@0: } // namespace ke danderson@0: danderson@0: #endif //_INCLUDE_CSDM_LIST_H