1 #ifndef LCDF_VECTOR_CC
2 #define LCDF_VECTOR_CC
3
4 /*
5 * vector.{cc,hh} -- simple array template class
6 * Eddie Kohler
7 *
8 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
9 * Copyright (c) 2001-2003 International Computer Science Institute
10 * Copyright (c) 1999-2012 Eddie Kohler
11 *
12 * Permission is hereby granted, free of charge, to any person obtaining a
13 * copy of this software and associated documentation files (the "Software"),
14 * to deal in the Software without restriction, subject to the conditions
15 * listed in the Click LICENSE file. These conditions include: you must
16 * preserve this copyright notice, and you cannot mention the copyright
17 * holders in advertising related to the Software without their permission.
18 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
19 * notice is a summary of the Click LICENSE file; the license in that file is
20 * legally binding.
21 */
22
23 /* #include <lcdf/vector.hh> */
24
25 template <class T>
Vector(const Vector<T> & x)26 Vector<T>::Vector(const Vector<T> &x)
27 : _l(0), _n(0), _capacity(0)
28 {
29 *this = x;
30 }
31
32 template <class T>
~Vector()33 Vector<T>::~Vector()
34 {
35 for (size_type i = 0; i < _n; i++)
36 _l[i].~T();
37 delete[] (unsigned char *)_l;
38 }
39
40 template <class T> Vector<T> &
operator =(const Vector<T> & o)41 Vector<T>::operator=(const Vector<T> &o)
42 {
43 if (&o != this) {
44 for (size_type i = 0; i < _n; i++)
45 _l[i].~T();
46 #ifdef VALGRIND_MAKE_MEM_NOACCESS
47 if (_l && _n)
48 VALGRIND_MAKE_MEM_NOACCESS(_l, _n * sizeof(T));
49 #endif
50 _n = 0;
51 if (reserve(o._n)) {
52 _n = o._n;
53 #ifdef VALGRIND_MAKE_MEM_UNDEFINED
54 if (_l && _n)
55 VALGRIND_MAKE_MEM_UNDEFINED(_l, _n * sizeof(T));
56 #endif
57 for (size_type i = 0; i < _n; i++)
58 new(velt(i)) T(o._l[i]);
59 }
60 }
61 return *this;
62 }
63
64 template <class T> Vector<T> &
assign(size_type n,const T & x)65 Vector<T>::assign(size_type n, const T &x)
66 {
67 if (&x >= begin() && &x < end()) {
68 T x_copy(x);
69 return assign(n, x_copy);
70 } else {
71 resize(0, x);
72 resize(n, x);
73 return *this;
74 }
75 }
76
77 template <class T> typename Vector<T>::iterator
insert(iterator it,const T & x)78 Vector<T>::insert(iterator it, const T &x)
79 {
80 assert(it >= begin() && it <= end());
81 if (&x >= begin() && &x < end()) {
82 T x_copy(x);
83 return insert(it, x_copy);
84 }
85 if (_n == _capacity) {
86 size_type pos = it - begin();
87 if (!reserve(RESERVE_GROW))
88 return end();
89 it = begin() + pos;
90 }
91 #ifdef VALGRIND_MAKE_MEM_UNDEFINED
92 VALGRIND_MAKE_MEM_UNDEFINED(velt(_n), sizeof(T));
93 #endif
94 for (iterator j = end(); j > it; ) {
95 --j;
96 new((void*) (j + 1)) T(*j);
97 j->~T();
98 #ifdef VALGRIND_MAKE_MEM_UNDEFINED
99 VALGRIND_MAKE_MEM_UNDEFINED(j, sizeof(T));
100 #endif
101 }
102 new((void*) it) T(x);
103 _n++;
104 return it;
105 }
106
107 template <class T> typename Vector<T>::iterator
erase(iterator a,iterator b)108 Vector<T>::erase(iterator a, iterator b)
109 {
110 if (b > a) {
111 assert(a >= begin() && b <= end());
112 iterator i = a, j = b;
113 for (; j < end(); i++, j++) {
114 i->~T();
115 #ifdef VALGRIND_MAKE_MEM_UNDEFINED
116 VALGRIND_MAKE_MEM_UNDEFINED(i, sizeof(T));
117 #endif
118 new((void*) i) T(*j);
119 }
120 for (; i < end(); i++)
121 i->~T();
122 _n -= b - a;
123 #ifdef VALGRIND_MAKE_MEM_NOACCESS
124 VALGRIND_MAKE_MEM_NOACCESS(_l + _n, (b - a) * sizeof(T));
125 #endif
126 return a;
127 } else
128 return b;
129 }
130
131 template <class T> bool
reserve_and_push_back(size_type want,const T * push_x)132 Vector<T>::reserve_and_push_back(size_type want, const T *push_x)
133 {
134 if (push_x && push_x >= begin() && push_x < end()) {
135 T x_copy(*push_x);
136 return reserve_and_push_back(want, &x_copy);
137 }
138
139 if (want < 0)
140 want = (_capacity > 0 ? _capacity * 2 : 4);
141
142 if (want > _capacity) {
143 T *new_l = (T *)new unsigned char[sizeof(T) * want];
144 if (!new_l)
145 return false;
146 #ifdef VALGRIND_MAKE_MEM_NOACCESS
147 VALGRIND_MAKE_MEM_NOACCESS(new_l + _n, (want - _n) * sizeof(T));
148 #endif
149
150 for (size_type i = 0; i < _n; i++) {
151 new(velt(new_l, i)) T(_l[i]);
152 _l[i].~T();
153 }
154 delete[] (unsigned char *)_l;
155
156 _l = new_l;
157 _capacity = want;
158 }
159
160 if (push_x)
161 push_back(*push_x);
162 return true;
163 }
164
165 template <class T> void
resize(size_type n,const T & x)166 Vector<T>::resize(size_type n, const T &x)
167 {
168 if (&x >= begin() && &x < end()) {
169 T x_copy(x);
170 resize(n, x_copy);
171 } else if (n <= _capacity || reserve(n)) {
172 for (size_type i = n; i < _n; i++)
173 _l[i].~T();
174 #ifdef VALGRIND_MAKE_MEM_NOACCESS
175 if (n < _n)
176 VALGRIND_MAKE_MEM_NOACCESS(_l + n, (_n - n) * sizeof(T));
177 if (_n < n)
178 VALGRIND_MAKE_MEM_UNDEFINED(_l + _n, (n - _n) * sizeof(T));
179 #endif
180 for (size_type i = _n; i < n; i++)
181 new(velt(i)) T(x);
182 _n = n;
183 }
184 }
185
186 template <class T> void
swap(Vector<T> & x)187 Vector<T>::swap(Vector<T> &x)
188 {
189 T *l = _l;
190 _l = x._l;
191 x._l = l;
192
193 size_type n = _n;
194 _n = x._n;
195 x._n = n;
196
197 size_type cap = _capacity;
198 _capacity = x._capacity;
199 x._capacity = cap;
200 }
201
202 #endif
203