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