CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > Class Template Reference

Tree node class to handle internal tree tasks and hash management. More...

#include <HashTreeNode.h>

Inheritance diagram for CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >:

Public Member Functions
CHashContainer< hashClass >	SubTreeHash (uint64 nPath, uint8 levelBottom)
	CHashTreeNode (CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &cTree, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *pParent=NULL)
	CHashTreeNode (uint64 nLength, uint8 nLevel=0)
	CHashTreeNode (CFile &cFile, uint64 nPath=0, uint8 nLevel=0, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *pParent=NULL)
	CHashTreeNode (uint8 *pData, uint32 nData, uint8 nLevel=0, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *pParent=NULL)
	CHashTreeNode (CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *pParent=NULL)
	~CHashTreeNode (void)
void	Init (void)
	Sets a few common internal values.
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	operator[] (uint64 nodeID)
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	FindNodePath (uint64 nPath, uint8 nLevel, bool nCreate=false)
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	FindNodeNum (uint64 nodeID)
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	DeleteNodePath (uint64 nPath, uint8 nLevel)
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	DeleteNodeNum (uint64 nodeID)
uint32	GetHashTreeList (uint64 nPath, uint8 levelTop, uint8 levelBottom, uint32 *pList)
uint32	GetHashStripList (uint64 nPath, uint8 nLevel, uint16 nHashes, uint32 *pList)
uint32	GetHashListList (uint16 nHashes, uint64 *pIDList, uint32 *pList)
uint32	GetHashDiffList (uint16 nHashes, uint64 *pIDList, uint64 *pList, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &cTree)
void	SaveTree (CFile &cFile)
uint8	Verify (uint64 nPath, uint8 nLevel, uint8 nSecured)
uint32	InsertTree (uint64 nPath, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &cTree)
bool	Graft (uint64 nPath, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *pTree)
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	Prune (uint64 nPath, uint8 nLevel)
bool	Trim (uint8 nLevel)
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &	operator= (CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &cTree)
	Subtree assignment operator.
Static Public Member Functions
uint8	SetIOLevel (uint8 nIOLevel)
	Sets a new block IO level. BlockIOLevel must always be greater or equal to CSBuildup.
uint8	GetIOLevel (void)
	Gets the current block IO level.
uint8	SetKeepLevel (uint8 nKeep)
	Sets a new keep level. Done through functions in case some checking is necessary.
uint8	GetKeepLevel (void)
	Gets the current keep level.
Protected Types
enum	NODE_Status {   NODE_Undefined = 0x00, NODE_Valid = 0x01, NODE_Complete = 0x02, NODE_OnDisk = 0x04,   NODE_Changed = 0x08, NODE_ICHKeep = 0x10, NODE_Singleton = 0x20, NODE_Verified = 0x40,   NODE_Secured = 0x80, NODE_Flags = NODE_Verified | NODE_ICHKeep | NODE_Singleton | NODE_Secured }
	Enumeration of possible node states. Nothing final here. More...
Protected Member Functions
uint32	HashBlock (uint8 *pData, uint32 nData)
uint32	HashFile (CFile &cFile, uint64 nPath)
Protected Attributes
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	nodePtr [2]
	Holds the pointers to the odd and even child branches for the binary tree structure.
CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *	nodeParent
	Pointer to the upper level node.
uint8	nodeLevel
	Stores the node level locally. An extra byte of RAM could be spared by passing this down the tree structure through every function call but it would be horribly nagging since nearly every member function needs it.
uint8	nodeFlags
	Stores the node's status, see NODE_Status for possible values.
Static Protected Attributes
uint8	KeepLevel = CSBase
	Lowest level to make available and maintain permanently.
uint8	BlockIOLevel = CSBuildup + 1
	Level at which block IOs are done.
