TSparseGroup< TVal, GroupSize > Class Template Reference

#include <shash.h>

Public Member Functions
	TSparseGroup ()
	TSparseGroup (TSIn &SIn)
	TSparseGroup (const TSparseGroup &SG)
	~TSparseGroup ()
void	Load (TSIn &SIn)
void	Save (TSOut &SOut) const
TSparseGroup &	operator= (const TSparseGroup &SG)
bool	operator== (const TSparseGroup &SG) const
bool	operator< (const TSparseGroup &SG) const
int	Len () const
int	MxLen () const
int	Reserved () const
bool	Empty () const
void	Clr (const bool &DoDel=true)
int	GetGroupSize () const
uint	GetDiskSz () const
bool	IsEmpty (const int &ValN) const
const TVal &	Offset (const int &Pos) const
TVal &	Offset (const int &Pos)
int	OffsetToPos (int Offset) const
int	PosToOffset (int Pos) const
const TVal &	DefVal () const
const TVal &	Get (const int &ValN) const
const TVal &	operator[] (const int ValN) const
TVal &	Set (const int &ValN, const TVal &Val)
TVal &	Set (const int &ValN)
void	Del (const int &ValN)

Private Member Functions
bool	BMTest (const int &ValN) const
void	BMSet (const int &ValN)
void	BMClear (const int &ValN)

Static Private Member Functions
static int	CharBit (const int &ValN)
static int	ModBit (const int &ValN)
static int	PosToOffset (const unsigned char *BitSet, int Pos)

Private Attributes
unsigned char	BitSet [(GroupSize-1)/8+1]
uint16	Buckets
TVal *	Group

Detailed Description

template<class TVal, uint16 GroupSize>
class TSparseGroup< TVal, GroupSize >

Definition at line 61 of file shash.h.

Constructor & Destructor Documentation

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::TSparseGroup ( )

inline

Definition at line 74 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet.

: Buckets(0), Group(NULL) { memset(BitSet, 0, sizeof(BitSet)); }

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::TSparseGroup ( TSIn &  SIn )

inline

Definition at line 75 of file shash.h.

References TSparseGroup< TVal, GroupSize >::Load().

