//
// File: hzIsamT.cpp
//
// Legal Notice: This file is part of the HadronZoo C++ Class Library. Copyright 2025 HadronZoo Project (http://www.hadronzoo.com)
//
// The HadronZoo C++ Class Library is free software: You can redistribute it, and/or modify it under the terms of the GNU Lesser General Public License, as published by the Free
// Software Foundation, either version 3 of the License, or any later version.
//
// The HadronZoo C++ Class Library 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 Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License along with the HadronZoo C++ Class Library. If not, see http://www.gnu.org/licenses.
//
#include <iostream>
#include "hzString.h"
#include "hzLock.h"
#include "hzProcess.h"
#include "hzIsamT.h"
using namespace std ;
/*
** Definitions
*/
void _hz_vn_Idx::SetCumulatives (void)
{
// Set the cumulative count in an index node
_hz_vn_Any* pChild ; // Child node to examine
int32_t n ; // Child iterator
m_nCumulative = 0 ;
for (n = 0 ; n < usage ; n++)
{
//pChild = (_hz_vn_Any*) pIdx->m_Ptrs[n] ;
pChild = m_Ptrs[n] ;
m_nCumulative += pChild->Cumulative() ;
}
}
void _hz_tmpl_ISAM::_moveElement (_hz_vn_Dat* pNodeTgt, _hz_vn_Dat* pNodeSrc, uint32_t tgtSlot, uint32_t srcSlot)
{
// Move object from one bucket to another
_hzfunc("_hz_tmpl_ISAM::_moveElement") ;
uchar* pSrc ;
uchar* pTgt ;
if (!pNodeTgt || !pNodeSrc)
Fatal("Src node %p tgt node %p\n", pNodeTgt, pNodeSrc) ;
pSrc = (uchar*) pNodeSrc->m_pElements ;
pTgt = (uchar*) pNodeTgt->m_pElements ;
if (!pSrc || !pTgt)
Fatal("Src bucket %p tgt bucket %p\n", pSrc, pTgt) ;
if (m_nSizeKey)
{
pSrc += m_nSizeKey * srcSlot ;
pTgt += m_nSizeKey * tgtSlot ;
memcpy(pTgt, pSrc, m_nSizeKey) ;
memset(pSrc, 0, m_nSizeKey) ;
}
if (m_nSizeObj)
{
pSrc = (uchar*) pNodeSrc->m_pElements ;
pTgt = (uchar*) pNodeTgt->m_pElements ;
pSrc += (m_nSizeKey * HZ_T_ISAMNODE_FULL) + (m_nSizeObj * srcSlot) ;
pTgt += (m_nSizeKey * HZ_T_ISAMNODE_FULL) + (m_nSizeObj * tgtSlot) ;
memcpy(pTgt, pSrc, m_nSizeObj) ;
memset(pSrc, 0, m_nSizeObj) ;
}
}
_hz_vn_Dat* _hz_tmpl_ISAM::_allocDataSlot (_hz_vn_Dat* pDN, int32_t& nSlot)
{
// Support function to make space available as part of an INSERT operation. A target data node and slot are supplied and these will have been identified earlier by one of two
// means: Either _findDnodeByKey() within InsertKey() or _findDnodeByPos() within InsertPos().
//
// This function has the following outcomes:-
//
// 1) If the target is not full the new entry will be placed in the target at the designated slot, shifting entries above the slot up by one place.
//
// 2) If the target node is full but the target's infra node has space then one of two things will happen:-
//
// a) If the designated slot is 0 then the new entry will be placed directly in the top slot of the infra node.
//
// b) If the designated slot is above 0 then slot 0 of the target is moved to the top slot of the infra node, the designated slot is reduced by 1 and all
// slots lower than the new designated slot is shifted down one place.
//
// 3) If the target node is full and there is no room on an infra, there will always be room on an ultra node. This is because if the ultra does not exist or
// is full, a new ultra will be created. Then one of two things will happen:-
//
// a) If the designated slot is HZ_T_ISAMNODE_FULL (which is possible if _findDnodeByPos() is called with bExpand = true), then the new entry will be placed in slot 0 of
// the ultra node.
//
// b) If the designated slot is < HZ_T_ISAMNODE_FULL then the top slot of the target node is moved to slot 0 of the ultra and then the insert will proceed as in
// scenario (1)
//
// Arguments 1) The target data node
// 2) The slot
//
// Returns Pointer to the actual node the new entry resides in
//
// NOTE that neither this function or its caller, actually writes the element being inserted as this can only be done within the Insert of a fully qualified template.
_hzfunc("_hz_tmpl_ISAM::_allocDataSlot") ;
_hz_vn_Dat* pInfra = 0 ; // New data node
_hz_vn_Dat* pUltra = 0 ; // New data node
_hz_vn_Idx* pIdx ; // Index node (for updating cimulatives)
int32_t n ; // Loop controller
// Test inputs
if (!pDN)
Fatal("isam=%d (%s): No taget data node supplied\n", m_isamId, *m_Name) ;
if (pDN->Usage() > HZ_T_ISAMNODE_FULL) Fatal("Isam=%d (%s): Garbage usage value (%d)\n", m_isamId, *m_Name, n) ;
if (nSlot > HZ_T_ISAMNODE_FULL) Fatal("Isam=%d (%s): Illegal slot value (%d)\n", m_isamId, *m_Name, nSlot) ;
if (nSlot > pDN->Usage()) Fatal("Isam=%d (%s): Excessive slot value (%d)\n", m_isamId, *m_Name, nSlot) ;
m_nElements++ ;
if (nSlot < HZ_T_ISAMNODE_FULL)
{
// Target slot within target node (only way the slot can be HZ_T_ISAMNODE_FULL is if the target data node is the highest one)
if (pDN->Usage() < HZ_T_ISAMNODE_FULL)
{
// New element can be accomodated on this node so add it and return
for (n = pDN->Usage() ; n > nSlot ; n--)
_moveElement(pDN, pDN, n, n-1) ;
pDN->IncUsage() ;
for (pIdx = pDN->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->m_nCumulative++ ;
return pDN ;
}
// Node is full so check if first element can be moved to the infra node, if it exists.
pInfra = (_hz_vn_Dat*) pDN->Infra() ;
if (pInfra && pInfra->Usage() < HZ_T_ISAMNODE_FULL)
{
// Space found on infra node
if (nSlot == 0)
{
// Store new object direcly in top slot in infra node
nSlot = pInfra->Usage() ;
pInfra->IncUsage() ;
for (pIdx = pInfra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->m_nCumulative++ ;
//pIdx->SetCumulatives() ;
return pInfra ;
}
// Move element 0 to infra node, decrement slot move all elements upto slot down one place, store object in slot
_moveElement(pInfra, pDN, pInfra->Usage(), 0) ;
pInfra->IncUsage() ;
for (pIdx = pInfra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->m_nCumulative++ ;
//pIdx->SetCumulatives() ;
nSlot-- ;
for (n = 0 ; n < nSlot ; n++)
_moveElement(pDN, pDN, n, n+1) ;
return pDN ;
}
}
// No room on the infra so we try the ultra. If this is not present or full, create a new empty ultra.
pUltra = pDN->Ultra() ;
if (!pUltra || pUltra->Usage() == HZ_T_ISAMNODE_FULL)
{
// Could not find space on either infra or ultra node so create a new ultra node
if (!pUltra)
{
pUltra = pDN->ultra = new _hz_vn_Dat ;
pUltra->infra = pDN ;
}
else
{
pUltra->infra = pDN->ultra = new _hz_vn_Dat ;
pUltra->infra->ultra = pUltra ;
pUltra->infra->infra = pDN ;
pUltra = pUltra->infra ;
}
pUltra->parent = pDN->parent ;
pUltra->m_isamId = m_isamId ;
pUltra->m_pElements = new uchar[HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)] ;
memset(pUltra->m_pElements, 0, HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)) ;
// Put this new node into the index
_allocIndxSlot(pDN, pUltra) ;
if (nSlot == HZ_T_ISAMNODE_FULL)
{
// This can only happen when current data node is the last. We can directly load into slot 0 of the new ultra node
pUltra->IncUsage() ;
for (pIdx = pUltra->parent ; pIdx ; pIdx = pIdx->parent)
//pIdx->m_nCumulative++ ;
pIdx->SetCumulatives() ;
nSlot = 0 ;
return pUltra ;
}
}
if (pUltra && pUltra->Usage() < HZ_T_ISAMNODE_FULL)
{
// Space found on ultra node so move top element to it
for (n = pUltra->Usage() ; n ; n--)
_moveElement(pUltra, pUltra, n, n-1) ;
_moveElement(pUltra, pDN, 0, pDN->Usage()-1) ;
pUltra->IncUsage() ;
pDN->DecUsage() ;
// Now insert new element in current node
for (n = pDN->Usage() ; n > nSlot ; n--)
_moveElement(pDN, pDN, n, n-1) ;
pDN->IncUsage() ;
for (pIdx = pDN->parent ; pIdx ; pIdx = pIdx->parent)
//pIdx->m_nCumulative++ ;
pIdx->SetCumulatives() ;
if (pDN->parent != pUltra->parent)
for (pIdx = pUltra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->SetCumulatives() ;
return pDN ;
}
threadLog("unhandled case\n") ;
return pDN ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::_expelDataSlot (_hz_vn_Dat* pDN, int32_t nSlot)
{
// The node can be removed if empty or if all remaining elements can be migrated to its infra and ultra adjacents. By convention we migrate what
// we can to the infra adjacent first and then migrate any remaining to the ultra adjacent.
//
// Arguments: 1) pDN The node from which an element is to be removed
// 2) nSlot The slot number of the depricated element
//
// Returns: Pointer to the current node remanent
// NULL if the current node is emptied by this action
//
// Note: In most cases, the return is ignored by the caller.
_hzfunc("_hz_tmpl_ISAM::_expelDataSlot") ;
_hz_vn_Idx* pPar ; // For setting cumulatives in index
_hz_vn_Dat* pInfra ; // For setting cumulatives in index
_hz_vn_Dat* pUltra ; // For setting cumulatives in index
uchar* pKeys ; // Keys on node
int32_t x = 0 ; // Loop control, doubles as No of elements moved to infra
int32_t y = 0 ; // Loop control, doubles as No of elements moved to ultra
uint32_t ino ; // ISAM number
// Test inputs
if (!pDN)
Fatal("Isam=%d (%s): No taget data node supplied\n", m_isamId, *m_Name) ;
ino = pDN->IsamId() ;
if (pDN->Usage() > HZ_T_ISAMNODE_FULL) Fatal("Isam=%d (%s): Garbage usage value (%d)\n", m_isamId, *m_Name, x) ;
if (nSlot < 0 || nSlot > HZ_T_ISAMNODE_FULL) Fatal("Isam=%d (%s): Illegal slot value (%d)\n", m_isamId, *m_Name, nSlot) ;
if (nSlot >= pDN->Usage()) Fatal("Isam=%d (%s): Excessive slot value (%d)\n", m_isamId, *m_Name, nSlot) ;
m_nElements-- ;
// Exclude the slot
pDN->DecUsage() ;
for (x = nSlot, y = pDN->Usage() ; x < y ; x++)
_moveElement(pDN, pDN, x, x+1) ;
// Set end slot to null
pKeys = (uchar*) pDN->m_pElements ;
memset(pKeys + (pDN->Usage() * m_nSizeKey), 0, m_nSizeKey) ;
// Decrement parent cumulatives
for (pPar = pDN->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative-- ;
pPar->SetCumulatives() ;
// See if reduced node can be purged
if (pDN->Usage() && pDN->Usage() < HZ_T_ISAMNODE_LOW)
{
pInfra = (_hz_vn_Dat*) pDN->Infra() ;
pUltra = (_hz_vn_Dat*) pDN->Ultra() ;
x = pInfra ? HZ_T_ISAMNODE_FULL - pInfra->Usage() : 0 ;
y = pUltra ? HZ_T_ISAMNODE_FULL - pUltra->Usage() : 0 ;
if ((x + y) >= pDN->Usage())
{
// All remaining slots on this node can be accomodated by adjacents. Begin by moving all that we can to infra node first
x = y = 0 ;
if (pInfra && pInfra->Usage() < HZ_T_ISAMNODE_FULL)
{
for (x = 0 ; pDN->Usage() && pInfra->Usage() < HZ_T_ISAMNODE_FULL ; x++)
{
//pInfra->setfromUlt(pInfra->Usage(), x) ;
_moveElement(pDN, pUltra, pInfra->Usage(), x) ;
pInfra->IncUsage() ;
pDN->DecUsage() ;
}
for (pPar = pInfra->Parent() ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += x ;
pPar->SetCumulatives() ;
if (pInfra->IsamId() != ino || pInfra->Usage() < 0 || pInfra->Usage() > HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d (%s): Infra %d Invalid: isam id (%d) usage (%d)\n", ino, *m_Name, pInfra->Ident(), pInfra->IsamId(), pInfra->Usage()) ;
}
if (pUltra && pDN->Usage() && pUltra->Usage() < HZ_T_ISAMNODE_FULL)
{
// If any elements remain on the current block we need to shift upwards the elements on the ultra to accomodate them
for (y = pUltra->Usage() + pDN->Usage() - 1 ; y >= pDN->Usage() ; y--)
_moveElement(pDN, pDN, y, y-pDN->Usage()) ;
//pUltra->setfromCur(y, y - pDN->Usage()) ;
pUltra->SetUsage(pUltra->Usage() + pDN->Usage()) ;
// Move remainder to ultra node
for (y = 0 ; y < pDN->Usage() ; y++)
_moveElement(pDN, pInfra, y, x+y) ;
//pUltra->setfromInf(y, x + y) ;
pDN->SetUsage(0) ;
for (pPar = pUltra->Parent() ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += y ;
pPar->SetCumulatives() ;
if (pUltra->IsamId() != ino || pUltra->Usage() < 0 || pUltra->Usage() > HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d (%s): Ultra %d Invalid: isam id (%d) usage (%d)\n", ino, *m_Name, pUltra->Ident(), pUltra->IsamId(), pUltra->Usage()) ;
}
x += y ;
for (pPar = pDN->Parent() ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative -= x ;
pPar->SetCumulatives() ;
}
}
if (pDN->Usage())
return pDN ;
// Eliminate node: Connect adjacents
pInfra = pDN->Infra() ;
pUltra = pDN->Ultra() ;
if (pUltra)
pUltra->SetInfra(pInfra) ;
if (pInfra)
pInfra->SetUltra(pUltra) ;
if (pDN->Parent())
_expelIndxSlot(pDN->Parent(), pDN) ;
else
{
delete pDN ;
m_pRoot = 0 ;
}
return 0 ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::_findDnodeByPos (int32_t& nSlot, uint32_t nPosn, bool bExpand) const
{
// Purpose: This function finds for an absolute element position, the data node and slot where the element resides. It is the first of three 'data-node
// locator' functions and the only one that can reside in a base ISAM as it does not rely on key comparison. These functions are critical since
// all access to elements depend on them.
//
// Method: Starting at the root we add up the cumulatives until they exceed the required position. Then go up to the next level and do the same.
// The exceptions to this are where there is no data and therefore no root or where the only node is the root.
//
// Arguments: 1) nSlot A reference to store the node offset of the element
// 2) nPosn The required position
// 3) bExpand Expand flag. If set function can find the end postion + 1 (set for insert, clear for lookup)
//
// Returns: Pointer to the data node for the element
_hzfunc("_hz_tmpl_ISAM::_findDnodeByPos") ;
_hz_vn_Idx* pIdx = 0 ; // Current index node
_hz_vn_Any* pChild = 0 ; // Can be index node or outer level data node
_hz_vn_Dat* pDN = 0 ; // Target data node
uint32_t nStart = 0 ; // True starting position of current node as per cumulatives
uint32_t nMin = 0 ; // The real position within the collection of the current node's lowest element.
uint32_t nMax = 0 ; // The real position within the collection of the current node's lowest element plus current node usage
int32_t n ; // Element iterator
// Check if there is a root
if (!this)
Fatal("No instance\n") ;
if (!m_pRoot)
{ nSlot = -1 ; return 0 ; }
// Check limits
nMax = bExpand ? m_pRoot->Cumulative() : m_pRoot->Cumulative()-1 ;
if (nPosn > nMax)
{ nSlot = -1 ; return 0 ; }
// If the root is the only node
if (m_pRoot->Level() == 0)
{
pDN = (_hz_vn_Dat*) m_pRoot ;
nSlot = nPosn ;
return pDN ;
}
// Common case, start at root which is an index node
pIdx = (_hz_vn_Idx*) m_pRoot ;
nMax = nMin = nStart = 0 ;
for (;;)
{
// Look on the node for the offset/pointer to the next node or the
nMin = nStart ;
if (!pIdx->Usage())
Fatal("Empty index node %p\n", pIdx) ;
for (n = 0 ; n < pIdx->Usage() ; n++)
{
pChild = (_hz_vn_Any*) pIdx->m_Ptrs[n] ;
if (!pChild)
Fatal("Isam=%d (%s): Missing node pointer on non leaf node\n", m_isamId, *m_Name) ;
if (pChild->Parent() != pIdx)
Fatal("isam=%d (%s): Child node %p (level %d) does not point back to current node %p (level %d)\n", m_isamId, *m_Name, pChild, pChild->Level(), pIdx, pIdx->level) ;
// If the cumulative exceeds the desired posn we have the node
nStart = nMin ;
nMax = nMin + pChild->Cumulative() ;
if (nPosn < nMax)
break ;
nMin = nMax ;
}
// Go to next level or accept data node as target
if (pChild->Level())
pIdx = (_hz_vn_Idx*) pChild ;
else
{
pDN = (_hz_vn_Dat*) pChild ;
break ;
}
}
nSlot = nPosn - nStart ;
if (pDN && nSlot > pDN->Usage())
Fatal("Isam=%d (%s): Node %d usage %u has offset %u\n", m_isamId, *m_Name, pDN->Ident(), pDN->Usage(), nSlot) ;
return pDN ;
}
hzEcode _hz_tmpl_ISAM::_allocIndxSlot (_hz_vn_Any* pOld, _hz_vn_Any* pNew)
{
// This function is called when a node (pOld) spawns an ultra sibling (pNew). Note that nodes never spawn infra siblings. pOld and pNew can be either a pair of data nodes or a
// pair of index nodes. Both must be supplied and both must be at the same level.
//
// pOld as the established node, will either have a parent or be the root. Adding a sibling to the root always results in a new root, in which case, both pOld and pNew become
// child nodes of the new root.
//
// Where pOld already has a parent, the action is to add pNew to the parent's list of child nodes, one place up from where pOld is placed. As a result of this action, pOld and
// pNew may have the same parent OR the parent of pNew can be the ultra sibling of the parent of pOld. It is possible for pOld to become a child of its original parent'e infra
// sibling. This function will set the parents of both pOld and pNew accordingly.
//
//
//
// having different parents
// The action takes place in the parent of pOld
//
// This function is called on an index node which may have either data or index node pointers as elements, but when a child node pOld spawns an ultra sibling pNew. Note that
// nodes never spawn infra siblings. The action is to find the slot occupied by pOld and place pNew in the next slot up. This is an insert action with all elements higher than pOld moving up one place to make room for pNew.
//
// In the event the current node pCur is null this is because pOld is currently the root and has no parent. A new root is formed with pOld in slot 0 and pNew
// (which must be pOld's ultra node) in slot 1.
//
// In the event the current node is full we first check if the infra exists and has space. If it does we move slot 0 to the top slot of the infra, move
// elements upto and including pOld down one place and put pNew in pOld's former slot. If the infra is full we see if a ultra has space. If not create
// a new ultra node. We then insert this node's top top element in the ultra's slot 0. In the special case where pOld is in the top slot of this node
// we just put pNew in the ultra slot 0.
//
// Note that if a new ultra sibling is created a pointer to it must be entered in the parent node. _allocIndxSlot() is called on the parent node with this node
// as pOld and the new sibling as pNew. If there is no parent a parent is created and both this node as the sibling added as children. This new parent node
// is returned. The calling function (_allocDataSlot) then sets this as the new root to the ISAM.
//
// Arguments: 1) pOld The pointer to the pre-existing node (prognitor)
// 2) pNew The pointer to the newly created ultra sibling of the prognitor
//
// Returns: E_OK Always
_hzfunc("_hz_tmpl_ISAM::_allocIndxSlot") ;
_hz_vn_Any* pNode = 0 ; // Shift element
_hz_vn_Idx* pIdxNew = 0 ; // New ultra sibling
_hz_vn_Idx* pCur = 0 ; // Original parent of pOld
_hz_vn_Idx* pPar = 0 ; // Parent for cumulatives
int32_t slot = 0 ; // Slot found for existing pOld
int32_t n = 0 ; // Slot iterator
int32_t za ; // Shift cumulative 1
int32_t zb ; // Shift cumulative 2
// Verify arguments
if (!pOld) Fatal("Isam=%d (%s): No pre-existing item supplied\n", m_isamId, *m_Name) ;
if (!pNew) Fatal("Isam=%d (%s): No new item supplied\n", m_isamId, *m_Name) ;
if (pNew->Infra() != pOld) Fatal("Isam=%d (%s): new %p does not point back to old %p\n", m_isamId, *m_Name, pNew, pOld) ;
if (pOld->Ultra() != pNew) Fatal("Isam=%d (%s): old %p does not point forward to new %p\n", m_isamId, *m_Name, pOld, pNew) ;
// Do we need a new root?
if (!pOld->Parent())
{
pIdxNew = new _hz_vn_Idx() ;
pIdxNew->m_Ptrs[0] = pOld ;
pIdxNew->m_Ptrs[1] = pNew ;
pOld->SetParent(pIdxNew) ;
pNew->SetParent(pIdxNew) ;
pIdxNew->m_isamId = m_isamId ;
pIdxNew->usage = 2 ;
pIdxNew->m_nCumulative = pOld->Cumulative() + pNew->Cumulative() ;
pIdxNew->level = pOld->Level()+1 ;
m_pRoot = pIdxNew ;
return E_OK ;
}
// Given we have a current node, further checks
pCur = pOld->Parent() ;
if ((pOld->Level()+1) != pCur->level) Fatal("Isam=%d (%s): At level %d but old element level is %d\n", m_isamId, *m_Name, pCur->level, pOld->Level()) ;
if ((pNew->Level()+1) != pCur->level) Fatal("Isam=%d (%s): At level %d but new element level is %d\n", m_isamId, *m_Name, pCur->level, pNew->Level()) ;
if (!pNew->Parent())
pNew->SetParent(pCur) ;
if (pNew->Parent() != pCur)
Fatal("Isam=%d (%s): new node %p does not have this node (%p) as its parent. Instead it has %p\n", m_isamId, *m_Name, pNew, pCur, pNew->Parent()) ;
// Find out which slot pOld is on
for (slot = 0 ; slot < pCur->usage ; slot++)
{
if (pCur->m_Ptrs[slot] == pOld)
break ;
}
if (slot == pCur->usage)
Fatal("Isam=%d (%s): On node %p: Child node %p not found\n", m_isamId, *m_Name, pCur, pOld) ;
slot++ ;
// If there is space on this node just insert the new element
if (pCur->usage < HZ_T_ISAMNODE_FULL)
{
pNew->SetParent(pCur) ;
for (n = pCur->usage ; n > slot ; n--)
pCur->m_Ptrs[n] = pCur->m_Ptrs[n-1] ;
pCur->m_Ptrs[slot] = pNew ;
pCur->usage++ ;
// Update cumulatives
//pCur->m_nCumulative += pNew->Cumulative() ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += pNew->Cumulative() ;
pPar->SetCumulatives() ;
return E_OK ;
}
// This node is full so we first see if we have an infra and with space
if (pCur->infra && pCur->infra->usage < HZ_T_ISAMNODE_FULL)
{
// Move element 0 to infra node
pNode = pCur->m_Ptrs[0] ;
za = pNode->Cumulative() ;
pNode->SetParent(pCur->infra) ;
pCur->infra->m_Ptrs[pCur->infra->usage] = pNode ;
pCur->infra->usage++ ;
// Insert the new element
slot-- ;
for (n = 0 ; n < slot ; n++)
pCur->m_Ptrs[n] = pCur->m_Ptrs[n+1] ;
zb = pNew->Cumulative() ;
pNew->SetParent(pCur) ;
pCur->m_Ptrs[slot] = pNew ;
// Update cumulatives
pCur->infra->m_nCumulative += za ;
pCur->m_nCumulative += (zb - za) ;
if (pCur->parent == pCur->infra->parent)
{
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += zb ;
pPar->SetCumulatives() ;
}
else
{
for (pPar = pCur->infra->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += za ;
pPar->SetCumulatives() ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += (zb - za) ;
pPar->SetCumulatives() ;
}
return E_OK ;
}
// No room on the infra so we try the ultra. If full or non-existant, create an empty one.
if (!pCur->ultra || pCur->ultra->usage == HZ_T_ISAMNODE_FULL)
{
pIdxNew = new _hz_vn_Idx ;
if (!pIdxNew)
Fatal("Could not allocate sibling\n") ;
pIdxNew->m_isamId = m_isamId ;
pIdxNew->level = pCur->level ;
if (pCur->ultra)
pCur->ultra->infra = pIdxNew ;
pIdxNew->ultra = pCur->ultra ;
pIdxNew->infra = pCur ;
pCur->ultra = pIdxNew ;
// The new sibling must be given a parent.
_allocIndxSlot(pCur, pIdxNew) ;
}
// OK now we can boogie as there is a ultra with space and parent
if (slot == HZ_T_ISAMNODE_FULL)
{
// pOld is in this node's top slot so pNew goes into slot 0 of ultra
zb = pNew->Cumulative() ;
for (n = pCur->ultra->usage ; n ; n--)
pCur->ultra->m_Ptrs[n] = pCur->ultra->m_Ptrs[n-1] ;
pCur->ultra->m_Ptrs[0] = pNew ;
pNew->SetParent(pCur->ultra) ;
pCur->ultra->usage++ ;
pCur->ultra->m_nCumulative += zb ;
for (pPar = pCur->ultra->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += zb ;
pPar->SetCumulatives() ;
return E_OK ;
}
// Higest element of this node goes into slot 0 of ultra, then new element inserted into this node
for (n = pCur->ultra->usage ; n ; n--)
pCur->ultra->m_Ptrs[n] = pCur->ultra->m_Ptrs[n-1] ;
pNode = pCur->m_Ptrs[pCur->usage-1] ;
za = pNode->Cumulative() ;
pNode->SetParent(pCur->ultra) ;
pCur->ultra->m_Ptrs[0] = pNode ;
pCur->ultra->usage++ ;
pCur->ultra->m_nCumulative += za ;
// Insert new element into this node
zb = pNew->Cumulative() ;
for (n = pCur->usage-1 ; n > slot ; n--)
pCur->m_Ptrs[n] = pCur->m_Ptrs[n-1] ;
pCur->m_Ptrs[slot] = pNew ;
pCur->m_nCumulative += (zb - za) ;
if (pCur->parent == pCur->ultra->parent)
{
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += zb ;
pPar->SetCumulatives() ;
}
else
{
for (pPar = pCur->ultra->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += za ;
pPar->SetCumulatives() ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += (zb - za) ;
pPar->SetCumulatives() ;
}
return E_OK ;
}
void _hz_tmpl_ISAM::_expelIndxSlot (_hz_vn_Idx* pCur, _hz_vn_Any* pChild)
{
// Expel the defunct child from this node. If this action leaves the current node disposable (empty or sparse enough to migrate its elements to its siblings)
// the current node will be excluded from its peers by connecting the infra and ultra siblings to each other. In this event and if this node has a parent
// ExpelIndex is called for the parent with this node as the child to be disposed of.
//
// Arguments: 1) pCur Parent ISAM block
// 2) pChild Child ISAM block to be removed
//
// Returns: None
_hzfunc("_hz_vn_Idx::_expelIndxSlot") ;
_hz_vn_Any* pXfer ; // Element (block pointer) being moved
_hz_vn_Idx* pPar = 0 ; // Parent for cumulatives
int32_t x = 0 ; // No of elements moved to infra
int32_t y = 0 ; // Offset into current node for copying elements to ultra
int32_t slot ; // Slot of element being deleted
int32_t za = 0 ; // Shift cumulative 1
int32_t zb = 0 ; // Shift cumulative 2
if (!pCur) Fatal("Isam=%d (%s): No node supplied from which to expell\n", *m_Name, m_isamId) ;
if (!pChild) Fatal("Isam=%d (%s): No child node supplied to expell from node %p\n", m_isamId, *m_Name, pCur) ;
for (slot = 0 ; slot < pCur->usage ; slot++)
{
if (pCur->m_Ptrs[slot] == pChild)
break ;
}
if (slot == pCur->usage)
Fatal("Isam=%d (%s): No pointer to depricated child node found on this node (%p)\n", m_isamId, *m_Name, pCur) ;
if (slot < 0 || slot >= pCur->usage)
Fatal("Isam=%d (%s): Node %p Illegal slot value (%d)\n", m_isamId, *m_Name, pCur, slot) ;
pCur->usage-- ;
for (x = slot, y = pCur->usage ; x < y ; x++)
pCur->m_Ptrs[x] = pCur->m_Ptrs[x+1] ;
pCur->m_Ptrs[pCur->usage] = 0 ;
pCur->m_nCumulative -= pChild->Cumulative() ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative -= pChild->Cumulative() ;
pPar->SetCumulatives() ;
delete pChild ;
if (pCur->usage && pCur->usage < HZ_T_ISAMNODE_LOW)
{
// Now that an entry has been removed, can we merge the current node with either or both adjacents?
x = pCur->infra ? HZ_T_ISAMNODE_FULL - pCur->infra->usage : 0 ;
y = pCur->ultra ? HZ_T_ISAMNODE_FULL - pCur->ultra->usage : 0 ;
if ((x + y) >= pCur->usage)
{
// Move all that we can to infra node first
if (pCur->infra && pCur->infra->usage < HZ_T_ISAMNODE_FULL)
{
for (x = 0 ; pCur->usage && pCur->infra->usage < HZ_T_ISAMNODE_FULL ; x++)
{
pXfer = pCur->m_Ptrs[x] ;
pXfer->SetParent(pCur->infra) ;
pCur->infra->m_Ptrs[pCur->infra->usage] = pXfer ;
za += pXfer->Cumulative() ;
pCur->infra->usage++ ;
pCur->usage-- ;
}
pCur->infra->m_nCumulative += za ;
for (pPar = pCur->infra->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += za ;
pPar->SetCumulatives() ;
}
if (pCur->ultra && pCur->ultra->usage < HZ_T_ISAMNODE_FULL)
{
// If any elements remain on the current block we need to shift upwards the elements on the ultra to accomodate them
for (y = pCur->ultra->usage + pCur->usage - 1 ; y >= pCur->usage ; y--)
pCur->ultra->m_Ptrs[y] = pCur->ultra->m_Ptrs[y - pCur->usage] ;
// Move remainder to ultra node
for (y = 0 ; y < pCur->usage ; y++)
{
pXfer = pCur->m_Ptrs[x + y] ;
pXfer->SetParent(pCur->ultra) ;
pCur->ultra->m_Ptrs[y] = pXfer ;
zb += pXfer->Cumulative() ;
}
pCur->usage = 0 ;
pCur->ultra->m_nCumulative += zb ;
pCur->ultra->usage += y ;
for (pPar = pCur->ultra->parent ; pPar ; pPar = pPar->parent)
//pPar->m_nCumulative += zb ;
pPar->SetCumulatives() ;
}
}
}
if (!pCur->usage)
{
// Connect adjacents
if (pCur->ultra)
pCur->ultra->infra = pCur->infra ;
if (pCur->infra)
pCur->infra->ultra = pCur->ultra ;
if (pCur->parent)
_expelIndxSlot(pCur->parent, pCur) ;
}
}
_hz_vn_Dat* _hz_tmpl_ISAM::_findDnodeByKey (int32_t& nSlot, const void* pKey, _hz_sbias eBias) const
{
// Find data node and slot for the supplied key and bias.
//
// This is the second data-node locator function and is best suited to unique key ISAMs. On the assumption the ISAM in question is in ascending
// order KEY value, this function supports searches of type HZ_ISAMSRCH_LO and HZ_ISAMSRCH_UIN.
//
// Note this function impliments a binary chop using 'pointer forwarding'. The lookup begins with a binary chop on the root node but since the
// elements for comparison are found only on data nodes, when on an index node we recurively follow the pointers to the zeroth element on the
// next node up until we are on a data node. Then we do the compare as though the data node value was the value of the slot in the (current)
// index node. We then follow the winning slot up the next level and binary chop that. Eventually we get to binary chop a data node and get the
// actual position that either matches the key or is just above or just below the key.
//
// Arguments: 1) A reference to store the node offset of the element
// 2) The isam to be searched
// 3) The search key
// 4) The pointer to the compare function
// 5) The lookup bias (HZ_ISAMSRCH_LO/HZ_ISAMSRCH_HI)
//
// Returns: Pointer to the data node if the key is matched,
// NULL pointer otherwise.
_hzfunc("_hz_tmpl_ISAM::_findDnodeByKey") ;
_hz_vn_Dat* pTgt = 0 ; // Target data node
_hz_vn_Dat* pTst = 0 ; // Test data node (from forward winding pointer)
_hz_vn_Idx* pIdx = 0 ; // Current index node
_hz_vn_Idx* pFwd = 0 ; // Forward pointer
int32_t nRes ; // Comparison result
int32_t nPos ; // Middle of index
int32_t nDiv ; // Divider
// If no root, retunr
nSlot = -1 ;
if (!Root())
return 0 ;
// Find target data node
if (Root() && Level() == 0)
pTgt = (_hz_vn_Dat*) Root() ;
else
{
// Determine next level node
for (pIdx = (_hz_vn_Idx*) Root() ; pIdx ;)
{
for (nPos = HZ_T_ISAMNODE_FULL - 1, nDiv = HZ_T_ISAMNODE_HALF ;; nDiv /= 2)
{
if (nPos >= pIdx->usage)
{
if (!nDiv)
{ nPos = pIdx->usage - 1 ; break ; }
nPos -= nDiv ;
continue ;
}
if (pIdx->level == 1)
pTst = (_hz_vn_Dat*) pIdx->m_Ptrs[nPos] ;
else
{
for (pFwd = (_hz_vn_Idx*) pIdx->m_Ptrs[nPos] ; pFwd->Level() > 1 ; pFwd = (_hz_vn_Idx*) pFwd->m_Ptrs[0]) ;
pTst = (_hz_vn_Dat*) pFwd->m_Ptrs[0] ;
}
// Now do the compare
nRes = m_compare(pKey, pTst, 0) ;
if (!nRes)
{ pTgt = pTst ; break ; }
if (nRes < 0)
{
if (nPos == 1)
{ nPos = 0 ; break ; }
if (!nDiv)
{ nPos-- ; break ; }
nPos -= nDiv ;
}
else
{
if (pIdx->usage == (nPos+1))
break ;
if (!nDiv)
break ;
nPos += nDiv ;
}
}
if (pTgt)
break ;
if (pIdx->Level() > 1)
pIdx = (_hz_vn_Idx*) pIdx->m_Ptrs[nPos] ;
else
{ pTgt = (_hz_vn_Dat*) pIdx->m_Ptrs[nPos] ; break ; }
}
}
if (!pTgt)
return 0 ;
// Identify the exact slot
for (nRes = 0, nSlot = HZ_T_ISAMNODE_FULL - 1, nDiv = HZ_T_ISAMNODE_HALF ;; nDiv /= 2)
{
// Ignore positions higher than highest used slot
if (nSlot >= pTgt->Usage())
{
nRes = 1 ;
if (!nDiv)
{ nSlot = pTgt->Usage() ; break ; }
nSlot -= nDiv ;
continue ;
}
// Do the compare
nRes = m_compare(pKey, pTgt, nSlot) ;
if (nRes == 0)
break ;
if (!nDiv)
break ;
if (nRes > 0)
nSlot += nDiv ;
else
nSlot -= nDiv ;
}
if (eBias == HZ_ISAMSRCH_LO)
{
// Exact match
if (nRes)
return 0 ;
if (nSlot >= pTgt->Usage())
Fatal("Isam=%d: Node %d usage %d has offset %d\n", IsamId(), pTgt->Ident(), pTgt->Usage(), nSlot) ;
return pTgt ;
}
// Deal with HZ_ISAMSRCH_END for inserts.
if (nRes > 0)
{
if (nSlot < pTgt->Usage())
nSlot++ ;
if (nSlot == HZ_T_ISAMNODE_FULL && pTgt->Ultra())
{
pTgt = (_hz_vn_Dat*) pTgt->Ultra() ;
nSlot = 0 ;
}
}
if (nSlot > pTgt->Usage())
Fatal("Isam=%d: Node %d usage %d has offset %d\n", IsamId(), pTgt->Ident(), pTgt->Usage(), nSlot) ;
return pTgt ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::_findAllByKey (int32_t& nSlot, uint32_t& nAbs, const void* pKey, _hz_sbias eBias) const
{
// Category: Collection Support
//
// This is the final data-node locator function. On the assumption the ISAM is in ascending order of KEY
// value, this function supports searches of types HZ_ISAMSRCH_LO, HZ_ISAMSRCH_HI and HZ_ISAMSRCH_END. It also provides the absolute position of
// the element in the ISAM in order to facilitate numeric iteration.
//
// This function impliments a binary chop using relative positions. The ISAM is treated as an array and numerically chopped using _findDnodeByPos(). If
// matches are found the lowest and highest matches are recorded. The nature of the chop is such that, assuming the ISAM elements are actually
// ordered, once a match is found the final test position must be within one place of either the lowest or the highest match. On the first match,
// both the lowest and highest matches are set to the position and it is possible, if this occurs ...
//
// Arguments: 1) A reference to store the absolute position
// 2) A reference to store the node offset of the element
// 3) The isam to be searched
// 4) The search key
// 5) The pointer to the compare function
// 6) The lookup bias (HZ_ISAMSRCH_LO/HZ_ISAMSRCH_HI)
//
// Returns: Pointer to the data node if the key is matched,
// NULL pointer otherwise.
//
// Note that numeric iterators are invalidated by insert and delete operations.
_hzfunc("_hz_tmpl_ISAM::_findAllByKey") ;
_hz_vn_Dat* pDN = 0 ; // Target data node
_hz_vn_Dat* pMK = 0 ; // Marked data node
uint32_t max ; // Top position
uint32_t posn ; // Test position
uint32_t posnMk ; // Marked position
int32_t slot ; // Slot
uint32_t slotMk ; // Marked slot
uint32_t nDiv ; // divider
int32_t res ; // result of compare
// if (eBias != HZ_ISAMSRCH_LO && eBias != HZ_ISAMSRCH_HI && eBias != HZ_ISAMSRCH_END)
// Fatal("_findAbsoluteByKey: Illegal bias %d", eBias) ;
nAbs = nSlot = posnMk = slotMk = 0xffffffff ;
if (!Root())
return 0 ;
// Set up initial test position and the divider
max = Count()-1 ;
for (posn = 2 ; posn < max ; posn *= 2) ;
nDiv = posn / 2 ;
posn-- ;
// Run up and down collection until we can divide no more
for (;;)
{
// Ignore positions higher than highest used slot
if (posn > max)
{
res = -1 ;
if (!nDiv)
break ;
posn -= nDiv ;
nDiv /= 2 ;
continue ;
}
// Do the compare
pDN = _findDnodeByPos(slot, posn, false) ;
//pKeys = (KEY*) pDN->Keys() ;
res = m_compare(pKey, pDN, slot) ;
if (res == 0)
{
// Have an exact match so mark it but is it the higest or lowest?
pMK = pDN ;
slotMk = slot ;
posnMk = posn ;
if (!nDiv)
break ;
// After marking posn, go lower or higher according to bias
if (eBias == HZ_ISAMSRCH_LO)
posn -= nDiv ;
else
posn += nDiv ;
}
else
{
// No match, go higher or lower if you can, otherwise fail
if (!nDiv)
break ;
if (res > 0)
posn += nDiv ;
else
posn -= nDiv ;
}
nDiv /= 2 ;
}
// If looking for lowest or highest and nothing found, give up
if (eBias == HZ_ISAMSRCH_LO || eBias == HZ_ISAMSRCH_HI)
{
if (!pMK)
return 0 ;
nAbs = posnMk ;
nSlot = slotMk ;
return pMK ;
}
// For HZ_ISAMSRCH_END if we have found highest entry, go up one place
if (pMK)
{
pDN = _findDnodeByPos(slot, posnMk+1, true) ;
nAbs = posnMk+1 ;
nSlot = slot ;
return pDN ;
}
// Otherwise go up one place ONLY if the last compare was > 0
if (res > 0)
posn++ ;
if (posn > max)
posn = max+1 ;
pDN = _findDnodeByPos(slot, posn, true) ;
nAbs = posn ;
nSlot = slot ;
return pDN ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::InsertKeyU (int32_t& nSlot, const void* pKey)
{
// Purpose: Insert an element by unique value.
//
// Arguments: 1) key The key to insert
//
// Returns: E_OK If operation successful
//
// Exits: E_CORRUPT If a target data node and slot was not located (integrity) or a population test fails
// E_MEMORY If there was insufficient memory
_hzfunc("_hz_tmpl_ISAM::InsertKeyU") ;
_hz_vn_Dat* pDN = 0 ; // Current data node
// If ordered list is empty
if (!Root())
{
pDN = new _hz_vn_Dat ;
if (!pDN)
Fatal("Isam=%d: Could not allocate root node\n", IsamId()) ;
pDN->m_pElements = new uchar[HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)] ;
memset(pDN->m_pElements, 0, HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)) ;
pDN->m_isamId = IsamId() ;
pDN->usage = 1 ;
m_nElements = 1 ;
m_pRoot = pDN ;
nSlot = 0 ;
return pDN ;
}
// Locate the 'target' top level node
pDN = _findDnodeByKey(nSlot, pKey, HZ_ISAMSRCH_END) ;
if (!pDN)
Fatal("Isam=%d: No data node found\n", IsamId()) ;
if (nSlot > HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d: Illegal slot no %d for node %d\n", IsamId(), nSlot, pDN->m_Id) ;
// If new element has identical key then ignore
if (nSlot < HZ_T_ISAMNODE_FULL)
{
if (m_compare(pKey, pDN, nSlot) == 0)
{
return pDN ;
}
}
pDN = (_hz_vn_Dat*) _allocDataSlot(pDN, nSlot) ;
if (Count() != Population()) Fatal("Isam=%d: Expected population %d, actual %d\n", IsamId(), Population(), Count()) ;
if (IntegBase() != E_OK) Fatal("Isam=%d: INTEGRITY FAILURE\n", IsamId()) ;
return pDN ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::InsertKeyM (int32_t& nSlot, const void* pKey)
{
// Purpose: Insert an element by non-unique value.
//
// Arguments: 1) key The key to insert
//
// Returns: E_OK If operation successful
//
// Exits: E_CORRUPT If a target data node and slot was not located (integrity) or a population test fails
// E_MEMORY If there was insufficient memory
_hzfunc("_hz_tmpl_ISAM::InsertKeyM") ;
_hz_vn_Dat* pDN = 0 ; // Current data node
uint32_t nPosn ; // Needed for _findAllByKey()
// If ordered list is empty
if (!Root())
{
pDN = new _hz_vn_Dat ;
if (!pDN)
Fatal("Isam=%d: Could not allocate root node\n", IsamId()) ;
pDN->m_pElements = new uchar[HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)] ;
memset(pDN->m_pElements, 0, HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)) ;
pDN->m_isamId = IsamId() ;
pDN->usage = 1 ;
m_nElements = 1 ;
m_pRoot = pDN ;
nSlot = 0 ;
return pDN ;
}
// Locate the 'target' top level node
pDN = _findAllByKey(nSlot, nPosn, pKey, HZ_ISAMSRCH_END) ;
if (!pDN)
Fatal("Isam=%d: No data node found\n", IsamId()) ;
if (nSlot > HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d: Illegal slot no %d for node %d\n", IsamId(), nSlot, pDN->m_Id) ;
// If new element has identical key then ignore
if (nSlot < HZ_T_ISAMNODE_FULL)
{
if (m_compare(pKey, pDN, nSlot) == 0)
return pDN ;
}
pDN = (_hz_vn_Dat*) _allocDataSlot(pDN, nSlot) ;
if (Count() != Population())
Fatal("Isam=%d: Expected population %d, actual %d\n", IsamId(), Population(), Count()) ;
if (IntegBase() != E_OK)
Fatal("Isam=%d: INTEGRITY FAILURE\n", IsamId()) ;
return pDN ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::DeleteKey (int32_t& nSlot, const void* pKey)
{
// Arguments: 1) key The key be removed
//
// Returns: E_OK If operation successful
// E_NOTFOUND If the key was not found in the ISAM
_hzfunc("_hz_tmpl_ISAM::DeleteKey") ;
_hz_vn_Dat* pDN = 0 ; // Target data node (from which delete will occur)
// Check args
if (!Root())
return 0 ;
// Locate the 'target' top level node
pDN = _findDnodeByKey(nSlot, pKey, HZ_ISAMSRCH_LO) ;
if (!pDN)
return 0 ;
if (nSlot >= HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d: Illegal slot no %d for node %d\n", IsamId(), nSlot, pDN->m_Id) ;
// Expel the entity from the node
pDN = _expelDataSlot(pDN, nSlot) ;
if (Count() != Population())
Fatal("Isam=%d: Expected population %d, actual %d\n", IsamId(), Population(), Count()) ;
return pDN ;
}
bool _hz_tmpl_ISAM::_shownode (_hz_vn_Any* pNode, hzLogger* plog, bool bData) const
{
// Support function to Show(). Prints out elements for a given node.
//
// Arguments: 1) pNode The current node
// 2) plog The logger to use for output
// 3) bData If set, output data part of element
//
// Returns: True If there were no integrity issues
// False If there were
_hzfunc("_hz_tmpl_ISAM::_shownode") ;
_hz_vn_Idx* pIdx = 0 ; // Index node
_hz_vn_Any* pChild ; // Child from slot
_hz_vn_Any* pPrev ; // Lower adjacent sibling
_hz_vn_Any* pNext ; // Higher adjacent sibling
_hz_vn_Idx* testA ; // Address of derived node
_hz_vn_Idx* testB ; // Address of derived node
uint32_t nTotal ; // Cumulative
int32_t nIndex ; // Iterator of children
bool bError = false ; // Error indicator
if (!pNode->Level())
{
if (bData)
plog->Out("\treport isam=%d Data Node %p parent %p inf %p sup %p level %d, usage %2d\n",
m_isamId, pNode, pNode->Parent(), pNode->Infra(), pNode->Ultra(), pNode->Level(), pNode->Usage()) ;
return true ;
}
pIdx = (_hz_vn_Idx*) pNode ;
if (bData)
plog->Out("report isam=%d Index Node %p parent %p inf %p sup %p level %d, usage %2d cumulate %d\n",
m_isamId, pNode, pNode->Parent(), pNode->Infra(), pNode->Ultra(), pNode->Level(), pNode->Usage(), pNode->Cumulative()) ;
if (pNode->Level() < 0 || pNode->Level() > 10)
{ plog->Out("\tOut of range level - no furthur analysis of node.\n") ; return false ; }
if (pNode->Usage() < 0 || pNode->Usage() > HZ_T_ISAMNODE_FULL)
{ plog->Out("\tOut of range usage - no furthur analysis of node.\n") ; return false ; }
// Check pointers
for (nIndex = 0 ; nIndex < pIdx->Usage() ; nIndex++)
{
pChild = pIdx->m_Ptrs[nIndex] ;
if (!pChild)
{
bError = true ;
plog->Out("\tInvalid pointer in posn %d\n", nIndex) ;
}
}
// Check cumulatives
nTotal = 0 ;
for (nIndex = 0 ; nIndex < pIdx->Usage() ; nIndex++)
{
pChild = (_hz_vn_Any*) pIdx->m_Ptrs[nIndex] ;
nTotal += pChild->Cumulative() ;
}
if (nTotal != pIdx->Cumulative())
{
bError = true ;
plog->Out(" -- ERROR: Counted cumulative for index node %p is %d, but empirical cumulatives is %d\n", pIdx, nTotal, pIdx->Cumulative()) ;
}
// Recurse to higher nodes
for (nIndex = 0 ; nIndex < pIdx->Usage() ; nIndex++)
{
pChild = (_hz_vn_Any*) pIdx->m_Ptrs[nIndex] ;
if (!_shownode(pChild, plog, bData))
bError = true ;
}
// Check integrity of this node in connection with its neighbours
for (nIndex = 0 ; nIndex < pIdx->Usage() ; nIndex++)
{
pChild = (_hz_vn_Any*) pIdx->m_Ptrs[nIndex] ;
// We are not on a data node
if (pChild->Parent() != pNode)
{
bError = true ;
plog->Out(" -- ERROR: Child in posn %d (%p) does not have this node (%p) as it's parent. Instead it has (%p)\n",
nIndex, pChild, pNode, pChild->Parent()) ;
continue ;
}
// Test siblings
if (nIndex == 0)
{
if (!pIdx->infra && pChild->Infra())
{
bError = true ;
plog->Out(" -- ERROR: Node %p While there is no infra node to this, the zeroth child has an infra (%p)\n",
pIdx, pChild->Infra()) ;
}
if (pIdx->infra && !pChild->Infra())
{
bError = true ;
plog->Out(" -- ERROR: Node %p There is an infra to this (%p) but the zeroth child does not have an infra\n", pIdx, pIdx->infra) ;
}
if (pIdx->infra && pChild->Infra())
{
testA = pChild->Infra() && pChild->Infra()->Parent() ? pChild->Infra()->Parent() : 0 ;
testB = pIdx->infra ? pIdx->infra : 0 ;
if (testA != testB)
{
bError = true ;
plog->Out(" -- ERROR: Node %p The parent of the zeroth child infra (%p) is not the infra of this (%p)\n",
pIdx, testA, testB) ;
}
}
}
else if (nIndex == (pIdx->Usage()-1))
{
if (!pIdx->ultra && pChild->Ultra())
{ bError = true ; plog->Out(" -- ERROR: While there is no ultra node to this node, the highest child has a ultra\n") ; }
if (pIdx->ultra && !pChild->Ultra())
{ bError = true ; plog->Out(" -- ERROR: There is an ultra to this node but the highest child does not have a ultra\n") ; }
if (pIdx->infra && pChild->Ultra())
{
if (pChild->Ultra()->Parent() != pIdx->ultra)
{ bError = true ; plog->Out(" -- ERROR: The parent of the highest child ultra is not the ultra of this node\n") ; }
}
}
else
{
pPrev = (_hz_vn_Any*) pIdx->m_Ptrs[nIndex-1] ;
pNext = (_hz_vn_Any*) pIdx->m_Ptrs[nIndex+1] ;
if (pChild->Infra() != pPrev)
{ bError = true ; plog->Out(" -- ERROR: Child %d infra is not the same as child %d\n", nIndex, nIndex-1) ; }
if (pChild->Ultra() != pNext)
{ bError = true ; plog->Out(" -- ERROR: Child %d ultra is not the same as child %d\n", nIndex, nIndex+1) ; }
}
}
return bError ? false : true ;
}
hzEcode _hz_tmpl_ISAM::NodeReport (bool bData) const
{
// Category: Diagnostics
//
// Starting from the root node and moving out to data nodes, this checks that nodes do not contain null pointers, have correct parent pointers and have
// correct cumulative values
//
// Arguments: 1) bData If set, print data object
//
// Returns: E_CORRUPT If any node has integrity issues
// E_OK If all nodes succeed
_hzfunc("_hz_tmpl_ISAM::NodeReport") ;
hzLogger* plog ; // Current thread logger
hzEcode rc = E_OK ; // Return code
plog = GetThreadLogger() ;
if (plog)
{
if (!m_pRoot)
{ plog->Out("The _hz_tmpl_ISAM object is empty\n") ; return E_OK ; }
if (!_shownode(m_pRoot, plog, bData))
rc = E_CORRUPT ;
}
return rc ;
}
hzEcode _hz_tmpl_ISAM::_integBase (hzLogger* plog, _hz_vn_Idx* pN) const
{
// Quick index node integrity test
//
// Arguments: 1) plog Logger
// 2) pN Current node
//
// Returns: E_CORRUPT If node fails integrity test
// E_OK If node passes
_hzfunc("_hz_tmpl_ISAM::_integBase") ;
_hz_vn_Any* pInf ; // Infra to the current node
_hz_vn_Any* pUlt ; // Ultra to the current node
_hz_vn_Any* pCA ; // Child node A
_hz_vn_Any* pCB ; // Child node B
_hz_vn_Idx* par ; // Parent of test node
uint32_t err = 0 ; // Set if error
int32_t n ; // Loop control
pInf = pN->Infra() ;
pUlt = pN->Ultra() ;
// Test if the infra and ultra pointers point back to current node
if (pInf && (pInf->Ultra() != pN)) { err=1 ; plog->Out("On node %p: Infra node %p does not point back to this node\n", pN, pInf) ; }
if (pUlt && (pUlt->Infra() != pN)) { err=1 ; plog->Out("On node %p: Infra node %p does not point back to this node\n", pN, pInf) ; }
// Test if the slot 0 child has an infra whose parent is this node's infra
pCA = pN->m_Ptrs[0] ;
if (pInf)
{
if (!pCA->Infra())
{ err=1 ; plog->Out("On node %p: Child 0 (%p) has no infra while this node does\n", pN, pCA) ; }
else
{
par = pCA->Infra()->Parent() ;
if (!par)
{ err=1 ; plog->Out("On node %p: Child 0 (%p) has parent -1 diff to the infra %p\n", pN, pCA, pInf) ; }
if (par && par != pInf)
{ err=1 ; plog->Out("On node %p: Child 0 (%p) has parent %p diff to the infra %p\n", pN, pCA, par, pInf) ; }
}
}
// Test if the top child has an ultra whose parent is this node's ultra
pCB = pN->m_Ptrs[pN->Usage()-1] ;
if (pUlt)
{
if (!pCB->Ultra())
{ err=1 ; plog->Out("On node %p: Child 0 (%p) has no infra while this node does\n", pN, pCB) ; }
else
{
par = pCB->Ultra()->Parent() ;
if (!par)
{ err=1 ; plog->Out("On node %p: Child 0 (%p) has parent -1 diff to the infra %p\n", pN, pCB, pUlt) ; }
if (par && par != pUlt)
{ err=1 ; plog->Out("On node %p: Child 0 (%p) has parent %p diff to the infra %p\n", pN, pCB, par, pUlt) ; }
}
}
// For each slot test if the child's infra points to the child of the next lower slot
// For each slot test if the child's ultra points to the child of the next higher slot
for (n = pN->Usage()-1 ; n > 0 ; n--)
{
pCA = pN->m_Ptrs[n-1] ;
if (pCA->Ultra() != pCB)
{ err=1; plog->Out("On node %p: Child in slot %d has infra of %p but slot %d points to %p\n", pN, n+1, pCA, n, pCB) ; }
if (pCB->Infra() != pCA)
{ err=1; plog->Out("On node %p: Child in slot %d has ultra of %p but slot %d points to %p\n", pN, n, pCA, n+1, pCA) ; }
pCB = pN->m_Ptrs[n-1] ;
}
// Recurse to child nodes
if (pN->Level() > 1)
{
for (n = 0 ; n < pN->Usage() ; n++)
{
if (_integBase(plog, (_hz_vn_Idx*) pN->m_Ptrs[n]) != E_OK)
err=1;
}
}
return err ? E_CORRUPT : E_OK ;
}
hzEcode _hz_tmpl_ISAM::IntegBase (void) const
{
// This test that index node are consistent. For each node pointer in an index node, the node pointed to is tested to ensure it's adjacents agree with ..
//
// Arguments: None
//
// Returns: E_CORRUPT If any ode fails integrity test
// E_OK If all nodes pass
_hzfunc("_hz_tmpl_ISAM::IntegBase") ;
_hz_vn_Idx* pN ; // ISAM root
hzLogger* plog ; // Current thread logger
if (!m_pRoot)
return E_OK ;
if (!m_pRoot->Level())
return E_OK ;
pN = (_hz_vn_Idx*) m_pRoot ;
plog = GetThreadLogger() ;
return _integBase(plog, pN) ;
}
_hz_vn_Dat* _hz_tmpl_ISAM::InsertPosn (int32_t& nSlot, uint32_t nPosn)
{
// Purpose: Insert an element at position.
//
// Arguments: 1) nPosn Position to insert object
// 2) key The key to insert
//
// Returns: E_OK If operation successful
// E_RANGE If position was invalid
// E_CORRUPT If there were integrity issues
_hzfunc("_hz_tmpl_ISAM::InsertPosn") ;
_hz_vn_Dat* pDN = 0 ; // Current data node
// Check args
if (Count() != Population()) Fatal("Isam=%d Found to have wrong population: Abs %d, root cumulative %d\n", IsamId(), Population(), Count()) ;
if (nPosn > Population()) Fatal("Isam=%d: Attempt to add element at position %d. Element set ends at %d\n", IsamId(), nPosn, Population()) ;
// If ordered list is empty
if (!Root())
{
pDN = new _hz_vn_Dat ;
if (!pDN)
Fatal("Isam=%d: Could not allocate root node\n", IsamId()) ;
pDN->m_pElements = new uchar[HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)] ;
memset(pDN->m_pElements, 0, HZ_T_ISAMNODE_FULL * (m_nSizeKey + m_nSizeObj)) ;
pDN->m_isamId = IsamId() ;
pDN->usage = 1 ;
m_nElements = 1 ;
m_pRoot = pDN ;
nSlot = 0 ;
return pDN ;
}
// Locate the 'target' top level node
pDN = (_hz_vn_Dat*) _findDnodeByPos(nSlot, nPosn, true) ;
if (!pDN)
Fatal("Isam=%%d: No target data node found for posn %d (pop %d)\n", IsamId(), nPosn, Population()) ;
if (nSlot < 0 || nSlot > HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d: Illegal slot no %d for node %d\n", IsamId(), nSlot, pDN->m_Id) ;
pDN = _allocDataSlot(pDN, nSlot) ;
if (Count() != Population())
Fatal("Isam=%d: Expected population %d, actual %d\n", IsamId(), Population(), Count()) ;
return pDN ;
}
hzEcode _hz_tmpl_ISAM::DeletePosn (uint32_t nPosn)
{
// Purpose: Delete an element at position.
//
// Method: This calls _findDnodeByPos to eastablish the target data node and slot for the requested position within the ISAM. It then calls _expelData() to delete
// the slot from the target node.
//
// Arguments: 1) nPosn Position of object to delete
//
// Returns: E_OK If operation successful
// E_RANGE If position was invalid
// E_NODATA If element was a null
// E_MEMORY If there was insufficient memory
_hzfunc("_hz_tmpl_ISAM::DeletePosn") ;
_hz_vn_Dat* pTgt = 0 ; // Target data node (from which delete will occur)
int32_t nSlot ; // Position within node
// Check args
if (!Root())
return E_NOTFOUND ;
if (nPosn < 0 || nPosn >= Cumulative())
return E_RANGE ;
// Locate the 'target' top level node
pTgt = (_hz_vn_Dat*) _findDnodeByPos(nSlot, nPosn, false) ;
if (!pTgt)
Fatal("Isam=%d: No data node found in spite of position %d being within range %d\n", IsamId(), nPosn, Cumulative()) ;
if (nSlot >= HZ_T_ISAMNODE_FULL)
Fatal("Isam=%d: Illegal slot no %d for node %d\n", IsamId(), nSlot, pTgt->m_Id) ;
// Expel the entity from the node
//mx->m_nElements-- ;
_expelDataSlot(pTgt, nSlot) ;
if (Count() != Population())
Fatal("Isam=%d: Expected population %d, actual %d\n", IsamId(), Population(), Count()) ;
return E_OK ;
}