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