Type of a node in a file_tree. More...

#include <file_tree.h>

Public Types
using	node_ptr = std::shared_ptr< node >
	Type of a pointer to a `node`.

using	child_list = std::map< std::string, node_ptr >
	Type of sequence of children of a `node`.

using	entry = child_list::value_type
	Type of an element in a `child_list`.

using	child_list_ptr = std::shared_ptr< child_list >
	Type of a pointer to a `child_list`

Public Member Functions
bool	is_file () const
	Say whether the `node` represents a file.

bool	is_dir () const
	Say whether the `node` represents a directory.

void	traverse (traverser &action) const
	Traverse the `node` recursively, performing an action at each node encountered. More...

node *	root ()
	Get a pointer to the root node of the `node`.

template<typename Filter >
unsigned	insert (path_t &abs_path, Filter &filter)
	Recursively insert files within a path into the `node`. More...

Private Member Functions
	node (node *parent=nullptr)
	Private default constructor.

	node (child_list_ptr children)
	Explicitly construct a node with a given `child_list`

node *	guardian (std::string const &key) const
	Test whether the parent of this `node` contains a given key. More...

node *	parent () const
	Get a pointer to the parent of this `node`, which may be `nullptr`

node *	find (std::string const &key)
	Test whether this `node` contains a given key. More...

node *	ancestral_candidate_for_real_path (path_t const &cur_path, path_t const &real_path)
	Ancestor probe for symbolic links. More...

template<typename Filter >
unsigned	intermediate_insert (path_t &abs_path, Filter &filter)
	Recursively insert files within a path into the `node`. More...

template<typename Filter >
unsigned	terminal_insert (path_t &abs_path, Filter &filter)
	Recursively insert files within a path into the `node`. More...

void	insert (std::string const &key, node_ptr &child)
	Insert a child to this `node` with a given key. More...

Private Attributes
node *	_parent
	Pointer to the parent `node`, or `nullptr`

std::shared_ptr< child_list >	_children
	Pointer to the immediate children of the `node`, or `nullptr`

Friends
struct	file_tree

Detailed Description

Type of a node in a file_tree.

struct node is the internal container type that implements file_tree. A node consists of a pointer to its parent node and a pointer to a map containing its children, keyed by filename.

Definition at line 66 of file file_tree.h.

Member Function Documentation

file_tree::node * file_tree::node::ancestral_candidate_for_real_path	(	path_t const &	cur_path,
		path_t const &	real_path
	)

private

Ancestor probe for symbolic links.

Find the nearest ancestor of the node, if any, that is:-

an unconfirmed candidate for inclusion in the file_tree
is keyed by a path that is an initial subpath of the path that keys this and also of the real path to which the path that keys this is resolved.

Parameters

cur_path	The path that keys `this`.
real_path	The real path to which `cur_path` resolves.

Returns: Pointer to the nearest ancestor of *this that satisfies the two conditions, if any, else nullptr.

This conceptually complicated method is called only when the path that keys *this refers to a symbolic link. In this case the obvious course is just to take the real path to which the symbolic link resolves, insert it "from scratch" at the root of the file tree and carry on with the current traversal. But this may be a mistake.

Since all top-level input paths are resolved to real paths, a symbolic link will only be encountered while we are recursively exploring some directory to determine whether any files are selected beneath it, and therefore whether the candidate node that represents it should actually be inserted in the file_tree. While we are doing this, and when we encounter the symbolic link, that candidate node has yet to be inserted. Hence, if the real path to the symbolic link extends the path that keys our candidate node, the path elements that key the nodes from the candidate downward will not be already present in the tree and all eligible nodes beneath the real path will be inserted with their keys. But some initial sequence of the same keys have already been confirmed not already present in the descent that lead us to the symbolic link in the first place. So in handling the symbolic link, we will prematurely generate a sub-tree that is identical with one we are in the process of generating, and which is to be inserted in the same place in the file_tree, if at all.

This could be an arbitrarily great waste of time, even though the implementation of the file_tree inherantly prevents duplicate entries being created by duplicate insertions. In fact it could be an infinite waste of time: if the symbolic link is "self-including" - i.e. refers to one of its own ancestral directories - then the simple "start from scratch" approach will loop forever. To avoid these hazards, when we encounter a symbolic link, we wish to know whether the real path it resolves to either is or extends any path that we are already recursively traversing to decide upon the insertion of some ancestral node. Only if that is not the case need we bother to explore the symbolic link. This method gives us the answer.

Definition at line 94 of file file_tree.cpp.

node* file_tree::node::find ( std::string const & key )

inlineprivate

Test whether this node contains a given key.

Parameters

key	The key to be sought.

Returns: A pointer to the child of this node that has key key, else nullptr.

Definition at line 143 of file file_tree.h.

node* file_tree::node::guardian ( std::string const & key ) const

inlineprivate

Test whether the parent of this node contains a given key.

Parameters

key	The key to be sought.

Returns: A pointer to the parent of this node if it exists and has a child with key key; otherwise nullptr.

Definition at line 129 of file file_tree.h.

template<typename Filter >

unsigned file_tree::node::insert	(	path_t &	abs_path,
		Filter &	filter
	)

inline

Recursively insert files within a path into the node.

Recursively insert files within a path into the node, selecting eligible files by a filter.

Parameters

abs_path	The absolute path within which files are to be added to the node.
filter	The filter for selecting eligible files.

Returns: The number of files inserted.

Definition at line 109 of file file_tree.h.

void file_tree::node::insert	(	std::string const &	key,
		node_ptr &	child
	)

private

Insert a child to this node with a given key.

Parameters

key	The key of the child node to be inserted
child	The child node to be inserted.

Definition at line 47 of file file_tree.cpp.

template<typename Filter >

template unsigned file_tree::node::intermediate_insert	(	path_t &	abs_path,
		Filter &	filter
	)

private

Recursively insert files within a path into the node.

Recursively insert files within a path into the node, selecting eligible files by a filter.

Parameters

abs_path	The absolute path within which files are to be added to the node.
filter	The filter for selecting eleigible files.

This member function implements the public member insert. It calls itself recursively for as long as successive elements of abs_path are already represented in the node and finally calls insert_terminal to insert files from the terminal remainder of abs_path.

Returns: The number of files inserted.

Definition at line 114 of file file_tree.cpp.

template<typename Filter >

unsigned file_tree::node::terminal_insert	(	path_t &	abs_path,
		Filter &	filter
	)

private

Recursively insert files within a path into the node.

Recursively insert files within a terminal segment of a path into the node, selecting eligible files by a filter.

Parameters

abs_path	The absolute path within which files are to be added to the node.
filter	The filter for selecting eleigible files.

Returns: The number of files inserted.

abs_path is assumed to be positioned at the first element, if any, from which files have not already been inserted to the node.

This member function is called by insert_intermediate when that function has exhausted the elements of the path that are already represented in the node.

Definition at line 140 of file file_tree.cpp.

void file_tree::node::traverse ( file_tree::traverser & action ) const

Traverse the node recursively, performing an action at each node encountered.

Parameters

action The action to be applied recursively to nodes.

Definition at line 63 of file file_tree.cpp.

The documentation for this struct was generated from the following files:

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Function Documentation