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, 22 insertions, 9 deletions

diff --git a/cmds-inspect-dump-tree.c b/cmds-inspect-dump-tree.c
index 563b4e37..1f217a9d 100644
--- a/cmds-inspect-dump-tree.c
+++ b/cmds-inspect-dump-tree.c
@@ -221,6 +221,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 	int uuid_tree_only = 0;
 	int roots_only = 0;
 	int root_backups = 0;
+	int traverse = BTRFS_PRINT_TREE_DEFAULT;
 	unsigned open_ctree_flags;
 	u64 block_only = 0;
 	struct btrfs_root *tree_root_scan;
@@ -238,7 +239,8 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 	optind = 0;
 	while (1) {
 		int c;
-		enum { GETOPT_VAL_FOLLOW = 256 };
+		enum { GETOPT_VAL_FOLLOW = 256, GETOPT_VAL_DFS,
+		       GETOPT_VAL_BFS };
 		static const struct option long_options[] = {
 			{ "extents", no_argument, NULL, 'e'},
 			{ "device", no_argument, NULL, 'd'},
@@ -248,6 +250,8 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 			{ "block", required_argument, NULL, 'b'},
 			{ "tree", required_argument, NULL, 't'},
 			{ "follow", no_argument, NULL, GETOPT_VAL_FOLLOW },
+			{ "bfs", no_argument, NULL, GETOPT_VAL_BFS },
+			{ "dfs", no_argument, NULL, GETOPT_VAL_DFS },
 			{ NULL, 0, NULL, 0 }
 		};
 
@@ -303,6 +307,12 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 		case GETOPT_VAL_FOLLOW:
 			follow = true;
 			break;
+		case GETOPT_VAL_DFS:
+			traverse = BTRFS_PRINT_TREE_DFS;
+			break;
+		case GETOPT_VAL_BFS:
+			traverse = BTRFS_PRINT_TREE_BFS;
+			break;
 		default:
 			usage(cmd_inspect_dump_tree_usage);
 		}
@@ -347,7 +357,7 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 				(unsigned long long)block_only);
 			goto close_root;
 		}
-		btrfs_print_tree(leaf, follow);
+		btrfs_print_tree(leaf, follow, BTRFS_PRINT_TREE_DEFAULT);
 		free_extent_buffer(leaf);
 		goto close_root;
 	}
@@ -374,17 +384,20 @@ int cmd_inspect_dump_tree(int argc, char **argv)
 		} else {
 			if (info->tree_root->node) {
 				printf("root tree\n");
-				btrfs_print_tree(info->tree_root->node, 1);
+				btrfs_print_tree(info->tree_root->node, 1,
+						 traverse);
 			}
 
 			if (info->chunk_root->node) {
 				printf("chunk tree\n");
-				btrfs_print_tree(info->chunk_root->node, 1);
+				btrfs_print_tree(info->chunk_root->node, 1,
+						 traverse);
 			}
 
 			if (info->log_root_tree) {
 				printf("log root tree\n");
-				btrfs_print_tree(info->log_root_tree->node, 1);
+				btrfs_print_tree(info->log_root_tree->node, 1,
+						 traverse);
 			}
 		}
 	}
@@ -404,7 +417,7 @@ again:
 			goto close_root;
 		}
 		printf("root tree\n");
-		btrfs_print_tree(info->tree_root->node, 1);
+		btrfs_print_tree(info->tree_root->node, 1, traverse);
 		goto close_root;
 	}
 
@@ -414,7 +427,7 @@ again:
 			goto close_root;
 		}
 		printf("chunk tree\n");
-		btrfs_print_tree(info->chunk_root->node, 1);
+		btrfs_print_tree(info->chunk_root->node, 1, traverse);
 		goto close_root;
 	}
 
@@ -424,7 +437,7 @@ again:
 			goto close_root;
 		}
 		printf("log root tree\n");
-		btrfs_print_tree(info->log_root_tree->node, 1);
+		btrfs_print_tree(info->log_root_tree->node, 1, traverse);
 		goto close_root;
 	}
 
@@ -570,7 +583,7 @@ again:
 					       btrfs_header_level(buf));
 				} else {
 					printf(" \n");
-					btrfs_print_tree(buf, 1);
+					btrfs_print_tree(buf, 1, traverse);
 				}
 			}
 			free_extent_buffer(buf);