array.h

Go to the documentation of this file.

// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; eval: (progn (c-set-style "stroustrup") (c-set-offset 'innamespace 0)); -*-
// vi:set ts=4 sts=4 sw=4 noet :
// Copyright 2010, 2012, The TPIE development team
// 
// This file is part of TPIE.
// 
// TPIE is free software: you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
// 
// TPIE is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
// License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with TPIE.  If not, see <http://www.gnu.org/licenses/>
#ifndef __TPIE_ARRAY_H__
#define __TPIE_ARRAY_H__

#include <tpie/util.h>
#include <boost/iterator/iterator_facade.hpp>
#include <tpie/memory.h>
#include <tpie/array_view_base.h>
#include <type_traits>
#include <cassert>
#include <ostream>

namespace tpie {

template <typename TT, bool forward>
class array_iter_base: public boost::iterator_facade<
    array_iter_base<TT, forward>,
    TT , boost::random_access_traversal_tag> {
private:
    template <typename, typename> friend class array;
    friend class boost::iterator_core_access;
    template <typename, bool> friend class array_iter_base;

    explicit array_iter_base(TT * e): elm(e) {}

    TT & dereference() const {return * elm;}
    template <class U>
    bool equal(array_iter_base<U, forward> const& o) const {return elm == o.elm;}
    void increment() {elm += forward?1:-1;}
    void decrement() {elm += forward?-1:1;}
    void advance(size_t n) {if (forward) elm += n; else elm -= n;}
    ptrdiff_t distance_to(array_iter_base const & o) const {return o.elm - elm;}
    TT * elm;
public:
    array_iter_base(): elm(0) {};

    template <class U>
    array_iter_base(array_iter_base<U, forward> const& o,
                    typename std::enable_if<
                    std::is_convertible<U*,TT*>::value>::type* = 0)
            : elm(o.elm) {}
};

#pragma pack(push, 1)
template <typename C>
struct trivial_same_size {
    char c[sizeof(C)];
};
#pragma pack(pop)

namespace bits {
    template <typename T, typename Allocator> struct allocator_usage;
} // namespace bits

// ASIDE about the C++ language: A type is said to be trivially constructible
//     if it has no user-defined constructors and all its members are trivially
//     constructible. `new T` will allocate memory for a T-element, and if T is
//     trivially constructible, the memory will be left uninitialized. This
//     goes for arrays (T[]) as well, meaning an array initialization of a
//     trivially constructible type takes practically no time.
//
// IMPLEMENTATION NOTE. We have three cases for how we want the item buffer
// `array::m_elements` to be initialized:
//
// 1. Default constructed. tpie_new_array<T> does this
//    allocation+initialization.
//
// 2. Copy constructed from a single element. Cannot be done with
//    tpie_new_array<T>.
//
// 3. Copy constructed from elements in another array. Cannot be done with
//    tpie_new_array<T> either.
//
// For cases 2 and 3, we must keep `new`-allocation separate from item
// initialization. Thus, for these cases we instead allocate an array of
// trivial_same_size<T>. This is a struct that has the same size as T, but is
// trivially constructible, meaning no memory initialization is done.
//
// Then, for case 2, we use std::uninitialized_fill, and for case 3 we use
// std::uninitialized_copy.
//
// Unfortunately, although we have the choice in case 1 of allocating a
// trivial_same_size<T> and then calling the default constructors afterwards,
// this turns out in some cases to be around 10% slower than allocating a
// T-array directly.
//
// Also, in order to have the same initialization semantics with regards to
// trivially constructible types as C++ new[], we need to check if the type is
// trivially constructible (using SFINAE/boost::enable_if/boost::type_traits)
// to avoid zero-initializing those (a speed penalty we cannot afford).
//
// Now it is clear that we must sometimes use tpie_new_array<T>, other times
// tpie_new_array<trivial_same_size<T> >. The TPIE memory manager checks that
// buffers allocated as one type are not deallocated as another type, so when
// the buffer is allocated as a trivial_same_size, we must remember this fact
// for later destruction and deallocation.
//
// We remember this fact in array::m_tss_used.

template <typename T, typename Allocator = allocator<T> >
class array : public linear_memory_base<array<T> > {
public:
    typedef array_iter_base<T const, true> const_iterator;

    typedef array_iter_base<T const, false> const_reverse_iterator;

    typedef array_iter_base<T, true> iterator;

    typedef array_iter_base<T, false> reverse_iterator;

    typedef T value_type;

    iterator find(size_t idx) throw () {
        assert(idx <= size());
        return get_iter(idx);
    }

    const_iterator find(size_t idx) const throw () {
        assert(idx <= size());
        return get_iter(idx);
    }
    
    T & at(size_t i) throw() {
        assert(i < size());
        return m_elements[i];
    }

    const T & at(size_t i) const throw() {
        assert(i < size());
        return m_elements[i];
    }
    
    array & operator=(const array & other) {
        resize(other.size());
        for (size_t i=0; i < size(); ++i) m_elements[i] = other[i];
        return *this;
    }

