Unreviewed, rolling out r197955.
[WebKit-https.git] / Source / bmalloc / bmalloc / Vector.h
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 "Inline.h"
30 #include "VMAllocate.h"
31 #include <cstddef>
32 #include <cstring>
33
34 namespace 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
39 template<typename T>
40 class Vector {
41     static_assert(std::is_trivially_destructible<T>::value, "Vector must have a trivial destructor.");
42 public:
43     typedef T* iterator;
44     typedef const T* const_iterator;
45
46     Vector(const Vector&) = delete;
47     Vector& operator=(const Vector&) = delete;
48
49     Vector();
50     ~Vector();
51
52     iterator begin() { return m_buffer; }
53     iterator end() { return m_buffer + m_size; }
54
55     size_t size() { return m_size; }
56     size_t capacity() { return m_capacity; }
57     
58     T& operator[](size_t);
59     T& last() { return m_buffer[m_size - 1]; }
60
61     void push(const T&);
62
63     T pop();
64     T pop(size_t);
65     T pop(const_iterator it) { return pop(it - begin()); }
66     
67     void insert(iterator, const T&);
68
69     void shrink(size_t);
70
71     void shrinkToFit();
72
73 private:
74     static const size_t growFactor = 2;
75     static const size_t shrinkFactor = 4;
76     static const size_t initialCapacity = vmPageSize / sizeof(T);
77
78     void growCapacity();
79     void shrinkCapacity();
80     void reallocateBuffer(size_t);
81
82     T* m_buffer;
83     size_t m_size;
84     size_t m_capacity;
85 };
86
87 template<typename T>
88 inline Vector<T>::Vector()
89     : m_buffer(0)
90     , m_size(0)
91     , m_capacity(0)
92 {
93 }
94
95 template<typename T>
96 Vector<T>::~Vector()
97 {
98     if (m_buffer)
99         vmDeallocate(m_buffer, vmSize(m_capacity * sizeof(T)));
100 }
101
102 template<typename T>
103 inline T& Vector<T>::operator[](size_t i)
104 {
105     BASSERT(i < m_size);
106     return m_buffer[i];
107 }
108
109 template<typename T>
110 INLINE void Vector<T>::push(const T& value)
111 {
112     if (m_size == m_capacity)
113         growCapacity();
114     m_buffer[m_size++] = value;
115 }
116
117 template<typename T>
118 inline T Vector<T>::pop()
119 {
120     BASSERT(m_size);
121     T value = m_buffer[m_size - 1];
122     shrink(m_size - 1);
123     return value;
124 }
125
126 template<typename T>
127 inline T Vector<T>::pop(size_t i)
128 {
129     BASSERT(i < m_size);
130     std::swap(m_buffer[i], last());
131     return pop();
132 }
133
134 template<typename T>
135 void Vector<T>::insert(iterator it, const T& value)
136 {
137     size_t index = it - begin();
138     size_t moveCount = end() - it;
139
140     if (m_size == m_capacity)
141         growCapacity();
142
143     std::memmove(&m_buffer[index + 1], &m_buffer[index], moveCount * sizeof(T));
144     m_buffer[index] = value;
145     m_size++;
146 }
147
148 template<typename T>
149 inline void Vector<T>::shrink(size_t size)
150 {
151     BASSERT(size <= m_size);
152     m_size = size;
153     if (m_capacity > initialCapacity && m_size < m_capacity / shrinkFactor)
154         shrinkCapacity();
155 }
156
157 template<typename T>
158 void Vector<T>::reallocateBuffer(size_t newCapacity)
159 {
160     size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
161     T* newBuffer = vmSize ? static_cast<T*>(vmAllocate(vmSize)) : nullptr;
162     if (m_buffer) {
163         std::memcpy(newBuffer, m_buffer, m_size * sizeof(T));
164         vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
165     }
166
167     m_buffer = newBuffer;
168     m_capacity = vmSize / sizeof(T);
169 }
170
171 template<typename T>
172 NO_INLINE void Vector<T>::shrinkCapacity()
173 {
174     size_t newCapacity = max(initialCapacity, m_capacity / shrinkFactor);
175     reallocateBuffer(newCapacity);
176 }
177
178 template<typename T>
179 NO_INLINE void Vector<T>::growCapacity()
180 {
181     size_t newCapacity = max(initialCapacity, m_size * growFactor);
182     reallocateBuffer(newCapacity);
183 }
184
185 template<typename T>
186 void Vector<T>::shrinkToFit()
187 {
188     if (m_size < m_capacity)
189         reallocateBuffer(m_size);
190 }
191
192 } // namespace bmalloc
193
194 #endif // Vector_h