btree_bsfs.c File Reference

Implementation of B-tree operations for the BSFS filesystem. More...

Functions
uint32_t	get_inode_key (const void *entry)
	Extracts the key from an inode entry.
int	compare_inode (const void *a, const void *b)
	Compares two inode entries by their inode number.
btree_handle_t *	btree_create_inode_handle ()
	Creates a B-tree handle specifically for managing inode entries.
uint32_t	get_bspan_key (const void *entry)
	Extracts the key from a bspan entry.
int	compare_bspan (const void *a, const void *b)
	Compares two bspan entries by their logical file block number.
btree_handle_t *	btree_create_bspan_handle ()
	Creates a B-tree handle for managing bspan entries.
uint32_t	hash_filename (const char *name)
	Computes the djb2 hash of a given filename.
uint32_t	get_dir_entry_key (const void *entry)
	Retrieves the key (hash of the filename) for a directory entry.
int	compare_dir_entry (const void *a, const void *b)
	Compares two directory entries by filename hash.
btree_handle_t *	btree_create_dir_entry_handle ()
	Creates a B-tree handle for managing directory entries.
uint32_t	get_rec_entry_key (const void *entry)
	Extracts the key from a recovery entry.
int	compare_rec_entry (const void *a, const void *b)
	Compares two recovery entries by their index field.
btree_handle_t *	btree_create_rec_entry_handle ()
	Creates a B-tree handle for managing recovery entries.
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.
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_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_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_insert (FILE *disk, superblock_t *sb, btree_handle_t *handle, void *entry)
	Inserts a new entry into the B-tree.
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_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

Implementation of B-tree operations for the BSFS filesystem.

This file implements a disk-based B-tree used to manage mappings in the BSFS filesystem, such as inode references, block span allocations, and recovery indexes.

The B-tree is parameterized by entry type and size, and each node is stored in a disk block. This implementation supports search, insertion, update, and deletion operations, ensuring the tree remains balanced across writes.

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.

compare_bspan()

int compare_bspan	(	const void *	a,
		const void *	b )

Compares two bspan entries by their logical file block number.

This function compares the keys extracted from two bspan_t entries using get_bspan_key. It returns:

• A negative value if a < b
• Zero if a == b
• A positive value if a > b

This comparison is used to maintain the order of bspan entries in the B-tree.

Parameters

a	Pointer to the first bspan entry.
b	Pointer to the second bspan entry.

Returns

int Comparison result: negative, zero, or positive.

compare_dir_entry()

int compare_dir_entry	(	const void *	a,
		const void *	b )

Compares two directory entries by filename hash.

This function compares two dir_entry_t entries based on the hash of their filenames using the djb2 algorithm. If the hashes are equal, it falls back to a full strcmp to resolve hash collisions.

Parameters

a	Pointer to the first dir_entry_t.
b	Pointer to the second dir_entry_t.

Returns

-1 if a < b, 1 if a > b, 0 if equal.

compare_inode()

int compare_inode	(	const void *	a,
		const void *	b )

Compares two inode entries by their inode number.

This function compares the keys extracted from two inode_t entries using get_inode_key. It returns:

• A negative value if a < b
• Zero if a == b
• A positive value if a > b

This comparison logic is used by the B-tree to maintain order among inode entries.

Parameters

a	Pointer to the first inode entry.
b	Pointer to the second inode entry.

Returns

int Comparison result: negative, zero, or positive.

compare_rec_entry()

int compare_rec_entry	(	const void *	a,
		const void *	b )

Compares two recovery entries by their index field.

This function compares the keys extracted from two rec_entry_t entries using get_rec_entry_key. It returns:

• A negative value if a < b
• Zero if a == b
• A positive value if a > b

This is used to maintain the sorted order of recovery entries in the B-tree.

Parameters

a	Pointer to the first recovery entry.
b	Pointer to the second recovery entry.

Returns

int Comparison result: negative, zero, or positive.

get_bspan_key()

uint32_t get_bspan_key

(

const void *

entry

)

Extracts the key from a bspan entry.

This function casts the input pointer to a bspan_t and returns the file_blk field, which represents the logical file block number. This value is used as the key in B-tree operations for bspan entries.

Parameters

entry

Pointer to a bspan entry (expected to be of type bspan_t).

Returns

uint32_t The logical file block number used as the key.

get_dir_entry_key()

uint32_t get_dir_entry_key

(

const void *

entry

)

Retrieves the key (hash of the filename) for a directory entry.

This function is used by the B-tree infrastructure to extract the comparison key from a directory entry, which is the result of hashing its filename with hash_filename.

Parameters

entry

Pointer to the dir_entry_t structure.

Returns

The hash of the filename as a 32-bit unsigned integer.

get_inode_key()

uint32_t get_inode_key

(

const void *

entry

)

Extracts the key from an inode entry.

This function casts the input pointer to an inode_t and returns its inode_number field, which is used as the key for insertion, search, and comparison in the B-tree of inodes.

Parameters

entry

Pointer to the inode entry (expected to be of type inode_t).

Returns

uint32_t The inode number used as the key.

get_rec_entry_key()

uint32_t get_rec_entry_key

(

const void *

entry

)

Extracts the key from a recovery entry.

This function casts the input pointer to a rec_entry_t and returns the index field, which serves as the unique identifier or key for the recovery entry in the B-tree.

Parameters

entry

Pointer to a recovery entry (expected to be of type rec_entry_t).

Returns

uint32_t The index value used as the key in the B-tree.

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.