summaryrefslogtreecommitdiff
path: root/third_party/agg23/agg_array.h
diff options
context:
space:
mode:
authorTom Sepez <tsepez@chromium.org>2015-06-17 10:01:00 -0700
committerTom Sepez <tsepez@chromium.org>2015-06-17 10:01:00 -0700
commitb7d358b498800e4c240d381fa6f098af17a4d95b (patch)
treeaa0d8677af748caf9881ecd011af2b00af925188 /third_party/agg23/agg_array.h
parent9555022ee550ee97415a86957686cc28716c4dee (diff)
downloadpdfium-b7d358b498800e4c240d381fa6f098af17a4d95b.tar.xz
Merge to XFA: Separate agg-authored code from fx-authored code.
Original Review URL: https://codereview.chromium.org/1152743007. BUG=pdfium:166 R=brucedawson@chromium.org, thestig@chromium.org TBR=brucedawson@chromium.org, thestig@chromium.org Review URL: https://codereview.chromium.org/1186423003.
Diffstat (limited to 'third_party/agg23/agg_array.h')
-rw-r--r--third_party/agg23/agg_array.h506
1 files changed, 506 insertions, 0 deletions
diff --git a/third_party/agg23/agg_array.h b/third_party/agg23/agg_array.h
new file mode 100644
index 0000000000..810eb4ef22
--- /dev/null
+++ b/third_party/agg23/agg_array.h
@@ -0,0 +1,506 @@
+
+//----------------------------------------------------------------------------
+// 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"
+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