Add option to sort results of bbackupquery ls command.

The new default is to sort by name, with directories first.

Put the documentation on the "ls" command, instead of the "list" command,
since that's annoyed me too many times.

The recursive list option is changed from "-r" to "-R", to match the shell
ls command.

3 files changed, 134 insertions, 16 deletions

diff --git a/bin/bbackupquery/BackupQueries.cpp b/bin/bbackupquery/BackupQueries.cpp
index 2c4c13d8..c701ff7e 100644
--- a/bin/bbackupquery/BackupQueries.cpp
+++ b/bin/bbackupquery/BackupQueries.cpp
@@ -24,6 +24,7 @@
 	#include <dirent.h>
 #endif
 
+#include <algorithm>
 #include <cstring>
 #include <limits>
 #include <iostream>
@@ -248,6 +249,19 @@ void BackupQueries::DoCommand(ParsedCommand& rCommand)
 	}
 }
 
+#define LIST_OPTION_TIMES_ATTRIBS	'a'
+#define LIST_OPTION_SORT_NO_DIRS_FIRST	'D'
+#define LIST_OPTION_NOFLAGS		'F'
+#define LIST_OPTION_DISPLAY_HASH	'h'
+#define LIST_OPTION_SORT_ID		'i'
+#define LIST_OPTION_NOOBJECTID		'I'
+#define LIST_OPTION_SORT_REVERSE	'r'
+#define LIST_OPTION_RECURSIVE		'R'
+#define LIST_OPTION_SIZEINBLOCKS	's'
+#define LIST_OPTION_SORT_SIZE		'S'
+#define LIST_OPTION_TIMES_LOCAL		't'
+#define LIST_OPTION_TIMES_UTC		'T'
+#define LIST_OPTION_SORT_NONE		'U'
 
 // --------------------------------------------------------------------------
 //
