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/algorithm.hpp>
12#include <immer/detail/arrays/node.hpp>
13
14namespace immer {
15namespace detail {
16namespace arrays {
17
18template <typename T, typename MemoryPolicy>
19struct no_capacity
20{
21 using node_t = node<T, MemoryPolicy>;
22 using edit_t = typename MemoryPolicy::transience_t::edit;
23 using size_t = std::size_t;
24
25 node_t* ptr;
26 size_t size;
27
28 static const no_capacity& empty()
29 {
30 static const no_capacity empty_ {
31 node_t::make_n(0),
32 0,
33 };
34 return empty_;
35 }
36
37 no_capacity(node_t* p, size_t s)
38 : ptr{p}, size{s}
39 {}
40
41 no_capacity(const no_capacity& other)
42 : no_capacity{other.ptr, other.size}
43 {
44 inc();
45 }
46
47 no_capacity(no_capacity&& other)
48 : no_capacity{empty()}
49 {
50 swap(*this, other);
51 }
52
53 no_capacity& operator=(const no_capacity& other)
54 {
55 auto next = other;
56 swap(*this, next);
57 return *this;
58 }
59
60 no_capacity& operator=(no_capacity&& other)
61 {
62 swap(*this, other);
63 return *this;
64 }
65
66 friend void swap(no_capacity& x, no_capacity& y)
67 {
68 using std::swap;
69 swap(x.ptr, y.ptr);
70 swap(x.size, y.size);
71 }
72
73 ~no_capacity()
74 {
75 dec();
76 }
77
78 void inc()
79 {
80 using immer::detail::get;
81 ptr->refs().inc();
82 }
83
84 void dec()
85 {
86 using immer::detail::get;
87 if (ptr->refs().dec())
88 node_t::delete_n(ptr, size, size);
89 }
90
91 T* data() { return ptr->data(); }
92 const T* data() const { return ptr->data(); }
93
94 T* data_mut(edit_t e)
95 {
96 if (!ptr->can_mutate(e))
97 ptr = node_t::copy_e(e, size, ptr, size);
98 return data();
99 }
100
101 template <typename Iter, typename Sent,
102 std::enable_if_t
103 <is_forward_iterator_v<Iter>
104 && compatible_sentinel_v<Iter, Sent>, bool> = true>
105 static no_capacity from_range(Iter first, Sent last)
106 {
107 auto count = static_cast<size_t>(distance(first, last));
108 return {
109 node_t::copy_n(count, first, last),
110 count,
111 };
112 }
113
114 static no_capacity from_fill(size_t n, T v)
115 {
116 return { node_t::fill_n(n, v), n };
117 }
118
119 template <typename U>
120 static no_capacity from_initializer_list(std::initializer_list<U> values)
121 {
122 using namespace std;
123 return from_range(begin(values), end(values));
124 }
125
126 template <typename Fn>
127 void for_each_chunk(Fn&& fn) const
128 {
129 std::forward<Fn>(fn)(data(), data() + size);
130 }
131
132 template <typename Fn>
133 bool for_each_chunk_p(Fn&& fn) const
134 {
135 return std::forward<Fn>(fn)(data(), data() + size);
136 }
137
138 const T& get(std::size_t index) const
139 {
140 return data()[index];
141 }
142
143 const T& get_check(std::size_t index) const
144 {
145 if (index >= size)
146 throw std::out_of_range{"out of range"};
147 return data()[index];
148 }
149
150 bool equals(const no_capacity& other) const
151 {
152 return ptr == other.ptr ||
153 (size == other.size &&
154 std::equal(data(), data() + size, other.data()));
155 }
156
157 no_capacity push_back(T value) const
158 {
159 auto p = node_t::copy_n(size + 1, ptr, size);
160 try {
161 new (p->data() + size) T{std::move(value)};
162 return { p, size + 1 };
163 } catch (...) {
164 node_t::delete_n(p, size, size + 1);
165 throw;
166 }
167 }
168
169 no_capacity assoc(std::size_t idx, T value) const
170 {
171 auto p = node_t::copy_n(size, ptr, size);
172 try {
173 p->data()[idx] = std::move(value);
174 return { p, size };
175 } catch (...) {
176 node_t::delete_n(p, size, size);
177 throw;
178 }
179 }
180
181 template <typename Fn>
182 no_capacity update(std::size_t idx, Fn&& op) const
183 {
184 auto p = node_t::copy_n(size, ptr, size);
185 try {
186 auto& elem = p->data()[idx];
187 elem = std::forward<Fn>(op)(std::move(elem));
188 return { p, size };
189 } catch (...) {
190 node_t::delete_n(p, size, size);
191 throw;
192 }
193 }
194
195 no_capacity take(std::size_t sz) const
196 {
197 auto p = node_t::copy_n(sz, ptr, sz);
198 return { p, sz };
199 }
200};
201
202} // namespace arrays
203} // namespace detail
204} // namespace immer
205