//
// File: hzIsam.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"
using namespace std ;
/*
** Prototypes
*/
#if 0
void Fatal (const char* va_alist ...) ;
#define CTMPL_NODESIZE 8
/*
** Section 2 Function Templates and support classes and class templatess
*/
// Compare
template<class X> int _tmpl_zet_compare (const X a, const X b) { return a>b ? 1 : a<b ? -1 : 0 ; }
#define HZ_ORDSZE 8
#define HZ_ISAM_LOW 5
class _hz_zet_node_Idx ;
class _hz_zet_node_Any
{
// Category: Collection Support
//
// Pure virtual base class for index and data nodes
public:
_hz_zet_node_Idx* parent ; // Parent node
virtual ~_hz_zet_node_Any (void) {}
virtual _hz_zet_node_Idx* Parent (void) = 0 ;
virtual _hz_zet_node_Any* Infra (void) = 0 ;
virtual _hz_zet_node_Any* Ultra (void) = 0 ;
virtual uint32_t Cumulative (void) = 0 ;
virtual uint32_t Level (void) = 0 ;
virtual uint32_t Usage (void) = 0 ;
virtual uint32_t IsamId (void) = 0 ;
virtual uint32_t Ident (void) = 0 ;
virtual uint32_t InfId (void) = 0 ;
virtual uint32_t UltId (void) = 0 ;
virtual void SetParent (_hz_zet_node_Idx*) = 0 ;
} ;
class _hz_zet_node_Idx : public _hz_zet_node_Any
{
// Category: Collection Support
//
// Common Index nodes
public:
_hz_zet_node_Idx* infra ; // Infra adjacent
_hz_zet_node_Idx* ultra ; // Ultra adjacent
_hz_zet_node_Any* m_Ptrs[HZ_ORDSZE] ; // Pointers either to index or data nodes
uint32_t cumulative ; // Number of elements ultimately pointed to by this block
uint32_t m_Id ; // Unique node id (for diagnostics)
uint16_t m_isamId ; // Ties the node to the ISAM
uint16_t usage ; // Number of elements in this block
uint16_t level ; // Level of this block in the tree
uint16_t resv ; // Reserved
_hz_zet_node_Idx (void)
{
//printf("NEW ISAM BLOCK\n") ;
m_Id = ++_hzGlobal_Memstats.m_numIsamIndx ;
m_Ptrs[0] = m_Ptrs[1] = m_Ptrs[2] = m_Ptrs[3] = m_Ptrs[4] = m_Ptrs[5] = m_Ptrs[6] = m_Ptrs[7] = 0 ;
parent = infra = ultra = 0 ;
cumulative = 0 ;
m_isamId = usage = level = resv = 0 ;
}
~_hz_zet_node_Idx (void)
{
_hzGlobal_Memstats.m_numIsamIndx-- ;
}
_hz_zet_node_Idx* Parent (void) { return parent ; }
_hz_zet_node_Idx* Infra (void) { return infra ; }
_hz_zet_node_Idx* Ultra (void) { return ultra ; }
uint32_t Cumulative (void) { return cumulative ; }
uint32_t Usage (void) { return usage ; }
uint32_t Level (void) { return level ; }
uint32_t IsamId (void) { return m_isamId ; }
uint32_t Ident (void) { return m_Id ; }
uint32_t InfId (void) { return infra ? infra->m_Id : 0 ; }
uint32_t UltId (void) { return ultra ? ultra->m_Id : 0 ; }
void SetParent (_hz_zet_node_Idx* par) { parent = par ; }
void SetLevel (int32_t v) { level = v ; }
} ;
template <class KEY> class _hz_zet_node_Dat : public _hz_zet_node_Any
{
// Category: Collection Support
//
// Single datum data blocks for use in the _hz_isam_Relpos and _hz_isam_val ISAM templates.
public:
_hz_zet_node_Dat<KEY>* infra ; // Infra adjacent
_hz_zet_node_Dat<KEY>* ultra ; // Ultra adjacent
KEY m_Keys[HZ_ORDSZE] ; // Pointers either to mapentries or higher nodes
uint32_t m_Id ; // Unique node id (for diagnostics)
uint16_t m_isamId ; // Ties node to ISAM
uint16_t usage ; // Number of elements in this block
_hz_zet_node_Dat (void)
{
//printf("NEW DATA A BLK %lu\n", sizeof(KEY)) ;
m_Id = ++_hzGlobal_Memstats.m_numIsamData ;
parent = 0 ;
infra = ultra = 0 ;
m_isamId = usage = 0 ;
memset(m_Keys, 0, (HZ_ORDSZE * sizeof(KEY))) ;
}
~_hz_zet_node_Dat (void)
{
_hzGlobal_Memstats.m_numIsamData-- ;
}
_hz_zet_node_Dat<KEY>* allocUltra (void)
{
// Allocate ultra node to this
//
// Arguments: None
// Returns: Pointer to the allocated ultra node
_hz_zet_node_Dat<KEY>* pUlt ; // Ultra node
pUlt = new _hz_zet_node_Dat<KEY> ;
if (ultra)
ultra->infra = pUlt ;
pUlt->ultra = ultra ;
pUlt->infra = this ;
pUlt->m_isamId = m_isamId ;
ultra = pUlt ;
return pUlt ;
}
// Get values
_hz_zet_node_Idx* Parent (void) { return parent ; }
_hz_zet_node_Dat<KEY>* Infra (void) { return infra ; }
_hz_zet_node_Dat<KEY>* Ultra (void) { return ultra ; }
uint32_t Cumulative (void) { return usage ; }
uint32_t Usage (void) { return usage ; }
uint32_t Level (void) { return 0 ; }
uint32_t IsamId (void) { return m_isamId ; }
uint32_t Ident (void) { return m_Id ; }
uint32_t InfId (void) { return infra ? infra->m_Id : 0 ; }
uint32_t UltId (void) { return ultra ? ultra->m_Id : 0 ; }
void* Keys (void) { return &m_Keys ; }
// Set values
void SetParent (_hz_zet_node_Idx* par) { parent = par ; }
void SetInfra (_hz_zet_node_Dat<KEY>* pInf) { infra = (_hz_zet_node_Dat<KEY>*) pInf ; }
void SetUltra (_hz_zet_node_Dat<KEY>* pUlt) { ultra = (_hz_zet_node_Dat<KEY>*) pUlt ; }
void IncUsage (void) { usage++ ; }
void DecUsage (void) { usage-- ; }
void SetUsage (uint32_t u) { usage = u ; }
void setfromCur (int32_t slot, int32_t srcSlot) { m_Keys[slot] = m_Keys[srcSlot] ; }
void setfromInf (int32_t slot, int32_t srcSlot) { m_Keys[slot] = infra->m_Keys[srcSlot] ; }
void setfromUlt (int32_t slot, int32_t srcSlot) { m_Keys[slot] = ultra->m_Keys[srcSlot] ; }
} ;
template <class KEY> class _hz_zet_isam_Base
{
// Category: Collection Support
//
// The _hz_zet_isam_Base is what holds the ISAM root (and thus the index and data) on behalf of ...
class _isam_ca
{
// ISAM control area
public:
_hz_zet_node_Any* m_pRoot ; // Start of index
hzLocker* m_pLock ; // Locking (off by default)
uint32_t isamId ; // For diagnostics
uint32_t m_nNodes ; // Number of nodes (also as node id allocator)
uint32_t m_nElements ; // Number of data objects
_m uint32_t m_copy ; // Copy count
KEY m_Default ; // Default (null) object
_isam_ca (void)
{
m_pLock = 0 ;
m_pRoot = 0 ;
m_nNodes = m_nElements = m_copy = 0 ;
memset(&m_Default, 0, sizeof(KEY)) ;
}
~_isam_ca (void) { _clear() ; }
void _clearnode (_hz_zet_node_Any* pBlk)
{
// Recursively clear supplied node and any child nodes
//
// Argument: pBlk The supplied node
// Returns: None
_hz_zet_node_Idx* pIdx ; // Current ISAM block pointer
uint32_t n ; // ISAM block selector
if (!pBlk->Level())
delete pBlk ;
else
{
pIdx = (_hz_zet_node_Idx*) pBlk ;
for (n = 0 ; n < pIdx->usage ; n++)
_clearnode(pIdx->m_Ptrs[n]) ;
delete pIdx ;
}
}
void _clear (void)
{
// Clear the map of all keys and elements
//
// Begin at root and take the least pointer out to the lowest data node and pass through the list of data nodes deleting them. Then drop back one level
// to delete the index nodes level by level
//
// Arguments: None
// Returns: None
if (!m_pRoot)
return ;
_clearnode(m_pRoot) ;
m_nElements = 0 ;
m_pRoot = 0 ;
}
void SetLock (hzLockOpt eLock)
{
if (eLock == HZ_ATOMIC) m_pLock = new hzLockRW() ;
if (eLock == HZ_MUTEX) m_pLock = new hzLockRWD() ;
}
} ;
_isam_ca* mz ; // The internal ISAM structure
hzString m_Name ; // ISAM name (all ISAM dependent templates use this)
// Prevent copies
_hz_zet_isam_Base<KEY> (const _hz_zet_isam_Base<KEY>&) ;
_hz_zet_isam_Base<KEY>& operator= (const _hz_zet_isam_Base<KEY>&) ;
public:
_hz_zet_isam_Base (void) { mz = 0 ; }
~_hz_zet_isam_Base (void)
{
LockWrite() ;
if (mz->m_copy)
{ mz->m_copy-- ; Unlock() ; }
else
{ mz->_clear() ; Unlock() ; delete mz ; }
_hzGlobal_Memstats.m_numIsams-- ;
}
void Start (void)
{
mz = new _isam_ca() ;
mz->isamId = ++_hzGlobal_Memstats.m_numIsams ;
//printf("ALLOC ISAM INTERNAL %d\n", mz->isamId) ; fflush(stdout) ;
}
void SetLock (hzLockOpt eLock)
{
if (eLock == HZ_ATOMIC)
mz->m_pLock = new hzLockRW() ;
else if (eLock == HZ_MUTEX)
mz->m_pLock = new hzLockRWD() ;
else
mz->m_pLock = 0 ;
}
void SetName (const hzString& name) { m_Name = name ; }
void SetDefault (const KEY& key) { mz->m_Default = key ; }
void LockRead (void) { if (mz->m_pLock) mz->m_pLock->LockRead() ; }
void LockWrite (void) { if (mz->m_pLock) mz->m_pLock->LockWrite() ; }
void Unlock (void) { if (mz->m_pLock) mz->m_pLock->Unlock() ; }
void Clear (void)
{
// Clear the map of all keys and elements
//
// Begin at root and take the least pointer out to the lowest data node and pass through the list of data nodes deleting them. Then drop back one level
// to delete the index nodes level by level
//
// Arguments: None
// Returns: None
LockWrite() ;
mz->_clear() ;
Unlock() ;
}
/*
_hz_zet_isam_Base<KEY>& operator= (const _hz_zet_isam_Base<KEY>& op)
{
// If this vector has the same internal data as the operand do nothing - otherwise clear this vector first and then assign to the operand.
if (mz && mz == op.mz)
return *this ;
Clear() ;
mz = op.mz ;
m_Name = op.m_Name ;
LockWrite() ;
mz->m_copy++ ;
Unlock() ;
return *this ;
}
*/
_hz_zet_node_Dat<KEY>* _nodetr (uint32_t& nOset, 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) nOset 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_ct("_hz_zet_isam_Base::_nodetr") ;
_hz_zet_node_Idx* pIdx = 0 ; // Current index node
_hz_zet_node_Any* pChild = 0 ; // Can be index node or outer level data node
_hz_zet_node_Dat<KEY>* 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
uint32_t n ; // Element iterator
// Check if there is a root
if (!mz->m_pRoot)
{ nOset = -1 ; return 0 ; }
// Check limits
nMax = bExpand ? mz->m_pRoot->Cumulative() : mz->m_pRoot->Cumulative()-1 ;
if (nPosn > nMax)
{ nOset = -1 ; return 0 ; }
// If the root is the only node
if (mz->m_pRoot->Level() == 0)
{
pDN = (_hz_zet_node_Dat<KEY>*) mz->m_pRoot ;
nOset = nPosn ;
return pDN ;
}
// Common case, start at root which is an index node
pIdx = (_hz_zet_node_Idx*) mz->m_pRoot ;
nMax = nMin = nStart = 0 ;
for (nStart = 0 ; !pDN ;)
{
// Look on the node for the offset/pointer to the next node or the
nMin = nStart ;
for (n = 0 ; n < pIdx->Usage() ; n++)
{
pChild = (_hz_zet_node_Any*) pIdx->m_Ptrs[n] ;
if (!pChild)
Fatal("_hz__zt_isam_Base::_nodetr: isam=%d (%s): Missing node pointer on non leaf node", mz->isamId, *m_Name) ;
if (pChild->Parent() != pIdx)
Fatal("_hz_zet_isam_Base::_nodetr: isam=%d (%s): Child node %d (level %d) does not point back to current node %d (level %d)",
mz->isamId, *m_Name, pChild->Ident(), pChild->Level(), pIdx->m_Id, 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_zet_node_Idx*) pChild ;
else
pDN = (_hz_zet_node_Dat<KEY>*) pChild ;
}
nOset = nPosn - nStart ;
if (nOset > pDN->Usage())
Fatal("_hz_zet_isam_Base::_nodetr: isam=%d (%s): Node %d usage %u has offset %u", mz->isamId, *m_Name, pDN->Ident(), pDN->Usage(), nOset) ;
return pDN ;
}
hzEcode _acceptIndx (_hz_zet_node_Idx* pCur, _hz_zet_node_Any* pOld, _hz_zet_node_Any* pNew)
{
// This function is called on an index node which may have either data node pointers or index node pointers as elements. It is only called when a child node
// pOld spawns a 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. _acceptIndx 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 (_acceptData) then sets this as the new root to the ISAM.
//
// Arguments: 1) pCur The pointer to the current node (parent to pOld and pNew)
// 2) pOld The pointer to the pre-existing child node (prognitor)
// 3) pNew The pointer to the newly created ultra sibling of the prognitor
//
// Returns: E_OK Always
_hzfunc_ct("_hz_zet_isam_Base::_acceptIndx") ;
_hz_zet_node_Any* pNode = 0 ; // Shift element
_hz_zet_node_Idx* pIdxNew = 0 ; // New ultra sibling
_hz_zet_node_Idx* pPar = 0 ; // Parent for cumulatives
uint32_t slot = 0 ; // Slot found for existing pOld
uint32_t n = 0 ; // Slot iterator
uint32_t za ; // Shift cumulative 1
uint32_t zb ; // Shift cumulative 2
// Verify arguments
if (!pOld) Fatal("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): No pre-existing item supplied", mz->isamId, *m_Name) ;
if (!pNew) Fatal("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): No new item supplied", mz->isamId, *m_Name) ;
if (pNew->Infra() != pOld)
Fatal("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): new %d does not point back to old %d", mz->isamId, *m_Name, pNew->Ident(), pOld->Ident()) ;
if (pOld->Ultra() != pNew)
Fatal("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): old %d does not point forward to new %d", mz->isamId, *m_Name, pOld->Ident(), pNew->Ident()) ;
// Do we need a new root?
if (!pCur)
{
pCur = new _hz_zet_node_Idx() ;
pCur->m_Ptrs[0] = pOld ;
pCur->m_Ptrs[1] = pNew ;
pOld->SetParent(pCur) ;
pNew->SetParent(pCur) ;
pCur->m_isamId = mz->isamId ;
pCur->usage = 2 ;
pCur->cumulative = pOld->Cumulative() + pNew->Cumulative() ;
pCur->level = pOld->Level()+1 ;
mz->m_pRoot = pCur ;
return E_OK ;
}
// Given we have a current node, further checks
if ((pOld->Level()+1) != pCur->level)
Fatal("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): At level %d but old element level is %d", mz->isamId, *m_Name, pCur->level, pOld->Level()) ;
if ((pNew->Level()+1) != pCur->level)
Fatal("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): At level %d but new element level is %d", mz->isamId, *m_Name, pCur->level, pNew->Level()) ;
if (!pNew->Parent())
pNew->SetParent(pCur) ;
if (pNew->Parent() != pCur)
Fatal("%s: isam=%d (%s): new %d does not have this node (%d) as its parent instad it has %d",
mz->isamId, *m_Name, pNew->Ident(), pCur->m_Id, pNew->Parent()->Ident()) ;
// 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("_hz_zet_isam_Base::_acceptIndx: isam=%d (%s): On node %d: Child node %d not found", mz->isamId, *m_Name, pCur->m_Id, pOld->Ident()) ;
slot++ ;
// If there is space on this node just insert the new element
if (pCur->usage < HZ_ORDSZE)
{
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->cumulative += pNew->Cumulative() ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += pNew->Cumulative() ;
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_ORDSZE)
{
// 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->cumulative += za ;
pCur->cumulative += (zb - za) ;
if (pCur->parent == pCur->infra->parent)
{
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += zb ;
}
else
{
for (pPar = pCur->infra->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += za ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += (zb - za) ;
}
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_ORDSZE)
{
pIdxNew = new _hz_zet_node_Idx ;
if (!pIdxNew)
Fatal("_hz_zet_isam_Base::_acceptIndx: Could not allocate sibling\n") ;
pIdxNew->m_isamId = mz->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.
_acceptIndx(pCur->parent, pCur, pIdxNew) ;
}
// OK now we can boogie as there is a ultra with space and parent
if (slot == HZ_ORDSZE)
{
// 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->cumulative += zb ;
for (pPar = pCur->ultra->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += zb ;
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->cumulative += 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->cumulative += (zb - za) ;
if (pCur->parent == pCur->ultra->parent)
{
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += zb ;
}
else
{
for (pPar = pCur->ultra->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += za ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += (zb - za) ;
}
return E_OK ;
}
void _expelIndx (_hz_zet_node_Idx* pCur, _hz_zet_node_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_ct("_hz_zet_node_Idx::_expelIndx") ;
_hz_zet_node_Any* pXfer ; // Element (block pointer) being moved
_hz_zet_node_Idx* pPar = 0 ; // Parent for cumulatives
uint32_t x = 0 ; // No of elements moved to infra
uint32_t y = 0 ; // Offset into current node for copying elements to ultra
uint32_t slot ; // Slot of element being deleted
uint32_t za = 0 ; // Shift cumulative 1
uint32_t zb = 0 ; // Shift cumulative 2
if (!pCur) Fatal("_hz_zet_node_Idx::_expelIndx: isam=%d (%s): No node supplied from which to expell", *m_Name, mz->isamId) ;
if (!pChild) Fatal("_hz_zet_node_Idx::_expelIndx: isam=%d (%s): No child node supplied to expell from node %d", mz->isamId, *m_Name, pCur->m_Id) ;
for (slot = 0 ; slot < pCur->usage ; slot++)
{
if (pCur->m_Ptrs[slot] == pChild)
break ;
}
if (slot == pCur->usage)
Fatal("_hz_zet_node_Idx::_expelIndx: isam=%d (%s): No pointer to depricated child node found on this node (%d)", mz->isamId, *m_Name, pCur->m_Id) ;
if (slot < 0 || slot >= pCur->usage)
Fatal("_hz_zet_node_Idx::_expelIndx: isam=%d (%s): Node %d Illegal slot value (%d)", mz->isamId, *m_Name, pCur->m_Id, 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->cumulative -= pChild->Cumulative() ;
for (pPar = pCur->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative -= pChild->Cumulative() ;
delete pChild ;
if (pCur->usage && pCur->usage < HZ_ISAM_LOW)
{
// Now that an entry has been removed, can we merge the current node with either or both adjacents?
x = pCur->infra ? HZ_ORDSZE - pCur->infra->usage : 0 ;
y = pCur->ultra ? HZ_ORDSZE - 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_ORDSZE)
{
for (x = 0 ; pCur->usage && pCur->infra->usage < HZ_ORDSZE ; 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->cumulative += za ;
for (pPar = pCur->infra->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += za ;
}
if (pCur->ultra && pCur->ultra->usage < HZ_ORDSZE)
{
// 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->cumulative += zb ;
pCur->ultra->usage += y ;
for (pPar = pCur->ultra->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative += zb ;
}
}
}
if (!pCur->usage)
{
// Connect adjacents
if (pCur->ultra)
pCur->ultra->infra = pCur->infra ;
if (pCur->infra)
pCur->infra->ultra = pCur->ultra ;
if (pCur->parent)
_expelIndx(pCur->parent, pCur) ;
}
}
_hz_zet_node_Dat<KEY>* _acceptData (_hz_zet_node_Dat<KEY>* pDN, const KEY& key, uint32_t& nSlot)
{
// With a target data node and slot identified by _nodetr this funtion performs an insert. This 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_ORDSZE (which is possible if _nodetr() 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_ORDSZE 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)
//
// It is essential that this function informs the called of the node and slot the new entry actually ended up in as only the key can be placed. If there are
// objects to be placed alongside the key, this will be done by the caller after this function has returned. To this end the actual data node is returned and
// nSlot, supplied as an int32_t& is set.
//
// Arguments 1) The target node identified by _nodetr()
// 2) The key value
// 3) The reference to target slot identified by _nodetr(), _findDnodeByKey() or _findAbsoluteByKey() and adjusted by this function.
//
// Returns Pointer to the actual node the new entry resides in
//
// Note that the target slot can be set to HZ_ORDSZE by _nodetr(), _findDnodeByKey() or _findAbsoluteByKey() if and only if the target node is full and has
// no ultra. After this function the slot will always have a value between 0 and HZ_ORDSZE-1
_hzfunc_ct("_hz_zet_isam_Base::_acceptData") ;
_hz_zet_node_Dat<KEY>* pInfra = 0 ; // New data node
_hz_zet_node_Dat<KEY>* pUltra = 0 ; // New data node
_hz_zet_node_Idx* pIdx ; // Index node (for updating cimulatives)
KEY* pKeys ; // Access to node's keys
uint32_t n ; // Loop controller
// Test inputs
if (!pDN)
Fatal("_hz_zet_isam_Base::_acceptData: isam=%d (%s): No taget data node supplied", mz->isamId, *m_Name) ;
n = pDN->Usage() ;
if (n > HZ_ORDSZE) Fatal("_hz_zet_isam_Base::_acceptData: isam=%d (%s): Garbage usage value (%d)", mz->isamId, *m_Name, n) ;
if (nSlot > HZ_ORDSZE) Fatal("_hz_zet_isam_Base::_acceptData: isam=%d (%s): Illegal slot value (%d)", mz->isamId, *m_Name, nSlot) ;
if (nSlot > pDN->Usage()) Fatal("_hz_zet_isam_Base::_acceptData: isam=%d (%s): Excessive slot value (%d)", mz->isamId, *m_Name, nSlot) ;
mz->m_nElements++ ;
// If new element can be accomodated on this node then add it and return
if (pDN->Usage() < HZ_ORDSZE)
{
for (n = pDN->Usage() ; n > nSlot ; n--)
pDN->setfromCur(n, n-1) ;
pKeys = (KEY*) pDN->Keys() ;
pKeys[nSlot] = key ;
pDN->IncUsage() ;
for (pIdx = pDN->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->cumulative++ ;
return pDN ;
}
// This node is full so we first see if the first element can be moved to this node's infra, if it exists
pInfra = (_hz_zet_node_Dat<KEY>*) pDN->Infra() ;
if (pInfra && pInfra->Usage() < HZ_ORDSZE)
{
if (nSlot == 0)
{
// Store object direcly in top slot in infra node
nSlot = pInfra->Usage() ;
pKeys = (KEY*) pInfra->Keys() ;
pKeys[nSlot] = key ;
pInfra->IncUsage() ;
for (pIdx = pInfra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->cumulative++ ;
return pInfra ;
}
// Move element 0 to infra node, decrement slot move all elements upto slot down one place, store object in slot
pInfra->setfromUlt(pInfra->Usage(), 0) ;
pInfra->IncUsage() ;
for (pIdx = pInfra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->cumulative++ ;
nSlot-- ;
for (n = 0 ; n < nSlot ; n++)
pDN->setfromCur(n, n+1) ;
pKeys = (KEY*) pDN->Keys() ;
pKeys[nSlot] = key ;
return pDN ;
}
// No room on the infra so we try the ultra. If there isn't one or there is but it is full, create an empty one. Note that if we create a new node at
// this point, we don't update the index cumulatives below. This is because we are going to return the new node so that it will be added to the parent and
// at that point the cumulatives on the parent index nodes will be adjusted.
pUltra = (_hz_zet_node_Dat<KEY>*) pDN->Ultra() ;
if (!pUltra || pUltra->Usage() == HZ_ORDSZE)
{
pUltra = pDN->allocUltra() ;
if (!pUltra)
Fatal("_hz_zet_isam_Base::_acceptData: Could not allocate sibling") ;
// Put this new node into the index
_acceptIndx((_hz_zet_node_Idx*) pDN->Parent(), pDN, pUltra) ;
}
// OK now we can boogie as there is a ultra with space
for (n = pUltra->Usage() ; n > 0 ; n--)
pUltra->setfromCur(n, n-1) ;
if (nSlot == HZ_ORDSZE)
{
// New element goes into slot 0 of ultra
pKeys = (KEY*) pUltra->Keys() ;
pKeys[0] = key ;
pUltra->IncUsage() ;
for (pIdx = pUltra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->cumulative++ ;
nSlot = 0 ;
return pUltra ;
}
// Higest element of this node goes into slot 0 of ultra, then new element inserted into this node
pUltra->setfromInf(0, pDN->Usage()-1) ;
pUltra->IncUsage() ;
for (pIdx = pUltra->parent ; pIdx ; pIdx = pIdx->parent)
pIdx->cumulative++ ;
// Insert new element into this node
for (n = pDN->Usage()-1 ; n > nSlot ; n--)
pDN->setfromCur(n, n-1) ;
pKeys = (KEY*) pDN->Keys() ;
pKeys[nSlot] = key ;
return pDN ;
}
_hz_zet_node_Dat<KEY>* _expelData (_hz_zet_node_Dat<KEY>* pDN, uint32_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_ct("_hz_zet_isam_Base::_expelData") ;
_hz_zet_node_Idx* pPar ; // For setting cumulatives in index
_hz_zet_node_Dat<KEY>* pInfra ; // For setting cumulatives in index
_hz_zet_node_Dat<KEY>* pUltra ; // For setting cumulatives in index
KEY* pKeys ; // Keys on node
uint32_t x = 0 ; // Loop control, doubles as No of elements moved to infra
uint32_t y = 0 ; // Loop control, doubles as No of elements moved to ultra
uint32_t ino ; // ISAM number
// Test inputs
if (!pDN)
Fatal("_hz_zet_isam_Base::_expelData: isam=%d (%s): No taget data node supplied", mz->isamId, *m_Name) ;
ino = pDN->IsamId() ;
x = pDN->Usage() ;
if (x > HZ_ORDSZE) Fatal("_hz_zet_isam_Base::_expelData: isam=%d (%s): Garbage usage value (%d)", mz->isamId, *m_Name, x) ;
if (nSlot > HZ_ORDSZE) Fatal("_hz_zet_isam_Base::_expelData: isam=%d (%s): Illegal slot value (%d)", mz->isamId, *m_Name, nSlot) ;
if (nSlot >= pDN->Usage()) Fatal("_hz_zet_isam_Base::_expelData: isam=%d (%s): Excessive slot value (%d)", mz->isamId, *m_Name, nSlot) ;
mz->m_nElements-- ;
// Exclude the slot
pDN->DecUsage() ;
for (x = nSlot, y = pDN->Usage() ; x < y ; x++)
pDN->setfromCur(x, x+1) ;
pKeys = (KEY*) pDN->Keys() ;
pKeys[pDN->Usage()] = mz->m_Default ;
for (pPar = pDN->parent ; pPar ; pPar = pPar->parent)
pPar->cumulative-- ;
// See if reduced node can be purged
if (pDN->Usage() && pDN->Usage() < HZ_ISAM_LOW)
{
pInfra = (_hz_zet_node_Dat<KEY>*) pDN->Infra() ;
pUltra = (_hz_zet_node_Dat<KEY>*) pDN->Ultra() ;
x = pInfra ? HZ_ORDSZE - pInfra->Usage() : 0 ;
y = pUltra ? HZ_ORDSZE - 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_ORDSZE)
{
for (x = 0 ; pDN->Usage() && pInfra->Usage() < HZ_ORDSZE ; x++)
{
pInfra->setfromUlt(pInfra->Usage(), x) ;
pInfra->IncUsage() ;
pDN->DecUsage() ;
}
for (pPar = pInfra->Parent() ; pPar ; pPar = pPar->parent)
pPar->cumulative += x ;
if (pInfra->IsamId() != ino || pInfra->Usage() < 0 || pInfra->Usage() > HZ_ORDSZE)
Fatal("_hz_zet_isam_Base::_expelData: isam=%d (%s): Infra %d Invalid: isam id (%d) usage (%d)",
ino, *m_Name, pInfra->Ident(), pInfra->IsamId(), pInfra->Usage()) ;
}
if (pUltra && pDN->Usage() && pUltra->Usage() < HZ_ORDSZE)
{
// 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--)
pUltra->setfromCur(y, y - pDN->Usage()) ;
pUltra->SetUsage(pUltra->Usage() + pDN->Usage()) ;
// Move remainder to ultra node
for (y = 0 ; y < pDN->Usage() ; y++)
pUltra->setfromInf(y, x + y) ;
pDN->SetUsage(0) ;
for (pPar = pUltra->Parent() ; pPar ; pPar = pPar->parent)
pPar->cumulative += y ;
if (pUltra->IsamId() != ino || pUltra->Usage() < 0 || pUltra->Usage() > HZ_ORDSZE)
Fatal("_hz_zet_isam_Base::_expelData: isam=%d (%s): Ultra %d Invalid: isam id (%d) usage (%d)",
ino, *m_Name, pUltra->Ident(), pUltra->IsamId(), pUltra->Usage()) ;
}
x += y ;
for (pPar = pDN->Parent() ; pPar ; pPar = pPar->parent)
pPar->cumulative -= x ;
}
}
if (pDN->Usage())
return pDN ;
// Eliminate node: Connect adjacents
pInfra = (_hz_zet_node_Dat<KEY>*) pDN->Infra() ;
pUltra = (_hz_zet_node_Dat<KEY>*) pDN->Ultra() ;
if (pUltra)
pUltra->SetInfra(pInfra) ;
if (pInfra)
pInfra->SetUltra(pUltra) ;
if (pDN->Parent())
_expelIndx(pDN->Parent(), pDN) ;
else
{
delete pDN ;
mz->m_pRoot = 0 ;
}
return 0 ;
}
bool _shownode (_hz_zet_node_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
_hz_zet_node_Idx* pIdx = 0 ; // Index node
_hz_zet_node_Any* pChild ; // Child from slot
_hz_zet_node_Any* pPrev ; // Lower adjacent sibling
_hz_zet_node_Any* pNext ; // Higher adjacent sibling
uint32_t nIndex ; // Iterator of children
uint32_t nTotal ; // Cumulative
uint32_t testA ; // Id of derived node
uint32_t testB ; // Id of derived node
uint32_t par ; // Parent node
uint32_t inf ; // Inferior node
uint32_t sup ; // superior node
bool bError = false ; // Error indicator
par = pNode->Parent() ? pNode->Parent()->Ident() : -1 ;
inf = pNode->Infra()? pNode->Infra()->Ident() : -1 ;
sup = pNode->Ultra()? pNode->Ultra()->Ident() : -1 ;
if (!pNode->Level())
{
if (bData)
plog->Out("\treport isam=%d Data Node %d parent %d inf %d sup %d level %d, usage %2d\n",
mz->isamId, pNode->Ident(), par, inf, sup, pNode->Level(), pNode->Usage()) ;
return true ;
}
pIdx = (_hz_zet_node_Idx*) pNode ;
if (bData)
plog->Out("report isam=%d Index Node %d parent %d inf %d sup %d level %d, usage %2d cumulate %d\n",
mz->isamId, pNode->Ident(), par, inf, sup, 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_ORDSZE)
{ 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_zet_node_Any*) pIdx->m_Ptrs[nIndex] ;
nTotal += pChild->Cumulative() ;
}
if (nTotal != pIdx->Cumulative())
{
bError = true ;
plog->Out(" -- ERROR: Counted cumulative for index node %d is %d, but empirical cumulatives is %d\n", pIdx->m_Id, nTotal, pIdx->Cumulative()) ;
}
// Recurse to higher nodes
for (nIndex = 0 ; nIndex < pIdx->Usage() ; nIndex++)
{
pChild = (_hz_zet_node_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_zet_node_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 (%d) does not have this node (%d) as it's parent. Instead it has (%d)\n",
nIndex, pChild->Ident(), pNode->Ident(), pChild->Parent()?pChild->Parent()->Ident():-1) ;
continue ;
}
// Test siblings
if (nIndex == 0)
{
if (!pIdx->infra && pChild->Infra())
{
bError = true ;
plog->Out(" -- ERROR: Node %d While there is no infra node to this, the zeroth child has an infra (%d)\n",
pIdx->m_Id, pChild->Infra()->Ident()) ;
}
if (pIdx->infra && !pChild->Infra())
{
bError = true ;
plog->Out(" -- ERROR: Node %d There is an infra to this (%d) but the zeroth child does not have an infra\n", pIdx->m_Id, pIdx->infra->m_Id) ;
}
if (pIdx->infra && pChild->Infra())
{
testA = pChild->Infra() && pChild->Infra()->Parent() ? pChild->Infra()->Parent()->Ident() : -1 ;
testB = pIdx->infra ? pIdx->infra->m_Id : -1 ;
if (testA != testB)
{
bError = true ;
plog->Out(" -- ERROR: Node %d The parent of the zeroth child infra (%d) is not the infra of this (%d)\n",
pIdx->m_Id, 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_zet_node_Any*) pIdx->m_Ptrs[nIndex-1] ;
pNext = (_hz_zet_node_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 NodeReport (bool bData = false) 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
hzLogger* plog ; // Current thread logger
hzEcode rc = E_OK ; // Return code
plog = GetThreadLogger() ;
if (plog)
{
if (!mz->m_pRoot)
{ plog->Out("The _hz_zet_isam_Base object is empty\n") ; return E_OK ; }
if (!_shownode(mz->m_pRoot, plog, bData))
rc = E_CORRUPT ;
}
return rc ;
}
hzEcode _integBase (hzLogger* plog, _hz_zet_node_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
_hz_zet_node_Any* pInf ; // Infra to the current node
_hz_zet_node_Any* pUlt ; // Ultra to the current node
_hz_zet_node_Any* pCA ; // Child node A
_hz_zet_node_Any* pCB ; // Child node B
_hz_zet_node_Idx* par ; // Parent of test node
uint32_t n ; // Loop control
uint32_t err = 0 ; // Set if error
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 %d: Infra node %d does not point back to this node\n", pN->Ident(), pInf->Ident()) ; }
if (pUlt && (pUlt->Infra() != pN)) { err=1 ; plog->Out("On node %d: Infra node %d does not point back to this node\n", pN->Ident(), pInf->Ident()) ; }
// 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 %d: Child 0 (%d) has no infra while this node does\n", pN->Ident(), pCA->Ident()) ; }
else
{
par = pCA->Infra()->Parent() ;
if (!par)
{ err=1 ; plog->Out("On node %d: Child 0 (%d) has parent -1 diff to the infra %d\n", pN->Ident(), pCA->Ident(), pInf->Ident()) ; }
if (par && par != pInf)
{ err=1 ; plog->Out("On node %d: Child 0 (%d) has parent %d diff to the infra %d\n", pN->Ident(), pCA->Ident(), par->Ident(), pInf->Ident()) ; }
}
}
// 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 %d: Child 0 (%d) has no infra while this node does\n", pN->Ident(), pCB->Ident()) ; }
else
{
par = pCB->Ultra()->Parent() ;
if (!par)
{ err=1 ; plog->Out("On node %d: Child 0 (%d) has parent -1 diff to the infra %d\n", pN->Ident(), pCB->Ident(), pUlt->Ident()) ; }
if (par && par != pUlt)
{ err=1 ; plog->Out("On node %d: Child 0 (%d) has parent %d diff to the infra %d\n", pN->Ident(), pCB->Ident(), par->Ident(), pUlt->Ident()) ; }
}
}
// 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 %d: Child in slot %d has infra of %d but slot %d points to %d\n", pN->Ident(), n+1, pCA->InfId(), n, pCB->Ident()) ; }
if (pCB->Infra() != pCA)
{ err=1; plog->Out("On node %d: Child in slot %d has ultra of %d but slot %d points to %d\n", pN->Ident(), n, pCA->UltId(), n+1, pCA->Ident()) ; }
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_zet_node_Idx*) pN->m_Ptrs[n]) != E_OK)
err=1;
}
}
return err ? E_CORRUPT : E_OK ;
}
hzEcode 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
_hz_zet_node_Idx* pN ; // ISAM root
hzLogger* plog ; // Current thread logger
if (!mz->m_pRoot)
return E_OK ;
if (!mz->m_pRoot->Level())
return E_OK ;
pN = (_hz_zet_node_Idx*) mz->m_pRoot ;
plog = GetThreadLogger() ;
return _integBase(plog, pN) ;
}
// Set functions
void SetRoot (_hz_zet_node_Any* pN)
{
if (!mz)
Fatal("ISAM %s has no root\n", *m_Name) ;
if (mz->m_pRoot)
Fatal("ISAM %s already has a root\n", *m_Name) ;
mz->m_nElements = 1 ;
mz->m_pRoot = pN ;
}
//void SetInitPop (void) { mz->m_nElements = 1 ; }
// Get functions
KEY& DefaultKey (void) const { return mz->m_Default ; }
_hz_zet_node_Any* Root (void) const { return mz->m_pRoot ; }
uint32_t Nodes (void) const { return mz->m_nNodes ; }
uint32_t Count (void) const { return mz->m_pRoot ? mz->m_pRoot->Cumulative() : 0 ; }
uint32_t Cumulative (void) const { return mz->m_pRoot ? mz->m_pRoot->Cumulative() : 0 ; }
uint32_t Population (void) const { return mz->m_nElements ; }
uint32_t Level (void) const { return mz->m_pRoot ? mz->m_pRoot->Level() : 0 ; }
uint32_t IsamId (void) const { return mz->isamId ; }
hzString Name (void) const { return m_Name ; }
bool IsInit (void) const { return mz ? true : false ; }
} ;
/* Move to hzBasedefs maybe
enum _hz_sbias
{
// Category: Collection Support
//
// ISAM Search Bias
//
// In an ISAM in which the keys must be unique, a simple binary chop comparison process will determine if any given key is present in the ISAM and if it is, give the location.
// However in an ISAM in which the same key can map to many objects, to iterate the objects found under the key, there has to be a method of identifying the first and the last
// object. Simply chopping and comparing until there is a match will not acheive this. Furthermore, in any ISAM regardless of whether keys are to be unique, the slot where the
// new key will go has to be identified and this can go wrong. For example, a new key could have a value that fell between that of slot 3 and 4. The comparison sequence would
// be 7, 3, 5 and then 4. This would be OK because slot 4 is where the new key will go with what was at slot 4 moving to slot 5. If however the new value fell between 2 and 3,
// the comparison sequence would be 7, 3, 1, and then 2. This is wrong as the new key needs to go in at slot 3.
//
// To resolve the matter, extra steps are taken at the end of the binary chop. These differ depending on what is required. The _hz_sbias enum serves to specify the option.
HZ_ISAMSRCH_LO, // Find the first instance of the key within the ISAM or fail
HZ_ISAMSRCH_HI, // Find the last instance of the key within the ISAM or fail
HZ_ISAMSRCH_END // Find the slot where where the key will reside. So if (b) target=(b+1) else target=(lowest slot exceeding the key).
} ;
*/
template<class KEY> static _hz_zet_node_Dat<KEY>* _findDnodeByKey
(uint32_t& nSlot, const _hz_zet_isam_Base<KEY>& isam, const KEY& val, int32_t (*cmpfn)(const KEY&,const KEY&), _hz_sbias eBias)
{
// Category: Collection Support
//
// 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_ct("_findDnodeByKey") ;
_hz_zet_node_Dat<KEY>* pTgt = 0 ; // Target data node
_hz_zet_node_Dat<KEY>* pTst = 0 ; // Target data node
_hz_zet_node_Idx* pIdx = 0 ; // Current index node
_hz_zet_node_Idx* pFwd = 0 ; // Forward pointer
KEY* pKeys ; // Array of keys from data node
int32_t nRes ; // Comparison result
uint32_t nPos ; // Middle of index
uint32_t nDiv ; // Divider
// if (eBias != HZ_ISAMSRCH_LO && eBias != HZ_ISAMSRCH_UIN)
// Fatal("_findDnodeByKey: Illegal bias %d", eBias) ;
if (!cmpfn)
cmpfn = _tmpl_zet_compare ;
nSlot = -1 ;
//if (!isam.mx->m_pRoot)
if (!isam.Root())
return 0 ;
// Find target data node
//if (isam.mx->m_pRoot && isam.mx->m_pRoot->Level() == 0)
if (isam.Root() && isam.Level() == 0)
//pTgt = (_hz_zet_node_Dat*) isam.mx->m_pRoot ;
pTgt = (_hz_zet_node_Dat<KEY>*) isam.Root() ;
else
{
// Determine next level node
//for (pIdx = (_hz_zet_node_Idx*) isam.mx->m_pRoot ; pIdx ;)
for (pIdx = (_hz_zet_node_Idx*) isam.Root() ; pIdx ;)
{
for (nPos = 7, nDiv = 4 ;; nDiv /= 2)
{
if (nPos >= pIdx->usage)
{ nPos -= nDiv ; continue ; }
if (pIdx->level == 1)
pTst = (_hz_zet_node_Dat<KEY>*) pIdx->m_Ptrs[nPos] ;
else
{
for (pFwd = (_hz_zet_node_Idx*) pIdx->m_Ptrs[nPos] ; pFwd->Level() > 1 ; pFwd = (_hz_zet_node_Idx*) pFwd->m_Ptrs[0]) ;
pTst = (_hz_zet_node_Dat<KEY>*) pFwd->m_Ptrs[0] ;
}
// Now do the compare
pKeys = (KEY*) pTst->Keys() ;
nRes = cmpfn(val, pKeys[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_zet_node_Idx*) pIdx->m_Ptrs[nPos] ;
else
{ pTgt = (_hz_zet_node_Dat<KEY>*) pIdx->m_Ptrs[nPos] ; break ; }
}
}
if (!pTgt)
return 0 ;
// Identify the offset
pKeys = (KEY*) pTgt->Keys() ;
for (nRes = 0, nSlot = 7, nDiv = 4 ;; 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 = cmpfn(val, pKeys[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("_findDnodeByKey: isam=%d: Node %d usage %d has offset %d", isam.IsamId(), pTgt->Ident(), pTgt->Usage(), nSlot) ;
return pTgt ;
}
// Deal with HZ_ISAMSRCH_UIN for inserts.
if (nRes > 0)
{
if (nSlot < pTgt->Usage())
nSlot++ ;
if (nSlot == HZ_ORDSZE && pTgt->Ultra())
{
pTgt = (_hz_zet_node_Dat<KEY>*) pTgt->Ultra() ;
nSlot = 0 ;
}
}
if (nSlot > pTgt->Usage())
Fatal("_findDnodeByKey: isam=%d: Node %d usage %d has offset %d", isam.IsamId(), pTgt->Ident(), pTgt->Usage(), nSlot) ;
return pTgt ;
}
template<class KEY> static _hz_zet_node_Dat<KEY>* _findAbsoluteByKey
(uint32_t& nAbs, uint32_t& nSlot, const _hz_zet_isam_Base<KEY>& isam, const KEY& val, int32_t (*cmpfn)(const KEY&, const KEY&), _hz_sbias eBias)
{
// 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 _nodetr(). 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_ct("_findAbsoluteByKey") ;
_hz_zet_node_Dat<KEY>* pDN = 0 ; // Target data node
_hz_zet_node_Dat<KEY>* pMK = 0 ; // Marked data node
KEY* pKeys ; // Array of keys from data node
uint32_t max ; // Top position
uint32_t posn ; // Test position
uint32_t posnMk ; // Marked position
uint32_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 (!isam.Root())
return 0 ;
// Set up initial test position and the divider
max = isam.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 = isam._nodetr(slot, posn, false) ;
pKeys = (KEY*) pDN->Keys() ;
res = cmpfn(val, pKeys[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 = isam._nodetr(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 = isam._nodetr(slot, posn, true) ;
nAbs = posn ;
nSlot = slot ;
return pDN ;
}
template <class KEY> class _hz_isam_val
{
// Category: Collection Support
//
// _hz_isam_val - Single datum ISAM proving insert, delete and lookup by value (effectively a set)
_hz_zet_isam_Base<KEY> isam ; // Underlying ISAM
int32_t (*m_cmpfn)(const KEY&, const KEY&) ; // Compare function (if null this will be _tmpl_zet_compare)
// Prevent copies
_hz_isam_val<KEY> (const _hz_isam_val<KEY>&) ;
_hz_isam_val<KEY>& operator= (const _hz_isam_val<KEY>&) ;
public:
_hz_isam_val (void) { m_cmpfn = _tmpl_zet_compare ; }
~_hz_isam_val (void) { Clear() ; }
void Start (void) { isam.Start() ; }
void SetLock (hzLockOpt eLock) { isam.SetLock(eLock) ; }
void SetName (const hzString& name) { isam.SetName(name) ; }
void SetDefault (const KEY& key) { isam.SetDefault(key) ; }
void SetCompare (int32_t (*cmpfn)(const KEY&, const KEY&))
{
m_cmpfn = cmpfn ;
}
void Clear (void) { isam.Clear() ; }
hzEcode _insUV (const KEY& key)
{
// 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_ct("_hz_isam_val::_insUV") ;
_hz_zet_node_Dat<KEY>* pDN = 0 ; // Current data node
uint32_t nOset ; // Offset into node (set by nodetrace)
// If ordered list is empty
if (!isam.Root())
{
pDN = new _hz_zet_node_Dat<KEY> ;
if (!pDN)
Fatal("_hz_isam_val::_insUV: isam=%d: Could not allocate root node", isam.IsamId()) ;
pDN->m_Keys[0] = key ;
pDN->m_isamId = isam.IsamId() ;
pDN->usage = 1 ;
isam.SetRoot(pDN) ;
return E_OK ;
}
// Locate the 'target' top level node
//pDN = (_hz_zet_node_Dat<KEY>*) _findDnodeByKey(nOset, isam, key, m_cmpfn, HZ_ISAMSRCH_UIN) ;
pDN = (_hz_zet_node_Dat<KEY>*) _findDnodeByKey(nOset, isam, key, m_cmpfn, HZ_ISAMSRCH_END) ;
if (!pDN)
Fatal("_hz_isam_val::_insUV: isam=%d: No data node found", isam.IsamId()) ;
if (nOset > HZ_ORDSZE)
Fatal("_hz_isam_val::_insUV: isam=%d: Illegal slot no %d for node %d", isam.IsamId(), nOset, pDN->m_Id) ;
// If new element has identical key then ignore
if (nOset < HZ_ORDSZE)
{
if (m_cmpfn(key, pDN->m_Keys[nOset]) == 0)
return E_OK ;
}
//isam.mx->m_nElements++ ;
pDN = (_hz_zet_node_Dat<KEY>*) isam._acceptData(pDN, key, nOset) ;
if (Count() != isam.Population())
Fatal("_hz_isam_val::_insUV: isam=%d: Expected population %d, actual %d ", isam.IsamId(), isam.Population(), Count()) ;
if (isam.IntegBase() != E_OK)
Fatal("_hz_isam_val::_insUV: isam=%d: INTEGRITY FAILURE", isam.IsamId()) ;
return E_OK ;
}
hzEcode _delUV (const KEY& key)
{
// 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_ct("_hz_isam_val::_delUV") ;
_hz_zet_node_Dat<KEY>* pDN = 0 ; // Target data node (from which delete will occur)
uint32_t nOset ; // Position within node
// Check args
if (!isam.Root())
return E_NOTFOUND ;
// Locate the 'target' top level node
pDN = (_hz_zet_node_Dat<KEY>*) _findDnodeByKey(nOset, isam, key, m_cmpfn, HZ_ISAMSRCH_LO) ;
if (!pDN)
return E_NOTFOUND ;
if (nOset >= HZ_ORDSZE)
Fatal("_hz_isam_val::_delUV: isam=%d: Illegal slot no %d for node %d", isam.IsamId(), nOset, pDN->m_Id) ;
// Expel the entity from the node
//isam.mx->m_nElements-- ;
pDN = (_hz_zet_node_Dat<KEY>*) isam._expelData(pDN, nOset) ;
if (Count() != isam.Population())
Fatal("_hz_isam_val::_delUV: isam=%d: Expected population %d, actual %d ", isam.IsamId(), isam.Population(), Count()) ;
return E_OK ;
}
KEY& _locatePos (uint32_t nPosn)
{
// Arguments: 1) nPosn Absolute position of element
//
// Returns: Reference to the key part of the resident element (non-const) or the default key if the supplied position is out of range.
_hzfunc_ct("_hz_isam_val::_locatePos") ;
_hz_zet_node_Dat<KEY>* pDN ; // Target ISAM data block
uint32_t nOset ; // Slot obtained from isam._nodetr()
if (!isam.Root() || nPosn >= isam.Cumulative())
//return isam.mx->m_Default ;
return isam.DefaultKey() ;
pDN = (_hz_zet_node_Dat<KEY>*) isam._nodetr(nOset, nPosn, false) ;
if (!pDN)
Fatal("_hz_isam_val::_locatePos: isam=%d: Data node not found for position %d", isam.IsamId(), nPosn) ;
if (nOset < 0 || nOset >= pDN->Usage())
Fatal("_hz_isam_val::_locatePos: isam=%d: Data node %d: Offset is %d, usage is %d", isam.IsamId(), pDN->m_Id, nOset, pDN->Usage()) ;
return pDN->m_Keys[nOset] ;
}
const KEY& _c_locatePos (uint32_t nPosn) const
{
// Arguments: 1) nPosn Absolute position of element
//
// Returns: Reference to the key part of the resident element (const) or the default key if the supplied position is out of range.
_hzfunc_ct("_hz_isam_val::_c_locatePos") ;
_hz_zet_node_Dat<KEY>* pDN ; // Target ISAM data block
uint32_t nOset ; // Slot obtained from isam._nodetr()
if (!isam.Root() || nPosn >= isam.Cumulative())
//return isam.mx->m_Default ;
return isam.DefaultKey() ;
pDN = (_hz_zet_node_Dat<KEY>*) isam._nodetr(nOset, nPosn, false) ;
if (!pDN)
Fatal("_hz_isam_val::_c_locatePos: isam=%d: Data node not found for position %d", isam.IsamId(), nPosn) ;
if (nOset >= pDN->Usage())
Fatal("_hz_isam_val::_c_locatePos: isam=%d: Data node %d: Offset is %d, usage is %d", isam.IsamId(), pDN->m_Id, nOset, pDN->Usage()) ;
return pDN->m_Keys[nOset] ;
}
KEY& _locUV (const KEY& key) const
{
// Arguments: 1) key Key value to search for
//
// Returns: Reference to the key part of the resident element or the default key if the supplied key does not exist.
_hzfunc_ct("_hz_isam_val::_locUV") ;
_hz_zet_node_Dat<KEY>* pDN ; // Target ISAM data block
uint32_t nOset ; // Slot obtained
if (!isam.Root())
//return isam.mx->m_Default ;
return isam.DefaultKey() ;
pDN = (_hz_zet_node_Dat<KEY>*) _findDnodeByKey(nOset, isam, key, m_cmpfn, HZ_ISAMSRCH_LO) ;
if (!pDN)
//return isam.mx->m_Default ;
return isam.DefaultKey() ;
if (nOset >= pDN->Usage())
Fatal("_hz_isam_val::_locUV: Isam %d Data node %d: Offset is %d, usage is %d", isam.IsamId(), pDN->m_Id, nOset, pDN->Usage()) ;
return pDN->m_Keys[nOset] ;
}
int32_t _getPosByKey (const KEY& key, _hz_sbias eBias) const
{
// Arguments: 1) key Key to search for
// 2) eBias Search bias
//
// Returns: Value being the current absolute position of the entry matching the supplied KEY and bias
_hzfunc_ct("_hz_isam_val::_getPosByKey") ;
_hz_zet_node_Dat<KEY>* pDN ; // Target ISAM data block
uint32_t nOset ; // Slot obtained
uint32_t nAbs ; // Absolute position
if (!isam.Root())
return -1 ;
pDN = _findAbsoluteByKey(nAbs, nOset, isam, key, m_cmpfn, eBias) ;
if (!pDN)
return -1 ;
return nAbs ;
}
bool _exists (const KEY& key) const
{
uint32_t nOset ; // Slot obtained
return _findDnodeByKey(nOset, isam, key, m_cmpfn, HZ_ISAMSRCH_LO) ? true : false ;
}
hzEcode Integrity (void) const
{
// Test integrity of the ISAM. This was a relic of early development days but has been left in for the benefit of testing any future changes. There are
// no circumstances where an application should ever have to test ISAM integrity.
//
// Arguments: None
//
// Returns: E_CORRUPT Integrity failure
// E_OK Integrity test passed
_hz_zet_node_Dat<KEY>* pA ; // Data block of lower position
_hz_zet_node_Dat<KEY>* pB ; // Data block of higher position
uint32_t osetA ; // Data block offset of lower position
uint32_t osetB ; // Data block offset of higher position
uint32_t nItems ; // Number of elements
uint32_t nCount ; // Element iterator
int32_t res ; // Comparison result
hzEcode rc = E_OK ; // Return code
nItems = Count() ;
if (nItems < 2)
return E_OK ;
for (nCount = 1 ; rc == E_OK && nCount < nItems ; nCount++)
{
pA = (_hz_zet_node_Dat<KEY>*) isam._nodetr(osetA, nCount-1, false) ;
pB = (_hz_zet_node_Dat<KEY>*) isam._nodetr(osetB, nCount, false) ;
res = m_cmpfn(pB->m_Keys[osetB], pA->m_Keys[osetA]) ;
if (!res) { threadLog("isam=%d pop %d - Integrity fails duplicate at posn %d\n", isam.IsamId(), Count(), nCount) ; rc = E_CORRUPT ; }
if (res<0) { threadLog("isam=%d pop %d - Integrity fails order at posn %d\n", isam.IsamId(), Count(), nCount) ; rc = E_CORRUPT ; }
}
return rc ;
}
hzEcode NodeReport (bool bData) const { isam.NodeReport(bData) ; }
uint32_t Count (void) const { return isam.Count() ; }
uint32_t Level (void) const { return isam.Level() ; }
uint32_t IsamId (void) const { return isam.IsamId() ; }
bool IsInit (void) const { return isam.IsInit() ; }
} ;
/*
** Section 3 The Indexed Collection Class Templates
*/
/*
** The formal hzMapS template
*/
/*
** The hzSet template
*/
template<class KEY> class hzSet
{
// Category: Object Collection
//
// The hzSet template is a memory resident set of unique objects. It is similar to hzMapS except that the objects serve as thier own keys. Note that the objects
// must have the comparison operators implimented.
_hz_isam_val<KEY> m_Data ; // _hz_isam_val ordered list by value
// Prevent copies
hzSet<KEY> (const hzSet<KEY>&) ;
hzSet<KEY>& operator= (const hzSet<KEY>&) ;
public:
hzSet (void) { m_Data.Start() ; m_Data.SetLock(HZ_NOLOCK) ; _hzGlobal_Memstats.m_numSets++ ; }
hzSet (hzLockOpt eLock) { m_Data.Start() ; m_Data.SetLock(eLock) ; _hzGlobal_Memstats.m_numSets++ ; }
hzSet (const hzString& name) { m_Data.Start() ; m_Data.SetLock(HZ_NOLOCK) ; m_Data.SetName(name) ; _hzGlobal_Memstats.m_numSets++ ; }
hzSet (hzLockOpt eLock, const hzString& name) { m_Data.Start() ; m_Data.SetLock(eLock) ; m_Data.SetName(name) ; _hzGlobal_Memstats.m_numSets++ ; }
~hzSet (void) { _hzGlobal_Memstats.m_numSets-- ; }
// Inits
void SetCompare (int32_t (*cmpfn)(const KEY&, const KEY&)) { m_Data.SetCompare(cmpfn) ; }
void SetName (const hzString& name) { m_Data.SetName(name) ; }
void SetLock (hzLockOpt eLock) { m_Data.SetLock(eLock) ; }
void SetDefault (KEY val) { m_Data.SetDefault(val) ; }
// Data operations
void Clear (void) { m_Data.Clear() ; }
// hzEcode Insert (const KEY& key) { _hzfunc("hzSet::Insert") ; return m_Data._insUV(key) ; }
// hzEcode Delete (const KEY& key) { _hzfunc("hzSet::Insert") ; return m_Data._delUV(key) ; }
hzEcode Insert (const KEY& key) { return m_Data._insUV(key) ; }
hzEcode Delete (const KEY& key) { return m_Data._delUV(key) ; }
// Lookup
const KEY& GetObj (uint32_t nIndex) const { return m_Data._c_locatePos(nIndex) ; }
KEY& GetReal (uint32_t nIndex) { return m_Data._locatePos(nIndex) ; }
bool Exists (const KEY& key) const { return m_Data._exists(key) ; }
KEY& operator[] (const KEY& key) const { return m_Data._locUV(key) ; }
// Diagnostics
uint32_t Nodes (void) const { return m_Data.Nodes() ; }
uint32_t Count (void) const { return m_Data.Count() ; }
bool IsInit (void) const { return m_Data.IsInit() ; }
hzEcode Integrity (void) const { return m_Data.Integrity() ; }
hzEcode NodeErrors (void) const { return m_Data.NodeReport(true) ; }
hzEcode NodeReport (void) const { return m_Data.NodeReport(false) ; }
} ;
#endif