d257fc534377496ba982e8c618f2b0ab904f9f07
[WebKit.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 grow(size_t);
70     void shrink(size_t);
71
72     void shrinkToFit();
73
74 private:
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
88 template<typename T>
89 inline Vector<T>::Vector()
90     : m_buffer(0)
91     , m_size(0)
92     , m_capacity(0)
93 {
94 }
95
96 template<typename T>
97 Vector<T>::~Vector()
98 {
99     if (m_buffer)
100         vmDeallocate(m_buffer, vmSize(m_capacity * sizeof(T)));
101 }
102
103 template<typename T>
104 inline T& Vector<T>::operator[](size_t i)
105 {
106     BASSERT(i < m_size);
107     return m_buffer[i];
108 }
109
110 template<typename T>
111 INLINE void Vector<T>::push(const T& value)
112 {
113     if (m_size == m_capacity)
114         growCapacity();
115     m_buffer[m_size++] = value;
116 }
117
118 template<typename T>
119 inline T Vector<T>::pop()
120 {
121     BASSERT(m_size);
122     T value = m_buffer[m_size - 1];
123     shrink(m_size - 1);
124     return value;
125 }
126
127 template<typename T>
128 inline T Vector<T>::pop(size_t i)
129 {
130     BASSERT(i < m_size);
131     std::swap(m_buffer[i], last());
132     return pop();
133 }
134
135 template<typename T>
136 void Vector<T>::insert(iterator it, const T& value)
137 {
138     size_t index = it - begin();
139     size_t moveCount = end() - it;
140
141     if (m_size == m_capacity)
142         growCapacity();
143
144     std::memmove(&m_buffer[index + 1], &m_buffer[index], moveCount * sizeof(T));
145     m_buffer[index] = value;
146     m_size++;
147 }
148
149 template<typename T>
150 inline void Vector<T>::grow(size_t size)
151 {
152     BASSERT(size >= m_size);
153     while (m_size < size)
154         push(T());
155 }
156
157 template<typename T>
158 inline void Vector<T>::shrink(size_t size)
159 {
160     BASSERT(size <= m_size);
161     m_size = size;
162     if (m_size < m_capacity / shrinkFactor && m_capacity > initialCapacity())
163         shrinkCapacity();
164 }
165
166 template<typename T>
167 void Vector<T>::reallocateBuffer(size_t newCapacity)
168 {
169     size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
170     T* newBuffer = vmSize ? static_cast<T*>(vmAllocate(vmSize)) : nullptr;
171     if (m_buffer) {
172         std::memcpy(newBuffer, m_buffer, m_size * sizeof(T));
173         vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
174     }
175
176     m_buffer = newBuffer;
177     m_capacity = vmSize / sizeof(T);
178 }
179
180 template<typename T>
181 NO_INLINE void Vector<T>::shrinkCapacity()
182 {
183     size_t newCapacity = max(initialCapacity(), m_capacity / shrinkFactor);
184     reallocateBuffer(newCapacity);
185 }
186
187 template<typename T>
188 NO_INLINE void Vector<T>::growCapacity()
189 {
190     size_t newCapacity = max(initialCapacity(), m_size * growFactor);
191     reallocateBuffer(newCapacity);
192 }
193
194 template<typename T>
195 void Vector<T>::shrinkToFit()
196 {
197     if (m_size < m_capacity)
198         reallocateBuffer(m_size);
199 }
200
201 } // namespace bmalloc
202
203 #endif // Vector_h