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>
48 using std::cerr;
49 using std::cout;
50 using std::endl;
51 #endif
52 
53 namespace mdds { namespace mtv {
54 
55 using element_t = int;
56 
57 constexpr element_t element_type_empty = -1;
58 
59 constexpr element_t element_type_boolean = 0;
60 constexpr element_t element_type_int8 = 1;
61 constexpr element_t element_type_uint8 = 2;
62 constexpr element_t element_type_int16 = 3;
63 constexpr element_t element_type_uint16 = 4;
64 constexpr element_t element_type_int32 = 5;
65 constexpr element_t element_type_uint32 = 6;
66 constexpr element_t element_type_int64 = 7;
67 constexpr element_t element_type_uint64 = 8;
68 constexpr element_t element_type_float = 9;
69 constexpr element_t element_type_double = 10;
70 constexpr element_t element_type_string = 11;
71 
72 constexpr element_t element_type_user_start = 50;
73 
80 enum 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 
115 enum 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 {
161 public:
162  element_block_error(const std::string& msg) : mdds::general_error(msg)
163  {}
164 };
165 
166 class base_element_block;
167 element_t get_block_type(const base_element_block&);
168 
174 {
175  friend element_t get_block_type(const base_element_block&);
176 
177 protected:
178  element_t type;
179  base_element_block(element_t _t) : type(_t)
180  {}
181 };
182 
183 template<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 
196 protected:
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 
204  element_block() : base_element_block(_TypeId)
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 
215 public:
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 
531 private:
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 
544 template<typename _Self, element_t _TypeId, typename _Data>
545 class copyable_element_block : public element_block<_Self, _TypeId, _Data>
546 {
548 
549 protected:
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 
561 public:
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 
571 template<typename _Self, element_t _TypeId, typename _Data>
572 class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
573 {
575 
576 protected:
578  {}
579  noncopyable_element_block(size_t n) : base_type(n)
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 
588 public:
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 
605 inline element_t get_block_type(const base_element_block& blk)
606 {
607  return blk.type;
608 }
609 
614 template<element_t _TypeId, typename _Data>
615 struct 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 
652 template<element_t _TypeId, typename _Data>
653 struct 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 
713 template<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