sourcehook/sh_vector.h
author David Anderson <dvander@alliedmods.net>
Tue Dec 06 03:13:50 2005 +0000 (2005-12-06)
changeset 150 22fbddfa0209
parent 99 bfbb04d6683f
child 154 083cb82d97df
permissions -rwxr-xr-x
Fixed operator overload bug in List
Fixed memory leak in TinyHash
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2005 Metamod:Source Development Team
     3 * No warranties of any kind
     4 *
     5 * License: zlib/libpng
     6 *
     7 * Author(s): Pavol "PM OnoTo" Marko
     8 * ============================
     9 */
    10 
    11 #ifndef __CVECTOR_H__
    12 #define __CVECTOR_H__
    13 
    14 #include <assert.h>
    15 
    16 //This file originally from AMX Mod X
    17 namespace SourceHook
    18 {
    19 // Vector
    20 template <class T> class CVector
    21 {
    22 	bool Grow()
    23 	{
    24 		// automatic grow
    25 		size_t newSize = m_Size * 2;
    26 		if (newSize == 0)
    27 			newSize = 8;					// a good init value
    28 		T *newData = new T[newSize];
    29 		if (!newData)
    30 			return false;
    31 		if (m_Data)
    32 		{
    33 			for (size_t i=0; i<m_CurrentUsedSize; i++)
    34 				newData[i] = m_Data[i];
    35 			delete [] m_Data;
    36 		}
    37 		m_Data = newData;
    38 		m_Size = newSize;
    39 		return true;
    40 	}
    41 
    42 	bool GrowIfNeeded()
    43 	{
    44 		if (m_CurrentUsedSize >= m_Size)
    45 			return Grow();
    46 		else
    47 			return true;
    48 	}
    49 
    50 	bool ChangeSize(size_t size)
    51 	{
    52 		// change size
    53 		if (size == m_Size)
    54 			return true;
    55 
    56 		if (!size)
    57 		{
    58 			if (m_Data)
    59 			{
    60 				delete [] m_Data;
    61 				m_Data = NULL;
    62 				m_Size = 0;
    63 			}
    64 			return true;
    65 		}
    66 
    67 		T *newData = new T[size];
    68 		if (!newData)
    69 			return false;
    70 		if (m_Data)
    71 		{
    72 			size_t end = (m_CurrentUsedSize < size) ? (m_CurrentUsedSize) : size;
    73 			for (size_t i=0; i<end; i++)
    74 				newData[i] = m_Data[i];
    75 			delete [] m_Data;
    76 		}
    77 		m_Data = newData;
    78 		m_Size = size;
    79 		if (m_CurrentUsedSize > m_Size)
    80 			m_CurrentUsedSize = m_Size;
    81 
    82 		return true;
    83 	}
    84 
    85 	void FreeMemIfPossible()
    86 	{
    87 		if (!m_Data)
    88 			return;
    89 
    90 		if (!m_CurrentUsedSize)
    91 		{
    92 			ChangeSize(0);
    93 			return;
    94 		}
    95 
    96 		size_t newSize = m_Size;
    97 		while (m_CurrentUsedSize <= newSize / 2)
    98 			newSize /= 2;
    99 
   100 		if (newSize != m_Size)
   101 			ChangeSize(newSize);
   102 	}
   103 protected:
   104 	T *m_Data;
   105 	size_t m_Size;
   106 	size_t m_CurrentUsedSize;
   107 public:
   108 	class iterator
   109 	{
   110 	protected:
   111 		T *m_Ptr;
   112 	public:
   113 		// constructors / destructors
   114 		iterator()
   115 		{
   116 			m_Ptr = NULL;
   117 		}
   118 
   119 		iterator(T * ptr)
   120 		{
   121 			m_Ptr = ptr;
   122 		}
   123 
   124 		// member functions
   125 		T * base()
   126 		{
   127 			return m_Ptr;
   128 		}
   129 
   130 		const T * base() const
   131 		{
   132 			return m_Ptr;
   133 		}
   134 
   135 		// operators
   136 		T & operator*()
   137 		{
   138 			return *m_Ptr;
   139 		}
   140 
   141 		T * operator->()
   142 		{
   143 			return m_Ptr;
   144 		}
   145 
   146 		iterator & operator++()		// preincrement
   147 		{
   148 			++m_Ptr;
   149 			return (*this);
   150 		}
   151 
   152 		iterator operator++(int)	// postincrement
   153 		{
   154 			iterator tmp = *this;
   155 			++m_Ptr;
   156 			return tmp;
   157 		}
   158 
   159 		iterator & operator--()		// predecrement
   160 		{
   161 			--m_Ptr;
   162 			return (*this);
   163 		}
   164 
   165 		iterator operator--(int)	// postdecrememnt
   166 		{
   167 			iterator tmp = *this;
   168 			--m_Ptr;
   169 			return tmp;
   170 		}
   171 
   172 		bool operator==(T * right) const
   173 		{
   174 			return (m_Ptr == right);
   175 		}
   176 
   177 		bool operator==(const iterator & right) const
   178 		{
   179 			return (m_Ptr == right.m_Ptr);
   180 		}
   181 
   182 		bool operator!=(T * right) const
   183 		{
   184 			return (m_Ptr != right);
   185 		}
   186 
   187 		bool operator!=(const iterator & right) const
   188 		{
   189 			return (m_Ptr != right.m_Ptr);
   190 		}
   191 
   192 		iterator & operator+=(size_t offset)
   193 		{
   194 			m_Ptr += offset;
   195 			return (*this);
   196 		}
   197 
   198 		iterator & operator-=(size_t offset)
   199 		{
   200 			m_Ptr -= offset;
   201 			return (*this);
   202 		}
   203 
   204 		iterator operator+(size_t offset) const
   205 		{
   206 			iterator tmp(*this);
   207 			tmp.m_Ptr += offset;
   208 			return tmp;
   209 		}
   210 
   211 		iterator operator-(size_t offset) const
   212 		{
   213 			iterator tmp(*this);
   214 			tmp.m_Ptr -= offset;
   215 			return tmp;
   216 		}
   217 
   218 		T & operator[](size_t offset)
   219 		{
   220 			return (*(*this + offset));
   221 		}
   222 
   223 		const T & operator[](size_t offset) const
   224 		{
   225 			return (*(*this + offset));
   226 		}
   227 
   228 		bool operator<(const iterator & right) const
   229 		{
   230 			return m_Ptr < right.m_Ptr;
   231 		}
   232 
   233 		bool operator>(const iterator & right) const
   234 		{
   235 			return m_Ptr > right.m_Ptr;
   236 		}
   237 
   238 		bool operator<=(const iterator & right) const
   239 		{
   240 			return m_Ptr <= right.m_Ptr;
   241 		}
   242 
   243 		bool operator>=(const iterator & right) const
   244 		{
   245 			return m_Ptr >= right.m_Ptr;
   246 		}
   247 
   248 		size_t operator-(const iterator & right) const
   249 		{
   250 			return m_Ptr - right.m_Ptr;
   251 		}
   252 	};
   253 
   254 	// constructors / destructors
   255 	CVector<T>()
   256 	{
   257 		m_Size = 0;
   258 		m_CurrentUsedSize = 0;
   259 		m_Data = NULL;
   260 	}
   261 
   262 	CVector<T>(const CVector<T> & other)
   263 	{
   264 		// copy data
   265 		m_Data = new T [other.m_CurrentUsedSize];
   266 		m_Size = other.m_CurrentUsedSize;
   267 		m_CurrentUsedSize = other.m_CurrentUsedSize;
   268 		for (size_t i=0; i<other.m_CurrentUsedSize; i++)
   269 			m_Data[i] = other.m_Data[i];
   270 	}
   271 
   272 	~CVector<T>()
   273 	{
   274 		clear();
   275 	}
   276 
   277 	// interface
   278 	size_t size() const
   279 	{
   280 		return m_CurrentUsedSize;
   281 	}
   282 
   283 	size_t capacity() const
   284 	{
   285 		return m_Size;
   286 	}
   287 
   288 	iterator begin() const
   289 	{
   290 		return iterator(m_Data);
   291 	}
   292 
   293 	iterator end() const
   294 	{
   295 		return iterator(m_Data + m_CurrentUsedSize);
   296 	}
   297 
   298 	iterator iterAt(size_t pos)
   299 	{
   300 		if (pos > m_CurrentUsedSize)
   301 			assert(0);
   302 		return iterator(m_Data + pos);
   303 	}
   304 
   305 	bool reserve(size_t newSize)
   306 	{
   307 		if (newSize > m_Size)
   308 			return ChangeSize(newSize);
   309 		return true;
   310 	}
   311 
   312 	bool push_back(const T & elem)
   313 	{
   314 		++m_CurrentUsedSize;
   315 		if (!GrowIfNeeded())
   316 		{
   317 			--m_CurrentUsedSize;
   318 			return false;
   319 		}
   320 
   321 		m_Data[m_CurrentUsedSize - 1] = elem;
   322 		return true;
   323 	}
   324 
   325 	void pop_back()
   326 	{
   327 		--m_CurrentUsedSize;
   328 		if (m_CurrentUsedSize < 0)
   329 			m_CurrentUsedSize = 0;
   330 
   331 		FreeMemIfPossible();
   332 	}
   333 
   334 	bool resize(size_t newSize)
   335 	{
   336 		if (!ChangeSize(newSize))
   337 			return false;
   338 		m_CurrentUsedSize = newSize;
   339 		return true;
   340 	}
   341 
   342 	bool empty() const
   343 	{
   344 		return (m_CurrentUsedSize == 0);
   345 	}
   346 
   347 	T & at(size_t pos)
   348 	{
   349 		if (pos > m_CurrentUsedSize)
   350 		{
   351 			assert(0);
   352 		}
   353 		return m_Data[pos];
   354 	}
   355 
   356 	const  T & at(size_t pos) const
   357 	{
   358 		if (pos > m_CurrentUsedSize)
   359 		{
   360 			assert(0);
   361 		}
   362 		return m_Data[pos];
   363 	}
   364 
   365 	T & operator[](size_t pos)
   366 	{
   367 		return at(pos);
   368 	}
   369 
   370 	const T & operator[](size_t pos) const
   371 	{
   372 		return at(pos);
   373 	}
   374 
   375 	T & front()
   376 	{
   377 		if (m_CurrentUsedSize < 1)
   378 		{
   379 			assert(0);
   380 		}
   381 		return m_Data[0];
   382 	}
   383 
   384 	const T & front() const
   385 	{
   386 		if (m_CurrentUsedSize < 1)
   387 		{
   388 			assert(0);
   389 		}
   390 		return m_Data[0];
   391 	}
   392 
   393 	T & back()
   394 	{
   395 		if (m_CurrentUsedSize < 1)
   396 		{
   397 			assert(0);
   398 		}
   399 		return m_Data[m_CurrentUsedSize - 1];
   400 	}
   401 
   402 	const T & back() const
   403 	{
   404 		if (m_CurrentUsedSize < 1)
   405 		{
   406 			assert(0);
   407 		}
   408 		return m_Data[m_CurrentUsedSize - 1];
   409 	}
   410 
   411 	iterator insert(iterator where, const T & value)
   412 	{
   413 		// validate iter
   414 		if (where < m_Data || where > (m_Data + m_CurrentUsedSize))
   415 			return iterator(0);
   416 
   417 		size_t ofs = where - begin();
   418 
   419 		++m_CurrentUsedSize;
   420 		if (!GrowIfNeeded())
   421 		{
   422 			--m_CurrentUsedSize;
   423 			return false;
   424 		}
   425 
   426 		where = begin() + ofs;
   427 
   428 		// Move subsequent entries
   429 		for (T *ptr = m_Data + m_CurrentUsedSize - 2; ptr >= where.base(); --ptr)
   430 			*(ptr + 1) = *ptr;
   431 
   432 		*where.base() = value;
   433 
   434 		return where;
   435 	}
   436 
   437 	iterator erase(iterator where)
   438 	{
   439 		// validate iter
   440 		if (where < m_Data || where >= (m_Data + m_CurrentUsedSize))
   441 			return iterator(0);
   442 
   443 		size_t ofs = where - begin();
   444 
   445 		if (m_CurrentUsedSize > 1)
   446 		{
   447 			// move
   448 			T *theend = m_Data + m_CurrentUsedSize;
   449 			for (T *ptr = where.base() + 1; ptr < theend; ++ptr)
   450 				*(ptr - 1) = *ptr;
   451 		}
   452 
   453 		--m_CurrentUsedSize;
   454 
   455 		FreeMemIfPossible();
   456 
   457 		return begin() + ofs;
   458 	}
   459 
   460 	void clear()
   461 	{
   462 		m_Size = 0;
   463 		m_CurrentUsedSize = 0;
   464 		if (m_Data)
   465 		{
   466 			delete [] m_Data;
   467 			m_Data = NULL;
   468 		}
   469 	}
   470 };
   471 };	//namespace SourceHook
   472 
   473 #endif // __CVECTOR_H__
   474