1 | // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors |
2 | // Licensed under the MIT License: |
3 | // |
4 | // Permission is hereby granted, free of charge, to any person obtaining a copy |
5 | // of this software and associated documentation files (the "Software"), to deal |
6 | // in the Software without restriction, including without limitation the rights |
7 | // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
8 | // copies of the Software, and to permit persons to whom the Software is |
9 | // furnished to do so, subject to the following conditions: |
10 | // |
11 | // The above copyright notice and this permission notice shall be included in |
12 | // all copies or substantial portions of the Software. |
13 | // |
14 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
15 | // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
16 | // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
17 | // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
18 | // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
19 | // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
20 | // THE SOFTWARE. |
21 | |
22 | #pragma once |
23 | |
24 | #if defined(__GNUC__) && !KJ_HEADER_WARNINGS |
25 | #pragma GCC system_header |
26 | #endif |
27 | |
28 | #include "array.h" |
29 | |
30 | namespace kj { |
31 | |
32 | template <typename T> |
33 | class Vector { |
34 | // Similar to std::vector, but based on KJ framework. |
35 | // |
36 | // This implementation always uses move constructors when growing the backing array. If the |
37 | // move constructor throws, the Vector is left in an inconsistent state. This is acceptable |
38 | // under KJ exception theory which assumes that exceptions leave things in inconsistent states. |
39 | |
40 | // TODO(someday): Allow specifying a custom allocator. |
41 | |
42 | public: |
43 | inline Vector() = default; |
44 | inline explicit Vector(size_t capacity): builder(heapArrayBuilder<T>(capacity)) {} |
45 | inline Vector(Array<T>&& array): builder(kj::mv(array)) {} |
46 | |
47 | inline operator ArrayPtr<T>() { return builder; } |
48 | inline operator ArrayPtr<const T>() const { return builder; } |
49 | inline ArrayPtr<T> asPtr() { return builder.asPtr(); } |
50 | inline ArrayPtr<const T> asPtr() const { return builder.asPtr(); } |
51 | |
52 | inline size_t size() const { return builder.size(); } |
53 | inline bool empty() const { return size() == 0; } |
54 | inline size_t capacity() const { return builder.capacity(); } |
55 | inline T& operator[](size_t index) const { return builder[index]; } |
56 | |
57 | inline const T* begin() const { return builder.begin(); } |
58 | inline const T* end() const { return builder.end(); } |
59 | inline const T& front() const { return builder.front(); } |
60 | inline const T& back() const { return builder.back(); } |
61 | inline T* begin() { return builder.begin(); } |
62 | inline T* end() { return builder.end(); } |
63 | inline T& front() { return builder.front(); } |
64 | inline T& back() { return builder.back(); } |
65 | |
66 | inline Array<T> releaseAsArray() { |
67 | // TODO(perf): Avoid a copy/move by allowing Array<T> to point to incomplete space? |
68 | if (!builder.isFull()) { |
69 | setCapacity(size()); |
70 | } |
71 | return builder.finish(); |
72 | } |
73 | |
74 | template <typename U> |
75 | inline bool operator==(const U& other) const { return asPtr() == other; } |
76 | template <typename U> |
77 | inline bool operator!=(const U& other) const { return asPtr() != other; } |
78 | |
79 | inline ArrayPtr<T> slice(size_t start, size_t end) { |
80 | return asPtr().slice(start, end); |
81 | } |
82 | inline ArrayPtr<const T> slice(size_t start, size_t end) const { |
83 | return asPtr().slice(start, end); |
84 | } |
85 | |
86 | template <typename... Params> |
87 | inline T& add(Params&&... params) { |
88 | if (builder.isFull()) grow(); |
89 | return builder.add(kj::fwd<Params>(params)...); |
90 | } |
91 | |
92 | template <typename Iterator> |
93 | inline void addAll(Iterator begin, Iterator end) { |
94 | size_t needed = builder.size() + (end - begin); |
95 | if (needed > builder.capacity()) grow(needed); |
96 | builder.addAll(begin, end); |
97 | } |
98 | |
99 | template <typename Container> |
100 | inline void addAll(Container&& container) { |
101 | addAll(container.begin(), container.end()); |
102 | } |
103 | |
104 | inline void removeLast() { |
105 | builder.removeLast(); |
106 | } |
107 | |
108 | inline void resize(size_t size) { |
109 | if (size > builder.capacity()) grow(size); |
110 | builder.resize(size); |
111 | } |
112 | |
113 | inline void operator=(decltype(nullptr)) { |
114 | builder = nullptr; |
115 | } |
116 | |
117 | inline void clear() { |
118 | builder.clear(); |
119 | } |
120 | |
121 | inline void truncate(size_t size) { |
122 | builder.truncate(size); |
123 | } |
124 | |
125 | inline void reserve(size_t size) { |
126 | if (size > builder.capacity()) { |
127 | setCapacity(size); |
128 | } |
129 | } |
130 | |
131 | private: |
132 | ArrayBuilder<T> builder; |
133 | |
134 | void grow(size_t minCapacity = 0) { |
135 | setCapacity(kj::max(minCapacity, capacity() == 0 ? 4 : capacity() * 2)); |
136 | } |
137 | void setCapacity(size_t newSize) { |
138 | if (builder.size() > newSize) { |
139 | builder.truncate(newSize); |
140 | } |
141 | ArrayBuilder<T> newBuilder = heapArrayBuilder<T>(newSize); |
142 | newBuilder.addAll(kj::mv(builder)); |
143 | builder = kj::mv(newBuilder); |
144 | } |
145 | }; |
146 | |
147 | template <typename T> |
148 | inline auto KJ_STRINGIFY(const Vector<T>& v) -> decltype(toCharSequence(v.asPtr())) { |
149 | return toCharSequence(v.asPtr()); |
150 | } |
151 | |
152 | } // namespace kj |
153 | |