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::cout;
49 using std::cerr;
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 class base_element_block;
166 element_t get_block_type(const base_element_block&);
167 
173 {
174  friend element_t get_block_type(const base_element_block&);
175 protected:
176  element_t type;
177  base_element_block(element_t _t) : type(_t) {}
178 };
179 
180 template<typename _Self, element_t _TypeId, typename _Data>
182 {
183 #ifdef MDDS_UNIT_TEST
184  struct print_block_array
185  {
186  void operator() (const _Data& val) const
187  {
188  std::cout << val << " ";
189  }
190  };
191 #endif
192 
193 protected:
194 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
195  typedef std::deque<_Data> store_type;
196 #else
197  typedef std::vector<_Data> store_type;
198 #endif
199  store_type m_array;
200 
201  element_block() : base_element_block(_TypeId) {}
202  element_block(size_t n) : base_element_block(_TypeId), m_array(n) {}
203  element_block(size_t n, const _Data& val) : base_element_block(_TypeId), m_array(n, val) {}
204 
205  template<typename _Iter>
206  element_block(const _Iter& it_begin, const _Iter& it_end) : base_element_block(_TypeId), m_array(it_begin, it_end) {}
207 
208 public:
209  static const element_t block_type = _TypeId;
210 
211  typedef typename store_type::iterator iterator;
212  typedef typename store_type::reverse_iterator reverse_iterator;
213  typedef typename store_type::const_iterator const_iterator;
214  typedef typename store_type::const_reverse_iterator const_reverse_iterator;
215  typedef _Data value_type;
216 
217  bool operator== (const _Self& r) const
218  {
219  return m_array == r.m_array;
220  }
221 
222  bool operator!= (const _Self& r) const
223  {
224  return !operator==(r);
225  }
226 
227  static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
228  {
229  return get(block).m_array.at(pos);
230  }
231 
232  static value_type& at(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* data(base_element_block& block)
238  {
239  return get(block).m_array.data();
240  }
241 
242  static typename store_type::size_type size(const base_element_block& block)
243  {
244  return get(block).m_array.size();
245  }
246 
247  static iterator begin(base_element_block& block)
248  {
249  return get(block).m_array.begin();
250  }
251 
252  static iterator end(base_element_block& block)
253  {
254  return get(block).m_array.end();
255  }
256 
257  static const_iterator begin(const base_element_block& block)
258  {
259  return get(block).m_array.begin();
260  }
261 
262  static const_iterator end(const base_element_block& block)
263  {
264  return get(block).m_array.end();
265  }
266 
267  static const_iterator cbegin(const base_element_block& block)
268  {
269  return get(block).m_array.begin();
270  }
271 
272  static const_iterator cend(const base_element_block& block)
273  {
274  return get(block).m_array.end();
275  }
276 
277  static reverse_iterator rbegin(base_element_block& block)
278  {
279  return get(block).m_array.rbegin();
280  }
281 
282  static reverse_iterator rend(base_element_block& block)
283  {
284  return get(block).m_array.rend();
285  }
286 
287  static const_reverse_iterator rbegin(const base_element_block& block)
288  {
289  return get(block).m_array.rbegin();
290  }
291 
292  static const_reverse_iterator rend(const base_element_block& block)
293  {
294  return get(block).m_array.rend();
295  }
296 
297  static const_reverse_iterator crbegin(const base_element_block& block)
298  {
299  return get(block).m_array.rbegin();
300  }
301 
302  static const_reverse_iterator crend(const base_element_block& block)
303  {
304  return get(block).m_array.rend();
305  }
306 
307  static _Self& get(base_element_block& block)
308  {
309 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
310  if (get_block_type(block) != _TypeId)
311  {
312  std::ostringstream os;
313  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
314  throw general_error(os.str());
315  }
316 #endif
317  return static_cast<_Self&>(block);
318  }
319 
320  static const _Self& get(const base_element_block& block)
321  {
322 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
323  if (get_block_type(block) != _TypeId)
324  {
325  std::ostringstream os;
326  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
327  throw general_error(os.str());
328  }
329 #endif
330  return static_cast<const _Self&>(block);
331  }
332 
333  static void set_value(base_element_block& blk, size_t pos, const _Data& val)
334  {
335  get(blk).m_array[pos] = val;
336  }
337 
338  static void get_value(const base_element_block& blk, size_t pos, _Data& val)
339  {
340  val = get(blk).m_array[pos];
341  }
342 
343  static value_type get_value(const base_element_block& blk, size_t pos)
344  {
345  return get(blk).m_array[pos];
346  }
347 
348  static void append_value(base_element_block& blk, const _Data& val)
349  {
350  get(blk).m_array.push_back(val);
351  }
352 
353  static void prepend_value(base_element_block& blk, const _Data& val)
354  {
355  store_type& blk2 = get(blk).m_array;
356  blk2.insert(blk2.begin(), val);
357  }
358 
359  static _Self* create_block(size_t init_size)
360  {
361  return new _Self(init_size);
362  }
363 
364  static void delete_block(const base_element_block* p)
365  {
366  delete static_cast<const _Self*>(p);
367  }
368 
369  static void resize_block(base_element_block& blk, size_t new_size)
370  {
371  store_type& st = get(blk).m_array;
372  st.resize(new_size);
373 
374  // Test if the vector's capacity is larger than twice its current
375  // size, and if so, shrink its capacity to free up some memory.
376  if (new_size < (st.capacity() / 2))
377  st.shrink_to_fit();
378  }
379 
380 #ifdef MDDS_UNIT_TEST
381  static void print_block(const base_element_block& blk)
382  {
383  const store_type& blk2 = get(blk).m_array;
384  std::for_each(blk2.begin(), blk2.end(), print_block_array());
385  std::cout << std::endl;
386  }
387 #else
388  static void print_block(const base_element_block&) {}
389 #endif
390 
391  static void erase_block(base_element_block& blk, size_t pos)
392  {
393  store_type& blk2 = get(blk).m_array;
394  blk2.erase(blk2.begin()+pos);
395  }
396 
397  static void erase_block(base_element_block& blk, size_t pos, size_t size)
398  {
399  store_type& blk2 = get(blk).m_array;
400  blk2.erase(blk2.begin()+pos, blk2.begin()+pos+size);
401  }
402 
403  static void append_values_from_block(base_element_block& dest, const base_element_block& src)
404  {
405  store_type& d = get(dest).m_array;
406  const store_type& s = get(src).m_array;
407  d.insert(d.end(), s.begin(), s.end());
408  }
409 
410  static void append_values_from_block(
411  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
412  {
413  store_type& d = get(dest).m_array;
414  const store_type& s = get(src).m_array;
415  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
416 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
417  d.reserve(d.size() + len);
418 #endif
419  d.insert(d.end(), its.first, its.second);
420  }
421 
422  static void assign_values_from_block(
423  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
424  {
425  store_type& d = get(dest).m_array;
426  const store_type& s = get(src).m_array;
427  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
428  d.assign(its.first, its.second);
429  }
430 
431  static void prepend_values_from_block(
432  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
433  {
434  store_type& d = get(dest).m_array;
435  const store_type& s = get(src).m_array;
436  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
437 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
438  d.reserve(d.size() + len);
439 #endif
440  d.insert(d.begin(), its.first, its.second);
441  }
442 
443  static void swap_values(
444  base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
445  {
446  store_type& st1 = get(blk1).m_array;
447  store_type& st2 = get(blk2).m_array;
448  assert(pos1 + len <= st1.size());
449  assert(pos2 + len <= st2.size());
450 
451  typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
452  std::advance(it1, pos1);
453  std::advance(it2, pos2);
454  for (size_t i = 0; i < len; ++i, ++it1, ++it2)
455  {
456 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
457  std::swap(*it1, *it2);
458 #else
459  value_type v1 = *it1, v2 = *it2;
460  *it1 = v2;
461  *it2 = v1;
462 #endif
463  }
464  }
465 
466  template<typename _Iter>
467  static void set_values(
468  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
469  {
470  store_type& d = get(block).m_array;
471  typename store_type::iterator it_dest = d.begin();
472  std::advance(it_dest, pos);
473  for (_Iter it = it_begin; it != it_end; ++it, ++it_dest)
474  *it_dest = *it;
475  }
476 
477  template<typename _Iter>
478  static void append_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
479  {
480  store_type& d = get(block).m_array;
481  typename store_type::iterator it = d.end();
482  d.insert(it, it_begin, it_end);
483  }
484 
485  template<typename _Iter>
486  static void prepend_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
487  {
488  store_type& d = get(block).m_array;
489  d.insert(d.begin(), it_begin, it_end);
490  }
491 
492  template<typename _Iter>
493  static void assign_values(base_element_block& dest, const _Iter& it_begin, const _Iter& it_end)
494  {
495  store_type& d = get(dest).m_array;
496  d.assign(it_begin, it_end);
497  }
498 
499  template<typename _Iter>
500  static void insert_values(
501  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
502  {
503  store_type& blk = get(block).m_array;
504  blk.insert(blk.begin()+pos, it_begin, it_end);
505  }
506 
507  static size_t capacity(const base_element_block& block)
508  {
509 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
510  return 0;
511 #else
512  const store_type& blk = get(block).m_array;
513  return blk.capacity();
514 #endif
515  }
516 
517  static void shrink_to_fit(base_element_block& block)
518  {
519 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
520  get(block).m_array.shrink_to_fit();
521 #endif
522  }
523 
524 private:
525  static std::pair<const_iterator,const_iterator>
526  get_iterator_pair(const store_type& array, size_t begin_pos, size_t len)
527  {
528  assert(begin_pos + len <= array.size());
529  const_iterator it = array.begin();
530  std::advance(it, begin_pos);
531  const_iterator it_end = it;
532  std::advance(it_end, len);
533  return std::pair<const_iterator,const_iterator>(it, it_end);
534  }
535 };
536 
537 template<typename _Self, element_t _TypeId, typename _Data>
538 class copyable_element_block : public element_block<_Self, _TypeId, _Data>
539 {
541 protected:
543  copyable_element_block(size_t n) : base_type(n) {}
544  copyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
545 
546  template<typename _Iter>
547  copyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
548 
549 public:
550  using base_type::get;
551 
552  static _Self* clone_block(const base_element_block& blk)
553  {
554  // Use copy constructor to copy the data.
555  return new _Self(get(blk));
556  }
557 };
558 
559 template<typename _Self, element_t _TypeId, typename _Data>
560 class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
561 {
563 protected:
565  noncopyable_element_block(size_t n) : base_type(n) {}
566  noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
567 
568  template<typename _Iter>
569  noncopyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
570 
571 public:
573  noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
574 
575  static _Self* clone_block(const base_element_block&)
576  {
577  throw element_block_error("attempted to clone a noncopyable element block.");
578  }
579 };
580 
588 inline element_t get_block_type(const base_element_block& blk)
589 {
590  return blk.type;
591 }
592 
597 template<element_t _TypeId, typename _Data>
598 struct default_element_block : public copyable_element_block<default_element_block<_TypeId,_Data>, _TypeId, _Data>
599 {
602 
604  default_element_block(size_t n) : base_type(n) {}
605  default_element_block(size_t n, const _Data& val) : base_type(n, val) {}
606 
607  template<typename _Iter>
608  default_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
609 
610  static self_type* create_block_with_value(size_t init_size, const _Data& val)
611  {
612  return new self_type(init_size, val);
613  }
614 
615  template<typename _Iter>
616  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
617  {
618  return new self_type(it_begin, it_end);
619  }
620 
621  static void overwrite_values(base_element_block&, size_t, size_t)
622  {
623  // Do nothing.
624  }
625 };
626 
631 template<element_t _TypeId, typename _Data>
632 struct managed_element_block : public copyable_element_block<managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
633 {
636 
637  using base_type::get;
638  using base_type::set_value;
639  using base_type::m_array;
640 
642  managed_element_block(size_t n) : base_type(n) {}
644  {
645 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
646  m_array.reserve(r.m_array.size());
647 #endif
648  typename managed_element_block::store_type::const_iterator it = r.m_array.begin(), it_end = r.m_array.end();
649  for (; it != it_end; ++it)
650  m_array.push_back(new _Data(**it));
651  }
652 
653  template<typename _Iter>
654  managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
655 
657  {
658  std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
659  }
660 
661  static self_type* create_block_with_value(size_t init_size, _Data* val)
662  {
663  // Managed blocks don't support initialization with value.
664  if (init_size > 1)
665  throw general_error("You can't create a managed block with initial value.");
666 
667  std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
668  if (init_size == 1)
669  set_value(*blk, 0, val);
670 
671  return blk.release();
672  }
673 
674  template<typename _Iter>
675  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
676  {
677  return new self_type(it_begin, it_end);
678  }
679 
680  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
681  {
682  managed_element_block& blk = get(block);
683  typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
684  typename managed_element_block::store_type::iterator it_end = it + len;
685  std::for_each(it, it_end, std::default_delete<_Data>());
686  }
687 };
688 
689 template<element_t _TypeId, typename _Data>
690 struct noncopyable_managed_element_block : public noncopyable_element_block<noncopyable_managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
691 {
694 
695  using base_type::get;
696  using base_type::m_array;
697  using base_type::set_value;
698 
701 
702  template<typename _Iter>
703  noncopyable_managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
704 
706  {
707  std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
708  }
709 
710  static self_type* create_block_with_value(size_t init_size, _Data* val)
711  {
712  // Managed blocks don't support initialization with value.
713  if (init_size > 1)
714  throw general_error("You can't create a managed block with initial value.");
715 
716  std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
717  if (init_size == 1)
718  set_value(*blk, 0, val);
719 
720  return blk.release();
721  }
722 
723  template<typename _Iter>
724  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
725  {
726  return new self_type(it_begin, it_end);
727  }
728 
729  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
730  {
731  noncopyable_managed_element_block& blk = get(block);
732  typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
733  typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
734  std::for_each(it, it_end, std::default_delete<_Data>());
735  }
736 };
737 
750 
751 }}
752 
753 #endif
754 
755 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
756 
Definition: global.hpp:82
Definition: types.hpp:173
friend element_t get_block_type(const base_element_block &)
Definition: types.hpp:588
Definition: types.hpp:539
Definition: types.hpp:160
Definition: types.hpp:182
Definition: types.hpp:561
Definition: types.hpp:599
Definition: types.hpp:633
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