xsfstree.c

一个操作系统,用C语言实现开发的,我在一个浙江大学的操作系统实验网站找到.大家学习以下

// XSFS B-Tree System

#include <knllib.h>
#include <knlcon.h>
#include <memory.h>
#include <string.h>
#include "xsfsunits.h"
#include "xsfstree.h"
#include "xsfsstream.h"

#ifdef __KERNEL__
#include <knlmm.h>
static inline void* xsfs_alloc(size_t size)
{ return kmalloc(size, 0); }
static inline void xsfs_free(void *buf)
{ kfree(buf); }
#else
#include <stdlib.h>
static inline void* xsfs_alloc(size_t size)
{ return malloc(size); }
static inline void xsfs_free(void *buf)
{ free(buf); }
#endif

static inline int read_unit_buf(HXSFS xsfs, void *buf, _u32 unit)
{
	return fsioRead(xsfs->handle, i_xsfs_start_sector(xsfs)+unit*xsfs->desc.n_scale,
					buf, xsfs->desc.n_scale);
}

static inline int read_unit(HXSFS xsfs, _u32 unit)
{
	return read_unit_buf(xsfs, xsfs->buffer, unit);
}

static inline int write_unit_buf(HXSFS xsfs, void *buf, _u32 unit)
{
	return fsioWrite(xsfs->handle, i_xsfs_start_sector(xsfs)+unit*xsfs->desc.n_scale,
					buf, xsfs->desc.n_scale);
}

static inline int write_unit(HXSFS xsfs, _u32 unit)
{
	return write_unit_buf(xsfs, xsfs->buffer, unit);
}

// Node helpers
#define NODE_LEFT_BUF(buf, n)	(XSFSBNODE*)((char*)(buf)+sizeof(XSFSBHEAD)+(n)*(sizeof(_u32)+sizeof(XSFSNODE)))
#define NODE_AT_BUF(buf, n)		(XSFSNODE*)((char*)NODE_LEFT_BUF(buf, n)+sizeof(_u32))
#define NODE_RIGHT_BUF(buf, n)	(_u32*)((char*)NODE_AT_BUF(buf, n)+sizeof(XSFSNODE))

#define NODE_LEFT(xsfs, n)		(NODE_LEFT_BUF(((HXSFS)(xsfs))->buffer, n))
#define NODE_AT(xsfs, n)		(NODE_AT_BUF(((HXSFS)(xsfs))->buffer, n))
#define NODE_RIGHT(xsfs, n)		(NODE_RIGHT_BUF(((HXSFS)(xsfs))->buffer, n))

static inline XSFSBNODE* get_bnode_buf(void *buf, int n)
{
	if(n<0 || ((XSFSBHEAD*)buf)->n_total<=(_u32)n) return NULL;
	return NODE_LEFT_BUF(buf, n);
}

static inline XSFSNODE* get_node_buf(void *buf, int n)
{
	if(n<0 || ((XSFSBHEAD*)buf)->n_total<=(_u32)n) return NULL;
	return NODE_AT_BUF(buf, n);
}

static inline _u32* get_noderight_buf(void *buf, int n)
{
	if(n<0 || ((XSFSBHEAD*)buf)->n_total<=(_u32)n) return NULL;
	return NODE_RIGHT_BUF(buf, n);
}

static inline XSFSBNODE* get_bnode(HXSFS xsfs, int n)
{
	return get_bnode_buf(xsfs->buffer, n);
}

static inline XSFSNODE* get_node(HXSFS xsfs, int n)
{
	return get_node_buf(xsfs->buffer, n);
}

static inline _u32* get_noderight(HXSFS xsfs, int n)
{
	return get_noderight_buf(xsfs->buffer, n);
}

// B-tree operations
static inline int compare_node(const char *name, XSFSNODE *node)
{
	KASSERT(name, "compare_node: invalid name");
	KASSERT(node, "compare_node: invalid node");
	
	return strcmp(name, node->name);
}

