|
SNAP Library 2.1, User 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, User 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(). |
| TVecPool< TVal, TSizeTy >::TVecPool | ( | const TVecPool< TVal, TSizeTy > & | Pool | ) |
Definition at line 2674 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]; } } }
Definition at line 2687 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); } } }
| 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.
Adds vector ValV to the pool and returns its id.
Definition at line 2739 of file ds.h.
{
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.
| 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] |
| TVecPool< TVal, TSizeTy > & TVecPool< TVal, TSizeTy >::operator= | ( | const TVecPool< TVal, TSizeTy > & | Pool | ) |
Definition at line 2717 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;
}
| 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.
{
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.
{
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.
{
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;
}
}
1.8.0