hnsrtreefileobj.cc

R 树

/*
 * HnSRTreeFileObj.cc
 * Copyright (C) 1997 Norio Katayama
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA
 *
 * 03/20/96 [e-mail]
 * $Id: HnSRTreeFileObj.cc,v 1.5 1997/12/04 03:32:30 katayama Exp $
 */

#include <math.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include "HnSRTreeFile.hh"
#include "HnSRTreeFileObj.hh"
#include "HnAbort.hh"

/*
 * Constructor and Destructor
 */

HnSRTreeFileObj::HnSRTreeFileObj(const char *path,
				 int dimension, int dataSize, int blockSize,
				 int splitFactor, int reinsertFactor)
{
	HnSRTreeLeaf leaf;

	if(splitFactor < 0 || splitFactor > 50)
		HnAbort("split factor %d is out of range.", splitFactor);

	if(reinsertFactor < 0 || reinsertFactor > 50)
		HnAbort("reinsert factor %d is out of range.", reinsertFactor);

	initialize();

	if((fp = fopen(path, "w+")) == NULL) {
		setSysError("fopen(%s, \"w+\")", path);
		return;
	}

	this->dimension = dimension;
	this->dataSize = dataSize;
	this->blockSize = blockSize;
	this->fileSize = blockSize;

	this->splitFactor = splitFactor;
	this->reinsertFactor = reinsertFactor;

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

	leaf = allocateLeaf();
	rootOffset = leaf.getOffset();
	height ++;

	writeLeaf(leaf);
	writeSuperBlock();
}

HnSRTreeFileObj::HnSRTreeFileObj(const char *path,
				 int dimension, int dataSize, int blockSize,
				 int splitFactor, int reinsertFactor,
				 HnPointArray &points, HnDataArray &values,
				 HnBool debug)
{
	HnSRTreeLeaf leaf;
	int numLevels, numSplits, numRootSplits, numNodeSplits;

	if(splitFactor < 0 || splitFactor > 50)
		HnAbort("split factor %d is out of range.", splitFactor);

	if(reinsertFactor < 0 || reinsertFactor > 50)
		HnAbort("reinsert factor %d is out of range.", reinsertFactor);

	initialize();

	if((fp = fopen(path, "w+")) == NULL) {
		setSysError("fopen(%s, \"w+\")", path);
		return;
	}

	this->dimension = dimension;
	this->dataSize = dataSize;
	this->blockSize = blockSize;
	this->fileSize = blockSize;

	this->splitFactor = splitFactor;
	this->reinsertFactor = reinsertFactor;

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

	this->debug = debug;

	getSplitFactors(points, values, &numLevels, 
			&numSplits, &numRootSplits, &numNodeSplits);

	if(numLevels == 1) {
		HnSRTreeLeaf leaf = allocateLeaf();
		int i;

		for(i=0; i<points.length(); i++)
			leaf.append(points[i], values[i]);

		rootOffset = leaf.getOffset();
		height = numLevels;

		writeLeaf(leaf);
		writeSuperBlock();
	}
	else {
		HnSRTreeNode node = allocateNode();

		constructTree(points, values, 0, points.length(),
			      0, numLevels, 0, numSplits,
			      numRootSplits, numNodeSplits,
			      node);

		rootOffset = node.getOffset();
		height = numLevels;

		writeNode(node);
		writeSuperBlock();
	}
}

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

	if(strcmp(mode, "rw") == 0) {
		if((fp = fopen(path, "r+")) == NULL) {
			setSysError("fopen(\"%s\", \"r+\")", path);
			return;
		}
	}
	else if(strcmp(mode, "r") == 0) {
		if((fp = fopen(path, "r")) == NULL) {
			setSysError("fopen(\"%s\", \"r\")", path);
			return;
		}
	}
	else
		HnAbort("mode must be `r' or `rw'");

	readSuperBlock();
}

HnSRTreeFileObj::~HnSRTreeFileObj(void)
{
	if(fp != NULL)
		fclose(fp);
}

void
HnSRTreeFileObj::close(void)
{
	if(fp != NULL)
		fclose(fp);
	fp = NULL;
}

/*
 * Super Block
 */

void
HnSRTreeFileObj::writeSuperBlock(void)
{
	SuperBlock superBlock;

	superBlock.dimension = dimension;
	superBlock.dataSize = dataSize;
	superBlock.blockSize = blockSize;
	superBlock.fileSize = fileSize;

	superBlock.freeOffset = freeOffset;
	superBlock.rootOffset = rootOffset;
	superBlock.height = height;

	superBlock.splitFactor = splitFactor;
	superBlock.reinsertFactor = reinsertFactor;

	if(fseek(fp, 0, SEEK_SET) < 0)
		HnSysError("fseek");
	if(fwrite(&superBlock, sizeof(superBlock), 1, fp) != 1)
		HnSysError("fwrite");
}

