mdds
multi_type_vector_types.hpp
1 /*************************************************************************
2  *
3  * Copyright (c) 2012-2018 Kohei Yoshida
4  *
5  * Permission is hereby granted, free of charge, to any person
6  * obtaining a copy of this software and associated documentation
7  * files (the "Software"), to deal in the Software without
8  * restriction, including without limitation the rights to use,
9  * copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following
12  * conditions:
13  *
14  * The above copyright notice and this permission notice shall be
15  * included in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24  * OTHER DEALINGS IN THE SOFTWARE.
25  *
26  ************************************************************************/
27 
28 #ifndef INCLUDED_MDDS_MULTI_TYPE_VECTOR_TYPES_HPP
29 #define INCLUDED_MDDS_MULTI_TYPE_VECTOR_TYPES_HPP
30 
31 #include "global.hpp"
32 
33 #include <algorithm>
34 #include <cassert>
35 #include <memory>
36 #include <cstdint>
37 
38 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
39 #include <deque>
40 #else
41 #include <vector>
42 #endif
43 
44 #if defined(MDDS_UNIT_TEST) || defined (MDDS_MULTI_TYPE_VECTOR_DEBUG)
45 #include <iostream>
46 #include <sstream>
47 using std::cout;
48 using std::cerr;
49 using std::endl;
50 #endif
51 
52 namespace mdds { namespace mtv {
53 
54 using element_t = int;
55 
56 constexpr element_t element_type_empty = -1;
57 
58 constexpr element_t element_type_boolean = 0;
59 constexpr element_t element_type_int8 = 1;
60 constexpr element_t element_type_uint8 = 2;
61 constexpr element_t element_type_int16 = 3;
62 constexpr element_t element_type_uint16 = 4;
63 constexpr element_t element_type_int32 = 5;
64 constexpr element_t element_type_uint32 = 6;
65 constexpr element_t element_type_int64 = 7;
66 constexpr element_t element_type_uint64 = 8;
67 constexpr element_t element_type_float = 9;
68 constexpr element_t element_type_double = 10;
69 constexpr element_t element_type_string = 11;
70 
71 constexpr element_t element_type_user_start = 50;
72 
76 class element_block_error : public mdds::general_error
77 {
78 public:
79  element_block_error(const std::string& msg) : mdds::general_error(msg) {}
80 };
81 
82 struct base_element_block;
83 element_t get_block_type(const base_element_block&);
84 
89 struct base_element_block
90 {
91  friend element_t get_block_type(const base_element_block&);
92 protected:
93  element_t type;
94  base_element_block(element_t _t) : type(_t) {}
95 };
96 
97 template<typename _Self, element_t _TypeId, typename _Data>
98 class element_block : public base_element_block
99 {
100 #ifdef MDDS_UNIT_TEST
101  struct print_block_array
102  {
103  void operator() (const _Data& val) const
104  {
105  std::cout << val << " ";
106  }
107  };
108 #endif
109 
110 protected:
111 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
112  typedef std::deque<_Data> store_type;
113 #else
114  typedef std::vector<_Data> store_type;
115 #endif
116  store_type m_array;
117 
118  element_block() : base_element_block(_TypeId) {}
119  element_block(size_t n) : base_element_block(_TypeId), m_array(n) {}
120  element_block(size_t n, const _Data& val) : base_element_block(_TypeId), m_array(n, val) {}
121 
122  template<typename _Iter>
123  element_block(const _Iter& it_begin, const _Iter& it_end) : base_element_block(_TypeId), m_array(it_begin, it_end) {}
124 
125 public:
126  static const element_t block_type = _TypeId;
127 
128  typedef typename store_type::iterator iterator;
129  typedef typename store_type::reverse_iterator reverse_iterator;
130  typedef typename store_type::const_iterator const_iterator;
131  typedef typename store_type::const_reverse_iterator const_reverse_iterator;
132  typedef _Data value_type;
133 
134  bool operator== (const _Self& r) const
135  {
136  return m_array == r.m_array;
137  }
138 
139  bool operator!= (const _Self& r) const
140  {
141  return !operator==(r);
142  }
143 
144  static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
145  {
146  return get(block).m_array.at(pos);
147  }
148 
149  static value_type& at(base_element_block& block, typename store_type::size_type pos)
150  {
151  return get(block).m_array.at(pos);
152  }
153 
154  static value_type* data(base_element_block& block)
155  {
156  return get(block).m_array.data();
157  }
158 
159  static typename store_type::size_type size(const base_element_block& block)
160  {
161  return get(block).m_array.size();
162  }
163 
164  static iterator begin(base_element_block& block)
165  {
166  return get(block).m_array.begin();
167  }
168 
169  static iterator end(base_element_block& block)
170  {
171  return get(block).m_array.end();
172  }
173 
174  static const_iterator begin(const base_element_block& block)
175  {
176  return get(block).m_array.begin();
177  }
178 
179  static const_iterator end(const base_element_block& block)
180  {
181  return get(block).m_array.end();
182  }
183 
184  static const_iterator cbegin(const base_element_block& block)
185  {
186  return get(block).m_array.begin();
187  }
188 
189  static const_iterator cend(const base_element_block& block)
190  {
191  return get(block).m_array.end();
192  }
193 
194  static reverse_iterator rbegin(base_element_block& block)
195  {
196  return get(block).m_array.rbegin();
197  }
198 
199  static reverse_iterator rend(base_element_block& block)
200  {
201  return get(block).m_array.rend();
202  }
203 
204  static const_reverse_iterator rbegin(const base_element_block& block)
205  {
206  return get(block).m_array.rbegin();
207  }
208 
209  static const_reverse_iterator rend(const base_element_block& block)
210  {
211  return get(block).m_array.rend();
212  }
213 
214  static const_reverse_iterator crbegin(const base_element_block& block)
215  {
216  return get(block).m_array.rbegin();
217  }
218 
219  static const_reverse_iterator crend(const base_element_block& block)
220  {
221  return get(block).m_array.rend();
222  }
223 
224  static _Self& get(base_element_block& block)
225  {
226 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
227  if (get_block_type(block) != _TypeId)
228  {
229  std::ostringstream os;
230  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
231  throw general_error(os.str());
232  }
233 #endif
234  return static_cast<_Self&>(block);
235  }
236 
237  static const _Self& get(const base_element_block& block)
238  {
239 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
240  if (get_block_type(block) != _TypeId)
241  {
242  std::ostringstream os;
243  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
244  throw general_error(os.str());
245  }
246 #endif
247  return static_cast<const _Self&>(block);
248  }
249 
250  static void set_value(base_element_block& blk, size_t pos, const _Data& val)
251  {
252  get(blk).m_array[pos] = val;
253  }
254 
255  static void get_value(const base_element_block& blk, size_t pos, _Data& val)
256  {
257  val = get(blk).m_array[pos];
258  }
259 
260  static value_type get_value(const base_element_block& blk, size_t pos)
261  {
262  return get(blk).m_array[pos];
263  }
264 
265  static void append_value(base_element_block& blk, const _Data& val)
266  {
267  get(blk).m_array.push_back(val);
268  }
269 
270  static void prepend_value(base_element_block& blk, const _Data& val)
271  {
272  store_type& blk2 = get(blk).m_array;
273  blk2.insert(blk2.begin(), val);
274  }
275 
276  static _Self* create_block(size_t init_size)
277  {
278  return new _Self(init_size);
279  }
280 
281  static void delete_block(const base_element_block* p)
282  {
283  delete static_cast<const _Self*>(p);
284  }
285 
286  static void resize_block(base_element_block& blk, size_t new_size)
287  {
288  store_type& st = get(blk).m_array;
289  st.resize(new_size);
290 
291  // Test if the vector's capacity is larger than twice its current
292  // size, and if so, shrink its capacity to free up some memory.
293  if (new_size < (st.capacity() / 2))
294  st.shrink_to_fit();
295  }
296 
297 #ifdef MDDS_UNIT_TEST
298  static void print_block(const base_element_block& blk)
299  {
300  const store_type& blk2 = get(blk).m_array;
301  std::for_each(blk2.begin(), blk2.end(), print_block_array());
302  std::cout << std::endl;
303  }
304 #else
305  static void print_block(const base_element_block&) {}
306 #endif
307 
308  static void erase_block(base_element_block& blk, size_t pos)
309  {
310  store_type& blk2 = get(blk).m_array;
311  blk2.erase(blk2.begin()+pos);
312  }
313 
314  static void erase_block(base_element_block& blk, size_t pos, size_t size)
315  {
316  store_type& blk2 = get(blk).m_array;
317  blk2.erase(blk2.begin()+pos, blk2.begin()+pos+size);
318  }
319 
320  static void append_values_from_block(base_element_block& dest, const base_element_block& src)
321  {
322  store_type& d = get(dest).m_array;
323  const store_type& s = get(src).m_array;
324  d.insert(d.end(), s.begin(), s.end());
325  }
326 
327  static void append_values_from_block(
328  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
329  {
330  store_type& d = get(dest).m_array;
331  const store_type& s = get(src).m_array;
332  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
333 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
334  d.reserve(d.size() + len);
335 #endif
336  d.insert(d.end(), its.first, its.second);
337  }
338 
339  static void assign_values_from_block(
340  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
341  {
342  store_type& d = get(dest).m_array;
343  const store_type& s = get(src).m_array;
344  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
345  d.assign(its.first, its.second);
346  }
347 
348  static void prepend_values_from_block(
349  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
350  {
351  store_type& d = get(dest).m_array;
352  const store_type& s = get(src).m_array;
353  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
354 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
355  d.reserve(d.size() + len);
356 #endif
357  d.insert(d.begin(), its.first, its.second);
358  }
359 
360  static void swap_values(
361  base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
362  {
363  store_type& st1 = get(blk1).m_array;
364  store_type& st2 = get(blk2).m_array;
365  assert(pos1 + len <= st1.size());
366  assert(pos2 + len <= st2.size());
367 
368  typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
369  std::advance(it1, pos1);
370  std::advance(it2, pos2);
371  for (size_t i = 0; i < len; ++i, ++it1, ++it2)
372  {
373 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
374  std::swap(*it1, *it2);
375 #else
376  value_type v1 = *it1, v2 = *it2;
377  *it1 = v2;
378  *it2 = v1;
379 #endif
380  }
381  }
382 
383  template<typename _Iter>
384  static void set_values(
385  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
386  {
387  store_type& d = get(block).m_array;
388  typename store_type::iterator it_dest = d.begin();
389  std::advance(it_dest, pos);
390  for (_Iter it = it_begin; it != it_end; ++it, ++it_dest)
391  *it_dest = *it;
392  }
393 
394  template<typename _Iter>
395  static void append_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
396  {
397  store_type& d = get(block).m_array;
398  typename store_type::iterator it = d.end();
399  d.insert(it, it_begin, it_end);
400  }
401 
402  template<typename _Iter>
403  static void prepend_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
404  {
405  store_type& d = get(block).m_array;
406  d.insert(d.begin(), it_begin, it_end);
407  }
408 
409  template<typename _Iter>
410  static void assign_values(base_element_block& dest, const _Iter& it_begin, const _Iter& it_end)
411  {
412  store_type& d = get(dest).m_array;
413  d.assign(it_begin, it_end);
414  }
415 
416  template<typename _Iter>
417  static void insert_values(
418  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
419  {
420  store_type& blk = get(block).m_array;
421  blk.insert(blk.begin()+pos, it_begin, it_end);
422  }
423 
424  static size_t capacity(const base_element_block& block)
425  {
426 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
427  return 0;
428 #else
429  const store_type& blk = get(block).m_array;
430  return blk.capacity();
431 #endif
432  }
433 
434  static void shrink_to_fit(base_element_block& block)
435  {
436 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
437  get(block).m_array.shrink_to_fit();
438 #endif
439  }
440 
441 private:
442  static std::pair<const_iterator,const_iterator>
443  get_iterator_pair(const store_type& array, size_t begin_pos, size_t len)
444  {
445  assert(begin_pos + len <= array.size());
446  const_iterator it = array.begin();
447  std::advance(it, begin_pos);
448  const_iterator it_end = it;
449  std::advance(it_end, len);
450  return std::pair<const_iterator,const_iterator>(it, it_end);
451  }
452 };
453 
454 template<typename _Self, element_t _TypeId, typename _Data>
455 class copyable_element_block : public element_block<_Self, _TypeId, _Data>
456 {
457  typedef element_block<_Self,_TypeId,_Data> base_type;
458 protected:
459  copyable_element_block() : base_type() {}
460  copyable_element_block(size_t n) : base_type(n) {}
461  copyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
462 
463  template<typename _Iter>
464  copyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
465 
466 public:
467  using base_type::get;
468 
469  static _Self* clone_block(const base_element_block& blk)
470  {
471  // Use copy constructor to copy the data.
472  return new _Self(get(blk));
473  }
474 };
475 
476 template<typename _Self, element_t _TypeId, typename _Data>
477 class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
478 {
479  typedef element_block<_Self,_TypeId,_Data> base_type;
480 protected:
481  noncopyable_element_block() : base_type() {}
482  noncopyable_element_block(size_t n) : base_type(n) {}
483  noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
484 
485  template<typename _Iter>
486  noncopyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
487 
488 public:
489  noncopyable_element_block(const noncopyable_element_block&) = delete;
490  noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
491 
492  static _Self* clone_block(const base_element_block&)
493  {
494  throw element_block_error("attempted to clone a noncopyable element block.");
495  }
496 };
497 
505 inline element_t get_block_type(const base_element_block& blk)
506 {
507  return blk.type;
508 }
509 
514 template<element_t _TypeId, typename _Data>
515 struct default_element_block : public copyable_element_block<default_element_block<_TypeId,_Data>, _TypeId, _Data>
516 {
517  typedef copyable_element_block<default_element_block, _TypeId, _Data> base_type;
518  typedef default_element_block<_TypeId,_Data> self_type;
519 
520  default_element_block() : base_type() {}
521  default_element_block(size_t n) : base_type(n) {}
522  default_element_block(size_t n, const _Data& val) : base_type(n, val) {}
523 
524  template<typename _Iter>
525  default_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
526 
527  static self_type* create_block_with_value(size_t init_size, const _Data& val)
528  {
529  return new self_type(init_size, val);
530  }
531 
532  template<typename _Iter>
533  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
534  {
535  return new self_type(it_begin, it_end);
536  }
537 
538  static void overwrite_values(base_element_block&, size_t, size_t)
539  {
540  // Do nothing.
541  }
542 };
543 
548 template<element_t _TypeId, typename _Data>
549 struct managed_element_block : public copyable_element_block<managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
550 {
551  typedef copyable_element_block<managed_element_block<_TypeId,_Data>, _TypeId, _Data*> base_type;
553 
554  using base_type::get;
555  using base_type::set_value;
556  using base_type::m_array;
557 
558  managed_element_block() : base_type() {}
559  managed_element_block(size_t n) : base_type(n) {}
560  managed_element_block(const managed_element_block& r)
561  {
562 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
563  m_array.reserve(r.m_array.size());
564 #endif
565  typename managed_element_block::store_type::const_iterator it = r.m_array.begin(), it_end = r.m_array.end();
566  for (; it != it_end; ++it)
567  m_array.push_back(new _Data(**it));
568  }
569 
570  template<typename _Iter>
571  managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
572 
573  ~managed_element_block()
574  {
575  std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
576  }
577 
578  static self_type* create_block_with_value(size_t init_size, _Data* val)
579  {
580  // Managed blocks don't support initialization with value.
581  if (init_size > 1)
582  throw general_error("You can't create a managed block with initial value.");
583 
584  std::unique_ptr<self_type> blk = make_unique<self_type>(init_size);
585  if (init_size == 1)
586  set_value(*blk, 0, val);
587 
588  return blk.release();
589  }
590 
591  template<typename _Iter>
592  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
593  {
594  return new self_type(it_begin, it_end);
595  }
596 
597  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
598  {
599  managed_element_block& blk = get(block);
600  typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
601  typename managed_element_block::store_type::iterator it_end = it + len;
602  std::for_each(it, it_end, std::default_delete<_Data>());
603  }
604 };
605 
606 template<element_t _TypeId, typename _Data>
607 struct noncopyable_managed_element_block : public noncopyable_element_block<noncopyable_managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
608 {
609  typedef noncopyable_element_block<noncopyable_managed_element_block<_TypeId,_Data>, _TypeId, _Data*> base_type;
610  typedef managed_element_block<_TypeId,_Data> self_type;
611 
612  using base_type::get;
613  using base_type::m_array;
614  using base_type::set_value;
615 
616  noncopyable_managed_element_block() : base_type() {}
617  noncopyable_managed_element_block(size_t n) : base_type(n) {}
618 
619  template<typename _Iter>
620  noncopyable_managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
621 
622  ~noncopyable_managed_element_block()
623  {
624  std::for_each(m_array.begin(), m_array.end(), std::default_delete<_Data>());
625  }
626 
627  static self_type* create_block_with_value(size_t init_size, _Data* val)
628  {
629  // Managed blocks don't support initialization with value.
630  if (init_size > 1)
631  throw general_error("You can't create a managed block with initial value.");
632 
633  std::unique_ptr<self_type> blk = make_unique<self_type>(init_size);
634  if (init_size == 1)
635  set_value(*blk, 0, val);
636 
637  return blk.release();
638  }
639 
640  template<typename _Iter>
641  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
642  {
643  return new self_type(it_begin, it_end);
644  }
645 
646  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
647  {
648  noncopyable_managed_element_block& blk = get(block);
649  typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
650  typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
651  std::for_each(it, it_end, std::default_delete<_Data>());
652  }
653 };
654 
667 
668 }}
669 
670 #endif
mdds::mtv::managed_element_block
Definition: multi_type_vector_types.hpp:596
mdds::mtv::base_element_block::get_block_type
friend element_t get_block_type(const base_element_block &)
Definition: multi_type_vector_types.hpp:552
mdds::general_error
Definition: global.hpp:69
mdds::mtv::default_element_block
Definition: multi_type_vector_types.hpp:562
mdds::mtv::base_element_block
Definition: multi_type_vector_types.hpp:136
mdds::mtv::element_block
Definition: multi_type_vector_types.hpp:145