Private Member Functions
bool	GSTHList (STHListStruc *STHListuint8, uint8 nDepth=0)
bool	GSTHHash (CHashContainer< hashClass > *cHash, uint8 *pData=NULL, uint32 nData=0)
bool	GSTHHash (uint8 *pData=NULL, uint32 nData=0)
	A simple override of GSTHHash() to make it work with implied 'this' cHash.
Static Private Attributes
const CString	CLASSNAME = CString("CHashTreeNode/") + StaticAlgorithmName()
	Defines this class' name.

---

Detailed Description

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth>
class CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >

Tree node class to handle internal tree tasks and hash management.

---

Member Enumeration Documentation

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> enum CHashTreeNode::NODE_Status [protected]

Enumeration of possible node states. Nothing final here. Enumeration values: NODE_Undefined  No hash assigned yet. NODE_Valid  Set if the node contains a valid hash. Validity is gain from the bottom. NODE_Complete  Nodes required to compute this node's hash are available. NODE_OnDisk  Set if nodes below have been dumped to disk to recover RAM. NODE_Changed  Set if the node's hash has changed and re-verification/generation of the higher levels is required. NODE_ICHKeep  Node flagged by ICH for delayed trimming. NODE_Singleton  This node only has an even branch. Should only happen on the EOF branch. NODE_Verified  Subtree has connected with a secured hash. NODE_Secured  Node successfully hashed into the secured top tree. Security is gained from the tree's top. NODE_Flags  Sticky flags.

---

Constructor & Destructor Documentation

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::CHashTreeNode (  CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &  cTree, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *  pParent = NULL )

Subtree copy constructor. Parameters: cTree  Tree node to copy from. pParent  Parent to attach the copy to, NULL for a stray copy.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::CHashTreeNode (  uint64  nLength, uint8  nLevel = 0 )

Creates a blank root node. Parameters: nLength  Size of the file to determine top level from, zero to force a node level. nLevel  Forced node level when nLength=0.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::CHashTreeNode (  CFile &  cFile, uint64  nPath = 0, uint8  nLevel = 0, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *  pParent = NULL )

Construct a tree from a file. Parameters: cFile  Open file object reference from which to extract data. nPath  Block path to generate a tree for. nLevel  Node level (block size along the path) to gerate a tree from. pParent  This node's parent, NULL for a top node. Warning: Do not hash zero-length files - this should never happen and log(0) = -infinity.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::CHashTreeNode (  uint8 *  pData, uint32  nData, uint8  nLevel = 0, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *  pParent = NULL )

Construct a (sub-)tree from memory block. Parameters: nLevel  This node's tree level. pData  Pointer to memory block used for hashing. nData  Number of bytes to hash. pParent  This node's parent, NULL for a top node. Warning: Do not hash zero-length data blocks - this should never happen and log(0) = -infinity.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::CHashTreeNode (  CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *  pParent = NULL  )

Creates an empty node. Parameters: pParent  This node's parent, NULL for a top node.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::~CHashTreeNode (  void   )

Destroy children objects when the node is destroyed. Modders: To delete anything less than a whole tree, use DeleteNode.

---

Member Function Documentation

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > * CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::DeleteNodeNum (  uint64  nodeID  )

Delete subtree by top node number. Parameters: nodeID  Node number as determined by normal creation order. Returns: NULL pointer on hit signals that the upper node must delete this node.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > * CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::DeleteNodePath (  uint64  nPath, uint8  nLevel )

Delete subtree by top node path and level. Parameters: nLevel  Node level to search down to. nPath  Binary tree path to follow. Returns: NULL if the node should be deleted by the upper level.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > * CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::FindNodeNum (  uint64  nodeID  )

Find node by node number. Parameters: nodeID  Node number as determined by normal creation order. Returns: Pointer to the requested node.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > * CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::FindNodePath (  uint64  nPath, uint8  nLevel, bool  nCreate = false )

