| author | Pavol Marko <pavolmarko@gmail.com> |
| Sun Oct 07 22:10:07 2007 +0000 (2007-10-07) | |
| changeset 380 | f9e21a2ac558 |
| parent 294 | 0d87bc8606f8 |
| child 435 | 35296642e147 |
| permissions | -rw-r--r-- |
| dvander@98 | 1 |
/* ======== SourceMM ======== |
| ds@294 | 2 |
* Copyright (C) 2004-2007 Metamod:Source Development Team |
| dvander@98 | 3 |
* No warranties of any kind |
| dvander@98 | 4 |
* |
| dvander@98 | 5 |
* License: zlib/libpng |
| dvander@98 | 6 |
* |
| dvander@98 | 7 |
* Author(s): David "BAILOPAN" Anderson |
| dvander@98 | 8 |
* ============================ |
| dvander@98 | 9 |
*/ |
| dvander@98 | 10 |
|
| dvander@98 | 11 |
#ifndef _INCLUDE_SMM_LIST_H |
| dvander@98 | 12 |
#define _INCLUDE_SMM_LIST_H |
| dvander@98 | 13 |
|
| pavolmarko@119 | 14 |
#include <new> |
| dvander@120 | 15 |
#include <malloc.h> |
| dvander@107 | 16 |
|
| dvander@98 | 17 |
namespace SourceHook |
| dvander@98 | 18 |
{ |
| pavolmarko@163 | 19 |
|
| pavolmarko@163 | 20 |
//This class is from CSDM for AMX Mod X |
| pavolmarko@163 | 21 |
/* |
| pavolmarko@163 | 22 |
A circular, doubly-linked list with one sentinel node |
| pavolmarko@163 | 23 |
|
| pavolmarko@163 | 24 |
Empty: |
| pavolmarko@163 | 25 |
m_Head = sentinel |
| pavolmarko@163 | 26 |
m_Head->next = m_Head; |
| pavolmarko@163 | 27 |
m_Head->prev = m_Head; |
| pavolmarko@163 | 28 |
One element: |
| pavolmarko@163 | 29 |
m_Head = sentinel |
| pavolmarko@163 | 30 |
m_Head->next = node1 |
| pavolmarko@163 | 31 |
m_Head->prev = node1 |
| pavolmarko@163 | 32 |
node1->next = m_Head |
| pavolmarko@163 | 33 |
node1->prev = m_Head |
| pavolmarko@163 | 34 |
Two elements: |
| pavolmarko@163 | 35 |
m_Head = sentinel |
| pavolmarko@163 | 36 |
m_Head->next = node1 |
| pavolmarko@163 | 37 |
m_Head->prev = node2 |
| pavolmarko@163 | 38 |
node1->next = node2 |
| pavolmarko@163 | 39 |
node1->prev = m_Head |
| pavolmarko@163 | 40 |
node2->next = m_Head |
| pavolmarko@163 | 41 |
node2->prev = node1 |
| pavolmarko@163 | 42 |
*/ |
| pavolmarko@163 | 43 |
template <class T> |
| pavolmarko@163 | 44 |
class List |
| dvander@98 | 45 |
{ |
| dvander@98 | 46 |
public: |
| pavolmarko@163 | 47 |
class iterator; |
| pavolmarko@163 | 48 |
friend class iterator; |
| pavolmarko@163 | 49 |
class ListNode |
| pavolmarko@163 | 50 |
{ |
| pavolmarko@163 | 51 |
public: |
| pavolmarko@163 | 52 |
ListNode(const T & o) : obj(o) { }; |
| pavolmarko@163 | 53 |
ListNode() { }; |
| pavolmarko@163 | 54 |
T obj; |
| pavolmarko@163 | 55 |
ListNode *next; |
| pavolmarko@163 | 56 |
ListNode *prev; |
| pavolmarko@163 | 57 |
}; |
| pavolmarko@163 | 58 |
private: |
| pavolmarko@163 | 59 |
// Initializes the sentinel node. |
| pavolmarko@163 | 60 |
// BAIL used malloc instead of new in order to bypass the need for a constructor. |
| pavolmarko@163 | 61 |
ListNode *_Initialize() |
| dvander@98 | 62 |
{ |
| pavolmarko@163 | 63 |
ListNode *n = (ListNode *)malloc(sizeof(ListNode)); |
| pavolmarko@163 | 64 |
n->next = n; |
| pavolmarko@163 | 65 |
n->prev = n; |
| pavolmarko@163 | 66 |
return n; |
| pavolmarko@163 | 67 |
} |
| pavolmarko@163 | 68 |
public: |
| pavolmarko@163 | 69 |
List() : m_Head(_Initialize()), m_Size(0) |
| pavolmarko@163 | 70 |
{ |
| dvander@98 | 71 |
} |
| pavolmarko@163 | 72 |
List(const List &src) : m_Head(_Initialize()), m_Size(0) |
| pavolmarko@163 | 73 |
{ |
| pavolmarko@163 | 74 |
iterator iter; |
| pavolmarko@163 | 75 |
for (iter=src.begin(); iter!=src.end(); iter++) |
| pavolmarko@163 | 76 |
push_back( (*iter) ); |
| pavolmarko@163 | 77 |
} |
| pavolmarko@163 | 78 |
~List() |
| pavolmarko@163 | 79 |
{ |
| pavolmarko@163 | 80 |
clear(); |
| dvander@98 | 81 |
|
| pavolmarko@163 | 82 |
// Don't forget to free the sentinel |
| pavolmarko@163 | 83 |
if (m_Head) |
| pavolmarko@163 | 84 |
{ |
| pavolmarko@163 | 85 |
free(m_Head); |
| pavolmarko@163 | 86 |
m_Head = NULL; |
| pavolmarko@163 | 87 |
} |
| pavolmarko@163 | 88 |
} |
| pavolmarko@163 | 89 |
void push_back(const T &obj) |
| dvander@98 | 90 |
{ |
| pavolmarko@163 | 91 |
ListNode *node = new ListNode(obj); |
| pavolmarko@163 | 92 |
|
| dvander@98 | 93 |
node->prev = m_Head->prev; |
| dvander@98 | 94 |
node->next = m_Head; |
| dvander@98 | 95 |
m_Head->prev->next = node; |
| dvander@98 | 96 |
m_Head->prev = node; |
| pavolmarko@163 | 97 |
|
| pavolmarko@163 | 98 |
m_Size++; |
| dvander@98 | 99 |
} |
| pavolmarko@380 | 100 |
|
| pavolmarko@380 | 101 |
void push_front(const T &obj) |
| pavolmarko@380 | 102 |
{ |
| pavolmarko@380 | 103 |
insert(begin(), obj); |
| pavolmarko@380 | 104 |
} |
| pavolmarko@380 | 105 |
|
| dvander@279 | 106 |
size_t size() const |
| pavolmarko@163 | 107 |
{ |
| pavolmarko@163 | 108 |
return m_Size; |
| pavolmarko@163 | 109 |
} |
| pavolmarko@163 | 110 |
|
| pavolmarko@163 | 111 |
void clear() |
| dvander@98 | 112 |
{ |
| pavolmarko@163 | 113 |
ListNode *node = m_Head->next; |
| pavolmarko@163 | 114 |
ListNode *temp; |
| pavolmarko@163 | 115 |
m_Head->next = m_Head; |
| pavolmarko@163 | 116 |
m_Head->prev = m_Head; |
| pavolmarko@163 | 117 |
|
| pavolmarko@163 | 118 |
// Iterate through the nodes until we find g_Head (the sentinel) again |
| pavolmarko@163 | 119 |
while (node != m_Head) |
| pavolmarko@163 | 120 |
{ |
| pavolmarko@163 | 121 |
temp = node->next; |
| pavolmarko@163 | 122 |
delete node; |
| pavolmarko@163 | 123 |
node = temp; |
| pavolmarko@163 | 124 |
} |
| pavolmarko@163 | 125 |
m_Size = 0; |
| dvander@98 | 126 |
} |
| dvander@279 | 127 |
bool empty() const |
| pavolmarko@163 | 128 |
{ |
| pavolmarko@163 | 129 |
return (m_Size == 0); |
| pavolmarko@163 | 130 |
} |
| pavolmarko@380 | 131 |
T & front() |
| pavolmarko@380 | 132 |
{ |
| pavolmarko@380 | 133 |
return m_Head->next->obj; |
| pavolmarko@380 | 134 |
} |
| pavolmarko@163 | 135 |
T & back() |
| pavolmarko@163 | 136 |
{ |
| pavolmarko@163 | 137 |
return m_Head->prev->obj; |
| pavolmarko@163 | 138 |
} |
| pavolmarko@163 | 139 |
private: |
| pavolmarko@163 | 140 |
ListNode *m_Head; |
| pavolmarko@163 | 141 |
size_t m_Size; |
| dvander@98 | 142 |
public: |
| pavolmarko@163 | 143 |
class iterator |
| dvander@98 | 144 |
{ |
| pavolmarko@163 | 145 |
friend class List; |
| pavolmarko@163 | 146 |
public: |
| pavolmarko@163 | 147 |
iterator() |
| pavolmarko@163 | 148 |
{ |
| pavolmarko@163 | 149 |
m_This = NULL; |
| pavolmarko@163 | 150 |
} |
| pavolmarko@163 | 151 |
iterator(const List &src) |
| pavolmarko@163 | 152 |
{ |
| pavolmarko@163 | 153 |
m_This = src.m_Head; |
| pavolmarko@163 | 154 |
} |
| pavolmarko@163 | 155 |
iterator(ListNode *n) : m_This(n) |
| pavolmarko@163 | 156 |
{ |
| pavolmarko@163 | 157 |
} |
| pavolmarko@163 | 158 |
iterator(const iterator &where) |
| pavolmarko@163 | 159 |
{ |
| pavolmarko@163 | 160 |
m_This = where.m_This; |
| pavolmarko@163 | 161 |
} |
| pavolmarko@163 | 162 |
//pre decrement |
| pavolmarko@163 | 163 |
iterator & operator--() |
| pavolmarko@163 | 164 |
{ |
| pavolmarko@163 | 165 |
if (m_This) |
| pavolmarko@163 | 166 |
m_This = m_This->prev; |
| pavolmarko@163 | 167 |
return *this; |
| pavolmarko@163 | 168 |
} |
| pavolmarko@163 | 169 |
//post decrement |
| pavolmarko@163 | 170 |
iterator operator--(int) |
| pavolmarko@163 | 171 |
{ |
| pavolmarko@163 | 172 |
iterator old(*this); |
| pavolmarko@163 | 173 |
if (m_This) |
| pavolmarko@163 | 174 |
m_This = m_This->prev; |
| pavolmarko@163 | 175 |
return old; |
| pavolmarko@163 | 176 |
} |
| pavolmarko@163 | 177 |
|
| pavolmarko@163 | 178 |
//pre increment |
| pavolmarko@163 | 179 |
iterator & operator++() |
| pavolmarko@163 | 180 |
{ |
| pavolmarko@163 | 181 |
if (m_This) |
| pavolmarko@163 | 182 |
m_This = m_This->next; |
| pavolmarko@163 | 183 |
return *this; |
| pavolmarko@163 | 184 |
} |
| pavolmarko@163 | 185 |
//post increment |
| pavolmarko@163 | 186 |
iterator operator++(int) |
| pavolmarko@163 | 187 |
{ |
| pavolmarko@163 | 188 |
iterator old(*this); |
| pavolmarko@163 | 189 |
if (m_This) |
| pavolmarko@163 | 190 |
m_This = m_This->next; |
| pavolmarko@163 | 191 |
return old; |
| pavolmarko@163 | 192 |
} |
| pavolmarko@163 | 193 |
|
| pavolmarko@163 | 194 |
const T & operator * () const |
| pavolmarko@163 | 195 |
{ |
| pavolmarko@163 | 196 |
return m_This->obj; |
| pavolmarko@163 | 197 |
} |
| pavolmarko@163 | 198 |
T & operator * () |
| pavolmarko@163 | 199 |
{ |
| pavolmarko@163 | 200 |
return m_This->obj; |
| pavolmarko@163 | 201 |
} |
| pavolmarko@163 | 202 |
|
| pavolmarko@163 | 203 |
T * operator -> () |
| pavolmarko@163 | 204 |
{ |
| pavolmarko@163 | 205 |
return &(m_This->obj); |
| pavolmarko@163 | 206 |
} |
| pavolmarko@163 | 207 |
const T * operator -> () const |
| pavolmarko@163 | 208 |
{ |
| pavolmarko@163 | 209 |
return &(m_This->obj); |
| pavolmarko@163 | 210 |
} |
| pavolmarko@163 | 211 |
|
| pavolmarko@163 | 212 |
bool operator != (const iterator &where) const |
| pavolmarko@163 | 213 |
{ |
| pavolmarko@163 | 214 |
return (m_This != where.m_This); |
| pavolmarko@163 | 215 |
} |
| pavolmarko@163 | 216 |
bool operator ==(const iterator &where) const |
| pavolmarko@163 | 217 |
{ |
| pavolmarko@163 | 218 |
return (m_This == where.m_This); |
| pavolmarko@163 | 219 |
} |
| pavolmarko@380 | 220 |
|
| pavolmarko@380 | 221 |
operator bool() |
| pavolmarko@380 | 222 |
{ |
| pavolmarko@380 | 223 |
return m_This != NULL; |
| pavolmarko@380 | 224 |
} |
| pavolmarko@163 | 225 |
private: |
| pavolmarko@163 | 226 |
ListNode *m_This; |
| pavolmarko@163 | 227 |
}; |
| pavolmarko@163 | 228 |
public: |
| pavolmarko@163 | 229 |
iterator begin() const |
| pavolmarko@111 | 230 |
{ |
| pavolmarko@163 | 231 |
return iterator(m_Head->next); |
| pavolmarko@163 | 232 |
} |
| pavolmarko@163 | 233 |
iterator end() const |
| pavolmarko@163 | 234 |
{ |
| pavolmarko@163 | 235 |
return iterator(m_Head); |
| pavolmarko@163 | 236 |
} |
| pavolmarko@163 | 237 |
iterator erase(iterator &where) |
| pavolmarko@163 | 238 |
{ |
| pavolmarko@163 | 239 |
ListNode *pNode = where.m_This; |
| pavolmarko@163 | 240 |
iterator iter(where); |
| pavolmarko@163 | 241 |
iter++; |
| pavolmarko@163 | 242 |
|
| pavolmarko@163 | 243 |
|
| pavolmarko@163 | 244 |
// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle... |
| pavolmarko@163 | 245 |
pNode->prev->next = pNode->next; |
| pavolmarko@163 | 246 |
pNode->next->prev = pNode->prev; |
| pavolmarko@163 | 247 |
|
| pavolmarko@163 | 248 |
delete pNode; |
| pavolmarko@163 | 249 |
m_Size--; |
| pavolmarko@163 | 250 |
|
| pavolmarko@163 | 251 |
return iter; |
| pavolmarko@163 | 252 |
} |
| pavolmarko@163 | 253 |
|
| pavolmarko@163 | 254 |
iterator insert(iterator where, const T &obj) |
| dvander@98 | 255 |
{ |
| pavolmarko@163 | 256 |
// Insert obj right before where |
| pavolmarko@163 | 257 |
|
| pavolmarko@163 | 258 |
ListNode *node = new ListNode(obj); |
| pavolmarko@163 | 259 |
ListNode *pWhereNode = where.m_This; |
| pavolmarko@163 | 260 |
|
| pavolmarko@163 | 261 |
pWhereNode->prev->next = node; |
| pavolmarko@163 | 262 |
node->prev = pWhereNode->prev; |
| pavolmarko@163 | 263 |
pWhereNode->prev = node; |
| pavolmarko@163 | 264 |
node->next = pWhereNode; |
| pavolmarko@163 | 265 |
|
| pavolmarko@163 | 266 |
m_Size++; |
| pavolmarko@163 | 267 |
|
| pavolmarko@163 | 268 |
return iterator(node); |
| pavolmarko@163 | 269 |
} |
| pavolmarko@163 | 270 |
|
| pavolmarko@163 | 271 |
public: |
| pavolmarko@163 | 272 |
void remove(const T & obj) |
| pavolmarko@163 | 273 |
{ |
| pavolmarko@163 | 274 |
iterator b; |
| pavolmarko@163 | 275 |
for (b=begin(); b!=end(); b++) |
| pavolmarko@163 | 276 |
{ |
| pavolmarko@163 | 277 |
if ( (*b) == obj ) |
| pavolmarko@163 | 278 |
{ |
| pavolmarko@163 | 279 |
erase( b ); |
| pavolmarko@163 | 280 |
break; |
| pavolmarko@163 | 281 |
} |
| pavolmarko@163 | 282 |
} |
| pavolmarko@163 | 283 |
} |
| pavolmarko@163 | 284 |
template <typename U> |
| dvander@279 | 285 |
iterator find(const U & equ) const |
| pavolmarko@163 | 286 |
{ |
| pavolmarko@163 | 287 |
iterator iter; |
| pavolmarko@163 | 288 |
for (iter=begin(); iter!=end(); iter++) |
| pavolmarko@163 | 289 |
{ |
| pavolmarko@163 | 290 |
if ( (*iter) == equ ) |
| pavolmarko@163 | 291 |
return iter; |
| pavolmarko@163 | 292 |
} |
| pavolmarko@163 | 293 |
return end(); |
| pavolmarko@163 | 294 |
} |
| pavolmarko@163 | 295 |
List & operator =(const List &src) |
| pavolmarko@163 | 296 |
{ |
| pavolmarko@163 | 297 |
clear(); |
| pavolmarko@163 | 298 |
iterator iter; |
| pavolmarko@163 | 299 |
for (iter=src.begin(); iter!=src.end(); iter++) |
| pavolmarko@163 | 300 |
push_back( (*iter) ); |
| dvander@98 | 301 |
return *this; |
| dvander@98 | 302 |
} |
| dvander@98 | 303 |
}; |
| dvander@98 | 304 |
}; //NAMESPACE |
| dvander@98 | 305 |
|
| dvander@98 | 306 |
#endif //_INCLUDE_CSDM_LIST_H |