1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/core/sourcehook/sh_list.h Fri Nov 14 04:04:02 2008 -0600
1.3 @@ -0,0 +1,321 @@
1.4 +/* ======== SourceMM ========
1.5 +* Copyright (C) 2004-2008 Metamod:Source Development Team
1.6 +* No warranties of any kind
1.7 +*
1.8 +* License: zlib/libpng
1.9 +*
1.10 +* Author(s): David "BAILOPAN" Anderson
1.11 +* ============================
1.12 +*/
1.13 +
1.14 +#ifndef _INCLUDE_SMM_LIST_H
1.15 +#define _INCLUDE_SMM_LIST_H
1.16 +
1.17 +#include <new>
1.18 +#include <malloc.h>
1.19 +
1.20 +namespace SourceHook
1.21 +{
1.22 +
1.23 + //This class is from CSDM for AMX Mod X
1.24 + /*
1.25 + A circular, doubly-linked list with one sentinel node
1.26 +
1.27 + Empty:
1.28 + m_Head = sentinel
1.29 + m_Head->next = m_Head;
1.30 + m_Head->prev = m_Head;
1.31 + One element:
1.32 + m_Head = sentinel
1.33 + m_Head->next = node1
1.34 + m_Head->prev = node1
1.35 + node1->next = m_Head
1.36 + node1->prev = m_Head
1.37 + Two elements:
1.38 + m_Head = sentinel
1.39 + m_Head->next = node1
1.40 + m_Head->prev = node2
1.41 + node1->next = node2
1.42 + node1->prev = m_Head
1.43 + node2->next = m_Head
1.44 + node2->prev = node1
1.45 + */
1.46 + template <class T>
1.47 + class List
1.48 + {
1.49 + public:
1.50 + class iterator;
1.51 + friend class iterator;
1.52 + class ListNode
1.53 + {
1.54 + public:
1.55 + ListNode(const T & o) : obj(o) { };
1.56 + ListNode() { };
1.57 + T obj;
1.58 + ListNode *next;
1.59 + ListNode *prev;
1.60 + };
1.61 + private:
1.62 + // Initializes the sentinel node.
1.63 + // BAIL used malloc instead of new in order to bypass the need for a constructor.
1.64 + ListNode *_Initialize()
1.65 + {
1.66 + ListNode *n = (ListNode *)malloc(sizeof(ListNode));
1.67 + n->next = n;
1.68 + n->prev = n;
1.69 + return n;
1.70 + }
1.71 + public:
1.72 + List() : m_Head(_Initialize()), m_Size(0)
1.73 + {
1.74 + }
1.75 + List(const List &src) : m_Head(_Initialize()), m_Size(0)
1.76 + {
1.77 + iterator iter;
1.78 + for (iter=src.begin(); iter!=src.end(); iter++)
1.79 + push_back( (*iter) );
1.80 + }
1.81 + ~List()
1.82 + {
1.83 + clear();
1.84 +
1.85 + // Don't forget to free the sentinel
1.86 + if (m_Head)
1.87 + {
1.88 + free(m_Head);
1.89 + m_Head = NULL;
1.90 + }
1.91 + }
1.92 + void push_back(const T &obj)
1.93 + {
1.94 + ListNode *node = new ListNode(obj);
1.95 +
1.96 + node->prev = m_Head->prev;
1.97 + node->next = m_Head;
1.98 + m_Head->prev->next = node;
1.99 + m_Head->prev = node;
1.100 +
1.101 + m_Size++;
1.102 + }
1.103 +
1.104 + void push_front(const T &obj)
1.105 + {
1.106 + insert(begin(), obj);
1.107 + }
1.108 +
1.109 + void push_sorted(const T &obj)
1.110 + {
1.111 + iterator iter;
1.112 + for (iter = begin(); iter != end(); ++iter)
1.113 + {
1.114 + if (obj < *iter)
1.115 + {
1.116 + insert(iter, obj);
1.117 + return;
1.118 + }
1.119 + }
1.120 + push_back(obj);
1.121 + }
1.122 +
1.123 + size_t size() const
1.124 + {
1.125 + return m_Size;
1.126 + }
1.127 +
1.128 + void clear()
1.129 + {
1.130 + ListNode *node = m_Head->next;
1.131 + ListNode *temp;
1.132 + m_Head->next = m_Head;
1.133 + m_Head->prev = m_Head;
1.134 +
1.135 + // Iterate through the nodes until we find g_Head (the sentinel) again
1.136 + while (node != m_Head)
1.137 + {
1.138 + temp = node->next;
1.139 + delete node;
1.140 + node = temp;
1.141 + }
1.142 + m_Size = 0;
1.143 + }
1.144 + bool empty() const
1.145 + {
1.146 + return (m_Size == 0);
1.147 + }
1.148 + T & front()
1.149 + {
1.150 + return m_Head->next->obj;
1.151 + }
1.152 + T & back()
1.153 + {
1.154 + return m_Head->prev->obj;
1.155 + }
1.156 + private:
1.157 + ListNode *m_Head;
1.158 + size_t m_Size;
1.159 + public:
1.160 + class iterator
1.161 + {
1.162 + friend class List;
1.163 + public:
1.164 + iterator()
1.165 + {
1.166 + m_This = NULL;
1.167 + }
1.168 + iterator(const List &src)
1.169 + {
1.170 + m_This = src.m_Head;
1.171 + }
1.172 + iterator(ListNode *n) : m_This(n)
1.173 + {
1.174 + }
1.175 + iterator(const iterator &where)
1.176 + {
1.177 + m_This = where.m_This;
1.178 + }
1.179 + //pre decrement
1.180 + iterator & operator--()
1.181 + {
1.182 + if (m_This)
1.183 + m_This = m_This->prev;
1.184 + return *this;
1.185 + }
1.186 + //post decrement
1.187 + iterator operator--(int)
1.188 + {
1.189 + iterator old(*this);
1.190 + if (m_This)
1.191 + m_This = m_This->prev;
1.192 + return old;
1.193 + }
1.194 +
1.195 + //pre increment
1.196 + iterator & operator++()
1.197 + {
1.198 + if (m_This)
1.199 + m_This = m_This->next;
1.200 + return *this;
1.201 + }
1.202 + //post increment
1.203 + iterator operator++(int)
1.204 + {
1.205 + iterator old(*this);
1.206 + if (m_This)
1.207 + m_This = m_This->next;
1.208 + return old;
1.209 + }
1.210 +
1.211 + const T & operator * () const
1.212 + {
1.213 + return m_This->obj;
1.214 + }
1.215 + T & operator * ()
1.216 + {
1.217 + return m_This->obj;
1.218 + }
1.219 +
1.220 + T * operator -> ()
1.221 + {
1.222 + return &(m_This->obj);
1.223 + }
1.224 + const T * operator -> () const
1.225 + {
1.226 + return &(m_This->obj);
1.227 + }
1.228 +
1.229 + bool operator != (const iterator &where) const
1.230 + {
1.231 + return (m_This != where.m_This);
1.232 + }
1.233 + bool operator ==(const iterator &where) const
1.234 + {
1.235 + return (m_This == where.m_This);
1.236 + }
1.237 +
1.238 + operator bool()
1.239 + {
1.240 + return m_This != NULL;
1.241 + }
1.242 + private:
1.243 + ListNode *m_This;
1.244 + };
1.245 + public:
1.246 + iterator begin() const
1.247 + {
1.248 + return iterator(m_Head->next);
1.249 + }
1.250 + iterator end() const
1.251 + {
1.252 + return iterator(m_Head);
1.253 + }
1.254 + iterator erase(iterator &where)
1.255 + {
1.256 + ListNode *pNode = where.m_This;
1.257 + iterator iter(where);
1.258 + iter++;
1.259 +
1.260 +
1.261 + // Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
1.262 + pNode->prev->next = pNode->next;
1.263 + pNode->next->prev = pNode->prev;
1.264 +
1.265 + delete pNode;
1.266 + m_Size--;
1.267 +
1.268 + return iter;
1.269 + }
1.270 +
1.271 + iterator insert(iterator where, const T &obj)
1.272 + {
1.273 + // Insert obj right before where
1.274 +
1.275 + ListNode *node = new ListNode(obj);
1.276 + ListNode *pWhereNode = where.m_This;
1.277 +
1.278 + pWhereNode->prev->next = node;
1.279 + node->prev = pWhereNode->prev;
1.280 + pWhereNode->prev = node;
1.281 + node->next = pWhereNode;
1.282 +
1.283 + m_Size++;
1.284 +
1.285 + return iterator(node);
1.286 + }
1.287 +
1.288 + public:
1.289 + void remove(const T & obj)
1.290 + {
1.291 + iterator b;
1.292 + for (b=begin(); b!=end(); b++)
1.293 + {
1.294 + if ( (*b) == obj )
1.295 + {
1.296 + erase( b );
1.297 + break;
1.298 + }
1.299 + }
1.300 + }
1.301 + template <typename U>
1.302 + iterator find(const U & equ) const
1.303 + {
1.304 + iterator iter;
1.305 + for (iter=begin(); iter!=end(); iter++)
1.306 + {
1.307 + if ( (*iter) == equ )
1.308 + return iter;
1.309 + }
1.310 + return end();
1.311 + }
1.312 + List & operator =(const List &src)
1.313 + {
1.314 + clear();
1.315 + iterator iter;
1.316 + for (iter=src.begin(); iter!=src.end(); iter++)
1.317 + push_back( (*iter) );
1.318 + return *this;
1.319 + }
1.320 + };
1.321 +
1.322 +}; //NAMESPACE
1.323 +
1.324 +#endif //_INCLUDE_CSDM_LIST_H