1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#pragma once
10
11#include <immer/detail/arrays/no_capacity.hpp>
12
13namespace immer {
14namespace detail {
15namespace arrays {
16
17template <typename T, typename MemoryPolicy>
18struct with_capacity
19{
20 using no_capacity_t = no_capacity<T, MemoryPolicy>;
21
22 using node_t = node<T, MemoryPolicy>;
23 using edit_t = typename MemoryPolicy::transience_t::edit;
24 using size_t = std::size_t;
25
26 node_t* ptr;
27 size_t size;
28 size_t capacity;
29
30 static const with_capacity& empty()
31 {
32 static const with_capacity empty_ {
33 node_t::make_n(1),
34 0,
35 1
36 };
37 return empty_;
38 }
39
40 with_capacity(node_t* p, size_t s, size_t c)
41 : ptr{p}, size{s}, capacity{c}
42 {}
43
44 with_capacity(const with_capacity& other)
45 : with_capacity{other.ptr, other.size, other.capacity}
46 {
47 inc();
48 }
49
50 with_capacity(const no_capacity_t& other)
51 : with_capacity{other.ptr, other.size, other.size}
52 {
53 inc();
54 }
55
56 with_capacity(with_capacity&& other)
57 : with_capacity{empty()}
58 {
59 swap(*this, other);
60 }
61
62 with_capacity& operator=(const with_capacity& other)
63 {
64 auto next = other;
65 swap(*this, next);
66 return *this;
67 }
68
69 with_capacity& operator=(with_capacity&& other)
70 {
71 swap(*this, other);
72 return *this;
73 }
74
75 friend void swap(with_capacity& x, with_capacity& y)
76 {
77 using std::swap;
78 swap(x.ptr, y.ptr);
79 swap(x.size, y.size);
80 swap(x.capacity, y.capacity);
81 }
82
83 ~with_capacity()
84 {
85 dec();
86 }
87
88 void inc()
89 {
90 using immer::detail::get;
91 ptr->refs().inc();
92 }
93
94 void dec()
95 {
96 using immer::detail::get;
97 if (ptr->refs().dec())
98 node_t::delete_n(ptr, size, capacity);
99 }
100
101 const T* data() const { return ptr->data(); }
102 T* data() { return ptr->data(); }
103
104 T* data_mut(edit_t e)
105 {
106 if (!ptr->can_mutate(e)) {
107 auto p = node_t::copy_e(e, capacity, ptr, size);
108 dec();
109 ptr = p;
110 }
111 return data();
112 }
113
114 operator no_capacity_t() const
115 {
116 if (size == capacity) {
117 ptr->refs().inc();
118 return { ptr, size };
119 } else {
120 return { node_t::copy_n(size, ptr, size), size };
121 }
122 }
123
124 template <typename Iter, typename Sent,
125 std::enable_if_t
126 <is_forward_iterator_v<Iter>
127 && compatible_sentinel_v<Iter, Sent>, bool> = true>
128 static with_capacity from_range(Iter first, Sent last)
129 {
130 auto count = static_cast<size_t>(distance(first, last));
131 return {
132 node_t::copy_n(count, first, last),
133 count,
134 count
135 };
136 }
137
138 template <typename U>
139 static with_capacity from_initializer_list(std::initializer_list<U> values)
140 {
141 using namespace std;
142 return from_range(begin(values), end(values));
143 }
144
145 static with_capacity from_fill(size_t n, T v)
146 {
147 return { node_t::fill_n(n, v), n, n };
148 }
149
150 template <typename Fn>
151 void for_each_chunk(Fn&& fn) const
152 {
153 std::forward<Fn>(fn)(data(), data() + size);
154 }
155
156 template <typename Fn>
157 bool for_each_chunk_p(Fn&& fn) const
158 {
159 return std::forward<Fn>(fn)(data(), data() + size);
160 }
161
162 const T& get(std::size_t index) const
163 {
164 return data()[index];
165 }
166
167 const T& get_check(std::size_t index) const
168 {
169 if (index >= size)
170 throw std::out_of_range{"out of range"};
171 return data()[index];
172 }
173
174 bool equals(const with_capacity& other) const
175 {
176 return ptr == other.ptr ||
177 (size == other.size &&
178 std::equal(data(), data() + size, other.data()));
179 }
180
181 static size_t recommend_up(size_t sz, size_t cap)
182 {
183 auto max = std::numeric_limits<size_t>::max();
184 return
185 sz <= cap ? cap :
186 cap >= max / 2 ? max
187 /* otherwise */ : std::max(2 * cap, sz);
188 }
189
190 static size_t recommend_down(size_t sz, size_t cap)
191 {
192 return sz == 0 ? 1 :
193 sz < cap / 2 ? sz * 2 :
194 /* otherwise */ cap;
195 }
196
197 with_capacity push_back(T value) const
198 {
199 auto cap = recommend_up(size + 1, capacity);
200 auto p = node_t::copy_n(cap, ptr, size);
201 try {
202 new (p->data() + size) T{std::move(value)};
203 return { p, size + 1, cap };
204 } catch (...) {
205 node_t::delete_n(p, size, cap);
206 throw;
207 }
208 }
209
210 void push_back_mut(edit_t e, T value)
211 {
212 if (ptr->can_mutate(e) && capacity > size) {
213 new (data() + size) T{std::move(value)};
214 ++size;
215 } else {
216 auto cap = recommend_up(size + 1, capacity);
217 auto p = node_t::copy_e(e, cap, ptr, size);
218 try {
219 new (p->data() + size) T{std::move(value)};
220 *this = { p, size + 1, cap };
221 } catch (...) {
222 node_t::delete_n(p, size, cap);
223 throw;
224 }
225 }
226 }
227
228 with_capacity assoc(std::size_t idx, T value) const
229 {
230 auto p = node_t::copy_n(capacity, ptr, size);
231 try {
232 p->data()[idx] = std::move(value);
233 return { p, size, capacity };
234 } catch (...) {
235 node_t::delete_n(p, size, capacity);
236 throw;
237 }
238 }
239
240 void assoc_mut(edit_t e, std::size_t idx, T value)
241 {
242 if (ptr->can_mutate(e)) {
243 data()[idx] = std::move(value);
244 } else {
245 auto p = node_t::copy_n(capacity, ptr, size);
246 try {
247 p->data()[idx] = std::move(value);
248 *this = { p, size, capacity };
249 } catch (...) {
250 node_t::delete_n(p, size, capacity);
251 throw;
252 }
253 }
254 }
255
256 template <typename Fn>
257 with_capacity update(std::size_t idx, Fn&& op) const
258 {
259 auto p = node_t::copy_n(capacity, ptr, size);
260 try {
261 auto& elem = p->data()[idx];
262 elem = std::forward<Fn>(op)(std::move(elem));
263 return { p, size, capacity };
264 } catch (...) {
265 node_t::delete_n(p, size, capacity);
266 throw;
267 }
268 }
269
270 template <typename Fn>
271 void update_mut(edit_t e, std::size_t idx, Fn&& op)
272 {
273 if (ptr->can_mutate(e)) {
274 auto& elem = data()[idx];
275 elem = std::forward<Fn>(op)(std::move(elem));
276 } else {
277 auto p = node_t::copy_e(e, capacity, ptr, size);
278 try {
279 auto& elem = p->data()[idx];
280 elem = std::forward<Fn>(op)(std::move(elem));
281 *this = { p, size, capacity };
282 } catch (...) {
283 node_t::delete_n(p, size, capacity);
284 throw;
285 }
286 }
287 }
288
289 with_capacity take(std::size_t sz) const
290 {
291 auto cap = recommend_down(sz, capacity);
292 auto p = node_t::copy_n(cap, ptr, sz);
293 return { p, sz, cap };
294 }
295
296 void take_mut(edit_t e, std::size_t sz)
297 {
298 if (ptr->can_mutate(e)) {
299 destroy_n(data() + size, size - sz);
300 size = sz;
301 } else {
302 auto cap = recommend_down(sz, capacity);
303 auto p = node_t::copy_e(e, cap, ptr, sz);
304 *this = { p, sz, cap };
305 }
306 }
307};
308
309} // namespace arrays
310} // namespace detail
311} // namespace immer
312