1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/sourcehook/sh_list.h Tue Sep 18 20:03:47 2007 +0000
1.3 @@ -0,0 +1,291 @@
1.4 +/* ======== SourceMM ========
1.5 +* Copyright (C) 2004-2007 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 + size_t size() const
1.104 + {
1.105 + return m_Size;
1.106 + }
1.107 +
1.108 + void clear()
1.109 + {
1.110 + ListNode *node = m_Head->next;
1.111 + ListNode *temp;
1.112 + m_Head->next = m_Head;
1.113 + m_Head->prev = m_Head;
1.114 +
1.115 + // Iterate through the nodes until we find g_Head (the sentinel) again
1.116 + while (node != m_Head)
1.117 + {
1.118 + temp = node->next;
1.119 + delete node;
1.120 + node = temp;
1.121 + }
1.122 + m_Size = 0;
1.123 + }
1.124 + bool empty() const
1.125 + {
1.126 + return (m_Size == 0);
1.127 + }
1.128 + T & back()
1.129 + {
1.130 + return m_Head->prev->obj;
1.131 + }
1.132 + private:
1.133 + ListNode *m_Head;
1.134 + size_t m_Size;
1.135 + public:
1.136 + class iterator
1.137 + {
1.138 + friend class List;
1.139 + public:
1.140 + iterator()
1.141 + {
1.142 + m_This = NULL;
1.143 + }
1.144 + iterator(const List &src)
1.145 + {
1.146 + m_This = src.m_Head;
1.147 + }
1.148 + iterator(ListNode *n) : m_This(n)
1.149 + {
1.150 + }
1.151 + iterator(const iterator &where)
1.152 + {
1.153 + m_This = where.m_This;
1.154 + }
1.155 + //pre decrement
1.156 + iterator & operator--()
1.157 + {
1.158 + if (m_This)
1.159 + m_This = m_This->prev;
1.160 + return *this;
1.161 + }
1.162 + //post decrement
1.163 + iterator operator--(int)
1.164 + {
1.165 + iterator old(*this);
1.166 + if (m_This)
1.167 + m_This = m_This->prev;
1.168 + return old;
1.169 + }
1.170 +
1.171 + //pre increment
1.172 + iterator & operator++()
1.173 + {
1.174 + if (m_This)
1.175 + m_This = m_This->next;
1.176 + return *this;
1.177 + }
1.178 + //post increment
1.179 + iterator operator++(int)
1.180 + {
1.181 + iterator old(*this);
1.182 + if (m_This)
1.183 + m_This = m_This->next;
1.184 + return old;
1.185 + }
1.186 +
1.187 + const T & operator * () const
1.188 + {
1.189 + return m_This->obj;
1.190 + }
1.191 + T & operator * ()
1.192 + {
1.193 + return m_This->obj;
1.194 + }
1.195 +
1.196 + T * operator -> ()
1.197 + {
1.198 + return &(m_This->obj);
1.199 + }
1.200 + const T * operator -> () const
1.201 + {
1.202 + return &(m_This->obj);
1.203 + }
1.204 +
1.205 + bool operator != (const iterator &where) const
1.206 + {
1.207 + return (m_This != where.m_This);
1.208 + }
1.209 + bool operator ==(const iterator &where) const
1.210 + {
1.211 + return (m_This == where.m_This);
1.212 + }
1.213 + private:
1.214 + ListNode *m_This;
1.215 + };
1.216 + public:
1.217 + iterator begin() const
1.218 + {
1.219 + return iterator(m_Head->next);
1.220 + }
1.221 + iterator end() const
1.222 + {
1.223 + return iterator(m_Head);
1.224 + }
1.225 + iterator erase(iterator &where)
1.226 + {
1.227 + ListNode *pNode = where.m_This;
1.228 + iterator iter(where);
1.229 + iter++;
1.230 +
1.231 +
1.232 + // Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
1.233 + pNode->prev->next = pNode->next;
1.234 + pNode->next->prev = pNode->prev;
1.235 +
1.236 + delete pNode;
1.237 + m_Size--;
1.238 +
1.239 + return iter;
1.240 + }
1.241 +
1.242 + iterator insert(iterator where, const T &obj)
1.243 + {
1.244 + // Insert obj right before where
1.245 +
1.246 + ListNode *node = new ListNode(obj);
1.247 + ListNode *pWhereNode = where.m_This;
1.248 +
1.249 + pWhereNode->prev->next = node;
1.250 + node->prev = pWhereNode->prev;
1.251 + pWhereNode->prev = node;
1.252 + node->next = pWhereNode;
1.253 +
1.254 + m_Size++;
1.255 +
1.256 + return iterator(node);
1.257 + }
1.258 +
1.259 + public:
1.260 + void remove(const T & obj)
1.261 + {
1.262 + iterator b;
1.263 + for (b=begin(); b!=end(); b++)
1.264 + {
1.265 + if ( (*b) == obj )
1.266 + {
1.267 + erase( b );
1.268 + break;
1.269 + }
1.270 + }
1.271 + }
1.272 + template <typename U>
1.273 + iterator find(const U & equ) const
1.274 + {
1.275 + iterator iter;
1.276 + for (iter=begin(); iter!=end(); iter++)
1.277 + {
1.278 + if ( (*iter) == equ )
1.279 + return iter;
1.280 + }
1.281 + return end();
1.282 + }
1.283 + List & operator =(const List &src)
1.284 + {
1.285 + clear();
1.286 + iterator iter;
1.287 + for (iter=src.begin(); iter!=src.end(); iter++)
1.288 + push_back( (*iter) );
1.289 + return *this;
1.290 + }
1.291 + };
1.292 +}; //NAMESPACE
1.293 +
1.294 +#endif //_INCLUDE_CSDM_LIST_H