GNU Radio's GSM Package
Vector.h
Go to the documentation of this file.
1 /**@file Simplified Vector template with aliases. */
2 /*
3 * Copyright 2008 Free Software Foundation, Inc.
4 * Copyright 2014 Range Networks, Inc.
5 *
6 * This software is distributed under the terms of the GNU Affero Public License.
7 * See the COPYING file in the main directory for details.
8 *
9 * This use of this software may be subject to additional restrictions.
10 * See the LEGAL file in the main directory for details.
11  This program is free software: you can redistribute it and/or modify
12  it under the terms of the GNU Affero General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15  This program is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  GNU Affero General Public License for more details.
19  You should have received a copy of the GNU Affero General Public License
20  along with this program. If not, see <http://www.gnu.org/licenses/>.
21 */
22 
23 
24 
25 
26 #ifndef VECTOR_H
27 #define VECTOR_H
28 
29 #include <string.h>
30 #include <iostream>
31 #include <assert.h>
32 #include <stdio.h>
33 // We cant use Logger.h in this file...
34 extern int gVectorDebug;
35 //#define ENABLE_VECTORDEBUG
36 #ifdef ENABLE_VECTORDEBUG
37 #define VECTORDEBUG(...) { printf(__VA_ARGS__); printf(" this=%p [%p,%p,%p]\n",(void*)this,(void*)&mData,mStart,mEnd); }
38 //#define VECTORDEBUG(msg) { std::cout<<msg<<std::endl; }
39 #else
40 #define VECTORDEBUG(...)
41 #endif
42 
43 #define BITVECTOR_REFCNTS 0
44 
45 #if BITVECTOR_REFCNTS
46 // (pat) Started to add refcnts, decided against it for now.
47 template <class T> class RCData : public RefCntBase {
48  public:
49  T* mPointer;
50 };
51 #endif
52 
53 
54 /**
55  A simplified Vector template with aliases.
56  Unlike std::vector, this class does not support dynamic resizing.
57  Unlike std::vector, this class does support "aliases" and subvectors.
58 */
59 // (pat) Nov 2013: Vector and the derived classes BitVector and SoftVector were originally written with behavior
60 // that differed for const and non-const cases, making them very difficult to use and resulting in many extremely
61 // difficult to find bugs in the code base.
62 // Ultimately these classes should all be converted to reference counted methodologies, but as an interim measure
63 // I am rationalizing their behavior until we flush out all places in the code base that inadvertently depended
64 // on the original behavior. This is done with assert statements in BitVector methods.
65 // ====
66 // What the behavior was probably supposed to be:
67 // Vectors can 'own' the data they point to or not. Only one Vector 'owns' the memory at a time,
68 // so that automatic destruction can be used. So whenever there is an operation that yields one
69 // vector from another the options were: clone (allocate a new vector from memory), alias (make the
70 // new vector point into the memory of the original vector) or shift (the new Vector steals the
71 // memory ownership from the original vector.)
72 // The const copy-constructor did a clone, the non-const copy constructor did a shiftMem, and the segment and
73 // related methods (head, tail, etc) returned aliases.
74 // Since a copy-constructor is inserted transparently in sometimes surprising places, this made the
75 // class very difficult to use. Moreover, since the C++ standard specifies that a copy-constructor is used
76 // to copy the return value from functions, it makes it literally impossible for a function to fully control
77 // the return value. Our code has relied on the "Return Value Optimization" which says that the C++ compiler
78 // may omit the copy-construction of the return value even if the copy-constructor has side-effects, which ours does.
79 // This methodology is fundamentally incompatible with C++.
80 // What the original behavior actually was:
81 // class Vector:
82 // The copy-constructor and assignment operators did a clone for the const case and a shift for the non-const case.
83 // This is really horrible.
84 // The segment methods were identical for const and non-const cases, always returning an alias.
85 // This also resulted in zillions of redundant mallocs and copies throughout the code base.
86 // class BitVector:
87 // Copy-constructor:
88 // BitVector did not have any copy-constructors, and I think the intent was that it would have the same behavior
89 // as Vector, but that is not how C++ works: with no copy-constructor the default copy-constructor
90 // uses only the const case, so only the const Vector copy-constructor was used. Therefore it always cloned,
91 // and the code base relied heavily on the "Return Value Optimization" to work at all.
92 // Assignment operator:
93 // BitVector did not have one, so C++ makes a default one that calls Vector::operator=() as a side effect,
94 // which did a clone; not sure if there was a non-const version and no longer care.
95 // segment methods:
96 // The non-const segment() returned an alias, and the const segment() returned a clone.
97 // I think the intent was that the behavior should be the same as Vector, but there was a conversion
98 // of the result of the const segment() method from Vector to BitVector which caused the Vector copy-constructor
99 // to be (inadvertently) invoked, resulting in the const version of the segment method returning a clone.
100 // What the behavior is now:
101 // VectorBase:
102 // There is a new VectorBase class that has only the common methods and extremely basic constructors.
103 // The VectorBase class MUST NOT CONTAIN: copy constructors, non-trivial constructors called from derived classes,
104 // or any method that returns a VectorBase type object. Why? Because any of the above when used in derived classes
105 // can cause copy-constructor invocation, often surprisingly, obfuscating the code.
106 // Each derived class must provide its own: copy-constructors and segment() and related methods, since we do not
107 // want to inadvertently invoke a copy-constructor to convert the segment() result from VectorBase to the derived type.
108 // BitVector:
109 // The BitVector copy-constructor and assignment operator (inherited from VectorBase) paradigm is:
110 // if the copied Vector owned memory, perform a clone so the new vector owns memory also,
111 // otherwise just do a simple copy, which is another alias. This isnt perfect but works every place
112 // in our code base and easier to use than the previous paradigm.
113 // The segment method always returns an alias.
114 // If you want a clone of a segment, use cloneSegment(), which replaces the previous: const segment(...) const method.
115 // Note that the semantics of cloneSegment still rely on the Return Value Optimization. Oh well, we should use refcnts.
116 // Vector:
117 // I left Vector alone (except for rearrangement to separate out VectorBase.) Vector should just not be used.
118 // SoftVector:
119 // SoftVector and signalVector should be updated similar to BitVector, but I did not want to disturb them.
120 // What the behavior should be:
121 // All these should be reference-counted, similar to ByteVector.
122 template <class T> class VectorBase
123 {
124  // TODO -- Replace memcpy calls with for-loops. (pat) in case class T is not POD [Plain Old Data]
125 
126  protected:
127 #if BITVECTOR_REFCNTS
128  typedef RefCntPointer<RCData<T> > VectorDataType;
129 #else
130  typedef T* VectorDataType;
131 #endif
132  VectorDataType mData; ///< allocated data block.
133  T* mStart; ///< start of useful data
134  T* mEnd; ///< end of useful data + 1
135 
136  // Init vector with specified size. Previous contents are completely discarded. This is only used for initialization.
137  void vInit(size_t elements)
138  {
139  mData = elements ? new T[elements] : NULL;
140  mStart = mData; // This is where mStart get set to zero
141  mEnd = mStart + elements;
142  }
143 
144  /** Assign from another Vector, shifting ownership. */
145  // (pat) This should be eliminated, but it is used by Vector and descendents.
147  {
148  VECTORDEBUG("VectorBase::shiftMem(%p)",(void*)&other);
149  this->clear();
150  this->mData=other.mData;
151  this->mStart=other.mStart;
152  this->mEnd=other.mEnd;
153  other.mData=NULL;
154  }
155 
156  // Assign from another Vector, making this an alias to other.
157  void makeAlias(const VectorBase<T> &other)
158  {
159  if (this->getData()) {
160  assert(this->getData() != other.getData()); // Not possible by the semantics of Vector.
161  this->clear();
162  }
163  this->mStart=const_cast<T*>(other.mStart);
164  this->mEnd=const_cast<T*>(other.mEnd);
165  }
166 
167  public:
168 
169  /** Return the size of the Vector in units, ie, the number of T elements. */
170  size_t size() const
171  {
172  assert(mStart>=mData);
173  assert(mEnd>=mStart);
174  return mEnd - mStart;
175  }
176 
177  /** Return size in bytes. */
178  size_t bytes() const { return this->size()*sizeof(T); }
179 
180  /** Change the size of the Vector in items (not bytes), discarding content. */
181  void resize(size_t newElements) {
182  //VECTORDEBUG("VectorBase::resize("<<(void*)this<<","<<newElements<<")");
183  VECTORDEBUG("VectorBase::resize(%p,%d) %s",this,newElements, (mData?"delete":""));
184  if (mData!=NULL) delete[] mData;
185  vInit(newElements);
186  }
187 
188  /** Release memory and clear pointers. */
189  void clear() { this->resize(0); }
190 
191 
192  /** Copy data from another vector. */
193  void clone(const VectorBase<T>& other) {
194  this->resize(other.size());
195  memcpy(mData,other.mStart,other.bytes());
196  }
197 
198  void vConcat(const VectorBase<T>&other1, const VectorBase<T>&other2) {
199  this->resize(other1.size()+other2.size());
200  memcpy(this->mStart, other1.mStart, other1.bytes());
201  memcpy(this->mStart+other1.size(), other2.mStart, other2.bytes());
202  }
203 
204  protected:
205 
206  VectorBase() : mData(0), mStart(0), mEnd(0) {}
207 
208  /** Build a Vector with explicit values. */
209  VectorBase(VectorDataType wData, T* wStart, T* wEnd) :mData(wData),mStart(wStart),mEnd(wEnd) {
210  //VECTORDEBUG("VectorBase("<<(void*)wData);
211  VECTORDEBUG("VectorBase(%p,%p,%p)",this->getData(),wStart,wEnd);
212  }
213 
214  public:
215 
216  /** Destroy a Vector, deleting held memory. */
218  //VECTORDEBUG("~VectorBase("<<(void*)this<<")");
219  VECTORDEBUG("~VectorBase(%p)",this);
220  this->clear();
221  }
222 
223  bool isOwner() { return !!this->mData; } // Do we own any memory ourselves?
224 
225  std::string inspect() const {
226  char buf[100];
227  snprintf(buf,100," mData=%p mStart=%p mEnd=%p ",(void*)mData,mStart,mEnd);
228  return std::string(buf);
229  }
230 
231 
232  /**
233  Copy part of this Vector to a segment of another Vector.
234  @param other The other vector.
235  @param start The start point in the other vector.
236  @param span The number of elements to copy.
237  */
238  void copyToSegment(VectorBase<T>& other, size_t start, size_t span) const
239  {
240  T* base = other.mStart + start;
241  assert(base+span<=other.mEnd);
242  assert(mStart+span<=mEnd);
243  memcpy(base,mStart,span*sizeof(T));
244  }
245 
246  /** Copy all of this Vector to a segment of another Vector. */
247  void copyToSegment(VectorBase<T>& other, size_t start=0) const { copyToSegment(other,start,size()); }
248 
249  void copyTo(VectorBase<T>& other) const { copyToSegment(other,0,size()); }
250 
251  /**
252  Copy a segment of this vector into another.
253  @param other The other vector (to copt into starting at 0.)
254  @param start The start point in this vector.
255  @param span The number of elements to copy.
256  WARNING: This function does NOT resize the result - you must set the result size before entering.
257  */
258  void segmentCopyTo(VectorBase<T>& other, size_t start, size_t span) const
259  {
260  const T* base = mStart + start;
261  assert(base+span<=mEnd);
262  assert(other.mStart+span<=other.mEnd);
263  memcpy(other.mStart,base,span*sizeof(T));
264  }
265 
266  void fill(const T& val)
267  {
268  T* dp=mStart;
269  while (dp<mEnd) *dp++=val;
270  }
271 
272  void fill(const T& val, unsigned start, unsigned length)
273  {
274  T* dp=mStart+start;
275  T* end=dp+length;
276  assert(end<=mEnd);
277  while (dp<end) *dp++=val;
278  }
279 
280  /** Assign from another Vector. */
281  // (pat) This is used for both const and non-const cases.
282  // If the original vector owned memory, clone it, otherwise just copy the segment data.
283  void operator=(const VectorBase<T>& other) {
284  //std::cout << "Vector=(this="<<this->inspect()<<",other="<<other.inspect()<<")"<<endl;
285  if (other.getData()) {
286  this->clone(other);
287  } else {
288  this->makeAlias(other);
289  }
290  //std::cout << "Vector= after(this="<<this->inspect()<<")"<<endl;
291  }
292 
293 
294  T& operator[](size_t index)
295  {
296  assert(mStart+index<mEnd);
297  return mStart[index];
298  }
299 
300  const T& operator[](size_t index) const
301  {
302  assert(mStart+index<mEnd);
303  return mStart[index];
304  }
305 
306  const T* begin() const { return this->mStart; }
307  T* begin() { return this->mStart; }
308  const T* end() const { return this->mEnd; }
309  T* end() { return this->mEnd; }
310 #if BITVECTOR_REFCNTS
311  const T*getData() const { return this->mData.isNULL() ? 0 : this->mData->mPointer; }
312 #else
313  const T*getData() const { return this->mData; }
314 #endif
315 };
316 
317 // (pat) Nov 2013. This class retains the original poor behavior. See comments at VectorBase
318 template <class T> class Vector : public VectorBase<T>
319 {
320  public:
321 
322  /** Build an empty Vector of a given size. */
323  Vector(size_t wSize=0) { this->resize(wSize); }
324 
325  /** Build a Vector by shifting the data block. */
326  Vector(Vector<T>& other) : VectorBase<T>(other.mData,other.mStart,other.mEnd) { other.mData=NULL; }
327 
328  /** Build a Vector by copying another. */
329  Vector(const Vector<T>& other):VectorBase<T>() { this->clone(other); }
330 
331  /** Build a Vector with explicit values. */
332  Vector(T* wData, T* wStart, T* wEnd) : VectorBase<T>(wData,wStart,wEnd) { }
333 
334  /** Build a vector from an existing block, NOT to be deleted upon destruction. */
335  Vector(T* wStart, size_t span) : VectorBase<T>(NULL,wStart,wStart+span) { }
336 
337  /** Build a Vector by concatenation. */
338  Vector(const Vector<T>& other1, const Vector<T>& other2):VectorBase<T>() {
339  assert(this->mData == 0);
340  this->vConcat(other1,other2);
341  }
342 
343  //@{
344 
345  /** Assign from another Vector, shifting ownership. */
346  void operator=(Vector<T>& other) { this->shiftMem(other); }
347 
348  /** Assign from another Vector, copying. */
349  void operator=(const Vector<T>& other) { this->clone(other); }
350 
351  /** Return an alias to a segment of this Vector. */
352  Vector<T> segment(size_t start, size_t span)
353  {
354  T* wStart = this->mStart + start;
355  T* wEnd = wStart + span;
356  assert(wEnd<=this->mEnd);
357  return Vector<T>(NULL,wStart,wEnd);
358  }
359 
360  /** Return an alias to a segment of this Vector. */
361  const Vector<T> segment(size_t start, size_t span) const
362  {
363  T* wStart = this->mStart + start;
364  T* wEnd = wStart + span;
365  assert(wEnd<=this->mEnd);
366  return Vector<T>(NULL,wStart,wEnd);
367  }
368 
369  Vector<T> head(size_t span) { return segment(0,span); }
370  const Vector<T> head(size_t span) const { return segment(0,span); }
371  Vector<T> tail(size_t start) { return segment(start,this->size()-start); }
372  const Vector<T> tail(size_t start) const { return segment(start,this->size()-start); }
373 
374  /**@name Iterator types. */
375  //@{
376  typedef T* iterator;
377  typedef const T* const_iterator;
378  //@}
379 
380  //@}
381 };
382 
383 
384 
385 
386 
387 /** Basic print operator for Vector objects. */
388 template <class T>
389 std::ostream& operator<<(std::ostream& os, const Vector<T>& v)
390 {
391  for (unsigned i=0; i<v.size(); i++) os << v[i] << " ";
392  return os;
393 }
394 
395 
396 
397 #endif
398 // vim: ts=4 sw=4
void makeAlias(const VectorBase< T > &other)
Definition: Vector.h:157
void operator=(const VectorBase< T > &other)
Definition: Vector.h:283
T * mStart
start of useful data
Definition: Vector.h:133
void vInit(size_t elements)
Definition: Vector.h:137
void operator=(Vector< T > &other)
Definition: Vector.h:346
std::string inspect() const
Definition: Vector.h:225
Definition: Vector.h:318
void vConcat(const VectorBase< T > &other1, const VectorBase< T > &other2)
Definition: Vector.h:198
int gVectorDebug
void copyToSegment(VectorBase< T > &other, size_t start=0) const
Definition: Vector.h:247
const Vector< T > head(size_t span) const
Definition: Vector.h:370
void fill(const T &val)
Definition: Vector.h:266
size_t size() const
Definition: Vector.h:170
void resize(size_t newElements)
Definition: Vector.h:181
T * VectorDataType
Definition: Vector.h:130
VectorBase()
Definition: Vector.h:206
VectorDataType mData
allocated data block.
Definition: Vector.h:132
void fill(const T &val, unsigned start, unsigned length)
Definition: Vector.h:272
size_t bytes() const
Definition: Vector.h:178
const T * begin() const
Definition: Vector.h:306
void segmentCopyTo(VectorBase< T > &other, size_t start, size_t span) const
Definition: Vector.h:258
Vector(const Vector< T > &other)
Definition: Vector.h:329
Vector(const Vector< T > &other1, const Vector< T > &other2)
Definition: Vector.h:338
const T & operator[](size_t index) const
Definition: Vector.h:300
T * mEnd
end of useful data + 1
Definition: Vector.h:134
void copyToSegment(VectorBase< T > &other, size_t start, size_t span) const
Definition: Vector.h:238
#define VECTORDEBUG(...)
Definition: Vector.h:40
void shiftMem(VectorBase< T > &other)
Definition: Vector.h:146
Vector< T > head(size_t span)
Definition: Vector.h:369
void copyTo(VectorBase< T > &other) const
Definition: Vector.h:249
Vector(size_t wSize=0)
Definition: Vector.h:323
Vector(T *wData, T *wStart, T *wEnd)
Definition: Vector.h:332
bool isOwner()
Definition: Vector.h:223
Vector< T > segment(size_t start, size_t span)
Definition: Vector.h:352
T * end()
Definition: Vector.h:309
void clear()
Definition: Vector.h:189
void operator=(const Vector< T > &other)
Definition: Vector.h:349
void clone(const VectorBase< T > &other)
Definition: Vector.h:193
Vector(Vector< T > &other)
Definition: Vector.h:326
T & operator[](size_t index)
Definition: Vector.h:294
Vector< T > tail(size_t start)
Definition: Vector.h:371
T * iterator
Definition: Vector.h:376
const Vector< T > tail(size_t start) const
Definition: Vector.h:372
const T * const_iterator
Definition: Vector.h:377
T * begin()
Definition: Vector.h:307
Vector(T *wStart, size_t span)
Definition: Vector.h:335
const T * end() const
Definition: Vector.h:308
const Vector< T > segment(size_t start, size_t span) const
Definition: Vector.h:361
~VectorBase()
Definition: Vector.h:217
const T * getData() const
Definition: Vector.h:313
Definition: Vector.h:122
VectorBase(VectorDataType wData, T *wStart, T *wEnd)
Definition: Vector.h:209