Find node by node path and level. Parameters: nLevel  Node level to search down to. nPath  Binary tree path to follow. nCreate  Wether or not to create missing nodes along the path. Returns: Pointer to the requested node.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::GetHashDiffList (  uint16  nHashes, uint64 *  pIDList, uint64 *  pList, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &  cTree )

Creates a hash list of differences between two sub-trees. Parameters: nHashes  Number of requested hashes. pIDList  List of node IDs to acquire hashes from. pList  Pointer to the pre-allocated buffer where the list will be stored. cTree  Top tree node to compare with. Returns: Number of uint64 IDs appended to the list, extraction stops at the first NULL node or list exhaustion. Todo: Implement.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::GetHashListList (  uint16  nHashes, uint64 *  pIDList, uint32 *  pList )

Creates a hash list corresponding to the requested node list. Parameters: nHashes  Number of requested hashes. pIDList  List of node IDs to acquire hashes from. pList  Pointer to the pre-allocated buffer where the hashes will be stored. Returns: Number of uint32 appended to the list, extraction stops at the first NULL node or list exhaustion. Todo: Implement.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::GetHashStripList (  uint64  nPath, uint8  nLevel, uint16  nHashes, uint32 *  pList )

Creates a hash strip of from a specified level starting at the specified path crossing. Parameters: nLevel  Level at which to extract hashes from. nHashes  Number of requested hashes. nPath  Binary tree path where to start extracting hashes from. pList  Pointer to the pre-allocated buffer where the hashes will be stored. Returns: Number of uint32 appended to the list, extraction stops at the first NULL node or request size. Todo: Implement.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::GetHashTreeList (  uint64  nPath, uint8  levelTop, uint8  levelBottom, uint32 *  pList )

Creates a list of hashes along a path coverling the specified level range. Parameters: levelTop  Top node level along the path to start acquiring hashes from. levelBottom  Bottom node level along the path to stop acquiring hashes from. nPath  Binary tree path to follow. pList  Pointer to the pre-allocated buffer where the hashes will be stored. Returns: Number of uint32 appended to the list, extraction stops at the first NULL node or request size.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.GetIOLevel (  void   )  [static]

Gets the current block IO level.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.GetKeepLevel (  void   )  [static]

Gets the current keep level.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> bool CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::Graft (  uint64  nPath, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > *  pTree )

Grafts a subtree to the tree. Parameters: nPath  Path where to attach the subtree to. pTree  pointer to the subtree to Graft. The tree owns the subtree after this. Returns: True on success.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> bool CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.GSTHHash (  uint8 *  pData = NULL, uint32  nData = 0 )  [private]

A simple override of GSTHHash() to make it work with implied 'this' cHash.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> bool CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::GSTHHash (  CHashContainer< hashClass > *  cHash, uint8 *  pData = NULL, uint32  nData = 0 )  [private]

Computes a sub-tree hash from a sub-tree hash list. Parameters: pData  Pointer to memory block used for hashing. nData  Number of bytes to hash. cHash  Hash container to assign the hash result to. Returns: True if all hashes were collected, false otherwise.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> bool CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::GSTHList (  STHListStruc *  STHList, uint8  nDepth = 0 )  [private]

Creates a list of hashes required to generate a sub-tree hash. Parameters: nDepth  Hash collection level depth counter. STHList  Pointer to the STHListStruc structure to store hashes and states in. Returns: True if all hashes were collected, false otherwise.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::HashBlock (  uint8 *  pData, uint32  nData )  [protected]

This function builds trees from data blocks (presumably from HashFile() or the block-hash constructor variant.), do not use for anything else! Parameters: pData  Pointer to memory block used for hashing. nData  Number of bytes to hash. Todo: Find something else to return since the return value is now meaningless. This should not happen.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::HashFile (  CFile &  cFile, uint64  nPath )  [protected]

