From 6639ffc2e026b34b906854b8c60bd72d4b95e78d Mon Sep 17 00:00:00 2001 From: Stephen Boyd Date: Mon, 3 Aug 2009 21:13:21 -0700 Subject: technical-docs: document tree-walking API Signed-off-by: Stephen Boyd Signed-off-by: Junio C Hamano --- Documentation/technical/api-tree-walking.txt | 147 +++++++++++++++++++++++++-- 1 file changed, 140 insertions(+), 7 deletions(-) (limited to 'Documentation/technical') diff --git a/Documentation/technical/api-tree-walking.txt b/Documentation/technical/api-tree-walking.txt index e3ddf9128..55b728632 100644 --- a/Documentation/technical/api-tree-walking.txt +++ b/Documentation/technical/api-tree-walking.txt @@ -1,12 +1,145 @@ tree walking API ================ -Talk about , things like +The tree walking API is used to traverse and inspect trees. -* struct tree_desc -* init_tree_desc -* tree_entry_extract -* update_tree_entry -* get_tree_entry +Data Structures +--------------- -(JC, Linus) +`struct name_entry`:: + + An entry in a tree. Each entry has a sha1 identifier, pathname, and + mode. + +`struct tree_desc`:: + + A semi-opaque data structure used to maintain the current state of the + walk. ++ +* `buffer` is a pointer into the memory representation of the tree. It always +points at the current entry being visited. + +* `size` counts the number of bytes left in the `buffer`. + +* `entry` points to the current entry being visited. + +`struct traverse_info`:: + + A structure used to maintain the state of a traversal. ++ +* `prev` points to the traverse_info which was used to descend into the +current tree. If this is the top-level tree `prev` will point to +a dummy traverse_info. + +* `name` is the entry for the current tree (if the tree is a subtree). + +* `pathlen` is the length of the full path for the current tree. + +* `conflicts` can be used by callbacks to maintain directory-file conflicts. + +* `fn` is a callback called for each entry in the tree. See Traversing for more +information. + +* `data` can be anything the `fn` callback would want to use. + +Initializing +------------ + +`init_tree_desc`:: + + Initialize a `tree_desc` and decode its first entry. The buffer and + size parameters are assumed to be the same as the buffer and size + members of `struct tree`. + +`fill_tree_descriptor`:: + + Initialize a `tree_desc` and decode its first entry given the sha1 of + a tree. Returns the `buffer` member if the sha1 is a valid tree + identifier and NULL otherwise. + +`setup_traverse_info`:: + + Initialize a `traverse_info` given the pathname of the tree to start + traversing from. The `base` argument is assumed to be the `path` + member of the `name_entry` being recursed into unless the tree is a + top-level tree in which case the empty string ("") is used. + +Walking +------- + +`tree_entry`:: + + Visit the next entry in a tree. Returns 1 when there are more entries + left to visit and 0 when all entries have been visited. This is + commonly used in the test of a while loop. + +`tree_entry_len`:: + + Calculate the length of a tree entry's pathname. This utilizes the + memory structure of a tree entry to avoid the overhead of using a + generic strlen(). + +`update_tree_entry`:: + + Walk to the next entry in a tree. This is commonly used in conjunction + with `tree_entry_extract` to inspect the current entry. + +`tree_entry_extract`:: + + Decode the entry currently being visited (the one pointed to by + `tree_desc's` `entry` member) and return the sha1 of the entry. The + `pathp` and `modep` arguments are set to the entry's pathname and mode + respectively. + +`get_tree_entry`:: + + Find an entry in a tree given a pathname and the sha1 of a tree to + search. Returns 0 if the entry is found and -1 otherwise. The third + and fourth parameters are set to the entry's sha1 and mode + respectively. + +Traversing +---------- + +`traverse_trees`:: + + Traverse `n` number of trees in parallel. The `fn` callback member of + `traverse_info` is called once for each tree entry. + +`traverse_callback_t`:: + The arguments passed to the traverse callback are as follows: ++ +* `n` counts the number of trees being traversed. + +* `mask` has its nth bit set if something exists in the nth entry. + +* `dirmask` has its nth bit set if the nth tree's entry is a directory. + +* `entry` is an array of size `n` where the nth entry is from the nth tree. + +* `info` maintains the state of the traversal. + ++ +Returning a negative value will terminate the traversal. Otherwise the +return value is treated as an update mask. If the nth bit is set the nth tree +will be updated and if the bit is not set the nth tree entry will be the +same in the next callback invocation. + +`make_traverse_path`:: + + Generate the full pathname of a tree entry based from the root of the + traversal. For example, if the traversal has recursed into another + tree named "bar" the pathname of an entry "baz" in the "bar" + tree would be "bar/baz". + +`traverse_path_len`:: + + Calculate the length of a pathname returned by `make_traverse_path`. + This utilizes the memory structure of a tree entry to avoid the + overhead of using a generic strlen(). + +Authors +------- + +Written by Junio C Hamano and Linus Torvalds + -- cgit v1.2.1