Fennel: LcsHashTable Class Reference (original) (raw)

LcsHashTable implements a hash table that fits the hash entries and the overflow nodes into one scratch buffer of size hashBlockSize. More...

#include <[LcsHash.h](LcsHash%5F8h-source.html)>

List of all members.

Public Member Functions
LcsHashTable ()
void init (PBuffer hashBlockInit, uint hashBlockSizeInit)
Sets up fields in LcsHashTable.
void resetHash ()
Resets the hash table to prepare for encoding the next page.
void resetBatch ()
Resets the entries present in the current batch to prepare for encoding the next batch.
uint numHashEntries ()
Returns the hash table size.
LcsHashValueNode * getNewValueNode ()
Gives out the next hash value node for the caller to fill in interesting information.
void insertNewValueNode (uint key, LcsHashValueNode *newNode)
Inserts a new node into the overflow chain.
void undoNewValueNode (uint key)
Undoes the most recent insert.
LcsHashValueNode * getFirstValueNode (uint key)
Returns the first value node having a certain key value.
LcsHashValueNode * getNextValueNode (LcsHashValueNode *pValueNode)
Returns the next value node following a value node.
bool isFull (uint leftOvers=0)
Checks if hash table is full.
Public Attributes
uint16_t * entry
Array indexed by the hash key value.
LcsHashValueNode * valueNodes
List of hash value nodes.
Private Attributes
PBuffer hashBlock
Buffer to fit the hash entry array and hash value nodes in.
uint hashBlockSize
Size of the buffer.
uint hashTableSize
Size of the hash table, i.e.
uint nextValueNode
Index of next hash value node to allocate.

Detailed Description

LcsHashTable implements a hash table that fits the hash entries and the overflow nodes into one scratch buffer of size hashBlockSize.

The overflow nodes are of type LcsHashValueNode.

Definition at line 130 of file LcsHash.h.

Constructor & Destructor Documentation

| LcsHashTable::LcsHashTable | ( | | ) | [inline, explicit] | | -------------------------- | - | | - | -------------------- |

Member Function Documentation

void LcsHashTable::init ( PBuffer hashBlockInit,
uint hashBlockSizeInit
)

| void LcsHashTable::resetHash | ( | | ) | [inline] | | ---------------------------- | - | | - | ---------- |

| void LcsHashTable::resetBatch | ( | | ) | [inline] | | ----------------------------- | - | | - | ---------- |

| uint LcsHashTable::numHashEntries | ( | | ) | [inline] | | ---------------------------------------------------------------------------------------------- | - | | - | ---------- |

void LcsHashTable::undoNewValueNode ( uint key ) [inline]

Undoes the most recent insert.

Parameters:

[in] key hash key of the node to remove. The most recently inserted value nodes is always at the beginning of the overflow list for a key

Definition at line 829 of file LcsHash.h.

References entry, hashBlock, and nextValueNode.

Referenced by LcsHash::undoInsert().

Returns the first value node having a certain key value.

Parameters:

[in] key hash key to locate

Returns:

pointer to the first value node

Definition at line 836 of file LcsHash.h.

References entry, and hashBlock.

Referenced by LcsHash::search().

bool LcsHashTable::isFull ( uint leftOvers = 0 ) [inline]

Member Data Documentation

Array indexed by the hash key value.

Each entry points(using offset) to a list of hash value nodes which have the same hash key.

Entry array is indexed by the hash kay and stores the first offsets of value nodes with the hash key. Though the offset value does not need to be uint16_t, it saves memory to use uint16_t than uint(32 or 64 bit) since the number of entries(i.e. hash table size) is limited to the numbers that can fit into a block. This also implied that the next field in LcsHashValueNode needs to be uint16_t.

Definition at line 167 of file LcsHash.h.

Referenced by getFirstValueNode(), init(), insertNewValueNode(), and undoNewValueNode().

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

Generated on Mon Jun 22 04:00:37 2009 for Fennel by doxygen 1.5.1