void
HnSRTreeFileObj::readSuperBlock(void)
{
	SuperBlock superBlock;

	if(fseek(fp, 0, SEEK_SET) < 0)
		HnSysError("fseek");
	if(fread(&superBlock, sizeof(superBlock), 1, fp) != 1)
		HnSysError("fread");

	dimension = superBlock.dimension;
	dataSize = superBlock.dataSize;
	blockSize = superBlock.blockSize;
	fileSize = superBlock.fileSize;

	freeOffset = superBlock.freeOffset;
	rootOffset = superBlock.rootOffset;
	height = superBlock.height;

	splitFactor = superBlock.splitFactor;
	reinsertFactor = superBlock.reinsertFactor;
}

/*
 * Block
 */

void
HnSRTreeFileObj::writeBlock(const HnSRTreeBlock &block)
{
	if(fseek(fp, block.getOffset(), SEEK_SET) < 0)
		HnSysError("fseek");
	if(fwrite(block.getBytes(), block.getSize(), 1, fp) != 1)
		HnSysError("fwrite");
}

HnSRTreeBlock
HnSRTreeFileObj::readBlock(off_t offset)
{
	char *bytes = new char[blockSize];
	HnSRTreeBlock block;

	if(fseek(fp, offset, SEEK_SET) < 0)
		HnSysError("fseek");
	if(fread(bytes, blockSize, 1, fp) != 1)
		HnSysError("fread");

	block = new_HnSRTreeBlock(offset, bytes, blockSize);
	delete bytes;

	return block;
}

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

	if(freeOffset < 0) {
		offset = fileSize;
		fileSize += blockSize;

		writeSuperBlock();
	}
	else {
		HnSRTreeBlock block;
		const char *bp;
		HnSRTreeBlock::Type type;

		offset = freeOffset;

		block = readBlock(freeOffset);
		bp = block.getBytes();

		memcpy(&type, bp, sizeof(type));
		bp += sizeof(type);

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

                memcpy(&freeOffset, bp, sizeof(off_t));

                writeSuperBlock();
        }

        return offset;
}

void
HnSRTreeFileObj::releaseBlock(off_t offset)
{
	HnSRTreeBlock block;
	char *buffer = new char[blockSize];
	char *bp;
	HnSRTreeBlock::Type type;

        memset(buffer, 0, blockSize);

	bp = buffer;

	type = HnSRTreeBlock::FREE;
	memcpy(bp, &type, sizeof(type));
	bp += sizeof(type);

	memcpy(bp, &freeOffset, sizeof(off_t));

        block = new_HnSRTreeBlock(offset, buffer, blockSize);

	delete buffer;

        writeBlock(block);

        freeOffset = 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)
{
	off_t offset;

	offset = allocateBlock();
	return new_HnSRTreeLeaf(dimension, dataSize, blockSize, offset);
}

/*
 * Node
 */

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

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

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

	offset = allocateBlock();
	return new_HnSRTreeNode(dimension, blockSize, offset);
}

/*
 * Store
 */

void
HnSRTreeFileObj::store(const HnPoint &point, const HnData &data)
{
	if(point.getDimension() != getDimension())
		HnAbort("mismatch in the dimensions (point: %d, file: %d)",
			point.getDimension(), getDimension());

	if(data.length() > dataSize)
		HnAbort("The size of data (%d) exceeds the limit (%d).",
			data.length(), dataSize);

	reinsertList = new_HnSRTreeReinsertArray();
	reinsertedBlocks = new_HnSRTreeOffsetArray();

	reinsertList.append(new_HnSRTreeReinsert(point, data));

	while(reinsertList.length() != 0) {
		if(reinsertList[0].getType() == HnSRTreeReinsert::POINT) {
			HnPoint point = reinsertList[0].getPoint();
			HnData data = reinsertList[0].getData();

			reinsertList.remove(0);
			insertPoint(point, data);
		}
		else {
			off_t offset = reinsertList[0].getOffset();
			int level = reinsertList[0].getLevel();

			reinsertList.remove(0);
			insertBlock(offset, level);
		}
	}

	if(debug)
		check();
}

