← Back to branch summary

~kalon33/corsix-th/master

« back to all changes in this revision

Viewing changes to agg/include/agg_array.h

  • Committer: corsixth.bot at gmail
  • Date: 2014-03-31 23:30:23 UTC
  • Revision ID: svn-v4:c39591fa-788f-11de-a72b-d90af8dea425:trunk:2687
Remove trailing whitespaces in .h, .cpp, .c and .lua files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
agg/include/agg_array.h
2
2
// Anti-Grain Geometry - Version 2.4
3
3
// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
4
4
//
5
 
// Permission to copy, use, modify, sell and distribute this software 
6
 
// is granted provided this copyright notice appears in all copies. 
 
5
// Permission to copy, use, modify, sell and distribute this software
 
6
// is granted provided this copyright notice appears in all copies.
7
7
// This software is provided "as is" without express or implied
8
8
// warranty, and with no claim as to its suitability for any purpose.
9
9
//
27
27
    {
28
28
    public:
29
29
        typedef T value_type;
30
 
        pod_array_adaptor(T* array, unsigned size) : 
 
30
        pod_array_adaptor(T* array, unsigned size) :
31
31
            m_array(array), m_size(size) {}
32
32
 
33
33
        unsigned size() const { return m_size; }
88
88
        void add(const T& v)         { m_array[m_size++] = v; }
89
89
        void push_back(const T& v)   { m_array[m_size++] = v; }
90
90
        void inc_size(unsigned size) { m_size += size; }
91
 
        
 
91
 
92
92
        unsigned size() const { return m_size; }
93
93
        const T& operator [] (unsigned i) const { return m_array[i]; }
94
94
              T& operator [] (unsigned i)       { return m_array[i]; }
112
112
        ~pod_array() { pod_allocator<T>::deallocate(m_array, m_size); }
113
113
        pod_array() : m_array(0), m_size(0) {}
114
114
 
115
 
        pod_array(unsigned size) : 
116
 
            m_array(pod_allocator<T>::allocate(size)), 
117
 
            m_size(size) 
 
115
        pod_array(unsigned size) :
 
116
            m_array(pod_allocator<T>::allocate(size)),
 
117
            m_size(size)
118
118
        {}
119
119
 
120
 
        pod_array(const self_type& v) : 
121
 
            m_array(pod_allocator<T>::allocate(v.m_size)), 
122
 
            m_size(v.m_size) 
 
120
        pod_array(const self_type& v) :
 
121
            m_array(pod_allocator<T>::allocate(v.m_size)),
 
122
            m_size(v.m_size)
123
123
        {
124
124
            memcpy(m_array, v.m_array, sizeof(T) * m_size);
125
125
        }
176
176
        void capacity(unsigned cap, unsigned extra_tail=0);
177
177
        unsigned capacity() const { return m_capacity; }
178
178
 
179
 
        // Allocate n elements. All data is lost, 
180
 
        // but elements can be accessed in range 0...size-1. 
 
179
        // Allocate n elements. All data is lost,
 
180
        // but elements can be accessed in range 0...size-1.
181
181
        void allocate(unsigned size, unsigned extra_tail=0);
182
182
 
183
183
        // Resize keeping the content.
216
216
    };
217
217
 
218
218
    //------------------------------------------------------------------------
219
 
    template<class T> 
 
219
    template<class T>
220
220
    void pod_vector<T>::capacity(unsigned cap, unsigned extra_tail)
221
221
    {
222
222
        m_size = 0;
229
229
    }
230
230
 
231
231
    //------------------------------------------------------------------------
232
 
    template<class T> 
 
232
    template<class T>
233
233
    void pod_vector<T>::allocate(unsigned size, unsigned extra_tail)
