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 | |
13 | namespace immer { |
14 | namespace detail { |
15 | namespace arrays { |
16 | |
17 | template <typename T, typename MemoryPolicy> |
18 | struct 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 | |