IOFireWireLibCoalesceTree.cpp [plain text]
#import "IOFireWireLibCoalesceTree.h"
#import <unistd.h>
namespace IOFireWireLib {
CoalesceTree::CoalesceTree()
{
mTop = nil ;
}
CoalesceTree::~CoalesceTree()
{
DeleteNode(mTop) ;
}
void
CoalesceTree::DeleteNode(Node* inNode)
{
if (inNode)
{
DeleteNode(inNode->left) ;
DeleteNode(inNode->right) ;
delete inNode ;
}
}
void
CoalesceTree::CoalesceRange(const IOVirtualRange& inRange)
{
if ( inRange.address == 0 or inRange.length == 0)
return ;
IOVirtualRange range = { trunc_page(inRange.address), round_page( (inRange.address & getpagesize() - 1) + inRange.length - 1) } ;
if (mTop)
CoalesceRange(range, mTop) ;
else
{
mTop = new Node ;
mTop->left = nil ;
mTop->right = nil ;
mTop->range.address = range.address ;
mTop->range.length = range.length ;
}
}
void
CoalesceTree::CoalesceRange(const IOVirtualRange& inRange, Node* inNode)
{
if (inRange.address > inNode->range.address)
{
if ( (inRange.address - inNode->range.address) <= inNode->range.length)
{
inNode->range.length = inNode->range.length >? ( inRange.address + inRange.length - inNode->range.address) ;
}
else
if (inNode->right)
CoalesceRange(inRange, inNode->right) ;
else
{
inNode->right = new Node ;
inNode->right->left = nil ;
inNode->right->right = nil ;
inNode->right->range.address = inRange.address ;
inNode->right->range.length = inRange.length ;
}
}
else
{
if ((inNode->range.address - inRange.address) <= inRange.length)
{
inNode->range.length = inRange.length >? ( inNode->range.address + inNode->range.length - inRange.address) ;
inNode->range.address = inRange.address ;
}
else
if (inNode->left)
CoalesceRange(inRange, inNode->left) ;
else
{
inNode->left = new Node ;
inNode->left->left = nil ;
inNode->left->right = nil ;
inNode->left->range.address = inRange.address ;
inNode->left->range.length = inRange.length ;
}
}
}
const UInt32
CoalesceTree::GetCount() const
{
return GetCount(mTop) ;
}
const UInt32
CoalesceTree::GetCount(Node* inNode) const
{
if (inNode)
return 1 + GetCount(inNode->left) + GetCount(inNode->right) ;
else
return 0 ;
}
void
CoalesceTree::GetCoalesceList(IOVirtualRange* outRanges) const
{
UInt32 index = 0 ;
GetCoalesceList(outRanges, mTop, & index) ;
}
void
CoalesceTree::GetCoalesceList(IOVirtualRange* outRanges, Node* inNode, UInt32* pIndex) const
{
if (inNode)
{
GetCoalesceList(outRanges, inNode->left, pIndex) ;
outRanges[*pIndex].address = inNode->range.address ;
outRanges[*pIndex].length = inNode->range.length ;
++(*pIndex) ;
GetCoalesceList(outRanges, inNode->right, pIndex) ;
}
}
}