//---------------------------------------------------------------------------- // Anti-Grain Geometry - Version 2.3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) // // Permission to copy, use, modify, sell and distribute this software // is granted provided this copyright notice appears in all copies. // This software is provided "as is" without express or implied // warranty, and with no claim as to its suitability for any purpose. // //---------------------------------------------------------------------------- // Contact: mcseem@antigrain.com // mcseemagg@yahoo.com // http://www.antigrain.com //---------------------------------------------------------------------------- #ifndef AGG_ARRAY_INCLUDED #define AGG_ARRAY_INCLUDED #include "agg_basics.h" #include "core/include/fxcrt/fx_memory.h" // For FXSYS_* macros. namespace agg { template <class T> class pod_array { public: typedef T value_type; ~pod_array() { FX_Free(m_array); } pod_array() : m_size(0), m_capacity(0), m_array(0) {} pod_array(unsigned cap, unsigned extra_tail = 0); pod_array(const pod_array<T>&); const pod_array<T>& operator = (const pod_array<T>&); void capacity(unsigned cap, unsigned extra_tail = 0); unsigned capacity() const { return m_capacity; } void allocate(unsigned size, unsigned extra_tail = 0); void resize(unsigned new_size); void zero() { FXSYS_memset(m_array, 0, sizeof(T) * m_size); } void add(const T& v) { m_array[m_size++] = v; } void inc_size(unsigned size) { m_size += size; } unsigned size() const { return m_size; } unsigned byte_size() const { return m_size * sizeof(T); } const T& operator [] (unsigned i) const { return m_array[i]; } T& operator [] (unsigned i) { return m_array[i]; } const T& at(unsigned i) const { return m_array[i]; } T& at(unsigned i) { return m_array[i]; } T value_at(unsigned i) const { return m_array[i]; } const T* data() const { return m_array; } T* data() { return m_array; } void remove_all() { m_size = 0; } void cut_at(unsigned num) { if(num < m_size) { m_size = num; } } private: unsigned m_size; unsigned m_capacity; T* m_array; }; template<class T> void pod_array<T>::capacity(unsigned cap, unsigned extra_tail) { m_size = 0; unsigned full_cap = cap + extra_tail; if(full_cap < cap) { FX_Free(m_array); m_array = 0; m_capacity = 0; } else if(full_cap > m_capacity) { FX_Free(m_array); m_array = FX_Alloc(T, full_cap); m_capacity = full_cap; } } template<class T> void pod_array<T>::allocate(unsigned size, unsigned extra_tail) { capacity(size, extra_tail); m_size = size; } template<class T> void pod_array<T>::resize(unsigned new_size) { if(new_size > m_size) { if(new_size > m_capacity) { T* data = FX_Alloc(T, new_size); FXSYS_memcpy(data, m_array, m_size * sizeof(T)); FX_Free(m_array); m_array = data; } } else { m_size = new_size; } } template<class T> pod_array<T>::pod_array(unsigned cap, unsigned extra_tail) : m_size(0), m_capacity(cap + extra_tail), m_array(FX_Alloc(T, m_capacity)) {} template<class T> pod_array<T>::pod_array(const pod_array<T>& v) : m_size(v.m_size), m_capacity(v.m_capacity), m_array(v.m_capacity ? FX_Alloc(T, v.m_capacity) : 0) { FXSYS_memcpy(m_array, v.m_array, sizeof(T) * v.m_size); } template<class T> const pod_array<T>& pod_array<T>::operator = (const pod_array<T>&v) { allocate(v.m_size); if(v.m_size) { FXSYS_memcpy(m_array, v.m_array, sizeof(T) * v.m_size); } return *this; } template<class T, unsigned S = 6> class pod_deque { public: enum block_scale_e { block_shift = S, block_size = 1 << block_shift, block_mask = block_size - 1 }; typedef T value_type; ~pod_deque(); pod_deque(); pod_deque(unsigned block_ptr_inc); pod_deque(const pod_deque<T, S>& v); const pod_deque<T, S>& operator = (const pod_deque<T, S>& v); void remove_all() { m_size = 0; } void free_all() { free_tail(0); } void free_tail(unsigned size); void add(const T& val); void modify_last(const T& val); void remove_last(); int allocate_continuous_block(unsigned num_elements); void add_array(const T* ptr, unsigned num_elem) { while(num_elem--) { add(*ptr++); } } template<class DataAccessor> void add_data(DataAccessor& data) { while(data.size()) { add(*data); ++data; } } void cut_at(unsigned size) { if(size < m_size) { m_size = size; } } unsigned size() const { return m_size; } const T& operator [] (unsigned i) const { return m_blocks[i >> block_shift][i & block_mask]; } T& operator [] (unsigned i) { return m_blocks[i >> block_shift][i & block_mask]; } const T& at(unsigned i) const { return m_blocks[i >> block_shift][i & block_mask]; } T& at(unsigned i) { return m_blocks[i >> block_shift][i & block_mask]; } T value_at(unsigned i) const { return m_blocks[i >> block_shift][i & block_mask]; } const T& curr(unsigned idx) const { return (*this)[idx]; } T& curr(unsigned idx) { return (*this)[idx]; } const T& prev(unsigned idx) const { return (*this)[(idx + m_size - 1) % m_size]; } T& prev(unsigned idx) { return (*this)[(idx + m_size - 1) % m_size]; } const T& next(unsigned idx) const { return (*this)[(idx + 1) % m_size]; } T& next(unsigned idx) { return (*this)[(idx + 1) % m_size]; } const T& last() const { return (*this)[m_size - 1]; } T& last() { return (*this)[m_size - 1]; } unsigned byte_size() const; const T* block(unsigned nb) const { return m_blocks[nb]; } public: void allocate_block(unsigned nb); T* data_ptr(); unsigned m_size; unsigned m_num_blocks; unsigned m_max_blocks; T** m_blocks; unsigned m_block_ptr_inc; }; template<class T, unsigned S> pod_deque<T, S>::~pod_deque() { if(m_num_blocks) { T** blk = m_blocks + m_num_blocks - 1; while(m_num_blocks--) { FX_Free(*blk); --blk; } FX_Free(m_blocks); } } template<class T, unsigned S> void pod_deque<T, S>::free_tail(unsigned size) { if(size < m_size) { unsigned nb = (size + block_mask) >> block_shift; while(m_num_blocks > nb) { FX_Free(m_blocks[--m_num_blocks]); } m_size = size; } } template<class T, unsigned S> pod_deque<T, S>::pod_deque() : m_size(0), m_num_blocks(0), m_max_blocks(0), m_blocks(0), m_block_ptr_inc(block_size) { } template<class T, unsigned S> pod_deque<T, S>::pod_deque(unsigned block_ptr_inc) : m_size(0), m_num_blocks(0), m_max_blocks(0), m_blocks(0), m_block_ptr_inc(block_ptr_inc) { } template<class T, unsigned S> pod_deque<T, S>::pod_deque(const pod_deque<T, S>& v) : m_size(v.m_size), m_num_blocks(v.m_num_blocks), m_max_blocks(v.m_max_blocks), m_blocks(v.m_max_blocks ? FX_Alloc(T*, v.m_max_blocks) : 0), m_block_ptr_inc(v.m_block_ptr_inc) { unsigned i; for(i = 0; i < v.m_num_blocks; ++i) { m_blocks[i] = FX_Alloc(T, block_size); FXSYS_memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); } } template<class T, unsigned S> const pod_deque<T, S>& pod_deque<T, S>::operator = (const pod_deque<T, S>& v) { unsigned i; for(i = m_num_blocks; i < v.m_num_blocks; ++i) { allocate_block(i); } for(i = 0; i < v.m_num_blocks; ++i) { FXSYS_memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); } m_size = v.m_size; return *this; } template<class T, unsigned S> void pod_deque<T, S>::allocate_block(unsigned nb) { if(nb >= m_max_blocks) { T** new_blocks = FX_Alloc(T*, m_max_blocks + m_block_ptr_inc); if(m_blocks) { FXSYS_memcpy(new_blocks, m_blocks, m_num_blocks * sizeof(T*)); FX_Free(m_blocks); } m_blocks = new_blocks; m_max_blocks += m_block_ptr_inc; } m_blocks[nb] = FX_Alloc(T, block_size); m_num_blocks++; } template<class T, unsigned S> inline T* pod_deque<T, S>::data_ptr() { unsigned nb = m_size >> block_shift; if(nb >= m_num_blocks) { allocate_block(nb); } return m_blocks[nb] + (m_size & block_mask); } template<class T, unsigned S> inline void pod_deque<T, S>::add(const T& val) { *data_ptr() = val; ++m_size; } template<class T, unsigned S> inline void pod_deque<T, S>::remove_last() { if(m_size) { --m_size; } } template<class T, unsigned S> void pod_deque<T, S>::modify_last(const T& val) { remove_last(); add(val); } template<class T, unsigned S> int pod_deque<T, S>::allocate_continuous_block(unsigned num_elements) { if(num_elements < block_size) { data_ptr(); unsigned rest = block_size - (m_size & block_mask); unsigned index; if(num_elements <= rest) { index = m_size; m_size += num_elements; return index; } m_size += rest; data_ptr(); index = m_size; m_size += num_elements; return index; } return -1; } template<class T, unsigned S> unsigned pod_deque<T, S>::byte_size() const { return m_size * sizeof(T); } class pod_allocator { public: void remove_all() { if(m_num_blocks) { int8u** blk = m_blocks + m_num_blocks - 1; while(m_num_blocks--) { FX_Free(*blk); --blk; } FX_Free(m_blocks); } m_num_blocks = 0; m_max_blocks = 0; m_blocks = 0; m_buf_ptr = 0; m_rest = 0; } ~pod_allocator() { remove_all(); } pod_allocator(unsigned block_size, unsigned block_ptr_inc = 256 - 8) : m_block_size(block_size), m_block_ptr_inc(block_ptr_inc), m_num_blocks(0), m_max_blocks(0), m_blocks(0), m_buf_ptr(0), m_rest(0) { } int8u* allocate(unsigned size, unsigned alignment = 1) { if(size == 0) { return 0; } if(size <= m_rest) { int8u* ptr = m_buf_ptr; if(alignment > 1) { unsigned align = (alignment - unsigned((size_t)ptr) % alignment) % alignment; size += align; ptr += align; if(size <= m_rest) { m_rest -= size; m_buf_ptr += size; return ptr; } allocate_block(size); return allocate(size - align, alignment); } m_rest -= size; m_buf_ptr += size; return ptr; } allocate_block(size + alignment - 1); return allocate(size, alignment); } private: void allocate_block(unsigned size) { if(size < m_block_size) { size = m_block_size; } if(m_num_blocks >= m_max_blocks) { int8u** new_blocks = FX_Alloc(int8u*, m_max_blocks + m_block_ptr_inc); if(m_blocks) { FXSYS_memcpy(new_blocks, m_blocks, m_num_blocks * sizeof(int8u*)); FX_Free(m_blocks); } m_blocks = new_blocks; m_max_blocks += m_block_ptr_inc; } m_blocks[m_num_blocks] = m_buf_ptr = FX_Alloc(int8u, size); m_num_blocks++; m_rest = size; } unsigned m_block_size; unsigned m_block_ptr_inc; unsigned m_num_blocks; unsigned m_max_blocks; int8u** m_blocks; int8u* m_buf_ptr; unsigned m_rest; }; enum quick_sort_threshold_e { quick_sort_threshold = 9 }; template<class T> inline void swap_elements(T& a, T& b) { T temp = a; a = b; b = temp; } } #endif