Line data Source code
1 : /**
2 : Copyright (c) 2017-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #ifndef STAPPLER_CORE_MEMORY_SPMEMRBTREE_H_
25 : #define STAPPLER_CORE_MEMORY_SPMEMRBTREE_H_
26 :
27 : #include "SPMemAlloc.h"
28 :
29 : #define SP_MEM_RBTREE_DEBUG 0
30 :
31 : namespace STAPPLER_VERSIONIZED stappler::memory::rbtree {
32 :
33 : enum NodeColor : uintptr_t {
34 : Red = 0,
35 : Black = 1
36 : };
37 :
38 : template <typename Value>
39 : using Storage = memory::Storage<Value>;
40 :
41 : struct NodeBase : public AllocPool {
42 : struct Flag {
43 : uintptr_t color : 1;
44 : uintptr_t prealloc : 1;
45 : uintptr_t index : (sizeof(uintptr_t) / 2) * 8 - 2;
46 : uintptr_t size : (sizeof(uintptr_t) / 2) * 8;
47 : };
48 :
49 : NodeBase *parent = nullptr;
50 : NodeBase *left = nullptr;
51 : NodeBase *right = nullptr;
52 : Flag flag;
53 :
54 : NodeBase() noexcept : flag(Flag{0, 0, 0, 0}) { }
55 2251485 : NodeBase(NodeColor c) noexcept : flag(Flag{uintptr_t(c ? 1 : 0), 0, 0, 0}) { }
56 :
57 73832798 : inline void setColor(NodeColor c) { flag.color = c ? 1 : 0; }
58 57293111 : inline NodeColor getColor() const { return NodeColor(flag.color); }
59 :
60 12487308 : inline void setPrealloc(bool v) { flag.prealloc = v ? 1 : 0; }
61 9812949 : inline bool isPrealloc() const { return flag.prealloc != 0; }
62 :
63 12488151 : inline void setSize(uintptr_t s) { flag.size = s; }
64 2341021 : inline uintptr_t getSize() const { return flag.size; }
65 :
66 8608890 : inline void setIndex(uintptr_t s) { flag.index = s; }
67 0 : inline uintptr_t getIndex() const { return flag.index; }
68 :
69 : static inline NodeBase * min (NodeBase * x) {
70 : while (x->left != 0) x = x->left;
71 : return x;
72 : }
73 :
74 : static inline const NodeBase * min(const NodeBase * x) {
75 : while (x->left != 0) x = x->left;
76 : return x;
77 : }
78 :
79 : static inline NodeBase * max(NodeBase * x) {
80 : while (x->right != 0) x = x->right;
81 : return x;
82 : }
83 :
84 : static inline const NodeBase * max(const NodeBase * x) {
85 : while (x->right != 0) x = x->right;
86 : return x;
87 : }
88 :
89 : static NodeBase * increment(NodeBase *c);
90 : static const NodeBase * increment(const NodeBase *c);
91 :
92 : static NodeBase * decrement(NodeBase *c);
93 : static const NodeBase * decrement(const NodeBase *c);
94 :
95 : // replace node in it's place in tree with new one
96 : static NodeBase *replace(NodeBase *old, NodeBase *n);
97 :
98 : static void insert(NodeBase *head, NodeBase * n);
99 : static void remove(NodeBase *head, NodeBase * n);
100 : };
101 :
102 : template <typename Value>
103 : struct Node : public NodeBase {
104 : Storage<Value> value;
105 :
106 15180930 : static inline Value *cast(NodeBase *n) { return static_cast<Node<Value> *>(n)->value.ptr(); }
107 329684746 : static inline const Value *cast(const NodeBase *n) { return static_cast<const Node<Value> *>(n)->value.ptr(); }
108 : };
109 :
110 : template<typename Value>
111 : struct TreeIterator {
112 : using iterator_category = std::bidirectional_iterator_tag;
113 :
114 : using node_type = Node<Value>;
115 : using value_type = Value;
116 : using reference = Value &;
117 : using pointer = Value *;
118 :
119 : using difference_type = ptrdiff_t;
120 :
121 : using self = TreeIterator<Value>;
122 : using node_ptr = NodeBase *;
123 : using link_ptr = Node<Value> *;
124 :
125 : TreeIterator() noexcept : _node() {}
126 :
127 140487723 : explicit TreeIterator(node_ptr x) noexcept : _node(x) {}
128 :
129 8629793 : reference operator*() const noexcept {return *node_type::cast(_node);}
130 6551138 : pointer operator->() const noexcept {return node_type::cast(_node);}
131 :
132 8639796 : self & operator++() noexcept {_node = node_type::increment(_node); return *this;}
133 170250 : self operator++(int) noexcept {self ret = *this; _node = node_type::increment(_node); return ret;}
134 :
135 : self & operator--() noexcept {_node = node_type::decrement(_node); return *this;}
136 : self operator--(int) noexcept {self ret = *this; _node = node_type::decrement(_node); return ret;}
137 :
138 173971 : bool operator==(const self & other) const noexcept {return _node == other._node;}
139 10898564 : bool operator!=(const self & other) const noexcept {return _node != other._node;}
140 :
141 : node_ptr _node;
142 : };
143 :
144 : template<typename Value>
145 : struct TreeConstIterator {
146 : using iterator_category = std::bidirectional_iterator_tag;
147 :
148 : using node_type = Node<Value>;
149 : using value_type = Value;
150 : using reference = const Value &;
151 : using pointer = const Value *;
152 :
153 : using iterator = TreeIterator<Value>;
154 :
155 : using difference_type = ptrdiff_t;
156 :
157 : using self = TreeConstIterator<Value>;
158 : using node_ptr = const NodeBase *;
159 : using link_ptr = const Node<Value> *;
160 :
161 : TreeConstIterator() noexcept : _node() {}
162 :
163 52362946 : explicit TreeConstIterator(node_ptr x) noexcept : _node(x) {}
164 :
165 121548533 : TreeConstIterator(const iterator& it) noexcept : _node(it._node) {}
166 :
167 9228274 : iterator constcast() const noexcept {return iterator(const_cast<typename iterator::node_ptr>(_node));}
168 :
169 249980359 : reference operator*() const noexcept {return *node_type::cast(_node); }
170 84033728 : pointer operator->() const noexcept {return node_type::cast(_node); }
171 :
172 210266726 : self & operator++() noexcept {_node = node_type::increment(_node); return *this;}
173 : self operator++(int) noexcept {self tmp = *this; _node = node_type::increment(_node); return tmp;}
174 :
175 5211138 : self & operator--() noexcept {_node = node_type::decrement(_node); return *this;}
176 : self operator--(int) noexcept {self tmp = *this; _node = node_type::decrement(_node); return tmp;}
177 :
178 5424306 : bool operator==(const self & x) const noexcept {return _node == x._node;}
179 257212916 : bool operator!=(const self & x) const noexcept {return _node != x._node;}
180 :
181 : node_ptr _node;
182 : };
183 :
184 :
185 : template<typename Value> inline bool
186 : operator==(const TreeIterator<Value> & l, const TreeConstIterator<Value> & r) noexcept { return l._node == r._node; }
187 :
188 : template<typename Value> inline bool
189 : operator!=(const TreeIterator<Value> & l, const TreeConstIterator<Value> & r) noexcept { return l._node != r._node; }
190 :
191 :
192 : template <typename Key, typename Value>
193 : struct TreeKeyExtractor;
194 :
195 : template <typename Key>
196 : struct TreeKeyExtractor<Key, Key> {
197 114924663 : static inline const Key & extract(const Key &k) noexcept { return k; }
198 :
199 : template <typename A, typename ... Args>
200 : static inline void construct(A &alloc, Node<Key> *node, const Key &key, Args && ... args) noexcept {
201 : alloc.construct(node->value.ptr(), key);
202 : }
203 :
204 : template <typename A, typename ... Args>
205 : static inline void construct(A &alloc, Node<Key> *node, Key &&key, Args && ... args) noexcept {
206 : alloc.construct(node->value.ptr(), std::move(key));
207 : }
208 : };
209 :
210 : template <typename Key, typename Value>
211 : struct TreeKeyExtractor<Key, Pair<Key, Value>> {
212 : static inline const Key & extract(const Pair<Key, Value> &k) noexcept { return k.first; }
213 :
214 : template <typename A, typename ... Args>
215 : static inline void construct(A &alloc, Node<Pair<Key, Value>> *node, const Key &k, Args && ... args) noexcept {
216 : alloc.construct(node->value.ptr(),
217 : std::piecewise_construct,
218 : std::forward_as_tuple(k),
219 : std::forward_as_tuple(std::forward<Args>(args)...));
220 : }
221 :
222 : template <typename A, typename ... Args>
223 : static inline void construct(A &alloc, Node<Pair<Key, Value>> *node, Key &&k, Args && ... args) noexcept {
224 : alloc.construct(node->value.ptr(),
225 : std::piecewise_construct,
226 : std::forward_as_tuple(std::move(k)),
227 : std::forward_as_tuple(std::forward<Args>(args)...));
228 : }
229 : };
230 :
231 : template <typename Key, typename Value>
232 : struct TreeKeyExtractor<Key, Pair<const Key, Value>> {
233 18106908 : static inline const Key & extract(const Pair<const Key, Value> &k) noexcept { return k.first; }
234 :
235 : template <typename A, typename ... Args>
236 35292 : static inline void construct(A &alloc, Node<Pair<const Key, Value>> *node, const Key &k, Args && ... args) noexcept {
237 35292 : alloc.construct(node->value.ptr(),
238 : std::piecewise_construct,
239 : std::forward_as_tuple(k),
240 600 : std::forward_as_tuple(std::forward<Args>(args)...));
241 35292 : }
242 :
243 : template <typename A, typename ... Args>
244 5675380 : static inline void construct(A &alloc, Node<Pair<const Key, Value>> *node, Key &&k, Args && ... args) noexcept {
245 11331687 : alloc.construct(node->value.ptr(),
246 : std::piecewise_construct,
247 5675384 : std::forward_as_tuple(std::move(k)),
248 19076 : std::forward_as_tuple(std::forward<Args>(args)...));
249 5675383 : }
250 : };
251 :
252 : template <typename Key, typename Comp, typename Transparent = void>
253 : struct TreeComparator {
254 32261496 : static inline bool compare(const Key &l, const Key &r, const Comp &comp) noexcept {
255 32261496 : return comp(l, r);
256 : }
257 :
258 : template <typename A, typename B>
259 18330269 : static inline bool compare(const A &l, const B &r, const Comp &comp, typename Comp::is_transparent * = nullptr) noexcept {
260 18330269 : return comp(l, r);
261 : }
262 : };
263 :
264 : template <typename Key, typename Comp>
265 : struct TreeComparator<Key, Comp, typename Comp::is_transparent> {
266 : template <typename A, typename B>
267 : static inline bool compare(const A &l, const B &r, const Comp &comp) noexcept {
268 : return comp(l, r);
269 : }
270 : };
271 :
272 : template <typename Key, typename Value, typename Comp = std::less<>>
273 : class Tree : public AllocPool {
274 : public:
275 : using value_type = Value;
276 : using node_type = Node<Value>;
277 : using node_ptr = Node<Value> *;
278 : using base_type = NodeBase *;
279 : using const_node_ptr = const node_type *;
280 :
281 : using node_allocator_type = Allocator<node_type>;
282 : using value_allocator_type = Allocator<value_type>;
283 : using comparator_type = Comp;
284 :
285 : using iterator = TreeIterator<Value>;
286 : using const_iterator = TreeConstIterator<Value>;
287 :
288 : using reverse_iterator = std::reverse_iterator<iterator>;
289 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
290 :
291 : public:
292 1276067 : Tree(const Comp &comp = Comp(), const value_allocator_type &alloc = value_allocator_type()) noexcept
293 1276067 : : _header(NodeColor::Black), _comp(comp), _allocator(alloc), _size(0) { }
294 :
295 876675 : Tree(const Tree &other, const value_allocator_type &alloc = value_allocator_type()) noexcept
296 876675 : : _header(NodeColor::Black), _comp(other._comp), _allocator(alloc), _size(0) {
297 876675 : clone(other);
298 876675 : }
299 :
300 46288 : Tree(Tree &&other, const value_allocator_type &alloc = value_allocator_type()) noexcept
301 46288 : : _header(NodeColor::Black), _comp(other._comp), _allocator(alloc), _size(0) {
302 46298 : if (other.get_allocator() == _allocator) {
303 46267 : _header = other._header;
304 46267 : _size = other._size;
305 46267 : _comp = std::move(other._comp);
306 46265 : if (_header.left != nullptr) {
307 10375 : _header.left->parent = &_header;
308 : }
309 46265 : other._header = NodeBase(NodeColor::Black);
310 46270 : other._size = 0;
311 : } else {
312 25 : clone(other);
313 : }
314 46295 : }
315 :
316 : Tree & operator = (const Tree &other) noexcept {
317 : clone(other);
318 : return *this;
319 : }
320 :
321 2625 : Tree & operator = (Tree &&other) noexcept {
322 2625 : if (other.get_allocator() == _allocator) {
323 2325 : clear();
324 2325 : _header = other._header;
325 2325 : _size = other._size;
326 2325 : _comp = std::move(other._comp);
327 2325 : if (_header.left != nullptr) {
328 1550 : _header.left->parent = &_header;
329 : }
330 2325 : other._header = NodeBase(NodeColor::Black);
331 2325 : other._size = 0;
332 : } else {
333 300 : clone(other);
334 : }
335 2625 : return *this;
336 : }
337 :
338 472390 : ~Tree() noexcept {
339 472390 : if (_size > 0) {
340 215076 : clear();
341 : }
342 472392 : releaseTmp();
343 472331 : }
344 :
345 71068 : const value_allocator_type & get_allocator() const noexcept { return _allocator; }
346 :
347 : template <typename ... Args>
348 9291103 : Pair<iterator,bool> emplace(Args && ... args) {
349 9291103 : auto ret = insertNodeUnique(std::forward<Args>(args)...);
350 9334434 : return pair(iterator(ret.first), ret.second);
351 : }
352 :
353 : template <typename ... Args>
354 : iterator emplace_hint(const_iterator hint, Args && ... args) {
355 : return iterator(insertNodeUniqueHint(hint, std::forward<Args>(args)...));
356 : }
357 :
358 : template <typename K, typename ... Args>
359 5711593 : Pair<iterator,bool> try_emplace(K &&k, Args && ... args) {
360 5711593 : auto ret = tryInsertNodeUnique(std::forward<K>(k), std::forward<Args>(args)...);
361 5711594 : return pair(iterator(ret.first), ret.second);
362 : }
363 :
364 : template <typename K, typename ... Args>
365 : iterator try_emplace(const_iterator hint, K &&k, Args && ... args) {
366 : return iterator(tryInsertNodeUniqueHint(hint, std::forward<K>(k), std::forward<Args>(args)...));
367 : }
368 :
369 : template <typename K, class M>
370 : Pair<iterator, bool> insert_or_assign(K&& k, M&& m) {
371 : auto ret = tryAssignNodeUnique(std::forward<K>(k), std::forward<M>(m));
372 : return pair(iterator(ret.first), ret.second);
373 : }
374 :
375 : template <typename K, class M>
376 : iterator insert_or_assign(const_iterator hint, K&& k, M&& m) {
377 : return iterator(tryAssignNodeUniqueHint(hint, std::forward<K>(k), std::forward<M>(m)));
378 : }
379 :
380 9227896 : iterator erase( const_iterator pos ) {
381 9227896 : if (pos._node != &_header) {
382 9229683 : auto next = NodeBase::increment(pos.constcast()._node);
383 9223681 : deleteNode(const_cast<NodeBase *>(pos._node));
384 9217807 : return iterator(next);
385 : }
386 0 : return pos.constcast();
387 : }
388 :
389 : iterator erase( const_iterator first, const_iterator last ) {
390 : for (auto it = first; it != last; it ++) {
391 : deleteNode(const_cast<NodeBase *>(it._node));
392 : }
393 : return last;
394 : }
395 :
396 300 : size_t erase_unique(const Key &key) {
397 300 : auto node = find_impl(key);
398 300 : if (node) {
399 225 : deleteNode(node);
400 225 : return 1;
401 : }
402 75 : return 0;
403 : }
404 :
405 10321285 : iterator begin() noexcept { return iterator(_header.left?left():&_header); }
406 89385897 : iterator end() noexcept { return iterator(&_header); }
407 :
408 28266824 : const_iterator begin() const noexcept { return const_iterator(_header.left?left():&_header); }
409 18722369 : const_iterator end() const noexcept { return const_iterator(&_header); }
410 :
411 : reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
412 : reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
413 :
414 : const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
415 : const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
416 :
417 : const_iterator cbegin() const noexcept { return const_iterator(_header.left?left():&_header); }
418 : const_iterator cend() const noexcept { return const_iterator(&_header); }
419 :
420 : const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }
421 : const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }
422 :
423 1100745 : void clear() noexcept {
424 1100745 : if (_header.left) {
425 218400 : clear_visit(static_cast<Node<Value> *>(_header.left));
426 : }
427 1100748 : _header.left = nullptr;
428 1100748 : _header.right = nullptr;
429 1100748 : _header.parent = nullptr;
430 1100748 : _size = 0;
431 1100748 : }
432 :
433 75 : void shrink_to_fit() noexcept {
434 75 : releaseTmp();
435 75 : }
436 :
437 375 : size_t capacity() const noexcept {
438 375 : return _size + _header.flag.size;
439 : }
440 :
441 666663 : size_t size() const noexcept {
442 666663 : return _size;
443 : }
444 :
445 23601012 : bool empty() const noexcept {
446 23601012 : return _header.left == nullptr;
447 : }
448 :
449 128880 : void set_memory_persistent(bool value) noexcept {
450 128880 : _header.flag.prealloc = value ? 1 : 0;
451 128880 : }
452 :
453 : bool memory_persistent() const noexcept {
454 : return _header.flag.prealloc;
455 : }
456 :
457 : void swap(Tree &other) noexcept {
458 : std::swap(_header, other._header);
459 : std::swap(_allocator, other._allocator);
460 : std::swap(_size, other._size);
461 : std::swap(_comp, other._comp);
462 : std::swap(_tmp, other._tmp);
463 : }
464 :
465 770229 : template< class K > iterator find( const K& x ) {
466 770229 : auto ptr = find_impl(x);
467 770228 : return (ptr) ? iterator(ptr) : end();
468 : }
469 :
470 581597 : template< class K > const_iterator find( const K& x ) const {
471 581597 : auto ptr = find_impl(x);
472 581597 : return (ptr) ? const_iterator(ptr) : end();
473 : }
474 :
475 : template< class K >
476 9203863 : iterator lower_bound(const K& x) {
477 9203863 : auto ptr = lower_bound_ptr(x);
478 9188425 : return (ptr) ? iterator(ptr) : end();
479 : }
480 :
481 : template< class K >
482 5293969 : const_iterator lower_bound(const K& x) const {
483 5293969 : auto ptr = lower_bound_ptr(x);
484 5288574 : return (ptr) ? const_iterator(ptr) : end();
485 : }
486 :
487 : template< class K >
488 : iterator upper_bound( const K& x ) {
489 : auto ptr = upper_bound_ptr(x);
490 : return (ptr) ? iterator(ptr) : end();
491 : }
492 :
493 : template< class K >
494 : const_iterator upper_bound( const K& x ) const {
495 : auto ptr = upper_bound_ptr(x);
496 : return (ptr) ? const_iterator(ptr) : end();
497 : }
498 : template< class K >
499 : Pair<iterator,iterator> equal_range( const K& x ) {
500 : return pair(lower_bound(x), upper_bound(x));
501 : }
502 :
503 : template< class K >
504 : Pair<const_iterator,const_iterator> equal_range( const K& x ) const {
505 : return pair(lower_bound(x), upper_bound(x));
506 : }
507 :
508 : template< class K >
509 : size_t count( const K& x ) const {
510 : return count_impl(x);
511 : }
512 :
513 : template< class K >
514 : size_t count_unique( const K& x ) const {
515 : return findNode(x)?1:0;
516 : }
517 :
518 525487 : void reserve(size_t c) {
519 : // requested count is greater then size + pending preallocated nodes
520 525487 : if (c > _size + _header.flag.size) {
521 525451 : allocateTmp(c - _size);
522 : }
523 525544 : }
524 :
525 : protected:
526 : friend class TreeDebug;
527 :
528 : // header values has a special meanings:
529 : // _header.parent - left node from root (first node of iteration)
530 : // _header.right - right node from root
531 : // _header.left - root node (actual root of the tree), nullptr if tree is not defined
532 : // &_header (pointer to the header) - last node in iteration
533 : // _header.size - extra capacity, available via _tmp
534 : // _header.index - count of preallocated blocks in use
535 : // _header.prealloc - flag of persistent mode (enabled if 1, disabled by default)
536 :
537 : NodeBase _header; // root is _header.left
538 : comparator_type _comp;
539 : value_allocator_type _allocator;
540 : size_t _size = 0;
541 : Node<Value> *_tmp = nullptr;
542 :
543 6536205 : inline node_ptr root() { return static_cast<node_ptr>(_header.left); }
544 15705649 : inline const_node_ptr root() const { return static_cast<const_node_ptr>(_header.left); }
545 1161415 : inline void setroot(base_type n) { _header.left = n; n->parent = &_header; }
546 :
547 36472274 : inline node_ptr left() { return static_cast<node_ptr>(_header.parent); }
548 28262724 : inline const_node_ptr left() const { return static_cast<const_node_ptr>(_header.parent); }
549 4140238 : inline void setleft(base_type n) { _header.parent = (n == &_header)?nullptr:n; }
550 :
551 26492935 : inline node_ptr right() { return static_cast<node_ptr>(_header.right); }
552 : inline const_node_ptr right() const { return static_cast<const_node_ptr>(_header.right); }
553 8459604 : inline void setright(base_type n) { _header.right = (n == &_header)?nullptr:n; }
554 :
555 :
556 133086257 : inline const Key & extract(const Value &val) const { return TreeKeyExtractor<Key, Value>::extract(val); }
557 53715990 : inline const Key & extract(const Storage<Value> &s) const { return extract(s.ref()); }
558 80660913 : inline const Key & extract(const NodeBase *s) const { return extract(static_cast<const Node<Value> *>(s)->value.ref()); }
559 :
560 : template <typename A, typename B>
561 49926277 : inline bool compareLtTransparent(const A &l, const B &r) const { return TreeComparator<Key, Comp>::compare(l, r, _comp); }
562 :
563 75748532 : inline bool compareLtKey(const Key &l, const Key &r) const { return _comp(l, r); }
564 : inline bool compareEqKey(const Key &l, const Key &r) const { return !compareLtKey(l, r) && !compareLtKey(r, l); }
565 :
566 : inline bool compareEqValue(const Value &l, const Value &r) const { return compareEqKey(extract(l), extract(r)); }
567 : inline bool compareLtValue(const Value &l, const Value &r) const { return compareLtKey(extract(l), extract(r)); }
568 :
569 : struct InsertData {
570 : const Key *key;
571 : Node<Value> *val;
572 : NodeBase * current;
573 : NodeBase * parent;
574 : bool isLeft;
575 : };
576 :
577 : template <typename ... Args> InsertData
578 9282294 : constructNode(Args && ... args) {
579 9282294 : Node<Value> * ret = allocateNode();
580 9280387 : ret->parent = nullptr;
581 9280387 : ret->left = nullptr;
582 9280387 : ret->right = nullptr;
583 9280387 : ret->setColor(NodeColor::Red);
584 9279488 : _allocator.construct(ret->value.ptr(), std::forward<Args>(args)...);
585 :
586 9266943 : return InsertData{&extract(ret->value), ret, nullptr, nullptr, false};
587 : }
588 :
589 35292 : InsertData constructKey(const Key &k) {
590 35292 : return InsertData{&k, nullptr, nullptr, nullptr, false};
591 : }
592 :
593 5676348 : InsertData constructKey(Key &&k) {
594 5676348 : return InsertData{&k, nullptr, nullptr, nullptr, false};
595 : }
596 :
597 : template <typename K, typename ... Args>
598 5710675 : Node<Value> *constructEmplace(K &&k, Args && ... args) {
599 5710675 : Node<Value> * ret = allocateNode();
600 5710673 : ret->parent = nullptr;
601 5710673 : ret->left = nullptr;
602 5710673 : ret->right = nullptr;
603 5710673 : ret->setColor(NodeColor::Red);
604 :
605 5710673 : TreeKeyExtractor<Key, Value>::construct(_allocator, ret, std::forward<K>(k), std::forward<Args>(args)...);
606 5710673 : return ret;
607 : }
608 :
609 : template <typename M>
610 : void constructAssign(Node<Value> *n, const M &m) {
611 : n->value.ref() = m;
612 : }
613 :
614 : template <typename M>
615 : void constructAssign(Node<Value> *n, M &&m) {
616 : n->value.ref() = std::move(m);
617 : }
618 :
619 6539403 : bool getInsertPositionUnique_search(InsertData &d) {
620 28026567 : while (d.current != nullptr) {
621 21434657 : d.parent = d.current;
622 21434657 : if (compareLtKey(*(d.key), extract(d.current))) {
623 11315990 : d.isLeft = true;
624 11315990 : d.current = static_cast<Node<Value> *> (d.current->left);
625 : } else {
626 10173092 : if (!compareLtKey(extract(d.current), *(d.key))) { // equality check
627 1965 : return false;
628 : }
629 10171174 : d.isLeft = false;
630 10171174 : d.current = static_cast<Node<Value> *> (d.current->right);
631 : }
632 : }
633 6591910 : return true;
634 : }
635 :
636 14960883 : bool getInsertPosition_tryRoot(InsertData &d) {
637 14960883 : if (_size == 0) {
638 1161460 : d.parent = nullptr;
639 1161460 : d.isLeft = true;
640 1161460 : d.current = nullptr;
641 1161460 : return true;
642 : }
643 13799423 : return false;
644 : }
645 :
646 13805782 : bool getInsertPositionUnique_tryHint(InsertData &d) {
647 13805782 : if (d.current == nullptr) {
648 13808583 : return false; // no hint provided
649 : }
650 :
651 : // check if hint is special value (begin or end)
652 0 : if (d.current == left() || static_cast<NodeBase *>(d.current) == &_header) {
653 0 : d.current = nullptr;
654 0 : return false; // this cases served by next two functions
655 : }
656 :
657 : // check if we can insert just before hint
658 0 : auto h = static_cast<Node<Value> *>(d.current);
659 0 : if (compareLtKey(*(d.key), extract(h->value))) {
660 : // check for bound
661 0 : auto p = static_cast<node_ptr>(NodeBase::decrement(d.current));
662 0 : if (compareLtKey(extract(p->value), *(d.key))) {
663 0 : d.parent = d.current;
664 0 : d.current = d.current->left;
665 0 : d.isLeft = true;
666 0 : if (!getInsertPositionUnique_search(d)) {
667 0 : return true; // stop searching, non-unique position, current is not null
668 : }
669 0 : return true;
670 : }
671 0 : } else if (compareLtKey(extract(h->value), *(d.key))) {
672 0 : auto p = static_cast<node_ptr>(NodeBase::increment(d.current));
673 0 : if (static_cast<NodeBase *>(p) == &_header) { // insert back case
674 0 : d.parent = d.current;
675 0 : d.current = d.current->right;
676 0 : d.isLeft = false;
677 0 : return true;
678 0 : } else if (compareLtKey(*(d.key), extract(p->value))) {
679 0 : d.parent = d.current;
680 0 : d.current = d.current->right;
681 0 : d.isLeft = false;
682 0 : if (!getInsertPositionUnique_search(d)) {
683 0 : return true; // stop searching, non-unique position, current is not null
684 : }
685 0 : return true;
686 : }
687 : } else { // hint and new one is equal
688 0 : return true; // current is hint, non-unique cancel
689 : }
690 :
691 0 : d.current = nullptr;
692 0 : return false;
693 : }
694 :
695 13802914 : bool getInsertPositionUnique_tryLeft(InsertData &d) {
696 13802914 : if (auto l = left()) {
697 13802734 : if (compareLtKey(*(d.key), extract(l->value))) {
698 1556787 : d.current = nullptr; d.parent = l; d.isLeft = true;
699 1556787 : return true;
700 12286217 : } else if (!compareLtKey(extract(l->value), *(d.key))) {
701 756 : d.current = l;
702 756 : return true;
703 : }
704 : }
705 12292218 : return false;
706 : }
707 :
708 12291307 : bool getInsertPositionUnique_tryRight(InsertData &d) {
709 12291307 : if (auto r = right()) {
710 12299030 : if (compareLtKey(extract(r->value), *(d.key))) {
711 5785799 : d.current = nullptr; d.parent = r; d.isLeft = false;
712 5785799 : return true;
713 6535648 : } else if (!compareLtKey(*(d.key), extract(r->value))) {
714 345 : d.current = r;
715 345 : return true;
716 : }
717 : }
718 6536280 : return false;
719 : }
720 :
721 14961788 : bool getInsertPositionUnique(InsertData &d) {
722 : // *_try* functions should return true with non-nullptr d.current
723 : // if new node is not unique to stop search process
724 14961788 : if (getInsertPosition_tryRoot(d)
725 13805314 : || getInsertPositionUnique_tryHint(d)
726 13807727 : || getInsertPositionUnique_tryLeft(d)
727 28788088 : || getInsertPositionUnique_tryRight(d)) {
728 8499177 : return d.current == nullptr;
729 : }
730 :
731 : // full-scan
732 6536172 : if (!d.current) { d.current = root(); }
733 : /* find where node belongs */
734 6539914 : return getInsertPositionUnique_search(d);
735 : }
736 :
737 : template <typename ... Args> Pair<Node<Value> *,bool>
738 9286656 : insertNodeUnique(Args && ... args) {
739 9286656 : InsertData d = constructNode(std::forward<Args>(args)...);
740 9250020 : if (!getInsertPositionUnique(d)) {
741 2150 : destroyNode(d.val);
742 2150 : return pair(static_cast<Node<Value> *>(d.current), false);
743 : }
744 :
745 9319074 : return pair(makeInsert(d.val, d.parent, d.isLeft), true);
746 : }
747 :
748 : template <typename ... Args> Node<Value> *
749 : insertNodeUniqueHint(const_iterator hint, Args && ... args) {
750 : InsertData d = constructNode(std::forward<Args>(args)...);
751 : d.current = hint.constcast()._node;
752 : if (!getInsertPositionUnique(d)) {
753 : destroyNode(d.val);
754 : return static_cast<Node<Value> *>(d.current);
755 : }
756 :
757 : return makeInsert(d.val, d.parent, d.isLeft);
758 : }
759 :
760 : template <typename K, typename ... Args> Pair<Node<Value> *,bool>
761 5711594 : tryInsertNodeUnique(K &&k, Args && ... args) {
762 5711594 : InsertData d = constructKey(std::forward<K>(k));
763 5711595 : if (!getInsertPositionUnique(d)) {
764 916 : return pair(static_cast<Node<Value> *>(d.current), false);
765 : }
766 :
767 5710675 : return pair(makeInsert(
768 : constructEmplace(std::forward<K>(k), std::forward<Args>(args)...),
769 11421354 : d.parent, d.isLeft), true);
770 : }
771 :
772 : template <typename K, typename ... Args> Node<Value> *
773 : tryInsertNodeUniqueHint(const_iterator hint, K &&k, Args && ... args) {
774 : InsertData d = constructKey(std::forward<K>(k));
775 : d.current = hint.constcast()._node;
776 : if (!getInsertPositionUnique(d)) {
777 : return static_cast<Node<Value> *>(d.current);
778 : }
779 :
780 : return makeInsert(constructEmplace(std::forward<K>(k), std::forward<Args>(args)...),
781 : d.parent, d.isLeft);
782 : }
783 :
784 : template <typename K, typename M> Pair<Node<Value> *,bool>
785 : tryAssignNodeUnique(K &&k, M &&m) {
786 : InsertData d = constructKey(std::forward<K>(k));
787 : if (!getInsertPositionUnique(d)) {
788 : constructAssign(d.current, std::forward<M>(m));
789 : return pair(static_cast<Node<Value> *>(d.current), false);
790 : }
791 :
792 : return pair(makeInsert(constructEmplace(std::forward<K>(k), std::forward<M>(m)),
793 : d.parent, d.isLeft), true);
794 : }
795 :
796 : template <typename K, typename M> Node<Value> *
797 : tryAssignNodeUniqueHint(const_iterator hint, K &&k, M &&m) {
798 : InsertData d = constructKey(std::forward<K>(k));
799 : d.current = hint.constcast()._node;
800 : if (!getInsertPositionUnique(d)) {
801 : constructAssign(d.current, std::forward<M>(m));
802 : return static_cast<Node<Value> *>(d.current);
803 : }
804 :
805 : return makeInsert(constructEmplace(std::forward<K>(k), std::forward<M>(m)),
806 : d.parent, d.isLeft);
807 : }
808 :
809 15029131 : Node<Value> * makeInsert(Node<Value> *n, NodeBase *parent, bool isLeft) {
810 15029131 : n->parent = parent;
811 15029131 : if (parent) {
812 13872738 : if (isLeft) {
813 5461017 : if (parent == left())
814 1557040 : setleft(n);
815 5460747 : parent->left = n;
816 : } else {
817 8411721 : if (parent == right())
818 5786189 : setright(n);
819 8433733 : parent->right = n;
820 : }
821 : } else {
822 1156393 : setleft(n);
823 1161421 : setright(n);
824 1161429 : setroot(n);
825 : }
826 :
827 15055922 : NodeBase::insert(&_header, n);
828 15029717 : ++ _size;
829 15029717 : return n;
830 : }
831 :
832 9218768 : void deleteNode(NodeBase * z) {
833 9218768 : NodeBase * x = nullptr;
834 9218768 : NodeBase * y = nullptr;
835 :
836 9218768 : if (!z) return;
837 :
838 9218768 : if (!z->left || !z->right) {
839 : /* y has a leaf node as a child */
840 5846704 : y = z;
841 :
842 5846704 : if (z == right()) {
843 1517207 : setright((z == left())?nullptr:NodeBase::decrement(z));
844 : }
845 5885452 : if (z == left()) {
846 1430080 : setleft(NodeBase::increment(z));
847 : }
848 : } else {
849 3372064 : y = z->left;
850 5222161 : while (y->right) y = y->right;
851 : }
852 :
853 : /* x is y's only child */
854 9253667 : if (y->left) {
855 2113065 : x = y->left;
856 : } else {
857 7140602 : x = y->right;
858 : }
859 :
860 9253667 : if (!x) {
861 : // if there is no replacement (we use empty leaf node as new Z),
862 : // we run rebalance with phantom Y node, then swap data and remove links
863 : // to phantom
864 6178786 : if (y->getColor() == NodeColor::Black) {
865 2748791 : NodeBase::remove(&_header, y);
866 : }
867 :
868 6202257 : if (y == y->parent->left)
869 3175765 : y->parent->left = nullptr;
870 : else
871 3026492 : y->parent->right = nullptr;
872 :
873 :
874 6202257 : if (y != z) {
875 : // copy node's data may be expensive, so, we keep data and replace node
876 2885169 : NodeBase::replace(z, y);
877 : }
878 :
879 : } else {
880 : // if we have replacement, we insert it at proper place then call rebalance
881 3074881 : x->parent = y->parent;
882 :
883 3074881 : if (y == y->parent->left)
884 2222144 : y->parent->left = x;
885 : else
886 852737 : y->parent->right = x;
887 :
888 3074881 : if (y != z) {
889 489531 : NodeBase::replace(z, y);
890 : } else {
891 2585350 : y->setColor(NodeColor::Red);
892 : }
893 :
894 3084383 : if (y->getColor() == NodeColor::Black) {
895 363100 : NodeBase::remove(&_header, x);
896 : } else {
897 2719401 : x->setColor(NodeColor::Black);
898 : }
899 : }
900 :
901 9287956 : destroyNode(static_cast<Node<Value> *>(z));
902 9220815 : -- _size;
903 : }
904 :
905 857804 : void clear_visit(Node<Value> *target) {
906 857804 : if (target->left) {
907 272461 : clear_visit(static_cast<Node<Value> *>(target->left));
908 : }
909 857802 : if (target->right) {
910 366945 : clear_visit(static_cast<Node<Value> *>(target->right));
911 : }
912 857799 : destroyNode(target);
913 857795 : }
914 :
915 5196650 : void clone_visit(const Node<Value> *source, Node<Value> *target) {
916 5196650 : _allocator.construct(target->value.ptr(), source->value.ref());
917 5196650 : target->setColor(source->getColor());
918 5196650 : if (source->left) {
919 2016075 : target->left = allocateNode();
920 2016075 : target->left->parent = target;
921 2016075 : clone_visit(static_cast<Node<Value> *>(source->left), static_cast<Node<Value> *>(target->left));
922 2016075 : if (_header.parent == source->left) { // check for leftmost node
923 675625 : _header.parent = target->left;
924 : }
925 : } else {
926 3180575 : target->left = nullptr;
927 : }
928 :
929 5196650 : if (source->right) {
930 2303900 : target->right = allocateNode();
931 2303900 : target->right->parent = target;
932 2303900 : clone_visit(static_cast<Node<Value> *>(source->right), static_cast<Node<Value> *>(target->right));
933 2303900 : if (_header.right == source->right) { // check for rightmost node
934 794300 : _header.right = target->right;
935 : }
936 : } else {
937 2892750 : target->right = nullptr;
938 : }
939 5196650 : }
940 :
941 877000 : void clone(const Tree &other) {
942 877000 : clear();
943 :
944 877000 : _size = other._size;
945 877000 : if (_size) {
946 876675 : allocateTmp(_size);
947 : }
948 :
949 : _comp = other._comp;
950 877000 : _header = other._header;
951 877000 : if (other._header.left) {
952 876675 : _header.left = allocateNode();
953 876675 : _header.left->parent = &_header;
954 876675 : if (other._header.left == other._header.parent) {
955 201050 : _header.parent = _header.left;
956 : }
957 876675 : if (other._header.left == other._header.right) {
958 82375 : _header.right = _header.left;
959 : }
960 876675 : clone_visit(static_cast<Node<Value> *>(other._header.left), static_cast<Node<Value> *>(_header.left));
961 : }
962 877000 : }
963 :
964 : template< class K >
965 1294141 : node_ptr find_impl(const K & x) const {
966 1294141 : const_node_ptr current = root();
967 3002736 : while(current) {
968 2335574 : if (compareLtTransparent(x, extract(current))) {
969 658964 : current = static_cast<const_node_ptr> (current->left);
970 : } else {
971 1676608 : if (!compareLtTransparent(extract(current), x)) { // equality check
972 626978 : return const_cast<node_ptr>(current);
973 : }
974 1049631 : current = static_cast<const_node_ptr> (current->right);
975 : }
976 : }
977 667162 : return nullptr;
978 : }
979 :
980 : template< class K >
981 14489632 : node_ptr lower_bound_ptr(const K& x) const {
982 14489632 : const_node_ptr current = root();
983 14481178 : const_node_ptr saved = nullptr;
984 60613475 : while (current) {
985 45987479 : if (!compareLtTransparent(extract(current), x)) {
986 24930097 : saved = current;
987 24930097 : current = static_cast<const_node_ptr> (current->left);
988 : } else {
989 21202200 : current = static_cast<const_node_ptr> (current->right);
990 : }
991 : }
992 14625996 : return const_cast<node_ptr>(saved);
993 : }
994 :
995 : template< class K >
996 : node_ptr upper_bound_ptr(const K& x) const {
997 : const_node_ptr current = root();
998 : const_node_ptr saved = current;
999 : while (current) {
1000 : if (compareLtTransparent(x, extract(current))) {
1001 : saved = current;
1002 : current = static_cast<const_node_ptr> (current->left);
1003 : } else {
1004 : current = static_cast<const_node_ptr> (current->right);
1005 : }
1006 : }
1007 : return const_cast<node_ptr>(saved);
1008 : }
1009 :
1010 : template< class K >
1011 : size_t count_impl(const K& x) const {
1012 : auto c = find_impl(x);
1013 : if (!c) {
1014 : return 0;
1015 : } else {
1016 : size_t ret = 1;
1017 : const_node_ptr next, current;
1018 :
1019 : current = c;
1020 : next = static_cast<const_node_ptr> (NodeBase::decrement(current));
1021 : while (next && !compareLtTransparent(extract(next), extract(current))) {
1022 : current = next;
1023 : next = static_cast<const_node_ptr> (NodeBase::decrement(current));
1024 : ret ++;
1025 : }
1026 :
1027 : current = c;
1028 : next = static_cast<const_node_ptr> (NodeBase::increment(current));
1029 : while (next && next != &_header && !compareLtTransparent(extract(current), extract(next))) {
1030 : current = next;
1031 : next = static_cast<const_node_ptr> (NodeBase::increment(current));
1032 : ret ++;
1033 : }
1034 : return ret;
1035 : }
1036 : }
1037 :
1038 10080322 : void destroyNode(Node<Value> *n) {
1039 10080322 : _allocator.destroy(n->value.ptr());
1040 10099465 : if (!_tmp) {
1041 : // no saved node - hold one
1042 1949607 : n->parent = nullptr;
1043 1949607 : _tmp = n;
1044 1949607 : ++ _header.flag.size; // increment capacity counter
1045 8149858 : } else if (n->isPrealloc() || _header.flag.prealloc) {
1046 : // node was preallocated - hold it in chain
1047 7735105 : n->parent = _tmp;
1048 7735105 : _tmp = n;
1049 7735105 : ++ _header.flag.size; // increment capacity counter
1050 : } else {
1051 : // deallocate node
1052 415281 : node_allocator_type(_allocator).__deallocate(n, 1, n->getSize());
1053 : }
1054 10099993 : }
1055 :
1056 20185359 : Node<Value> * allocateNode() {
1057 20185359 : if (_tmp) {
1058 16341982 : auto ret = _tmp;
1059 16341982 : _tmp = (Node<Value> *)ret->parent;
1060 16341982 : -- _header.flag.size; // decrement capacity counter
1061 16341982 : return ret;
1062 : } else {
1063 : size_t s;
1064 3843377 : auto ret = node_allocator_type(_allocator).__allocate(1, s);
1065 3847394 : ret->setSize(s);
1066 3847398 : ret->setPrealloc(false);
1067 3847399 : return ret;
1068 : }
1069 : }
1070 :
1071 1402103 : void allocateTmp(size_t count) {
1072 : // preallocate new n nodes
1073 :
1074 1402103 : uintptr_t preallocIdx = ++ _header.flag.index;
1075 1402103 : _header.flag.size += count; // increment capacity counter
1076 :
1077 : size_t s;
1078 1402103 : auto ret = node_allocator_type(_allocator).__allocate(count, s);
1079 1402003 : auto n = ret;
1080 :
1081 10011901 : for (size_t i = 0; i < count; ++ i) {
1082 8609646 : NodeBase *tmpN = n;
1083 8609646 : tmpN->parent = n + 1;
1084 8609646 : tmpN->setPrealloc(true);
1085 8608931 : tmpN->setIndex(preallocIdx);
1086 8610695 : if (i < count - 1) {
1087 7208464 : tmpN->parent = n + 1;
1088 7208464 : tmpN->setSize(sizeof(Node<Value>));
1089 7207877 : s -= sizeof(Node<Value>);
1090 : } else {
1091 1402231 : tmpN->parent = _tmp;
1092 1402231 : n->setSize(s);
1093 : }
1094 8609898 : ++ n;
1095 : }
1096 1402255 : _tmp = ret;
1097 1402255 : }
1098 :
1099 472453 : void releaseTmp() {
1100 : // release any tmp nodes if possible
1101 : // preallocated nodes released in batch as acquired, only if tree is empty
1102 :
1103 : struct PreallocatedData {
1104 : Node<Value> *head = (Node<Value> *)maxOf<uintptr_t>();
1105 : size_t count = 0;
1106 : size_t size = 0;
1107 : };
1108 :
1109 472453 : if (_size != 0) {
1110 : // release only free tmps;
1111 25 : auto ptr = &_tmp;
1112 150 : while (*ptr) {
1113 125 : if (!(*ptr)->isPrealloc()) {
1114 75 : node_allocator_type(_allocator).__deallocate(*ptr, 1, (*ptr)->getSize());
1115 75 : *ptr = (Node<Value> *)(*ptr)->parent;
1116 75 : -- _header.flag.size;
1117 : } else {
1118 50 : ptr = (Node<Value> **)&((*ptr)->parent);
1119 : }
1120 : }
1121 25 : return;
1122 : }
1123 :
1124 472428 : if (_header.flag.index == 0) {
1125 : // no preallocated blocks
1126 558378 : while (_tmp) {
1127 250917 : auto ptr = _tmp;
1128 250917 : _tmp = (Node<Value> *)_tmp->parent;
1129 250917 : node_allocator_type(_allocator).__deallocate(ptr, 1, ptr->getSize());
1130 250919 : -- _header.flag.size;
1131 : }
1132 307461 : _tmp = nullptr;
1133 164970 : } else if (_header.flag.index == 1) {
1134 : // all preallocated nodes should be in tmp chain, only one preallocated block
1135 164959 : PreallocatedData data;
1136 :
1137 1828991 : while (_tmp) {
1138 1663803 : auto ptr = _tmp;
1139 1663803 : _tmp = (Node<Value> *)_tmp->parent;
1140 :
1141 1663803 : if (ptr->isPrealloc()) {
1142 1217849 : if (ptr < data.head) {
1143 353294 : data.head = ptr;
1144 : }
1145 1217849 : ++ data.count;
1146 1217849 : data.size += ptr->getSize();
1147 : } else {
1148 445972 : node_allocator_type(_allocator).__deallocate(ptr, 1, ptr->getSize());
1149 446087 : -- _header.flag.size;
1150 : }
1151 : }
1152 165188 : if (data.head != (Node<Value> *)maxOf<uintptr_t>()) {
1153 164929 : _header.flag.size -= data.count;
1154 164929 : node_allocator_type(_allocator).__deallocate(data.head, data.count, data.size);
1155 : }
1156 : } else {
1157 : // multiple preallocated blocks make things complicated
1158 : // VLA, compilers should support C99,
1159 : // MSVC - fuck off, use new[] or std::vector=)
1160 11 : PreallocatedData data[_header.flag.index];
1161 :
1162 0 : while (_tmp) {
1163 0 : auto ptr = _tmp;
1164 0 : _tmp = (Node<Value> *)_tmp->parent;
1165 :
1166 0 : if (ptr->isPrealloc()) {
1167 0 : if (ptr < data[ptr->getIndex() - 1].head) {
1168 0 : data[ptr->getIndex() - 1].head = ptr;
1169 : }
1170 0 : ++ data[ptr->getIndex() - 1].count;
1171 0 : data[ptr->getIndex() - 1].size += ptr->getSize();
1172 : } else {
1173 0 : node_allocator_type(_allocator).__deallocate(ptr, 1, ptr->getSize());
1174 0 : -- _header.flag.size;
1175 : }
1176 : }
1177 0 : for (size_t i = 0; i < _header.flag.index; ++ i) {
1178 0 : if (data[i].head != (Node<Value> *)maxOf<uintptr_t>()) {
1179 0 : _header.flag.size -= data[i].count;
1180 0 : node_allocator_type(_allocator).__deallocate(data[i].head, data[i].count, data[i].size);
1181 : }
1182 : }
1183 11 : }
1184 472379 : _tmp = nullptr;
1185 : }
1186 : };
1187 :
1188 : }
1189 :
1190 : #if SP_MEM_RBTREE_DEBUG
1191 :
1192 : namespace STAPPLER_VERSIONIZED stappler::memory::rbtree {
1193 :
1194 : class TreeDebug {
1195 : public:
1196 : enum class Validation {
1197 : Valid,
1198 : RootIsNotBlack,
1199 : RedChildIntoRedNode,
1200 : DifferentBlackNodeCount,
1201 : };
1202 :
1203 : template <class T>
1204 : static void visit(const T & tree, std::ostream &stream) {
1205 : typename T::const_node_ptr r = tree.root();
1206 : stream << "visit " << (void *)r << " header: " << tree._header.left << " | " << tree._header.right << " | " << tree._header.parent;
1207 : stream << "\n";
1208 : if (r) {
1209 : visit(tree, stream, static_cast<typename T::const_node_ptr>(r), 0);
1210 : }
1211 : }
1212 :
1213 : template <class T>
1214 : static Validation validate(const T & tree) {
1215 : if (tree._header.left && tree._header.left->flag.color == NodeColor::Red) {
1216 : return Validation::RootIsNotBlack;
1217 : } else {
1218 : auto counter = 0;
1219 : auto root = tree._header.left;
1220 : while (root) {
1221 : if (root->flag.color == NodeColor::Black) ++counter;
1222 : root = root->left;
1223 : }
1224 : return validate(counter, tree._header.left, 0);
1225 : }
1226 : }
1227 :
1228 : //static bool make_test(std::ostream &stream, int size = 128);
1229 : //static bool make_test(std::ostream &stream, const apr::array<int> &insert, const apr::array<int> &erase);
1230 :
1231 : static bool make_hint_test(std::ostream &stream, int size = 128);
1232 : protected:
1233 : template <class T>
1234 : static void visit(const T & tree, std::ostream &stream, typename T::const_node_ptr node, int depth) {
1235 : if (node->left) {
1236 : visit(tree, stream, static_cast<typename T::const_node_ptr>(node->left), depth + 1);
1237 : }
1238 : for (int i = 0; i < depth; i++) {
1239 : stream << "--";
1240 : }
1241 : stream << (void *)node << " l:" << (void *)node->left << " r:" << (void *)node->right << " p:"
1242 : << (void *)node->parent << " v:" << *(node->value.ptr()) << (node->flag.color?" black":" red") << "\n";
1243 : if (node->right) {
1244 : visit(tree, stream, static_cast<typename T::const_node_ptr>(node->right), depth + 1);
1245 : }
1246 : }
1247 :
1248 : static Validation validate(int counter, NodeBase *node, int path) {
1249 : if (node == nullptr) {
1250 : if (counter != path) {
1251 : return Validation::DifferentBlackNodeCount;
1252 : }
1253 : return Validation::Valid;
1254 : } else {
1255 : if (node->flag.color == NodeColor::Black) {
1256 : auto res = validate(counter, node->left, path + 1);
1257 : if (res == Validation::Valid) {
1258 : res = validate(counter, node->right, path + 1);
1259 : }
1260 : return res;
1261 : } else {
1262 : if ((node->left && node->left->flag.color == NodeColor::Red)
1263 : || (node->right && node->right->flag.color == NodeColor::Red)) {
1264 : return Validation::RedChildIntoRedNode;
1265 : } else {
1266 : auto res = validate(counter, node->left, path);
1267 : if (res == Validation::Valid) {
1268 : res = validate(counter, node->right, path);
1269 : }
1270 : return res;
1271 : }
1272 : }
1273 : }
1274 : }
1275 : };
1276 :
1277 : template<typename CharType> inline std::basic_ostream<CharType> &
1278 : operator << (std::basic_ostream<CharType> & os, const TreeDebug::Validation & v) {
1279 : switch(v) {
1280 : case TreeDebug::Validation::Valid: os << "Valid"; break;
1281 : case TreeDebug::Validation::DifferentBlackNodeCount: os << "DifferentBlackNodeCount"; break;
1282 : case TreeDebug::Validation::RedChildIntoRedNode: os << "RedChildIntoRedNode"; break;
1283 : case TreeDebug::Validation::RootIsNotBlack: os << "RootIsNotBlack"; break;
1284 : }
1285 : return os;
1286 : }
1287 :
1288 : }
1289 :
1290 : #endif // SP_MEM_RBTREE_DEBUG
1291 :
1292 : #endif /* STAPPLER_CORE_MEMORY_SPMEMRBTREE_H_ */
|