This function creates a complete hash tree from a file, do not use for anything else! Parameters: cFile  Open file object reference from which to extract data. nPath  Binary tree path to follow. Todo: Find something else to return since the return value is now meaningless. I'd like to move all the file-oriented stuff to CHashTreeCtrl and have the tree focussed on data blocks only but because this was an implementation nightmare and would be less efficient, I have decided to leave it as it is - at least for the time being. Find this block's range, allocate the buffer, read the file and hash the block.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> void CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::Init (  void   )

Sets a few common internal values.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint32 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::InsertTree (  uint64  nPath, CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &  cTree )

Inserts a sub-tree into the main tree. Parameters: nPath  Path to the insertion point. cTree  Tree to insert if compatible. Todo: Implement better/finer ways of handlong various confidence levels. The current implementation will strictly discard subtrees that clash with the valid/secured top tree and blindly accept anything that does not.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > & CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::operator= (  CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > &  cTree  )

Subtree assignment operator.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >* CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.operator[] (  uint64  nodeID  )

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth > * CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::Prune (  uint64  nPath, uint8  nLevel )

Prunes (detach/release) a subtree from the tree. Parameters: nLevel  Level at which to apply pruning. nPath  Path along which pruning is going to occur. Returns: Pruned node's pointer on success, NULL otherwise. The caller owns the subtree after this.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> void CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::SaveTree (  CFile &  cFile  )

Save the tree to file. Parameters: cFile  Open file to which to save the hashes.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.SetIOLevel (  uint8  nIOLevel  )  [static]

Sets a new block IO level. BlockIOLevel must always be greater or equal to CSBuildup.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.SetKeepLevel (  uint8  nKeep  )  [static]

Sets a new keep level. Done through functions in case some checking is necessary.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashContainer<hashClass> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.SubTreeHash (  uint64  nPath, uint8  levelBottom )

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> bool CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::Trim (  uint8  nLevel  )

Trims unprotected subtrees below the specified level. Parameters: nLevel  Level below which to start deleting unlocked branches. Returns: true if this node can be deleted.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::Verify (  uint64  nPath, uint8  nLevel, uint8  nSecured )

Subtree verification. Parameters: nLevel  Target node verification level. nSecured  Lowest secured level above the current node. nPath  Binary tree path to follow. Returns: Lowest complete level, or'd with the node's Secured flag. (0x80)

---

Field Documentation

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::BlockIOLevel = CSBuildup + 1 [static, protected]

Level at which block IOs are done. When the hash recursion reaches this level during a file hash, a block of 1<<level bytes is loaded and the recursion is then passed to the data block hash function which carries on the hashing down to the final (CSBase) level. This should always be greater or equal to CSBuildup.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> const CString CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::CLASSNAME = CString("CHashTreeNode/") + StaticAlgorithmName() [static, private]

Defines this class' name. Reimplemented from CHashContainer< hashClass >. Reimplemented in CHashTreeCtrl< hashClass >.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >::KeepLevel = CSBase [static, protected]

Lowest level to make available and maintain permanently. When performing clean-up, all tree levels below this are discarded once no longer required for the immediate task in order to conserve memory. A lower value means more hashes will be kept, leading to a larger tree size and smaller shareable fragment size. This effectively allows the user to select his preferred minimum fragment size. This must obviously be a higher value than CSBase.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.nodeFlags [protected]

Stores the node's status, see NODE_Status for possible values.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> uint8 CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.nodeLevel [protected]

Stores the node level locally. An extra byte of RAM could be spared by passing this down the tree structure through every function call but it would be horribly nagging since nearly every member function needs it.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >* CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.nodeParent [protected]

Pointer to the upper level node.

template<class hashClass, uint8 CSBase, uint8 CSBuildup, uint8 CSDepth> CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >* CHashTreeNode< hashClass, CSBase, CSBuildup, CSDepth >.nodePtr[2] [protected]

Holds the pointers to the odd and even child branches for the binary tree structure.

---

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

• HashTreeNode.h
• HashTreeNode.cpp

---