/src/immer/immer/detail/arrays/with_capacity.hpp

Source
//
// immer: immutable data structures for C++
// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
//
// This software is distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
//

#pragma once

#include <immer/config.hpp>
#include <immer/detail/arrays/no_capacity.hpp>

#include <cassert>
#include <cstddef>
#include <stdexcept>

namespace immer {
namespace detail {
namespace arrays {

template <typename T, typename MemoryPolicy>
struct with_capacity
{
    using no_capacity_t = no_capacity<T, MemoryPolicy>;

    using node_t = node<T, MemoryPolicy>;
    using edit_t = typename MemoryPolicy::transience_t::edit;
    using size_t = std::size_t;

    node_t* ptr;
    size_t size;
    size_t capacity;

    static const with_capacity& empty()
    {
        static const with_capacity empty_{node_t::make_n(1), 0, 1};
        return empty_;
    }

    with_capacity(node_t* p, size_t s, size_t c)
        : ptr{p}
        , size{s}
        , capacity{c}
    {
    }

    with_capacity(const with_capacity& other)
        : with_capacity{other.ptr, other.size, other.capacity}
    {
        inc();
    }

    with_capacity(const no_capacity_t& other)
        : with_capacity{other.ptr, other.size, other.size}
    {
        inc();
    }

    with_capacity(with_capacity&& other)
        : with_capacity{empty()}
    {
        swap(*this, other);
    }

    with_capacity& operator=(const with_capacity& other)
    {
        auto next = other;
        swap(*this, next);
        return *this;
    }

    with_capacity& operator=(with_capacity&& other)
    {
        swap(*this, other);
        return *this;
    }

    friend void swap(with_capacity& x, with_capacity& y)
    {
        using std::swap;
        swap(x.ptr, y.ptr);
        swap(x.size, y.size);
        swap(x.capacity, y.capacity);
    }

    ~with_capacity() { dec(); }

    void inc()
    {
        using immer::detail::get;
        ptr->refs().inc();
    }

    void dec()
    {
        using immer::detail::get;
        if (ptr->refs().dec())
            node_t::delete_n(ptr, size, capacity);
    }

    const T* data() const { return ptr->data(); }
    T* data() { return ptr->data(); }

    T* data_mut(edit_t e)
    {
        if (!ptr->can_mutate(e)) {
            auto p = node_t::copy_e(e, capacity, ptr, size);
            dec();
            ptr = p;
        }
        return data();
    }

    operator no_capacity_t() const
    {
        if (size == capacity) {
            ptr->refs().inc();
            return {ptr, size};
        } else {
            return {node_t::copy_n(size, ptr, size), size};
        }
    }

    template <typename Iter,
              typename Sent,
              std::enable_if_t<is_forward_iterator_v<Iter> &&
                                   compatible_sentinel_v<Iter, Sent>,
                               bool> = true>
    static with_capacity from_range(Iter first, Sent last)
    {
        auto count = static_cast<size_t>(detail::distance(first, last));
        if (count == 0)
            return empty();
        else
            return {node_t::copy_n(count, first, last), count, count};
    }

    template <typename U>
    static with_capacity from_initializer_list(std::initializer_list<U> values)
    {
        using namespace std;
        return from_range(begin(values), end(values));
    }

    static with_capacity from_fill(size_t n, T v)
    {
        return {node_t::fill_n(n, v), n, n};
    }

    template <typename Fn>
    void for_each_chunk(Fn&& fn) const
    {
        std::forward<Fn>(fn)(data(), data() + size);
    }

    template <typename Fn>
    bool for_each_chunk_p(Fn&& fn) const
    {
        return std::forward<Fn>(fn)(data(), data() + size);
    }

    const T& get(std::size_t index) const { return data()[index]; }

    const T& get_check(std::size_t index) const
    {
        if (index >= size)
            IMMER_THROW(std::out_of_range{"out of range"});
        return data()[index];
    }

    bool equals(const with_capacity& other) const
    {
        return ptr == other.ptr ||
               (size == other.size &&
                std::equal(data(), data() + size, other.data()));
    }

