TVecPool< TVal, TSizeTy > Class Template Reference

Vector Pool. More...

#include <ds.h>

Public Types
typedef TPt< TVecPool< TVal, TSizeTy > >	PVecPool
typedef TVec< TVal, TSizeTy >	TValV

Public Member Functions
	TVecPool (const TSize &ExpectVals=0, const TSize &_GrowBy=1000000, const bool &_FastCopy=false, const TVal &_EmptyVal=TVal())
	Vector pool constructor. More...
	TVecPool (const TVecPool< TVal, TSizeTy > &Pool)
	TVecPool (TSIn &SIn)
	~TVecPool ()
void	Save (TSOut &SOut) const
TVecPool &	operator= (const TVecPool &Pool)
int	GetVecs () const
	Returns the total number of vectors stored in the vector pool. More...
TSize	GetVals () const
	Returns the total number of values stored in the vector pool. More...
bool	IsVId (const int &VId) const
	Tests whether vector of id VId is in the pool. More...
uint64	Reserved () const
	Returns the total capacity of the pool. More...
void	Reserve (const TSize &MxVals)
	Reserves enough capacity for the pool to store MxVals elements. More...
const TVal &	GetEmptyVal () const
	Returns the reference to an empty value. More...
void	SetEmptyVal (const TVal &_EmptyVal)
	Sets the empty value. More...
uint64	GetMemUsed () const
	Returns the total memory footprint (in bytes) of the pool. More...
int	AddV (const TValV &ValV)
	Adds vector ValV to the pool and returns its id. More...
int	AddEmptyV (const int &ValVLen)
	Adds a vector of length ValVLen to the pool and returns its id. More...
int	GetVLen (const int &VId) const
	Returns the number of elements in the vector with id VId. More...
TVal *	GetValVPt (const int &VId) const
	Returns pointer to the first element of the vector with id VId. More...
void	GetV (const int &VId, TValV &ValV) const
	Returns ValV which is a reference (not a copy) to vector with id VId. More...
void	PutV (const int &VId, const TValV &ValV)
	Sets the values of vector VId with those in ValV. More...
void	CompactPool (const TVal &DelVal)
	Deletes all elements of value DelVal from all vectors. More...
void	ShuffleAll (TRnd &Rnd=TInt::Rnd)
	Shuffles the order of all elements in the pool. More...
void	Clr (bool DoDel=true)
	Clears the contents of the pool. More...
void	PutAll (const TVal &Val)
	Sets the values of all elements in the pool to Val. More...

Static Public Member Functions
static PVecPool	New (const TSize &ExpectVals=0, const TSize &GrowBy=1000000, const bool &FastCopy=false)
static PVecPool	Load (TSIn &SIn)
static PVecPool	Load (const TStr &FNm)

Private Member Functions
void	Resize (const TSize &_MxVals)

Private Attributes
TCRef	CRef
TBool	FastCopy
TSize	GrowBy
TSize	MxVals
TSize	Vals
TVal	EmptyVal
TVal *	ValBf
TVec< uint64, int >	IdToOffV

Friends
class	TPt< TVecPool< TVal > >

Detailed Description

template<class TVal, class TSizeTy = int>
class TVecPool< TVal, TSizeTy >

Vector Pool.

Used for storing a large number of small vectors. The pool can store up to 2G different vectors, each with up to 2G elements. Each vector in the pool gets a consecutive integer ID. IDs range 0...GetVecs(). Once a vector is added to the pool, the vector can modify the values of its elements (e.g., be sorted), but the vector is not allowed to change its length — it cannot grow or shrink.

Definition at line 1672 of file ds.h.

Member Typedef Documentation

template<class TVal, class TSizeTy = int>

typedef TPt<TVecPool<TVal, TSizeTy> > TVecPool< TVal, TSizeTy >::PVecPool

Definition at line 1674 of file ds.h.

template<class TVal, class TSizeTy = int>

typedef TVec<TVal, TSizeTy> TVecPool< TVal, TSizeTy >::TValV

Definition at line 1675 of file ds.h.

Constructor & Destructor Documentation

template<class TVal, class TSizeTy >

TVecPool< TVal, TSizeTy >::TVecPool	(	const TSize &	ExpectVals = 0,
		const TSize &	_GrowBy = 1000000,
		const bool &	_FastCopy = false,
		const TVal &	_EmptyVal = TVal()
	)

Vector pool constructor.

Parameters

