hnsrtreefileobj.cpp

SR-tree is an index structure for high-dimensional nearest neighbor queries

		    &blockSize, &splitFactor, &reinsertFactor,
		    &staticAlgorithm, &nonLeafFloatType,
		    &neighborAlgorithm);

    fileSize = blockSize;
    freeOffset = -1;
    rootOffset = 0;
    height = 0;

    info = new_HnSRTreeInfo(dimension, dataItemSize,
			    fileSize, freeOffset, rootOffset, height,
			    blockSize, splitFactor, reinsertFactor,
			    staticAlgorithm, nonLeafFloatType,
			    neighborAlgorithm);

    /*
     * NOTE:
     *	    The algorithm of the VAMSplit R-tree requires that
     *	    the capacity of a non-leaf node should be greater than or
     *      equal to three.
     */
    if ( HnSRTreeNode::getMaxCount(info) < 3 ) {
	HnAbort("the block size (%d) is too small; "
		"at least three entries should be allocated "
		"in a non-leaf node.", blockSize);
    }
    if ( HnSRTreeLeaf::getMaxCount(info) < 1 ) {
	HnAbort("the block size (%d) is too small; "
		"at least one entry should be allocated in a leaf node.",
		blockSize);
    }

    blockFile = new_HnBlockFile(path, blockSize);
    if ( blockFile == HnBlockFile::null ) {
	setConstructorFailureFlag();
	return;
    }

    switch ( info.getStaticAlgorithm() ) {
    case HnSRTreeInfo::VAM_ORIGINAL:
    case HnSRTreeInfo::VAM_CORRECTED:
	constructTree_VAM(points, dataItems);
	break;
    default:
	HnAbort("unexpected value for ``staticAlgorithm'' (%d).",
		info.getStaticAlgorithm());
    }
}

HnSRTreeFileObj::HnSRTreeFileObj(const char *path, const char *mode)
{
    initialize();

    if ( strcmp(mode, "rw") == 0 ) {
	blockFile = new_HnBlockFile(path, "rw");
	if ( blockFile == HnBlockFile::null ) {
	    setConstructorFailureFlag();
	    return;
	}
    }
    else if ( strcmp(mode, "r") == 0 ) {
	blockFile = new_HnBlockFile(path, "r");
	if ( blockFile == HnBlockFile::null ) {
	    setConstructorFailureFlag();
	    return;
	}
    }
    else {
	HnAbort("mode must be `r' or `rw'");
    }

    readSuperBlock();
}

HnSRTreeFileObj::~HnSRTreeFileObj(void)
{
    if ( blockFile != HnBlockFile::null ) {
	blockFile.close();
    }

    dispose();
}

void
HnSRTreeFileObj::close(void)
{
    if ( blockFile != HnBlockFile::null ) {
	blockFile.close();
    }
    blockFile = HnBlockFile::null;
}

/*
 * Super Block
 */

void
HnSRTreeFileObj::writeSuperBlock(void)
{
    HnBlockStream blockStream;

    blockStream = new_HnBlockStream(blockFile.getSuperBlockCapacity());
    blockStream.rewind();
    info.writeTo(blockStream);

    blockFile.writeSuperBlock(blockStream);

    profile->numSuperBlockWrites ++;
}

void
HnSRTreeFileObj::readSuperBlock(void)
{
    HnBlockStream blockStream;

    blockStream = new_HnBlockStream(blockFile.getSuperBlockCapacity());
    blockFile.readSuperBlock(blockStream);

    blockStream.rewind();
    info = new_HnSRTreeInfo(blockStream);

    profile->numSuperBlockReads ++;
}

/*
 * Block
 */

void
HnSRTreeFileObj::writeBlock(const HnSRTreeBlock &block)
{
    blockFile.writeBlock(block.getOffset(), block.getBlockStream());

    if ( block.isNode() ) {
	profile->numNodeBlockWrites ++;
    }
    else {
	profile->numLeafBlockWrites ++;
    }
}

HnSRTreeBlock
HnSRTreeFileObj::readBlock(long offset)
{
    HnBlockStream blockStream;
    HnSRTreeBlock block;

    blockStream = new_HnBlockStream(blockFile.getBlockSize());
    blockFile.readBlock(offset, blockStream);
    block = new_HnSRTreeBlock(offset, blockStream);

    if ( block.isNode() ) {
	profile->numNodeBlockReads ++;
    }
    else {
	profile->numLeafBlockReads ++;
    }

    return block;
}

long
HnSRTreeFileObj::allocateBlock(void)
{
    long offset;

    if ( info.getFreeOffset() < 0 ) {
	offset = info.getFileSize();
	info.setFileSize(info.getFileSize() + info.getBlockSize());

	writeSuperBlock();
    }
    else {
	HnSRTreeBlock block;
	HnBlockStream body;

	offset = info.getFreeOffset();

	block = readBlock(info.getFreeOffset());

	if ( block.getType() != HnSRTreeBlock::FREE ) {
	    HnAbort("busy block is included in the free block chain.");
	}

	body = block.getBody();
	body.rewind();
	info.setFreeOffset(body.readLong());

	writeSuperBlock();
    }

    return offset;
}

