btree_bsfs.h File Reference

Public interface for the B-tree implementation in the BSFS filesystem. More...

Classes
struct	btree_node_t
	Represents a single node in the B-tree stored on disk. More...
struct	btree_handle_t
	Describes the configuration and root reference for a B-tree instance. More...

Typedefs
typedef uint32_t(*	key_fn) (const void *entry)
	Function pointer type for extracting a key from an entry.
typedef int(*	compare_fn) (const void *a, const void *b)
	Function pointer type for comparing two entries.

Enumerations
enum	btree_data_type_t { BTREE_TYPE_INODE , BTREE_TYPE_BSPAN , BTREE_TYPE_RECOVERY , BTREE_TYPE_DIR_ENTRY }
	Represents the type of data stored in the B-tree. More...

Functions
uint32_t	hash_filename (const char *name)
	Computes the djb2 hash of a given filename.
btree_handle_t *	btree_create_handle (btree_data_type_t type, size_t entry_size, compare_fn cmp, key_fn get_key)
	Creates a generic B-tree handle for managing structured data.
btree_handle_t *	btree_create_inode_handle (void)
	Creates a B-tree handle specifically for managing inode entries.
btree_handle_t *	btree_create_bspan_handle (void)
	Creates a B-tree handle for managing bspan entries.
btree_handle_t *	btree_create_dir_entry_handle ()
	Creates a B-tree handle for managing directory entries.
btree_handle_t *	btree_create_rec_entry_handle (void)
	Creates a B-tree handle for managing recovery entries.
int	btree_insert (FILE *disk, superblock_t *sb, btree_handle_t *handle, void *entry)
	Inserts a new entry into the B-tree.
int	btree_search (FILE *disk, btree_handle_t *handle, uint32_t node_block, uint32_t key, void *output)
	Searches for a key in the B-tree and retrieves the associated entry.
int	btree_search_entry (FILE *disk, btree_handle_t *handle, uint32_t node_block, const void *needle, void *output)
	Searches for an entry in the B-tree using the handle's compare function (full entry comparison), not just the numeric key.
int	btree_update (FILE *disk, btree_handle_t *handle, uint32_t node_block, void *new_entry)
	Updates an existing entry in the B-tree with new data.
int	btree_remove (FILE *disk, superblock_t *sb, btree_handle_t *handle, uint32_t key)
	Removes an entry from the B-tree based on its key.
int	btree_remove_entry (FILE *disk, superblock_t *sb, btree_handle_t *handle, const void *entry)
	Remove an entry using the handle's comparator (exact-match).
int	btree_write_node (FILE *disk, btree_handle_t *handle, uint32_t block, btree_node_t *node)
	Writes a B-tree node to disk.
btree_node_t *	btree_read_node (FILE *disk, btree_handle_t *handle, uint32_t block)
	Reads and deserializes a B-tree node from disk.
void	btree_free_node (btree_node_t *node)
	Frees the memory allocated for a B-tree node.
int	btree_deallocate_all (FILE *disk, superblock_t *sb, btree_handle_t *handle, uint32_t node_block)
	Recursively deallocates all nodes and data blocks in a B-tree.

Detailed Description

Public interface for the B-tree implementation in the BSFS filesystem.

This header defines the core structures and function prototypes for handling B-tree operations over disk blocks in the BSFS system. B-trees are used to organize entries such as inodes, block spans (bspan), directory entries and recovery entries.

The API supports creation, insertion, search, update, and removal of entries in the B-tree stored on disk, and allows configuration for different types of data.

Typedef Documentation

compare_fn

typedef int(* compare_fn) (const void *a, const void *b)

Function pointer type for comparing two entries.

A comparison function used to determine the ordering of two entries in the B-tree. It returns a negative value if a < b, zero if a == b, and a positive value if a > b.

key_fn

typedef uint32_t(* key_fn) (const void *entry)

Function pointer type for extracting a key from an entry.

A function of this type takes a pointer to an entry and returns a unique 32-bit key used to index and compare entries within the B-tree.

Enumeration Type Documentation

btree_data_type_t

enum btree_data_type_t

Represents the type of data stored in the B-tree.

This enumeration defines the supported logical types of data that can be stored in B-trees managed by the BSFS filesystem. Each type corresponds to a different kind of entry managed in the system.

Function Documentation

btree_create_bspan_handle()

btree_handle_t * btree_create_bspan_handle

(

void

)

Creates a B-tree handle for managing bspan entries.

This function initializes a btree_handle_t configured for use with bspan_t entries. It sets:

• The data type identifier to BTREE_TYPE_BSPAN
• The entry size to sizeof(bspan_t)
• The comparison function to compare_bspan
• The key extraction function to get_bspan_key

