Defined in file: hzIsamT.h
The hzVect class template provides a form of vector or an array. The elements are accessible via the [] operator but are held in an _hz_isam_vect ISAM rather than in a contiguous buffer. This confers the advantage of avoiding expensive reallocation in the general case where the number of elements is not known in advance but with the caveat that elements have relative rather then absolute addresses. Note that as the [] operator returns a reference to an element, out of range calls must return something and to this end hzVect has a default element which is returned in this event. The default element is created by default hzVect construction and so is 'empty' but this is the only guide to the calling program that the requested element was out of range. Note that in stark contrast to the vector class template of the STL, the [] operator NEVER creates elements. This must be done explicitly either by the Add() method which always places the new element at the end or the Insert() method which requires an additional argument to indicate the position. Errors: The only relevant error that can occur is that of memory allocaton which currently causes imeadiate termination of the progrem.
Constructors/Detructors
| _hz_tmpl_ISAM* | _hz_tmpl_ISAM | (_hz_tmpl_ISAM&) | |
| _hz_tmpl_ISAM* | _hz_tmpl_ISAM | (void) | |
| void | ~_hz_tmpl_ISAM | (void) |
Public Methods:
| 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 |
| uint32_t | Count | (void) | |
| uint32_t | Cumulative | (void) | |
| _hz_vn_Dat* | DeleteKey | (int32_t& nSlot)const void* pKey, | |
| hzEcode | 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. |
| _hz_vn_Dat* | InsertKeyM | (int32_t& nSlot)const void* pKey, | Purpose: Insert an element by non-unique value. 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 |
| _hz_vn_Dat* | InsertKeyU | (int32_t& nSlot)const void* pKey, | Purpose: Insert an element by unique value. 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 |
| _hz_vn_Dat* | InsertPosn | (int32_t& nSlot)uint32_t nPosn, | Purpose: Insert an element at position. |
| hzEcode | IntegBase | (void) | 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 |
| uint32_t | IsamId | (void) | |
| uint32_t | Level | (void) | |
| void | LockRead | (void) | |
| void | LockWrite | (void) | |
| hzString | Name | (void) | |
| hzEcode | NodeReport | (bool bData) | 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 |
| uint32_t | Nodes | (void) | |
| uint32_t | Population | (void) | |
| _hz_vn_Any* | Root | (void) | |
| void | SetLock | (hzLockOpt eLock) | |
| void | SetName | (hzString& name) | |
| void | Start | (uint32_t nSizeKey)uint32_t nSizeObj, | |
| void | Unlock | (void) | |
| _hz_vn_Dat* | _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. |
| hzEcode | _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. |
| void | _clear | (void) | Clear the map of all keys and elements. Calls recursive _clearnode() function on the root node. |
| void | _clearnode | (_hz_vn_Any* pBlk) | Recursively clear supplied node and any child nodes |
| _hz_vn_Dat* | _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. 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. |
| void | _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. Returns: None |
| _hz_vn_Dat* | _findAllByKey | (int32_t& nSlot)uint32_t& nAbs, const void* pKey, _hz_sbias eBias, | 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 ... Pointer to the data node if the key is matched, NULL pointer otherwise. Note that numeric iterators are invalidated by insert and delete operations. |
| _hz_vn_Dat* | _findDnodeByKey | (int32_t& nSlot)const void* pKey, _hz_sbias eBias, | 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. Pointer to the data node if the key is matched, NULL pointer otherwise. |
| _hz_vn_Dat* | _findDnodeByPos | (int32_t& nSlot)uint32_t nPosn, bool bExpand, | 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. Pointer to the data node for the element |
| hzEcode | _integBase | (hzLogger* plog)_hz_vn_Idx* pN, | Quick index node integrity test |
| void | _moveElement | (_hz_vn_Dat* pNodeTgt)_hz_vn_Dat* pNodeSrc, uint32_t tgtSlot, uint32_t srcSlot, | Move object from one bucket to another |
| bool | _shownode | (_hz_vn_Any* pNode)hzLogger* plog, bool bData, | Support function to Show(). Prints out elements for a given node. |
Overloaded operators:
| _hz_tmpl_ISAM& | operator= | (_hz_tmpl_ISAM&) |
Member Variables:
| hzString | m_Name | Optional ISAM name (all ISAM dependent templates use this) | |
| int32_t(*)(const void*,_hz_vn_Dat*,uint32_t) | m_compare | No description | |
| uint32_t | m_isamId | For diagnostics | |
| uint32_t | m_nElements | Number of data objects | |
| uint32_t | m_nNodes | Number of nodes (also as node id allocator) | |
| uint16_t | m_nSizeKey | Key size | |
| uint16_t | m_nSizeObj | Object size | |
| hzLocker* | m_pLock | Locking (off by default) | |
| _hz_vn_Any* | m_pRoot | Start of index |