Galois
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PODResizeableArray.h
Go to the documentation of this file.
1 /*
2  * This file belongs to the Galois project, a C++ library for exploiting
3  * parallelism. The code is being released under the terms of the 3-Clause BSD
4  * License (a copy is located in LICENSE.txt at the top-level directory).
5  *
6  * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
7  * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
8  * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
9  * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
10  * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
11  * DEALING OR USAGE OF TRADE. NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
12  * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
13  * shall University be liable for incidental, special, indirect, direct or
14  * consequential damages or loss of profits, interruption of business, or
15  * related expenses which may arise from use of Software or Documentation,
16  * including but not limited to those resulting from defects in Software and/or
17  * Documentation, or loss or inaccuracy of data of any kind.
18  */
19 
20 #ifndef GALOIS_PODRESIZEABLEARRAY_H
21 #define GALOIS_PODRESIZEABLEARRAY_H
22 
23 #include <iterator>
24 #include <stdexcept>
25 #include <cstddef>
26 #include <algorithm>
27 #include <utility>
28 #include <type_traits>
29 
30 #include "galois/config.h"
31 
32 namespace galois {
33 
39 template <typename _Tp>
41  _Tp* data_;
42  size_t capacity_;
43  size_t size_;
44 
45 public:
46  typedef _Tp value_type;
47  typedef size_t size_type;
48  typedef ptrdiff_t difference_type;
50  typedef const value_type& const_reference;
51  typedef value_type* pointer;
52  typedef const value_type* const_pointer;
53  typedef pointer iterator;
55  typedef std::reverse_iterator<iterator> reverse_iterator;
56  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
57 
58  PODResizeableArray() : data_(NULL), capacity_(0), size_(0) {}
59 
60  template <class InputIterator>
61  PODResizeableArray(InputIterator first, InputIterator last)
62  : data_(NULL), capacity_(0), size_(0) {
63  size_t to_add = last - first;
64  resize(to_add);
65  std::copy_n(first, to_add, begin());
66  }
67 
68  PODResizeableArray(size_t n) : data_(NULL), capacity_(0), size_(0) {
69  resize(n);
70  }
71 
73  PODResizeableArray(const PODResizeableArray&) = delete;
74 
77  : data_(v.data_), capacity_(v.capacity_), size_(v.size_) {
78  v.data_ = NULL;
79  v.capacity_ = 0;
80  v.size_ = 0;
81  }
82 
85 
88  if (data_ != NULL)
89  free(data_);
90  data_ = v.data_;
91  capacity_ = v.capacity_;
92  size_ = v.size_;
93  v.data_ = NULL;
94  v.capacity_ = 0;
95  v.size_ = 0;
96  return *this;
97  }
98 
100  if (data_ != NULL)
101  free(data_);
102  }
103 
104  // iterators:
105  iterator begin() { return iterator(&data_[0]); }
106  const_iterator begin() const { return const_iterator(&data_[0]); }
107  iterator end() { return iterator(&data_[size_]); }
108  const_iterator end() const { return const_iterator(&data_[size_]); }
109 
112  return const_reverse_iterator(end());
113  }
116  return const_reverse_iterator(begin());
117  }
118 
119  const_iterator cbegin() const { return begin(); }
120  const_iterator cend() const { return end(); }
121  const_reverse_iterator crbegin() const { return rbegin(); }
122  const_reverse_iterator crend() const { return rend(); }
123 
124  // size:
125  size_type size() const { return size_; }
126  size_type max_size() const { return capacity_; }
127  bool empty() const { return size_ == 0; }
128 
129  void reserve(size_t n) {
130  if (n > capacity_) {
131  if (capacity_ == 0) {
132  capacity_ = 1;
133  }
134  while (capacity_ < n) {
135  capacity_ <<= 1;
136  }
137  data_ = static_cast<_Tp*>(
138  realloc(reinterpret_cast<void*>(data_), capacity_ * sizeof(_Tp)));
139  }
140  }
141 
142  void resize(size_t n) {
143  reserve(n);
144  size_ = n;
145  }
146 
147  void clear() { size_ = 0; }
148 
149  // element access:
150  reference operator[](size_type __n) { return data_[__n]; }
151  const_reference operator[](size_type __n) const { return data_[__n]; }
153  if (__n >= size_)
154  throw std::out_of_range("PODResizeableArray::at");
155  return data_[__n];
156  }
158  if (__n >= size_)
159  throw std::out_of_range("PODResizeableArray::at");
160  return data_[__n];
161  }
162 
163  void assign(iterator first, iterator last) {
164  size_t n = last - first;
165  resize(n);
166  memcpy(reinterpret_cast<void*>(data_), first, n * sizeof(_Tp));
167  }
168 
169  reference front() { return data_[0]; }
170  const_reference front() const { return data_[0]; }
171  reference back() { return data_[size_ - 1]; }
172  const_reference back() const { return data_[size_ - 1]; }
173 
174  pointer data() { return data_; }
175  const_pointer data() const { return data_; }
176 
177  void push_back(const _Tp& value) {
178  resize(size_ + 1);
179  data_[size_ - 1] = value;
180  }
181 
182  template <class InputIterator>
183  void insert(iterator GALOIS_USED_ONLY_IN_DEBUG(position), InputIterator first,
184  InputIterator last) {
185  assert(position == end());
186  size_t old_size = size_;
187  size_t to_add = last - first;
188  resize(old_size + to_add);
189  std::copy_n(first, to_add, begin() + old_size);
190  }
191 
193  std::swap(data_, v.data_);
194  std::swap(size_, v.size_);
195  std::swap(capacity_, v.capacity_);
196  }
197 };
198 
199 } // namespace galois
200 #endif // GALOIS_PODRESIZEABLEARRAY_H
const_reverse_iterator crbegin() const
Definition: PODResizeableArray.h:121
iterator end()
Definition: PODResizeableArray.h:107
const_reference back() const
Definition: PODResizeableArray.h:172
const_pointer data() const
Definition: PODResizeableArray.h:175
PODResizeableArray(size_t n)
Definition: PODResizeableArray.h:68
reference at(size_type __n)
Definition: PODResizeableArray.h:152
const_reverse_iterator crend() const
Definition: PODResizeableArray.h:122
void push_back(const _Tp &value)
Definition: PODResizeableArray.h:177
size_t size_type
Definition: PODResizeableArray.h:47
const_iterator end() const
Definition: PODResizeableArray.h:108
reference front()
Definition: PODResizeableArray.h:169
ptrdiff_t difference_type
Definition: PODResizeableArray.h:48
reference back()
Definition: PODResizeableArray.h:171
const value_type * const_pointer
Definition: PODResizeableArray.h:52
const_iterator cbegin() const
Definition: PODResizeableArray.h:119
size_type max_size() const
Definition: PODResizeableArray.h:126
PODResizeableArray & operator=(PODResizeableArray &&v)
move assignment operator
Definition: PODResizeableArray.h:87
void resize(size_t n)
Definition: PODResizeableArray.h:142
bool empty() const
Definition: PODResizeableArray.h:127
const_reference at(size_type __n) const
Definition: PODResizeableArray.h:157
PODResizeableArray(InputIterator first, InputIterator last)
Definition: PODResizeableArray.h:61
void insert(iterator GALOIS_USED_ONLY_IN_DEBUG(position), InputIterator first, InputIterator last)
Definition: PODResizeableArray.h:183
reference operator[](size_type __n)
Definition: PODResizeableArray.h:150
PODResizeableArray & operator=(const PODResizeableArray &)=delete
disabled (shallow) copy assignment operator
const_pointer const_iterator
Definition: PODResizeableArray.h:54
void assign(iterator first, iterator last)
Definition: PODResizeableArray.h:163
const_reverse_iterator rend() const
Definition: PODResizeableArray.h:115
const_reference front() const
Definition: PODResizeableArray.h:170
void reserve(size_t n)
Definition: PODResizeableArray.h:129
std::reverse_iterator< iterator > reverse_iterator
Definition: PODResizeableArray.h:55
void swap(PODResizeableArray &v)
Definition: PODResizeableArray.h:192
PODResizeableArray()
Definition: PODResizeableArray.h:58
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: PODResizeableArray.h:56
const_iterator cend() const
Definition: PODResizeableArray.h:120
value_type & reference
Definition: PODResizeableArray.h:49
const value_type & const_reference
Definition: PODResizeableArray.h:50
size_type size() const
Definition: PODResizeableArray.h:125
const_reverse_iterator rbegin() const
Definition: PODResizeableArray.h:111
value_type * pointer
Definition: PODResizeableArray.h:51
void clear()
Definition: PODResizeableArray.h:147
const_iterator begin() const
Definition: PODResizeableArray.h:106
~PODResizeableArray()
Definition: PODResizeableArray.h:99
pointer iterator
Definition: PODResizeableArray.h:53
_Tp value_type
Definition: PODResizeableArray.h:46
iterator begin()
Definition: PODResizeableArray.h:105
reverse_iterator rbegin()
Definition: PODResizeableArray.h:110
This is a container that encapsulates a resizeable array of plain-old-datatype (POD) elements...
Definition: PODResizeableArray.h:40
pointer data()
Definition: PODResizeableArray.h:174
const_reference operator[](size_type __n) const
Definition: PODResizeableArray.h:151
PODResizeableArray(PODResizeableArray &&v)
move constructor
Definition: PODResizeableArray.h:76
reverse_iterator rend()
Definition: PODResizeableArray.h:114