This handle can be used for managing logical-to-physical block mappings of files stored in the BSFS.

Returns

Pointer to a configured btree_handle_t for bspan entries.

btree_create_dir_entry_handle()

btree_handle_t * btree_create_dir_entry_handle

(

)

Creates a B-tree handle for managing directory entries.

This function initializes a new btree_handle_t configured to operate on directory entries (dir_entry_t) using their hashed filenames as keys.

Returns

A pointer to a newly allocated B-tree handle configured for directory entries.

btree_create_handle()

btree_handle_t * btree_create_handle	(	btree_data_type_t	type,
		size_t	entry_size,
		compare_fn	cmp,
		key_fn	get_key )

Creates a generic B-tree handle for managing structured data.

This function initializes a btree_handle_t structure, which serves as the context for performing B-tree operations (insertion, search, removal, etc.) on a specific data type. It sets up key parameters including:

• The type of data being stored (btree_data_type_t)
• The size of each entry (in bytes)
• A comparison function for ordering keys
• A key extraction function used by the B-tree logic

If a comparison function is not provided, the default one (default_compare) is used. The function also calculates the minimum degree of the B-tree nodes based on the entry size and BLOCK_SIZE.

Parameters

type	The type of data the B-tree will manage (e.g., INODE, BSPAN, RECOVERY).
entry_size	The size in bytes of each entry in the tree.
cmp	A comparison function for comparing two entries. Can be NULL.
get_key	A function to extract the key from an entry.

Returns

Pointer to a newly allocated and configured btree_handle_t.

btree_create_inode_handle()

btree_handle_t * btree_create_inode_handle

(

void

)

Creates a B-tree handle specifically for managing inode entries.

This function initializes and returns a pointer to a btree_handle_t configured to operate on entries of type inode_t. It sets the appropriate:

• Data type identifier (BTREE_TYPE_INODE)
• Entry size (based on sizeof(inode_t))
• Key extraction function (get_inode_key)
• Comparison function (compare_inode)

The resulting handle can be used for all B-tree operations involving inodes, such as insertion, search, update, and removal.

Returns

Pointer to a newly allocated and configured btree_handle_t for inodes.

btree_create_rec_entry_handle()

btree_handle_t * btree_create_rec_entry_handle

(

void

)

Creates a B-tree handle for managing recovery entries.

This function sets up a btree_handle_t for use with entries of type rec_entry_t. It specifies:

• The data type as BTREE_TYPE_RECOVERY
• The entry size as sizeof(rec_entry_t)
• The comparison function as compare_rec_entry
• The key extraction function as get_rec_entry_key

The resulting handle is used to manage entries in the recovery subsystem of the BSFS.

Returns

Pointer to a configured btree_handle_t for recovery entries.

btree_deallocate_all()

int btree_deallocate_all	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	handle,
		uint32_t	node_block )

Recursively deallocates all nodes and data blocks in a B-tree.

This function traverses the entire B-tree starting from the given node block. It recursively frees child nodes (if any), and also deallocates each data block referenced by bspan_t entries (only applies to BTREE_TYPE_BSPAN). Finally, it deallocates the node block itself from the bitmap.

Parameters

disk	Pointer to the filesystem image.
sb	Pointer to the superblock.
handle	Pointer to the B-tree handle.
node_block	Block number of the current node.

Returns

0 on success, -1 on failure (e.g., deallocation errors).

btree_free_node()

void btree_free_node

(

btree_node_t *

node

)

Frees the memory allocated for a B-tree node.

This function deallocates all dynamic memory used by a btree_node_t structure, including:

• The entries array.
• The children array.
• The node structure itself.

Should be called after reading or allocating a B-tree node to avoid memory leaks.

Parameters

node	Pointer to the B-tree node to be deallocated.

btree_insert()

int btree_insert	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	handle,
		void *	entry )

Inserts a new entry into the B-tree.

This function inserts a new entry into the B-tree associated with the given btree_handle_t. If the tree is empty, it initializes the root node. If the root node is full, it performs a split and creates a new root, maintaining the B-tree balance properties. Otherwise, it inserts directly into the appropriate non-full node.

Internally, the function may allocate new nodes on disk using the allocate_single_block function and uses helper functions btree_insert_nonfull and btree_split_child to perform recursive insertion and node splitting logic.

Parameters

