xsfstree.c

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

	}
	else write_unit(xsfs, unit);
	return 1;
}

// unit should be preloaded to xsfs->buffer
int xsfsDelNodePos(HXSFS xsfs, XSFSNODE *parent, _u32 unit, int index)
{
	char *bufs, *buf[2];
	XSFSBNODE *pbnode;
	XSFSBHEAD *pHead, *pHeadL, *pHeadR;
	_u32 child, left, right;
	int ni;

	// new buffer used for inserting node
	bufs = (char*)xsfs_alloc((i_xsfs_unit_size(xsfs)+sizeof(XSFSBNODE))*2);
	if(!bufs) return 0;
	buf[0] = bufs; 
	buf[1] = bufs+i_xsfs_unit_size(xsfs)+sizeof(XSFSBNODE);
	pHeadL = (XSFSBHEAD*)buf[0];
	pHeadR = (XSFSBHEAD*)buf[1];
	pHead = (XSFSBHEAD*)xsfs->buffer;
	child = unit;

	while(child)
	{
		pbnode = get_bnode(xsfs, index);
		left = pbnode->b_left; right = pbnode->b_right;
		// one child is null, delete right on self
		if(!left && !right || (!left || !right) && pHead->n_total>1)
		{ delete_on_self(xsfs, unit, index, parent, bufs); break; }

		if(left) read_unit_buf(xsfs, buf[0], left);
		if(right) read_unit_buf(xsfs, buf[1], right);
	
		if(!right || left && pHeadL->n_total>pHeadR->n_total)	// choose left
		{ pHead = pHeadL; child = left; }
		else{ pHead = pHeadR; child = right; }

		// update self
		ni = child==left ? pHead->n_total-1 : 0;
		memcpy(get_node(xsfs, index), get_node_buf(pHead, ni), sizeof(XSFSNODE));
		write_unit(xsfs, unit);
		// switch to child
		unit = child; index = ni;
		memcpy(xsfs->buffer, pHead, i_xsfs_unit_size(xsfs));
	}

	xsfs_free(bufs);
	return 1;
}

int xsfsDelNode(HXSFS xsfs, XSFSNODE *parent, const char *name)
{
	_u32 unit;
	int index;

	unit = locate_node(xsfs, parent->child_unit, name, &index, NULL);
	if(!unit || index%2==0) return -1;
	if(!read_unit(xsfs, unit)) return 1;
	return xsfsDelNodePos(xsfs, parent, unit, index/2) ? 0 : 1;
}

static int update_root(HXSSTREAM fststream, XSFSROOT *root)
{
	return xsfsWriteStream(fststream, 0, root, sizeof(XSFSROOT));
}

static _u32 new_block(HXSSTREAM fststream, XSFSROOT *root, _u32 flags)
{
	char buf[MAX_BLOCKSIZE];
	FSTBLOCK blk;

	memset(buf, 0, MAX_BLOCKSIZE);
	((FSTBLOCK*)buf)->flags = flags;
	if(root->free_start==0)	// 0 free blocks now
	{
		if(!xsfsWriteStream(fststream, (_u64)root->start_pos+(_u64)root->n_blocks*root->block_size, buf, root->block_size))
			return 0;
		root->n_blocks++;
		update_root(fststream, root);
		return root->n_blocks;
	}
	else
	{
		_u32 old = root->free_start-1;
		if(!xsfsReadStream(fststream, (_u64)root->start_pos+(_u64)old*root->block_size, &blk, sizeof(blk)))
			return 0;
		if(!xsfsWriteStream(fststream, (_u64)root->start_pos+(_u64)old*root->block_size, buf, root->block_size))
			return 0;
		root->free_start = blk.next;
		update_root(fststream, root);
		return old;
	}
}

static void del_block(HXSSTREAM fststream, XSFSROOT *root, _u32 block)
{
	FSTBLOCK blk;

	if(block>=root->n_blocks) return;
	if(!xsfsReadStream(fststream, (_u64)root->start_pos+(_u64)block*root->block_size, &blk, sizeof(blk)))
		return;
	if(!(blk.flags&BF_DELETED))
	{
		blk.flags|=BF_DELETED;
		blk.next = root->free_start;
		if(!xsfsWriteStream(fststream, (_u64)root->start_pos+(_u64)block*root->block_size, &blk, sizeof(blk)))
			return;
		root->free_start = block+1;
		update_root(fststream, root);
	}
}