    array & operator=(array && other) {
        resize(0);
        std::swap(m_allocator, other.m_allocator);
        std::swap(m_elements, other.m_elements);
        std::swap(m_size, other.m_size);
        std::swap(m_tss_used, other.m_tss_used);
        return *this;
    }
    
    template <typename OtherAllocator>
    array & operator=(const array<T, OtherAllocator> & other) {
        resize(other.size());
        for (size_t i=0; i < size(); ++i) m_elements[i] = other[i];
        return *this;
    }

    bool empty() const {return size() == 0;}

    const T & operator[](size_t i) const {
        assert(i < size());
        return at(i);
    }

    T & operator[](size_t i) {
        assert(i < size());
        return at(i);
    }

    bool operator==(const array & other) const {
        if (size() != other.size()) return false;
        for (size_t i=0;i<size();++i) if (*get_iter(i) != *other.get_iter(i)) return false;
        return true;
    }

    bool operator!=(const array & other) const {
        if (size() != other.size()) return true;
        for (size_t i=0; i<size(); ++i) if (*get_iter(i) != *other.get_iter(i)) return true;
        return false;
    }

    iterator begin() {return get_iter(0);}

    const_iterator begin() const {return get_iter(0);}

    iterator end() {return get_iter(size());}

    const_iterator end() const {return get_iter(size());}

    const T & front() const {return at(0);}

    T & front() {return at(0);}

    const T & back() const {return at(size()-1);}

    T & back() {return at(size()-1);}

    reverse_iterator rbegin() {return get_rev_iter(0);}

    const_reverse_iterator rbegin() const {return get_rev_iter(0);}

    reverse_iterator rend() {return get_rev_iter(size());}

    const_reverse_iterator rend() const {return get_rev_iter(size());}

private:
    T * m_elements;
    size_t m_size;

    iterator get_iter(size_t idx) {
        return iterator(m_elements+idx);
    }

    const_iterator get_iter(size_t idx) const {
        return const_iterator(m_elements+idx);
    }

    reverse_iterator get_rev_iter(size_t idx) {
        return reverse_iterator(m_elements+m_size-idx-1);
    }

    const_reverse_iterator get_rev_iter(size_t idx) const {
        return const_reverse_iterator(m_elements+m_size-idx-1);
    }
public:
    static double memory_coefficient() {
        return (double)sizeof(T);
    }

    static double memory_overhead() {return sizeof(array);}

    array(size_type s, const T & value,
          const Allocator & alloc=Allocator()
        ): m_elements(0), m_size(0), m_tss_used(false), m_allocator(alloc)
        {resize(s, value);}

    array(size_type s, memory_bucket_ref bucket):
        m_elements(0), m_size(0), m_tss_used(false), m_allocator(bucket)
        {resize(s);}

    array(memory_bucket_ref bucket):
        m_elements(0), m_size(0), m_tss_used(false), m_allocator(bucket) {}
    
    array(size_type s=0, const Allocator & alloc=
          Allocator()): m_elements(0), m_size(0), m_tss_used(false),
                        m_allocator(alloc) {resize(s);}

    array(const array & other): m_elements(0), m_size(other.m_size), m_tss_used(false), m_allocator(other.m_allocator) {
        if (other.size() == 0) return;
        alloc_copy(other.m_elements);
    }

    array(array && other)
        : m_elements(other.m_elements)
        , m_size(other.m_size)
        , m_tss_used(other.m_tss_used)
        , m_allocator(other.m_allocator) {
        other.m_elements = nullptr;
        other.m_size = 0;
        other.m_tss_used = false;
    }

    array(const array_view_base<T> & view)
        : m_elements(0)
        , m_size(view.size())
        , m_tss_used(false)
    {
        if (view.size() == 0) return;
        alloc_copy(&*view.begin());
    }

    array(const array_view_base<const T> & view)
        : m_elements(0)
        , m_size(view.size())
        , m_tss_used(false)
    {
        if (view.size() == 0) return;
        alloc_copy(&*view.begin());
    }

    ~array() {resize(0);}
    
    void resize(size_t size, const T & elm) {
        if (size != m_size) {
            destruct_and_dealloc();
            m_size = size;

            alloc_fill(elm);
        } else {
            std::fill(m_elements+0, m_elements+m_size, elm);
        }
    }

    void swap(array & other) {
        std::swap(m_allocator, other.m_allocator);
        std::swap(m_elements, other.m_elements);
        std::swap(m_size, other.m_size);
        std::swap(m_tss_used, other.m_tss_used);
    }

    void resize(size_t s) {
        destruct_and_dealloc();
        m_size = s;
        alloc_dfl();
    }

    size_type size() const {return m_size;}

    T * get() {return m_elements;}

    const T * get() const {return m_elements;}

    Allocator get_allocator() const {return m_allocator;}
private:
    friend struct bits::allocator_usage<T, Allocator>;

    void alloc_copy(const T * copy_from) { bits::allocator_usage<T, Allocator>::alloc_copy(*this, copy_from); }