static _u32 locate_node(HXSFS xsfs, _u32 root_unit, const char *name, int *index, int *pn_fullnodes)
{
	_u32 cur_unit, next_unit;
	int mi, ma, mm, cc, c_fullnodes, split_root;
	XSFSBHEAD *pHead;

	next_unit = root_unit;
	c_fullnodes = 0; split_root = 1;
	while(next_unit)
	{
		cur_unit = next_unit;

		// read a unit and obtain head
		if(!read_unit(xsfs, cur_unit)) return 0;
		pHead = (XSFSBHEAD*)xsfs->buffer;
		
		// modify c_fullnodes
		if(pHead->n_total==pHead->n_max) c_fullnodes++;
		else{ c_fullnodes = 0; split_root = 0; }

		// binary search
		mi = 0; ma = pHead->n_total-1;
		mm = -1;
		while(mi<ma-1)
		{
			mm = (mi+ma)/2;
			cc = compare_node(name, get_node(xsfs, mm));
			if(cc<0) ma = mm;
			if(cc>0) mi = mm;
			if(cc==0) mi=ma=mm; 
		}
		if(mi<ma-1) return 0;	// there must be some error
		if(mm>=0 && cc==0)
		{
			if(index) *index = mm*2+1;
			break;
		}
		cc = compare_node(name, get_node(xsfs, mi));
		if(cc==0)	// node found
		{ if(index) *index = mi*2+1; break; }
		if(cc<0)	// less then min
		{ if(index) *index = mi*2; next_unit = get_bnode(xsfs, mi)->b_left; }
		else	// bigger then mm
		{
			cc = compare_node(name, (XSFSNODE*)get_node(xsfs, ma));
			if(cc==0){ if(index) *index = ma*2+1; break; }	// equal
			mm = cc>0 ? ma : mi;
			if(index) *index = (mm+1)*2; 
			next_unit = *get_noderight(xsfs, mm);
		}
	}

	if(split_root) c_fullnodes ++;
	if(pn_fullnodes) *pn_fullnodes = c_fullnodes;
	return cur_unit;
}

_u32 xsfsFindNode(HXSFS xsfs, _u32 root_unit, const char *name, XSFSNODE *result, int *index)
{
	int i;
	_u32 unit = locate_node(xsfs, root_unit, name, &i, NULL);
	//KTRACE2("locate_node %u, %d\n", unit, i);
	// unit is 0 mean error occured
	// and index should be odd or node is not found
	if(unit==0 || i%2==0) return 0;
	if(result) memcpy(result, get_node(xsfs, i/2), sizeof(XSFSNODE));
	//KTRACE("xsfsFindNode: after memcpy\n");
	if(index) *index = i/2;
	//KTRACE("xsfsFindNode: to leave\n");
	return unit;
}

_u32 xsfsLocateNode(HXSFS xsfs, XSFSNODE *parent, const char *name, XSFSNODE *result, int *index)
{
	int i;
	_u32 unit = locate_node(xsfs, parent->child_unit, name, &i, NULL);
	if(unit==0 || i%2==0) return 0;
	if(index) *index = i/2;
	if(result) memcpy(result, get_node(xsfs, i/2), sizeof(XSFSNODE));
	return unit;
}

