Home - sourcemod-central - file revision - core/sm_fastlink.h@948527637fc8 Mercurial
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
core/sm_fastlink.h
author Borja Ferrer <faluco@alliedmods.net>
Fri Jul 27 04:37:00 2007 +0000 (2007-07-27)
changeset 1190 948527637fc8
parent 1131 d109d9e33ee5
child 1231 17badaf66ce4
permissions -rw-r--r--
bintools will now align the stack before calling a function 
     1 /**
     2  * vim: set ts=4 :
     3  * ===============================================================
     4  * SourceMod (C)2004-2007 AlliedModders LLC.  All rights reserved.
     5  * ===============================================================
     6  *
     7  * This file is not open source and may not be copied without explicit
     8  * written permission of AlliedModders LLC.  This file may not be redistributed 
     9  * in whole or significant part.
    10  * For information, see LICENSE.txt or http://www.sourcemod.net/license.php
    11  *
    12  * Version: $Id$
    13  */
    14 
    15 
    16 #ifndef _INCLUDE_SOURCEMOD_FASTLINK_H_
    17 #define _INCLUDE_SOURCEMOD_FASTLINK_H_
    18 
    19 #include <assert.h>
    20 
    21 template <typename T>
    22 class FastLink
    23 {
    24 	friend class iterator;
    25 public:
    26 	struct FastLinkNode
    27 	{
    28 		unsigned int prev;
    29 		unsigned int next;
    30 		unsigned int freeNode;
    31 		T obj;
    32 	};
    33 public:
    34 	FastLink(unsigned int maxsize) : m_Size(0), m_FirstLink(0), m_FreeNodes(0), m_LastLink(0), m_UsableIndex(0)
    35 	{
    36 		m_MaxSize = maxsize;
    37 		m_Nodes = new FastLinkNode[m_MaxSize+1];
    38 	}
    39 public:
    40 	bool push_back(const T & obj)
    41 	{
    42 		unsigned int new_node = GetFreeIndex();
    43 		if (!new_node)
    44 		{
    45 			return false;
    46 		}
    47 		m_Nodes[new_node].obj = obj;
    48 		m_Nodes[new_node].next = 0;
    49 		if (!m_FirstLink)
    50 		{
    51 			m_Nodes[new_node].prev = 0;
    52 			m_FirstLink = new_node;
    53 			m_LastLink = new_node;
    54 		} else {
    55 			m_Nodes[new_node].prev = m_LastLink;
    56 			m_Nodes[m_LastLink].next = new_node;
    57 			m_LastLink = new_node;
    58 		}
    59 		m_Size++;
    60 		return true;
    61 	}
    62 	size_t size() const
    63 	{
    64 		return m_Size;
    65 	}
    66 private:
    67 	unsigned int GetFreeIndex()
    68 	{
    69 		if (m_FreeNodes)
    70 		{
    71 			return m_Nodes[m_FreeNodes--].freeNode;
    72 		} else {
    73 			if (m_UsableIndex >= m_MaxSize)
    74 			{
    75 				return 0;
    76 			}
    77 			m_UsableIndex++;
    78 			return m_UsableIndex;
    79 		}
    80 	}
    81 public:
    82 	class iterator
    83 	{
    84 		friend class FastLink;
    85 	public:
    86 		iterator()
    87 		{
    88 			link = NULL;
    89 			position = 0;
    90 		}
    91 		iterator(const FastLink *_link, unsigned int _position)
    92 		{
    93 			link = _link;
    94 			position = _position;
    95 		}
    96 	public:
    97 		bool operator ==(const iterator &where) const
    98 		{
    99 			return (link == where.link && position == where.position);
   100 		}
   101 		bool operator !=(const iterator &where) const
   102 		{
   103 			return (link != where.link || position != where.position);
   104 		}
   105 		T & operator *()
   106 		{
   107 			return link->m_Nodes[position].obj;
   108 		}
   109 		const T & operator *() const
   110 		{
   111 			return link->m_Nodes[position].obj;
   112 		}
   113 		iterator & operator++()
   114 		{
   115 			position = link->m_Nodes[position].next;
   116 			return *this;
   117 		}
   118 	private:
   119 		const FastLink *link;
   120 		unsigned int position;
   121 	};
   122 public:
   123 	iterator begin() const
   124 	{
   125 		return iterator(this, m_FirstLink);
   126 	}
   127 	iterator end() const
   128 	{
   129 		return iterator(this, 0);
   130 	}
   131 	void remove(const T & obj)
   132 	{
   133 		for (iterator iter=begin(); iter!=end(); ++iter)
   134 		{
   135 			if ((*iter) == obj)
   136 			{
   137 				erase(iter);
   138 				return;
   139 			}
   140 		}
   141 	}
   142 	iterator erase(const iterator &where)
   143 	{
   144 		/* Whoa, this better be right! */
   145 		assert(where.link == this);
   146 
   147 		iterator iter(where.link, where.position);
   148 		++iter;
   149 
   150 		unsigned int index = where.position;
   151 
   152 		/* Each case is different, we have no sentinel.
   153 		 * CASE: We're the HEAD AND the TAIL */
   154 		if (index == m_FirstLink
   155 			&& index == m_LastLink)
   156 		{
   157 			m_FirstLink = 0;
   158 			m_LastLink = 0;
   159 		}
   160 		/* We're the HEAD */
   161 		else if (index == m_FirstLink)
   162 		{
   163 			m_FirstLink = m_Nodes[index].next;
   164 			m_Nodes[m_FirstLink].prev = 0;
   165 		}
   166 		/* We're the TAIL */
   167 		else if (index == m_LastLink)
   168 		{
   169 			m_LastLink = m_Nodes[index].prev;
   170 			m_Nodes[m_LastLink].next = 0;
   171 		}
   172 		/* We're in the middle! */
   173 		else
   174 		{
   175 			/* Patch forward reference */
   176 			m_Nodes[m_Nodes[index].next].prev = m_Nodes[index].prev;
   177 			/* Patch backward reference */
   178 			m_Nodes[m_Nodes[index].prev].next = m_Nodes[index].next;
   179 		}
   180 
   181 		/* Add us to the free list */
   182 		m_Nodes[++m_FreeNodes].freeNode = index;
   183 
   184 		m_Size--;
   185 
   186 		return iter;
   187 	}
   188 #if defined MENU_DEBUG
   189 public:
   190 #else
   191 private:
   192 #endif
   193 	size_t m_Size;
   194 	unsigned int m_FirstLink;
   195 	unsigned int m_FreeNodes;
   196 	unsigned int m_LastLink;
   197 	unsigned int m_MaxSize;
   198 	unsigned int m_UsableIndex;
   199 	FastLinkNode *m_Nodes;
   200 };
   201 
   202 #endif //_INCLUDE_SOURCEMOD_FASTLINK_H_
sourcemod-central
Feed