1/*
2 * Copyright (C) 2014 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef Vector_h
27#define Vector_h
28
29#include "BInline.h"
30#include "VMAllocate.h"
31#include <cstddef>
32#include <cstring>
33
34namespace bmalloc {
35
36// A replacement for std::vector that allocates using vmAllocate instead of
37// malloc, shrinks automatically, and supports "popping" from the middle.
38
39template<typename T>
40class Vector {
41 static_assert(std::is_trivially_destructible<T>::value, "Vector must have a trivial destructor.");
42public:
43 typedef T* iterator;
44 typedef const T* const_iterator;
45
46 Vector();
47 Vector(Vector&&);
48 ~Vector();
49
50 iterator begin() { return m_buffer; }
51 iterator end() { return m_buffer + m_size; }
52
53 size_t size() { return m_size; }
54 size_t capacity() { return m_capacity; }
55
56 T& operator[](size_t);
57 T& last() { return m_buffer[m_size - 1]; }
58
59 void push(const T&);
60
61 T pop();
62 T pop(size_t);
63 T pop(const_iterator it) { return pop(it - begin()); }
64
65 void insert(iterator, const T&);
66 T remove(iterator);
67
68 void grow(size_t);
69 void shrink(size_t);
70 void resize(size_t);
71
72 void shrinkToFit();
73
74private:
75 static const size_t growFactor = 2;
76 static const size_t shrinkFactor = 4;
77 static size_t initialCapacity() { return vmPageSize() / sizeof(T); }
78
79 void growCapacity();
80 void shrinkCapacity();
81 void reallocateBuffer(size_t);
82
83 T* m_buffer;
84 size_t m_size;
85 size_t m_capacity;
86};
87
88template<typename T>
89inline Vector<T>::Vector()
90 : m_buffer(nullptr)
91 , m_size(0)
92 , m_capacity(0)
93{
94}
95
96template<typename T>
97inline Vector<T>::Vector(Vector&& other)
98 : m_buffer(other.m_buffer)
99 , m_size(other.m_size)
100 , m_capacity(other.m_capacity)
101{
102 other.m_buffer = nullptr;
103 other.m_size = 0;
104 other.m_capacity = 0;
105}
106
107template<typename T>
108Vector<T>::~Vector()
109{
110 if (m_buffer)
111 vmDeallocate(m_buffer, vmSize(m_capacity * sizeof(T)));
112}
113
114template<typename T>
115inline T& Vector<T>::operator[](size_t i)
116{
117 BASSERT(i < m_size);
118 return m_buffer[i];
119}
120
121template<typename T>
122BINLINE void Vector<T>::push(const T& value)
123{
124 if (m_size == m_capacity)
125 growCapacity();
126 m_buffer[m_size++] = value;
127}
128
129template<typename T>
130inline T Vector<T>::pop()
131{
132 BASSERT(m_size);
133 T value = m_buffer[m_size - 1];
134 shrink(m_size - 1);
135 return value;
136}
137
138template<typename T>
139inline T Vector<T>::pop(size_t i)
140{
141 BASSERT(i < m_size);
142 std::swap(m_buffer[i], last());
143 return pop();
144}
145
146template<typename T>
147void Vector<T>::insert(iterator it, const T& value)
148{
149 size_t index = it - begin();
150 size_t moveCount = end() - it;
151
152 grow(m_size + 1);
153 std::memmove(&m_buffer[index + 1], &m_buffer[index], moveCount * sizeof(T));
154
155 m_buffer[index] = value;
156}
157
158template<typename T>
159T Vector<T>::remove(iterator it)
160{
161 size_t index = it - begin();
162 size_t moveCount = end() - it - 1;
163
164 T result = *it;
165
166 std::memmove(&m_buffer[index], &m_buffer[index + 1], moveCount * sizeof(T));
167 shrink(m_size - 1);
168
169 return result;
170}
171
172template<typename T>
173inline void Vector<T>::grow(size_t size)
174{
175 BASSERT(size >= m_size);
176 while (m_size < size)
177 push(T());
178}
179
180template<typename T>
181inline void Vector<T>::shrink(size_t size)
182{
183 BASSERT(size <= m_size);
184 m_size = size;
185 if (m_size < m_capacity / shrinkFactor && m_capacity > initialCapacity())
186 shrinkCapacity();
187}
188
189template<typename T>
190inline void Vector<T>::resize(size_t size)
191{
192 if (size <= m_size)
193 shrink(size);
194 else
195 grow(size);
196}
197
198template<typename T>
199void Vector<T>::reallocateBuffer(size_t newCapacity)
200{
201 RELEASE_BASSERT(newCapacity < std::numeric_limits<size_t>::max() / sizeof(T));
202
203 size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
204 T* newBuffer = vmSize ? static_cast<T*>(vmAllocate(vmSize)) : nullptr;
205 if (m_buffer) {
206 std::memcpy(newBuffer, m_buffer, m_size * sizeof(T));
207 vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
208 }
209
210 m_buffer = newBuffer;
211 m_capacity = vmSize / sizeof(T);
212}
213
214template<typename T>
215BNO_INLINE void Vector<T>::shrinkCapacity()
216{
217 size_t newCapacity = max(initialCapacity(), m_capacity / shrinkFactor);
218 reallocateBuffer(newCapacity);
219}
220
221template<typename T>
222BNO_INLINE void Vector<T>::growCapacity()
223{
224 size_t newCapacity = max(initialCapacity(), m_size * growFactor);
225 reallocateBuffer(newCapacity);
226}
227
228template<typename T>
229void Vector<T>::shrinkToFit()
230{
231 if (m_size < m_capacity)
232 reallocateBuffer(m_size);
233}
234
235} // namespace bmalloc
236
237#endif // Vector_h
238