Added missing hashmap tests.
1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
4 // All rights reserved.
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
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.
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.
30 #ifndef _include_amtl_linkedlist_h_
31 #define _include_amtl_linkedlist_h_
35 #include <am-allocator-policies.h>
36 #include <am-utility.h>
37 #include <am-moveable.h>
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.
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
53 friend class iterator;
73 LinkedList(AllocPolicy = AllocPolicy())
76 head()->prev = head();
77 head()->next = head();
83 bool append(const T &obj) {
84 return insertBefore(end(), obj) != end();
86 bool append(Moveable<T> obj) {
87 return insertBefore(end(), obj) != end();
90 bool prepend(const T &obj) {
91 return insertBefore(begin(), obj) != begin();
93 bool prepend(Moveable<T> obj) {
94 return insertBefore(begin(), obj) != begin();
97 size_t length() const {
102 Node *node = head()->next;
104 head()->next = head();
105 head()->prev = head();
107 // Iterate through the nodes until we find the sentinel again.
108 while (node != head()) {
117 return (length_ == 0);
122 return head()->next->obj;
126 return head()->prev->obj;
130 const Node *head() const {
131 return sentinel_.address();
134 return sentinel_.address();
137 Node *allocNode(const T &obj) {
138 Node *node = (Node *)this->malloc(sizeof(Node));
141 new (node) Node(obj);
144 Node *allocNode(Moveable<T> obj) {
145 Node *node = (Node *)this->malloc(sizeof(Node));
148 new (node) Node(obj);
152 void freeNode(Node *node) {
158 StorageBuffer<Node> sentinel_;
164 friend class LinkedList;
171 iterator(const LinkedList &src)
179 iterator(const iterator &where)
184 iterator &operator --() {
189 iterator operator --(int) {
195 iterator &operator ++() {
200 iterator operator ++(int) {
207 const T &operator * () const {
216 const T *operator ->() const {
217 return &(this_->obj);
220 bool operator !=(const iterator &where) const {
221 return (this_ != where.this_);
223 bool operator ==(const iterator &where) const {
224 return (this_ == where.this_);
236 // Insert obj right before where.
237 iterator insert(iterator where, Node *node) {
241 Node *pWhereNode = where.this_;
243 pWhereNode->prev->next = node;
244 node->prev = pWhereNode->prev;
245 pWhereNode->prev = node;
246 node->next = pWhereNode;
249 return iterator(node);
254 return iterator(head()->next);
257 return iterator(head());
259 iterator erase(iterator where) {
260 Node *pNode = where.this_;
261 iterator iter(where);
264 pNode->prev->next = pNode->next;
265 pNode->next->prev = pNode->prev;
272 iterator insertBefore(iterator where, const T &obj) {
273 return insert(where, allocNode(obj));
275 iterator insertBefore(iterator where, Moveable<T> obj) {
276 return insert(where, allocNode(obj));
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++) {
290 template <typename U>
291 iterator find(const U &equ) {
292 for (iterator iter = begin(); iter != end(); iter++) {
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;
309 #endif //_INCLUDE_CSDM_LIST_H