void
HnSRTreeFileObj::insertPoint(const HnPoint &point, const HnData &data)
{
	HnSRTreeStack stack;
	HnSRTreeLeaf leaf;

	stack = chooseLeaf(point);

	leaf = stack.getTopLeaf();

	if(!leaf.isFull()) {
		leaf.append(point, data);
		writeLeaf(leaf);
		updateCoreAndRect(stack);
	}
	else {
		int index = -1;

		if(stack.getDepth() != 1 &&
		   (index = reinsertedBlocks.indexOf(leaf.getOffset())) < 0) {
			reinsertedBlocks.append(leaf.getOffset());
			reinsertLeaf(stack, point, data);
		}
		else {
			if(index >= 0)
				reinsertedBlocks.remove(index);
			splitLeaf(stack, point, data);
		}
	}
}

void
HnSRTreeFileObj::insertBlock(off_t offset, int level)
{
	HnSRTreeBlock block = readBlock(offset);
	HnSRTreeCore core;
	HnRect rect;
	HnSRTreeStack stack;
	HnSRTreeNode node;

	if(block.isNode()) {
		HnSRTreeNode node = new_HnSRTreeNode(dimension, block);
		core = node.getCore();
		rect = node.getBoundingRect();
	}
	else if(block.isLeaf()) {
		HnSRTreeLeaf leaf =
			new_HnSRTreeLeaf(dimension, dataSize, block);
		core = leaf.getCore();
		rect = leaf.getBoundingRect();
	}
	else
		HnAbort("unexpected block type.");

	stack = chooseNode(core, level);

	node = stack.getTopNode();

	if(!node.isFull()) {
		node.append(core, rect, offset);
		writeNode(node);
		updateCoreAndRect(stack);
	}
	else {
		int index = -1;

		if(stack.getDepth() != 1 &&
		   (index = reinsertedBlocks.indexOf(node.getOffset())) < 0) {
			reinsertedBlocks.append(node.getOffset());
			reinsertNode(stack, core, rect, offset);
		}
		else {
			if(index >= 0)
				reinsertedBlocks.remove(index);
			splitNode(stack, core, rect, offset);
		}
	}
}

HnSRTreeStack
HnSRTreeFileObj::chooseLeaf(const HnPoint &point)
{
	HnSRTreeStack stack = new_HnSRTreeStack();
	HnSRTreeBlock block;
	HnSRTreeNode node;
	HnSRTreeLeaf leaf;
	int index;

	/*
	 * NOTE:
	 *	The stack is used for keeping the trace of the access path.
	 *	Cursors indicates which entry is used at each node.
	 */

	block = readBlock(rootOffset);

	while(block.isNode()) {
		node = new_HnSRTreeNode(dimension, block);
		index = chooseSubtree(node, point);

		stack.push(node, index);
		block = readBlock(node.getOffsetAt(index));
	}

	leaf = new_HnSRTreeLeaf(dimension, dataSize, block);
	stack.push(leaf, -1);

	return stack;
}

int
HnSRTreeFileObj::chooseSubtree(const HnSRTreeNode &node, const HnPoint &point)
{
	struct {
		int index;
		double distance;
	} min, cur;

	min.index = -1;
	min.distance = -1;

	for(cur.index=0; cur.index<node.getCount(); cur.index++) {
		HnSRTreeCore core = node.getCoreAt(cur.index);

		cur.distance = point.getDistance(core.getCenter());

		if(min.index == -1)
			min = cur;
		else {
			if(cur.distance < min.distance)
				min = cur;
		}
	}

	return min.index;
}

HnSRTreeStack
HnSRTreeFileObj::chooseNode(const HnSRTreeCore &core, int level)
{
	HnSRTreeStack stack = new_HnSRTreeStack();
	HnSRTreeBlock block;
	HnSRTreeNode node;
	int index;

	/*
	 * NOTE:
	 *	The stack is used for keeping the trace of the access path.
	 *	Cursors indicates which entry is used at each node.
	 */

	block = readBlock(rootOffset);

	while(stack.getDepth() != height - level) {
		node = new_HnSRTreeNode(dimension, block);
		index = chooseSubtree(node, core.getCenter());

		stack.push(node, index);
		block = readBlock(node.getOffsetAt(index));
	}

	return stack;
}

void
HnSRTreeFileObj::updateCoreAndRect(HnSRTreeStack stack)
{
	HnSRTreeCore core;
	HnRect rect;
	HnSRTreeLeaf leaf;
	HnSRTreeNode node;
	int cursor;

	if(stack.isTopNode()) {
		node = stack.getTopNode();
		core = node.getCore();
		rect = node.getBoundingRect();
		stack.pop();
	}
	else {
		leaf = stack.getTopLeaf();
		core = leaf.getCore();
		rect = leaf.getBoundingRect();
		stack.pop();
	}

	while(stack.getDepth() != 0) {