2cda0dda2e7ebf75f0270a23008dd8242274b4b0
[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     Vector(const Vector&) = delete;
44     Vector& operator=(const Vector&) = delete;
45
46     Vector();
47     ~Vector();
48
49     T* begin() { return m_buffer; }
50     T* end() { return m_buffer + m_size; }
51
52     size_t size() { return m_size; }
53     size_t capacity() { return m_capacity; }
54     
55     T& operator[](size_t);
56     T& last() { return m_buffer[m_size - 1]; }
57
58     void push(const T&);
59     void push(const T*, const T*);
60     T pop();
61     T pop(size_t);
62     T pop(const T* it) { return pop(it - begin()); }
63
64     void shrink(size_t);
65
66 private:
67     static const size_t growFactor = 2;
68     static const size_t shrinkFactor = 4;
69     static const size_t initialCapacity = vmPageSize / sizeof(T);
70
71     void growCapacity(size_t size);
72     void shrinkCapacity();
73     void reallocateBuffer(size_t);
74
75     T* m_buffer;
76     size_t m_size;
77     size_t m_capacity;
78 };
79
80 template<typename T>
81 inline Vector<T>::Vector()
82     : m_buffer(0)
83     , m_size(0)
84     , m_capacity(0)
85 {
86 }
87
88 template<typename T>
89 Vector<T>::~Vector()
90 {
91     if (m_buffer)
92         vmDeallocate(m_buffer, vmSize(m_capacity * sizeof(T)));
93 }
94
95 template<typename T>
96 inline T& Vector<T>::operator[](size_t i)
97 {
98     BASSERT(i < m_size);
99     return m_buffer[i];
100 }
101
102 template<typename T>
103 INLINE void Vector<T>::push(const T& value)
104 {
105     if (m_size == m_capacity)
106         growCapacity(m_size);
107     m_buffer[m_size++] = value;
108 }
109
110 template<typename T>
111 void Vector<T>::push(const T* begin, const T* end)
112 {
113     size_t newSize = m_size + (end - begin);
114     if (newSize > m_capacity)
115         growCapacity(newSize);
116     std::memcpy(this->end(), begin, (end - begin) * sizeof(T));
117     m_size = newSize;
118 }
119
120 template<typename T>
121 inline T Vector<T>::pop()
122 {
123     BASSERT(m_size);
124     T value = m_buffer[m_size - 1];
125     shrink(m_size - 1);
126     return value;
127 }
128
129 template<typename T>
130 inline T Vector<T>::pop(size_t i)
131 {
132     BASSERT(i < m_size);
133     std::swap(m_buffer[i], last());
134     return pop();
135 }
136
137 template<typename T>
138 inline void Vector<T>::shrink(size_t size)
139 {
140     BASSERT(size <= m_size);
141     m_size = size;
142     if (m_capacity > initialCapacity && m_size < m_capacity / shrinkFactor)
143         shrinkCapacity();
144 }
145
146 template<typename T>
147 void Vector<T>::reallocateBuffer(size_t newCapacity)
148 {
149     size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
150     T* newBuffer = static_cast<T*>(vmAllocate(vmSize));
151     if (m_buffer) {
152         std::memcpy(newBuffer, m_buffer, m_size * sizeof(T));
153         vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
154     }
155
156     m_buffer = newBuffer;
157     m_capacity = vmSize / sizeof(T);
158 }
159
160 template<typename T>
161 NO_INLINE void Vector<T>::shrinkCapacity()
162 {
163     size_t newCapacity = max(initialCapacity, m_capacity / shrinkFactor);
164     reallocateBuffer(newCapacity);
165 }
166
167 template<typename T>
168 NO_INLINE void Vector<T>::growCapacity(size_t size)
169 {
170     size_t newCapacity = max(initialCapacity, size * growFactor);
171     reallocateBuffer(newCapacity);
172 }
173
174 } // namespace bmalloc
175
176 #endif // Vector_h