btrfs-progs: print-tree: Introduce --bfs and --dfs options

Originally print-tree uses depth first search to print trees.
This works fine until we reach 3 level trees (root node level is 2).

For tall trees whose root level is 2 or higher, DFS will mix nodes and
leaves like the following example:

Level 2                       A
                             / \
Level 1                     B   C
                          / |   | \
Level 0                  D  E   F  G

DFS will cause the following output sequence:
A   B   D   E   C   F   G
Which in term of node/leave is:
N   N   L   L   N   L   L

Such mixed node/leave result is sometimes hard for human to read.

This patch will introduce 2 new options, --bfs and --dfs.

  --dfs: keeps the original output sequence, and to keep things
         compatible it's the default behavior.

  --bfs: uses breadth-first search, and will cause better output
         sequence like:

	 A   B   C   D   E   F   G
	 Which in term of node/leave is:
	 N   N   N   L   L   L   L

Much better sorted and may become default in the future.

Reviewed-by: Nikolay Borisov <nborisov@suse.com>
Signed-off-by: Qu Wenruo <wqu@suse.com>
Signed-off-by: David Sterba <dsterba@suse.com>

1 files changed, 14 insertions, 1 deletions

diff --git a/print-tree.h b/print-tree.h
index 62667d7f..9e041a34 100644
--- a/print-tree.h
+++ b/print-tree.h
@@ -20,7 +20,20 @@
 #define __PRINT_TREE_H__
 
 void btrfs_print_leaf(struct extent_buffer *l);
-void btrfs_print_tree(struct extent_buffer *t, int follow);
+
+/*
+ * Print a tree block (applies to both node and leaf).
+ *
+ * @eb:		Tree block
+ * @follow:	Set non-zero to print all its children.
+ * @traverse:	The traverse order. Support DFS and BFS.
+ *		Will fallback to DFS for unknown order.
+ */
+#define BTRFS_PRINT_TREE_DFS		0
+#define BTRFS_PRINT_TREE_BFS		1
+#define BTRFS_PRINT_TREE_DEFAULT	BTRFS_PRINT_TREE_DFS
+void btrfs_print_tree(struct extent_buffer *eb, int follow, int traverse);
+
 void btrfs_print_key(struct btrfs_disk_key *disk_key);
 void print_chunk_item(struct extent_buffer *eb, struct btrfs_chunk *chunk);
 void print_extent_item(struct extent_buffer *eb, int slot, int metadata);