|
SNAP Library 2.1, Developer Reference
2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
|
SNAP Library 2.1, Developer Reference
2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
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. | |
| 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. | |
| TSize | GetVals () const |
| Returns the total number of values stored in the vector pool. | |
| bool | IsVId (const int &VId) const |
Tests whether vector of id VId is in the pool. | |
| uint64 | Reserved () const |
| Returns the total capacity of the pool. | |
| void | Reserve (const TSize &MxVals) |
Reserves enough capacity for the pool to store MxVals elements. | |
| const TVal & | GetEmptyVal () const |
| Returns the reference to an empty value. | |
| void | SetEmptyVal (const TVal &_EmptyVal) |
| Sets the empty value. | |
| uint64 | GetMemUsed () const |
| Returns the total memory footprint (in bytes) of the pool. | |
| int | AddV (const TValV &ValV) |
Adds vector ValV to the pool and returns its id. | |
| int | AddEmptyV (const int &ValVLen) |
Adds a vector of length ValVLen to the pool and returns its id. | |
| int | GetVLen (const int &VId) const |
Returns the number of elements in the vector with id VId. | |
| TVal * | GetValVPt (const int &VId) const |
Returns pointer to the first element of the vector with id VId. | |
| void | GetV (const int &VId, TValV &ValV) const |
Returns ValV which is a reference (not a copy) to vector with id VId. | |
| void | PutV (const int &VId, const TValV &ValV) |
Sets the values of vector VId with those in ValV. | |
| void | CompactPool (const TVal &DelVal) |
Deletes all elements of value DelVal from all vectors. | |
| void | ShuffleAll (TRnd &Rnd=TInt::Rnd) |
| Shuffles the order of all elements in the pool. | |
| void | Clr (bool DoDel=true) |
| Clears the contents of the pool. | |
| void | PutAll (const TVal &Val) |
Sets the values of all elements in the pool to Val. | |
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 > > |
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.
| TVecPool< TVal, TSizeTy >::TVecPool | ( | const TSize & | ExpectVals = 0, |
| const TSize & | _GrowBy = 1000000, |
||
| const bool & | _FastCopy = false, |
||
| const TVal & | _EmptyVal = TVal() |
||
| ) |
Vector pool constructor.
| 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 2668 of file ds.h.
References TVec< TVal, TSizeTy >::Add(), TVecPool< TVal, TSizeTy >::IdToOffV, and TVecPool< TVal, TSizeTy >::Resize().
Referenced by TVecPool< TInt >::Load(), and TVecPool< TInt >::New().
: GrowBy(_GrowBy), MxVals(0), Vals(0), EmptyVal(_EmptyVal), ValBf(NULL) { IdToOffV.Add(0); Resize(ExpectVals); }
| TVecPool< TVal, TSizeTy >::TVecPool | ( | const TVecPool< TVal, TSizeTy > & | Pool | ) |
Definition at line 2674 of file ds.h.
References TStr::CStr(), FailR, TVecPool< TVal, TSizeTy >::FastCopy, TStr::Fmt(), TInt::GetStr(), IAssert, TVecPool< TVal, TSizeTy >::MxVals, and TVecPool< TVal, TSizeTy >::ValBf.
: 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]; } } }
Definition at line 2687 of file ds.h.
References TVecPool< TVal, TSizeTy >::EmptyVal, TVec< TVal, TSizeTy >::Gen(), TVecPool< TVal, TSizeTy >::GrowBy, IAssert, IAssertR, TVecPool< TVal, TSizeTy >::IdToOffV, TSIn::Load(), TVecPool< TVal, TSizeTy >::MxVals, TSizeMx, TVecPool< TVal, TSizeTy >::ValBf, and TVecPool< TVal, TSizeTy >::Vals.
: 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); } } }
| int TVecPool< TVal, TSizeTy >::AddEmptyV | ( | const int & | ValVLen | ) |
Adds vector ValV to the pool and returns its id.
Definition at line 2739 of file ds.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::BegI(), TVec< TVal, TSizeTy >::Len(), and max.
{
const TSizeTy 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 (uint ValN=0; ValN < ValVLen; ValN++) { ValBf[Vals+ValN]=ValV[ValN]; } }
Vals+=ValVLen; IdToOffV.Add(Vals);
return IdToOffV.Len()-1;
}
| 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 2629 of file ds.h.
Referenced by TBigNet< TNodeData, IsDir >::Clr().
{
IdToOffV.Clr(DoDel); MxVals=0; Vals=0;
if (DoDel && ValBf!=NULL) { delete [] ValBf; ValBf=NULL;}
if (! DoDel) { PutAll(EmptyVal); } }
| 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 2759 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);
}
| const TVal& TVecPool< TVal, TSizeTy >::GetEmptyVal | ( | ) | const [inline] |
| uint64 TVecPool< TVal, TSizeTy >::GetMemUsed | ( | ) | const [inline] |
| TSize TVecPool< TVal, TSizeTy >::GetVals | ( | ) | const [inline] |
Returns the total number of values stored in the vector pool.
Definition at line 2576 of file ds.h.
Referenced by TBigNet< TNodeData, IsDir >::GetEdges().
{ return Vals; }
| 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 2600 of file ds.h.
Referenced by TUNGraph::AddNode(), TNGraph::AddNode(), TBigNet< TNodeData, IsDir >::GetInNIdVPt(), TBigNet< TNodeData, IsDir >::TNodeI::GetInOutNIdV(), TBigNet< TNodeData, IsDir >::GetOutNIdVPt(), TVecPool< TInt >::GetV(), and TVecPool< TInt >::PutV().
| int TVecPool< TVal, TSizeTy >::GetVLen | ( | const int & | VId | ) | const [inline] |
Returns the number of elements in the vector with id VId.
Definition at line 2598 of file ds.h.
Referenced by TUNGraph::AddNode(), TNGraph::AddNode(), TBigNet< TNodeData, IsDir >::TNodeI::GetInOutNIdV(), TVecPool< TInt >::GetV(), TVecPool< TInt >::GetValVPt(), and TVecPool< TInt >::PutV().
| bool TVecPool< TVal, TSizeTy >::IsVId | ( | const int & | VId | ) | const [inline] |
Tests whether vector of id VId is in the pool.
Definition at line 2578 of file ds.h.
Referenced by TBigNet< TNodeData, IsDir >::TNodeI::GetInOutNIdV(), and TVecPool< TInt >::PutV().
| static PVecPool TVecPool< TVal, TSizeTy >::Load | ( | const TStr & | FNm | ) | [inline, static] |
Definition at line 2569 of file ds.h.
Referenced by TVecPool< TInt >::Load().
| TVecPool< TVal, TSizeTy > & TVecPool< TVal, TSizeTy >::operator= | ( | const TVecPool< TVal, TSizeTy > & | Pool | ) |
Definition at line 2717 of file ds.h.
References TStr::CStr(), TVecPool< TVal, TSizeTy >::EmptyVal, FailR, TVecPool< TVal, TSizeTy >::FastCopy, TStr::Fmt(), TInt::GetStr(), TVecPool< TVal, TSizeTy >::GrowBy, IAssert, TVecPool< TVal, TSizeTy >::IdToOffV, TVecPool< TVal, TSizeTy >::MxVals, TVecPool< TVal, TSizeTy >::ValBf, and TVecPool< TVal, TSizeTy >::Vals.
{
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;
}
| void TVecPool< TVal, TSizeTy >::PutV | ( | const int & | VId, |
| const TValV & | ValV | ||
| ) | [inline] |
Sets the values of vector VId with those in ValV.
| void TVecPool< TVal, TSizeTy >::Resize | ( | const TSize & | _MxVals | ) | [private] |
Definition at line 2640 of file ds.h.
References TStr::CStr(), FailR, TStr::Fmt(), TInt::GetStr(), and IAssert.
Referenced by TVecPool< TInt >::Reserve(), and TVecPool< TVal, TSizeTy >::TVecPool().
{
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;
}
}
Definition at line 2704 of file ds.h.
References TSOut::Save().
Referenced by TBigNet< TNodeData, IsDir >::SaveToDisk().
{
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);
} }
}
| void TVecPool< TVal, TSizeTy >::SetEmptyVal | ( | const TVal & | _EmptyVal | ) | [inline] |
| 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 2788 of file ds.h.
References TRnd::GetUniDevInt().
{
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;
}
}
Definition at line 2550 of file ds.h.
Referenced by TVecPool< TInt >::Clr(), TVecPool< TInt >::GetEmptyVal(), TVecPool< TInt >::GetValVPt(), TVecPool< TVal, TSizeTy >::operator=(), TVecPool< TInt >::SetEmptyVal(), and TVecPool< TVal, TSizeTy >::TVecPool().
Definition at line 2548 of file ds.h.
Referenced by TVecPool< TInt >::New(), TVecPool< TVal, TSizeTy >::operator=(), TVecPool< TInt >::PutV(), and TVecPool< TVal, TSizeTy >::TVecPool().
Definition at line 2549 of file ds.h.
Referenced by TVecPool< TInt >::New(), TVecPool< TVal, TSizeTy >::operator=(), and TVecPool< TVal, TSizeTy >::TVecPool().
TVec<uint64, int> TVecPool< TVal, TSizeTy >::IdToOffV [private] |
Definition at line 2552 of file ds.h.
Referenced by TVecPool< TInt >::Clr(), TVecPool< TInt >::GetValVPt(), TVecPool< TInt >::GetVecs(), TVecPool< TInt >::GetVLen(), TVecPool< TInt >::IsVId(), TVecPool< TVal, TSizeTy >::operator=(), and TVecPool< TVal, TSizeTy >::TVecPool().
Definition at line 2549 of file ds.h.
Referenced by TVecPool< TInt >::Clr(), TVecPool< TInt >::GetMemUsed(), TVecPool< TVal, TSizeTy >::operator=(), TVecPool< TInt >::PutAll(), TVecPool< TInt >::Reserved(), and TVecPool< TVal, TSizeTy >::TVecPool().
Definition at line 2551 of file ds.h.
Referenced by TVecPool< TInt >::Clr(), TVecPool< TInt >::GetValVPt(), TVecPool< TVal, TSizeTy >::operator=(), TVecPool< TInt >::PutAll(), TVecPool< TVal, TSizeTy >::TVecPool(), and TVecPool< TInt >::~TVecPool().
Definition at line 2549 of file ds.h.
Referenced by TVecPool< TInt >::Clr(), TVecPool< TInt >::GetVals(), TVecPool< TVal, TSizeTy >::operator=(), and TVecPool< TVal, TSizeTy >::TVecPool().
1.8.0