1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Anti-Grain Geometry - Version 2.3 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Permission to copy, use, modify, sell and distribute this software 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// is granted provided this copyright notice appears in all copies. 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// This software is provided "as is" without express or implied 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// warranty, and with no claim as to its suitability for any purpose. 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// Contact: mcseem@antigrain.com 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// mcseemagg@yahoo.com 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov// http://www.antigrain.com 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov//---------------------------------------------------------------------------- 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifndef AGG_ARRAY_INCLUDED 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define AGG_ARRAY_INCLUDED 18ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "agg_basics.h" 204d3acf4ec42bf6e838f9060103aff98fbf170794Philip P. Moltmann#include "core/fxcrt/fx_memory.h" // For FXSYS_* macros. 21ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmann 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovnamespace agg 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 24ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmanntemplate <class T> 25ac3d58cff7c80b0ef56bf55130d91da17cbaa3c4Philip P. Moltmannclass pod_array { 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpublic: 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov typedef T value_type; 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ~pod_array() 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_array); 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_array() : m_size(0), m_capacity(0), m_array(0) {} 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_array(unsigned cap, unsigned extra_tail = 0); 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_array(const pod_array<T>&); 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const pod_array<T>& operator = (const pod_array<T>&); 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void capacity(unsigned cap, unsigned extra_tail = 0); 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned capacity() const 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_capacity; 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void allocate(unsigned size, unsigned extra_tail = 0); 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void resize(unsigned new_size); 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void zero() 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memset(m_array, 0, sizeof(T) * m_size); 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void add(const T& v) 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_array[m_size++] = v; 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void inc_size(unsigned size) 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size += size; 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned size() const 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_size; 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned byte_size() const 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_size * sizeof(T); 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& operator [] (unsigned i) const 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array[i]; 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& operator [] (unsigned i) 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array[i]; 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& at(unsigned i) const 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array[i]; 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& at(unsigned i) 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array[i]; 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T value_at(unsigned i) const 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array[i]; 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T* data() const 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array; 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T* data() 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_array; 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void remove_all() 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = 0; 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void cut_at(unsigned num) 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(num < m_size) { 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = num; 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovprivate: 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_size; 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_capacity; 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T* m_array; 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}; 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid pod_array<T>::capacity(unsigned cap, unsigned extra_tail) 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = 0; 110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned full_cap = cap + extra_tail; 111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(full_cap < cap) { 112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_array); 113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_array = 0; 114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_capacity = 0; 115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if(full_cap > m_capacity) { 116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_array); 117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_array = FX_Alloc(T, full_cap); 118e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganov m_capacity = full_cap; 119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> 122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid pod_array<T>::allocate(unsigned size, unsigned extra_tail) 123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov capacity(size, extra_tail); 125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = size; 126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> 128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid pod_array<T>::resize(unsigned new_size) 129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(new_size > m_size) { 131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(new_size > m_capacity) { 132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T* data = FX_Alloc(T, new_size); 133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(data, m_array, m_size * sizeof(T)); 134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_array); 135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_array = data; 136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = new_size; 139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> pod_array<T>::pod_array(unsigned cap, unsigned extra_tail) : 142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size(0), m_capacity(cap + extra_tail), m_array(FX_Alloc(T, m_capacity)) {} 143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> pod_array<T>::pod_array(const pod_array<T>& v) : 144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size(v.m_size), 145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_capacity(v.m_capacity), 146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_array(v.m_capacity ? FX_Alloc(T, v.m_capacity) : 0) 147ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(m_array, v.m_array, sizeof(T) * v.m_size); 149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> const pod_array<T>& 151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpod_array<T>::operator = (const pod_array<T>&v) 152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov allocate(v.m_size); 154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(v.m_size) { 155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(m_array, v.m_array, sizeof(T) * v.m_size); 156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return *this; 158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 159e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovtemplate<class T, unsigned S = 6> class pod_deque 160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpublic: 162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov enum block_scale_e { 163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov block_shift = S, 164ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov block_size = 1 << block_shift, 165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov block_mask = block_size - 1 166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }; 167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov typedef T value_type; 168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ~pod_deque(); 169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_deque(); 170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_deque(unsigned block_ptr_inc); 171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_deque(const pod_deque<T, S>& v); 172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const pod_deque<T, S>& operator = (const pod_deque<T, S>& v); 173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void remove_all() 174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = 0; 176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void free_all() 178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov free_tail(0); 180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void free_tail(unsigned size); 182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void add(const T& val); 183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void modify_last(const T& val); 184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void remove_last(); 185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int allocate_continuous_block(unsigned num_elements); 186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void add_array(const T* ptr, unsigned num_elem) 187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while(num_elem--) { 189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov add(*ptr++); 190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov template<class DataAccessor> void add_data(DataAccessor& data) 193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while(data.size()) { 195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov add(*data); 196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ++data; 197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void cut_at(unsigned size) 200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(size < m_size) { 202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = size; 203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned size() const 206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_size; 208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& operator [] (unsigned i) const 210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[i >> block_shift][i & block_mask]; 212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& operator [] (unsigned i) 214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[i >> block_shift][i & block_mask]; 216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& at(unsigned i) const 218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[i >> block_shift][i & block_mask]; 220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& at(unsigned i) 222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[i >> block_shift][i & block_mask]; 224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T value_at(unsigned i) const 226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 227ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[i >> block_shift][i & block_mask]; 228ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 229ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& curr(unsigned idx) const 230ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 231ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[idx]; 232ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 233ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& curr(unsigned idx) 234ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 235ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[idx]; 236ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 237ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& prev(unsigned idx) const 238ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 239ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[(idx + m_size - 1) % m_size]; 240ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 241ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& prev(unsigned idx) 242ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 243ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[(idx + m_size - 1) % m_size]; 244ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 245ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& next(unsigned idx) const 246ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 247ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[(idx + 1) % m_size]; 248ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 249ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& next(unsigned idx) 250ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 251ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[(idx + 1) % m_size]; 252ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 253ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T& last() const 254ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 255ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[m_size - 1]; 256ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 257ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T& last() 258ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 259ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (*this)[m_size - 1]; 260ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 261ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned byte_size() const; 262ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const T* block(unsigned nb) const 263ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 264ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[nb]; 265ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 266ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpublic: 267ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void allocate_block(unsigned nb); 268ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T* data_ptr(); 269ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_size; 270ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_num_blocks; 271ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_max_blocks; 272ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T** m_blocks; 273ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_block_ptr_inc; 274ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}; 275ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> pod_deque<T, S>::~pod_deque() 276ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 277ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_num_blocks) { 278ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T** blk = m_blocks + m_num_blocks - 1; 279ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while(m_num_blocks--) { 280ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(*blk); 281ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov --blk; 282ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 283ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_blocks); 284ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 285ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 286ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 287ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid pod_deque<T, S>::free_tail(unsigned size) 288ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 289ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(size < m_size) { 290ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned nb = (size + block_mask) >> block_shift; 291ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while(m_num_blocks > nb) { 292ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_blocks[--m_num_blocks]); 293ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 294ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = size; 295ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 296ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 297ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> pod_deque<T, S>::pod_deque() : 298ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size(0), 299ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks(0), 300ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks(0), 301ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks(0), 302ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_block_ptr_inc(block_size) 303ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 304ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 305ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 306ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpod_deque<T, S>::pod_deque(unsigned block_ptr_inc) : 307ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size(0), 308ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks(0), 309ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks(0), 310ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks(0), 311ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_block_ptr_inc(block_ptr_inc) 312ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 313ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 314ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 315ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpod_deque<T, S>::pod_deque(const pod_deque<T, S>& v) : 316ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size(v.m_size), 317ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks(v.m_num_blocks), 318ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks(v.m_max_blocks), 319ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks(v.m_max_blocks ? FX_Alloc(T*, v.m_max_blocks) : 0), 320ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_block_ptr_inc(v.m_block_ptr_inc) 321ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 322ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned i; 323ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for(i = 0; i < v.m_num_blocks; ++i) { 324ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks[i] = FX_Alloc(T, block_size); 325ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); 326ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 327ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 328ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 329ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovconst pod_deque<T, S>& pod_deque<T, S>::operator = (const pod_deque<T, S>& v) 330ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 331ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned i; 332ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for(i = m_num_blocks; i < v.m_num_blocks; ++i) { 333ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov allocate_block(i); 334ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 335ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for(i = 0; i < v.m_num_blocks; ++i) { 336ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); 337ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 338ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size = v.m_size; 339ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return *this; 340ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 341ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 342ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid pod_deque<T, S>::allocate_block(unsigned nb) 343ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 344ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(nb >= m_max_blocks) { 345ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T** new_blocks = FX_Alloc(T*, m_max_blocks + m_block_ptr_inc); 346ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_blocks) { 347ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(new_blocks, 348ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks, 349ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks * sizeof(T*)); 350ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_blocks); 351ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 352ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks = new_blocks; 353ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks += m_block_ptr_inc; 354ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 355ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks[nb] = FX_Alloc(T, block_size); 356ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks++; 357ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 358ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 359ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovinline T* pod_deque<T, S>::data_ptr() 360ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 361ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned nb = m_size >> block_shift; 362ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(nb >= m_num_blocks) { 363ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov allocate_block(nb); 364ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 365ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_blocks[nb] + (m_size & block_mask); 366ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 367ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 368ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovinline void pod_deque<T, S>::add(const T& val) 369ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 370ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *data_ptr() = val; 371ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ++m_size; 372ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 373ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 374ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovinline void pod_deque<T, S>::remove_last() 375ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 376ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_size) { 377ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov --m_size; 378ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 379ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 380ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 381ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid pod_deque<T, S>::modify_last(const T& val) 382ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 383ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov remove_last(); 384ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov add(val); 385ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 386ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 387ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovint pod_deque<T, S>::allocate_continuous_block(unsigned num_elements) 388ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 389ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(num_elements < block_size) { 390ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov data_ptr(); 391ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned rest = block_size - (m_size & block_mask); 392ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned index; 393ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(num_elements <= rest) { 394ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov index = m_size; 395ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size += num_elements; 396ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return index; 397ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 398ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size += rest; 399ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov data_ptr(); 400ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov index = m_size; 401ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_size += num_elements; 402ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return index; 403ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 404ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return -1; 405ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 406ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T, unsigned S> 407ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovunsigned pod_deque<T, S>::byte_size() const 408ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 409ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return m_size * sizeof(T); 410ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 411e6986e1e8d4a57987f47c215490cb080a65ee29aSvet Ganovclass pod_allocator 412ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 413ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovpublic: 414ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void remove_all() 415ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 416ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_num_blocks) { 417ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int8u** blk = m_blocks + m_num_blocks - 1; 418ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while(m_num_blocks--) { 419ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(*blk); 420ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov --blk; 421ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 422ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_blocks); 423ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 424ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks = 0; 425ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks = 0; 426ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks = 0; 427ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_buf_ptr = 0; 428ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_rest = 0; 429ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 430ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ~pod_allocator() 431ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 432ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov remove_all(); 433ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 434ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pod_allocator(unsigned block_size, unsigned block_ptr_inc = 256 - 8) : 435ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_block_size(block_size), 436ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_block_ptr_inc(block_ptr_inc), 437ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks(0), 438ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks(0), 439ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks(0), 440ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_buf_ptr(0), 441ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_rest(0) 442ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 443ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 444ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int8u* allocate(unsigned size, unsigned alignment = 1) 445ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 446ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(size == 0) { 447ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return 0; 448ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 449ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(size <= m_rest) { 450ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int8u* ptr = m_buf_ptr; 451ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(alignment > 1) { 452ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned align = (alignment - unsigned((size_t)ptr) % alignment) % alignment; 453ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov size += align; 454ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ptr += align; 455ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(size <= m_rest) { 456ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_rest -= size; 457ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_buf_ptr += size; 458ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return ptr; 459ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 460ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov allocate_block(size); 461ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return allocate(size - align, alignment); 462ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 463ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_rest -= size; 464ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_buf_ptr += size; 465ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return ptr; 466ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 467ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov allocate_block(size + alignment - 1); 468ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return allocate(size, alignment); 469ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 470ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovprivate: 471ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov void allocate_block(unsigned size) 472ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 473ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(size < m_block_size) { 474ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov size = m_block_size; 475ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 476ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_num_blocks >= m_max_blocks) { 477ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int8u** new_blocks = FX_Alloc(int8u*, m_max_blocks + m_block_ptr_inc); 478ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if(m_blocks) { 479ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FXSYS_memcpy(new_blocks, 480ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks, 481ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks * sizeof(int8u*)); 482ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FX_Free(m_blocks); 483ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 484ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks = new_blocks; 485ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_max_blocks += m_block_ptr_inc; 486ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 487ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_blocks[m_num_blocks] = m_buf_ptr = FX_Alloc(int8u, size); 488ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_num_blocks++; 489ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m_rest = size; 490ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 491ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_block_size; 492ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_block_ptr_inc; 493ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_num_blocks; 494ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_max_blocks; 495ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int8u** m_blocks; 496ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int8u* m_buf_ptr; 497ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned m_rest; 498ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}; 499ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovenum quick_sort_threshold_e { 500ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov quick_sort_threshold = 9 501ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}; 502ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovtemplate<class T> inline void swap_elements(T& a, T& b) 503ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 504ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov T temp = a; 505ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov a = b; 506ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov b = temp; 507ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 508ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 509ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 510