ExpectVals	At creation the pool allocates enough memory for storing the total of ExpectVals elements (not vectors).
_GrowBy	Whenever the size of the pool needs to be expanded, it will be expanded to be able to store additional _GrowBy elements.
_FastCopy	If true, then vectors are copied using memcpy(), otherwise the assignment operator is used for copying. This option is slower but useful for complex objects where assignment operator is non-trivial.
_EmptyVal	Empty (not yet used) elements in the pool are assigned to this value. By default _EmptyVal = TVal().

Definition at line 1798 of file ds.h.

                                                                                                                             : GrowBy(_GrowBy), MxVals(0), Vals(0), EmptyVal(_EmptyVal), ValBf(NULL) {
  IdToOffV.Add(0);
  Resize(ExpectVals);
}

template<class TVal, class TSizeTy >

TVecPool< TVal, TSizeTy >::TVecPool

(

const TVecPool< TVal, TSizeTy > &

Pool

)

Definition at line 1804 of file ds.h.

                                                      : FastCopy(Pool.FastCopy), GrowBy(Pool.GrowBy), MxVals(Pool.MxVals), Vals(Pool.Vals), EmptyVal(Pool.EmptyVal), IdToOffV(Pool.IdToOffV) {
  try {
    ValBf = new TVal [MxVals]; }
  catch (std::exception Ex) {
    FailR(TStr::Fmt("TVecPool::TVecPool: %s, MxVals: %s. [Program failed to allocate memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(MxVals)).CStr()).CStr()); }
  IAssert(ValBf != NULL);
  if (FastCopy) {
    memcpy(ValBf, Pool.ValBf, MxVals*sizeof(TVal)); }
  else {
    for (TSize ValN = 0; ValN < MxVals; ValN++){ ValBf[ValN] = Pool.ValBf[ValN]; } }
}

template<class TVal, class TSizeTy >

TVecPool< TVal, TSizeTy >::TVecPool

(

TSIn &

SIn

)

Definition at line 1817 of file ds.h.

                                           : FastCopy(SIn) {
  uint64 _GrowBy, _MxVals, _Vals;
  SIn.Load(_GrowBy); SIn.Load(_MxVals);  SIn.Load(_Vals);
  IAssertR(_GrowBy<TSizeMx && _MxVals<TSizeMx && _Vals<TSizeMx, "This is a 64-bit vector pool. Use a 64-bit compiler.");
  GrowBy=TSize(_GrowBy);  MxVals=TSize(_Vals);  Vals=TSize(_Vals); //note MxVals==Vals
  EmptyVal = TVal(SIn);
  if (MxVals==0) { ValBf = NULL; } else { ValBf = new TVal [MxVals]; }
  for (TSize ValN = 0; ValN < Vals; ValN++) { ValBf[ValN] = TVal(SIn); }
  { TInt MxVals(SIn), Vals(SIn);
    IdToOffV.Gen(Vals);
    for (int ValN = 0; ValN < Vals; ValN++) {
      uint64 Offset;  SIn.Load(Offset);  IAssert(Offset < TSizeMx);
      IdToOffV[ValN]=TSize(Offset);
    } }
}

template<class TVal, class TSizeTy = int>

TVecPool< TVal, TSizeTy >::~TVecPool ( )

inline

Definition at line 1695 of file ds.h.

{ if (ValBf != NULL) { delete [] ValBf; } ValBf=NULL; }

Member Function Documentation

template<class TVal , class TSizeTy >

int TVecPool< TVal, TSizeTy >::AddEmptyV

(

const int &

ValVLen

)

Adds a vector of length ValVLen to the pool and returns its id.

Elements of the vector are initialized to EmptyVal.

Definition at line 1880 of file ds.h.

                                                         {
  if (ValVLen==0){return 0;}
  if (MxVals < Vals+ValVLen){Resize(Vals+MAX(TSize(ValVLen), GrowBy)); }
  Vals+=ValVLen; IdToOffV.Add(Vals);
  return IdToOffV.Len()-1;
}

template<class TVal , class TSizeTy >

int TVecPool< TVal, TSizeTy >::AddV

(

const TValV &

ValV

)

Adds vector ValV to the pool and returns its id.

Definition at line 1869 of file ds.h.

                                                   {
  const TSize ValVLen = ValV.Len();
  if (ValVLen == 0) { return 0; }
  if (MxVals < Vals+ValVLen) { Resize(Vals+MAX(ValVLen, GrowBy)); }
  if (FastCopy) { memcpy(ValBf+Vals, ValV.BegI(), sizeof(TVal)*ValV.Len()); }
  else { for (TSize ValN=0; ValN < ValVLen; ValN++) { ValBf[Vals+ValN]=ValV[ValN]; } }
  Vals+=ValVLen;  IdToOffV.Add(Vals);
  return IdToOffV.Len()-1;
}

template<class TVal, class TSizeTy = int>

void TVecPool< TVal, TSizeTy >::Clr ( bool  DoDel = true )

inline

Clears the contents of the pool.

If DoDel=true memory is freed, otherwise all vectors are deleted and all element values in the pool are set to EmptyVal.

Definition at line 1759 of file ds.h.

                              {
    IdToOffV.Clr(DoDel);  MxVals=0;  Vals=0;
    if (DoDel && ValBf!=NULL) { delete [] ValBf; ValBf=NULL;}
    if (! DoDel) { PutAll(EmptyVal); } }

template<class TVal, class TSizeTy >

void TVecPool< TVal, TSizeTy >::CompactPool

(

const TVal &

DelVal

)

Deletes all elements of value DelVal from all vectors.

Empty space is left at the end of the pool.

Definition at line 1889 of file ds.h.

                                                            {
  ::TSize TotalDel=0, NDel=0;
  // printf("Compacting %d vectors\n", IdToOffV.Len());
  for (int vid = 1; vid < IdToOffV.Len(); vid++) {
    // if (vid % 10000000 == 0) { printf(" %dm", vid/1000000);  fflush(stdout); }
    const uint Len = GetVLen(vid);
    TVal* ValV = GetValVPt(vid);
    if (TotalDel > 0) { IdToOffV[vid-1] -= TotalDel; } // update end of vector
    if (Len == 0) { continue; }
    NDel = 0;
    for (TVal* v = ValV; v < ValV+Len-NDel; v++) {
      if (*v == DelVal) {
        TVal* Beg = v;
        while (*v == DelVal && v < ValV+Len) { v++; NDel++; }
        memcpy(Beg, v, sizeof(TVal)*int(Len - ::TSize(v - ValV)));
        v -= NDel;
      }
    }
    memcpy(ValV-TotalDel, ValV, sizeof(TVal)*Len);  // move data
    TotalDel += NDel;
  }
  IdToOffV.Last() -= TotalDel;
  for (::TSize i = Vals-TotalDel; i < Vals; i++) { ValBf[i] = EmptyVal; }
  Vals -= TotalDel;
  // printf("  deleted %llu elements from the pool\n", TotalDel);
}

template<class TVal, class TSizeTy = int>

const TVal& TVecPool< TVal, TSizeTy >::GetEmptyVal ( ) const

inline

Returns the reference to an empty value.

Definition at line 1714 of file ds.h.

{ return EmptyVal; }

template<class TVal, class TSizeTy = int>

uint64 TVecPool< TVal, TSizeTy >::GetMemUsed ( ) const

inline

Returns the total memory footprint (in bytes) of the pool.

Definition at line 1718 of file ds.h.

                            {
    return sizeof(TCRef)+sizeof(TBool)+3*sizeof(TSize)+sizeof(TVal*)+MxVals*sizeof(TVal);}

template<class TVal, class TSizeTy = int>

void TVecPool< TVal, TSizeTy >::GetV ( const int &  VId, TValV &  ValV  ) const

inline

Returns ValV which is a reference (not a copy) to vector with id VId.

No data is copied. Elements of the vector ValV can be modified but the vector cannot change its size.

Definition at line 1736 of file ds.h.

                                               {
    if (GetVLen(VId)==0){ValV.Clr();}
    else { ValV.GenExt(GetValVPt(VId), GetVLen(VId)); } }

template<class TVal, class TSizeTy = int>

TSize TVecPool< TVal, TSizeTy >::GetVals ( ) const

inline

Returns the total number of values stored in the vector pool.

Definition at line 1706 of file ds.h.

{ return Vals; }

template<class TVal, class TSizeTy = int>

TVal* TVecPool< TVal, TSizeTy >::GetValVPt ( const int &  VId ) const

inline

Returns pointer to the first element of the vector with id VId.

Definition at line 1730 of file ds.h.

                                        {
    if (GetVLen(VId)==0){return (TVal*)&EmptyVal;}
    else {return ValBf+IdToOffV[VId-1];}}

template<class TVal, class TSizeTy = int>

int TVecPool< TVal, TSizeTy >::GetVecs ( ) const

inline

Returns the total number of vectors stored in the vector pool.

Definition at line 1704 of file ds.h.

{ return IdToOffV.Len(); }

template<class TVal, class TSizeTy = int>

int TVecPool< TVal, TSizeTy >::GetVLen ( const int &  VId ) const

inline

Returns the number of elements in the vector with id VId.

Definition at line 1728 of file ds.h.

{ if (VId==0){return 0;} else {return int(IdToOffV[VId]-IdToOffV[VId-1]);}}

template<class TVal, class TSizeTy = int>

bool TVecPool< TVal, TSizeTy >::IsVId ( const int &  VId ) const

inline

Tests whether vector of id VId is in the pool.

Definition at line 1708 of file ds.h.

{ return (0 <= VId) && (VId < IdToOffV.Len()); }

template<class TVal, class TSizeTy = int>

static PVecPool TVecPool< TVal, TSizeTy >::Load ( TSIn &  SIn )

inlinestatic

Definition at line 1698 of file ds.h.

{ return new TVecPool(SIn); }

template<class TVal, class TSizeTy = int>

static PVecPool TVecPool< TVal, TSizeTy >::Load ( const TStr &  FNm )

inlinestatic

Definition at line 1699 of file ds.h.

{ TFIn FIn(FNm); return Load(FIn); }

template<class TVal, class TSizeTy = int>

static PVecPool TVecPool< TVal, TSizeTy >::New ( const TSize &  ExpectVals = 0, const TSize &  GrowBy = 1000000, const bool &  FastCopy = false  )

inlinestatic

Definition at line 1696 of file ds.h.

                                                                                                          {
    return new TVecPool(ExpectVals, GrowBy, FastCopy); }

template<class TVal , class TSizeTy >

TVecPool< TVal, TSizeTy > & TVecPool< TVal, TSizeTy >::operator=

(

const TVecPool< TVal, TSizeTy > &

Pool

)

Definition at line 1847 of file ds.h.

                                                                                  {
  if (this!=&Pool) {
    FastCopy = Pool.FastCopy;
    GrowBy = Pool.GrowBy;
    MxVals = Pool.MxVals;
    Vals = Pool.Vals;
    EmptyVal = Pool.EmptyVal;
    IdToOffV=Pool.IdToOffV;
    try {
      ValBf = new TVal [MxVals]; }
    catch (std::exception Ex) {
      FailR(TStr::Fmt("TVecPool::operator=: %s, MxVals: %s. [Program failed to allocate memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(MxVals)).CStr()).CStr()); }
    IAssert(ValBf != NULL);
    if (FastCopy) {
      memcpy(ValBf, Pool.ValBf, Vals*sizeof(TVal)); }
    else {
      for (TSize ValN = 0; ValN < Vals; ValN++){ ValBf[ValN] = Pool.ValBf[ValN]; } }
  }
  return *this;
}

template<class TVal, class TSizeTy = int>

void TVecPool< TVal, TSizeTy >::PutAll ( const TVal &  Val )

inline

Sets the values of all elements in the pool to Val.

Definition at line 1764 of file ds.h.

                               {
    for (TSize ValN = 0; ValN < MxVals; ValN++) { ValBf[ValN]=Val; } }

template<class TVal, class TSizeTy = int>

void TVecPool< TVal, TSizeTy >::PutV ( const int &  VId, const TValV &  ValV  )

inline

Sets the values of vector VId with those in ValV.

Definition at line 1740 of file ds.h.

                                               {
    IAssert(IsVId(VId) && GetVLen(VId) == ValV.Len());
    if (FastCopy) {
      memcpy(GetValVPt(VId), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
    else { TVal* ValPt = GetValVPt(VId);
      for (::TSize ValN=0; ValN < ::TSize(ValV.Len()); ValN++, ValPt++) { *ValPt=ValV[ValN]; }
    } }

template<class TVal, class TSizeTy = int>

void TVecPool< TVal, TSizeTy >::Reserve ( const TSize &  MxVals )

inline

Reserves enough capacity for the pool to store MxVals elements.

Definition at line 1712 of file ds.h.

{ Resize(MxVals); }

template<class TVal, class TSizeTy = int>

uint64 TVecPool< TVal, TSizeTy >::Reserved ( ) const

inline

Returns the total capacity of the pool.

Definition at line 1710 of file ds.h.

{ return MxVals; }

template<class TVal , class TSizeTy >

void TVecPool< TVal, TSizeTy >::Resize ( const TSize &  _MxVals )

private

Definition at line 1770 of file ds.h.

                                                        {
  if (_MxVals <= MxVals){ return; } else { MxVals = _MxVals; }
  if (ValBf == NULL) {
    try { ValBf = new TVal [MxVals]; }
    catch (std::exception Ex) {
      FailR(TStr::Fmt("TVecPool::Resize 1: %s, MxVals: %s. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(_MxVals)).CStr()).CStr()); }
    IAssert(ValBf != NULL);
    if (EmptyVal != TVal()) { PutAll(EmptyVal); }
  } else {
    // printf("*** Resize vector pool: %llu -> %llu\n", uint64(Vals), uint64(MxVals));
    TVal* NewValBf = NULL;
    try { NewValBf = new TVal [MxVals]; }
    catch (std::exception Ex) {
      FailR(TStr::Fmt("TVecPool::Resize 1: %s, MxVals: %s. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(_MxVals)).CStr()).CStr()); }
    IAssert(NewValBf != NULL);
    if (FastCopy) {
      memcpy(NewValBf, ValBf, Vals*sizeof(TVal)); }
    else {
      for (TSize ValN = 0; ValN < Vals; ValN++){ NewValBf[ValN] = ValBf[ValN]; } }
    if (EmptyVal != TVal()) { // init empty values
      for (TSize ValN = Vals; ValN < MxVals; ValN++) { NewValBf[ValN] = EmptyVal; }
    }
    delete [] ValBf;
    ValBf = NewValBf;
  }
}

template<class TVal , class TSizeTy >

void TVecPool< TVal, TSizeTy >::Save

(

TSOut &

SOut

)

const

Definition at line 1834 of file ds.h.

                                                    {
  SOut.Save(FastCopy);
  uint64 _GrowBy=GrowBy, _MxVals=MxVals, _Vals=Vals;
  SOut.Save(_GrowBy); SOut.Save(_MxVals);  SOut.Save(_Vals);
  SOut.Save(EmptyVal);
  for (TSize ValN = 0; ValN < Vals; ValN++) { ValBf[ValN].Save(SOut); }
  { SOut.Save(IdToOffV.Len());  SOut.Save(IdToOffV.Len());
    for (int ValN = 0; ValN < IdToOffV.Len(); ValN++) {
      const uint64 Offset=IdToOffV[ValN];  SOut.Save(Offset);
    } }
}

template<class TVal, class TSizeTy = int>

void TVecPool< TVal, TSizeTy >::SetEmptyVal ( const TVal &  _EmptyVal )

inline

Sets the empty value.

Definition at line 1716 of file ds.h.

{ EmptyVal = _EmptyVal; }

template<class TVal , class TSizeTy >

void TVecPool< TVal, TSizeTy >::ShuffleAll

(

TRnd &

Rnd = TInt::Rnd

)

Shuffles the order of all elements in the pool.

It does not respect vector boundaries!

Definition at line 1918 of file ds.h.

                                                  {
  for (::TSize n = Vals-1; n > 0; n--) {
    const ::TSize k = ::TSize(((uint64(Rnd.GetUniDevInt())<<32) | uint64(Rnd.GetUniDevInt())) % (n+1));
    const TVal Tmp = ValBf[n];
    ValBf[n] = ValBf[k];
    ValBf[k] = Tmp;
  }
}

Friends And Related Function Documentation

template<class TVal, class TSizeTy = int>

friend class TPt< TVecPool< TVal > >

friend

Definition at line 1766 of file ds.h.

Member Data Documentation

template<class TVal, class TSizeTy = int>

TCRef TVecPool< TVal, TSizeTy >::CRef

private

Definition at line 1677 of file ds.h.

template<class TVal, class TSizeTy = int>

TVal TVecPool< TVal, TSizeTy >::EmptyVal

private

Definition at line 1680 of file ds.h.

template<class TVal, class TSizeTy = int>

TBool TVecPool< TVal, TSizeTy >::FastCopy

private

Definition at line 1678 of file ds.h.

template<class TVal, class TSizeTy = int>

TSize TVecPool< TVal, TSizeTy >::GrowBy

private

Definition at line 1679 of file ds.h.

template<class TVal, class TSizeTy = int>

TVec<uint64, int> TVecPool< TVal, TSizeTy >::IdToOffV

private

Definition at line 1682 of file ds.h.

template<class TVal, class TSizeTy = int>

TSize TVecPool< TVal, TSizeTy >::MxVals

private

Definition at line 1679 of file ds.h.

template<class TVal, class TSizeTy = int>

TVal* TVecPool< TVal, TSizeTy >::ValBf

private

Definition at line 1681 of file ds.h.

template<class TVal, class TSizeTy = int>

TSize TVecPool< TVal, TSizeTy >::Vals

private

Definition at line 1679 of file ds.h.

---

The documentation for this class was generated from the following file:

• glib-core/ds.h