mdds
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#ifndef INCLUDED_MDDS_MULTI_TYPE_VECTOR_TYPES_2_HPP
30#define INCLUDED_MDDS_MULTI_TYPE_VECTOR_TYPES_2_HPP
31
32#include "../global.hpp"
33
34#include <algorithm>
35#include <cassert>
36#include <memory>
37#include <cstdint>
38
39#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
40#include <deque>
41#else
42#include <vector>
43#endif
44
45#if defined(MDDS_UNIT_TEST) || defined(MDDS_MULTI_TYPE_VECTOR_DEBUG)
46#include <iostream>
47#include <sstream>
48using std::cerr;
49using std::cout;
50using std::endl;
51#endif
52
53namespace mdds { namespace mtv {
54
55using element_t = int;
56
57constexpr element_t element_type_empty = -1;
58
59constexpr element_t element_type_boolean = 0;
60constexpr element_t element_type_int8 = 1;
61constexpr element_t element_type_uint8 = 2;
62constexpr element_t element_type_int16 = 3;
63constexpr element_t element_type_uint16 = 4;
64constexpr element_t element_type_int32 = 5;
65constexpr element_t element_type_uint32 = 6;
66constexpr element_t element_type_int64 = 7;
67constexpr element_t element_type_uint64 = 8;
68constexpr element_t element_type_float = 9;
69constexpr element_t element_type_double = 10;
70constexpr element_t element_type_string = 11;
71
72constexpr element_t element_type_user_start = 50;
73
80enum class lu_factor_t : int
81{
82 none = 0,
83 lu4 = 4,
84 lu8 = 8,
85 lu16 = 16,
86 lu32 = 32,
87 sse2_x64 = 1 << 8,
88 sse2_x64_lu4 = 1 << 8 | 4,
89 sse2_x64_lu8 = 1 << 8 | 8,
90 sse2_x64_lu16 = 1 << 8 | 16,
91 avx2_x64 = 2 << 8,
92 avx2_x64_lu4 = 2 << 8 | 4,
93 avx2_x64_lu8 = 2 << 8 | 8,
94};
95
115enum class trace_method_t : int
116{
117 unspecified = 0,
118 accessor = 1,
119 accessor_with_pos_hint = 1 << 8 | 1,
120 mutator = 2,
121 mutator_with_pos_hint = 1 << 8 | 2,
122 constructor = 3,
123 destructor = 4
124};
125
130{
131 trace_method_t type = trace_method_t::unspecified;
132
138 const void* instance = nullptr;
139
141 const char* function_name = nullptr;
142
147 std::string function_args;
148
150 const char* filepath = nullptr;
151
153 int line_number = -1;
154};
155
160{
161public:
162 element_block_error(const std::string& msg) : mdds::general_error(msg)
163 {}
164};
165
167element_t get_block_type(const base_element_block&);
168
174{
175 friend element_t get_block_type(const base_element_block&);
176
177protected:
178 element_t type;
179 base_element_block(element_t _t) : type(_t)
180 {}
181};
182
183template<typename _Self, element_t _TypeId, typename _Data>
185{
186#ifdef MDDS_UNIT_TEST
187 struct print_block_array
188 {
189 void operator()(const _Data& val) const
190 {
191 std::cout << val << " ";
192 }
193 };
194#endif
195
196protected:
197#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
198 typedef std::deque<_Data> store_type;
199#else
200 typedef std::vector<_Data> store_type;
201#endif
202 store_type m_array;
203
205 {}
206 element_block(size_t n) : base_element_block(_TypeId), m_array(n)
207 {}
208 element_block(size_t n, const _Data& val) : base_element_block(_TypeId), m_array(n, val)
209 {}
210
211 template<typename _Iter>
212 element_block(const _Iter& it_begin, const _Iter& it_end) : base_element_block(_TypeId), m_array(it_begin, it_end)
213 {}
214
215public:
216 static const element_t block_type = _TypeId;
217
218 typedef typename store_type::iterator iterator;
219 typedef typename store_type::reverse_iterator reverse_iterator;
220 typedef typename store_type::const_iterator const_iterator;
221 typedef typename store_type::const_reverse_iterator const_reverse_iterator;
222 typedef _Data value_type;
223
224 bool operator==(const _Self& r) const
225 {
226 return m_array == r.m_array;
227 }
228
229 bool operator!=(const _Self& r) const
230 {
231 return !operator==(r);
232 }
233
234 static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
235 {
236 return get(block).m_array.at(pos);
237 }
238
239 static value_type& at(base_element_block& block, typename store_type::size_type pos)
240 {
241 return get(block).m_array.at(pos);
242 }
243
244 static value_type* data(base_element_block& block)
245 {
246 return get(block).m_array.data();
247 }
248
249 static typename store_type::size_type size(const base_element_block& block)
250 {
251 return get(block).m_array.size();
252 }
253
254 static iterator begin(base_element_block& block)
255 {
256 return get(block).m_array.begin();
257 }
258
259 static iterator end(base_element_block& block)
260 {
261 return get(block).m_array.end();
262 }
263
264 static const_iterator begin(const base_element_block& block)
265 {
266 return get(block).m_array.begin();
267 }
268
269 static const_iterator end(const base_element_block& block)
270 {
271 return get(block).m_array.end();
272 }
273
274 static const_iterator cbegin(const base_element_block& block)
275 {
276 return get(block).m_array.begin();
277 }
278
279 static const_iterator cend(const base_element_block& block)
280 {
281 return get(block).m_array.end();
282 }
283
284 static reverse_iterator rbegin(base_element_block& block)
285 {
286 return get(block).m_array.rbegin();
287 }
288
289 static reverse_iterator rend(base_element_block& block)
290 {
291 return get(block).m_array.rend();
292 }
293
294 static const_reverse_iterator rbegin(const base_element_block& block)
295 {
296 return get(block).m_array.rbegin();
297 }
298
299 static const_reverse_iterator rend(const base_element_block& block)
300 {
301 return get(block).m_array.rend();
302 }
303
304 static const_reverse_iterator crbegin(const base_element_block& block)
305 {
306 return get(block).m_array.rbegin();
307 }
308
309 static const_reverse_iterator crend(const base_element_block& block)
310 {
311 return get(block).m_array.rend();
312 }
313
314 static _Self& get(base_element_block& block)
315 {
316#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
317 if (get_block_type(block) != _TypeId)
318 {
319 std::ostringstream os;
320 os << "incorrect block type: expected block type=" << _TypeId
321 << ", passed block type=" << get_block_type(block);
322 throw general_error(os.str());
323 }
324#endif
325 return static_cast<_Self&>(block);
326 }
327
328 static const _Self& get(const base_element_block& block)
329 {
330#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
331 if (get_block_type(block) != _TypeId)
332 {
333 std::ostringstream os;
334 os << "incorrect block type: expected block type=" << _TypeId
335 << ", passed block type=" << get_block_type(block);
336 throw general_error(os.str());
337 }
338#endif
339 return static_cast<const _Self&>(block);
340 }
341
342 static void set_value(base_element_block& blk, size_t pos, const _Data& val)
343 {
344 get(blk).m_array[pos] = val;
345 }
346
347 static void get_value(const base_element_block& blk, size_t pos, _Data& val)
348 {
349 val = get(blk).m_array[pos];
350 }
351
352 static value_type get_value(const base_element_block& blk, size_t pos)
353 {
354 return get(blk).m_array[pos];
355 }
356
357 static void append_value(base_element_block& blk, const _Data& val)
358 {
359 get(blk).m_array.push_back(val);
360 }
361
362 static void prepend_value(base_element_block& blk, const _Data& val)
363 {
364 store_type& blk2 = get(blk).m_array;
365 blk2.insert(blk2.begin(), val);
366 }
367
368 static _Self* create_block(size_t init_size)
369 {
370 return new _Self(init_size);
371 }
372
373 static void delete_block(const base_element_block* p)
374 {
375 delete static_cast<const _Self*>(p);
376 }
377
378 static void resize_block(base_element_block& blk, size_t new_size)
379 {
380 store_type& st = get(blk).m_array;
381 st.resize(new_size);
382
383 // Test if the vector's capacity is larger than twice its current
384 // size, and if so, shrink its capacity to free up some memory.
385 if (new_size < (st.capacity() / 2))
386 st.shrink_to_fit();
387 }
388
389#ifdef MDDS_UNIT_TEST
390 static void print_block(const base_element_block& blk)
391 {
392 const store_type& blk2 = get(blk).m_array;
393 std::for_each(blk2.begin(), blk2.end(), print_block_array());
394 std::cout << std::endl;
395 }
396#else
397 static void print_block(const base_element_block&)
398 {}
399#endif
400
401 static void erase_block(base_element_block& blk, size_t pos)
402 {
403 store_type& blk2 = get(blk).m_array;
404 blk2.erase(blk2.begin() + pos);
405 }
406
407 static void erase_block(base_element_block& blk, size_t pos, size_t size)
408 {
409 store_type& blk2 = get(blk).m_array;
410 blk2.erase(blk2.begin() + pos, blk2.begin() + pos + size);
411 }
412
413 static void append_values_from_block(base_element_block& dest, const base_element_block& src)
414 {
415 store_type& d = get(dest).m_array;
416 const store_type& s = get(src).m_array;
417 d.insert(d.end(), s.begin(), s.end());
418 }
419
420 static void append_values_from_block(
421 base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
422 {
423 store_type& d = get(dest).m_array;
424 const store_type& s = get(src).m_array;
425 std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
426#ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
427 d.reserve(d.size() + len);
428#endif
429 d.insert(d.end(), its.first, its.second);
430 }
431
432 static void assign_values_from_block(
433 base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
434 {
435 store_type& d = get(dest).m_array;
436 const store_type& s = get(src).m_array;
437 std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
438 d.assign(its.first, its.second);
439 }
440
441 static void prepend_values_from_block(
442 base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
443 {
444 store_type& d = get(dest).m_array;
445 const store_type& s = get(src).m_array;
446 std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
447#ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
448 d.reserve(d.size() + len);
449#endif
450 d.insert(d.begin(), its.first, its.second);
451 }
452
453 static void swap_values(base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
454 {
455 store_type& st1 = get(blk1).m_array;
456 store_type& st2 = get(blk2).m_array;
457 assert(pos1 + len <= st1.size());
458 assert(pos2 + len <= st2.size());
459
460 typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
461 std::advance(it1, pos1);
462 std::advance(it2, pos2);
463 for (size_t i = 0; i < len; ++i, ++it1, ++it2)
464 {
465#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
466 std::swap(*it1, *it2);
467#else
468 value_type v1 = *it1, v2 = *it2;
469 *it1 = v2;
470 *it2 = v1;
471#endif
472 }
473 }
474
475 template<typename _Iter>
476 static void set_values(base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
477 {
478 store_type& d = get(block).m_array;
479 typename store_type::iterator it_dest = d.begin();
480 std::advance(it_dest, pos);
481 for (_Iter it = it_begin; it != it_end; ++it, ++it_dest)
482 *it_dest = *it;
483 }
484
485 template<typename _Iter>
486 static void append_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
487 {
488 store_type& d = get(block).m_array;
489 typename store_type::iterator it = d.end();
490 d.insert(it, it_begin, it_end);
491 }
492
493 template<typename _Iter>
494 static void prepend_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
495 {
496 store_type& d = get(block).m_array;
497 d.insert(d.begin(), it_begin, it_end);
498 }
499
500 template<typename _Iter>
501 static void assign_values(base_element_block& dest, const _Iter& it_begin, const _Iter& it_end)
502 {
503 store_type& d = get(dest).m_array;
504 d.assign(it_begin, it_end);
505 }
506
507 template<typename _Iter>
508 static void insert_values(base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
509 {
510 store_type& blk = get(block).m_array;
511 blk.insert(blk.begin() + pos, it_begin, it_end);
512 }
513
514 static size_t capacity(const base_element_block& block)
515 {
516#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
517 return 0;
518#else
519 const store_type& blk = get(block).m_array;
520 return blk.capacity();
521#endif
522 }
523
524 static void shrink_to_fit(base_element_block& block)
525 {
526#ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
527 get(block).m_array.shrink_to_fit();
528#endif
529 }
530
531private:
532 static std::pair<const_iterator, const_iterator> get_iterator_pair(
533 const store_type& array, size_t begin_pos, size_t len)
534 {
535 assert(begin_pos + len <= array.size());
536 const_iterator it = array.begin();
537 std::advance(it, begin_pos);
538 const_iterator it_end = it;
539 std::advance(it_end, len);
540 return std::pair<const_iterator, const_iterator>(it, it_end);
541 }
542};
543
544template<typename _Self, element_t _TypeId, typename _Data>
545class copyable_element_block : public element_block<_Self, _TypeId, _Data>
546{
548
549protected:
551 {}
552 copyable_element_block(size_t n) : base_type(n)
553 {}
554 copyable_element_block(size_t n, const _Data& val) : base_type(n, val)
555 {}
556
557 template<typename _Iter>
558 copyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end)
559 {}
560
561public:
562 using base_type::get;
563
564 static _Self* clone_block(const base_element_block& blk)
565 {
566 // Use copy constructor to copy the data.
567 return new _Self(get(blk));
568 }
569};
570
571template<typename _Self, element_t _TypeId, typename _Data>
572class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
573{
575
576protected:
578 {}
580 {}
581 noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val)
582 {}
583
584 template<typename _Iter>
585 noncopyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end)
586 {}
587
588public:
590 noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
591
592 static _Self* clone_block(const base_element_block&)
593 {
594 throw element_block_error("attempted to clone a noncopyable element block.");
595 }
596};
597
605inline element_t get_block_type(const base_element_block& blk)
606{
607 return blk.type;
608}
609
614template<element_t _TypeId, typename _Data>
615struct default_element_block : public copyable_element_block<default_element_block<_TypeId, _Data>, _TypeId, _Data>
616{
619
621 {}
622 default_element_block(size_t n) : base_type(n)
623 {}
624 default_element_block(size_t n, const _Data& val) : base_type(n, val)
625 {}
626
627 template<typename _Iter>
628 default_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end)
629 {}
630
631 static self_type* create_block_with_value(size_t init_size, const _Data& val)
632 {
633 return new self_type(init_size, val);
634 }
635
636 template<typename _Iter>
637 static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
638 {
639 return new self_type(it_begin, it_end);
640 }
641
642 static void overwrite_values(base_element_block&, size_t, size_t)
643 {
644 // Do nothing.
645 }
646};
647
652template<element_t _TypeId, typename _Data>
653struct managed_element_block : public copyable_element_block<managed_element_block<_TypeId, _Data>, _TypeId, _Data*>
654{
657
658 using base_type::get;
659 using base_type::m_array;
660 using base_type::set_value;
661
663 {}
664 managed_element_block(size_t n) : base_type(n)
665 {}
667 {
668#ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
669 m_array.reserve(r.m_array.size());
670#endif
671 typename managed_element_block::store_type::const_iterator it = r.m_array.begin(), it_end = r.m_array.end();
672 for (; it != it_end; ++it)
673 m_array.push_back(new _Data(**it));
674 }
675
676 template<typename _Iter>
677 managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end)
678 {}
679
681 {
682 std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
683 }
684
685 static self_type* create_block_with_value(size_t init_size, _Data* val)
686 {
687 // Managed blocks don't support initialization with value.
688 if (init_size > 1)
689 throw general_error("You can't create a managed block with initial value.");
690
691 std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
692 if (init_size == 1)
693 set_value(*blk, 0, val);
694
695 return blk.release();
696 }
697
698 template<typename _Iter>
699 static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
700 {
701 return new self_type(it_begin, it_end);
702 }
703
704 static void overwrite_values(base_element_block& block, size_t pos, size_t len)
705 {
706 managed_element_block& blk = get(block);
707 typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
708 typename managed_element_block::store_type::iterator it_end = it + len;
709 std::for_each(it, it_end, std::default_delete<_Data>());
710 }
711};
712
713template<element_t _TypeId, typename _Data>
715 : public noncopyable_element_block<noncopyable_managed_element_block<_TypeId, _Data>, _TypeId, _Data*>
716{
719
720 using base_type::get;
721 using base_type::m_array;
722 using base_type::set_value;
723
725 {}
727 {}
728
729 template<typename _Iter>
730 noncopyable_managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end)
731 {}
732
734 {
735 std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
736 }
737
738 static self_type* create_block_with_value(size_t init_size, _Data* val)
739 {
740 // Managed blocks don't support initialization with value.
741 if (init_size > 1)
742 throw general_error("You can't create a managed block with initial value.");
743
744 std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
745 if (init_size == 1)
746 set_value(*blk, 0, val);
747
748 return blk.release();
749 }
750
751 template<typename _Iter>
752 static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
753 {
754 return new self_type(it_begin, it_end);
755 }
756
757 static void overwrite_values(base_element_block& block, size_t pos, size_t len)
758 {
759 noncopyable_managed_element_block& blk = get(block);
760 typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
761 typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
762 std::for_each(it, it_end, std::default_delete<_Data>());
763 }
764};
765
778
779}} // namespace mdds::mtv
780
781#endif
782
783/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: global.hpp:84
Definition: types.hpp:174
friend element_t get_block_type(const base_element_block &)
Definition: types.hpp:605
Definition: types.hpp:546
Definition: types.hpp:160
Definition: types.hpp:185
Definition: types.hpp:573
Definition: types.hpp:616
Definition: types.hpp:654
Definition: types.hpp:130
std::string function_args
Definition: types.hpp:147
const char * function_name
Definition: types.hpp:141
int line_number
Definition: types.hpp:153
const void * instance
Definition: types.hpp:138
const char * filepath
Definition: types.hpp:150