: Buckets(0), Group(NULL) { Load(SIn); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::TSparseGroup

(

const TSparseGroup< TVal, GroupSize > &

SG

)

Definition at line 141 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

                                                                  : Buckets(SG.Buckets), Group(NULL) {
  memcpy(BitSet, SG.BitSet, sizeof(BitSet));
  if (Buckets > 0) {
    Group = new TVal [Buckets];
    for (int b = 0; b < Buckets; b++) { Group[b] = SG.Group[b]; }
  }
}

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::~TSparseGroup ( )

inline

Definition at line 77 of file shash.h.

References TSparseGroup< TVal, GroupSize >::Group.

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

Member Function Documentation

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::BMClear ( const int &  ValN )

inlineprivate

Definition at line 71 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::CharBit(), and TSparseGroup< TVal, GroupSize >::ModBit().

{ BitSet[CharBit(ValN)] &= ~ModBit(ValN); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::BMSet ( const int &  ValN )

inlineprivate

Definition at line 70 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::CharBit(), and TSparseGroup< TVal, GroupSize >::ModBit().

{ BitSet[CharBit(ValN)] |= ModBit(ValN); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::BMTest ( const int &  ValN ) const

inlineprivate

Definition at line 69 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::CharBit(), and TSparseGroup< TVal, GroupSize >::ModBit().

Referenced by TSparseGroup< TVal, GroupSize >::Get(), TSparseGroup< TVal, GroupSize >::IsEmpty(), and TSparseGroup< TVal, GroupSize >::Set().

{ return (BitSet[CharBit(ValN)] & ModBit(ValN)) != 0; }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

static int TSparseGroup< TVal, GroupSize >::CharBit ( const int &  ValN )

inlinestaticprivate

Definition at line 67 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::BMClear(), TSparseGroup< TVal, GroupSize >::BMSet(), and TSparseGroup< TVal, GroupSize >::BMTest().

{ return ValN >> 3; }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Clr

(

const bool &

DoDel = true

)

Definition at line 221 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::MoveFrom().

                                                         {
  if (DoDel && Group != NULL) {
    delete [] Group;
    Group = 0;
  }
  memset(BitSet, 0, sizeof(BitSet));
  Buckets = 0;
}

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::DefVal ( ) const

inline

Definition at line 99 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Get(), and TSparseGroup< TVal, GroupSize >::Set().

{ static TVal DefValue = TVal();  return DefValue; }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Del

(

const int &

ValN

)

Definition at line 247 of file shash.h.

Referenced by TSparseTable< TVal, GroupSize >::Del().

                                                       {
  if (BMTest(ValN)) {
    const int Offset = PosToOffset(BitSet, ValN);
    if (--Buckets == 0) {
      delete [] Group;
      Group = 0;
    } else {
      const TVal *OldGroup = Group;
      Group = new TVal [Buckets];
      for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
      for (int b = Offset+1; b <= Buckets; b++) Group[b-1] = OldGroup[b];
      if (OldGroup != NULL) delete [] OldGroup;
    }
    BMClear(ValN);
  }
}

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::Empty ( ) const

inline

Definition at line 88 of file shash.h.

{ return Buckets == 0; }

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::Get ( const int &  ValN ) const

inline

Definition at line 100 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::BMTest(), TSparseGroup< TVal, GroupSize >::DefVal(), and TSparseGroup< TVal, GroupSize >::PosToOffset().

Referenced by TSparseGroup< TVal, GroupSize >::operator[]().

                                         {
    if (BMTest(ValN)) return Group[PosToOffset(BitSet, ValN)]; else return DefVal(); }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

uint TSparseGroup< TVal, GroupSize >::GetDiskSz ( ) const

inline

Definition at line 91 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet.

{ return sizeof(BitSet) + sizeof(uint16) + Buckets*sizeof(TVal); }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::GetGroupSize ( ) const

inline

Definition at line 90 of file shash.h.

{ return GroupSize; }

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::IsEmpty ( const int &  ValN ) const

inline

Definition at line 93 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BMTest().

{ return ! BMTest(ValN); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::Len ( ) const

inline

Definition at line 85 of file shash.h.

References TSparseGroup< TVal, GroupSize >::Buckets.

Referenced by TSparseHash< TKey, TDat, GroupSize >::CopyFrom(), TSparseTable< TVal, GroupSize >::Del(), TSparseHash< TKey, TDat, GroupSize >::MoveFrom(), and TSparseTable< TVal, GroupSize >::Set().

{ return Buckets; }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Load

(

TSIn &

SIn

)

Definition at line 150 of file shash.h.

References TSIn::Load(), and TSIn::LoadBf().

Referenced by TSparseGroup< TVal, GroupSize >::TSparseGroup().

                                                  {
  SIn.LoadBf(BitSet, sizeof(BitSet));
  SIn.Load(Buckets);
  if (Group != NULL) delete [] Group;
  Group = new TVal [Buckets];
  for (int b = 0; b < Buckets; b++) { Group[b] = TVal(SIn); }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

static int TSparseGroup< TVal, GroupSize >::ModBit ( const int &  ValN )

inlinestaticprivate

Definition at line 68 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::BMClear(), TSparseGroup< TVal, GroupSize >::BMSet(), and TSparseGroup< TVal, GroupSize >::BMTest().

{ return 1 << (ValN&7); }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::MxLen ( ) const

inline

Definition at line 86 of file shash.h.

{ return GroupSize; }

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::Offset ( const int &  Pos ) const

inline

Definition at line 94 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::CopyFrom(), and TSparseHash< TKey, TDat, GroupSize >::MoveFrom().

{ return Group[Pos]; }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

TVal& TSparseGroup< TVal, GroupSize >::Offset ( const int &  Pos )

inline

Definition at line 95 of file shash.h.

{ return Group[Pos]; }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::OffsetToPos

(

int

Offset

)

const

Definition at line 206 of file shash.h.

References Assert, Fail, and TB1Def::GetBit().

                                                               {
  Assert(Offset < Buckets);
  for (int i = 0; i < sizeof(BitSet); i++) {
    for (int b = 0; b < 8; b++) {
      if (TB1Def::GetBit(b, BitSet[i])) {
        if (Offset == 0) return i*8 + b;
        Offset--;
      }
    }
  }
  Fail;
  return -1;
}

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::operator<

(

const TSparseGroup< TVal, GroupSize > &

SG

)

const

Definition at line 196 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

                                                                            {
  if (Buckets < SG.Buckets) return true;
  if (memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == -1) return true;
  for (int b = 0; b < Buckets; b++) {
    if (Group[b] < SG.Group[b]) return true;
  }
  return false;
}

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize > & TSparseGroup< TVal, GroupSize >::operator=

(

const TSparseGroup< TVal, GroupSize > &

SG

)

Definition at line 166 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

                                                                                                {
  if (this != &SG) {
    if (SG.Buckets == 0 && Group != NULL) {
      delete [] Group;
      Group = 0;
    } else {
      if (Buckets != SG.Buckets) {
        if (Group != NULL) delete [] Group;
        Group = new TVal [SG.Buckets];
      }
      for (int b = 0; b < SG.Buckets; b++) { Group[b] = SG.Group[b]; }
    }
    Buckets = SG.Buckets;
    memcpy(BitSet, SG.BitSet, sizeof(BitSet));
  }
  return *this;
}

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::operator==

(

const TSparseGroup< TVal, GroupSize > &

SG

)

const

Definition at line 185 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

                                                                             {
  if (Buckets == SG.Buckets && memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == 0) {
    for (int b = 0; b < Buckets; b++) {
      if (Group[b] != SG.Group[b]) return false;
    }
    return true;
  }
  return false;
}

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::operator[] ( const int  ValN ) const

inline

Definition at line 102 of file shash.h.

References TSparseGroup< TVal, GroupSize >::Get().

{ return Get(ValN); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::PosToOffset ( const unsigned char *  BitSet, int  Pos  )

staticprivate

Definition at line 113 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Get(), and TSparseGroup< TVal, GroupSize >::Set().

                                                                                   {
  static const int bits_in [256] = {      // # of bits set in one char
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  };
  // [Note: condition pos > 8 is an optimization; convince yourself we
  // give exactly the same result as if we had pos >= 8 here instead.]
  int Offset = 0;
  for ( ; Pos > 8; Pos -= 8 )                        // bm[0..pos/8-1]
    Offset += bits_in[*BitSet++];                    // chars we want *all* bits in
  return Offset + bits_in[*BitSet & ((1 << Pos)-1)]; // the char that includes pos
}

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::PosToOffset ( int  Pos ) const

inline

Definition at line 97 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, and TSparseGroup< TVal, GroupSize >::PosToOffset().

Referenced by TSparseGroup< TVal, GroupSize >::PosToOffset().

{ return PosToOffset(BitSet, Pos); }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::Reserved ( ) const

inline

Definition at line 87 of file shash.h.

{ return GroupSize; }

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Save

(

TSOut &

SOut

)

const

Definition at line 159 of file shash.h.

References TSOut::Save(), and TSOut::SaveBf().

                                                          {
  SOut.SaveBf(BitSet, sizeof(BitSet));
  SOut.Save(Buckets);
  for (int b = 0; b < Buckets; b++) { Group[b].Save(SOut); }
}

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>

TVal & TSparseGroup< TVal, GroupSize >::Set	(	const int &	ValN,
		const TVal &	Val
	)

Definition at line 231 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Set(), and TSparseTable< TVal, GroupSize >::Set().

                                                                         {
  const int Offset = PosToOffset(BitSet, ValN);
  if (! BMTest(ValN)) {
    const TVal *OldGroup = Group;
    Group = new TVal [Buckets+1];
    for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
    for (int b = Offset+1; b <= Buckets; b++) Group[b] = OldGroup[b-1];
    if (OldGroup != NULL) delete [] OldGroup;
    Buckets++;
    BMSet(ValN);
  }
  Group[Offset] = Val;
  return Group[Offset];
}

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>

TVal& TSparseGroup< TVal, GroupSize >::Set ( const int &  ValN )

inline

Definition at line 105 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::BMTest(), TSparseGroup< TVal, GroupSize >::DefVal(), TSparseGroup< TVal, GroupSize >::PosToOffset(), and TSparseGroup< TVal, GroupSize >::Set().

                             {
    if (! BMTest(ValN)) Set(ValN, DefVal());
    return Group[PosToOffset(BitSet, ValN)];
  }

Here is the call graph for this function:

Member Data Documentation

template<class TVal , uint16 GroupSize>

unsigned char TSparseGroup< TVal, GroupSize >::BitSet[(GroupSize-1)/8+1]

private

Definition at line 63 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::BMClear(), TSparseGroup< TVal, GroupSize >::BMSet(), TSparseGroup< TVal, GroupSize >::BMTest(), TSparseGroup< TVal, GroupSize >::Get(), TSparseGroup< TVal, GroupSize >::GetDiskSz(), TSparseGroup< TVal, GroupSize >::operator<(), TSparseGroup< TVal, GroupSize >::operator=(), TSparseGroup< TVal, GroupSize >::operator==(), TSparseGroup< TVal, GroupSize >::PosToOffset(), TSparseGroup< TVal, GroupSize >::Set(), and TSparseGroup< TVal, GroupSize >::TSparseGroup().

template<class TVal , uint16 GroupSize>

uint16 TSparseGroup< TVal, GroupSize >::Buckets

private

Definition at line 64 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Len(), TSparseGroup< TVal, GroupSize >::operator<(), TSparseGroup< TVal, GroupSize >::operator=(), TSparseGroup< TVal, GroupSize >::operator==(), and TSparseGroup< TVal, GroupSize >::TSparseGroup().

template<class TVal , uint16 GroupSize>

TVal* TSparseGroup< TVal, GroupSize >::Group

private

Definition at line 65 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::operator<(), TSparseGroup< TVal, GroupSize >::operator=(), TSparseGroup< TVal, GroupSize >::operator==(), TSparseGroup< TVal, GroupSize >::TSparseGroup(), and TSparseGroup< TVal, GroupSize >::~TSparseGroup().

---

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

• glib-core/shash.h