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_SPMEMMAP_H_
25 : #define STAPPLER_CORE_MEMORY_SPMEMMAP_H_
26 :
27 : #include "SPMemRbtree.h"
28 :
29 : namespace STAPPLER_VERSIONIZED stappler::memory {
30 :
31 : template <typename Key, typename Value, typename Comp = std::less<>>
32 : class map : public AllocPool {
33 : public:
34 : using key_type = Key;
35 : using mapped_type = Value;
36 : using value_type = Pair<const Key, Value>;
37 : using key_compare = Comp;
38 : using allocator_type = Allocator<value_type>;
39 :
40 : using pointer = value_type *;
41 : using const_pointer = const value_type *;
42 : using reference = value_type &;
43 : using const_reference = const value_type &;
44 :
45 : using tree_type = rbtree::Tree<Key, value_type, Comp>;
46 :
47 : using iterator = typename tree_type::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 1103177 : map() noexcept : map( Comp() ) { }
56 :
57 1103167 : explicit map(const Comp& comp, const allocator_type& alloc = allocator_type()) noexcept : _tree(comp, alloc) { }
58 : explicit map(const allocator_type& alloc) noexcept : _tree(key_compare(), alloc) { }
59 :
60 : template<class InputIterator>
61 : map(InputIterator first, InputIterator last,
62 : const Comp& comp = Comp(), const allocator_type& alloc = allocator_type())
63 : : _tree(comp, alloc) {
64 : for (auto it = first; it != last; it ++) {
65 : do_insert(*it);
66 : }
67 : }
68 : template< class InputIterator >
69 : map( InputIterator first, InputIterator last, const allocator_type& alloc ) : _tree(key_compare(), alloc) {
70 : for (auto it = first; it != last; it ++) {
71 : do_insert(*it);
72 : }
73 : }
74 :
75 876500 : map(const map& x) noexcept : _tree(x._tree) { }
76 : map(const map& x, const allocator_type& alloc) noexcept : _tree(x._tree, alloc) { }
77 :
78 36343 : map(map&& x) noexcept : _tree(std::move(x._tree)) { }
79 : map(map&& x, const allocator_type& alloc) noexcept : _tree(std::move(x._tree), alloc) { }
80 :
81 75 : map(InitializerList<value_type> il,
82 : const Comp& comp = Comp(), const allocator_type& alloc = allocator_type()) noexcept
83 75 : : _tree(comp, alloc) {
84 200 : for (auto &it : il) {
85 125 : do_insert(std::move(const_cast<reference>(it)));
86 : }
87 75 : }
88 : map(InitializerList<value_type> il, const allocator_type& alloc) noexcept
89 : : _tree(key_compare(), alloc) {
90 : for (auto &it : il) {
91 : do_insert(std::move(const_cast<reference>(it)));
92 : }
93 : }
94 :
95 : map& operator= (const map& other) noexcept {
96 : _tree = other._tree;
97 : return *this;
98 : }
99 2400 : map& operator= (map&& other) noexcept {
100 2400 : _tree = std::move(other._tree);
101 2400 : return *this;
102 : }
103 : map& operator= (InitializerList<value_type> ilist) noexcept {
104 : _tree.clear();
105 : for (auto &it : ilist) {
106 : do_insert(std::move(const_cast<reference>(it)));
107 : }
108 : return *this;
109 : }
110 :
111 22150 : allocator_type get_allocator() const noexcept { return _tree.get_allocator(); }
112 24125 : bool empty() const noexcept { return _tree.empty(); }
113 657125 : size_t size() const noexcept { return _tree.size(); }
114 375 : size_t capacity() const noexcept { return _tree.capacity(); }
115 6346 : void clear() { _tree.clear(); }
116 75 : void shrink_to_fit() { _tree.shrink_to_fit(); }
117 :
118 25 : void set_memory_persistent(bool value) noexcept { _tree.set_memory_persistent(value); }
119 : bool memory_persistent() const noexcept { return _tree.memory_persistent(); }
120 :
121 : Value& at(const Key& key) {
122 : auto it = find(key);
123 : if (it == end()) {
124 : //throw std::out_of_range("Invalid key for apr::map");
125 : }
126 : return it->second;
127 : }
128 36550 : const Value& at(const Key& key) const {
129 36550 : auto it = find(key);
130 36550 : if (it == end()) {
131 : //throw std::out_of_range("Invalid key for apr::map");
132 : }
133 36550 : return it->second;
134 : }
135 :
136 : Value& operator[] ( const Key& key ) {
137 : return this->try_emplace(key).first->second;
138 : }
139 : Value& operator[] ( Key&& key ) {
140 : return this->try_emplace(std::move(key)).first->second;
141 : }
142 :
143 1481788 : iterator begin() noexcept { return _tree.begin(); }
144 2447696 : iterator end() noexcept { return _tree.end(); }
145 :
146 101555 : const_iterator begin() const noexcept { return _tree.begin(); }
147 527198 : const_iterator end() const noexcept { return _tree.end(); }
148 :
149 : const_iterator cbegin() const noexcept { return _tree.cbegin(); }
150 : const_iterator cend() const noexcept { return _tree.cend(); }
151 :
152 : reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
153 : reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
154 :
155 : const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
156 : const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
157 :
158 : const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }
159 : const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }
160 :
161 : void swap(map &other) noexcept { _tree.swap(other._tree); }
162 :
163 : template <class P>
164 : Pair<iterator,bool> insert( P&& value ) {
165 : return do_insert(std::forward<P>(value));
166 : }
167 :
168 : template <class P>
169 : iterator insert( const_iterator hint, P&& value ) {
170 : return do_insert(hint, std::forward<P>(value));
171 : }
172 :
173 : template< class InputIt >
174 : void insert( InputIt first, InputIt last ) {
175 : for (auto it = first; it != last; it ++) {
176 : do_insert(*it);
177 : }
178 : }
179 :
180 : void insert( InitializerList<value_type> ilist ) {
181 : for (auto &it : ilist) {
182 : do_insert(std::move(it));
183 : }
184 : }
185 :
186 :
187 : template <class M>
188 : Pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) {
189 : return _tree.insert_or_assign(k, obj);
190 : }
191 :
192 : template <class M>
193 : Pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
194 : return _tree.insert_or_assign(std::move(k), obj);
195 : }
196 :
197 : template <class M>
198 : iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj) {
199 : return _tree.insert_or_assign(hint, k, obj);
200 : }
201 :
202 : template <class M>
203 : iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) {
204 : return _tree.insert_or_assign(hint, std::move(k), obj);
205 : }
206 :
207 :
208 : template< class... Args >
209 5711191 : Pair<iterator,bool> emplace( Args&&... args ) {
210 5711191 : auto ret = try_emplace(std::forward<Args>(args)...);
211 5711191 : if (!ret.second) {
212 916 : do_assign(ret.first, std::forward<Args>(args)...);
213 : }
214 5711190 : return ret;
215 : }
216 :
217 : template <class... Args>
218 : iterator emplace_hint( const_iterator hint, Args&&... args ) {
219 : auto ret = _tree.emplace_hint(hint, std::forward<Args>(args)...);
220 : if (!ret.second) {
221 : do_assign(ret.first, std::forward<Args>(args)...);
222 : }
223 : return ret.first;
224 : }
225 :
226 :
227 : template <class... Args>
228 35292 : Pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) {
229 35292 : return _tree.try_emplace(k, std::forward<Args>(args)...);
230 : }
231 :
232 : template <class... Args>
233 5676300 : Pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
234 5676300 : return _tree.try_emplace(std::move(k), std::forward<Args>(args)...);
235 : }
236 :
237 : template <class... Args>
238 : iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) {
239 : return _tree.try_emplace(hint, k, std::forward<Args>(args)...);
240 : }
241 :
242 : template <class... Args>
243 : iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) {
244 : return _tree.try_emplace(hint, std::move(k), std::forward<Args>(args)...);
245 : }
246 :
247 5517 : iterator erase( const_iterator pos ) { return _tree.erase(pos); }
248 : iterator erase( const_iterator first, const_iterator last ) { return _tree.erase(first, last); }
249 300 : size_type erase( const key_type& key ) { return _tree.erase_unique(key); }
250 :
251 :
252 769453 : template< class K > iterator find( const K& x ) { return _tree.find(x); }
253 425697 : template< class K > const_iterator find( const K& x ) const { return _tree.find(x); }
254 :
255 : template< class K > iterator lower_bound(const K& x) { return _tree.lower_bound(x); }
256 : template< class K > const_iterator lower_bound(const K& x) const { return _tree.lower_bound(x); }
257 :
258 : template< class K > iterator upper_bound( const K& x ) { return _tree.upper_bound(x); }
259 : template< class K > const_iterator upper_bound( const K& x ) const { return _tree.upper_bound(x); }
260 :
261 : template< class K > Pair<iterator,iterator> equal_range( const K& x ) { return _tree.equal_range(x); }
262 : template< class K > Pair<const_iterator,const_iterator> equal_range( const K& x ) const { return _tree.equal_range(x); }
263 :
264 : template< class K > size_t count( const K& x ) const { return _tree.count_unique(x); }
265 :
266 396700 : void reserve(size_t c) { _tree.reserve(c); }
267 :
268 : protected:
269 : template <class A, class B>
270 : Pair<iterator,bool> do_insert( const Pair<A, B> & value ) {
271 : return emplace(value.first, value.second);
272 : }
273 :
274 : template <class A, class B>
275 125 : Pair<iterator,bool> do_insert( Pair<A, B> && value ) {
276 125 : return emplace(std::move(value.first), std::move(value.second));
277 : }
278 :
279 : template <class A, class B>
280 : iterator do_insert( const_iterator hint, const Pair<A, B> & value ) {
281 : return emplace_hint(hint, value.first, value.second);
282 : }
283 :
284 : template <class A, class B>
285 : iterator do_insert( const_iterator hint, Pair<A, B> && value ) {
286 : return emplace_hint(hint, std::move(value.first), std::move(value.second));
287 : }
288 :
289 : template <class T, class ... Args>
290 916 : void do_assign( iterator it, T &&, Args && ... args) {
291 916 : it->second = Value(std::forward<Args>(args)...);
292 916 : }
293 :
294 : rbtree::Tree<Key, Pair<const Key, Value>, Comp> _tree;
295 : };
296 :
297 : template<typename Key, typename Value, typename Comp> inline bool
298 50 : operator==(const map<Key, Value, Comp>& __x, const map<Key, Value, Comp>& __y) {
299 50 : return (__x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()));
300 : }
301 :
302 : template<typename Key, typename Value, typename Comp> inline bool
303 : operator<(const map<Key, Value, Comp>& __x, const map<Key, Value, Comp>& __y) {
304 : return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
305 : }
306 :
307 : /// Based on operator==
308 : template<typename Key, typename Value, typename Comp> inline bool
309 : operator!=(const map<Key, Value, Comp>& __x, const map<Key, Value, Comp>& __y) {
310 : return !(__x == __y);
311 : }
312 :
313 : /// Based on operator<
314 : template<typename Key, typename Value, typename Comp> inline bool
315 : operator>(const map<Key, Value, Comp>& __x, const map<Key, Value, Comp>& __y) {
316 : return __y < __x;
317 : }
318 :
319 : /// Based on operator<
320 : template<typename Key, typename Value, typename Comp> inline bool
321 : operator<=(const map<Key, Value, Comp>& __x, const map<Key, Value, Comp>& __y) {
322 : return !(__y < __x);
323 : }
324 :
325 : /// Based on operator<
326 : template<typename Key, typename Value, typename Comp> inline bool
327 : operator>=(const map<Key, Value, Comp>& __x, const map<Key, Value, Comp>& __y) {
328 : return !(__x < __y);
329 : }
330 :
331 : }
332 :
333 : #endif /* STAPPLER_CORE_MEMORY_SPMEMMAP_H_ */
|
