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 | |
18 | namespace { |
19 | |
20 | template <typename Iterator> |
21 | struct 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 | |
39 | template <typename Range> |
40 | struct 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 | |
51 | template <typename Range> |
52 | auto make_rotator(Range r) -> range_rotator<Range> |
53 | { |
54 | return { r }; |
55 | } |
56 | |
57 | inline 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 | |
66 | struct dada_error {}; |
67 | |
68 | struct dadaism; |
69 | static dadaism* g_dadaism = nullptr; |
70 | |
71 | struct 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 | |
111 | inline void dada() |
112 | { |
113 | if (g_dadaism) |
114 | g_dadaism->dada(); |
115 | } |
116 | |
117 | inline bool soft_dada() |
118 | { |
119 | try { |
120 | dada(); |
121 | return false; |
122 | } catch (dada_error) { |
123 | return true; |
124 | } |
125 | } |
126 | |
127 | template <typename Heap> |
128 | struct 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 | |
138 | template <typename MP> |
139 | struct 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 | |
154 | struct 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 | |
163 | template <typename T> |
164 | struct 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 | |
173 | template <typename T> |
174 | struct dadaist_wrapper; |
175 | |
176 | using rbits_t = immer::detail::rbts::bits_t; |
177 | using hbits_t = immer::detail::rbts::bits_t; |
178 | |
179 | template <template <class, class, rbits_t, rbits_t> class V, |
180 | typename T, typename MP, rbits_t B, rbits_t BL> |
181 | struct dadaist_wrapper<V<T, MP, B, BL>> |
182 | { |
183 | using type = V<dadaist<T>, dadaist_memory_policy<MP>, B, BL>; |
184 | }; |
185 | |
186 | template <template <class, class> class V, |
187 | typename T, typename MP> |
188 | struct dadaist_wrapper<V<T, MP>> |
189 | { |
190 | using type = V<dadaist<T>, dadaist_memory_policy<MP>>; |
191 | }; |
192 | |
193 | template <template <class, class, class, class, hbits_t> class V, |
194 | typename T, typename E, typename H, typename MP, hbits_t B> |
195 | struct dadaist_wrapper<V<T, H, E, MP, B>> |
196 | { |
197 | using type = V<dadaist<T>, H, E, dadaist_memory_policy<MP>, B>; |
198 | }; |
199 | |
200 | template <template <class, class, class, class, class, hbits_t> class V, |
201 | typename K, typename T, typename E, typename H, typename MP, hbits_t B> |
202 | struct 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 | |