static int read_block(HXSSTREAM fststream, XSFSROOT *root, _u32 bi, _u32 bo, void *buffer, int len)
{
	char buf[MAX_BLOCKSIZE], *p;
	int l, cnt = 0;

	if(bi>=root->n_blocks || bo>=root->block_size-sizeof(FSTBLOCK)) return 0;
	p = (char*)buffer;
	while(len && bi)
	{
		if(!xsfsReadStream(fststream, root->start_pos+(_u64)bi*root->block_size, buf, root->block_size))
			break;
		l = root->block_size-sizeof(FSTBLOCK)-bo;
		if(l>len) l = len;
		memcpy(p, buf+sizeof(FSTBLOCK)+bo, l);
		p+=l; len-=l; bo = 0; cnt+=l;
		bi = ((FSTBLOCK*)buf)->next;
	}
	return cnt;
}

static int write_block(HXSSTREAM fststream, XSFSROOT *root, _u32 bi, _u32 bo, void *buffer, int len)
{
	char buf[MAX_BLOCKSIZE], *p;
	int l, cnt = 0;
	FSTBLOCK blk;

	if(bi>=root->n_blocks || bo>=root->block_size-sizeof(FSTBLOCK)) return 0;
	p = (char*)buffer;
	while(len && bi)
	{
		if(!xsfsReadStream(fststream, root->start_pos+(_u64)bi*root->block_size, buf, root->block_size))
			break;
		memcpy(&blk, buf, sizeof(blk));

		l = root->block_size-sizeof(FSTBLOCK)-bo;
		if(l>len) l = len;
		if((_u32)l<root->block_size)
			memcpy(buf+sizeof(FSTBLOCK)+bo, p, l);
		p+=l; len-=l; bo = 0;

		// if new blocks are needed
		if(len && blk.next==0)
		{
			blk.next = new_block(fststream, root, BF_FINAL);
			if(blk.next)
			{
				blk.next--;
				blk.flags&=~BF_FINAL;
				memcpy(buf, &blk, sizeof(blk));
			}
		}
		if(!xsfsWriteStream(fststream, root->start_pos+(_u64)bi*root->block_size, buf, root->block_size))
			break;
		cnt+=l;
		bi = ((FSTBLOCK*)buf)->next;
	}
	return cnt;
}

static FSTBLOCK *load_block(HXSSTREAM fststream, XSFSROOT *root, _u32 block, void *buf)
{
	FSTBLOCK *pBlk;

	if(block>=root->n_blocks) return NULL;
	if(!xsfsReadStream(fststream, (_u64)root->start_pos+(_u64)block*root->block_size, buf, root->block_size)) 
		return NULL;

	pBlk = (FSTBLOCK*)buf;
	if(!(pBlk->flags&BF_FIRST)) return NULL;	// it is not the first block in the chain

	return pBlk;
}

static void free_blocks(HXSSTREAM fststream, XSFSROOT *root, _u32 block)
{
	char buf[MAX_BLOCKSIZE];
	FSTBLOCK blk;

	while(block)
	{
		if(!xsfsReadStream(fststream, (_u64)root->start_pos+(_u64)block*root->block_size, buf, root->block_size)) 
			break;
		memcpy(&blk, buf, sizeof(blk));
		del_block(fststream, root, block);
		block = !(blk.flags&BF_FINAL) ? blk.next : 0;
	}
}

_u32 xsfsAllocDataEntry(HXSSTREAM fststream, XSFSROOT *root)
{
	_u32 block = new_block(fststream, root, BF_FINAL|BF_FIRST);
	return block ? block-1 : 0;
}

void xsfsFreeDataEntry(HXSSTREAM fststream, XSFSROOT *root, _u32 block)
{
	char buf[MAX_BLOCKSIZE];
	FSTBLOCK *pBlk;
	FSTBLOCKDEF *pDef;
	_u32 u, i;

	pBlk = load_block(fststream, root, block, buf);
	if(!pBlk) return;
	pDef = (FSTBLOCKDEF*)((char*)pBlk+sizeof(FSTBLOCK));
	if(pDef->bo_name) free_blocks(fststream, root, pDef->bo_name);
	for(i=0; i<root->n_streams; i++)
	{
		u = *(_u32*)((char*)pDef+sizeof(FSTBLOCKDEF)+i*2*sizeof(_u32));
		if(u) free_blocks(fststream, root, u);
	}
	free_blocks(fststream, root, block);
}

