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 
100 {
101 public:
102  element_block_error(const std::string& msg) : mdds::general_error(msg) {}
103 };
104 
105 class base_element_block;
106 element_t get_block_type(const base_element_block&);
107 
113 {
114  friend element_t get_block_type(const base_element_block&);
115 protected:
116  element_t type;
117  base_element_block(element_t _t) : type(_t) {}
118 };
119 
120 template<typename _Self, element_t _TypeId, typename _Data>
122 {
123 #ifdef MDDS_UNIT_TEST
124  struct print_block_array
125  {
126  void operator() (const _Data& val) const
127  {
128  std::cout << val << " ";
129  }
130  };
131 #endif
132 
133 protected:
134 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
135  typedef std::deque<_Data> store_type;
136 #else
137  typedef std::vector<_Data> store_type;
138 #endif
139  store_type m_array;
140 
141  element_block() : base_element_block(_TypeId) {}
142  element_block(size_t n) : base_element_block(_TypeId), m_array(n) {}
143  element_block(size_t n, const _Data& val) : base_element_block(_TypeId), m_array(n, val) {}
144 
145  template<typename _Iter>
146  element_block(const _Iter& it_begin, const _Iter& it_end) : base_element_block(_TypeId), m_array(it_begin, it_end) {}
147 
148 public:
149  static const element_t block_type = _TypeId;
150 
151  typedef typename store_type::iterator iterator;
152  typedef typename store_type::reverse_iterator reverse_iterator;
153  typedef typename store_type::const_iterator const_iterator;
154  typedef typename store_type::const_reverse_iterator const_reverse_iterator;
155  typedef _Data value_type;
156 
157  bool operator== (const _Self& r) const
158  {
159  return m_array == r.m_array;
160  }
161 
162  bool operator!= (const _Self& r) const
163  {
164  return !operator==(r);
165  }
166 
167  static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
168  {
169  return get(block).m_array.at(pos);
170  }
171 
172  static value_type& at(base_element_block& block, typename store_type::size_type pos)
173  {
174  return get(block).m_array.at(pos);
175  }
176 
177  static value_type* data(base_element_block& block)
178  {
179  return get(block).m_array.data();
180  }
181 
182  static typename store_type::size_type size(const base_element_block& block)
183  {
184  return get(block).m_array.size();
185  }
186 
187  static iterator begin(base_element_block& block)
188  {
189  return get(block).m_array.begin();
190  }
191 
192  static iterator end(base_element_block& block)
193  {
194  return get(block).m_array.end();
195  }
196 
197  static const_iterator begin(const base_element_block& block)
198  {
199  return get(block).m_array.begin();
200  }
201 
202  static const_iterator end(const base_element_block& block)
203  {
204  return get(block).m_array.end();
205  }
206 
207  static const_iterator cbegin(const base_element_block& block)
208  {
209  return get(block).m_array.begin();
210  }
211 
212  static const_iterator cend(const base_element_block& block)
213  {
214  return get(block).m_array.end();
215  }
216 
217  static reverse_iterator rbegin(base_element_block& block)
218  {
219  return get(block).m_array.rbegin();
220  }
221 
222  static reverse_iterator rend(base_element_block& block)
223  {
224  return get(block).m_array.rend();
225  }
226 
227  static const_reverse_iterator rbegin(const base_element_block& block)
228  {
229  return get(block).m_array.rbegin();
230  }
231 
232  static const_reverse_iterator rend(const base_element_block& block)
233  {
234  return get(block).m_array.rend();
235  }
236 
237  static const_reverse_iterator crbegin(const base_element_block& block)
238  {
239  return get(block).m_array.rbegin();
240  }
241 
242  static const_reverse_iterator crend(const base_element_block& block)
243  {
244  return get(block).m_array.rend();
245  }
246 
247  static _Self& get(base_element_block& block)
248  {
249 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
250  if (get_block_type(block) != _TypeId)
251  {
252  std::ostringstream os;
253  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
254  throw general_error(os.str());
255  }
256 #endif
257  return static_cast<_Self&>(block);
258  }
259 
260  static const _Self& get(const base_element_block& block)
261  {
262 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
263  if (get_block_type(block) != _TypeId)
264  {
265  std::ostringstream os;
266  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
267  throw general_error(os.str());
268  }
269 #endif
270  return static_cast<const _Self&>(block);
271  }
272 
273  static void set_value(base_element_block& blk, size_t pos, const _Data& val)
274  {
275  get(blk).m_array[pos] = val;
276  }
277 
278  static void get_value(const base_element_block& blk, size_t pos, _Data& val)
279  {
280  val = get(blk).m_array[pos];
281  }
282 
283  static value_type get_value(const base_element_block& blk, size_t pos)
284  {
285  return get(blk).m_array[pos];
286  }
287 
288  static void append_value(base_element_block& blk, const _Data& val)
289  {
290  get(blk).m_array.push_back(val);
291  }
292 
293  static void prepend_value(base_element_block& blk, const _Data& val)
294  {
295  store_type& blk2 = get(blk).m_array;
296  blk2.insert(blk2.begin(), val);
297  }
298 
299  static _Self* create_block(size_t init_size)
300  {
301  return new _Self(init_size);
302  }
303 
304  static void delete_block(const base_element_block* p)
305  {
306  delete static_cast<const _Self*>(p);
307  }
308 
309  static void resize_block(base_element_block& blk, size_t new_size)
310  {
311  store_type& st = get(blk).m_array;
312  st.resize(new_size);
313 
314  // Test if the vector's capacity is larger than twice its current
315  // size, and if so, shrink its capacity to free up some memory.
316  if (new_size < (st.capacity() / 2))
317  st.shrink_to_fit();
318  }
319 
320 #ifdef MDDS_UNIT_TEST
321  static void print_block(const base_element_block& blk)
322  {
323  const store_type& blk2 = get(blk).m_array;
324  std::for_each(blk2.begin(), blk2.end(), print_block_array());
325  std::cout << std::endl;
326  }
327 #else
328  static void print_block(const base_element_block&) {}
329 #endif
330 
331  static void erase_block(base_element_block& blk, size_t pos)
332  {
333  store_type& blk2 = get(blk).m_array;
334  blk2.erase(blk2.begin()+pos);
335  }
336 
337  static void erase_block(base_element_block& blk, size_t pos, size_t size)
338  {
339  store_type& blk2 = get(blk).m_array;
340  blk2.erase(blk2.begin()+pos, blk2.begin()+pos+size);
341  }
342 
343  static void append_values_from_block(base_element_block& dest, const base_element_block& src)
344  {
345  store_type& d = get(dest).m_array;
346  const store_type& s = get(src).m_array;
347  d.insert(d.end(), s.begin(), s.end());
348  }
349 
350  static void append_values_from_block(
351  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
352  {
353  store_type& d = get(dest).m_array;
354  const store_type& s = get(src).m_array;
355  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
356 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
357  d.reserve(d.size() + len);
358 #endif
359  d.insert(d.end(), its.first, its.second);
360  }
361 
362  static void assign_values_from_block(
363  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
364  {
365  store_type& d = get(dest).m_array;
366  const store_type& s = get(src).m_array;
367  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
368  d.assign(its.first, its.second);
369  }
370 
371  static void prepend_values_from_block(
372  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
373  {
374  store_type& d = get(dest).m_array;
375  const store_type& s = get(src).m_array;
376  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
377 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
378  d.reserve(d.size() + len);
379 #endif
380  d.insert(d.begin(), its.first, its.second);
381  }
382 
383  static void swap_values(
384  base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
385  {
386  store_type& st1 = get(blk1).m_array;
387  store_type& st2 = get(blk2).m_array;
388  assert(pos1 + len <= st1.size());
389  assert(pos2 + len <= st2.size());
390 
391  typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
392  std::advance(it1, pos1);
393  std::advance(it2, pos2);
394  for (size_t i = 0; i < len; ++i, ++it1, ++it2)
395  {
396 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
397  std::swap(*it1, *it2);
398 #else
399  value_type v1 = *it1, v2 = *it2;
400  *it1 = v2;
401  *it2 = v1;
402 #endif
403  }
404  }
405 
406  template<typename _Iter>
407  static void set_values(
408  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
409  {
410  store_type& d = get(block).m_array;
411  typename store_type::iterator it_dest = d.begin();
412  std::advance(it_dest, pos);
413  for (_Iter it = it_begin; it != it_end; ++it, ++it_dest)
414  *it_dest = *it;
415  }
416 
417  template<typename _Iter>
418  static void append_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
419  {
420  store_type& d = get(block).m_array;
421  typename store_type::iterator it = d.end();
422  d.insert(it, it_begin, it_end);
423  }
424 
425  template<typename _Iter>
426  static void prepend_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
427  {
428  store_type& d = get(block).m_array;
429  d.insert(d.begin(), it_begin, it_end);
430  }
431 
432  template<typename _Iter>
433  static void assign_values(base_element_block& dest, const _Iter& it_begin, const _Iter& it_end)
434  {
435  store_type& d = get(dest).m_array;
436  d.assign(it_begin, it_end);
437  }
438 
439  template<typename _Iter>
440  static void insert_values(
441  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
442  {
443  store_type& blk = get(block).m_array;
444  blk.insert(blk.begin()+pos, it_begin, it_end);
445  }
446 
447  static size_t capacity(const base_element_block& block)
448  {
449 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
450  return 0;
451 #else
452  const store_type& blk = get(block).m_array;
453  return blk.capacity();
454 #endif
455  }
456 
457  static void shrink_to_fit(base_element_block& block)
458  {
459 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
460  get(block).m_array.shrink_to_fit();
461 #endif
462  }
463 
464 private:
465  static std::pair<const_iterator,const_iterator>
466  get_iterator_pair(const store_type& array, size_t begin_pos, size_t len)
467  {
468  assert(begin_pos + len <= array.size());
469  const_iterator it = array.begin();
470  std::advance(it, begin_pos);
471  const_iterator it_end = it;
472  std::advance(it_end, len);
473  return std::pair<const_iterator,const_iterator>(it, it_end);
474  }
475 };
476 
477 template<typename _Self, element_t _TypeId, typename _Data>
478 class copyable_element_block : public element_block<_Self, _TypeId, _Data>
479 {
481 protected:
483  copyable_element_block(size_t n) : base_type(n) {}
484  copyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
485 
486  template<typename _Iter>
487  copyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
488 
489 public:
490  using base_type::get;
491 
492  static _Self* clone_block(const base_element_block& blk)
493  {
494  // Use copy constructor to copy the data.
495  return new _Self(get(blk));
496  }
497 };
498 
499 template<typename _Self, element_t _TypeId, typename _Data>
500 class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
501 {
503 protected:
505  noncopyable_element_block(size_t n) : base_type(n) {}
506  noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
507 
508  template<typename _Iter>
509  noncopyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
510 
511 public:
513  noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
514 
515  static _Self* clone_block(const base_element_block&)
516  {
517  throw element_block_error("attempted to clone a noncopyable element block.");
518  }
519 };
520 
528 inline element_t get_block_type(const base_element_block& blk)
529 {
530  return blk.type;
531 }
532 
537 template<element_t _TypeId, typename _Data>
538 struct default_element_block : public copyable_element_block<default_element_block<_TypeId,_Data>, _TypeId, _Data>
539 {
542 
544  default_element_block(size_t n) : base_type(n) {}
545  default_element_block(size_t n, const _Data& val) : base_type(n, val) {}
546 
547  template<typename _Iter>
548  default_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
549 
550  static self_type* create_block_with_value(size_t init_size, const _Data& val)
551  {
552  return new self_type(init_size, val);
553  }
554 
555  template<typename _Iter>
556  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
557  {
558  return new self_type(it_begin, it_end);
559  }
560 
561  static void overwrite_values(base_element_block&, size_t, size_t)
562  {
563  // Do nothing.
564  }
565 };
566 
571 template<element_t _TypeId, typename _Data>
572 struct managed_element_block : public copyable_element_block<managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
573 {
576 
577  using base_type::get;
578  using base_type::set_value;
579  using base_type::m_array;
580 
582  managed_element_block(size_t n) : base_type(n) {}
584  {
585 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
586  m_array.reserve(r.m_array.size());
587 #endif
588  typename managed_element_block::store_type::const_iterator it = r.m_array.begin(), it_end = r.m_array.end();
589  for (; it != it_end; ++it)
590  m_array.push_back(new _Data(**it));
591  }
592 
593  template<typename _Iter>
594  managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
595 
597  {
598  std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
599  }
600 
601  static self_type* create_block_with_value(size_t init_size, _Data* val)
602  {
603  // Managed blocks don't support initialization with value.
604  if (init_size > 1)
605  throw general_error("You can't create a managed block with initial value.");
606 
607  std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
608  if (init_size == 1)
609  set_value(*blk, 0, val);
610 
611  return blk.release();
612  }
613 
614  template<typename _Iter>
615  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
616  {
617  return new self_type(it_begin, it_end);
618  }
619 
620  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
621  {
622  managed_element_block& blk = get(block);
623  typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
624  typename managed_element_block::store_type::iterator it_end = it + len;
625  std::for_each(it, it_end, std::default_delete<_Data>());
626  }
627 };
628 
629 template<element_t _TypeId, typename _Data>
630 struct noncopyable_managed_element_block : public noncopyable_element_block<noncopyable_managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
631 {
634 
635  using base_type::get;
636  using base_type::m_array;
637  using base_type::set_value;
638 
641 
642  template<typename _Iter>
643  noncopyable_managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
644 
646  {
647  std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
648  }
649 
650  static self_type* create_block_with_value(size_t init_size, _Data* val)
651  {
652  // Managed blocks don't support initialization with value.
653  if (init_size > 1)
654  throw general_error("You can't create a managed block with initial value.");
655 
656  std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
657  if (init_size == 1)
658  set_value(*blk, 0, val);
659 
660  return blk.release();
661  }
662 
663  template<typename _Iter>
664  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
665  {
666  return new self_type(it_begin, it_end);
667  }
668 
669  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
670  {
671  noncopyable_managed_element_block& blk = get(block);
672  typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
673  typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
674  std::for_each(it, it_end, std::default_delete<_Data>());
675  }
676 };
677 
690 
691 }}
692 
693 #endif
694 
695 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
696 
Definition: global.hpp:82
Definition: types.hpp:113
friend element_t get_block_type(const base_element_block &)
Definition: types.hpp:528
Definition: types.hpp:479
Definition: types.hpp:100
Definition: types.hpp:122
Definition: types.hpp:501
Definition: types.hpp:539
Definition: types.hpp:573