core/sourcehook/sh_list.h
author Scott Ehlert <ds@alliedmods.net>
Thu Dec 10 00:59:50 2009 -0600 (2009-12-10)
changeset 689 4065ba5e9155
parent 684 8015336442cb
child 733 2365240861a2
permissions -rw-r--r--
Rewrote user message caching code to always use IServerGameDLL::GetUserMessageInfo (bug 4117, r=dvander).

Games where the above function can crash are handled by detouring tier0's Error() function and jumping back to our own code. So in theory this should work on all games now.
dvander@98
     1
/* ======== SourceMM ========
ds@523
     2
* Copyright (C) 2004-2008 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@684
    15
#include <stdlib.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
pavolmarko@435
   106
		void push_sorted(const T &obj)
pavolmarko@435
   107
		{
pavolmarko@435
   108
			iterator iter;
pavolmarko@435
   109
			for (iter = begin(); iter != end(); ++iter)
pavolmarko@435
   110
			{
pavolmarko@435
   111
				if (obj < *iter)
pavolmarko@435
   112
				{
pavolmarko@435
   113
					insert(iter, obj);
pavolmarko@435
   114
					return;
pavolmarko@435
   115
				}
pavolmarko@435
   116
			}
pavolmarko@435
   117
			push_back(obj);
pavolmarko@435
   118
		}
pavolmarko@435
   119
dvander@279
   120
		size_t size() const
pavolmarko@163
   121
		{
pavolmarko@163
   122
			return m_Size;
pavolmarko@163
   123
		}
pavolmarko@163
   124
pavolmarko@163
   125
		void clear()
dvander@98
   126
		{
pavolmarko@163
   127
			ListNode *node = m_Head->next;
pavolmarko@163
   128
			ListNode *temp;
pavolmarko@163
   129
			m_Head->next = m_Head;
pavolmarko@163
   130
			m_Head->prev = m_Head;
pavolmarko@163
   131
pavolmarko@163
   132
			// Iterate through the nodes until we find g_Head (the sentinel) again
pavolmarko@163
   133
			while (node != m_Head)
pavolmarko@163
   134
			{
pavolmarko@163
   135
				temp = node->next;
pavolmarko@163
   136
				delete node;
pavolmarko@163
   137
				node = temp;
pavolmarko@163
   138
			}
pavolmarko@163
   139
			m_Size = 0;
dvander@98
   140
		}
dvander@279
   141
		bool empty() const
pavolmarko@163
   142
		{
pavolmarko@163
   143
			return (m_Size == 0);
pavolmarko@163
   144
		}
pavolmarko@380
   145
		T & front()
pavolmarko@380
   146
		{
pavolmarko@380
   147
			return m_Head->next->obj;
pavolmarko@380
   148
		}
pavolmarko@163
   149
		T & back()
pavolmarko@163
   150
		{
pavolmarko@163
   151
			return m_Head->prev->obj;
pavolmarko@163
   152
		}
pavolmarko@163
   153
	private:
pavolmarko@163
   154
		ListNode *m_Head;
pavolmarko@163
   155
		size_t m_Size;
dvander@98
   156
	public:
pavolmarko@163
   157
		class iterator
dvander@98
   158
		{
pavolmarko@163
   159
		friend class List;
pavolmarko@163
   160
		public:
pavolmarko@163
   161
			iterator()
pavolmarko@163
   162
			{
pavolmarko@163
   163
				m_This = NULL;
pavolmarko@163
   164
			}
pavolmarko@163
   165
			iterator(const List &src)
pavolmarko@163
   166
			{
pavolmarko@163
   167
				m_This = src.m_Head;
pavolmarko@163
   168
			}
pavolmarko@163
   169
			iterator(ListNode *n) : m_This(n)
pavolmarko@163
   170
			{
pavolmarko@163
   171
			}
pavolmarko@163
   172
			iterator(const iterator &where)
pavolmarko@163
   173
			{
pavolmarko@163
   174
				m_This = where.m_This;
pavolmarko@163
   175
			}
pavolmarko@163
   176
			//pre decrement
pavolmarko@163
   177
			iterator & operator--()
pavolmarko@163
   178
			{
pavolmarko@163
   179
				if (m_This)
pavolmarko@163
   180
					m_This = m_This->prev;
pavolmarko@163
   181
				return *this;
pavolmarko@163
   182
			}
pavolmarko@163
   183
			//post decrement
pavolmarko@163
   184
			iterator operator--(int)
pavolmarko@163
   185
			{
pavolmarko@163
   186
				iterator old(*this);
pavolmarko@163
   187
				if (m_This)
pavolmarko@163
   188
					m_This = m_This->prev;
pavolmarko@163
   189
				return old;
pavolmarko@163
   190
			}	
pavolmarko@163
   191
			
pavolmarko@163
   192
			//pre increment
pavolmarko@163
   193
			iterator & operator++()
pavolmarko@163
   194
			{
pavolmarko@163
   195
				if (m_This)
pavolmarko@163
   196
					m_This = m_This->next;
pavolmarko@163
   197
				return *this;
pavolmarko@163
   198
			}
pavolmarko@163
   199
			//post increment
pavolmarko@163
   200
			iterator operator++(int)
pavolmarko@163
   201
			{
pavolmarko@163
   202
				iterator old(*this);
pavolmarko@163
   203
				if (m_This)
pavolmarko@163
   204
					m_This = m_This->next;
pavolmarko@163
   205
				return old;
pavolmarko@163
   206
			}
pavolmarko@163
   207
			
pavolmarko@163
   208
			const T & operator * () const
pavolmarko@163
   209
			{
pavolmarko@163
   210
				return m_This->obj;
pavolmarko@163
   211
			}
pavolmarko@163
   212
			T & operator * ()
pavolmarko@163
   213
			{
pavolmarko@163
   214
				return m_This->obj;
pavolmarko@163
   215
			}
pavolmarko@163
   216
			
pavolmarko@163
   217
			T * operator -> ()
pavolmarko@163
   218
			{
pavolmarko@163
   219
				return &(m_This->obj);
pavolmarko@163
   220
			}
pavolmarko@163
   221
			const T * operator -> () const
pavolmarko@163
   222
			{
pavolmarko@163
   223
				return &(m_This->obj);
pavolmarko@163
   224
			}
pavolmarko@163
   225
			
pavolmarko@163
   226
			bool operator != (const iterator &where) const
pavolmarko@163
   227
			{
pavolmarko@163
   228
				return (m_This != where.m_This);
pavolmarko@163
   229
			}
pavolmarko@163
   230
			bool operator ==(const iterator &where) const
pavolmarko@163
   231
			{
pavolmarko@163
   232
				return (m_This == where.m_This);
pavolmarko@163
   233
			}
pavolmarko@380
   234
pavolmarko@380
   235
			operator bool()
pavolmarko@380
   236
			{
pavolmarko@380
   237
				return m_This != NULL;
pavolmarko@380
   238
			}
pavolmarko@163
   239
		private:
pavolmarko@163
   240
			ListNode *m_This;
pavolmarko@163
   241
		};
pavolmarko@163
   242
	public:
pavolmarko@163
   243
		iterator begin() const
pavolmarko@111
   244
		{
pavolmarko@163
   245
			return iterator(m_Head->next);
pavolmarko@163
   246
		}
pavolmarko@163
   247
		iterator end() const
pavolmarko@163
   248
		{
pavolmarko@163
   249
			return iterator(m_Head);
pavolmarko@163
   250
		}
pavolmarko@163
   251
		iterator erase(iterator &where)
pavolmarko@163
   252
		{
pavolmarko@163
   253
			ListNode *pNode = where.m_This;
pavolmarko@163
   254
			iterator iter(where);
pavolmarko@163
   255
			iter++;
pavolmarko@163
   256
pavolmarko@163
   257
pavolmarko@163
   258
			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
pavolmarko@163
   259
			pNode->prev->next = pNode->next;
pavolmarko@163
   260
			pNode->next->prev = pNode->prev;
pavolmarko@163
   261
pavolmarko@163
   262
			delete pNode;
pavolmarko@163
   263
			m_Size--;
pavolmarko@163
   264
pavolmarko@163
   265
			return iter;
pavolmarko@163
   266
		}
pavolmarko@163
   267
pavolmarko@163
   268
		iterator insert(iterator where, const T &obj)
dvander@98
   269
		{
pavolmarko@163
   270
			// Insert obj right before where
pavolmarko@163
   271
pavolmarko@163
   272
			ListNode *node = new ListNode(obj);
pavolmarko@163
   273
			ListNode *pWhereNode = where.m_This;
pavolmarko@163
   274
			
pavolmarko@163
   275
			pWhereNode->prev->next = node;
pavolmarko@163
   276
			node->prev = pWhereNode->prev;
pavolmarko@163
   277
			pWhereNode->prev = node;
pavolmarko@163
   278
			node->next = pWhereNode;
pavolmarko@163
   279
pavolmarko@163
   280
			m_Size++;
pavolmarko@163
   281
pavolmarko@163
   282
			return iterator(node);
pavolmarko@163
   283
		}
pavolmarko@163
   284
pavolmarko@163
   285
	public:
pavolmarko@163
   286
		void remove(const T & obj)
pavolmarko@163
   287
		{
pavolmarko@163
   288
			iterator b;
pavolmarko@163
   289
			for (b=begin(); b!=end(); b++)
pavolmarko@163
   290
			{
pavolmarko@163
   291
				if ( (*b) == obj )
pavolmarko@163
   292
				{
pavolmarko@163
   293
					erase( b );
pavolmarko@163
   294
					break;
pavolmarko@163
   295
				}
pavolmarko@163
   296
			}
pavolmarko@163
   297
		}
pavolmarko@163
   298
		template <typename U>
dvander@279
   299
		iterator find(const U & equ) const
pavolmarko@163
   300
		{
pavolmarko@163
   301
			iterator iter;
pavolmarko@163
   302
			for (iter=begin(); iter!=end(); iter++)
pavolmarko@163
   303
			{
pavolmarko@163
   304
				if ( (*iter) == equ )
pavolmarko@163
   305
					return iter;
pavolmarko@163
   306
			}
pavolmarko@163
   307
			return end();
pavolmarko@163
   308
		}
pavolmarko@163
   309
		List & operator =(const List &src)
pavolmarko@163
   310
		{
pavolmarko@163
   311
			clear();
pavolmarko@163
   312
			iterator iter;
pavolmarko@163
   313
			for (iter=src.begin(); iter!=src.end(); iter++)
pavolmarko@163
   314
				push_back( (*iter) );
dvander@98
   315
			return *this;
dvander@98
   316
		}
dvander@98
   317
	};
pavolmarko@435
   318
dvander@98
   319
};	//NAMESPACE
dvander@98
   320
dvander@98
   321
#endif //_INCLUDE_CSDM_LIST_H