LcsHashTable Class Reference

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>

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]

Definition at line 782 of file LcsHash.h.

References hashBlock, hashTableSize, and nextValueNode.

{
    hashBlock = NULL;
    hashTableSize = 0;
    nextValueNode = 0;
}

---

Member Function Documentation

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

Sets up fields in LcsHashTable.

Parameters:

[in]	hashBlockInit	buffer to fit the variable length fields entry and valueNodes
[in]	hashBlockSizeInit	size of the buffer

Definition at line 535 of file LcsHash.cpp.

References entry, hashBlock, hashBlockSize, hashTableSize, nextValueNode, and valueNodes.

Referenced by LcsHash::init().

{
    hashBlock     = hashBlockInit;
    hashBlockSize = hashBlockSizeInit;
    memset(hashBlock, 0, hashBlockSize);

    /*
     * hashTableSize is the size for entry array. Reserve space assuming no
     * one valueNode for each entry(no empty entry, and no overflow).
     */
    hashTableSize = hashBlockSize /
        (sizeof(uint16_t) + sizeof(LcsHashValueNode));

    /*
     * entry points to the beginning of the hashBlock
     */
    entry = (uint16_t *)hashBlock;

    /*
     * valueNodes follow the entry array.
     */
    valueNodes = reinterpret_cast<LcsHashValueNode *>(
        hashBlock + sizeof(uint16_t) * hashTableSize);

    /*
     * Starts from the very first valueNodes.
     */
    nextValueNode = 0;
}

void LcsHashTable::resetHash

(

)

[inline]

Resets the hash table to prepare for encoding the next page.

Definition at line 789 of file LcsHash.h.

References hashBlock, hashBlockSize, and nextValueNode.

Referenced by LcsHash::startNewBatch().

{
    memset(hashBlock, 0, hashBlockSize);
    nextValueNode = 0;
}

void LcsHashTable::resetBatch

(

)

[inline]

Resets the entries present in the current batch to prepare for encoding the next batch.

Definition at line 795 of file LcsHash.h.

References nextValueNode, and valueNodes.

Referenced by LcsHash::startNewBatch().

{
    for (int i = 0; i < nextValueNode; i++) {
        (&(valueNodes[i].valueOrd))->clearValueInBatch();
    }
}

uint LcsHashTable::numHashEntries

(

)

[inline]

Returns the hash table size.

Definition at line 802 of file LcsHash.h.

References hashTableSize.

Referenced by LcsHash::computeKey().

{
    return hashTableSize;
}

LcsHashValueNode * LcsHashTable::getNewValueNode

(

)

[inline]

Gives out the next hash value node for the caller to fill in interesting information.

Definition at line 807 of file LcsHash.h.

References nextValueNode, and valueNodes.

Referenced by LcsHash::insert(), and LcsHash::restore().

{
    return &(valueNodes[nextValueNode]);
}

void LcsHashTable::insertNewValueNode	(	uint	key,
		LcsHashValueNode *	newNode
	)			[inline]

Inserts a new node into the overflow chain.

Parameters:

[in]	key	hash key of the newNode
[in]	newNode	the new node to insert

Definition at line 812 of file LcsHash.h.

References entry, hashBlock, LcsHashValueNode::next, and nextValueNode.

Referenced by LcsHash::insert(), and LcsHash::restore().

{
    newNode->next = (uint16_t)entry[key];

    /*
      Insert at the beginning.
    */
    entry[key] = (uint16_t)((uint8_t*)newNode - hashBlock);

    /*
      Bump up the value for the next node to give out.
    */
    nextValueNode++;
}

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().

{
    entry[key] = (uint16_t)
        ((LcsHashValueNode*)(hashBlock + entry[key]))->next;
    nextValueNode--;
}

LcsHashValueNode * LcsHashTable::getFirstValueNode

(

uint

key

)

[inline]

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().

{
    uint16_t offset = entry[key];

    if (offset) {
        return (LcsHashValueNode*) (hashBlock + offset);
    } else {
        return NULL;
    }
}

LcsHashValueNode * LcsHashTable::getNextValueNode

(

LcsHashValueNode *

pValueNode

)

[inline]

Returns the next value node following a value node.

Parameters:

[in]

pValueNode

pointer to the current LcsHashValueNode

Returns:

pointer to the next value node

Definition at line 847 of file LcsHash.h.

References hashBlock, and LcsHashValueNode::next.

Referenced by LcsHash::search().

{
    uint16_t offset = pValueNode->next;

    if (offset) {
        return (LcsHashValueNode*) (hashBlock + offset);
    } else {
        return NULL;
    }
}

bool LcsHashTable::isFull

(

uint

leftOvers = 0

)

[inline]

Checks if hash table is full.

Parameters:

[in]

leftOvers

additional value nodes to accommodate with a default value of 0

Returns:

true if hash table is full

Definition at line 859 of file LcsHash.h.

References hashBlock, hashBlockSize, nextValueNode, and valueNodes.

Referenced by LcsHash::insert(), LcsHash::isHashFull(), LcsHash::restore(), and LcsHash::startNewBatch().

{
    /*
      need to leave one spot for sorting and leftsOvers that
      will be added
    */
    return ((PBuffer)(&(valueNodes[nextValueNode])
            + (leftOvers + 1) * sizeof(LcsHashValueNode))
        >= (PBuffer) (hashBlock + hashBlockSize));
}

---

Member Data Documentation

PBuffer LcsHashTable::hashBlock [private]

Buffer to fit the hash entry array and hash value nodes in.

Definition at line 137 of file LcsHash.h.

Referenced by getFirstValueNode(), getNextValueNode(), init(), insertNewValueNode(), isFull(), LcsHashTable(), resetHash(), and undoNewValueNode().

uint LcsHashTable::hashBlockSize [private]

Size of the buffer.

Definition at line 142 of file LcsHash.h.

Referenced by init(), isFull(), and resetHash().

uint LcsHashTable::hashTableSize [private]

Size of the hash table, i.e.

size of the hash entry array.

Definition at line 147 of file LcsHash.h.

Referenced by init(), LcsHashTable(), and numHashEntries().

uint LcsHashTable::nextValueNode [private]

Index of next hash value node to allocate.

Definition at line 152 of file LcsHash.h.

Referenced by getNewValueNode(), init(), insertNewValueNode(), isFull(), LcsHashTable(), resetBatch(), resetHash(), and undoNewValueNode().

uint16_t* LcsHashTable::entry

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().

LcsHashValueNode* LcsHashTable::valueNodes

List of hash value nodes.

Definition at line 172 of file LcsHash.h.

Referenced by LcsHash::clearFixedEntries(), getNewValueNode(), init(), isFull(), LcsCompareColKeyUsingOffsetIndex::lessThan(), LcsHash::prepareCompressedBatch(), LcsHash::prepareFixedOrVariableBatch(), and resetBatch().

---

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

• /home/pub/open/dev/fennel/lucidera/colstore/LcsHash.h
• /home/pub/open/dev/fennel/lucidera/colstore/LcsHash.cpp

---