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_COMMON_MEMORY_SPMEMDICT_H_
25 : #define STAPPLER_COMMON_MEMORY_SPMEMDICT_H_
26 :
27 : #include "SPMemString.h"
28 : #include "SPMemVector.h"
29 :
30 : namespace STAPPLER_VERSIONIZED stappler::memory {
31 :
32 : template <typename Key, typename Value, typename Comp = std::less<>>
33 : class dict : public AllocPool {
34 : public:
35 : using key_type = Key;
36 : using mapped_type = Value;
37 : using value_type = Pair<const Key, Value>;
38 : using key_compare = Comp;
39 : using comparator_type = Comp;
40 : using allocator_type = Allocator<value_type>;
41 :
42 : using pointer = value_type *;
43 : using const_pointer = const value_type *;
44 : using reference = value_type &;
45 : using const_reference = const value_type &;
46 :
47 : using vector_type = storage_mem<value_type>;
48 :
49 : using iterator = typename vector_type::iterator;
50 : using const_iterator = typename vector_type::const_iterator;
51 : using reverse_iterator = typename vector_type::const_reverse_iterator;
52 : using const_reverse_iterator = typename vector_type::const_reverse_iterator;
53 : using size_type = size_t;
54 : using difference_type = std::ptrdiff_t;
55 :
56 : template <typename T>
57 : struct value_comparator {
58 83738 : bool operator() (const value_type &l, const T &r) {
59 83738 : return comp(l.first, r);
60 : }
61 : bool operator() (const T &l, const value_type &r) {
62 : return comp(l, r.first);
63 : }
64 : bool operator() (const value_type &l, const value_type &r) {
65 : return comp(l.first, r.first);
66 : }
67 :
68 : comparator_type comp;
69 : };
70 :
71 : public:
72 15248 : dict() noexcept : dict( Comp() ) { }
73 :
74 15248 : explicit dict(const Comp& comp, const allocator_type& alloc = allocator_type()) noexcept : _data(alloc), _comp(comp) { }
75 : explicit dict(const allocator_type& alloc) noexcept : _data(alloc), _comp(key_compare()) { }
76 :
77 : template<class InputIterator>
78 : dict(InputIterator first, InputIterator last,
79 : const Comp& comp = Comp(), const allocator_type& alloc = allocator_type())
80 : : _data(alloc), _comp(comp) {
81 : for (auto it = first; it != last; it ++) {
82 : do_insert(*it);
83 : }
84 : }
85 : template< class InputIterator >
86 : dict( InputIterator first, InputIterator last, const allocator_type& alloc ) : _data(alloc), _comp(key_compare()) {
87 : for (auto it = first; it != last; it ++) {
88 : do_insert(*it);
89 : }
90 : }
91 :
92 50 : dict(const dict& x) noexcept : _data(x._data), _comp(x._comp) { }
93 : dict(const dict& x, const allocator_type& alloc) noexcept : _data(x._data, alloc), _comp(x._comp) { }
94 :
95 48 : dict(dict&& x) noexcept : _data(std::move(x._data)), _comp(std::move(x._comp)) { }
96 : dict(dict&& x, const allocator_type& alloc) noexcept : _data(std::move(x._data), alloc), _comp(std::move(x._comp)) { }
97 :
98 : dict(InitializerList<value_type> il,
99 : const Comp& comp = Comp(), const allocator_type& alloc = allocator_type()) noexcept
100 : : _data(alloc), _comp(comp) {
101 : for (auto &it : il) {
102 : do_insert(std::move(const_cast<reference>(it)));
103 : }
104 : }
105 : dict(InitializerList<value_type> il, const allocator_type& alloc) noexcept
106 : : _data(alloc), _comp(key_compare()) {
107 : for (auto &it : il) {
108 : do_insert(std::move(const_cast<reference>(it)));
109 : }
110 : }
111 :
112 : dict& operator= (const dict& other) noexcept {
113 : _data = other._data;
114 : _comp = other._comp;
115 : return *this;
116 : }
117 0 : dict& operator= (dict&& other) noexcept {
118 0 : _data = std::move(other._data);
119 0 : _comp = std::move(other._comp);
120 0 : return *this;
121 : }
122 : dict& operator= (InitializerList<value_type> ilist) noexcept {
123 : _data.clear();
124 : for (auto &it : ilist) {
125 : do_insert(std::move(const_cast<reference>(it)));
126 : }
127 : return *this;
128 : }
129 :
130 : void reserve( size_type new_cap ) { _data.reserve(new_cap); }
131 :
132 : allocator_type get_allocator() const noexcept { return _data.get_allocator(); }
133 : bool empty() const noexcept { return _data.empty(); }
134 150 : size_t size() const noexcept { return _data.size(); }
135 2325 : void clear() { _data.clear(); }
136 :
137 75 : iterator begin() noexcept { return _data.begin(); }
138 41869 : iterator end() noexcept { return _data.end(); }
139 :
140 150 : const_iterator begin() const noexcept { return _data.begin(); }
141 75 : const_iterator end() const noexcept { return _data.end(); }
142 :
143 : const_iterator cbegin() const noexcept { return _data.cbegin(); }
144 : const_iterator cend() const noexcept { return _data.cend(); }
145 :
146 : reverse_iterator rbegin() noexcept { return _data.rbegin(); }
147 : reverse_iterator rend() noexcept { return _data.rend(); }
148 :
149 : const_reverse_iterator rbegin() const noexcept { return _data.rbegin(); }
150 : const_reverse_iterator rend() const noexcept { return _data.rend(); }
151 :
152 : const_reverse_iterator crbegin() const noexcept { return _data.crbegin(); }
153 : const_reverse_iterator crend() const noexcept { return _data.crend(); }
154 :
155 : template <class P>
156 : Pair<iterator,bool> insert( P&& value ) {
157 : return do_insert(std::forward<P>(value));
158 : }
159 :
160 : template <class P>
161 : iterator insert( const_iterator hint, P&& value ) {
162 : return do_insert(hint, std::forward<P>(value));
163 : }
164 :
165 : template< class InputIt >
166 : void insert( InputIt first, InputIt last ) {
167 : for (auto it = first; it != last; it ++) {
168 : do_insert(*it);
169 : }
170 : }
171 :
172 : void insert( InitializerList<value_type> ilist ) {
173 : for (auto &it : ilist) {
174 : do_insert(std::move(it));
175 : }
176 : }
177 :
178 :
179 : template <class M>
180 : Pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) {
181 : return do_insert_or_assign(k, obj);
182 : }
183 :
184 : template <class M>
185 : Pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
186 : return do_insert_or_assign(std::move(k), obj);
187 : }
188 :
189 : template <class M>
190 : iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj) {
191 : return do_insert_or_assign(hint, k, obj);
192 : }
193 :
194 : template <class M>
195 : iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj) {
196 : return do_insert_or_assign(hint, std::move(k), obj);
197 : }
198 :
199 :
200 : template< class... Args >
201 10909 : Pair<iterator,bool> emplace( Args&&... args ) {
202 10909 : auto ret = do_try_emplace(std::forward<Args>(args)...);
203 10909 : if (!ret.second) {
204 25 : do_assign(ret.first, std::forward<Args>(args)...);
205 : }
206 10909 : return ret;
207 : }
208 :
209 : template <class... Args>
210 100 : iterator emplace_hint( const_iterator hint, Args&&... args ) {
211 100 : auto ret = do_try_emplace(hint, std::forward<Args>(args)...);
212 100 : if (!ret.second) {
213 0 : do_assign(ret.first, std::forward<Args>(args)...);
214 : }
215 200 : return ret.first;
216 : }
217 :
218 : template <class... Args>
219 : Pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) {
220 : return do_try_emplace(k, std::forward<Args>(args)...);
221 : }
222 :
223 : template <class... Args>
224 : Pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
225 : return do_try_emplace(std::move(k), std::forward<Args>(args)...);
226 : }
227 :
228 : template <class... Args>
229 : iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) {
230 : return do_try_emplace(hint, k, std::forward<Args>(args)...).first;
231 : }
232 :
233 : template <class... Args>
234 : iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args) {
235 : return do_try_emplace(hint, std::move(k), std::forward<Args>(args)...).first;
236 : }
237 :
238 : iterator erase( iterator pos ) { return _data.erase(pos); }
239 : iterator erase( const_iterator pos ) { return _data.erase(pos); }
240 : iterator erase( const_iterator first, const_iterator last ) { return _data.erase(first, last); }
241 :
242 : template< class K > size_type erase( const K& key ) {
243 : return do_erase(key);
244 : }
245 :
246 41869 : template< class K > iterator find( const K& x ) { return do_find(x); }
247 : template< class K > const_iterator find( const K& x ) const { return do_find(x); }
248 :
249 52828 : template< class K > iterator lower_bound(const K& x) {
250 52828 : return std::lower_bound(_data.begin(), _data.end(), x, value_comparator<K>{_comp});
251 : }
252 : template< class K > const_iterator lower_bound(const K& x) const {
253 : return std::lower_bound(_data.begin(), _data.end(), x, value_comparator<K>{_comp});
254 : }
255 :
256 : template< class K > iterator upper_bound( const K& x ) {
257 : return std::upper_bound(_data.begin(), _data.end(), x, value_comparator<K>{_comp});
258 : }
259 : template< class K > const_iterator upper_bound( const K& x ) const {
260 : return std::upper_bound(_data.begin(), _data.end(), x, value_comparator<K>{_comp});
261 : }
262 :
263 : template< class K > Pair<iterator,iterator> equal_range( const K& x ) {
264 : return std::equal_range(_data.begin(), _data.end(), x, value_comparator<K>{_comp});
265 : }
266 : template< class K > Pair<const_iterator,const_iterator> equal_range( const K& x ) const {
267 : return std::equal_range(_data.begin(), _data.end(), x, value_comparator<K>{_comp});
268 : }
269 :
270 : template< class K > size_t count( const K& x ) const { return do_count(x); }
271 :
272 :
273 : protected:
274 : template <typename L, typename R>
275 30406 : bool do_equal_check(const L &l, const R &r) const {
276 30406 : return !_comp(l, r) && !_comp(r, l);
277 : }
278 :
279 : template <typename K, class M>
280 : Pair<iterator, bool> do_insert_or_assign(K&& k, M&& m) {
281 : auto it = lower_bound(k);
282 : if (it != _data.end() && do_equal_check(it->first, k)) {
283 : it->second = std::forward<M>(m);
284 : return pair(it, false);
285 : } else {
286 : return pair(_data.emplace_safe(it, std::forward<K>(k), std::forward<M>(m)), true);
287 : }
288 : }
289 :
290 : template <typename K, class M>
291 : iterator do_insert_or_assign(const_iterator hint, K&& k, M&& m) {
292 : if (hint != _data.begin()) {
293 : if (_comp((hint - 1)->first, k) && (hint == _data.end() || !_comp(hint->first, k))) {
294 : return _data.emplace_safe(hint, std::forward<K>(k), std::forward<M>(m));
295 : }
296 : }
297 : return do_insert_or_assign(std::forward<K>(k), std::forward<M>(m));
298 : }
299 :
300 : template <typename K, typename ... Args>
301 10959 : Pair<iterator,bool> do_try_emplace(K &&k, Args && ... args) {
302 10959 : auto it = lower_bound(k);
303 10959 : if (it == _data.end() || !do_equal_check(it->first, k)) {
304 : return pair(_data.emplace_safe(it, std::piecewise_construct,
305 10934 : std::forward_as_tuple(std::forward<K>(k)), std::forward_as_tuple(std::forward<Args>(args)...)), true);
306 : }
307 50 : return pair(it, false);
308 : }
309 :
310 : template <typename K, typename ... Args>
311 100 : Pair<iterator,bool> do_try_emplace(const_iterator hint, K &&k, Args && ... args) {
312 100 : if (hint != _data.begin()) {
313 100 : if (_comp((hint - 1)->first, k) && (hint == _data.end() || !_comp(hint->first, k))) {
314 : return pair(_data.emplace_safe(hint, std::piecewise_construct,
315 50 : std::forward_as_tuple(std::forward<K>(k)), std::forward_as_tuple(std::forward<Args>(args)...)), true);
316 : }
317 : }
318 50 : return do_try_emplace(std::forward<K>(k), std::forward<Args>(args)...);
319 : }
320 :
321 : template <class A, class B>
322 : Pair<iterator,bool> do_insert( const Pair<A, B> & value ) {
323 : return emplace(value.first, value.second);
324 : }
325 :
326 : template <class A, class B>
327 : Pair<iterator,bool> do_insert( Pair<A, B> && value ) {
328 : return emplace(std::move(value.first), std::move(value.second));
329 : }
330 :
331 : template <class A, class B>
332 : iterator do_insert( const_iterator hint, const Pair<A, B> & value ) {
333 : return emplace_hint(hint, value.first, value.second);
334 : }
335 :
336 : template <class A, class B>
337 : iterator do_insert( const_iterator hint, Pair<A, B> && value ) {
338 : return emplace_hint(hint, std::move(value.first), std::move(value.second));
339 : }
340 :
341 : template <class T, class ... Args>
342 25 : void do_assign( iterator it, T &&, Args && ... args) {
343 25 : it->second = Value(std::forward<Args>(args)...);
344 25 : }
345 :
346 : template< class K > size_type do_erase( const K& key ) {
347 : auto b = equal_range(key);
348 : erase(b.first, b.second);
349 : return std::distance(b.first, b.second);
350 : }
351 :
352 : template< class K >
353 41869 : iterator do_find( const K& k ) {
354 41869 : auto it = lower_bound(k);
355 41869 : if (it != _data.end() && do_equal_check(it->first, k)) {
356 20241 : return it;
357 : }
358 21628 : return _data.end();
359 : }
360 :
361 : template< class K >
362 : const_iterator do_find( const K& k ) const {
363 : auto it = lower_bound(k);
364 : if (it != _data.end() && do_equal_check(it->first, k)) {
365 : return it;
366 : }
367 : return _data.end();
368 : }
369 :
370 : template< class K >
371 : size_t do_count( const K& key ) const {
372 : auto b = equal_range(key);
373 : return std::distance(b.first, b.second);
374 : }
375 :
376 : vector_type _data;
377 : comparator_type _comp;
378 : };
379 :
380 : template<typename Key, typename Value, typename Comp> inline bool
381 75 : operator==(const dict<Key, Value, Comp>& __x, const dict<Key, Value, Comp>& __y) {
382 75 : return (__x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()));
383 : }
384 :
385 : template<typename Key, typename Value, typename Comp> inline bool
386 : operator<(const dict<Key, Value, Comp>& __x, const dict<Key, Value, Comp>& __y) {
387 : return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
388 : }
389 :
390 : /// Based on operator==
391 : template<typename Key, typename Value, typename Comp> inline bool
392 : operator!=(const dict<Key, Value, Comp>& __x, const dict<Key, Value, Comp>& __y) {
393 : return !(__x == __y);
394 : }
395 :
396 : /// Based on operator<
397 : template<typename Key, typename Value, typename Comp> inline bool
398 : operator>(const dict<Key, Value, Comp>& __x, const dict<Key, Value, Comp>& __y) {
399 : return __y < __x;
400 : }
401 :
402 : /// Based on operator<
403 : template<typename Key, typename Value, typename Comp> inline bool
404 : operator<=(const dict<Key, Value, Comp>& __x, const dict<Key, Value, Comp>& __y) {
405 : return !(__y < __x);
406 : }
407 :
408 : /// Based on operator<
409 : template<typename Key, typename Value, typename Comp> inline bool
410 : operator>=(const dict<Key, Value, Comp>& __x, const dict<Key, Value, Comp>& __y) {
411 : return !(__x < __y);
412 : }
413 :
414 : }
415 :
416 : #endif /* STAPPLER_CORE_MEMORY_SPMEMDICT_H_ */
|
