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 <cstddef>
12#include <utility>
13#include <array>
14
15#include <immer/detail/rbts/bits.hpp>
16#include <immer/detail/hamts/bits.hpp>
17
18namespace {
19
20template <typename Iterator>
21struct rotator
22{
23 using value_type = typename std::iterator_traits<Iterator>::value_type;
24
25 Iterator first;
26 Iterator last;
27 Iterator curr;
28
29 void init(Iterator f, Iterator l)
30 { first = f; last = l; curr = f; }
31
32 value_type next()
33 {
34 if (curr == last) curr = first;
35 return *curr++;
36 }
37};
38
39template <typename Range>
40struct range_rotator : rotator<typename Range::iterator>
41{
42 using base_t = rotator<typename Range::iterator>;
43
44 Range range;
45
46 range_rotator(Range r)
47 : range{std::move(r)}
48 { base_t::init(range.begin(), range.end()); }
49};
50
51template <typename Range>
52auto make_rotator(Range r) -> range_rotator<Range>
53{
54 return { r };
55}
56
57inline auto magic_rotator()
58{
59 return make_rotator(std::array<unsigned, 15>{{
60 7, 11, 2, 3, 5,
61 7, 11, 13, 17, 19,
62 23, 5, 29, 31, 37
63 }});
64}
65
66struct dada_error {};
67
68struct dadaism;
69static dadaism* g_dadaism = nullptr;
70
71struct dadaism
72{
73 using rotator_t = decltype(magic_rotator());
74
75 rotator_t magic = magic_rotator();
76
77 unsigned step = magic.next();
78 unsigned count = 0;
79 unsigned happenings = 0;
80 unsigned last = 0;
81 bool toggle = false;
82
83 struct scope
84 {
85 bool moved = false;
86 dadaism* save_ = g_dadaism;
87 scope(scope&& s) { save_ = s.save_; s.moved = true; }
88 scope(dadaism* self) { g_dadaism = self; }
89 ~scope() { if (!moved) g_dadaism = save_; }
90 };
91
92 static scope disable() { return { nullptr }; }
93
94 scope next()
95 {
96 toggle = last == happenings;
97 last = happenings;
98 step = toggle ? step : magic.next();
99 return { this };
100 }
101
102 void dada()
103 {
104 if (toggle && ++count % step == 0) {
105 ++happenings;
106 throw dada_error{};
107 }
108 }
109};
110
111inline void dada()
112{
113 if (g_dadaism)
114 g_dadaism->dada();
115}
116
117inline bool soft_dada()
118{
119 try {
120 dada();
121 return false;
122 } catch (dada_error) {
123 return true;
124 }
125}
126
127template <typename Heap>
128struct dadaist_heap : Heap
129{
130 template <typename... Tags>
131 static auto allocate(std::size_t s, Tags... tags)
132 {
133 dada();
134 return Heap::allocate(s, tags...);
135 }
136};
137
138template <typename MP>
139struct dadaist_memory_policy : MP
140{
141 struct heap
142 {
143 using type = dadaist_heap<typename MP::heap::type>;
144
145 template <std::size_t Size>
146 struct optimized
147 {
148 using base = typename MP::heap::template optimized<Size>::type;
149 using type = dadaist_heap<base>;
150 };
151 };
152};
153
154struct tristan_tzara
155{
156 tristan_tzara() { dada(); }
157 tristan_tzara(const tristan_tzara&) { dada(); }
158 tristan_tzara(tristan_tzara&&) { dada(); }
159 tristan_tzara& operator= (const tristan_tzara&) { dada(); return *this; }
160 tristan_tzara& operator= (tristan_tzara&&) { dada(); return *this; }
161};
162
163template <typename T>
164struct dadaist : tristan_tzara
165{
166 T value;
167
168 dadaist() : value{} {}
169 dadaist(T v) : value{std::move(v)} {}
170 operator T() const { return value; }
171};
172
173template <typename T>
174struct dadaist_wrapper;
175
176using rbits_t = immer::detail::rbts::bits_t;
177using hbits_t = immer::detail::rbts::bits_t;
178
179template <template <class, class, rbits_t, rbits_t> class V,
180 typename T, typename MP, rbits_t B, rbits_t BL>
181struct dadaist_wrapper<V<T, MP, B, BL>>
182{
183 using type = V<dadaist<T>, dadaist_memory_policy<MP>, B, BL>;
184};
185
186template <template <class, class> class V,
187 typename T, typename MP>
188struct dadaist_wrapper<V<T, MP>>
189{
190 using type = V<dadaist<T>, dadaist_memory_policy<MP>>;
191};
192
193template <template <class, class, class, class, hbits_t> class V,
194 typename T, typename E, typename H, typename MP, hbits_t B>
195struct dadaist_wrapper<V<T, H, E, MP, B>>
196{
197 using type = V<dadaist<T>, H, E, dadaist_memory_policy<MP>, B>;
198};
199
200template <template <class, class, class, class, class, hbits_t> class V,
201 typename K, typename T, typename E, typename H, typename MP, hbits_t B>
202struct dadaist_wrapper<V<K, T, H, E, MP, B>>
203{
204 using type = V<K, dadaist<T>, H, E, dadaist_memory_policy<MP>, B>;
205};
206
207} // anonymous namespace
208