mdds
Loading...
Searching...
No Matches
types.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*************************************************************************
3 *
4 * Copyright (c) 2021 Kohei Yoshida
5 *
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
13 * conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 *
27 ************************************************************************/
28
29#pragma once
30
31#include "../global.hpp"
32#include "./types_util.hpp"
33#include "./delayed_delete_vector.hpp"
34
35#include <algorithm>
36#include <cassert>
37#include <memory>
38#include <cstdint>
39#include <vector>
40
41#if defined(MDDS_UNIT_TEST) || defined(MDDS_MULTI_TYPE_VECTOR_DEBUG)
42#include <iostream>
43#include <sstream>
44#endif
45
46namespace mdds { namespace mtv {
47
48using element_t = int;
49
50constexpr element_t element_type_empty = -1;
51
52constexpr element_t element_type_reserved_start = 0;
53constexpr element_t element_type_reserved_end = 49;
54
55constexpr element_t element_type_user_start = 50;
56
63enum class lu_factor_t : int
64{
65 none = 0,
66 lu4 = 4,
67 lu8 = 8,
68 lu16 = 16,
69 lu32 = 32,
70 sse2_x64 = 1 << 8,
71 sse2_x64_lu4 = 1 << 8 | 4,
72 sse2_x64_lu8 = 1 << 8 | 8,
73 sse2_x64_lu16 = 1 << 8 | 16,
74 avx2_x64 = 2 << 8,
75 avx2_x64_lu4 = 2 << 8 | 4,
76 avx2_x64_lu8 = 2 << 8 | 8,
77};
78
98enum class trace_method_t : int
99{
100 unspecified = 0,
101 accessor = 1,
102 accessor_with_pos_hint = 1 << 8 | 1,
103 mutator = 2,
104 mutator_with_pos_hint = 1 << 8 | 2,
105 constructor = 3,
106 destructor = 4
107};
108
113{
114 trace_method_t type = trace_method_t::unspecified;
115
121 const void* instance = nullptr;
122
124 const char* function_name = nullptr;
125
130 std::string function_args;
131
133 const char* filepath = nullptr;
134
136 int line_number = -1;
137};
138
143{
144public:
145 element_block_error(const std::string& msg) : mdds::general_error(msg)
146 {}
147};
148
150element_t get_block_type(const base_element_block&);
151
157{
158 friend element_t get_block_type(const base_element_block&);
159
160protected:
161 element_t type;
162 base_element_block(element_t _t) : type(_t)
163 {}
164};
165
166template<typename Self, element_t TypeId, typename ValueT, template<typename, typename> class StoreT>
168{
169public:
170 using store_type = StoreT<ValueT, std::allocator<ValueT>>;
171 static constexpr element_t block_type = TypeId;
172
173protected:
174 store_type m_array;
175
177 {}
178 element_block(size_t n) : base_element_block(TypeId), m_array(n)
179 {}
180 element_block(size_t n, const ValueT& val) : base_element_block(TypeId), m_array(n, val)
181 {}
182
183 template<typename Iter>
184 element_block(const Iter& it_begin, const Iter& it_end) : base_element_block(TypeId), m_array(it_begin, it_end)
185 {}
186
187public:
188 typedef typename store_type::iterator iterator;
189 typedef typename store_type::reverse_iterator reverse_iterator;
190 typedef typename store_type::const_iterator const_iterator;
191 typedef typename store_type::const_reverse_iterator const_reverse_iterator;
192 typedef ValueT value_type;
193
194private:
195 template<bool Mutable>
196 class base_range_type
197 {
198 using block_type = mdds::detail::mutable_t<base_element_block, Mutable>;
199 block_type& m_blk;
200
201 public:
202 using iter_type = std::conditional_t<Mutable, iterator, const_iterator>;
203
204 base_range_type(block_type& blk) : m_blk(blk)
205 {}
206
207 iter_type begin()
208 {
209 return element_block::begin(m_blk);
210 }
211
212 iter_type end()
213 {
214 return element_block::end(m_blk);
215 }
216 };
217
218public:
219 using range_type = base_range_type<true>;
220 using const_range_type = base_range_type<false>;
221
222 bool operator==(const Self& r) const
223 {
224 return m_array == r.m_array;
225 }
226
227 bool operator!=(const Self& r) const
228 {
229 return !operator==(r);
230 }
231
232 static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
233 {
234 return get(block).m_array.at(pos);
235 }
236
237 static value_type& at(base_element_block& block, typename store_type::size_type pos)
238 {
239 return get(block).m_array.at(pos);
240 }
241
242 static value_type* data(base_element_block& block)
243 {
244 return get(block).m_array.data();
245 }
246
247 static typename store_type::size_type size(const base_element_block& block)
248 {
249 return get(block).m_array.size();
250 }
251
252 static iterator begin(base_element_block& block)
253 {
254 return get(block).m_array.begin();
255 }
256
257 static iterator end(base_element_block& block)
258 {
259 return get(block).m_array.end();
260 }
261
262 static const_iterator begin(const base_element_block& block)
263 {
264 return get(block).m_array.begin();
265 }
266
267 static const_iterator end(const base_element_block& block)
268 {
269 return get(block).m_array.end();
270 }
271
272 static const_iterator cbegin(const base_element_block& block)
273 {
274 return get(block).m_array.begin();
275 }
276
277 static const_iterator cend(const base_element_block& block)
278 {
279 return get(block).m_array.end();
280 }
281
282 static reverse_iterator rbegin(base_element_block& block)
283 {
284 return get(block).m_array.rbegin();
285 }
286
287 static reverse_iterator rend(base_element_block& block)
288 {
289 return get(block).m_array.rend();
290 }
291
292 static const_reverse_iterator rbegin(const base_element_block& block)
293 {
294 return get(block).m_array.rbegin();
295 }
296
297 static const_reverse_iterator rend(const base_element_block& block)
298 {
299 return get(block).m_array.rend();
300 }
301
302 static const_reverse_iterator crbegin(const base_element_block& block)
303 {
304 return get(block).m_array.rbegin();
305 }
306
307 static const_reverse_iterator crend(const base_element_block& block)
308 {
309 return get(block).m_array.rend();
310 }
311
312 static const_range_type range(const base_element_block& block)
313 {
314 return const_range_type(block);
315 }
316
317 static range_type range(base_element_block& block)
318 {
319 return range_type(block);
320 }
321
322 static Self& get(base_element_block& block)
323 {
324#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
325 if (get_block_type(block) != TypeId)
326 {
327 std::ostringstream os;
328 os << "incorrect block type: expected block type=" << TypeId
329 << ", passed block type=" << get_block_type(block);
330 throw general_error(os.str());
331 }
332#endif
333 return static_cast<Self&>(block);
334 }
335
336 static const Self& get(const base_element_block& block)
337 {
338#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
339 if (get_block_type(block) != TypeId)
340 {
341 std::ostringstream os;
342 os << "incorrect block type: expected block type=" << TypeId
343 << ", passed block type=" << get_block_type(block);
344 throw general_error(os.str());
345 }
346#endif
347 return static_cast<const Self&>(block);
348 }
349
350 static void set_value(base_element_block& blk, size_t pos, const ValueT& val)
351 {
352 get(blk).m_array[pos] = val;
353 }
354
355 static void get_value(const base_element_block& blk, size_t pos, ValueT& val)
356 {
357 val = get(blk).m_array[pos];
358 }
359
360 static value_type get_value(const base_element_block& blk, size_t pos)
361 {
362 return get(blk).m_array[pos];
363 }
364
365 template<typename T = ValueT>
366 static void append_value(base_element_block& blk, T&& val)
367 {
368 get(blk).m_array.push_back(std::forward<T>(val));
369 }
370
371 template<typename... Args>
372 static void emplace_back_value(base_element_block& blk, Args&&... args)
373 {
374 get(blk).m_array.emplace_back(std::forward<Args>(args)...);
375 }
376
377 static void prepend_value(base_element_block& blk, const ValueT& val)
378 {
379 store_type& blk2 = get(blk).m_array;
380 blk2.insert(blk2.begin(), val);
381 }
382
383 static Self* create_block(size_t init_size)
384 {
385 return new Self(init_size);
386 }
387
388 static void delete_block(const base_element_block* p)
389 {
390 delete static_cast<const Self*>(p);
391 }
392
393 static void resize_block(base_element_block& blk, size_t new_size)
394 {
395 store_type& st = get(blk).m_array;
396 st.resize(new_size);
397
398 // Test if the vector's capacity is larger than twice its current
399 // size, and if so, shrink its capacity to free up some memory.
400 if (new_size < (detail::get_block_capacity(st) / 2))
401 detail::shrink_to_fit(st);
402 }
403
404#ifdef MDDS_UNIT_TEST
405 static void print_block(const base_element_block& blk)
406 {
407 const store_type& blk2 = get(blk).m_array;
408 for (const auto& val : blk2)
409 std::cout << val << " ";
410
411 std::cout << std::endl;
412 }
413#else
414 static void print_block(const base_element_block&)
415 {}
416#endif
417
418 static void erase_value(base_element_block& blk, size_t pos)
419 {
420 store_type& blk2 = get(blk).m_array;
421 blk2.erase(blk2.begin() + pos);
422 }
423
424 static void erase_values(base_element_block& blk, size_t pos, size_t size)
425 {
426 store_type& blk2 = get(blk).m_array;
427 blk2.erase(blk2.begin() + pos, blk2.begin() + pos + size);
428 }
429
430 static void append_block(base_element_block& dest, const base_element_block& src)
431 {
432 store_type& d = get(dest).m_array;
433 const store_type& s = get(src).m_array;
434 d.insert(d.end(), s.begin(), s.end());
435 }
436
437 static void append_values_from_block(
438 base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
439 {
440 store_type& d = get(dest).m_array;
441 const store_type& s = get(src).m_array;
442 std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
443 detail::reserve(d, d.size() + len);
444 d.insert(d.end(), its.first, its.second);
445 }
446
447 static void assign_values_from_block(
448 base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
449 {
450 store_type& d = get(dest).m_array;
451 const store_type& s = get(src).m_array;
452 std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
453 d.assign(its.first, its.second);
454 }
455
456 static void prepend_values_from_block(
457 base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
458 {
459 store_type& d = get(dest).m_array;
460 const store_type& s = get(src).m_array;
461 std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
462 detail::reserve(d, d.size() + len);
463 d.insert(d.begin(), its.first, its.second);
464 }
465
466 static void swap_values(base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
467 {
468 store_type& st1 = get(blk1).m_array;
469 store_type& st2 = get(blk2).m_array;
470 assert(pos1 + len <= st1.size());
471 assert(pos2 + len <= st2.size());
472
473 typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
474 std::advance(it1, pos1);
475 std::advance(it2, pos2);
476
477 for (size_t i = 0; i < len; ++i, ++it1, ++it2)
478 {
479 value_type v1 = *it1, v2 = *it2;
480 *it1 = v2;
481 *it2 = v1;
482 }
483 }
484
485 static bool equal_block(const base_element_block& left, const base_element_block& right)
486 {
487 return get(left) == get(right);
488 }
489
490 template<typename Iter>
491 static void set_values(base_element_block& block, size_t pos, const Iter& it_begin, const Iter& it_end)
492 {
493 store_type& d = get(block).m_array;
494 typename store_type::iterator it_dest = d.begin();
495 std::advance(it_dest, pos);
496 for (Iter it = it_begin; it != it_end; ++it, ++it_dest)
497 *it_dest = *it;
498 }
499
500 template<typename Iter>
501 static void append_values(base_element_block& block, const Iter& it_begin, const Iter& it_end)
502 {
503 store_type& d = get(block).m_array;
504 typename store_type::iterator it = d.end();
505 d.insert(it, it_begin, it_end);
506 }
507
508 template<typename Iter>
509 static void prepend_values(base_element_block& block, const Iter& it_begin, const Iter& it_end)
510 {
511 store_type& d = get(block).m_array;
512 d.insert(d.begin(), it_begin, it_end);
513 }
514
515 template<typename Iter>
516 static void assign_values(base_element_block& dest, const Iter& it_begin, const Iter& it_end)
517 {
518 store_type& d = get(dest).m_array;
519 d.assign(it_begin, it_end);
520 }
521
522 template<typename Iter>
523 static void insert_values(base_element_block& block, size_t pos, const Iter& it_begin, const Iter& it_end)
524 {
525 store_type& blk = get(block).m_array;
526 blk.insert(blk.begin() + pos, it_begin, it_end);
527 }
528
529 static size_t capacity(const base_element_block& block)
530 {
531 const store_type& blk = get(block).m_array;
532 return detail::get_block_capacity(blk);
533 }
534
535 static void reserve(base_element_block& block, std::size_t size)
536 {
537 store_type& blk = get(block).m_array;
538 detail::reserve(blk, size);
539 }
540
541 static void shrink_to_fit(base_element_block& block)
542 {
543 store_type& blk = get(block).m_array;
544 detail::shrink_to_fit(blk);
545 }
546
547private:
548 static std::pair<const_iterator, const_iterator> get_iterator_pair(
549 const store_type& array, size_t begin_pos, size_t len)
550 {
551 assert(begin_pos + len <= array.size());
552 const_iterator it = array.begin();
553 std::advance(it, begin_pos);
554 const_iterator it_end = it;
555 std::advance(it_end, len);
556 return std::pair<const_iterator, const_iterator>(it, it_end);
557 }
558};
559
560template<typename Self, element_t TypeId, typename ValueT, template<typename, typename> class StoreT>
561class copyable_element_block : public element_block<Self, TypeId, ValueT, StoreT>
562{
564
565protected:
567 {}
568 copyable_element_block(size_t n) : base_type(n)
569 {}
570 copyable_element_block(size_t n, const ValueT& val) : base_type(n, val)
571 {}
572
573 template<typename Iter>
574 copyable_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
575 {}
576
577public:
578 using base_type::get;
579
580 static Self* clone_block(const base_element_block& blk)
581 {
582 // Use copy constructor to copy the data.
583 return new Self(get(blk));
584 }
585};
586
587template<typename Self, element_t TypeId, typename ValueT, template<typename, typename> class StoreT>
588class noncopyable_element_block : public element_block<Self, TypeId, ValueT, StoreT>
589{
591
592protected:
594 {}
596 {}
597 noncopyable_element_block(size_t n, const ValueT& val) : base_type(n, val)
598 {}
599
600 template<typename Iter>
601 noncopyable_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
602 {}
603
604public:
606 noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
607
608 static Self* clone_block(const base_element_block&)
609 {
610 throw element_block_error("attempted to clone a noncopyable element block.");
611 }
612};
613
621inline element_t get_block_type(const base_element_block& blk)
622{
623 return blk.type;
624}
625
630template<element_t TypeId, typename ValueT, template<typename, typename> class StoreT = delayed_delete_vector>
632 : public copyable_element_block<default_element_block<TypeId, ValueT, StoreT>, TypeId, ValueT, StoreT>
633{
636
638 {}
639 default_element_block(size_t n) : base_type(n)
640 {}
641 default_element_block(size_t n, const ValueT& val) : base_type(n, val)
642 {}
643
644 template<typename Iter>
645 default_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
646 {}
647
648 static self_type* create_block_with_value(size_t init_size, const ValueT& val)
649 {
650 return new self_type(init_size, val);
651 }
652
653 template<typename Iter>
654 static self_type* create_block_with_values(const Iter& it_begin, const Iter& it_end)
655 {
656 return new self_type(it_begin, it_end);
657 }
658
659 static void overwrite_values(base_element_block&, size_t, size_t)
660 {
661 // Do nothing.
662 }
663};
664
669template<element_t TypeId, typename ValueT, template<typename, typename> class StoreT = delayed_delete_vector>
671 : public copyable_element_block<managed_element_block<TypeId, ValueT, StoreT>, TypeId, ValueT*, StoreT>
672{
675
676 using base_type::get;
677 using base_type::m_array;
678 using base_type::reserve;
679 using base_type::set_value;
680
682 {}
683 managed_element_block(size_t n) : base_type(n)
684 {}
686 {
687 detail::reserve(m_array, r.m_array.size());
688 for (const auto& v : r.m_array)
689 m_array.push_back(new ValueT(*v));
690 }
691
692 template<typename Iter>
693 managed_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
694 {}
695
697 {
698 std::for_each(m_array.begin(), m_array.end(), std::default_delete<ValueT>());
699 }
700
701 static self_type* create_block_with_value(size_t init_size, ValueT* val)
702 {
703 // Managed blocks don't support initialization with value.
704 if (init_size > 1)
705 throw general_error("You can't create a managed block with initial value.");
706
707 std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
708 if (init_size == 1)
709 set_value(*blk, 0, val);
710
711 return blk.release();
712 }
713
714 template<typename Iter>
715 static self_type* create_block_with_values(const Iter& it_begin, const Iter& it_end)
716 {
717 return new self_type(it_begin, it_end);
718 }
719
720 static void overwrite_values(base_element_block& block, size_t pos, size_t len)
721 {
722 managed_element_block& blk = get(block);
723 typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
724 typename managed_element_block::store_type::iterator it_end = it + len;
725 std::for_each(it, it_end, std::default_delete<ValueT>());
726 }
727};
728
729template<element_t TypeId, typename ValueT, template<typename, typename> class StoreT = delayed_delete_vector>
732 noncopyable_managed_element_block<TypeId, ValueT, StoreT>, TypeId, ValueT*, StoreT>
733{
736
737 using base_type::get;
738 using base_type::m_array;
739 using base_type::set_value;
740
742 {}
744 {}
745
746 template<typename Iter>
747 noncopyable_managed_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
748 {}
749
751 {
752 std::for_each(m_array.begin(), m_array.end(), std::default_delete<ValueT>());
753 }
754
755 static self_type* create_block_with_value(size_t init_size, ValueT* val)
756 {
757 // Managed blocks don't support initialization with value.
758 if (init_size > 1)
759 throw general_error("You can't create a managed block with initial value.");
760
761 std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
762 if (init_size == 1)
763 set_value(*blk, 0, val);
764
765 return blk.release();
766 }
767
768 template<typename Iter>
769 static self_type* create_block_with_values(const Iter& it_begin, const Iter& it_end)
770 {
771 return new self_type(it_begin, it_end);
772 }
773
774 static void overwrite_values(base_element_block& block, size_t pos, size_t len)
775 {
776 noncopyable_managed_element_block& blk = get(block);
777 typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
778 typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
779 std::for_each(it, it_end, std::default_delete<ValueT>());
780 }
781};
782
783namespace detail {
784
785template<typename Blk>
786bool get_block_element_at(const mdds::mtv::base_element_block& data, size_t offset, std::true_type)
787{
788 auto it = Blk::cbegin(data);
789 std::advance(it, offset);
790 return *it;
791}
792
793template<typename Blk>
794typename Blk::value_type get_block_element_at(const mdds::mtv::base_element_block& data, size_t offset, std::false_type)
795{
796 return Blk::at(data, offset);
797}
798
799template<typename Blk>
800typename Blk::value_type get_block_element_at(const mdds::mtv::base_element_block& data, size_t offset)
801{
802 typename mdds::mtv::detail::has_std_vector_bool_store<Blk>::type v;
803 return get_block_element_at<Blk>(data, offset, v);
804}
805
806} // namespace detail
807
808}} // namespace mdds::mtv
809
810/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition global.hpp:84
Definition types.hpp:157
friend element_t get_block_type(const base_element_block &)
Definition types.hpp:621
Definition types.hpp:562
Definition delayed_delete_vector.hpp:44
Definition types.hpp:143
Definition types.hpp:168
Definition types.hpp:589
Definition types.hpp:633
Definition types.hpp:672
Definition types.hpp:113
std::string function_args
Definition types.hpp:130
const char * function_name
Definition types.hpp:124
int line_number
Definition types.hpp:136
const void * instance
Definition types.hpp:121
const char * filepath
Definition types.hpp:133