index.h File Reference

File index mapping and serialization functions. More...

#include <stdio.h>
#include "fs.h"

Include dependency graph for index.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	inode_s
	Individual file node in the index map. More...
struct	ibucket_s
	Index bucket structure for storing linked list head/tail pointers. More...
struct	index_s
	Index map structure for storing file nodes. More...

Macros
#define	INDEXBUCKETS   4096
	The fixed number of buckets in the index map.
#define	INDEXBUCKETSMASK   0xFFF
	The bitmask used for deriving the bucket index from the hash value.

Functions
uint64_t	indexhash (const char *fp)
	Hashes the filepath string for use in the index map.
struct inode_s *	indexfind (const struct index_s *idx, const char *fp, uint64_t fphash)
	Searches the index for a node with a matching filepath.
int	indexwrite (struct index_s *idx, FILE *s)
	Flattens the index map into a sorted array of nodes (by filepath). The list is then written to the file stream and freed.
int	indexread (struct index_s *idx, FILE *s)
	Reads a file stream and deserializes the contents into a map of individual file nodes.
struct inode_s *	indexput (struct index_s *idx, const char *fp, uint64_t fphash, struct fsstat_s st)
	Copies the node and inserts it into the index mapping.
void	indexfree (struct index_s *idx)
	Frees all nodes in the index map.
struct inode_s **	indexlist (const struct index_s *idx)
	Flattens the index map into an unsorted array of nodes. The list is dynamically allocated and must be freed by the caller. Array size is determined by the size field in the index struct.

Detailed Description

File index mapping and serialization functions.

Macro Definition Documentation

INDEXBUCKETS

#define INDEXBUCKETS   4096

The fixed number of buckets in the index map.

Note

This is a magic number, but via testing, performance is healthy around ~40 nodes per bucket, so this should roughly accommodate ~150k nodes.

INDEXBUCKETSMASK

#define INDEXBUCKETSMASK   0xFFF

The bitmask used for deriving the bucket index from the hash value.

Maximum bucket index mask.

Note

This should correspond to the number of buckets defined in INDEXBUCKETS (0xFFF, 0b1111_1111_1111, 2^12-1 = 4095).

Function Documentation

indexfind()

struct inode_s * indexfind	(	const struct index_s *	idx,
		const char *	fp,
		uint64_t	fphash )

Searches the index for a node with a matching filepath.

Parameters

idx	The index to search
fp	The search value (filepath) to compare
fphash	The hash value of the filepath to compare

Returns

If a match is found, its pointer is returned, otherwise NULL.

Here is the caller graph for this function:

indexfree()

void indexfree

(

struct index_s *

idx

)

Frees all nodes in the index map.

Parameters

idx	The index to free

Here is the call graph for this function:

Here is the caller graph for this function:

indexhash()

uint64_t indexhash

(

const char *

fp

)

Hashes the filepath string for use in the index map.

Note

64-bit FNV-1a implementation is used for hashing.

Parameters

fp	The filepath string to hash

Returns

The hashed value of the filepath.

Here is the caller graph for this function:

indexlist()

struct inode_s ** indexlist

(

const struct index_s *

idx

)

Flattens the index map into an unsorted array of nodes. The list is dynamically allocated and must be freed by the caller. Array size is determined by the size field in the index struct.

Parameters

idx	The index to flatten

Returns

If successful, a pointer to an array of size idx->size is returned. Otherwise, NULL is returned and errno is set.

Here is the caller graph for this function:

indexput()

struct inode_s * indexput	(	struct index_s *	idx,
		const char *	fp,
		uint64_t	fphash,
		struct fsstat_s	st )

Copies the node and inserts it into the index mapping.

Parameters

idx	The index to insert into
fp	The file path to use for the new node, duplicated internally
fphash	The file path hash value to use for the new node
st	The file stat info to use for the new node

Returns

The pointer to the new node in the index map, otherwise NULL is returned and errno is set.

Here is the call graph for this function:

Here is the caller graph for this function:

indexread()

int indexread	(	struct index_s *	idx,
		FILE *	s )

Reads a file stream and deserializes the contents into a map of individual file nodes.

Parameters

idx	The index to populate
s	The file stream to read from

Returns

If successful, 0 is returned. Otherwise, -1 is returned and errno is set.

Here is the call graph for this function:

Here is the caller graph for this function:

indexwrite()

int indexwrite	(	struct index_s *	idx,
		FILE *	s )

Flattens the index map into a sorted array of nodes (by filepath). The list is then written to the file stream and freed.

Parameters

idx	The index to flatten
s	The file stream to write to

Returns

If successful, 0 is returned. Otherwise, -1 is returned and errno is set.

Here is the call graph for this function:

Here is the caller graph for this function: