bmalloc
[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 <string>
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;
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     vmDeallocate(m_buffer, vmSize(m_capacity * sizeof(T)));
92 }
93
94 template<typename T>
95 inline T& Vector<T>::operator[](size_t i)
96 {
97     ASSERT(i < m_size);
98     return m_buffer[i];
99 }
100
101 template<typename T>
102 INLINE void Vector<T>::push(const T& value)
103 {
104     if (m_size == m_capacity)
105         growCapacity(m_size);
106     m_buffer[m_size++] = value;
107 }
108
109 template<typename T>
110 void Vector<T>::push(const T* begin, const T* end)
111 {
112     size_t newSize = m_size + (end - begin);
113     if (newSize > m_capacity)
114         growCapacity(newSize);
115     memcpy(this->end(), begin, (end - begin) * sizeof(T));
116     m_size = newSize;
117 }
118
119 template<typename T>
120 inline T Vector<T>::pop()
121 {
122     ASSERT(m_size);
123     T value = m_buffer[m_size - 1];
124     shrink(m_size - 1);
125     return value;
126 }
127
128 template<typename T>
129 inline T Vector<T>::pop(size_t i)
130 {
131     ASSERT(i < m_size);
132     std::swap(m_buffer[i], last());
133     return pop();
134 }
135
136 template<typename T>
137 inline void Vector<T>::shrink(size_t size)
138 {
139     ASSERT(size <= m_size);
140     m_size = size;
141     if (m_capacity > initialCapacity && m_size < m_capacity / shrinkFactor)
142         shrinkCapacity();
143 }
144
145 template<typename T>
146 void Vector<T>::reallocateBuffer(size_t newCapacity)
147 {
148     size_t vmSize = bmalloc::vmSize(newCapacity * sizeof(T));
149     T* newBuffer = static_cast<T*>(vmAllocate(vmSize));
150     if (m_buffer) {
151         memcpy(newBuffer, m_buffer, m_size * sizeof(T));
152         vmDeallocate(m_buffer, bmalloc::vmSize(m_capacity * sizeof(T)));
153     }
154
155     m_buffer = newBuffer;
156     m_capacity = vmSize / sizeof(T);
157 }
158
159 template<typename T>
160 NO_INLINE void Vector<T>::shrinkCapacity()
161 {
162     size_t newCapacity = max(initialCapacity, m_capacity / shrinkFactor);
163     reallocateBuffer(newCapacity);
164 }
165
166 template<typename T>
167 NO_INLINE void Vector<T>::growCapacity(size_t size)
168 {
169     size_t newCapacity = max(initialCapacity, size * growFactor);
170     reallocateBuffer(newCapacity);
171 }
172
173 } // namespace bmalloc
174
175 #endif // Vector_h