234
234
    {
235
235
        capacity(size, extra_tail);
238
238
 
239
239
 
240
240
    //------------------------------------------------------------------------
241
 
    template<class T> 
 
241
    template<class T>
242
242
    void pod_vector<T>::resize(unsigned new_size)
243
243
    {
244
244
        if(new_size > m_size)
259
259
 
260
260
    //------------------------------------------------------------------------
261
261
    template<class T> pod_vector<T>::pod_vector(unsigned cap, unsigned extra_tail) :
262
 
        m_size(0), 
263
 
        m_capacity(cap + extra_tail), 
 
262
        m_size(0),
 
263
        m_capacity(cap + extra_tail),
264
264
        m_array(pod_allocator<T>::allocate(m_capacity)) {}
265
265
 
266
266
    //------------------------------------------------------------------------
273
273
    }
274
274
 
275
275
    //------------------------------------------------------------------------
276
 
    template<class T> const pod_vector<T>& 
 
276
    template<class T> const pod_vector<T>&
277
277
    pod_vector<T>::operator = (const pod_vector<T>&v)
278
278
    {
279
279
        allocate(v.m_size);
283
283
 
284
284
    //------------------------------------------------------------------------
285
285
    template<class T> void pod_vector<T>::serialize(int8u* ptr) const
286
 
    { 
287
 
        if(m_size) memcpy(ptr, m_array, m_size * sizeof(T)); 
 
286
    {
 
287
        if(m_size) memcpy(ptr, m_array, m_size * sizeof(T));
288
288
    }
289
289
 
290
290
    //------------------------------------------------------------------------
291
 
    template<class T> 
 
291
    template<class T>
292
292
    void pod_vector<T>::deserialize(const int8u* data, unsigned byte_size)
293
293
    {
294
294
        byte_size /= sizeof(T);
297
297
    }
298
298
 
299
299
    //------------------------------------------------------------------------
300
 
    template<class T> 
 
300
    template<class T>
301
301
    void pod_vector<T>::insert_at(unsigned pos, const T& val)
302
302
    {
303
 
        if(pos >= m_size) 
 
303
        if(pos >= m_size)
304
304
        {
305
305
            m_array[m_size] = val;
306
306
        }
314
314
 
315
315
    //---------------------------------------------------------------pod_bvector
316
316
    // A simple class template to store Plain Old Data, similar to std::deque
317
 
    // It doesn't reallocate memory but instead, uses blocks of data of size 
318
 
    // of (1 << S), that is, power of two. The data is NOT contiguous in memory, 
 
317
    // It doesn't reallocate memory but instead, uses blocks of data of size
 
318
    // of (1 << S), that is, power of two. The data is NOT contiguous in memory,
319
319
    // so the only valid access method is operator [] or curr(), prev(), next()
320
 
    // 
321
 
    // There reallocs occure only when the pool of pointers to blocks needs 
322
 
    // to be extended (it happens very rarely). You can control the value 
 
320
    //
 
321
    // There reallocs occure only when the pool of pointers to blocks needs
 
322
    // to be extended (it happens very rarely). You can control the value
323
323
    // of increment to reallocate the pointer buffer. See the second constructor.
324
324
    // By default, the incremeent value equals (1 << S), i.e., the block size.
325
325
    //------------------------------------------------------------------------
327
327
    {
328
328
    public:
329
329
        enum block_scale_e
330
 
        {   
 
330
        {
331
331
            block_shift = S,
332
332
            block_size  = 1 << block_shift,
333
333
            block_mask  = block_size - 1
389
389
        }
390
390
 
391
391
        const T& at(unsigned i) const
392
 
        { 
 
392
        {
393
393
            return m_blocks[i >> block_shift][i & block_mask];
394
394
        }
395
395
 
396
 
        T& at(unsigned i) 
397
 
        { 
 
396
        T& at(unsigned i)
 
397
        {
398
398
            return m_blocks[i >> block_shift][i & block_mask];
399
399
        }
400
400
 
401
401
        T value_at(unsigned i) const
402
 
        { 
 
402
        {
403
403
            return m_blocks[i >> block_shift][i & block_mask];
404
404
        }
405
405
 
446
446
        unsigned byte_size() const;
447
447
        void serialize(int8u* ptr) const;
448
448
        void deserialize(const int8u* data, unsigned byte_size);
449
 
        void deserialize(unsigned start, const T& empty_val, 
 
449
        void deserialize(unsigned start, const T& empty_val,
450
450
                         const int8u* data, unsigned byte_size);
451
451
 
452
 
        template<class ByteAccessor> 
 
452
        template<class ByteAccessor>
453
453
        void deserialize(ByteAccessor data)
454
454
        {
455
455
            remove_all();
527
527
 
528
528
 
529
529
    //------------------------------------------------------------------------
530
 
    template<class T, unsigned S> 
 
530
    template<class T, unsigned S>
531
531
    void pod_bvector<T, S>::free_tail(unsigned size)
532
532
    {
533
533
        if(size < m_size)
560
560
 
561
561
 
562
562
    //------------------------------------------------------------------------
563
 
    template<class T, unsigned S> 
 
563
    template<class T, unsigned S>
564
564
    pod_bvector<T, S>::pod_bvector(unsigned block_ptr_inc) :
565
565
        m_size(0),
566
566
        m_num_blocks(0),
572
572
 
573
573
 
574
574
    //------------------------------------------------------------------------
575
 
    template<class T, unsigned S> 
 
575
    template<class T, unsigned S>
576
576
    pod_bvector<T, S>::pod_bvector(const pod_bvector<T, S>& v) :
577
577
        m_size(v.m_size),
578
578
        m_num_blocks(v.m_num_blocks),
579
579
        m_max_blocks(v.m_max_blocks),
580
 
        m_blocks(v.m_max_blocks ? 
581
 
                 pod_allocator<T*>::allocate(v.m_max_blocks) : 
 
580
        m_blocks(v.m_max_blocks ?
 
581
                 pod_allocator<T*>::allocate(v.m_max_blocks) :
582
582
                 0),
583
583
        m_block_ptr_inc(v.m_block_ptr_inc)
584
584
    {
592
592
 
593
593
 
594
594
    //------------------------------------------------------------------------
595
 
    template<class T, unsigned S> 
596
 
    const pod_bvector<T, S>& 
 
595
    template<class T, unsigned S>
 
596
    const pod_bvector<T, S>&
597
597
    pod_bvector<T, S>::operator = (const pod_bvector<T, S>& v)
598
598
    {
599
599
        unsigned i;
614
614
    template<class T, unsigned S>
615
615
    void pod_bvector<T, S>::allocate_block(unsigned nb)
616
616
    {
617
 
        if(nb >= m_max_blocks) 
 
617
        if(nb >= m_max_blocks)
618
618
        {
619
619
            T** new_blocks = pod_allocator<T*>::allocate(m_max_blocks + m_block_ptr_inc);
620
620
 
621
621
            if(m_blocks)
622
622
            {
623
 
                memcpy(new_blocks, 
624
 
                       m_blocks, 
 
623
                memcpy(new_blocks,
 
624
                       m_blocks,
625
625
                       m_num_blocks * sizeof(T*));
626
626
 
627
627
                pod_allocator<T*>::deallocate(m_blocks, m_max_blocks);
650
650
 
651
651
 
652
652
    //------------------------------------------------------------------------
653
 
    template<class T, unsigned S> 
 
653
    template<class T, unsigned S>
654
654
    inline void pod_bvector<T, S>::add(const T& val)
655
655
    {
656
656
        *data_ptr() = val;
659
659
 
660
660
 
661
661
    //------------------------------------------------------------------------
662
 
    template<class T, unsigned S> 
 
662
    template<class T, unsigned S>
663
663
    inline void pod_bvector<T, S>::remove_last()
664
664
    {
665
665
        if(m_size) --m_size;
667
667
 
668
668
 
669
669
    //------------------------------------------------------------------------
670
 
    template<class T, unsigned S> 
 
670
    template<class T, unsigned S>
671
671
    void pod_bvector<T, S>::modify_last(const T& val)
672
672
    {
673
673
        remove_last();
676
676
 
677
677
 
678
678
    //------------------------------------------------------------------------
679
 
    template<class T, unsigned S> 
 
679
    template<class T, unsigned S>
680
680
    int pod_bvector<T, S>::allocate_continuous_block(unsigned num_elements)
681
681
    {
682
682
        if(num_elements < block_size)
706
706
 
707
707
 
708
708
    //------------------------------------------------------------------------
709
 
    template<class T, unsigned S> 
 
709
    template<class T, unsigned S>
710
710
    unsigned pod_bvector<T, S>::byte_size() const
711
711
    {
712
712
        return m_size * sizeof(T);
714
714
 
715
715
 
716
716
    //------------------------------------------------------------------------
717
 
    template<class T, unsigned S> 
 
717
    template<class T, unsigned S>
718
718
    void pod_bvector<T, S>::serialize(int8u* ptr) const
719
719
    {
720
720
        unsigned i;
726
726
    }
727
727
 
728
728
    //------------------------------------------------------------------------
729
 
    template<class T, unsigned S> 
 
729
    template<class T, unsigned S>
730
730
    void pod_bvector<T, S>::deserialize(const int8u* data, unsigned byte_size)
731
731
    {
732
732
        remove_all();
743
743
 
744
744
    // Replace or add a number of elements starting from "start" position
745
745
    //------------------------------------------------------------------------
746
 
    template<class T, unsigned S> 
747
 
    void pod_bvector<T, S>::deserialize(unsigned start, const T& empty_val, 
 
746
    template<class T, unsigned S>
 
747
    void pod_bvector<T, S>::deserialize(unsigned start, const T& empty_val,
748
748
                                        const int8u* data, unsigned byte_size)
749
749
    {
750
750
        while(m_size < start)
772
772
 
773
773
    //---------------------------------------------------------block_allocator
774
774
    // Allocator for arbitrary POD data. Most usable in different cache
775
 
    // systems for efficient memory allocations. 
 
775
    // systems for efficient memory allocations.
776
776
    // Memory is allocated with blocks of fixed size ("block_size" in
777
777
    // the constructor). If required size exceeds the block size the allocator
778
778
    // creates a new block of the required size. However, the most efficient
779
 
    // use is when the average reqired size is much less than the block size. 
 
779
    // use is when the average reqired size is much less than the block size.
780
780
    //------------------------------------------------------------------------
781
781
    class block_allocator
782
782
    {
821
821
            m_rest(0)
822
822
        {
823
823
        }
824
 
       
 
824
 
825
825
 
826
826
        int8u* allocate(unsigned size, unsigned alignment=1)
827
827
        {
831
831
                int8u* ptr = m_buf_ptr;
832
832
                if(alignment > 1)
833
833
                {
834
 
                    unsigned align = 
 
834
                    unsigned align =
835
835
                        (alignment - unsigned((size_t)ptr) % alignment) % alignment;
836
836
 
837
837
                    size += align;
858
858
        void allocate_block(unsigned size)
859
859
        {
860
860
            if(size < m_block_size) size = m_block_size;
861
 
            if(m_num_blocks >= m_max_blocks) 
 
861
            if(m_num_blocks >= m_max_blocks)
862
862
            {
863
 
                block_type* new_blocks = 
 
863
                block_type* new_blocks =
864
864
                    pod_allocator<block_type>::allocate(m_max_blocks + m_block_ptr_inc);
865
865
 
866
866
                if(m_blocks)
867
867
                {
868
 
                    memcpy(new_blocks, 
869
 
                           m_blocks, 
 
868
                    memcpy(new_blocks,
 
869
                           m_blocks,
870
870
                           m_num_blocks * sizeof(block_type));
871
871
                    pod_allocator<block_type>::deallocate(m_blocks, m_max_blocks);
872
872
                }
875
875
            }
876
876
 
877
877
            m_blocks[m_num_blocks].size = size;
878
 
            m_blocks[m_num_blocks].data = 
 
878
            m_blocks[m_num_blocks].data =
879
879
                m_buf_ptr =
880
880
                pod_allocator<int8u>::allocate(size);
881
881
 
905
905
        quick_sort_threshold = 9
906
906
    };
907
907
 
908
 
    
 
908
 
909
909
    //-----------------------------------------------------------swap_elements
910
910
    template<class T> inline void swap_elements(T& a, T& b)
911
911
    {
925
925
        typename Array::value_type* e2;
926
926
 
927
927
        int  stack[80];
928
 
        int* top = stack; 
 
928
        int* top = stack;
929
929
        int  limit = arr.size();
930
930
        int  base = 0;
931
931
 
946
946
                i = base + 1;
947
947
                j = limit - 1;
948
948
 
949
 
                // now ensure that *i <= *base <= *j 
950
 
                e1 = &(arr[j]); 
951
 
                e2 = &(arr[i]);
952
 
                if(less(*e1, *e2)) swap_elements(*e1, *e2);
953
 
 
954
 
                e1 = &(arr[base]); 
955
 
                e2 = &(arr[i]);
956
 
                if(less(*e1, *e2)) swap_elements(*e1, *e2);
957
 
 
958
 
                e1 = &(arr[j]); 
 
949
                // now ensure that *i <= *base <= *j
 
950
                e1 = &(arr[j]);
 
951
                e2 = &(arr[i]);
 
952
                if(less(*e1, *e2)) swap_elements(*e1, *e2);
 
953
 
 
954
                e1 = &(arr[base]);
 
955
                e2 = &(arr[i]);
 
956
                if(less(*e1, *e2)) swap_elements(*e1, *e2);
 
957
 
 
958
                e1 = &(arr[j]);
959
959
                e2 = &(arr[base]);
960
960
                if(less(*e1, *e2)) swap_elements(*e1, *e2);
961
961
 
1024
1024
 
1025
1025
 
1026
1026
    //------------------------------------------------------remove_duplicates
1027
 
    // Remove duplicates from a sorted array. It doesn't cut the 
 
1027
    // Remove duplicates from a sorted array. It doesn't cut the
1028
1028
    // tail of the array, it just returns the number of remaining elements.
1029
1029
    //-----------------------------------------------------------------------
1030
1030
    template<class Array, class Equal>
1070
1070
        while(end - beg > 1)
1071
1071
        {
1072
1072
            unsigned mid = (end + beg) >> 1;
1073
 
            if(less(val, arr[mid])) end = mid; 
 
1073
            if(less(val, arr[mid])) end = mid;
1074
1074
            else                    beg = mid;
1075
1075
        }
1076
1076