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