agg_array.h.svn-base

okular

    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)
        {
            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 = new T* [m_max_blocks + m_block_ptr_inc];

            if(m_blocks)
            {
                memcpy(new_blocks, 
                       m_blocks, 
                       m_num_blocks * sizeof(T*));

                delete [] m_blocks;
            }
            m_blocks = new_blocks;
            m_max_blocks += m_block_ptr_inc;
        }
        m_blocks[nb] = new 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(); // Allocate initial block if necessary
            unsigned rest = block_size - (m_size & block_mask);
            unsigned index;
            if(num_elements <= rest)
            {
                // The rest of the block is good, we can use it
                //-----------------
                index = m_size;
                m_size += num_elements;
                return index;
            }

            // New block
            //---------------
            m_size += rest;
            data_ptr();
            index = m_size;
            m_size += num_elements;
            return index;
        }
        return -1; // Impossible to allocate
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    unsigned pod_deque<T, S>::byte_size() const
    {
        return m_size * sizeof(T);
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    void pod_deque<T, S>::serialize(int8u* ptr) const
    {
        unsigned i;
        for(i = 0; i < m_size; i++)
        {
            memcpy(ptr, &(*this)[i], sizeof(T));
            ptr += sizeof(T);
        }
    }

    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    void pod_deque<T, S>::deserialize(const int8u* data, unsigned byte_size)
    {
        remove_all();
        byte_size /= sizeof(T);
        for(unsigned i = 0; i < byte_size; ++i)
        {
            T* ptr = data_ptr();
            memcpy(ptr, data, sizeof(T));
            ++m_size;
            data += sizeof(T);
        }
    }


    // Replace or add a number of elements starting from "start" position
    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    void pod_deque<T, S>::deserialize(unsigned start, const T& empty_val, 
                                      const int8u* data, unsigned byte_size)
    {
        while(m_size < start)
        {
            add(empty_val);
        }

        byte_size /= sizeof(T);
        for(unsigned i = 0; i < byte_size; ++i)
        {
            if(start + i < m_size)
            {
                memcpy(&((*this)[start + i]), data, sizeof(T));
            }
            else
            {
                T* ptr = data_ptr();
                memcpy(ptr, data, sizeof(T));
                ++m_size;
            }
            data += sizeof(T);
        }
    }


    //-----------------------------------------------------------pod_allocator
    // Allocator for arbitrary POD data. Most usable in different cache
    // systems for efficient memory allocations. 
    // Memory is allocated with blocks of fixed size ("block_size" in
    // the constructor). If required size exceeds the block size the allocator
    // creates a new block of the required size. However, the most efficient
    // use is when the average reqired size is much less than the block size. 
    //------------------------------------------------------------------------
    class pod_allocator
    {
    public:
        void remove_all()
        {
            if(m_num_blocks)
            {
                int8u** blk = m_blocks + m_num_blocks - 1;
                while(m_num_blocks--)
                {
                    delete [] *blk;
                    --blk;
                }
                delete [] 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 = new int8u* [m_max_blocks + m_block_ptr_inc];

                if(m_blocks)
                {
                    memcpy(new_blocks, 
                           m_blocks, 
                           m_num_blocks * sizeof(int8u*));

                    delete [] m_blocks;
                }
                m_blocks = new_blocks;
                m_max_blocks += m_block_ptr_inc;
            }
            m_blocks[m_num_blocks] = m_buf_ptr = new 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 = 9
    };

    
    //-----------------------------------------------------------swap_elements
    template<class T> inline void swap_elements(T& a, T& b)
    {
        T temp = a;
        a = b;
        b = temp;
    }


    //--------------------------------------------------------------quick_sort
    template<class Array, class Less>
    void quick_sort(Array& arr, Less less)
    {
        if(arr.size() < 2) return;

        typename Array::value_type* e1;
        typename Array::value_type* e2;

        int  stack[80];
        int* top = stack; 
        int  limit = arr.size();
        int  base = 0;

        for(;;)
        {
            int len = limit - base;

            int i;
            int j;
            int pivot;

            if(len > quick_sort_threshold)
            {
                // we use base + len/2 as the pivot
                pivot = base + len / 2;
                swap_elements(arr[base], arr[pivot]);

                i = base + 1;
                j = limit - 1;

                // now ensure that *i <= *base <= *j 
                e1 = &(arr[j]); 
                e2 = &(arr[i]);
                if(less(*e1, *e2)) swap_elements(*e1, *e2);

                e1 = &(arr[base]); 
                e2 = &(arr[i]);
                if(less(*e1, *e2)) swap_elements(*e1, *e2);

                e1 = &(arr[j]); 
                e2 = &(arr[base]);
                if(less(*e1, *e2)) swap_elements(*e1, *e2);

                for(;;)
                {
                    do i++; while( less(arr[i], arr[base]) );
                    do j--; while( less(arr[base], arr[j]) );

                    if( i > j )
                    {
                        break;
                    }

                    swap_elements(arr[i], arr[j]);
                }

                swap_elements(arr[base], arr[j]);

                // now, push the largest sub-array
                if(j - base > limit - i)
                {
                    top[0] = base;
                    top[1] = j;
                    base   = i;
                }
                else
                {
                    top[0] = i;
                    top[1] = limit;
                    limit  = j;
                }
                top += 2;
            }
            else
            {
                // the sub-array is small, perform insertion sort
                j = base;
                i = j + 1;

                for(; i < limit; j = i, i++)
                {
                    for(; less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--)
                    {
                        swap_elements(*e1, *e2);
                        if(j == base)
                        {
                            break;
                        }
                    }
                }
                if(top > stack)
                {
                    top  -= 2;
                    base  = top[0];
                    limit = top[1];
                }
                else
                {
                    break;
                }
            }
        }
    }




    //------------------------------------------------------remove_duplicates
    // Remove duplicates from a sorted array. It doesn't cut the the 
    // tail of the array, it just returns the number of remaining elements.
    //-----------------------------------------------------------------------
    template<class Array, class Equal>
    unsigned remove_duplicates(Array& arr, Equal equal)
    {
        if(arr.size() < 2) return arr.size();

        unsigned i, j;
        for(i = 1, j = 1; i < arr.size(); i++)
        {
            typename Array::value_type& e = arr[i];
            if(!equal(e, arr[i - 1]))
            {
                arr[j++] = e;
            }
        }
        return j;
    }




}

#endif