int xsfsAddNode(HXSFS xsfs, XSFSNODE *parent, XSFSNODE *newnode, _u32 up_unit, int up_index)
{
	int l1, l2, index, new_units, cnt_units;
	_u32 unit, parent_unit, units[256];
	char *buf;
	XSFSBHEAD *pHead;
	XSFSBNODE *pbnode, bnode;

	// create new root if not existed
	if(!parent->child_unit)
	{
		if(xsfsAllocUnits(xsfs, 0, 1, &unit, 0)!=1) return 0;
		pHead = (XSFSBHEAD*)xsfs->buffer;
		pbnode = (XSFSBNODE*)((char*)xsfs->buffer+sizeof(XSFSBHEAD));
		memset(pHead, 0, sizeof(XSFSBHEAD)+sizeof(XSFSBNODE));
		pHead->n_max = i_xsfs_node_num(xsfs);
		pHead->n_total = 1;
		pHead->uplevel_unit = up_unit;
		pHead->uplevel_index = up_index;
		memcpy(&pbnode->node, newnode, sizeof(XSFSNODE));
		write_unit(xsfs, unit);
		parent->child_unit = unit;
		return 1;
	}

	unit = locate_node(xsfs, parent->child_unit, newnode->name, &index, &new_units);
	// index should be even or the node already existed
	if(unit==0 || index%2==1) return 0;
	// now, new_units can't exceeds 256
	if(new_units>256) return 0;

	// new buffer used for inserting node
	buf = (char*)xsfs_alloc(i_xsfs_unit_size(xsfs)+sizeof(XSFSBNODE));
	if(!buf) return 0;

	// allocate units for future use
	if(new_units>0)
	{
		if(xsfsAllocUnits(xsfs, 0, new_units, units, 0)!=new_units)
		{ if(buf) xsfs_free(buf); return 0; }
		// node should be reloaded
		read_unit(xsfs, unit);
	}
	cnt_units = 0;

	// build new node and ready to insert
	index/=2; pbnode = &bnode;
	memset(pbnode, 0, sizeof(bnode));
	memcpy(&bnode.node, newnode, sizeof(XSFSNODE));

	while(pbnode)
	{
		l1 = sizeof(XSFSBHEAD)+index*(sizeof(_u32)+sizeof(XSFSNODE));
		l2 = (((XSFSBHEAD*)xsfs->buffer)->n_total-index)*(sizeof(XSFSNODE)+sizeof(_u32));

		// front part
		memcpy(buf, xsfs->buffer, l1);
		// insert node
		memcpy(buf+l1, pbnode, sizeof(XSFSBNODE));
		// latter part
		memcpy(buf+l1+sizeof(XSFSBNODE), (char*)xsfs->buffer+l1+sizeof(_u32), l2);

		pHead = (XSFSBHEAD*)buf;
		pHead->n_total++;
		// if pHead->n_total exceeds pHead->n_max split the node
		if(pHead->n_total>pHead->n_max)
		{
			index = pHead->parent_index;
			parent_unit = pHead->parent_unit;

			// caculate the size of front and latter parts splitted
			l1 = sizeof(XSFSBHEAD)+(pHead->n_max+1)/2*(sizeof(_u32)+sizeof(XSFSNODE));
			l2 = pHead->n_max/2*(sizeof(XSFSNODE)+sizeof(_u32));

			// save the middle node
			memcpy(pbnode, buf+l1, sizeof(XSFSBHEAD));
			pbnode->b_left = unit;

			// write the front part back
			memcpy(xsfs->buffer, buf, l1+sizeof(_u32));
			((XSFSBHEAD*)xsfs->buffer)->n_total = (pHead->n_max+1)/2;
			if(!parent_unit)	// root
			{
				pHead->parent_index = 0;
				pHead->parent_unit = units[new_units-1];
				((XSFSBHEAD*)xsfs->buffer)->parent_index = 0;
				((XSFSBHEAD*)xsfs->buffer)->parent_unit = units[new_units-1];
			}
			((XSFSBHEAD*)xsfs->buffer)->n_total = (pHead->n_max+1)/2;
			write_unit(xsfs, unit);

			unit = units[cnt_units++];	// the latter part, assigned a unit to
			pbnode->b_right = unit;
			// ok, now, the middle node is completed

			// copy the latter part
			memcpy((char*)xsfs->buffer+sizeof(XSFSBHEAD), buf+l1+sizeof(XSFSBNODE)-sizeof(_u32), l2+sizeof(_u32));
			memcpy(xsfs->buffer, buf, sizeof(XSFSBHEAD));
			((XSFSBHEAD*)xsfs->buffer)->n_total = pHead->n_max/2;
			((XSFSBHEAD*)xsfs->buffer)->parent_index ++; // parent_index is increamented by 1, that's correct
			write_unit(xsfs, unit);	// write back

			if(parent_unit)
			{
				// read parent
				read_unit(xsfs, pHead->parent_unit);
				// now, index is already in parent, and new pbnode will be inserted
			}
			else // split root
			{
				pHead = (XSFSBHEAD*)xsfs->buffer;
				pHead->n_total = 1;
				pHead->parent_index = 0;
				pHead->parent_unit = 0;
				memcpy((char*)xsfs->buffer+sizeof(XSFSBHEAD), pbnode, sizeof(XSFSBNODE));
				parent->child_unit = units[new_units-1];
				write_unit(xsfs, units[new_units-1]);
				pbnode = NULL;
			}
		}
		else
		{
			pbnode = NULL;
			memcpy(xsfs->buffer, buf, l1+l2+sizeof(XSFSBNODE));
			write_unit(xsfs, unit);
		}
	}
	xsfs_free(buf);
	return 1;
}

static int delete_on_self(HXSFS xsfs, _u32 unit, int index, XSFSNODE *parent, void *buf)
{
	XSFSBHEAD *pHead;
	XSFSBNODE *pNode;
	_u32 left, right, parent_unit;
	int parent_index;

	pHead = (XSFSBHEAD*)xsfs->buffer;
	pNode = get_bnode(xsfs, index);
	left = pNode->b_left; right = pNode->b_right;
	memcpy(buf, xsfs->buffer, i_xsfs_unit_size(xsfs));
	memcpy(get_bnode(xsfs, index), NODE_LEFT_BUF(buf, index+1), 
			i_xsfs_unit_size(xsfs)-sizeof(XSFSBHEAD)-(index+1)*(sizeof(_u32)+sizeof(XSFSNODE)));
	pNode->b_left = left ? left : right;
	pHead->n_total--;
	parent_unit = pHead->parent_unit;
	parent_index = pHead->parent_index;

	// here we violate B-tree rule (pHead->n_total>pHead->n_max/2)
	// only for simple implementation
	if(pHead->n_total==0)	// delete root
	{
		xsfsFreeUnits(xsfs, &unit, 1, 0);
		if(parent_unit)
		{
			read_unit(xsfs, parent_unit);
			pNode = NODE_LEFT(xsfs, parent_index);
			pNode->b_left = 0;
			write_unit(xsfs, parent_unit);
		}
		else parent->child_unit = 0;