@@ -259,15 +273,6 @@ void BackupQueries::DoCommand(ParsedCommand& rCommand)
 // --------------------------------------------------------------------------
 void BackupQueries::CommandList(const std::vector<std::string> &args, const bool *opts)
 {
-	#define LIST_OPTION_RECURSIVE		'r'
-	#define LIST_OPTION_NOOBJECTID		'I'
-	#define LIST_OPTION_NOFLAGS		'F'
-	#define LIST_OPTION_TIMES_LOCAL		't'
-	#define LIST_OPTION_TIMES_UTC		'T'
-	#define LIST_OPTION_TIMES_ATTRIBS	'a'
-	#define LIST_OPTION_SIZEINBLOCKS	's'
-	#define LIST_OPTION_DISPLAY_HASH	'h'
-
 	// default to using the current directory
 	int64_t rootDir = GetCurrentDirectoryID();
 
@@ -350,6 +355,75 @@ static std::string GetTimeString(BackupStoreDirectory::Entry& en,
 	return out.str();
 }
 
+/* We need a way to pass options to sort functions for sorting. The algorithm
+ * doesn't seem to provide a way to do this, so I'm using a global variable.
+ * Which is not thread safe, but we don't currently use threads so that should
+ * be OK. Do not use threads without checking!
+ */
+const bool *gThreadUnsafeOptions;
+
+int DirsFirst(BackupStoreDirectory::Entry* a,
+	BackupStoreDirectory::Entry* b)
+{
+	if (a->IsDir() && !b->IsDir())
+	{
+		return -1; // a < b
+	}
+	else if (!a->IsDir() && b->IsDir())
+	{
+		return 1; // b > a
+	}
+	else
+	{
+		return 0; // continue comparison
+	}
+}
+
+#define MAYBE_DIRS_FIRST(a, b) \
+	if (!gThreadUnsafeOptions[LIST_OPTION_SORT_NO_DIRS_FIRST]) \
+	{ \
+		int result = DirsFirst(a, b); \
+		if (result < 0) return true; /* a < b */ \
+		else if (result > 0) return false; /* a > b */ \
+		/* else: fall through */ \
+	}
+
+#define MAYBE_REVERSE(result) \
+	(result != gThreadUnsafeOptions[LIST_OPTION_SORT_REVERSE])
+// result is false, opts[reverse] is false => return false
+// result is false, opts[reverse] is true  => return true
+// result is true,  opts[reverse] is false => return true
+// result is true,  opts[reverse] is true  => return false
+// this is logical XOR, for which the boolean operator is !=.
+
+bool SortById(BackupStoreDirectory::Entry* a,
+	BackupStoreDirectory::Entry* b)
+{
+	MAYBE_DIRS_FIRST(a, b);
+	bool result = (a->GetObjectID() < b->GetObjectID());
+	return MAYBE_REVERSE(result);
+}
+
+bool SortBySize(BackupStoreDirectory::Entry* a,
+	BackupStoreDirectory::Entry* b)
+{
+	MAYBE_DIRS_FIRST(a, b);
+	bool result = (a->GetSizeInBlocks() < b->GetSizeInBlocks());
+	return MAYBE_REVERSE(result);
+}
+
+bool SortByName(BackupStoreDirectory::Entry* a,
+	BackupStoreDirectory::Entry* b)
+{
+	MAYBE_DIRS_FIRST(a, b);
+	BackupStoreFilenameClear afc(a->GetName());
+	BackupStoreFilenameClear bfc(b->GetName());
+	std::string an = afc.GetClearFilename();
+	std::string bn = bfc.GetClearFilename();
+	bool result = (an < bn);
+	return MAYBE_REVERSE(result);
+}
+
 // --------------------------------------------------------------------------
 //
 // Function
@@ -399,11 +473,51 @@ void BackupQueries::List(int64_t DirID, const std::string &rListRoot,
 	std::auto_ptr<IOStream> dirstream(mrConnection.ReceiveStream());
 	dir.ReadFromStream(*dirstream, mrConnection.GetTimeout());
 
-	// Then... display everything
+	// Store entry pointers in a std::vector for sorting
 	BackupStoreDirectory::Iterator i(dir);
 	BackupStoreDirectory::Entry *en = 0;
+	std::vector<BackupStoreDirectory::Entry*> sorted_entries;
 	while((en = i.Next()) != 0)
 	{
+		sorted_entries.push_back(en);
+	}
+
+	// Typedef to avoid mind-bending while dealing with pointers to functions.
+	typedef bool (EntryComparator_t)(BackupStoreDirectory::Entry* a,
+		BackupStoreDirectory::Entry* b);
+	// Default is no comparator, i.e. no sorting.
+	EntryComparator_t* pComparator = NULL;
+
+	if (opts[LIST_OPTION_SORT_ID])
+	{
+		pComparator = &SortById;
+	}
+	else if (opts[LIST_OPTION_SORT_SIZE])
+	{
+		pComparator = &SortBySize;
+	}
+	else if (opts[LIST_OPTION_SORT_NONE])
+	{
+		// do nothing
+	}
+	else // sort by name
+	{
+		pComparator = &SortByName;
+	}
+
+	if (pComparator != NULL)
+	{
+		gThreadUnsafeOptions = opts;
+		sort(sorted_entries.begin(), sorted_entries.end(),
+			pComparator);
+		gThreadUnsafeOptions = NULL;
+	}
+
+	for (std::vector<BackupStoreDirectory::Entry*>::const_iterator
+		i = sorted_entries.begin();
+		i != sorted_entries.end(); i++)
+	{
+		en = *i;
 		std::ostringstream buf;
 
 		// Display this entry
diff --git a/bin/bbackupquery/CommandCompletion.cpp b/bin/bbackupquery/CommandCompletion.cpp
index 3bc79f3a..2ca26991 100644
--- a/bin/bbackupquery/CommandCompletion.cpp
+++ b/bin/bbackupquery/CommandCompletion.cpp
@@ -428,7 +428,7 @@ QueryCommandSpecification commands[] =
 {
 	{ "quit",	"",		Command_Quit, 	{} },
 	{ "exit",	"",		Command_Quit,	{} },
-	{ "list",	"rodIFtTash",	Command_List,	{CompleteRemoteDir} },
+	{ "list",	"aDFhiIrRsStTU",	Command_List,	{CompleteRemoteDir} },
 	{ "pwd",	"",		Command_pwd,	{} },
 	{ "cd",		"od",		Command_cd,	{CompleteRemoteDir} },
 	{ "lcd",	"",		Command_lcd,	{CompleteLocalDir} },
diff --git a/bin/bbackupquery/documentation.txt b/bin/bbackupquery/documentation.txt
index 214fe218..b16a6f7c 100644
--- a/bin/bbackupquery/documentation.txt
+++ b/bin/bbackupquery/documentation.txt
@@ -29,11 +29,11 @@ All directory names relative to a "current" directory, or from root if they
 start with '/'. The initial directory is always the root directory.
 
 
-> list [options] [directory-name]
+> ls [options] [directory-name]
 
 	List contents of current directory, or specified directory.
 	
-	-r -- recursively list all files
+	-R -- recursively list all files
 	-d -- list deleted files/directories
 	-o -- list old versions of files/directories
 	-I -- don't display object ID
@@ -45,13 +45,17 @@ start with '/'. The initial directory is always the root directory.
 	-s -- show file size in blocks used on server
 	      (only very approximate indication of size locally)
 	-h -- show file attributes hash
+	-D -- sort directories together with files (not dirs first)
+	-i -- sort by object ID (the old default)
+	-S -- sort by object size in blocks
+	-U -- don't sort the results (new default is to sort by name)
 
-ls can be used as an alias.
+list can be used as an alias.
 <
 
-> ls
+> list
 
-	Alias for 'list'. Type 'help list' for options.
+	Alias for 'ls'. Type 'help ls' for options.
 <
 
 > cd [options] <directory-name>