    void alloc_fill(const T & elm) { bits::allocator_usage<T, Allocator>::alloc_fill(*this, elm); }

    void alloc_dfl() { bits::allocator_usage<T, Allocator>::alloc_dfl(*this); }

    void destruct_and_dealloc() { bits::allocator_usage<T, Allocator>::destruct_and_dealloc(*this); }

    bool m_tss_used;

    Allocator m_allocator;
};

namespace bits {

template <typename T>
struct allocator_usage<T, allocator<T> > {
    static void alloc_copy(array<T, allocator<T> > & host, const T * copy_from) {
        host.m_elements = host.m_size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(host.m_size)) : 0;
        host.m_tss_used = true;

        if (host.m_allocator.bucket)
            host.m_allocator.bucket->count += sizeof(T) * host.m_size;
            
        std::uninitialized_copy(copy_from+0, copy_from+host.m_size, host.m_elements+0);
    }

    static void alloc_fill(array<T, allocator<T> > & host, const T & elm) {
        host.m_elements = host.m_size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(host.m_size)) : 0;
        host.m_tss_used = true;

        if (host.m_allocator.bucket)
            host.m_allocator.bucket->count += sizeof(T) * host.m_size;
        
        // call copy constructors manually
        std::uninitialized_fill(host.m_elements+0, host.m_elements+host.m_size, elm);
    }

    static void alloc_dfl(array<T, allocator<T> > & host) {
        host.m_elements = host.m_size ? tpie_new_array<T>(host.m_size) : 0;
        host.m_tss_used = false;
        
        if (host.m_allocator.bucket)
            host.m_allocator.bucket->count += sizeof(T) * host.m_size;
    }

    static void destruct_and_dealloc(array<T, allocator<T> > & host) {
        if (host.m_allocator.bucket)
            host.m_allocator.bucket->count -= sizeof(T) * host.m_size;
        
        if (!host.m_tss_used) {
            // calls destructors
            tpie_delete_array(host.m_elements, host.m_size);
            return;
        }

        // call destructors manually
        for (size_t i = 0; i < host.m_size; ++i) {
            host.m_elements[i].~T();
        }
        tpie_delete_array(reinterpret_cast<trivial_same_size<T>*>(host.m_elements), host.m_size);
    }
};

template <typename T, typename Allocator>
struct allocator_usage {
    static void alloc_copy(array<T, Allocator> & host, const T * copy_from) {
        host.m_elements = host.m_size ? host.m_allocator.allocate(host.m_size) : 0;
        for (size_t i = 0; i < host.m_size; ++i) {
            host.m_allocator.construct(host.m_elements+i, copy_from[i]);
        }
    }

    static void alloc_fill(array<T, Allocator> & host, const T & elm) {
        host.m_elements = host.m_size ? host.m_allocator.allocate(host.m_size) : 0;
        for (size_t i = 0; i < host.m_size; ++i) {
            host.m_allocator.construct(host.m_elements+i, elm);
        }
    }

    static void alloc_dfl(array<T, Allocator> & host) {
        host.m_elements = host.m_size ? host.m_allocator.allocate(host.m_size) : 0;
        for (size_t i = 0; i < host.m_size; ++i) {
            host.m_allocator.construct(host.m_elements+i);
        }
    }

    static void destruct_and_dealloc(array<T, Allocator> & host) {
        for (size_t i = 0; i < host.m_size; ++i) {
            host.m_allocator.destroy(host.m_elements+i);
        }
        host.m_allocator.deallocate(host.m_elements, host.m_size);
    }
};

} // namespace bits

template <typename T>
std::ostream & operator<<(std::ostream & o, const array<T> & a) {
    o << "[";
    bool first=true;
    for(size_t i=0; i < a.size(); ++i) {
        if (first) first = false;
        else o << ", ";
        o << a[i];
    }
    return o << "]";
}

} // namespace tpie

namespace std {


template <typename T>
void swap(tpie::array<T> & a, tpie::array<T> & b) {
    a.swap(b);
}

template <typename TT1, bool forward1, typename TT2, bool forward2>
tpie::array_iter_base<TT2, forward2>
copy(tpie::array_iter_base<TT1, forward1> first,
     tpie::array_iter_base<TT1, forward1> last,
     tpie::array_iter_base<TT2, forward2> d_first) {

    ptrdiff_t dist = copy(&*first, &*last, &*d_first) - &*d_first;
    return d_first + dist;
}

template <typename TT, bool forward, typename OutputIterator>
OutputIterator
copy(tpie::array_iter_base<TT, forward> first,
     tpie::array_iter_base<TT, forward> last,
     OutputIterator d_first) {

    return copy(&*first, &*last, d_first);
}

template <typename TT, bool forward, typename InputIterator>
tpie::array_iter_base<TT, forward>
copy(InputIterator first,
     InputIterator last,
     tpie::array_iter_base<TT, forward> d_first) {

    ptrdiff_t dist = copy(first, last, &*d_first) - &*d_first;
    return d_first + dist;
}

} // namespace std

#endif //__TPIE_ARRAY_H__