mirror of
https://github.com/mariadb-corporation/mariadb-columnstore-engine.git
synced 2025-04-20 09:07:44 +03:00
1521 lines
48 KiB
C++
1521 lines
48 KiB
C++
/* Copyright (C) 2014 InfiniDB, Inc.
|
|
|
|
This program is free software; you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License
|
|
as published by the Free Software Foundation; version 2 of
|
|
the License.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program; if not, write to the Free Software
|
|
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
|
|
MA 02110-1301, USA. */
|
|
|
|
/******************************************************************************************
|
|
* $Id: we_indextree.cpp 4450 2013-01-21 14:13:24Z rdempsey $
|
|
*
|
|
******************************************************************************************/
|
|
/** @file */
|
|
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
|
|
#define WRITEENGINEINDEXTREE_DLLEXPORT
|
|
#include "we_indextree.h"
|
|
#undef WRITEENGINEINDEXTREE_DLLEXPORT
|
|
|
|
namespace WriteEngine
|
|
{
|
|
/**
|
|
* Constructor
|
|
*/
|
|
IndexTree::IndexTree()
|
|
: m_useFreeMgr(true), m_useListMgr(true), m_useMultiCol(false), m_useMultiRid(false), m_assignFbo(0)
|
|
{
|
|
clearBlock(&m_rootBlock);
|
|
}
|
|
|
|
/**
|
|
* Default Destructor
|
|
*/
|
|
IndexTree::~IndexTree()
|
|
{
|
|
}
|
|
|
|
/*
|
|
const int IndexTree::getIndexTreeBitTestEntry( uint64_t entry, short* entryType, int* bitTest, int* group,
|
|
int32_t* treePointer )
|
|
{
|
|
*treePointer = entry & IDX_PTR_MASK;
|
|
entry = entry >> IDX_PTR_SIZE + 2; // skip one spare bit and bit-compare bit
|
|
|
|
*group = entry & THREE_BIT_MASK;
|
|
entry = entry >> IDX_GROUP_SIZE;
|
|
|
|
*bitTest = entry & TEN_BIT_MASK;
|
|
*entryType = entry >> IDX_BITTEST_SIZE;
|
|
|
|
*entryType = entry & THREE_BIT_MASK;
|
|
|
|
return NO_ERROR;
|
|
}
|
|
|
|
const void IndexTree::setIndexTreeBitTestEntry( uint64_t* entry, short entryType, int bitTest, int group,
|
|
int32_t treePointer )
|
|
{
|
|
memset( entry, 0, ROW_PER_BYTE );
|
|
|
|
*entry = treePointer | group << ( IDX_PTR_SIZE + 2 );
|
|
*entry = *entry | bitTest << ( IDX_PTR_SIZE + 2 + IDX_GROUP_SIZE );
|
|
*entry = *entry | entryType << ( IDX_PTR_SIZE + 2 + IDX_GROUP_SIZE + IDX_TYPE_SIZE );
|
|
|
|
return NO_ERROR;
|
|
}
|
|
*/
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Clear the tree
|
|
* PARAMETERS:
|
|
* myTree - tree pointer
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::clearTree(IdxTree* myTree)
|
|
{
|
|
myTree->width = myTree->key = myTree->rid = myTree->maxLevel = 0;
|
|
|
|
for (int i = 0; i < IDX_MAX_TREE_LEVEL; i++)
|
|
clearTreeNode(&myTree->node[i]);
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Clear the tree node
|
|
* PARAMETERS:
|
|
* myNode - node pointer
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::clearTreeNode(IdxTreeNode* myNode)
|
|
{
|
|
myNode->level = 0;
|
|
myNode->allocCount = 0;
|
|
myNode->useCount = 0;
|
|
// myNode->group = 0;
|
|
myNode->used = false;
|
|
setBlankEntry(&myNode->next);
|
|
setBlankEntry(&myNode->current);
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Assign segment from free manager
|
|
* PARAMETERS:
|
|
* segmentType - group type
|
|
* assignPtr - the assigned ptr
|
|
* no - internal debug use flag
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::assignSegment(int segmentType, IdxEmptyListEntry* assignPtr, int no)
|
|
{
|
|
int rc = NO_ERROR;
|
|
|
|
m_rootBlock.dirty = true;
|
|
|
|
if (m_useFreeMgr)
|
|
{
|
|
if (isDebug(DEBUG_3))
|
|
{
|
|
printf("\n++++++ Before Assign");
|
|
printMemSubBlock(&m_rootBlock, 0, true);
|
|
}
|
|
|
|
rc = m_freeMgr.assignSegment(/*m_pTreeFile*/ m_cbTree, &m_rootBlock, TREE, (IdxTreeGroupType)segmentType,
|
|
assignPtr /*, TREE */);
|
|
|
|
if (isDebug(DEBUG_3))
|
|
{
|
|
printf("\nAssign the pointer, entry segment=%d fbo=%2d sbid=%2d entry=%2d", segmentType,
|
|
(int)assignPtr->fbo, (int)assignPtr->sbid, (int)assignPtr->entry);
|
|
printMemSubBlock(&m_rootBlock, 0, true);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
assignPtr->fbo = 1 + m_assignFbo;
|
|
assignPtr->sbid = 3 + no;
|
|
assignPtr->entry = 4;
|
|
}
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Build a complete empty tree branch
|
|
* PARAMETERS:
|
|
* key - key value
|
|
* width - key width
|
|
* rid - row id
|
|
* rootTestbitVal - test bit test value at root level
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::buildEmptyIndexTreeBranch(const uint64_t key, const int width, const RID rid,
|
|
const int rootTestbitVal)
|
|
{
|
|
int rc;
|
|
IdxBitmapPointerEntry bitmapEntry = {0};
|
|
|
|
rc = buildEmptyTreePart(key, width, rid, 1);
|
|
|
|
// set the root level bitmapPointerMap
|
|
bitmapEntry.type = BITMAP_PTR; // BIT_TEST;
|
|
bitmapEntry.fbo = m_tree.node[0].next.fbo;
|
|
bitmapEntry.sbid = m_tree.node[0].next.sbid;
|
|
bitmapEntry.entry = m_tree.node[0].next.entry;
|
|
|
|
setSubBlockEntry(m_rootBlock.data, IDX_BITMAP_SUBBLOCK_NO, rootTestbitVal, MAX_COLUMN_BOUNDARY,
|
|
&bitmapEntry);
|
|
m_rootBlock.dirty = true;
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Build exist index tree branch
|
|
* PARAMETERS:
|
|
* key - key value
|
|
* width - key width
|
|
* rid - row id
|
|
* rootTestbitVal - test bit at root level
|
|
* bitmapEntry - current bitmap entry
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::buildExistIndexTreeBranch(const uint64_t key, const int width, const RID rid,
|
|
const int rootTestbitVal, IdxBitmapPointerEntry bitmapEntry)
|
|
{
|
|
int rc = NO_ERROR, loopCount, testbitVal, i, j, allocCount, realCount, matchPos, moveCount, parentLevel = 0,
|
|
curLevel, curOffset = 0;
|
|
bool bSuccess;
|
|
IdxEmptyListEntry assignPtrEntry, releasePtrEntry;
|
|
IdxBitTestEntry bittestEntry, matchBitTestEntry, parentBitTestEntry, curEntry;
|
|
DataBlock curBlock, parentBlock;
|
|
bool bAddFlag = false, bDone = false, bFound, bExitOuterLoop, bExitInnerLoop, entryMap[ENTRY_PER_SUBBLOCK];
|
|
|
|
bExitOuterLoop = false;
|
|
loopCount = m_tree.maxLevel;
|
|
|
|
for (i = 1; !bExitOuterLoop && i < loopCount; i++)
|
|
{
|
|
// load the block
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry,
|
|
MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
if (i == 1 && isAddrPtrEmpty(&bittestEntry, BIT_TEST))
|
|
return ERR_STRUCT_EMPTY;
|
|
|
|
rc = getTreeNodeInfo(&curBlock, m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry,
|
|
width, (IdxTreeGroupType)bittestEntry.group, &allocCount, &realCount, entryMap);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
matchBitTestEntry = bittestEntry; // assign to the value of the first entry
|
|
bSuccess = getTestbitValue(key, width, i, &testbitVal);
|
|
|
|
setBittestEntry(&curEntry, testbitVal, bittestEntry.group, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry);
|
|
setTreeNode(&m_tree.node[i], i, allocCount, realCount, 0, bittestEntry, curEntry);
|
|
|
|
matchBitTestEntry.bitTest = testbitVal;
|
|
bFound =
|
|
getTreeMatchEntry(&curBlock, m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry,
|
|
width, allocCount, entryMap, &matchPos, &matchBitTestEntry);
|
|
|
|
if (!bFound) // this testbit not exist at the current level
|
|
{
|
|
bExitOuterLoop = true; // tell to exit the outer loop
|
|
bAddFlag = true;
|
|
|
|
if (allocCount < realCount + 1) // we have enough space to take care of the extra one
|
|
{
|
|
// we don't have space to take care of the extra one, have to reassign to a big block
|
|
if (bittestEntry.group >= ENTRY_32) // it's impossible this condition holds true
|
|
return ERR_IDX_TREE_INVALID_GRP;
|
|
|
|
m_tree.node[i].current.group++;
|
|
rc = assignSegment(m_tree.node[i].current.group, &assignPtrEntry, i);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
m_tree.node[i].allocCount = 0x1 << m_tree.node[i].current.group;
|
|
|
|
if (isDebug(DEBUG_3))
|
|
{
|
|
printf("\nEntry starting from %d:%d:%d (type %d ) will move to %d:%d:%d (type %d)",
|
|
(int)m_tree.node[parentLevel].next.fbo, (int)m_tree.node[parentLevel].next.sbid,
|
|
(int)m_tree.node[parentLevel].next.entry, (int)(m_tree.node[i].current.group - 1),
|
|
(int)assignPtrEntry.fbo, (int)assignPtrEntry.sbid, (int)assignPtrEntry.entry,
|
|
(int)m_tree.node[i].current.group);
|
|
printf("\nNew space capacity is %d", (int)m_tree.node[i].allocCount);
|
|
printf("\nBefore the move");
|
|
printSubBlock(m_tree.node[parentLevel].next.fbo, m_tree.node[parentLevel].next.sbid);
|
|
printSubBlock(assignPtrEntry.fbo, assignPtrEntry.sbid);
|
|
}
|
|
|
|
rc = moveEntry(m_tree.node[parentLevel].next.fbo, m_tree.node[parentLevel].next.sbid,
|
|
m_tree.node[parentLevel].next.entry, width, assignPtrEntry.fbo, assignPtrEntry.sbid,
|
|
assignPtrEntry.entry, m_tree.node[i].current.group, allocCount, entryMap, &moveCount,
|
|
m_tree.node[i].allocCount);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
if (isDebug(DEBUG_3))
|
|
{
|
|
printf("\nAfter the move");
|
|
printSubBlock(m_tree.node[parentLevel].next.fbo, m_tree.node[parentLevel].next.sbid);
|
|
printSubBlock(assignPtrEntry.fbo, assignPtrEntry.sbid);
|
|
}
|
|
|
|
if (moveCount != realCount)
|
|
return ERR_IDX_TREE_MOVE_ENTRY;
|
|
|
|
// set release entry
|
|
setEmptyListEntry(&releasePtrEntry, bittestEntry.group, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry);
|
|
|
|
if (i == 1) // handle bitmap parent
|
|
{
|
|
bitmapEntry.fbo = m_tree.node[0].next.fbo = m_tree.node[i].current.fbo = assignPtrEntry.fbo;
|
|
bitmapEntry.sbid = m_tree.node[0].next.sbid = m_tree.node[i].current.sbid = assignPtrEntry.sbid;
|
|
bitmapEntry.entry = m_tree.node[0].next.entry = m_tree.node[i].current.entry = assignPtrEntry.entry;
|
|
setSubBlockEntry(m_rootBlock.data, IDX_BITMAP_SUBBLOCK_NO, rootTestbitVal, MAX_COLUMN_BOUNDARY,
|
|
&bitmapEntry);
|
|
}
|
|
else // handle parent for the rest of levels in the tree
|
|
{
|
|
rc =
|
|
readSubBlockEntry(m_cbTree, &parentBlock, m_tree.node[parentLevel].current.fbo,
|
|
m_tree.node[parentLevel].current.sbid, m_tree.node[parentLevel].current.entry,
|
|
MAX_COLUMN_BOUNDARY, &parentBitTestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
parentBitTestEntry.fbo = m_tree.node[parentLevel].next.fbo = m_tree.node[i].current.fbo =
|
|
assignPtrEntry.fbo;
|
|
parentBitTestEntry.sbid = m_tree.node[parentLevel].next.sbid = m_tree.node[i].current.sbid =
|
|
assignPtrEntry.sbid;
|
|
parentBitTestEntry.entry = m_tree.node[parentLevel].next.entry = m_tree.node[i].current.entry =
|
|
assignPtrEntry.entry;
|
|
|
|
rc = writeSubBlockEntry(m_cbTree, &parentBlock, m_tree.node[parentLevel].current.fbo,
|
|
m_tree.node[parentLevel].current.sbid,
|
|
m_tree.node[parentLevel].current.entry, MAX_COLUMN_BOUNDARY,
|
|
&parentBitTestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
}
|
|
|
|
// here's the work to release the ptr
|
|
rc = releaseSegment(bittestEntry.group, &releasePtrEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
} // end of if( allocCount >=
|
|
|
|
// take care of rest of empty part
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry,
|
|
MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
m_tree.node[i].current.bitTest = testbitVal;
|
|
matchBitTestEntry.group = m_tree.node[i].current.group;
|
|
m_tree.node[i].allocCount = 0x1 << m_tree.node[i].current.group;
|
|
|
|
bExitInnerLoop = false;
|
|
|
|
for (j = 0; !bExitInnerLoop && j < m_tree.node[i].allocCount; j++)
|
|
if (!entryMap[j]) // here's the empty spot
|
|
{
|
|
if (m_tree.maxLevel > 2 && i != loopCount - 1)
|
|
{
|
|
rc = buildEmptyTreePart(key, width, rid, i + 1, 0);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
bDone = true;
|
|
}
|
|
|
|
// check out of bound
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry + j,
|
|
MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
matchBitTestEntry.fbo = m_tree.node[i + 1].current.fbo;
|
|
matchBitTestEntry.sbid = m_tree.node[i + 1].current.sbid;
|
|
matchBitTestEntry.entry = m_tree.node[i + 1].current.entry;
|
|
|
|
rc = writeSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry + j,
|
|
MAX_COLUMN_BOUNDARY, &matchBitTestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
m_tree.node[i].useCount++;
|
|
|
|
m_tree.node[i].current.entry += j;
|
|
entryMap[j] = true;
|
|
curOffset = j;
|
|
|
|
bExitInnerLoop = true;
|
|
} // end of if( !entryMap[j] )
|
|
|
|
} // end of if( !bFound
|
|
else
|
|
{
|
|
m_tree.node[i].current.entry += matchPos;
|
|
m_tree.node[parentLevel].next.entry += matchPos;
|
|
}
|
|
|
|
m_tree.node[i].next = matchBitTestEntry;
|
|
parentLevel++;
|
|
} // end of for( i = 1;
|
|
|
|
curLevel = m_tree.maxLevel - 1;
|
|
|
|
if (!bDone)
|
|
{
|
|
rc =
|
|
updateListFile(key, width, rid, curLevel, m_tree.node[curLevel].current.group,
|
|
m_tree.node[curLevel].allocCount, m_tree.node[curLevel].useCount, curOffset, bAddFlag);
|
|
}
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Build a a part of empty tree branch
|
|
* PARAMETERS:
|
|
* key - key value
|
|
* width - key width
|
|
* rid - row id
|
|
* startLevel - tree level
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
* retBitTestEntry - return address pointer
|
|
***********************************************************/
|
|
const int IndexTree::buildEmptyTreePart(const uint64_t key, const int width, const RID rid,
|
|
const int startLevel, const int offset)
|
|
{
|
|
int rc, loopCount, testbitVal, i, parentLevel;
|
|
bool bSuccess;
|
|
IdxEmptyListEntry assignPtrEntry, childPtrEntry; //, listEntry;
|
|
IdxBitTestEntry bittestEntry, curEntry;
|
|
DataBlock curBlock;
|
|
|
|
if (startLevel <= 0 || m_tree.maxLevel < 2) // the start level must >= 1 and maxLevel >= 2
|
|
return ERR_IDX_TREE_INVALID_LEVEL;
|
|
|
|
loopCount = (m_tree.maxLevel - 1) > 1 ? m_tree.maxLevel - 1 : 0; //( width/5 ) - 1;
|
|
|
|
rc = assignSegment(ENTRY_1, &assignPtrEntry, 0);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
if (isAddrPtrEmpty(&assignPtrEntry, EMPTY_LIST))
|
|
return ERR_STRUCT_EMPTY;
|
|
|
|
parentLevel = startLevel - 1;
|
|
|
|
// assuming the parent take care of group, bit test value, and type
|
|
m_tree.node[parentLevel].next.fbo = assignPtrEntry.fbo;
|
|
m_tree.node[parentLevel].next.sbid = assignPtrEntry.sbid;
|
|
m_tree.node[parentLevel].next.entry = assignPtrEntry.entry;
|
|
|
|
// assign bit test for rest of levels
|
|
for (i = startLevel; i < loopCount; i++)
|
|
{
|
|
// assign another one for child
|
|
rc = assignSegment(ENTRY_1, &childPtrEntry, i);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry,
|
|
/*width*/ MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
bSuccess = getTestbitValue(key, width, i, &testbitVal);
|
|
|
|
if (!bSuccess)
|
|
return ERR_IDX_TREE_INVALID_LEVEL;
|
|
|
|
setBittestEntry(&bittestEntry, testbitVal, ENTRY_1, childPtrEntry.fbo, childPtrEntry.sbid,
|
|
childPtrEntry.entry);
|
|
setSubBlockEntry(&curBlock, m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry,
|
|
MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
writeDBFile(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo);
|
|
|
|
setBittestEntry(&curEntry, testbitVal, ENTRY_1, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry);
|
|
setTreeNode(&m_tree.node[i], i, 1, 1, 0, bittestEntry, curEntry);
|
|
parentLevel++;
|
|
}
|
|
|
|
// assign the bit test for the last level
|
|
// load the last piece
|
|
rc = updateListFile(key, width, rid, i, ENTRY_1, 1, 1, offset, true);
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Close index files
|
|
* PARAMETERS:
|
|
* none
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::closeIndex()
|
|
{
|
|
if (m_rootBlock.dirty)
|
|
{
|
|
uint64_t lbid0 = 0;
|
|
#ifdef BROKEN_BY_MULTIPLE_FILES_PER_OID
|
|
BRMWrapper::getInstance()->getBrmInfo(m_cbTree.file.oid, 0, lbid0);
|
|
#endif
|
|
writeDBFile(m_cbTree, m_rootBlock.data, lbid0);
|
|
}
|
|
|
|
if (Cache::getUseCache())
|
|
flushCache();
|
|
|
|
m_fileopTree.closeFile(m_cbTree.file.pFile);
|
|
m_fileopList.closeFile(m_cbList.file.pFile);
|
|
m_cbTree.file.pFile = NULL;
|
|
m_cbList.file.pFile = NULL;
|
|
clear();
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Create index related files
|
|
* PARAMETERS:
|
|
* treeFid - the index tree file id
|
|
* listFid - the index list file id
|
|
* useFreeMgrFlag - internal use flag
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::createIndex(const FID treeFid, const FID listFid, const bool useFreeMgrFlag)
|
|
{
|
|
#ifdef BROKEN_BY_MULTIPLE_FILES_PER_OID
|
|
int allocSize;
|
|
|
|
// init
|
|
// clear();
|
|
|
|
RETURN_ON_ERROR(createFile(treeFid, DEFAULT_TOTAL_BLOCK /* * 10*/, allocSize));
|
|
RETURN_ON_ERROR(createFile(listFid, DEFAULT_TOTAL_BLOCK /* * 10*/, allocSize));
|
|
#endif
|
|
|
|
// load index files
|
|
// RETURN_ON_ERROR( openIndex( treeFid, listFid ) );
|
|
// rc = initIndex( treeFid, listFid );
|
|
// closeIndex();
|
|
|
|
return initIndex(treeFid, listFid);
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Delete a value from the tree
|
|
* PARAMETERS:
|
|
* key - key value
|
|
* width - key width
|
|
* rid - row id
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::deleteIndex(const uint64_t key, const int width, const RID rid)
|
|
{
|
|
IdxEmptyListEntry listHdrAddr;
|
|
|
|
return processIndex(key, width, rid, listHdrAddr);
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Get test bit values
|
|
* PARAMETERS:
|
|
* key - index key
|
|
* width - key width
|
|
* curTestNo - test bit iteration no
|
|
* RETURN:
|
|
* True if success, otherwise if out of bound
|
|
* bittestVal - test bit value
|
|
***********************************************************/
|
|
const bool IndexTree::getTestbitValue(const uint64_t key, const int width, const int curTestNo,
|
|
int* bittestVal)
|
|
{
|
|
int shiftPos, maskPos = 0;
|
|
bool bSuccess = true;
|
|
|
|
if (!m_useMultiCol)
|
|
{
|
|
*bittestVal = 0;
|
|
shiftPos = width - (curTestNo + 1) * 5;
|
|
|
|
if (shiftPos > 0)
|
|
*bittestVal = getBitValue(key, shiftPos, BIT_MASK_ARRAY[5]);
|
|
else
|
|
{
|
|
if (shiftPos >= -4)
|
|
{
|
|
maskPos = width - curTestNo * 5;
|
|
*bittestVal = key & BIT_MASK_ARRAY[maskPos];
|
|
}
|
|
else
|
|
bSuccess = false;
|
|
}
|
|
}
|
|
else
|
|
*bittestVal = m_multiColKey.testbitArray[curTestNo];
|
|
|
|
return bSuccess;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Get the matching entry within the current tree node
|
|
* PARAMETERS:
|
|
* block - block data
|
|
* fbo, sbid, entry - pointer address
|
|
* width - key width
|
|
* allocCount - the total number of allocated entries
|
|
* entryMap - the entry availablibility map
|
|
* checkEntry - bittest value
|
|
* RETURN:
|
|
* True if found, False otherwise
|
|
* checkEntry - if found the ptr got reset
|
|
***********************************************************/
|
|
const bool IndexTree::getTreeMatchEntry(DataBlock* block, const uint64_t sbid, const uint64_t entry,
|
|
const int width, const int allocCount, const bool* entryMap,
|
|
int* matchEntry, IdxBitTestEntry* checkEntry)
|
|
{
|
|
IdxBitTestEntry curEntry;
|
|
bool bFoundFlag = false;
|
|
|
|
for (int i = 0; i < allocCount; i++)
|
|
{
|
|
getSubBlockEntry(block->data, sbid, entry + i, MAX_COLUMN_BOUNDARY, &curEntry);
|
|
|
|
if (entryMap[i] && (curEntry.type == checkEntry->type && curEntry.bitTest == checkEntry->bitTest))
|
|
{
|
|
*checkEntry = curEntry;
|
|
*matchEntry = i;
|
|
bFoundFlag = true;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return bFoundFlag;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Get tree node summary information
|
|
* PARAMETERS:
|
|
* block - block data
|
|
* fbo, sbid, entry - pointer address
|
|
* width - key width
|
|
* group - entry group
|
|
* testbitVal - current bit test value
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
* allocCount - the total number of allocated entries
|
|
* realCount - the total number of real entries
|
|
* entryMap - the entry availablibility map
|
|
***********************************************************/
|
|
const int IndexTree::getTreeNodeInfo(DataBlock* block, const uint64_t sbid, const uint64_t entry,
|
|
const int width, const IdxTreeGroupType group, int* allocCount,
|
|
int* realCount, bool* entryMap)
|
|
{
|
|
IdxBitTestEntry curEntry;
|
|
int rc = NO_ERROR;
|
|
|
|
memset(entryMap, false, ENTRY_PER_SUBBLOCK);
|
|
*realCount = 0;
|
|
*allocCount = 0x1 << group;
|
|
|
|
for (int i = 0; i < *allocCount; i++)
|
|
{
|
|
getSubBlockEntry(block->data, sbid, entry + i, MAX_COLUMN_BOUNDARY, &curEntry);
|
|
|
|
if (curEntry.type == BIT_TEST || curEntry.type == LEAF_LIST) // every guy here must have the same type
|
|
{
|
|
entryMap[i] = true;
|
|
*realCount = *realCount + 1;
|
|
}
|
|
else if (curEntry.type == EMPTY_ENTRY)
|
|
entryMap[i] = false;
|
|
else
|
|
rc = ERR_IDX_TREE_INVALID_TYPE;
|
|
|
|
if (rc != NO_ERROR)
|
|
break;
|
|
}
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Check index entry address pointer is empty or not
|
|
* PARAMETERS:
|
|
* pStruct - index entry pointer
|
|
* entryType - the entry type
|
|
* RETURN:
|
|
* True if empty, False otherwise
|
|
***********************************************************/
|
|
const bool IndexTree::isAddrPtrEmpty(void* pStruct, const IdxTreeEntryType entryType) const
|
|
{
|
|
bool bStatus;
|
|
IdxBitmapPointerEntry* pBitmap;
|
|
IdxBitTestEntry* pBittest;
|
|
IdxEmptyListEntry* pEmptyList;
|
|
|
|
switch (entryType)
|
|
{
|
|
case BITMAP_PTR /*EMPTY_PTR*/: // this is the case for bitmap pointer address
|
|
pBitmap = (IdxBitmapPointerEntry*)pStruct;
|
|
bStatus = /*!pBitmap->oid &&*/ !pBitmap->fbo && !pBitmap->sbid && !pBitmap->entry;
|
|
break;
|
|
|
|
case BIT_TEST: // this is the case for bittest pointer address
|
|
pBittest = (IdxBitTestEntry*)pStruct;
|
|
bStatus = /*!pBittest->oid &&*/ !pBittest->fbo && !pBittest->sbid && !pBittest->entry;
|
|
break;
|
|
|
|
case EMPTY_LIST: // this is the case for bittest pointer address
|
|
pEmptyList = (IdxEmptyListEntry*)pStruct;
|
|
bStatus = !pEmptyList->fbo && !pEmptyList->sbid && !pEmptyList->entry;
|
|
break;
|
|
|
|
default: bStatus = true;
|
|
}
|
|
|
|
return bStatus;
|
|
}
|
|
|
|
const int IndexTree::initIndex(const FID treeFid, const FID listFid)
|
|
{
|
|
int rc = NO_ERROR;
|
|
long numOfBlock;
|
|
unsigned char writeBuf[BYTE_PER_BLOCK];
|
|
|
|
bool oldUseVb = BRMWrapper::getUseVb();
|
|
BRMWrapper::setUseVb(false);
|
|
|
|
clear();
|
|
RETURN_ON_ERROR(openIndex(treeFid, listFid));
|
|
|
|
memset(writeBuf, 0, BYTE_PER_BLOCK);
|
|
numOfBlock = getFileSize(m_cbTree.file.pFile) / BYTE_PER_BLOCK;
|
|
|
|
for (int i = 0; i < numOfBlock; i++)
|
|
fwrite(writeBuf, sizeof(writeBuf), 1, m_cbTree.file.pFile);
|
|
|
|
numOfBlock = getFileSize(m_cbList.file.pFile) / BYTE_PER_BLOCK;
|
|
|
|
for (int i = 0; i < numOfBlock; i++)
|
|
fwrite(writeBuf, sizeof(writeBuf), 1, m_cbList.file.pFile);
|
|
|
|
// very weird, have to close before we can call free mgr init
|
|
closeIndex();
|
|
RETURN_ON_ERROR(openIndex(treeFid, listFid));
|
|
|
|
rc = m_freeMgr.init(m_cbTree, TREE);
|
|
|
|
if (rc == NO_ERROR)
|
|
rc = m_freeMgr.init(m_cbList, LIST);
|
|
|
|
closeIndex();
|
|
|
|
BRMWrapper::setUseVb(oldUseVb);
|
|
|
|
if (isDebug(DEBUG_1))
|
|
printf("\nEnd of the init for oid %d\n", m_cbTree.file.oid);
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Move tree entries
|
|
* PARAMETERS:
|
|
* fbo, sbid, entry - pointer address
|
|
* width - key width
|
|
* allocCount - the total number of allocated entries
|
|
* entryMap - the entry availablibility map
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::moveEntry(const uint64_t oldFbo, const uint64_t oldSbid, const uint64_t oldEntry,
|
|
const int width, const uint64_t newFbo, const uint64_t newSbid,
|
|
const uint64_t newEntry, const int newGroup, const int allocCount,
|
|
bool* entryMap, int* moveCount, const int newAllocCount)
|
|
{
|
|
int rc, i;
|
|
DataBlock oldBlock, newBlock;
|
|
IdxBitTestEntry curEntry, blankEntry;
|
|
|
|
rc = readSubBlockEntry(m_cbTree, &oldBlock, oldFbo, oldSbid, oldEntry, /*width*/ MAX_COLUMN_BOUNDARY,
|
|
&curEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
rc = readSubBlockEntry(m_cbTree, &newBlock, newFbo, newSbid, newEntry, /*width*/ MAX_COLUMN_BOUNDARY,
|
|
&curEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
setBlankEntry(&blankEntry);
|
|
|
|
for (i = 0; i < newAllocCount; i++)
|
|
setSubBlockEntry(newBlock.data, newSbid, newEntry + i, MAX_COLUMN_BOUNDARY, &blankEntry);
|
|
|
|
*moveCount = 0;
|
|
|
|
for (i = 0; i < allocCount; i++)
|
|
{
|
|
getSubBlockEntry(oldBlock.data, oldSbid, oldEntry + i, MAX_COLUMN_BOUNDARY, &curEntry);
|
|
|
|
if (entryMap[i])
|
|
{
|
|
curEntry.group = newGroup;
|
|
setSubBlockEntry(newBlock.data, newSbid, newEntry + *moveCount, MAX_COLUMN_BOUNDARY, &curEntry);
|
|
*moveCount = *moveCount + 1;
|
|
}
|
|
|
|
setBlankEntry(&curEntry);
|
|
|
|
if (newFbo != oldFbo)
|
|
setSubBlockEntry(oldBlock.data, oldSbid, oldEntry + i, MAX_COLUMN_BOUNDARY, &curEntry);
|
|
else
|
|
setSubBlockEntry(newBlock.data, oldSbid, oldEntry + i, MAX_COLUMN_BOUNDARY, &curEntry);
|
|
}
|
|
|
|
rc = writeDBFile(m_cbTree, &newBlock, newFbo);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
if (newFbo != oldFbo)
|
|
rc = writeDBFile(m_cbTree, &oldBlock, oldFbo);
|
|
|
|
// reset map
|
|
memset(entryMap, false, ENTRY_PER_SUBBLOCK);
|
|
|
|
for (i = 0; i < *moveCount; i++)
|
|
entryMap[i] = true;
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Open index related files
|
|
* PARAMETERS:
|
|
* treeFid - the index tree file id
|
|
* listFid - the index list file id
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::openIndex(const FID treeFid, const FID listFid)
|
|
{
|
|
int rc = NO_ERROR;
|
|
clear();
|
|
|
|
// load index files
|
|
#ifdef BROKEN_BY_MULTIPLE_FILES_PER_OID
|
|
m_cbTree.file.pFile = m_fileopTree.openFile(treeFid);
|
|
#endif
|
|
|
|
if (m_cbTree.file.pFile == NULL)
|
|
return ERR_FILE_OPEN;
|
|
|
|
#ifdef BROKEN_BY_MULTIPLE_FILES_PER_OID
|
|
m_cbList.file.pFile = m_fileopList.openFile(listFid);
|
|
#endif
|
|
|
|
if (m_cbList.file.pFile == NULL)
|
|
{
|
|
m_fileopTree.closeFile(m_cbTree.file.pFile); // close the one just open
|
|
return ERR_FILE_OPEN;
|
|
}
|
|
|
|
m_cbTree.file.oid = treeFid;
|
|
m_cbList.file.oid = listFid;
|
|
|
|
uint64_t lbid0 = 0;
|
|
#ifdef BROKEN_BY_MULTIPLE_FILES_PER_OID
|
|
rc = BRMWrapper::getInstance()->getBrmInfo(m_cbTree.file.oid, 0, lbid0);
|
|
#endif
|
|
|
|
if (rc != NO_ERROR)
|
|
{
|
|
if (isDebug(DEBUG_1))
|
|
{
|
|
printf("\nFor oid : %d block zero is %ld", m_cbTree.file.oid, (long)lbid0);
|
|
printf("\nIn open index, have problem in get brmInfo, rc=%d", rc);
|
|
}
|
|
|
|
return rc;
|
|
}
|
|
|
|
rc = readDBFile(m_cbTree, m_rootBlock.data, lbid0);
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Process index, including search or delete
|
|
* PARAMETERS:
|
|
* key - key value
|
|
* width - key width
|
|
* rid - row id
|
|
* listHdrAddr - list header address
|
|
* bDelete - delete operation flag
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::processIndex(const uint64_t key, const int width, const RID rid,
|
|
IdxEmptyListEntry& listHdrAddr, const bool bDelete)
|
|
{
|
|
int loopCount, testbitVal, i, allocCount, realCount, matchPos, curFbo, curSbid, curEntry;
|
|
bool bSuccess;
|
|
IdxEmptyListEntry listEntry;
|
|
IdxBitTestEntry bittestEntry, matchBitTestEntry;
|
|
DataBlock curBlock;
|
|
bool bFound, entryMap[ENTRY_PER_SUBBLOCK];
|
|
|
|
int rootTestbitVal, rc = NO_ERROR;
|
|
IdxBitmapPointerEntry bitmapEntry;
|
|
|
|
getTestbitValue(key, width, 0, &rootTestbitVal);
|
|
getSubBlockEntry(m_rootBlock.data, 1, rootTestbitVal, MAX_COLUMN_BOUNDARY, &bitmapEntry);
|
|
|
|
if (isAddrPtrEmpty(&bitmapEntry, /*EMPTY_PTR*/ BITMAP_PTR))
|
|
return bDelete ? ERR_IDX_LIST_INVALID_DELETE : NOT_FOUND;
|
|
|
|
// get the rootbittestEntry level bitmapPointerMap
|
|
curFbo = bitmapEntry.fbo;
|
|
curSbid = bitmapEntry.sbid;
|
|
curEntry = bitmapEntry.entry;
|
|
|
|
loopCount = width / 5 + 1;
|
|
|
|
for (i = 1; i < loopCount; i++)
|
|
{
|
|
// load the block
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, curFbo, curSbid, curEntry, /*width*/ MAX_COLUMN_BOUNDARY,
|
|
&bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
if (isDebug(DEBUG_3))
|
|
{
|
|
printf("\nIn processIndex, level %d", i);
|
|
printSubBlock(curFbo, curSbid);
|
|
}
|
|
|
|
rc = getTreeNodeInfo(&curBlock, curSbid, curEntry, width, (IdxTreeGroupType)bittestEntry.group,
|
|
&allocCount, &realCount, entryMap);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
matchBitTestEntry = bittestEntry; // assign to the value of the first entry
|
|
bSuccess = getTestbitValue(key, width, i, &testbitVal);
|
|
|
|
matchBitTestEntry.bitTest = testbitVal;
|
|
bFound = getTreeMatchEntry(&curBlock, curSbid, curEntry, width, allocCount, entryMap, &matchPos,
|
|
&matchBitTestEntry);
|
|
|
|
if (bFound) // this test bit exists at the current level
|
|
{
|
|
if (i == loopCount - 1)
|
|
{
|
|
// if( loopCount == 2 ) // because of bitmap, it requires a special treatment
|
|
curEntry += matchPos;
|
|
break;
|
|
}
|
|
}
|
|
else
|
|
return NOT_FOUND;
|
|
|
|
getSubBlockEntry(&curBlock, curSbid, curEntry + matchPos, MAX_COLUMN_BOUNDARY, &matchBitTestEntry);
|
|
|
|
curFbo = matchBitTestEntry.fbo;
|
|
curSbid = matchBitTestEntry.sbid;
|
|
curEntry = matchBitTestEntry.entry;
|
|
|
|
} // end of for( i = 0;
|
|
|
|
// here's the last level
|
|
// load the last piece
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, curFbo, curSbid, curEntry /*+ matchPos*/, MAX_COLUMN_BOUNDARY,
|
|
&bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
listEntry.fbo = bittestEntry.fbo;
|
|
listEntry.sbid = bittestEntry.sbid;
|
|
listEntry.entry = bittestEntry.entry;
|
|
|
|
if (bDelete)
|
|
{
|
|
rc = m_listMgr.deleteIndexList(m_cbList, rid, key, &listEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
bSuccess = getTestbitValue(key, width, loopCount - 1, &testbitVal);
|
|
setBittestEntry(&bittestEntry, testbitVal, bittestEntry.group, listEntry.fbo, listEntry.sbid,
|
|
listEntry.entry, LEAF_LIST);
|
|
setSubBlockEntry(&curBlock, curSbid, curEntry, MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
rc = writeDBFile(m_cbTree, &curBlock, curFbo);
|
|
}
|
|
else
|
|
listHdrAddr = listEntry;
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Print a sub block
|
|
* PARAMETERS:
|
|
* fbo - file block offset
|
|
* sbid - sub block id
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::printSubBlock(const int fbo, const int sbid, const bool bNoZero)
|
|
{
|
|
DataBlock curBlock;
|
|
|
|
readDBFile(m_cbTree, &curBlock, fbo);
|
|
printf("\n lbid=%2d sbid=%2d", fbo, sbid);
|
|
printMemSubBlock(&curBlock, sbid);
|
|
}
|
|
|
|
void IndexTree::printMemSubBlock(DataBlock* curBlock, const int sbid, const bool bNoZero)
|
|
{
|
|
int off;
|
|
unsigned char* curPos;
|
|
IdxBitTestEntry curEntry, testZero;
|
|
|
|
setBlankEntry(&testZero);
|
|
curPos = curBlock->data + BYTE_PER_SUBBLOCK * sbid;
|
|
printf("\n========================");
|
|
|
|
for (int i = 0; i < ENTRY_PER_SUBBLOCK; i++)
|
|
{
|
|
memcpy(&curEntry, curPos, MAX_COLUMN_BOUNDARY);
|
|
off = memcmp(&testZero, &curEntry, MAX_COLUMN_BOUNDARY);
|
|
printf("\n Entry %2d : ", i);
|
|
|
|
for (int j = 0; j < MAX_COLUMN_BOUNDARY; j++)
|
|
printf(" %2X", *(curPos + j));
|
|
|
|
printf(" fbo=%2d sbid=%2d entry=%2d group=%d bit=%2d type=%2d", (int)curEntry.fbo, (int)curEntry.sbid,
|
|
(int)curEntry.entry, (int)curEntry.group, (int)curEntry.bitTest, (int)curEntry.type);
|
|
|
|
curPos += MAX_COLUMN_BOUNDARY;
|
|
}
|
|
|
|
printf("\n");
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Assign segment from free manager
|
|
* PARAMETERS:
|
|
* segmentType - group type
|
|
* assignPtr - the assigned ptr
|
|
* no - internal debug use flag
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::releaseSegment(int segmentType, IdxEmptyListEntry* myPtr)
|
|
{
|
|
int rc = NO_ERROR;
|
|
|
|
m_rootBlock.dirty = true;
|
|
|
|
if (m_useFreeMgr)
|
|
{
|
|
if (isDebug(DEBUG_3))
|
|
printf("\n----------Release the pointer, entry segment=%d fbo=%d sbid=%d entry=%d", segmentType,
|
|
(int)myPtr->fbo, (int)myPtr->sbid, (int)myPtr->entry);
|
|
|
|
rc = m_freeMgr.releaseSegment(m_cbTree, &m_rootBlock, TREE, (IdxTreeGroupType)segmentType,
|
|
myPtr /*, TREE */);
|
|
|
|
if (isDebug(DEBUG_3))
|
|
printf("\nReleased");
|
|
}
|
|
|
|
return rc;
|
|
}
|
|
|
|
const int IndexTree::resetIndexFile(const FID treeFid, const FID listFid)
|
|
{
|
|
/* long numOfBlock;
|
|
unsigned char writeBuf[BYTE_PER_BLOCK];
|
|
|
|
memset( writeBuf, 0, BYTE_PER_BLOCK );
|
|
numOfBlock = getFileSize( m_cbTree.file.pFile )/BYTE_PER_BLOCK;
|
|
for( int i = 0; i < numOfBlock; i++ )
|
|
fwrite( writeBuf, sizeof( writeBuf ), 1, m_cbTree.file.pFile );
|
|
|
|
numOfBlock = getFileSize( m_cbList.file.pFile )/BYTE_PER_BLOCK;
|
|
for( int i = 0; i < numOfBlock; i++ )
|
|
fwrite( writeBuf, sizeof( writeBuf ), 1, m_cbList.file.pFile );
|
|
*/
|
|
return initIndex(treeFid, listFid);
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Calculate bit test array for multi column index
|
|
* PARAMETERS:
|
|
* none
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::calculateBittestArray()
|
|
{
|
|
if (m_multiColKey.totalBit <= 0)
|
|
return ERR_INVALID_PARAM;
|
|
|
|
m_multiColKey.maxLevel = m_multiColKey.totalBit / 5 + 1;
|
|
|
|
if (m_multiColKey.maxLevel > IDX_MAX_MULTI_COL_IDX_LEVEL)
|
|
return ERR_VALUE_OUTOFRANGE;
|
|
|
|
for (int i = 0; i < m_multiColKey.maxLevel - 1; i++)
|
|
{
|
|
m_multiColKey.curBitset =
|
|
(m_multiColKey.bitSet & m_multiColKey.curMask) >> (IDX_MAX_MULTI_COL_BIT - (i + 1) * 5);
|
|
m_multiColKey.testbitArray[i] = m_multiColKey.curBitset.to_ulong();
|
|
m_multiColKey.curMask = m_multiColKey.curMask >> 5;
|
|
}
|
|
|
|
m_multiColKey.curBitset =
|
|
(m_multiColKey.bitSet & m_multiColKey.curMask) >> (IDX_MAX_MULTI_COL_BIT - m_multiColKey.totalBit);
|
|
m_multiColKey.testbitArray[m_multiColKey.maxLevel - 1] = m_multiColKey.curBitset.to_ulong();
|
|
return NO_ERROR;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Setup bit test array for multi column index
|
|
* PARAMETERS:
|
|
* keyArray - index key array
|
|
* totalByte - total byte in the key
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::setBitsetColumn(void* val, const int pos, const int width, const ColType colType)
|
|
{
|
|
int copyLen = width / 8;
|
|
|
|
switch (colType)
|
|
{
|
|
// No body is using float or double for indexing
|
|
/* case WriteEngine::WR_FLOAT : m_multiColKey.curBitset = *((float*) val);
|
|
break;
|
|
case WriteEngine::WR_DOUBLE : m_multiColKey.curBitset = *((double*) val);
|
|
break;
|
|
*/
|
|
case WriteEngine::WR_CHAR:
|
|
m_multiColKey.curBitset.reset();
|
|
|
|
for (int i = 0; i < width / 8; i++)
|
|
{
|
|
uint64_t curChar = ((char*)val)[i];
|
|
m_multiColKey.curBitset = m_multiColKey.curBitset << 8;
|
|
m_multiColKey.curBitset |= curChar;
|
|
}
|
|
|
|
memcpy(m_multiColKey.keyBuf + m_multiColKey.totalBit / 8, (char*)val, copyLen);
|
|
break;
|
|
|
|
case WriteEngine::WR_SHORT:
|
|
m_multiColKey.curBitset = *((short*)val);
|
|
memcpy(m_multiColKey.keyBuf + m_multiColKey.totalBit / 8, (short*)val, copyLen);
|
|
break;
|
|
|
|
case WriteEngine::WR_BYTE:
|
|
m_multiColKey.curBitset = *((char*)val);
|
|
memcpy(m_multiColKey.keyBuf + m_multiColKey.totalBit / 8, (char*)val, copyLen);
|
|
break;
|
|
|
|
case WriteEngine::WR_LONGLONG:
|
|
m_multiColKey.curBitset = *((long long*)val);
|
|
memcpy(m_multiColKey.keyBuf + m_multiColKey.totalBit / 8, (long long*)val, copyLen);
|
|
break;
|
|
|
|
case WriteEngine::WR_INT:
|
|
case WriteEngine::WR_MEDINT:
|
|
default:
|
|
memcpy(m_multiColKey.keyBuf + m_multiColKey.totalBit / 8, (int*)val, copyLen);
|
|
m_multiColKey.curBitset = *((int*)val);
|
|
break;
|
|
}
|
|
|
|
m_multiColKey.totalBit += width;
|
|
m_multiColKey.curBitset = m_multiColKey.curBitset << (IDX_MAX_MULTI_COL_BIT - m_multiColKey.totalBit);
|
|
m_multiColKey.bitSet |= m_multiColKey.curBitset;
|
|
return NO_ERROR;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Set bit test entry
|
|
* PARAMETERS:
|
|
* bittestEntry - the bit test entry
|
|
* testbitVal - current bit test value
|
|
* group - entry group
|
|
* fbo, sbid, entry - pointer address
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::setBittestEntry(IdxBitTestEntry* bittestEntry, const uint64_t testbitVal,
|
|
const uint64_t group, const uint64_t fbo, const uint64_t sbid,
|
|
const uint64_t entry, const uint64_t entryType) const
|
|
{
|
|
bittestEntry->type = entryType;
|
|
bittestEntry->bitTest = testbitVal;
|
|
bittestEntry->group = group;
|
|
bittestEntry->bitCompare = BIT_5;
|
|
bittestEntry->spare = 0;
|
|
|
|
bittestEntry->fbo = fbo;
|
|
bittestEntry->sbid = sbid;
|
|
bittestEntry->entry = entry;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Set empty list entry for free manager
|
|
* PARAMETERS:
|
|
* bittestEntry - the bit test entry
|
|
* testbitVal - current bit test value
|
|
* group - entry group
|
|
* fbo, sbid, entry - pointer address
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
// todo: need test case
|
|
void IndexTree::setEmptyListEntry(IdxEmptyListEntry* myEntry, const uint64_t group, const uint64_t fbo,
|
|
const uint64_t sbid, const uint64_t entry) const
|
|
{
|
|
myEntry->type = EMPTY_PTR;
|
|
myEntry->group = group;
|
|
myEntry->spare = 0;
|
|
myEntry->spare2 = 0;
|
|
myEntry->fbo = fbo;
|
|
myEntry->sbid = sbid;
|
|
myEntry->entry = entry;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Set the tree header node
|
|
* PARAMETERS:
|
|
* myTree - tree pointer
|
|
* key - index key
|
|
* width - key width
|
|
* rid - ROW ID
|
|
* testbitVal - bit test value at root level
|
|
* bitmapEntry - bitmap entry
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::setTreeHeader(IdxTree* myTree, const uint64_t key, const RID rid, const int width,
|
|
const int testbitVal, const IdxBitmapPointerEntry bitmapEntry)
|
|
{
|
|
IdxBitTestEntry nextEntry, curEntry;
|
|
|
|
myTree->width = width;
|
|
myTree->key = key;
|
|
myTree->rid = rid;
|
|
myTree->maxLevel = (width / 5) + 1;
|
|
|
|
setBlankEntry(&nextEntry);
|
|
setBlankEntry(&curEntry);
|
|
|
|
// myEntry.bitTest = testbitVal;
|
|
nextEntry.fbo = bitmapEntry.fbo;
|
|
nextEntry.sbid = bitmapEntry.sbid;
|
|
nextEntry.entry = bitmapEntry.entry;
|
|
nextEntry.type = BIT_TEST;
|
|
|
|
// nextEntry.group = ENTRY_32;
|
|
|
|
curEntry.fbo = 0;
|
|
curEntry.sbid = IDX_BITMAP_SUBBLOCK_NO;
|
|
curEntry.entry = testbitVal;
|
|
curEntry.type = BITMAP_PTR;
|
|
curEntry.group = ENTRY_32;
|
|
curEntry.bitTest = testbitVal;
|
|
|
|
// at this point useCount not known
|
|
setTreeNode(&myTree->node[0], 0, ENTRY_PER_SUBBLOCK, 0, testbitVal, nextEntry, curEntry);
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Set the tree node
|
|
* PARAMETERS:
|
|
* myNode - node pointer
|
|
* level - current tree level
|
|
* allocCount - allocated count
|
|
* useCount - used count
|
|
* offset - entry offset
|
|
* nextEntry - next entry
|
|
* curEntry - current entry
|
|
* RETURN:
|
|
* none
|
|
***********************************************************/
|
|
void IndexTree::setTreeNode(IdxTreeNode* myNode, const int level, const int allocCount, const int useCount,
|
|
const int offset, const IdxBitTestEntry nextEntry, const IdxBitTestEntry curEntry)
|
|
{
|
|
myNode->level = level;
|
|
myNode->allocCount = allocCount;
|
|
myNode->useCount = useCount;
|
|
myNode->offset = offset;
|
|
myNode->next = nextEntry;
|
|
myNode->current = curEntry;
|
|
myNode->used = true;
|
|
}
|
|
|
|
const bool IndexTree::isTreeEmpty()
|
|
{
|
|
bool bEmpty = true;
|
|
IdxBitmapPointerEntry curBitmapPointer, emptyPointer;
|
|
|
|
memset(&emptyPointer, 0, MAX_COLUMN_BOUNDARY);
|
|
|
|
for (int i = 0; i < 32; i++)
|
|
{
|
|
getSubBlockEntry(m_rootBlock.data, IDX_BITMAP_SUBBLOCK_NO, i, MAX_COLUMN_BOUNDARY, &curBitmapPointer);
|
|
|
|
if (memcmp(&curBitmapPointer, &emptyPointer, MAX_COLUMN_BOUNDARY))
|
|
{
|
|
bEmpty = false;
|
|
break;
|
|
}
|
|
}
|
|
|
|
// printMemSubBlock( &m_rootBlock, IDX_BITMAP_SUBBLOCK_NO );
|
|
return bEmpty;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Allocate Row ID
|
|
* PARAMETERS:
|
|
* tableFid - the file id for table bitmap file
|
|
* totalRow - the total number of rows need to be allocated
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* rowIdArray - allocation of the row id left here
|
|
***********************************************************/
|
|
const int IndexTree::updateIndex(const uint64_t key, const int width, const RID rid)
|
|
{
|
|
int rootTestbitVal, rc = NO_ERROR;
|
|
IdxBitmapPointerEntry curBitmapPointer;
|
|
|
|
clearTree(&m_tree);
|
|
|
|
getTestbitValue(key, width, 0, &rootTestbitVal);
|
|
getSubBlockEntry(m_rootBlock.data, IDX_BITMAP_SUBBLOCK_NO, rootTestbitVal, MAX_COLUMN_BOUNDARY,
|
|
&curBitmapPointer);
|
|
|
|
setTreeHeader(&m_tree, key, rid, width, rootTestbitVal, curBitmapPointer);
|
|
|
|
if (m_tree.maxLevel > IDX_MAX_TREE_LEVEL)
|
|
return ERR_VALUE_OUTOFRANGE;
|
|
|
|
if (isAddrPtrEmpty(&curBitmapPointer, (IdxTreeEntryType)curBitmapPointer.type))
|
|
rc = buildEmptyIndexTreeBranch(key, width, rid, rootTestbitVal);
|
|
else // at least we have the root level pointer
|
|
rc = buildExistIndexTreeBranch(key, width, rid, rootTestbitVal, curBitmapPointer);
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Dummy list addr generator
|
|
* PARAMETERS:
|
|
* key - index key
|
|
* width - key width
|
|
* rid - ROW ID
|
|
* myEntry - return entry with addr
|
|
* no - sequence no
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::updateIndexList(const uint64_t key, const int width, const RID rid,
|
|
IdxEmptyListEntry* myEntry, const int no, const bool addFlag)
|
|
{
|
|
int rc = NO_ERROR;
|
|
|
|
if (m_useListMgr)
|
|
{
|
|
// doing something here
|
|
if (!addFlag) // update list
|
|
{
|
|
if (m_useMultiRid)
|
|
rc = m_listMgr.updateIndexList(m_cbList, m_multiRid, key, myEntry);
|
|
else
|
|
rc = m_listMgr.updateIndexList(m_cbList, rid, key, myEntry);
|
|
}
|
|
else // add list
|
|
{
|
|
if (m_useMultiRid)
|
|
rc = m_listMgr.addIndexListHdr(m_cbList, m_multiRid, key, myEntry);
|
|
else
|
|
rc = m_listMgr.addIndexListHdr(m_cbList, rid, key, myEntry);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
myEntry->fbo = 3;
|
|
myEntry->sbid = 3;
|
|
myEntry->entry = 3 + no;
|
|
}
|
|
|
|
return rc;
|
|
}
|
|
|
|
/***********************************************************
|
|
* DESCRIPTION:
|
|
* Update the entry in index list file
|
|
* PARAMETERS:
|
|
* key - index key
|
|
* width - key width
|
|
* rid - ROW ID
|
|
* curLevel - current tree level
|
|
* group - current group
|
|
* allocCount - allocated count
|
|
* useCount - used count
|
|
* offset - entry offset
|
|
* RETURN:
|
|
* NO_ERROR if success
|
|
* error no if fail
|
|
***********************************************************/
|
|
const int IndexTree::updateListFile(const uint64_t key, const int width, const RID rid, const int curLevel,
|
|
const uint64_t group, const int allocCount, const int useCount,
|
|
const int offset, const bool addFlag)
|
|
{
|
|
int rc, testbitVal, parentLevel = curLevel - 1;
|
|
IdxEmptyListEntry listEntry;
|
|
IdxBitTestEntry bittestEntry, curEntry;
|
|
bool bSuccess;
|
|
DataBlock curBlock;
|
|
|
|
rc = readSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry + offset,
|
|
MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
if (!addFlag)
|
|
{
|
|
listEntry.fbo = bittestEntry.fbo;
|
|
listEntry.sbid = bittestEntry.sbid;
|
|
listEntry.entry = bittestEntry.entry;
|
|
}
|
|
|
|
rc = updateIndexList(key, width, rid, &listEntry, curLevel, addFlag);
|
|
|
|
if (rc != NO_ERROR)
|
|
return rc;
|
|
|
|
bSuccess = getTestbitValue(key, width, curLevel, &testbitVal);
|
|
setBittestEntry(&bittestEntry, testbitVal, group, listEntry.fbo, listEntry.sbid, listEntry.entry,
|
|
LEAF_LIST);
|
|
|
|
rc = writeSubBlockEntry(m_cbTree, &curBlock, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry + offset,
|
|
MAX_COLUMN_BOUNDARY, &bittestEntry);
|
|
|
|
setBittestEntry(&curEntry, testbitVal, group, m_tree.node[parentLevel].next.fbo,
|
|
m_tree.node[parentLevel].next.sbid, m_tree.node[parentLevel].next.entry, LEAF_LIST);
|
|
setTreeNode(&m_tree.node[curLevel], curLevel, allocCount, useCount, offset, bittestEntry, curEntry);
|
|
|
|
return rc;
|
|
}
|
|
|
|
} // namespace WriteEngine
|