lfVector.ipp

/* Copyright (c) 2011-2014, EPFL/Blue Brain Project
 *                          Daniel Nachbaur <daniel.nachbaur@epfl.ch>
 *                          Stefan.Eilemann@epfl.ch
 *
 * This file is part of Lunchbox <https://github.com/Eyescale/Lunchbox>
 *
 * This library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License version 3.0 as published
 * by the Free Software Foundation.
 *
 * This library 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 this library; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include "lfVectorIterator.h"

namespace lunchbox
{
template <class T, int32_t nSlots>
LFVector<T, nSlots>::LFVector()
    : size_(0)
{
    setZero(slots_, nSlots * sizeof(T*));
}

template <class T, int32_t nSlots>
LFVector<T, nSlots>::LFVector(const size_t n)
    : size_(n)
{
    LBASSERT(n != 0);
    setZero(slots_, nSlots * sizeof(T*));
    const int32_t s = getIndexOfLastBit(uint64_t(n));
    for (int32_t i = 0; i <= s; ++i)
        slots_[i] = new T[1 << i];
}

template <class T, int32_t nSlots>
LFVector<T, nSlots>::LFVector(const size_t n, const T& t)
    : size_(0)
{
    LBASSERT(n != 0);
    setZero(slots_, nSlots * sizeof(T*));
    const int32_t s = getIndexOfLastBit(uint64_t(n));
    for (size_t i = 0; i <= size_t(s); ++i)
    {
        const size_t sz = 1 << i;
        slots_[i] = new T[sz];
        for (size_t j = 0; size_ < n && j < sz; ++j)
        {
            slots_[i][j] = t;
            ++size_;
        }
    }
    LBASSERTINFO(size_ == n, size_ << " != " << n);
}

template <class T, int32_t nSlots>
LFVector<T, nSlots>::LFVector(const LFVector& from)
    : size_(0)
    , lock_()
{
    assign_(from);
}

template <class T, int32_t nSlots>
template <int32_t fromSlots>
LFVector<T, nSlots>::LFVector(const LFVector<T, fromSlots>& from)
    : size_(0)
    , lock_()
{
    assign_(from);
}

template <class T, int32_t nSlots>
LFVector<T, nSlots>::~LFVector()
{
    for (size_t i = 0; i < nSlots; ++i)
        delete[] slots_[i];
}

template <class T, int32_t nSlots>
LFVector<T, nSlots>& LFVector<T, nSlots>::operator=(
    const LFVector<T, nSlots>& from)
{
    if (&from == this)
        return *this;

    ScopedWrite mutex1(lock_);      // DEADLOCK when doing a=b and b=a
    ScopedWrite mutex2(from.lock_); // consider trySet/yield approach
    size_ = 0;
    for (size_t i = 0; i < size_t(nSlots); ++i)
    {
        if (from.slots_[i])
        {
            const size_t sz = size_t(1) << i;
            if (!slots_[i])
                slots_[i] = new T[sz];

            for (size_t j = 0; size_ < from.size_ && j < sz; ++j)
            {
                slots_[i][j] = from.slots_[i][j];
                ++size_;
            }
        }
        else if (slots_[i]) // done copying, free unneeded slots
        {
            delete[] slots_[i];
            slots_[i] = 0;
        }
    }

    LBASSERTINFO(size_ == from.size_, size_ << " != " << from.size_);
    return *this;
}

template <class T, int32_t nSlots>
bool LFVector<T, nSlots>::operator==(const LFVector& rhs) const
{
    if (&rhs == this)
        return true;

    if (size() != rhs.size())
        return false;

    const_iterator it = begin();
    const_iterator rhsIt = rhs.begin();
    for (; it != end() && rhsIt != end(); ++it, ++rhsIt)
    {
        if (*it != *rhsIt)
            return false;
    }

    return true;
}

#ifdef LB_GCC_4_6_OR_LATER // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51721
#ifndef LB_GCC_4_8         // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56824
#pragma GCC diagnostic push
#endif
#pragma GCC diagnostic ignored "-Warray-bounds"
#endif

template <class T, int32_t nSlots>
T& LFVector<T, nSlots>::operator[](size_t i)
{
    // one beyond end is possible when called by erase
    LBASSERTINFO(size_ >= i, size_ << " < " << i);
    ++i;
    const int32_t slot = getIndexOfLastBit(i);
    const size_t index = i ^ (size_t(1) << slot);

    LBASSERTINFO(slot >= 0 && slot < nSlots, slot);
    LBASSERT(slots_[slot]);
    LBASSERT(index < (1ull << slot));
    return slots_[slot][index];
}

template <class T, int32_t nSlots>
const T& LFVector<T, nSlots>::operator[](size_t i) const
{
    LBASSERTINFO(size_ > i, size_ << " <= " << i);
    ++i;
    const int32_t slot = getIndexOfLastBit(i);
    const size_t index = i ^ (size_t(1) << slot);

    LBASSERTINFO(slot >= 0 && slot < nSlots, slot);
    LBASSERT(slots_[slot]);
    LBASSERT(index < (1ull << slot));
    return slots_[slot][index];
}

#ifdef LB_GCC_4_6_OR_LATER
#ifndef LB_GCC_4_8
#pragma GCC diagnostic pop
#endif
#endif

template <class T, int32_t nSlots>
T& LFVector<T, nSlots>::front()
{
    LBASSERT(!empty());
    return slots_[0][0];
}

template <class T, int32_t nSlots>
T& LFVector<T, nSlots>::back()
{
    LBASSERT(!empty());
    return (*this)[size_ - 1];
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::expand(const size_t newSize, const T& item)
{
    ScopedWrite mutex(lock_);
    while (newSize > size())
        push_back_unlocked_(item);
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::push_back(const T& item, bool lock)
{
    if (lock)
    {
        ScopedWrite mutex(lock_);
        push_back_unlocked_(item);
    }
    else
        push_back_unlocked_(item);
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::pop_back()
{
    ScopedWrite mutex(lock_);
    if (size_ == 0)
        return;
    --size_;
    (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
    trim_();
}

template <class T, int32_t nSlots>
bool LFVector<T, nSlots>::pop_back(T& element)
{
    ScopedWrite mutex(lock_);
    if (size_ == 0)
        return false;

    element = back();
    --size_;
    (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
    trim_();
    return true;
}

template <class T, int32_t nSlots>
typename LFVector<T, nSlots>::iterator LFVector<T, nSlots>::erase(
    typename LFVector<T, nSlots>::iterator pos)
{
    LBASSERT(pos.container_ == this);
    if (pos.container_ != this || pos.i_ >= size_)
        return end();

    ScopedWrite mutex(lock_);
    --size_;
#pragma warning(push)
#pragma warning(disable : 4996) // unchecked iterators
    std::copy(pos + 1, end() + 1, pos);
#pragma warning(pop)
    (*this)[size_] = T(); // correct for all T? Needed to reset RefPtr
    trim_();
    return pos;
}

template <class T, int32_t nSlots>
typename LFVector<T, nSlots>::iterator LFVector<T, nSlots>::erase(
    const T& element)
{
    ScopedWrite mutex(lock_);
    for (size_t i = size_; i != 0; --i)
    {
        if ((*this)[i - 1] == element)
        {
            --size_;
            iterator pos(this, i - 1);
#pragma warning(push)
#pragma warning(disable : 4996) // unchecked iterators
            std::copy(pos + 1, end() + 1, pos);
#pragma warning(pop)
            (*this)[size_] = 0; // see comment in other erase
            trim_();
            return pos;
        }
    }
    return end();
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::resize(const size_t newSize, const T& value)
{
    ScopedWrite mutex(lock_);
    while (size_ > newSize)
    {
        --size_;
        (*this)[size_] = T(); // not correct for all T? Needed to reset RefPtr
    }
    trim_();

    while (size_ < newSize)
        push_back_unlocked_(value);
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::clear()
{
    ScopedWrite mutex(lock_);
    while (size_ > 0)
    {
        --size_;
        (*this)[size_] = T(); // Needed to reset RefPtr
    }
    for (int32_t i = 0; i < nSlots; ++i)
    {
        delete[] slots_[i];
        slots_[i] = 0;
    }
}

template <class T, int32_t nSlots>
typename LFVector<T, nSlots>::ScopedWrite LFVector<T, nSlots>::getWriteLock()
{
    lock_.set();
    return {lock_, std::adopt_lock};
}

template <class T, int32_t nSlots>
template <int32_t fromSlots>
void LFVector<T, nSlots>::assign_(const LFVector<T, fromSlots>& from)
{
    setZero(slots_, nSlots * sizeof(T*));

    ScopedWrite mutex(from.lock_);
    for (int32_t i = 0; i < nSlots; ++i)
    {
        if (i >= fromSlots || !from.slots_[i]) // done copying
        {
            LBASSERTINFO(size_ == from.size_, size_ << " != " << from.size_);
            return;
        }

        const int32_t sz = 1 << i;
        slots_[i] = new T[sz];
        for (int32_t j = 0; size_ < from.size_ && j < sz; ++j)
        {
            slots_[i][j] = from.slots_[i][j];
            ++size_;
        }
    }
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::push_back_unlocked_(const T& item)
{
    const size_t i = size_ + 1;
    const int32_t slot = getIndexOfLastBit(i);
    if (slot < 0 || slot >= nSlots)
    {
        LBASSERTINFO(slot >= 0 && slot < nSlots, slot);
        LBTHROW(std::runtime_error("LFVector full"));
    }

    const size_t sz = (size_t(1) << slot);

    if (!slots_[slot])
        slots_[slot] = new T[sz];

    const ssize_t index = i ^ sz;
    slots_[slot][index] = item;
    ++size_;
}

template <class T, int32_t nSlots>
void LFVector<T, nSlots>::trim_()
{
    const int32_t nextSlot = getIndexOfLastBit(size_ + 1) + 1;
    if (nextSlot < nSlots && slots_[nextSlot])
    {
        delete[] slots_[nextSlot]; // delete next slot (keep a spare)
        slots_[nextSlot] = 0;
    }
}

template <class T, int32_t nSlots>
inline typename LFVector<T, nSlots>::const_iterator LFVector<T, nSlots>::begin()
    const
{
    return const_iterator(this, 0);
}

template <class T, int32_t nSlots>
inline typename LFVector<T, nSlots>::const_iterator LFVector<T, nSlots>::end()
    const
{
    return const_iterator(this, size_);
}

template <class T, int32_t nSlots>
inline typename LFVector<T, nSlots>::iterator LFVector<T, nSlots>::begin()
{
    return iterator(this, 0);
}

template <class T, int32_t nSlots>
inline typename LFVector<T, nSlots>::iterator LFVector<T, nSlots>::end()
{
    return iterator(this, size_);
}

template <class T, int32_t nSlots>
template <class Archive>
inline void LFVector<T, nSlots>::save(Archive& ar,
                                      const unsigned int /*version*/) const
{
    ar << size_;
    for (size_t i = 0; i < size_; ++i)
        ar << operator[](i);
}

template <class T, int32_t nSlots>
template <class Archive>
inline void LFVector<T, nSlots>::load(Archive& ar,
                                      const unsigned int /*version*/)
{
    size_t newSize = 0;
    ar >> newSize;
    expand(newSize);
    LBASSERT(size_ == newSize);

    for (size_t i = 0; i < size_; ++i)
        ar >> operator[](i);
}
template <class T>
std::ostream& operator<<(std::ostream& os, const LFVector<T>& v)
{
    os << className(&v) << " size " << v.size() << " [ ";
    for (typename LFVector<T>::const_iterator i = v.begin(); i != v.end(); ++i)
    {
        if (i.getPosition() > 255)
        {
            os << "... ";
            break;
        }
        os << (*i) << ' ';
    }
    return os << ']' << std::endl;
}
}