1/*
2 * Copyright (C) 2014-2017 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 FixedVector_h
27#define FixedVector_h
28
29#include "BAssert.h"
30#include <array>
31#include <cstddef>
32#include <type_traits>
33
34namespace bmalloc {
35
36// A replacement for std::vector that uses a fixed-sized inline backing store.
37
38template<typename T, size_t Capacity>
39class FixedVector {
40 static_assert(std::is_trivially_destructible<T>::value, "FixedVector must have a trivial destructor.");
41public:
42 FixedVector();
43
44 const T* begin() const { return &m_buffer[0]; }
45 const T* end() const { return begin() + size(); }
46
47 size_t size() const { return m_size; }
48 size_t capacity() const { return Capacity; }
49
50 T& operator[](size_t);
51
52 void push(const T&);
53 void push(const T*, const T*);
54 T pop();
55
56 void shrink(T*);
57 void shrink(size_t);
58
59 void clear() { shrink(static_cast<size_t>(0)); }
60 bool isEmpty() { return !m_size; }
61
62private:
63 size_t m_size;
64 std::array<T, Capacity> m_buffer;
65};
66
67template<typename T, size_t Capacity>
68inline FixedVector<T, Capacity>::FixedVector()
69 : m_size(0)
70{
71}
72
73template<typename T, size_t Capacity>
74inline T& FixedVector<T, Capacity>::operator[](size_t i)
75{
76 BASSERT(i < m_size);
77 return m_buffer[i];
78}
79
80template<typename T, size_t Capacity>
81inline void FixedVector<T, Capacity>::push(const T& value)
82{
83 BASSERT(m_size < Capacity);
84 m_buffer[m_size++] = value;
85}
86
87template<typename T, size_t Capacity>
88inline void FixedVector<T, Capacity>::push(const T* begin, const T* end)
89{
90 for (const T* it = begin; it != end; ++it)
91 push(*it);
92}
93
94template<typename T, size_t Capacity>
95inline T FixedVector<T, Capacity>::pop()
96{
97 BASSERT(m_size);
98 return m_buffer[--m_size];
99}
100
101template<typename T, size_t Capacity>
102inline void FixedVector<T, Capacity>::shrink(size_t size)
103{
104 BASSERT(size <= m_size);
105 m_size = size;
106}
107
108template<typename T, size_t Capacity>
109inline void FixedVector<T, Capacity>::shrink(T* end)
110{
111 shrink(end - begin());
112}
113
114} // namespace bmalloc
115
116#endif // FixedVector_h
117