base/containers/PodVector.h

// Copyright 2014 The Android Open Source Project
//
// This software is licensed under the terms of the GNU General Public
// License version 2, as published by the Free Software Foundation, and
// may be copied, distributed, and modified under those terms.
//
// This program 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 General Public License for more details.

#ifndef ANDROID_BASE_CONTAINERS_POD_VECTOR_H
#define ANDROID_BASE_CONTAINERS_POD_VECTOR_H

#include <android/base/Limits.h>
#include <android/base/Log.h>

#include <stddef.h>
#include <stdint.h>

namespace android {
namespace base {

// A PodVector is a templated vector-like type that is used to store
// POD-struct compatible items only. This allows the implementation to
// use ::memmove() to move items, and also malloc_usable_size() to
// determine the best capacity.
//
// std::vector<> is capable of doing this in theory, using horrible
// templating tricks that make error messages very difficult to
// understand.
//
// Note that a PodVector can be used to store items that contain pointers,
// as long as these do not point to items in the same container.
//
// The PodVector provides methods that also follow the std::vector<>
// conventions, i.e. push_back() is an alias for append().
//

// PodVectorBase is a base, non-templated, implementation class that all
// PodVector instances derive from. This is used to reduce template
// specialization. Do not use directly, i..e it's an implementation detail.
class PodVectorBase {
protected:
    PodVectorBase() : mBegin(NULL), mEnd(NULL), mLimit(NULL) {}
    explicit PodVectorBase(const PodVectorBase& other);
    PodVectorBase& operator=(const PodVectorBase& other);
    ~PodVectorBase();

    bool empty() const { return mEnd == mBegin; }

    size_t byteSize() const { return mEnd - mBegin; }

    size_t byteCapacity() const { return mLimit - mBegin; }

    void* begin() { return mBegin; }
    const void* begin() const { return mBegin; }
    void* end() { return mEnd; }
    const void* end() const { return mEnd; }

    void* itemAt(size_t pos, size_t itemSize) {
        const size_t kMaxCapacity = SIZE_MAX / itemSize;
        DCHECK(pos <= kMaxCapacity);
        return mBegin + pos * itemSize;
    }

    const void* itemAt(size_t pos, size_t itemSize) const {
        const size_t kMaxCapacity = SIZE_MAX / itemSize;
        DCHECK(pos <= kMaxCapacity);
        return mBegin + pos * itemSize;
    }

    void assignFrom(const PodVectorBase& other);

    inline size_t itemCount(size_t itemSize) const {
        DCHECK(itemSize > 0) << "Item size cannot be 0!";
        return byteSize() / itemSize;
    }

    inline size_t itemCapacity(size_t itemSize) const {
        DCHECK(itemSize > 0) << "Item size cannot be 0!";
        return byteCapacity() / itemSize;
    }

    inline size_t maxItemCapacity(size_t itemSize) const {
        DCHECK(itemSize > 0) << "Item size cannot be 0!";
        return SIZE_MAX / itemSize;
    }

    void resize(size_t newSize, size_t itemSize);
    void reserve(size_t newSize, size_t itemSize);

    void removeAt(size_t index, size_t itemSize);
    void* insertAt(size_t index, size_t itemSize);
    void swapAll(PodVectorBase* other);

    char* mBegin;
    char* mEnd;
    char* mLimit;

private:
    void initFrom(const void* from, size_t fromLen);
};


// A PodVector<T> holds a vector (dynamically resizable array) or items
// that must be POD-struct compatible (i.e. they cannot have constructors,
// destructors, or virtual members). This allows the implementation to be
// small, fast and efficient, memory-wise.
//
// If you want to implement a vector of C++ objects, consider using
// std::vector<> instead, but keep in mind that this implies a non-trivial
// cost when appending, inserting, removing items in the collection.
//
template <typename T>
class PodVector : public PodVectorBase {
public:
    // Default constructor for an empty PodVector<T>
    PodVector() : PodVectorBase() {}

    // Copy constructor. This copies all items from |other| into
    // the new instance with ::memmove().
    PodVector(const PodVector& other) : PodVectorBase(other) {}

    // Assignment operator.
    PodVector& operator=(const PodVector& other) {
        this->assignFrom(other);
        return *this;
    }

    // Destructor, this simply releases the internal storage block that
    // holds all the items, but doesn't touch them otherwise.
    ~PodVector() {}

