1.1 --- a/sourcehook/sh_stack.h Sun Oct 07 03:12:19 2007 +0000
1.2 +++ b/sourcehook/sh_stack.h Sun Oct 07 22:10:07 2007 +0000
1.3 @@ -12,17 +12,28 @@
1.4 #define __SH_STACK_H__
1.5
1.6 #include <stddef.h>
1.7 -
1.8 -#define SH_STACK_DEFAULT_SIZE 4
1.9 +#include "sh_vector.h"
1.10
1.11 namespace SourceHook
1.12 {
1.13 - // Vector
1.14 + // May _never_ reallocate used memory!
1.15 +
1.16 template <class T> class CStack
1.17 {
1.18 - T *m_Elements;
1.19 - size_t m_AllocatedSize;
1.20 + static const int SECTOR_SIZE = 16;
1.21 +
1.22 + CVector<T *> m_Sectors; // Stores sectors
1.23 +
1.24 size_t m_UsedSize;
1.25 +
1.26 + void clear()
1.27 + {
1.28 + for (CVector<T*>::iterator sect_iter = m_Sectors.begin(); sect_iter != m_Sectors.end(); ++sect_iter)
1.29 + {
1.30 + delete [] *sect_iter;
1.31 + }
1.32 + m_Sectors.clear();
1.33 + }
1.34 public:
1.35 friend class iterator;
1.36 class iterator
1.37 @@ -44,21 +55,21 @@
1.38
1.39 T &operator *()
1.40 {
1.41 - return m_pParent->m_Elements[m_Index];
1.42 + return m_pParent->at(m_Index);
1.43 }
1.44 const T &operator *() const
1.45 {
1.46 - return m_pParent->m_Elements[m_Index];
1.47 + return m_pParent->at(m_Index);
1.48 }
1.49
1.50 T * operator->()
1.51 {
1.52 - return m_pParent->m_Elements + m_Index;
1.53 + return &(m_pParent->at(m_Index));
1.54 }
1.55
1.56 const T * operator->() const
1.57 {
1.58 - return m_pParent->m_Elements + m_Index;
1.59 + return &(m_pParent->at(m_Index));
1.60 }
1.61
1.62 iterator & operator++() // preincrement
1.63 @@ -97,71 +108,76 @@
1.64 return !(*this == right);
1.65 }
1.66 };
1.67 - CStack() : m_Elements(new T[SH_STACK_DEFAULT_SIZE]),
1.68 - m_AllocatedSize(SH_STACK_DEFAULT_SIZE),
1.69 - m_UsedSize(0)
1.70 - {
1.71 - }
1.72 - CStack(size_t size) : m_Elements(new T[size]),
1.73 - m_AllocatedSize(size),
1.74 - m_UsedSize(0)
1.75 + CStack() : m_UsedSize(0)
1.76 {
1.77 }
1.78
1.79 - CStack(const CStack &other) : m_Elements(NULL),
1.80 - m_AllocatedSize(0),
1.81 - m_UsedSize(0)
1.82 + CStack(const CStack &other)
1.83 {
1.84 - reserve(other.m_AllocatedSize);
1.85 + for (CVector<T*>::iterator sect_iter = other.m_Sectors.begin();
1.86 + sect_iter != other.m_Sectors.end(); ++sect_iter)
1.87 + {
1.88 + m_Sectors.push_back(new T[SECTOR_SIZE]);
1.89 + for (size_t i = 0; i < SECTOR_SIZE; ++i)
1.90 + m_Sectors.back()[i] = (*sect_iter)[i];
1.91 + }
1.92 m_UsedSize = other.m_UsedSize;
1.93 - for (size_t i = 0; i < m_UsedSize; ++i)
1.94 - m_Elements[i] = other.m_Elements[i];
1.95 + }
1.96 +
1.97 + CStack & operator =(const CStack &other)
1.98 + {
1.99 + clear();
1.100 + for (CVector<T*>::iterator sect_iter = other.m_Sectors.begin();
1.101 + sect_iter != other.m_Sectors.end(); ++sect_iter)
1.102 + {
1.103 + m_Sectors.push_back(new T[SECTOR_SIZE]);
1.104 + for (size_t i = 0; i < SECTOR_SIZE; ++i)
1.105 + m_Sectors.back()[i] = (*sect_iter)[i];
1.106 + }
1.107 + m_UsedSize = other.m_UsedSize;
1.108 + return *this;
1.109 }
1.110
1.111 ~CStack()
1.112 {
1.113 - if (m_Elements)
1.114 - delete [] m_Elements;
1.115 + clear();
1.116 }
1.117 -
1.118 - void operator=(const CStack &other)
1.119 +
1.120 + T &at(size_t x)
1.121 {
1.122 - if (m_AllocatedSize < other.m_AllocatedSize)
1.123 - {
1.124 - if (m_Elements)
1.125 - delete [] m_Elements;
1.126 - m_Elements = new T[other.m_AllocatedSize];
1.127 - m_AllocatedSize = other.m_AllocatedSize;
1.128 - }
1.129 - m_UsedSize = other.m_UsedSize;
1.130 - for (size_t i = 0; i < m_UsedSize; ++i)
1.131 - m_Elements[i] = other.m_Elements[i];
1.132 + return m_Sectors[x / SECTOR_SIZE][x % SECTOR_SIZE];
1.133 + }
1.134 +
1.135 + const T &at(size_t x) const
1.136 + {
1.137 + return m_Sectors[x / SECTOR_SIZE][x % SECTOR_SIZE];
1.138 }
1.139
1.140 bool push(const T &val)
1.141 {
1.142 - if (m_UsedSize + 1 == m_AllocatedSize)
1.143 + if ((m_UsedSize / SECTOR_SIZE) >= m_Sectors.size())
1.144 {
1.145 - // zOHNOES! REALLOCATE!
1.146 - m_AllocatedSize *= 2;
1.147 - T *newElements = new T[m_AllocatedSize];
1.148 - if (!newElements)
1.149 - {
1.150 - m_AllocatedSize /= 2;
1.151 - return false;
1.152 - }
1.153 - if (m_Elements)
1.154 - {
1.155 - for (size_t i = 0; i < m_UsedSize; ++i)
1.156 - newElements[i] = m_Elements[i];
1.157 - delete [] m_Elements;
1.158 - }
1.159 - m_Elements = newElements;
1.160 + // New sector
1.161 + m_Sectors.push_back(new T[SECTOR_SIZE]);
1.162 }
1.163 - m_Elements[m_UsedSize++] = val;
1.164 +
1.165 + at(m_UsedSize) = val;
1.166 +
1.167 + ++m_UsedSize;
1.168 return true;
1.169 }
1.170
1.171 + T *make_next()
1.172 + {
1.173 + if ((m_UsedSize / SECTOR_SIZE) >= m_Sectors.size())
1.174 + {
1.175 + // New sector
1.176 + m_Sectors.push_back(new T[SECTOR_SIZE]);
1.177 + }
1.178 +
1.179 + return &(at(m_UsedSize++));
1.180 + }
1.181 +
1.182 void pop()
1.183 {
1.184 --m_UsedSize;
1.185 @@ -174,22 +190,22 @@
1.186
1.187 T &front()
1.188 {
1.189 - return m_Elements[m_UsedSize - 1];
1.190 + return at(m_UsedSize-1);
1.191 }
1.192
1.193 const T &front() const
1.194 {
1.195 - return m_Elements[m_UsedSize - 1];
1.196 + return at(m_UsedSize-1);
1.197 }
1.198
1.199 T &second()
1.200 {
1.201 - return m_Elements[m_UsedSize - 2];
1.202 + return at(m_UsedSize-2);
1.203 }
1.204
1.205 const T &second() const
1.206 {
1.207 - return m_Elements[m_UsedSize - 2];
1.208 + return at(m_UsedSize-2);
1.209 }
1.210
1.211 iterator begin()
1.212 @@ -205,32 +221,10 @@
1.213 {
1.214 return m_UsedSize;
1.215 }
1.216 - size_t capacity()
1.217 - {
1.218 - return m_AllocatedSize;
1.219 - }
1.220 bool empty()
1.221 {
1.222 return m_UsedSize == 0 ? true : false;
1.223 }
1.224 - bool reserve(size_t size)
1.225 - {
1.226 - if (size > m_AllocatedSize)
1.227 - {
1.228 - T *newElements = new T[size];
1.229 - if (!newElements)
1.230 - return false;
1.231 - if (m_Elements)
1.232 - {
1.233 - for (size_t i = 0; i < m_UsedSize; ++i)
1.234 - newElements[i] = m_Elements[i];
1.235 - delete [] m_Elements;
1.236 - }
1.237 - m_Elements = newElements;
1.238 - m_AllocatedSize = size;
1.239 - }
1.240 - return true;
1.241 - }
1.242 };
1.243 }; //namespace SourceHook
1.244