    static size_t recommend_up(size_t sz, size_t cap)
    {
        auto max = std::numeric_limits<size_t>::max();
        return sz <= cap        ? cap
               : cap >= max / 2 ? max
                                /* otherwise */
                                : std::max(2 * cap, sz);
    }

    static size_t recommend_down(size_t sz, size_t cap)
    {
        return sz == 0        ? 1
               : sz < cap / 2 ? sz * 2
                              :
                              /* otherwise */ cap;
    }

    with_capacity push_back(T value) const
    {
        auto cap = recommend_up(size + 1, capacity);
        auto p   = node_t::copy_n(cap, ptr, size);
        IMMER_TRY {
            new (p->data() + size) T(std::move(value));
            return {p, size + 1, cap};
        }
        IMMER_CATCH (...) {
            node_t::delete_n(p, size, cap);
            IMMER_RETHROW;
        }
    }

    void push_back_mut(edit_t e, T value)
    {
        if (ptr->can_mutate(e) && capacity > size) {
            new (data() + size) T(std::move(value));
            ++size;
        } else {
            auto cap = recommend_up(size + 1, capacity);
            auto p   = node_t::copy_e(e, cap, ptr, size);
            IMMER_TRY {
                new (p->data() + size) T(std::move(value));
                *this = {p, size + 1, cap};
            }
            IMMER_CATCH (...) {
                node_t::delete_n(p, size, cap);
                IMMER_RETHROW;
            }
        }
    }

    with_capacity assoc(std::size_t idx, T value) const
    {
        auto p = node_t::copy_n(capacity, ptr, size);
        IMMER_TRY {
            p->data()[idx] = std::move(value);
            return {p, size, capacity};
        }
        IMMER_CATCH (...) {
            node_t::delete_n(p, size, capacity);
            IMMER_RETHROW;
        }
    }

    void assoc_mut(edit_t e, std::size_t idx, T value)
    {
        if (ptr->can_mutate(e)) {
            data()[idx] = std::move(value);
        } else {
            auto p = node_t::copy_n(capacity, ptr, size);
            IMMER_TRY {
                p->data()[idx] = std::move(value);
                *this          = {p, size, capacity};
            }
            IMMER_CATCH (...) {
                node_t::delete_n(p, size, capacity);
                IMMER_RETHROW;
            }
        }
    }

    template <typename Fn>
    with_capacity update(std::size_t idx, Fn&& op) const
    {
        auto p = node_t::copy_n(capacity, ptr, size);
        IMMER_TRY {
            auto& elem = p->data()[idx];
            elem       = std::forward<Fn>(op)(std::move(elem));
            return {p, size, capacity};
        }
        IMMER_CATCH (...) {
            node_t::delete_n(p, size, capacity);
            IMMER_RETHROW;
        }
    }

    template <typename Fn>
    void update_mut(edit_t e, std::size_t idx, Fn&& op)
    {
        if (ptr->can_mutate(e)) {
            auto& elem = data()[idx];
            elem       = std::forward<Fn>(op)(std::move(elem));
        } else {
            auto p = node_t::copy_e(e, capacity, ptr, size);
            IMMER_TRY {
                auto& elem = p->data()[idx];
                elem       = std::forward<Fn>(op)(std::move(elem));
                *this      = {p, size, capacity};
            }
            IMMER_CATCH (...) {
                node_t::delete_n(p, size, capacity);
                IMMER_RETHROW;
            }
        }
    }

    with_capacity take(std::size_t sz) const
    {
        assert(sz <= size);
        auto cap = recommend_down(sz, capacity);
        auto p   = node_t::copy_n(cap, ptr, sz);
        return {p, sz, cap};
    }

    void take_mut(edit_t e, std::size_t sz)
    {
        assert(sz <= size);
        if (ptr->can_mutate(e)) {
            detail::destroy_n(data() + size, size - sz);
            size = sz;
        } else {
            auto cap = recommend_down(sz, capacity);
            auto p   = node_t::copy_e(e, cap, ptr, sz);
            *this    = {p, sz, cap};
        }
    }
};

} // namespace arrays
} // namespace detail
} // namespace immer

Coverage Report

Created: 2026-10-28 06:04

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