From 258fd85505e7c9b52394f18565148e03d17c1c32 Mon Sep 17 00:00:00 2001
From: Andres Mejia <amejia004@gmail.com>
Date: Sat, 9 Feb 2013 19:13:53 -0500
Subject: [PATCH] Add a convenience function to sort a list of strings. This is
 useful for sorting a list of filepaths to multivolume RARs for example.

---
 libarchive/archive.h                  |  4 ++
 libarchive/archive_util.c             | 42 ++++++++++++++++++
 libarchive/test/test_archive_string.c | 61 +++++++++++++++++++++++++++
 3 files changed, 107 insertions(+)

diff --git a/libarchive/archive.h b/libarchive/archive.h
index f56bc38e5..5f5c38159 100644
--- a/libarchive/archive.h
+++ b/libarchive/archive.h
@@ -1025,6 +1025,10 @@ __LA_DECL int	archive_match_include_gname(struct archive *, const char *);
 __LA_DECL int	archive_match_include_gname_w(struct archive *,
 		    const wchar_t *);
 
+/* Utility functions */
+/* Convenience function to sort a NULL terminated list of strings */
+__LA_DECL int archive_utility_string_sort(char **);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/libarchive/archive_util.c b/libarchive/archive_util.c
index 34d8081cb..57db5a654 100644
--- a/libarchive/archive_util.c
+++ b/libarchive/archive_util.c
@@ -54,6 +54,8 @@ __FBSDID("$FreeBSD: head/lib/libarchive/archive_util.c 201098 2009-12-28 02:58:1
 #define O_CLOEXEC	0
 #endif
 
+static int archive_utility_string_sort_helper(char **, unsigned int);
+
 /* Generic initialization of 'struct archive' objects. */
 int
 __archive_clean(struct archive *a)
@@ -499,3 +501,43 @@ __archive_ensure_cloexec_flag(int fd)
 	}
 #endif
 }
+
+/*
+ * Utility function to sort a group of strings using quicksort.
+ */
+static int
+archive_utility_string_sort_helper(char **strings, unsigned int n)
+{
+  unsigned int i, j, pivot;
+  char *tmp;
+
+  if (n <= 1)
+    return (ARCHIVE_OK);
+
+  pivot = 0;
+  for (i = 1; i < n; i++)
+  {
+    if (strcmp(strings[i], strings[pivot]) < 0)
+    {
+      tmp = strings[i];
+      for (j = i; j > pivot; j--)
+      {
+        strings[j] = strings[j - 1];
+      }
+      strings[pivot] = tmp;
+      pivot++;
+    }
+  }
+  archive_utility_string_sort_helper(strings, pivot + 1);
+  archive_utility_string_sort_helper(strings + pivot + 1, n - (pivot + 1));
+  return (ARCHIVE_OK);
+}
+
+int
+archive_utility_string_sort(char **strings)
+{
+  unsigned int size = 0;
+  while (strings[size] != NULL)
+    size++;
+  return archive_utility_string_sort_helper(strings, size);
+}
diff --git a/libarchive/test/test_archive_string.c b/libarchive/test/test_archive_string.c
index 54f68bdae..1abd2b21b 100644
--- a/libarchive/test/test_archive_string.c
+++ b/libarchive/test/test_archive_string.c
@@ -342,3 +342,64 @@ DEFINE_TEST(test_archive_string)
 	test_archive_string_copy();
 	test_archive_string_sprintf();
 }
+
+static const char *strings[] =
+{
+  "dir/path",
+  "dir/path2",
+  "dir/path3",
+  "dir/path4",
+  "dir/path5",
+  "dir/path6",
+  "dir/path7",
+  "dir/path8",
+  "dir/path9",
+  "dir/subdir/path",
+  "dir/subdir/path2",
+  "dir/subdir/path3",
+  "dir/subdir/path4",
+  "dir/subdir/path5",
+  "dir/subdir/path6",
+  "dir/subdir/path7",
+  "dir/subdir/path8",
+  "dir/subdir/path9",
+  "dir2/path",
+  "dir2/path2",
+  "dir2/path3",
+  "dir2/path4",
+  "dir2/path5",
+  "dir2/path6",
+  "dir2/path7",
+  "dir2/path8",
+  "dir2/path9",
+  NULL
+};
+
+DEFINE_TEST(test_archive_string_sort)
+{
+  unsigned int i, j, size;
+  char **test_strings, *tmp;
+
+  srand(time(NULL));
+  size = sizeof(strings) / sizeof(char *);
+  assert((test_strings = (char **)calloc(1, sizeof(strings))) != NULL);
+  for (i = 0; i < size; i++)
+    test_strings[i] = strings[i];
+
+  /* Shuffle the test strings */
+  for (i = 0; i < (size - 1); i++)
+  {
+    j = rand() % ((size - 1) - i);
+    j += i;
+    tmp = test_strings[i];
+    test_strings[i] = test_strings[j];
+    test_strings[j] = tmp;
+  }
+
+  /* Sort and test */
+  assertEqualInt(ARCHIVE_OK, archive_utility_string_sort(test_strings));
+  for (i = 0; i < (size - 1); i++)
+    assertEqualString(test_strings[i], strings[i]);
+
+  free(test_strings);
+}
-- 
2.47.2