1// Copyright 2014 The Android Open Source Project
2//
3// This software is licensed under the terms of the GNU General Public
4// License version 2, as published by the Free Software Foundation, and
5// may be copied, distributed, and modified under those terms.
6//
7// This program is distributed in the hope that it will be useful,
8// but WITHOUT ANY WARRANTY; without even the implied warranty of
9// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10// GNU General Public License for more details.
11
12#ifndef ANDROID_BASE_CONTAINERS_POD_VECTOR_H
13#define ANDROID_BASE_CONTAINERS_POD_VECTOR_H
14
15#include <android/base/Limits.h>
16#include <android/base/Log.h>
17
18#include <stddef.h>
19#include <stdint.h>
20
21namespace android {
22namespace base {
23
24// A PodVector is a templated vector-like type that is used to store
25// POD-struct compatible items only. This allows the implementation to
26// use ::memmove() to move items, and also malloc_usable_size() to
27// determine the best capacity.
28//
29// std::vector<> is capable of doing this in theory, using horrible
30// templating tricks that make error messages very difficult to
31// understand.
32//
33// Note that a PodVector can be used to store items that contain pointers,
34// as long as these do not point to items in the same container.
35//
36// The PodVector provides methods that also follow the std::vector<>
37// conventions, i.e. push_back() is an alias for append().
38//
39
40// PodVectorBase is a base, non-templated, implementation class that all
41// PodVector instances derive from. This is used to reduce template
42// specialization. Do not use directly, i..e it's an implementation detail.
43class PodVectorBase {
44protected:
45    PodVectorBase() : mBegin(NULL), mEnd(NULL), mLimit(NULL) {}
46    explicit PodVectorBase(const PodVectorBase& other);
47    PodVectorBase& operator=(const PodVectorBase& other);
48    ~PodVectorBase();
49
50    bool empty() const { return mEnd == mBegin; }
51
52    size_t byteSize() const { return mEnd - mBegin; }
53
54    size_t byteCapacity() const { return mLimit - mBegin; }
55
56    void* begin() { return mBegin; }
57    const void* begin() const { return mBegin; }
58    void* end() { return mEnd; }
59    const void* end() const { return mEnd; }
60
61    void* itemAt(size_t pos, size_t itemSize) {
62        const size_t kMaxCapacity = SIZE_MAX / itemSize;
63        DCHECK(pos <= kMaxCapacity);
64        return mBegin + pos * itemSize;
65    }
66
67    const void* itemAt(size_t pos, size_t itemSize) const {
68        const size_t kMaxCapacity = SIZE_MAX / itemSize;
69        DCHECK(pos <= kMaxCapacity);
70        return mBegin + pos * itemSize;
71    }
72
73    void assignFrom(const PodVectorBase& other);
74
75    inline size_t itemCount(size_t itemSize) const {
76        DCHECK(itemSize > 0) << "Item size cannot be 0!";
77        return byteSize() / itemSize;
78    }
79
80    inline size_t itemCapacity(size_t itemSize) const {
81        DCHECK(itemSize > 0) << "Item size cannot be 0!";
82        return byteCapacity() / itemSize;
83    }
84
85    inline size_t maxItemCapacity(size_t itemSize) const {
86        DCHECK(itemSize > 0) << "Item size cannot be 0!";
87        return SIZE_MAX / itemSize;
88    }
89
90    void resize(size_t newSize, size_t itemSize);
91    void reserve(size_t newSize, size_t itemSize);
92
93    void removeAt(size_t index, size_t itemSize);
94    void* insertAt(size_t index, size_t itemSize);
95    void swapAll(PodVectorBase* other);
96
97    char* mBegin;
98    char* mEnd;
99    char* mLimit;
100
101private:
102    void initFrom(const void* from, size_t fromLen);
103};
104
105
106// A PodVector<T> holds a vector (dynamically resizable array) or items
107// that must be POD-struct compatible (i.e. they cannot have constructors,
108// destructors, or virtual members). This allows the implementation to be
109// small, fast and efficient, memory-wise.
110//
111// If you want to implement a vector of C++ objects, consider using
112// std::vector<> instead, but keep in mind that this implies a non-trivial
113// cost when appending, inserting, removing items in the collection.
114//
115template <typename T>
116class PodVector : public PodVectorBase {
117public:
118    // Default constructor for an empty PodVector<T>
119    PodVector() : PodVectorBase() {}
120
121    // Copy constructor. This copies all items from |other| into
122    // the new instance with ::memmove().
123    PodVector(const PodVector& other) : PodVectorBase(other) {}
124
125    // Assignment operator.
126    PodVector& operator=(const PodVector& other) {
127        this->assignFrom(other);
128        return *this;
129    }
130
131    // Destructor, this simply releases the internal storage block that
132    // holds all the items, but doesn't touch them otherwise.
133    ~PodVector() {}
134
135    // Return true iff the PodVector<T> instance is empty, i.e. does not
136    // have any items.
137    bool empty() const { return PodVectorBase::empty(); }
138
139    // Return the number of items in the current PodVector<T> instance.
140    size_t size() const { return PodVectorBase::itemCount(sizeof(T)); }
141
142    // Return the current capacity in the current PodVector<T> instance.
143    // Do not use directly, except if you know what you're doing. Try to
144    // use resize() or reserve() instead.
145    size_t capacity() const {
146        return PodVectorBase::itemCapacity(sizeof(T));
147    }
148
149    // Return the maximum capacity of any PodVector<T> instance.
150    static inline size_t maxCapacity() { return SIZE_MAX / sizeof(T); }
151
152    // Resize the vector to ensure it can hold |newSize|
153    // items. This may or may not call reserve() under the hood.
154    // It's a fatal error to try to resize above maxCapacity().
155    void resize(size_t newSize) {
156        PodVectorBase::resize(newSize, sizeof(T));
157    }
158
159    // Resize the vector's storage array to ensure that it can hold at
160    // least |newSize| items. It's a fatal error to try to resize above
161    // maxCapacity().
162    void reserve(size_t newSize) {
163        PodVectorBase::reserve(newSize, sizeof(T));
164    }
165
166    // Return a pointer to the first item in the vector. This is only
167    // valid until the next call to any function that changes the size
168    // or capacity of the vector. Can be NULL if the vector is empty.
169    T* begin() {
170        return reinterpret_cast<T*>(PodVectorBase::begin());
171    }
172
173    // Return a constant pointer to the first item in the vector. This is
174    // only valid until the next call to any function that changes the
175    // size of capacity of the vector.
176    const T* begin() const {
177        return reinterpret_cast<T*>(PodVectorBase::begin());
178    }
179
180    // Return a pointer past the last item in the vector. I.e. if the
181    // result is not NULL, then |result - 1| points to the last item.
182    // Can be NULL if the vector is empty.
183    T* end() {
184        return reinterpret_cast<T*>(PodVectorBase::end());
185    }
186
187    // Return a constant pointer past the last item in the vector. I.e. if
188    // the result is not NULL, then |result - 1| points to the last item.
189    // Can be NULL if the vector is empty.
190    const T* end() const {
191        return reinterpret_cast<T*>(PodVectorBase::end());
192    }
193
194    // Returns a reference to the item a position |index| in the vector.
195    // It may be a fatal error to access an out-of-bounds position.
196    T& operator[](size_t index) {
197        return *reinterpret_cast<T*>(
198                PodVectorBase::itemAt(index, sizeof(T)));
199    }
200
201    const T& operator[](size_t index) const {
202        return *reinterpret_cast<const T*>(
203                PodVectorBase::itemAt(index, sizeof(T)));
204    }
205
206    // Increase the vector's size by 1, then move all items past a given
207    // position to the right. Return the position of the insertion point
208    // to let the caller copy the content it desires there. It's preferrable
209    // to use insert() directly, which will do the item copy for you.
210    T* emplace(size_t index) {
211        return reinterpret_cast<T*>(
212                PodVectorBase::insertAt(index, sizeof(T)));
213    }
214
215    // Insert an item at a given position. |index| is the insertion position
216    // which must be between 0 and size() included, or a fatal error may
217    // occur. |item| is a reference to an item to copy into the array,
218    // byte-by-byte.
219    void insert(size_t index, const T& item) {
220        *(this->emplace(index)) = item;
221    }
222
223    // Prepend an item at the start of a vector. This moves all vector items
224    // to the right, and is thus costly. |item| is a reference to an item
225    // to copy to the start of the vector.
226    void prepend(const T& item) {
227        *(this->emplace(0U)) = item;
228    }
229
230    // Append an item at the end of a vector. Specialized version of insert()
231    // which always uses size() as the insertion position.
232    void append(const T& item) {
233        *(this->emplace(this->size())) = item;
234    }
235
236    // Remove the item at a given position. |index| is the position of the
237    // item to delete. It must be between 0 and size(), included, or
238    // a fatal error may occur. Deleting the item at position size()
239    // doesn't do anything.
240    void remove(size_t index) {
241        PodVectorBase::removeAt(index, sizeof(T));
242    }
243
244    void swap(PodVector* other) {
245        PodVectorBase::swapAll(other);
246    }
247
248    // Compatibility methods for std::vector<>
249    void push_back(const T& item) { append(item); }
250    void pop() { remove(0U); }
251
252    typedef T* iterator;
253    typedef const T* const_iterator;
254};
255
256}  // namespace base
257}  // namespace android
258
259
260#endif  // ANDROID_BASE_VECTOR_H
261