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
30namespace kj {
31
32template <typename T>
33class 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
42public:
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
131private:
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
147template <typename T>
148inline auto KJ_STRINGIFY(const Vector<T>& v) -> decltype(toCharSequence(v.asPtr())) {
149 return toCharSequence(v.asPtr());
150}
151
152} // namespace kj
153