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_SPMEMSET_H_
25 : #define STAPPLER_CORE_MEMORY_SPMEMSET_H_
26 :
27 : #include "SPMemRbtree.h"
28 :
29 : namespace STAPPLER_VERSIONIZED stappler::memory {
30 :
31 : template <typename Value, typename Comp = std::less<>>
32 : class set : public AllocPool {
33 : public:
34 : using key_type = Value;
35 : using value_type = Value;
36 : using key_compare = Comp;
37 : using value_compare = Comp;
38 : using allocator_type = Allocator<Value>;
39 :
40 : using pointer = Value *;
41 : using const_pointer = const Value *;
42 : using reference = Value &;
43 : using const_reference = const Value &;
44 :
45 : using tree_type = rbtree::Tree<Value, Value, Comp>;
46 :
47 : using iterator = typename tree_type::const_iterator ;
48 : using const_iterator = typename tree_type::const_iterator ;
49 : using reverse_iterator = typename tree_type::const_reverse_iterator ;
50 : using const_reverse_iterator = typename tree_type::const_reverse_iterator ;
51 : using size_type = size_t;
52 : using difference_type = std::ptrdiff_t;
53 :
54 : public:
55 44060 : set() noexcept : _tree() { }
56 : explicit set (const key_compare & comp, const allocator_type & alloc = allocator_type()) noexcept : _tree(comp, alloc) { }
57 128766 : explicit set (const allocator_type & alloc) noexcept : _tree(key_compare(), alloc) { }
58 :
59 : template <class InputIterator>
60 : set (InputIterator first, InputIterator last,
61 : const key_compare & comp = key_compare(), const allocator_type & alloc = allocator_type())
62 : : _tree(comp, alloc) {
63 : for (auto it = first; it != last; it ++) {
64 : emplace(*it);
65 : }
66 : }
67 :
68 : template <class InputIterator>
69 : set (InputIterator first, InputIterator last, const allocator_type & alloc)
70 : : _tree(key_compare(), alloc) {
71 : for (auto it = first; it != last; it ++) {
72 : emplace(*it);
73 : }
74 : }
75 :
76 175 : set (const set& x) noexcept : _tree(x._tree) { }
77 : set (const set& x, const allocator_type& alloc) noexcept : _tree(x._tree, alloc) { }
78 :
79 9950 : set (set&& x) noexcept : _tree(std::move(x._tree)) { }
80 : set (set&& x, const allocator_type& alloc) noexcept : _tree(std::move(x._tree), alloc) { }
81 :
82 0 : set (InitializerList<value_type> il,
83 : const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()) noexcept
84 0 : : _tree(comp, alloc) {
85 0 : for (auto &it : il) {
86 0 : emplace(std::move(it));
87 : }
88 0 : }
89 : set (InitializerList<value_type> il, const allocator_type& alloc) noexcept
90 : : _tree(key_compare(), alloc) {
91 : for (auto &it : il) {
92 : emplace(std::move(it));
93 : }
94 : }
95 :
96 : set& operator= (const set& other) noexcept {
97 : _tree = other._tree;
98 : return *this;
99 : }
100 225 : set& operator= (set&& other) noexcept {
101 225 : _tree = std::move(other._tree);
102 225 : return *this;
103 : }
104 : set& operator= (InitializerList<value_type> ilist) noexcept {
105 : _tree.clear();
106 : for (auto &it : ilist) {
107 : emplace(std::move(it));
108 : }
109 : return *this;
110 : }
111 :
112 : allocator_type get_allocator() const noexcept { return _tree.get_allocator(); }
113 23579190 : bool empty() const noexcept { return _tree.empty(); }
114 9538 : size_t size() const noexcept { return _tree.size(); }
115 : size_t capacity() const noexcept { return _tree.capacity(); }
116 : void clear() { _tree.clear(); }
117 : void shrink_to_fit() { _tree.shrink_to_fit(); }
118 :
119 128852 : void set_memory_persistent(bool value) noexcept { _tree.set_memory_persistent(value); }
120 : bool memory_persistent() const noexcept { return _tree.memory_persistent(); }
121 :
122 75 : Pair<iterator,bool> insert( const value_type& value ) {
123 75 : return emplace(value);
124 : }
125 :
126 0 : Pair<iterator,bool> insert( value_type&& value ) {
127 0 : return emplace(std::move(value));
128 : }
129 :
130 : iterator insert( const_iterator hint, const value_type& value ) {
131 : return emplace_hint(hint, value);
132 : }
133 :
134 : iterator insert( const_iterator hint, value_type&& value ) {
135 : return emplace_hint(hint, std::move(value));
136 : }
137 :
138 : template< class InputIt > void insert( InputIt first, InputIt last ) {
139 : for (auto it = first; it != last; it ++) {
140 : emplace(*it);
141 : }
142 : }
143 :
144 : void insert( InitializerList<value_type> ilist ) {
145 : for (auto &it : ilist) {
146 : emplace(std::move(it));
147 : }
148 : }
149 :
150 : template< class... Args >
151 9302238 : Pair<iterator,bool> emplace( Args && ... args ) {
152 9302238 : return _tree.emplace(std::forward<Args>(args)...);
153 : }
154 :
155 : template <class... Args>
156 : iterator emplace_hint( const_iterator hint, Args&&... args ) {
157 : return _tree.emplace_hint(hint, std::forward<Args>(args)...);
158 : }
159 :
160 9231127 : iterator erase( const_iterator pos ) { return _tree.erase(pos); }
161 : iterator erase( const_iterator first, const_iterator last ) { return _tree.erase(first, last); }
162 0 : size_type erase( const key_type& key ) { return _tree.erase_unique(key); }
163 :
164 8845663 : iterator begin() noexcept { return _tree.begin(); }
165 86506723 : iterator end() noexcept { return _tree.end(); }
166 :
167 28168917 : const_iterator begin() const noexcept { return _tree.begin(); }
168 17969289 : const_iterator end() const noexcept { return _tree.end(); }
169 :
170 : const_iterator cbegin() const noexcept { return _tree.cbegin(); }
171 : const_iterator cend() const noexcept { return _tree.cend(); }
172 :
173 : reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
174 : reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
175 :
176 : const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
177 : const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
178 :
179 : const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }
180 : const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }
181 :
182 : void swap(set &other) noexcept {
183 : _tree.swap(other._tree);
184 : }
185 :
186 775 : template< class K > iterator find( const K& x ) { return _tree.find(x); }
187 155900 : template< class K > const_iterator find( const K& x ) const { return _tree.find(x); }
188 :
189 9208662 : template< class K > iterator lower_bound(const K& x) { return _tree.lower_bound(x); }
190 5294824 : template< class K > const_iterator lower_bound(const K& x) const { return _tree.lower_bound(x); }
191 :
192 : template< class K > iterator upper_bound( const K& x ) { return _tree.upper_bound(x); }
193 : template< class K > const_iterator upper_bound( const K& x ) const { return _tree.upper_bound(x); }
194 :
195 : template< class K > Pair<iterator,iterator> equal_range( const K& x ) { return _tree.equal_range(x); }
196 : template< class K > Pair<const_iterator,const_iterator> equal_range( const K& x ) const { return _tree.equal_range(x); }
197 :
198 : template< class K > size_t count( const K& x ) const { return _tree.count_unique(x); }
199 :
200 128804 : void reserve(size_t c) { _tree.reserve(c); }
201 :
202 : #if MEM_RBTREE_DEBUG
203 : public:
204 : #else
205 : protected:
206 : #endif
207 : rbtree::Tree<Value, Value, Comp> _tree;
208 : };
209 :
210 : template<typename _Tp, typename Comp> inline bool
211 : operator==(const set<_Tp, Comp>& __x, const set<_Tp, Comp>& __y) {
212 : return (__x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()));
213 : }
214 :
215 : template<typename _Tp, typename Comp> inline bool
216 : operator<(const set<_Tp, Comp>& __x, const set<_Tp, Comp>& __y) {
217 : return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
218 : }
219 :
220 : /// Based on operator==
221 : template<typename _Tp, typename Comp> inline bool
222 : operator!=(const set<_Tp, Comp>& __x, const set<_Tp, Comp>& __y) {
223 : return !(__x == __y);
224 : }
225 :
226 : /// Based on operator<
227 : template<typename _Tp, typename Comp> inline bool
228 : operator>(const set<_Tp, Comp>& __x, const set<_Tp, Comp>& __y) {
229 : return __y < __x;
230 : }
231 :
232 : /// Based on operator<
233 : template<typename _Tp, typename Comp> inline bool
234 : operator<=(const set<_Tp, Comp>& __x, const set<_Tp, Comp>& __y) {
235 : return !(__y < __x);
236 : }
237 :
238 : /// Based on operator<
239 : template<typename _Tp, typename Comp> inline bool
240 : operator>=(const set<_Tp, Comp>& __x, const set<_Tp, Comp>& __y) {
241 : return !(__x < __y);
242 : }
243 :
244 : /// See std::vector::swap().
245 : template<typename _Tp, typename Comp> inline void
246 : swap(set<_Tp, Comp>& __x, set<_Tp, Comp>& __y) noexcept {
247 : __x.swap(__y);
248 : }
249 :
250 : }
251 :
252 : #endif /* STAPPLER_CORE_MEMORY_SPMEMSET_H_ */
|
