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