Updated BitVector to recent source
diff --git a/lib/decoding/Vector.h b/lib/decoding/Vector.h
index 88ab654..23b4dd3 100644
--- a/lib/decoding/Vector.h
+++ b/lib/decoding/Vector.h
@@ -1,23 +1,23 @@
/**@file Simplified Vector template with aliases. */
/*
* Copyright 2008 Free Software Foundation, Inc.
+* Copyright 2014 Range Networks, Inc.
*
-* This software is distributed under the terms of the GNU Public License.
+* This software is distributed under the terms of the GNU Affero Public License.
* See the COPYING file in the main directory for details.
-
- This program is free software: you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation, either version 3 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
-
+*
+* This use of this software may be subject to additional restrictions.
+* See the LEGAL file in the main directory for details.
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Affero General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU Affero General Public License for more details.
+ You should have received a copy of the GNU Affero General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
@@ -29,216 +29,358 @@
#include <string.h>
#include <iostream>
#include <assert.h>
+#include <stdio.h>
+// We cant use Logger.h in this file...
+extern int gVectorDebug;
+//#define ENABLE_VECTORDEBUG
+#ifdef ENABLE_VECTORDEBUG
+#define VECTORDEBUG(...) { printf(__VA_ARGS__); printf(" this=%p [%p,%p,%p]\n",(void*)this,(void*)&mData,mStart,mEnd); }
+//#define VECTORDEBUG(msg) { std::cout<<msg<<std::endl; }
+#else
+#define VECTORDEBUG(...)
+#endif
+
+#define BITVECTOR_REFCNTS 0
+
+#if BITVECTOR_REFCNTS
+// (pat) Started to add refcnts, decided against it for now.
+template <class T> class RCData : public RefCntBase {
+ public:
+ T* mPointer;
+};
+#endif
+
/**
- A simplified Vector template with aliases.
- Unlike std::vector, this class does not support dynamic resizing.
- Unlike std::vector, this class does support "aliases" and subvectors.
+ A simplified Vector template with aliases.
+ Unlike std::vector, this class does not support dynamic resizing.
+ Unlike std::vector, this class does support "aliases" and subvectors.
*/
-template <class T> class Vector {
+// (pat) Nov 2013: Vector and the derived classes BitVector and SoftVector were originally written with behavior
+// that differed for const and non-const cases, making them very difficult to use and resulting in many extremely
+// difficult to find bugs in the code base.
+// Ultimately these classes should all be converted to reference counted methodologies, but as an interim measure
+// I am rationalizing their behavior until we flush out all places in the code base that inadvertently depended
+// on the original behavior. This is done with assert statements in BitVector methods.
+// ====
+// What the behavior was probably supposed to be:
+// Vectors can 'own' the data they point to or not. Only one Vector 'owns' the memory at a time,
+// so that automatic destruction can be used. So whenever there is an operation that yields one
+// vector from another the options were: clone (allocate a new vector from memory), alias (make the
+// new vector point into the memory of the original vector) or shift (the new Vector steals the
+// memory ownership from the original vector.)
+// The const copy-constructor did a clone, the non-const copy constructor did a shiftMem, and the segment and
+// related methods (head, tail, etc) returned aliases.
+// Since a copy-constructor is inserted transparently in sometimes surprising places, this made the
+// class very difficult to use. Moreover, since the C++ standard specifies that a copy-constructor is used
+// to copy the return value from functions, it makes it literally impossible for a function to fully control
+// the return value. Our code has relied on the "Return Value Optimization" which says that the C++ compiler
+// may omit the copy-construction of the return value even if the copy-constructor has side-effects, which ours does.
+// This methodology is fundamentally incompatible with C++.
+// What the original behavior actually was:
+// class Vector:
+// The copy-constructor and assignment operators did a clone for the const case and a shift for the non-const case.
+// This is really horrible.
+// The segment methods were identical for const and non-const cases, always returning an alias.
+// This also resulted in zillions of redundant mallocs and copies throughout the code base.
+// class BitVector:
+// Copy-constructor:
+// BitVector did not have any copy-constructors, and I think the intent was that it would have the same behavior
+// as Vector, but that is not how C++ works: with no copy-constructor the default copy-constructor
+// uses only the const case, so only the const Vector copy-constructor was used. Therefore it always cloned,
+// and the code base relied heavily on the "Return Value Optimization" to work at all.
+// Assignment operator:
+// BitVector did not have one, so C++ makes a default one that calls Vector::operator=() as a side effect,
+// which did a clone; not sure if there was a non-const version and no longer care.
+// segment methods:
+// The non-const segment() returned an alias, and the const segment() returned a clone.
+// I think the intent was that the behavior should be the same as Vector, but there was a conversion
+// of the result of the const segment() method from Vector to BitVector which caused the Vector copy-constructor
+// to be (inadvertently) invoked, resulting in the const version of the segment method returning a clone.
+// What the behavior is now:
+// VectorBase:
+// There is a new VectorBase class that has only the common methods and extremely basic constructors.
+// The VectorBase class MUST NOT CONTAIN: copy constructors, non-trivial constructors called from derived classes,
+// or any method that returns a VectorBase type object. Why? Because any of the above when used in derived classes
+// can cause copy-constructor invocation, often surprisingly, obfuscating the code.
+// Each derived class must provide its own: copy-constructors and segment() and related methods, since we do not
+// want to inadvertently invoke a copy-constructor to convert the segment() result from VectorBase to the derived type.
+// BitVector:
+// The BitVector copy-constructor and assignment operator (inherited from VectorBase) paradigm is:
+// if the copied Vector owned memory, perform a clone so the new vector owns memory also,
+// otherwise just do a simple copy, which is another alias. This isnt perfect but works every place
+// in our code base and easier to use than the previous paradigm.
+// The segment method always returns an alias.
+// If you want a clone of a segment, use cloneSegment(), which replaces the previous: const segment(...) const method.
+// Note that the semantics of cloneSegment still rely on the Return Value Optimization. Oh well, we should use refcnts.
+// Vector:
+// I left Vector alone (except for rearrangement to separate out VectorBase.) Vector should just not be used.
+// SoftVector:
+// SoftVector and signalVector should be updated similar to BitVector, but I did not want to disturb them.
+// What the behavior should be:
+// All these should be reference-counted, similar to ByteVector.
+template <class T> class VectorBase
+{
+ // TODO -- Replace memcpy calls with for-loops. (pat) in case class T is not POD [Plain Old Data]
- // TODO -- Replace memcpy calls with for-loops.
+ protected:
+#if BITVECTOR_REFCNTS
+ typedef RefCntPointer<RCData<T> > VectorDataType;
+#else
+ typedef T* VectorDataType;
+#endif
+ VectorDataType mData; ///< allocated data block.
+ T* mStart; ///< start of useful data
+ T* mEnd; ///< end of useful data + 1
- public:
+ // Init vector with specified size. Previous contents are completely discarded. This is only used for initialization.
+ void vInit(size_t elements)
+ {
+ mData = elements ? new T[elements] : NULL;
+ mStart = mData; // This is where mStart get set to zero
+ mEnd = mStart + elements;
+ }
- /**@name Iterator types. */
- //@{
- typedef T* iterator;
- typedef const T* const_iterator;
- //@}
+ /** Assign from another Vector, shifting ownership. */
+ // (pat) This should be eliminated, but it is used by Vector and descendents.
+ void shiftMem(VectorBase<T>&other)
+ {
+ VECTORDEBUG("VectorBase::shiftMem(%p)",(void*)&other);
+ this->clear();
+ this->mData=other.mData;
+ this->mStart=other.mStart;
+ this->mEnd=other.mEnd;
+ other.mData=NULL;
+ }
- protected:
+ // Assign from another Vector, making this an alias to other.
+ void makeAlias(const VectorBase<T> &other)
+ {
+ if (this->getData()) {
+ assert(this->getData() != other.getData()); // Not possible by the semantics of Vector.
+ this->clear();
+ }
+ this->mStart=const_cast<T*>(other.mStart);
+ this->mEnd=const_cast<T*>(other.mEnd);
+ }
- T* mData; ///< allocated data block, if any
- T* mStart; ///< start of useful data
- T* mEnd; ///< end of useful data + 1
+ public:
- public:
+ /** Return the size of the Vector in units, ie, the number of T elements. */
+ size_t size() const
+ {
+ assert(mStart>=mData);
+ assert(mEnd>=mStart);
+ return mEnd - mStart;
+ }
- /** Return the size of the Vector. */
- size_t size() const
- {
- assert(mStart>=mData);
- assert(mEnd>=mStart);
- return mEnd - mStart;
- }
+ /** Return size in bytes. */
+ size_t bytes() const { return this->size()*sizeof(T); }
- /** Return size in bytes. */
- size_t bytes() const { return size()*sizeof(T); }
+ /** Change the size of the Vector in items (not bytes), discarding content. */
+ void resize(size_t newElements) {
+ //VECTORDEBUG("VectorBase::resize("<<(void*)this<<","<<newElements<<")");
+ VECTORDEBUG("VectorBase::resize(%p,%d) %s",this,newElements, (mData?"delete":""));
+ if (mData!=NULL) delete[] mData;
+ vInit(newElements);
+ }
- /** Change the size of the Vector, discarding content. */
- void resize(size_t newSize)
- {
- if (mData!=NULL) delete[] mData;
- if (newSize==0) mData=NULL;
- else mData = new T[newSize];
- mStart = mData;
- mEnd = mStart + newSize;
- }
-
- /** Release memory and clear pointers. */
- void clear() { resize(0); }
+ /** Release memory and clear pointers. */
+ void clear() { this->resize(0); }
- /** Copy data from another vector. */
- void clone(const Vector<T>& other)
- {
- resize(other.size());
- memcpy(mData,other.mStart,other.bytes());
- }
+ /** Copy data from another vector. */
+ void clone(const VectorBase<T>& other) {
+ this->resize(other.size());
+ memcpy(mData,other.mStart,other.bytes());
+ }
+
+ void vConcat(const VectorBase<T>&other1, const VectorBase<T>&other2) {
+ this->resize(other1.size()+other2.size());
+ memcpy(this->mStart, other1.mStart, other1.bytes());
+ memcpy(this->mStart+other1.size(), other2.mStart, other2.bytes());
+ }
+
+ protected:
+
+ VectorBase() : mData(0), mStart(0), mEnd(0) {}
+
+ /** Build a Vector with explicit values. */
+ VectorBase(VectorDataType wData, T* wStart, T* wEnd) :mData(wData),mStart(wStart),mEnd(wEnd) {
+ //VECTORDEBUG("VectorBase("<<(void*)wData);
+ VECTORDEBUG("VectorBase(%p,%p,%p)",this->getData(),wStart,wEnd);
+ }
+
+ public:
+
+ /** Destroy a Vector, deleting held memory. */
+ ~VectorBase() {
+ //VECTORDEBUG("~VectorBase("<<(void*)this<<")");
+ VECTORDEBUG("~VectorBase(%p)",this);
+ this->clear();
+ }
+
+ bool isOwner() { return !!this->mData; } // Do we own any memory ourselves?
+
+ std::string inspect() const {
+ char buf[100];
+ snprintf(buf,100," mData=%p mStart=%p mEnd=%p ",(void*)mData,mStart,mEnd);
+ return std::string(buf);
+ }
+ /**
+ Copy part of this Vector to a segment of another Vector.
+ @param other The other vector.
+ @param start The start point in the other vector.
+ @param span The number of elements to copy.
+ */
+ void copyToSegment(VectorBase<T>& other, size_t start, size_t span) const
+ {
+ T* base = other.mStart + start;
+ assert(base+span<=other.mEnd);
+ assert(mStart+span<=mEnd);
+ memcpy(base,mStart,span*sizeof(T));
+ }
+
+ /** Copy all of this Vector to a segment of another Vector. */
+ void copyToSegment(VectorBase<T>& other, size_t start=0) const { copyToSegment(other,start,size()); }
+
+ void copyTo(VectorBase<T>& other) const { copyToSegment(other,0,size()); }
+
+ /**
+ Copy a segment of this vector into another.
+ @param other The other vector (to copt into starting at 0.)
+ @param start The start point in this vector.
+ @param span The number of elements to copy.
+ WARNING: This function does NOT resize the result - you must set the result size before entering.
+ */
+ void segmentCopyTo(VectorBase<T>& other, size_t start, size_t span) const
+ {
+ const T* base = mStart + start;
+ assert(base+span<=mEnd);
+ assert(other.mStart+span<=other.mEnd);
+ memcpy(other.mStart,base,span*sizeof(T));
+ }
+
+ void fill(const T& val)
+ {
+ T* dp=mStart;
+ while (dp<mEnd) *dp++=val;
+ }
+
+ void fill(const T& val, unsigned start, unsigned length)
+ {
+ T* dp=mStart+start;
+ T* end=dp+length;
+ assert(end<=mEnd);
+ while (dp<end) *dp++=val;
+ }
+
+ /** Assign from another Vector. */
+ // (pat) This is used for both const and non-const cases.
+ // If the original vector owned memory, clone it, otherwise just copy the segment data.
+ void operator=(const VectorBase<T>& other) {
+ //std::cout << "Vector=(this="<<this->inspect()<<",other="<<other.inspect()<<")"<<endl;
+ if (other.getData()) {
+ this->clone(other);
+ } else {
+ this->makeAlias(other);
+ }
+ //std::cout << "Vector= after(this="<<this->inspect()<<")"<<endl;
+ }
- //@{
+ T& operator[](size_t index)
+ {
+ assert(mStart+index<mEnd);
+ return mStart[index];
+ }
- /** Build an empty Vector of a given size. */
- Vector(size_t wSize=0):mData(NULL) { resize(wSize); }
+ const T& operator[](size_t index) const
+ {
+ assert(mStart+index<mEnd);
+ return mStart[index];
+ }
- /** Build a Vector by shifting the data block. */
- Vector(Vector<T>& other)
- :mData(other.mData),mStart(other.mStart),mEnd(other.mEnd)
- { other.mData=NULL; }
-
- /** Build a Vector by copying another. */
- Vector(const Vector<T>& other):mData(NULL) { clone(other); }
-
- /** Build a Vector with explicit values. */
- Vector(T* wData, T* wStart, T* wEnd)
- :mData(wData),mStart(wStart),mEnd(wEnd)
- { }
-
- /** Build a vector from an existing block, NOT to be deleted upon destruction. */
- Vector(T* wStart, size_t span)
- :mData(NULL),mStart(wStart),mEnd(wStart+span)
- { }
-
- /** Build a Vector by concatenation. */
- Vector(const Vector<T>& other1, const Vector<T>& other2)
- :mData(NULL)
- {
- resize(other1.size()+other2.size());
- memcpy(mStart, other1.mStart, other1.bytes());
- memcpy(mStart+other1.size(), other2.mStart, other2.bytes());
- }
-
- //@}
-
- /** Destroy a Vector, deleting held memory. */
- ~Vector() { clear(); }
-
-
-
-
- //@{
-
- /** Assign from another Vector, shifting ownership. */
- void operator=(Vector<T>& other)
- {
- clear();
- mData=other.mData;
- mStart=other.mStart;
- mEnd=other.mEnd;
- other.mData=NULL;
- }
-
- /** Assign from another Vector, copying. */
- void operator=(const Vector<T>& other) { clone(other); }
-
- //@}
-
-
- //@{
-
- /** Return an alias to a segment of this Vector. */
- Vector<T> segment(size_t start, size_t span)
- {
- T* wStart = mStart + start;
- T* wEnd = wStart + span;
- assert(wEnd<=mEnd);
- return Vector<T>(NULL,wStart,wEnd);
- }
-
- /** Return an alias to a segment of this Vector. */
- const Vector<T> segment(size_t start, size_t span) const
- {
- T* wStart = mStart + start;
- T* wEnd = wStart + span;
- assert(wEnd<=mEnd);
- return Vector<T>(NULL,wStart,wEnd);
- }
-
- Vector<T> head(size_t span) { return segment(0,span); }
- const Vector<T> head(size_t span) const { return segment(0,span); }
- Vector<T> tail(size_t start) { return segment(start,size()-start); }
- const Vector<T> tail(size_t start) const { return segment(start,size()-start); }
-
- /**
- Copy part of this Vector to a segment of another Vector.
- @param other The other vector.
- @param start The start point in the other vector.
- @param span The number of elements to copy.
- */
- void copyToSegment(Vector<T>& other, size_t start, size_t span) const
- {
- T* base = other.mStart + start;
- assert(base+span<=other.mEnd);
- assert(mStart+span<=mEnd);
- memcpy(base,mStart,span*sizeof(T));
- }
-
- /** Copy all of this Vector to a segment of another Vector. */
- void copyToSegment(Vector<T>& other, size_t start=0) const { copyToSegment(other,start,size()); }
-
- void copyTo(Vector<T>& other) const { copyToSegment(other,0,size()); }
-
- /**
- Copy a segment of this vector into another.
- @param other The other vector (to copt into starting at 0.)
- @param start The start point in this vector.
- @param span The number of elements to copy.
- */
- void segmentCopyTo(Vector<T>& other, size_t start, size_t span)
- {
- T* base = mStart + start;
- assert(base+span<=mEnd);
- assert(other.mStart+span<=other.mEnd);
- memcpy(other.mStart,base,span*sizeof(T));
- }
-
- void fill(const T& val)
- {
- T* dp=mStart;
- while (dp<mEnd) *dp++=val;
- }
-
-
- //@}
-
-
- //@{
-
- T& operator[](size_t index)
- {
- assert(mStart+index<mEnd);
- return mStart[index];
- }
-
- const T& operator[](size_t index) const
- {
- assert(mStart+index<mEnd);
- return mStart[index];
- }
-
- const T* begin() const { return mStart; }
- T* begin() { return mStart; }
- const T* end() const { return mEnd; }
- T* end() { return mEnd; }
- //@}
-
-
+ const T* begin() const { return this->mStart; }
+ T* begin() { return this->mStart; }
+ const T* end() const { return this->mEnd; }
+ T* end() { return this->mEnd; }
+#if BITVECTOR_REFCNTS
+ const T*getData() const { return this->mData.isNULL() ? 0 : this->mData->mPointer; }
+#else
+ const T*getData() const { return this->mData; }
+#endif
};
+// (pat) Nov 2013. This class retains the original poor behavior. See comments at VectorBase
+template <class T> class Vector : public VectorBase<T>
+{
+ public:
+
+ /** Build an empty Vector of a given size. */
+ Vector(size_t wSize=0) { this->resize(wSize); }
+
+ /** Build a Vector by shifting the data block. */
+ Vector(Vector<T>& other) : VectorBase<T>(other.mData,other.mStart,other.mEnd) { other.mData=NULL; }
+
+ /** Build a Vector by copying another. */
+ Vector(const Vector<T>& other):VectorBase<T>() { this->clone(other); }
+
+ /** Build a Vector with explicit values. */
+ Vector(T* wData, T* wStart, T* wEnd) : VectorBase<T>(wData,wStart,wEnd) { }
+
+ /** Build a vector from an existing block, NOT to be deleted upon destruction. */
+ Vector(T* wStart, size_t span) : VectorBase<T>(NULL,wStart,wStart+span) { }
+
+ /** Build a Vector by concatenation. */
+ Vector(const Vector<T>& other1, const Vector<T>& other2):VectorBase<T>() {
+ assert(this->mData == 0);
+ this->vConcat(other1,other2);
+ }
+
+ //@{
+
+ /** Assign from another Vector, shifting ownership. */
+ void operator=(Vector<T>& other) { this->shiftMem(other); }
+
+ /** Assign from another Vector, copying. */
+ void operator=(const Vector<T>& other) { this->clone(other); }
+
+ /** Return an alias to a segment of this Vector. */
+ Vector<T> segment(size_t start, size_t span)
+ {
+ T* wStart = this->mStart + start;
+ T* wEnd = wStart + span;
+ assert(wEnd<=this->mEnd);
+ return Vector<T>(NULL,wStart,wEnd);
+ }
+
+ /** Return an alias to a segment of this Vector. */
+ const Vector<T> segment(size_t start, size_t span) const
+ {
+ T* wStart = this->mStart + start;
+ T* wEnd = wStart + span;
+ assert(wEnd<=this->mEnd);
+ return Vector<T>(NULL,wStart,wEnd);
+ }
+
+ Vector<T> head(size_t span) { return segment(0,span); }
+ const Vector<T> head(size_t span) const { return segment(0,span); }
+ Vector<T> tail(size_t start) { return segment(start,this->size()-start); }
+ const Vector<T> tail(size_t start) const { return segment(start,this->size()-start); }
+
+ /**@name Iterator types. */
+ //@{
+ typedef T* iterator;
+ typedef const T* const_iterator;
+ //@}
+
+ //@}
+};
+
+
@@ -246,8 +388,8 @@
template <class T>
std::ostream& operator<<(std::ostream& os, const Vector<T>& v)
{
- for (unsigned i=0; i<v.size(); i++) os << v[i] << " ";
- return os;
+ for (unsigned i=0; i<v.size(); i++) os << v[i] << " ";
+ return os;
}