disk	Pointer to the open disk file.
sb	Pointer to the superblock structure, used for block allocation.
handle	Pointer to the B-tree handle containing metadata and logic functions.
entry	Pointer to the entry to be inserted (must match the tree's entry type).

btree_read_node()

btree_node_t * btree_read_node	(	FILE *	disk,
		btree_handle_t *	handle,
		uint32_t	block )

Reads and deserializes a B-tree node from disk.

This function reads a B-tree node from the specified disk block and reconstructs it into a btree_node_t structure in memory. The format must match the layout written by btree_write_node, including:

• A flag indicating whether the node is a leaf.
• The number of entries.
• The array of entries.
• The array of child pointers.

Memory for the node and its arrays is dynamically allocated. The caller is responsible for freeing the resulting node using btree_free_node.

Parameters

disk	Pointer to the opened disk file.
handle	Pointer to the B-tree handle (used to determine entry size and degree).
block	The disk block number to read from.

Returns

Pointer to a newly allocated and populated btree_node_t structure.

btree_remove()

int btree_remove	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	handle,
		uint32_t	key )

Removes an entry from the B-tree based on its key.

This is the public interface for removing an entry from a B-tree. It initiates a recursive deletion process starting from the tree root.

Internally, the actual logic is handled by btree_remove_internal, which updates the tree structure, balances nodes if necessary, and writes changes to disk.

Parameters

disk	Pointer to the open disk file.
sb	Pointer to the superblock, used for block deallocation if necessary.
handle	Pointer to the B-tree handle structure.
key	The key of the entry to remove from the tree.

Returns

int 1 if the key was found and removed, 0 if the key was not found.

btree_remove_entry()

int btree_remove_entry	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	handle,
		const void *	entry )

Remove an entry using the handle's comparator (exact-match).

Suitable for trees where ordering is defined by a comparator (e.g., directory entries ordered by hash+name). Returns 1 if the entry was found and removed, 0 if not found, -1 on error.

btree_search()

int btree_search	(	FILE *	disk,
		btree_handle_t *	handle,
		uint32_t	node_block,
		uint32_t	key,
		void *	output )

Searches for a key in the B-tree and retrieves the associated entry.

This function performs a recursive search in the B-tree starting at the node identified by node_block. It uses the comparison function and key extractor provided in the B-tree handle to locate the entry corresponding to the given key.

If the key is found, the corresponding entry is copied into output. If not found, the function returns 0.

Parameters

disk	Pointer to the open disk file.
handle	Pointer to the B-tree handle containing type and logic information.
node_block	Block number of the node to begin searching from.
key	The key to search for.
output	Pointer to a memory location where the found entry will be copied.

Returns

int 1 if the key was found, 0 otherwise.

btree_search_entry()

int btree_search_entry	(	FILE *	disk,
		btree_handle_t *	handle,
		uint32_t	node_block,
		const void *	needle,
		void *	output )

Searches for an entry in the B-tree using the handle's compare function (full entry comparison), not just the numeric key.

This is useful for data types whose ordering depends on a composite key (e.g., directory entries ordered by (hash(filename), filename)).

Parameters

disk	Pointer to the open disk file.
handle	Pointer to the B-tree handle containing type/logic functions.
node_block	Block number of the node to begin searching from.
needle	Pointer to an in-memory entry (same type as tree entries) used for comparison and navigation.
output	Pointer where the found entry will be copied if present.

Returns

int 1 if found, 0 otherwise.

btree_update()

int btree_update	(	FILE *	disk,
		btree_handle_t *	handle,
		uint32_t	node_block,
		void *	new_entry )

Updates an existing entry in the B-tree with new data.

This function searches for an entry in the B-tree based on the key extracted from new_entry, and if found, replaces the existing entry with the new one. The update is performed in-place within the node and persisted to disk.

If the key is not found in the current node and the node is not a leaf, the function recurses into the appropriate child. If the key is not found anywhere in the tree, the function returns 0 and no update occurs.

Parameters

disk	Pointer to the open disk file.
handle	Pointer to the B-tree handle that contains type-specific information.
node_block	Block number of the node to start searching from (typically the root).
new_entry	Pointer to the entry containing updated data (must contain a valid key).

Returns

int 1 if the entry was found and updated, 0 if the key was not found.

btree_write_node()

int btree_write_node	(	FILE *	disk,
		btree_handle_t *	handle,
		uint32_t	block,
		btree_node_t *	node )

Writes a B-tree node to disk.

Serializes the in-memory B-tree node structure into a fixed-size block and writes it to the specified block number on disk.

Parameters

disk	Pointer to the open disk file.
handle	Pointer to the B-tree handle containing entry configuration.
block	The block number where the node should be written.
node	Pointer to the in-memory B-tree node structure.

Returns

0 on success, -1 on failure.

hash_filename()

uint32_t hash_filename

(

const char *

name

)

Computes the djb2 hash of a given filename.

This function implements the classic djb2 hashing algorithm created by Daniel J. Bernstein. It is fast and widely used for hashing strings.

Parameters

name	The null-terminated string (filename) to be hashed.

Returns

A 32-bit unsigned integer hash value.