void
HnSRTreeFileObj::releaseBlock(long offset)
{
    HnSRTreeBlock block;
    HnBlockStream body;

    block = new_HnSRTreeBlock(offset, info.getBlockSize(),
			      HnSRTreeBlock::FREE);

    body = block.getBody();
    body.rewind();
    body.writeLong(info.getFreeOffset());

    writeBlock(block);

    info.setFreeOffset(offset);
    writeSuperBlock();
}

/*
 * Leaf
 */

void
HnSRTreeFileObj::writeLeaf(const HnSRTreeLeaf &leaf)
{
    HnSRTreeBlock block;

    if ( debug ) {
	fprintf(stderr, "HnSRTreeFileObj::writeLeaf: %s\n",
		(char *)leaf.toString());
    }

    block = leaf.toBlock();
    writeBlock(block);
}

HnSRTreeLeaf
HnSRTreeFileObj::allocateLeaf(void)
{
    long offset;

    offset = allocateBlock();
    return new_HnSRTreeLeaf(info, offset);
}

/*
 * Node
 */

void
HnSRTreeFileObj::writeNode(const HnSRTreeNode &node)
{
    HnSRTreeBlock block;

    block = node.toBlock();
    writeBlock(block);
}

HnSRTreeNode
HnSRTreeFileObj::allocateNode(void)
{
    long offset;

    offset = allocateBlock();
    return new_HnSRTreeNode(info, offset);
}

/*
 * Check
 */

void
HnSRTreeFileObj::check(void)
{
    checkBlock(info.getRootOffset(), HnSRTreeNode::null, -1);
    checkInclusion(info.getRootOffset());
}

int
HnSRTreeFileObj::checkBlock(long offset,
			    const HnSRTreeNode &parent, int childIndex)
{
    HnSRTreeBlock block;
    HnSRTreeNode node;
    HnSRTreeLeaf leaf;
    int i, code, level = -1;

    block = readBlock(offset);

    if ( block.isNode() ) {
	node = new_HnSRTreeNode(info, block);

	if ( parent != HnSRTreeNode::null ) {
	    HnSRTreeCluster cluster = parent.getClusterAt(childIndex);

	    if ( !node.getCluster().equals(cluster) ) {
		HnAbort("mismatch in clusters %s and %s.",
			(char *)node.getCluster().toString(),
			(char *)cluster.toString());
	    }
	}

	for ( i=0; i<node.getCount(); i++ ) {
	    code = checkBlock(node.getOffsetAt(i), node, i);

	    /* test the balance of the tree */
	    if ( i == 0 ) {
		level = code;
	    }
	    else {
		if ( code != level ) {
		    HnAbort("the tree is not balanced at a node %08X.",
			    (int)offset);
		}
	    }
	}
    }
    else if ( block.isLeaf() ) {
	leaf = new_HnSRTreeLeaf(info, block);

	if ( parent != HnSRTreeNode::null ) {
	    HnSRTreeCluster cluster = parent.getClusterAt(childIndex);

	    if ( !leaf.getCluster().equals(cluster) ) {
		HnAbort("mismatch in clusters %s and %s.",
			(char *)leaf.getCluster().toString(),
			(char *)cluster.toString());
	    }
	}
    }
    else {
	HnAbort("unexpected block type.");
    }
		

    /*
     * The `level' variable is used to confirm that the tree is balanced.
     */

    return level + 1;
}

HnPointVector
HnSRTreeFileObj::checkInclusion(long offset)
{
    HnSRTreeBlock block;
    HnPointVector sum = new_HnPointVector();

    block = readBlock(offset);

    if ( block.isNode() ) {
	HnSRTreeNode node = new_HnSRTreeNode(info, block);
	int i, j;

	for ( i=0; i<node.getCount(); i++ ) {
	    HnPointVector points = checkInclusion(node.getOffsetAt(i));
	    HnSphere sphere = node.getClusterAt(i).getSphere();

	    for ( j=0; j<points.size(); j++ ) {
		if ( !sphere.includes(points[j]) ) {
		    describeExclusion(node.getOffsetAt(i), sphere.getCenter());
		    HnAbort("point (%s) is not included "
			    "in the sphere (%s) of the node %08X "
			    "when the distance from the center of "
			    "the sphere is %g.",
			    (char *)points[j].toString(),
			    (char *)sphere.toString(), (int)offset,
			    sphere.getCenter().getDistance(points[j]));
		}
	    }

	    sum.addElements(points);
	}
    }
    else if ( block.isLeaf() ) {
	HnSRTreeLeaf leaf = new_HnSRTreeLeaf(info, block);
	int i;

	for ( i=0; i<leaf.getCount(); i++ )
	    sum.addElement(leaf.getPointAt(i));
    }