int xsfsLoadDataStream(HXSSTREAM fststream, XSFSROOT *root, _u32 block, _u32 n_stream, XSSTREAM *stream)
{
	char buf[MAX_BLOCKSIZE];
	FSTBLOCK *pBlk;
	FSTBLOCKDEF *pDef;
	_u32 *p;

	pBlk = load_block(fststream, root, block, buf);
	if(!pBlk) return 0;

	// locate stream enty
	pDef = (FSTBLOCKDEF*)(buf+sizeof(FSTBLOCK));	
	if(n_stream>=root->n_streams) return 0;
	p = (_u32*)((char*)pDef+sizeof(FSTBLOCKDEF)+n_stream*2*(sizeof(_u32)));

	// find stream sector and offset
	stream->sector = xsfsLocate(fststream, (_u64)root->start_pos+(_u64)p[0]*root->block_size+sizeof(FSTBLOCK)+p[1], 
									&stream->offset);
	if(!stream->sector) return 0;
	stream->sector = i_xsfs_start_sector(fststream->xsfs)+stream->sector*fststream->xsfs->desc.n_scale;
	
	// read and update
	if(read_block(fststream, root, p[0], p[1], 
			&stream->stream, sizeof(stream->stream))!=sizeof(stream->stream)) return 0;
	stream->xsfs = fststream->xsfs;
	return 1;
}

int xsfsSaveDataStream(HXSSTREAM fststream, XSFSROOT *root, _u32 block, _u32 n_stream, XSSTREAM *stream)
{
	char buf[MAX_BLOCKSIZE];
	FSTBLOCK *pBlk;
	FSTBLOCKDEF *pDef;
	_u32 *p;
	int new_allocate;

	pBlk = load_block(fststream, root, block, buf);
	if(!pBlk) return 0;

	// locate stream enty
	pDef = (FSTBLOCKDEF*)(buf+sizeof(FSTBLOCK));	
	if(n_stream>=root->n_streams) return 0;
	p = (_u32*)((char*)pDef+sizeof(FSTBLOCKDEF)+n_stream*2*(sizeof(_u32)));

	if(p[0]==0)
	{
		p[0] = new_block(fststream, root, BF_FINAL|BF_FIRST);
		if(!p[0]) return 0;
		p[0]--; p[1] = 0; new_allocate = 1;
	}
	else new_allocate = 0;

	// find stream sector and offset
	stream->sector = xsfsLocate(fststream, (_u64)root->start_pos+(_u64)p[0]*root->block_size+sizeof(FSTBLOCK)+p[1], 
									&stream->offset);
	if(!stream->sector)
	{
		if(new_allocate) del_block(fststream, root, p[0]);
		return 0;
	}
	stream->sector = i_xsfs_start_sector(fststream->xsfs)+stream->sector*fststream->xsfs->desc.n_scale;

	// save stream
	if(write_block(fststream, root, p[0], p[1], 
			&stream->stream, sizeof(stream->stream))!=sizeof(stream->stream))
	{
		if(new_allocate) del_block(fststream, root, p[0]);
		return 0;
	}

	// write block back
	if(new_allocate)
		xsfsWriteStream(fststream, (_u64)root->start_pos+(_u64)block*root->block_size, buf, root->block_size); 

	stream->xsfs = fststream->xsfs;
	return 1;
}

int xsfsLoadRoot(HXSFS xsfs, XSSTREAM *stream, XSFSROOT *root)
{
	XSFSSTREAM *pStream;
	
	if(fsioRead(xsfs->handle, xsfs->desc.n_reserved, xsfs->buffer, 1)!=1) return 0;
	pStream = (XSFSSTREAM*)xsfs->buffer;
	if(stream)
	{
		memcpy(&stream->stream, &pStream[SSI_FSTREE], sizeof(XSFSSTREAM));		
		stream->xsfs = xsfs;
		stream->sector = xsfs->desc.n_reserved;
		stream->offset = SSI_FSTREE*sizeof(XSFSSTREAM);
	}
	if(fsioRead(xsfs->handle, 
				i_xsfs_start_sector(xsfs)+pStream[SSI_FSTREE].pri_index[0]*xsfs->desc.n_scale, 
				xsfs->buffer, 1)!=1)
		return 0;
	memcpy(root, xsfs->buffer, sizeof(XSFSROOT));
	return 1;
}

int xsfsSaveRoot(HXSFS xsfs, XSFSROOT *root)
{
	XSFSSTREAM *pStream;
	_u32 unit;
	
	if(fsioRead(xsfs->handle, xsfs->desc.n_reserved, xsfs->buffer, 1)!=1) return 0;
	pStream = (XSFSSTREAM*)xsfs->buffer;
	unit = pStream[SSI_FSTREE].pri_index[0];
	if(fsioRead(xsfs->handle, i_xsfs_start_sector(xsfs)+unit*xsfs->desc.n_scale, xsfs->buffer, 1)!=1)
		return 0;
	memcpy(xsfs->buffer, root, sizeof(XSFSROOT));
	return fsioWrite(xsfs->handle, i_xsfs_start_sector(xsfs)+unit*xsfs->desc.n_scale, xsfs->buffer, 1);
}