btree.c File Reference

#include <linux/kernel.h>
#include <linux/string.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/buffer_head.h>
#include "befs.h"
#include "btree.h"
#include "datastream.h"

Go to the source code of this file.

Data Structures
struct	befs_btree_node

Functions
int	befs_btree_find (struct super_block *sb, befs_data_stream *ds, const char *key, befs_off_t *value)
int	befs_btree_read (struct super_block *sb, befs_data_stream *ds, loff_t key_no, size_t bufsize, char *keybuf, size_t *keysize, befs_off_t *value)

Function Documentation

int befs_btree_find	(	struct super_block *	sb,
		befs_data_stream *	ds,
		const char *	key,
		befs_off_t *	value
	)

befs_btree_find - Find a key in a befs B+tree : Filesystem superblock : Datastream containing btree : Key string to lookup in btree : Value stored with

On success, returns BEFS_OK and sets * to the value stored with (usually the disk block number of an inode).

On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND.

Algorithm: Read the superblock and rootnode of the b+tree. Drill down through the interior nodes using befs_find_key(). Once at the correct leaf node, use befs_find_key() again to get the actuall value stored with the key.

Definition at line 247 of file btree.c.

int befs_btree_read	(	struct super_block *	sb,
		befs_data_stream *	ds,
		loff_t	key_no,
		size_t	bufsize,
		char *	keybuf,
		size_t *	keysize,
		befs_off_t *	value
	)

befs_btree_read - Traverse leafnodes of a btree : Filesystem superblock : Datastream containing btree : Key number (alphabetical order) of key to read : Size of the buffer to return key in : Pointer to a buffer to put the key in : Length of the returned key : Value stored with the returned key

Heres how it works: Key_no is the index of the key/value pair to return in keybuf/value. Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is the number of charecters in the key (just a convenience).

Algorithm: Get the first leafnode of the tree. See if the requested key is in that node. If not, follow the node->right link to the next leafnode. Repeat until the (key_no)th key is found or the tree is out of keys.

Definition at line 416 of file btree.c.