    // Return true iff the PodVector<T> instance is empty, i.e. does not
    // have any items.
    bool empty() const { return PodVectorBase::empty(); }

    // Return the number of items in the current PodVector<T> instance.
    size_t size() const { return PodVectorBase::itemCount(sizeof(T)); }

    // Return the current capacity in the current PodVector<T> instance.
    // Do not use directly, except if you know what you're doing. Try to
    // use resize() or reserve() instead.
    size_t capacity() const {
        return PodVectorBase::itemCapacity(sizeof(T));
    }

    // Return the maximum capacity of any PodVector<T> instance.
    static inline size_t maxCapacity() { return SIZE_MAX / sizeof(T); }

    // Resize the vector to ensure it can hold |newSize|
    // items. This may or may not call reserve() under the hood.
    // It's a fatal error to try to resize above maxCapacity().
    void resize(size_t newSize) {
        PodVectorBase::resize(newSize, sizeof(T));
    }

    // Resize the vector's storage array to ensure that it can hold at
    // least |newSize| items. It's a fatal error to try to resize above
    // maxCapacity().
    void reserve(size_t newSize) {
        PodVectorBase::reserve(newSize, sizeof(T));
    }

    // Return a pointer to the first item in the vector. This is only
    // valid until the next call to any function that changes the size
    // or capacity of the vector. Can be NULL if the vector is empty.
    T* begin() {
        return reinterpret_cast<T*>(PodVectorBase::begin());
    }

    // Return a constant pointer to the first item in the vector. This is
    // only valid until the next call to any function that changes the
    // size of capacity of the vector.
    const T* begin() const {
        return reinterpret_cast<T*>(PodVectorBase::begin());
    }

    // Return a pointer past the last item in the vector. I.e. if the
    // result is not NULL, then |result - 1| points to the last item.
    // Can be NULL if the vector is empty.
    T* end() {
        return reinterpret_cast<T*>(PodVectorBase::end());
    }

    // Return a constant pointer past the last item in the vector. I.e. if
    // the result is not NULL, then |result - 1| points to the last item.
    // Can be NULL if the vector is empty.
    const T* end() const {
        return reinterpret_cast<T*>(PodVectorBase::end());
    }

    // Returns a reference to the item a position |index| in the vector.
    // It may be a fatal error to access an out-of-bounds position.
    T& operator[](size_t index) {
        return *reinterpret_cast<T*>(
                PodVectorBase::itemAt(index, sizeof(T)));
    }

    const T& operator[](size_t index) const {
        return *reinterpret_cast<const T*>(
                PodVectorBase::itemAt(index, sizeof(T)));
    }

    // Increase the vector's size by 1, then move all items past a given
    // position to the right. Return the position of the insertion point
    // to let the caller copy the content it desires there. It's preferrable
    // to use insert() directly, which will do the item copy for you.
    T* emplace(size_t index) {
        return reinterpret_cast<T*>(
                PodVectorBase::insertAt(index, sizeof(T)));
    }

    // Insert an item at a given position. |index| is the insertion position
    // which must be between 0 and size() included, or a fatal error may
    // occur. |item| is a reference to an item to copy into the array,
    // byte-by-byte.
    void insert(size_t index, const T& item) {
        *(this->emplace(index)) = item;
    }

    // Prepend an item at the start of a vector. This moves all vector items
    // to the right, and is thus costly. |item| is a reference to an item
    // to copy to the start of the vector.
    void prepend(const T& item) {
        *(this->emplace(0U)) = item;
    }

    // Append an item at the end of a vector. Specialized version of insert()
    // which always uses size() as the insertion position.
    void append(const T& item) {
        *(this->emplace(this->size())) = item;
    }

    // Remove the item at a given position. |index| is the position of the
    // item to delete. It must be between 0 and size(), included, or
    // a fatal error may occur. Deleting the item at position size()
    // doesn't do anything.
    void remove(size_t index) {
        PodVectorBase::removeAt(index, sizeof(T));
    }

    void swap(PodVector* other) {
        PodVectorBase::swapAll(other);
    }

    // Compatibility methods for std::vector<>
    void push_back(const T& item) { append(item); }
    void pop() { remove(0U); }

    typedef T* iterator;
    typedef const T* const_iterator;
};

}  // namespace base
}  // namespace android


#endif  // ANDROID_BASE_VECTOR_H