Add searchable android.DirectorySortedPaths
Add an android.DirectorySortedPaths that stores paths sorted such
that all paths in a directory including subdirectories are in a
contiguous subslice. This will allow efficient O(log(N)) finding
of all paths in a directory using a binary search on the directory
prefix.
Test: TestDirectorySortedPaths in paths_test.go
Change-Id: I5a06a89351ae06e88c06526be54a6b79075361b7
diff --git a/android/paths.go b/android/paths.go
index d6a1c66..4adaa2d 100644
--- a/android/paths.go
+++ b/android/paths.go
@@ -18,6 +18,7 @@
"fmt"
"path/filepath"
"reflect"
+ "sort"
"strings"
"github.com/google/blueprint"
@@ -380,6 +381,38 @@
return ret
}
+// DirectorySortedPaths is a slice of paths that are sorted such that all files in a directory
+// (including subdirectories) are in a contiguous subslice of the list, and can be found in
+// O(log(N)) time using a binary search on the directory prefix.
+type DirectorySortedPaths Paths
+
+func PathsToDirectorySortedPaths(paths Paths) DirectorySortedPaths {
+ ret := append(DirectorySortedPaths(nil), paths...)
+ sort.Slice(ret, func(i, j int) bool {
+ return ret[i].String() < ret[j].String()
+ })
+ return ret
+}
+
+// PathsInDirectory returns a subslice of the DirectorySortedPaths as a Paths that contains all entries
+// that are in the specified directory and its subdirectories.
+func (p DirectorySortedPaths) PathsInDirectory(dir string) Paths {
+ prefix := filepath.Clean(dir) + "/"
+ start := sort.Search(len(p), func(i int) bool {
+ return prefix < p[i].String()
+ })
+
+ ret := p[start:]
+
+ end := sort.Search(len(ret), func(i int) bool {
+ return !strings.HasPrefix(ret[i].String(), prefix)
+ })
+
+ ret = ret[:end]
+
+ return Paths(ret)
+}
+
// WritablePaths is a slice of WritablePaths, used for multiple outputs.
type WritablePaths []WritablePath
diff --git a/android/paths_test.go b/android/paths_test.go
index 248f4d4..82ae4dc 100644
--- a/android/paths_test.go
+++ b/android/paths_test.go
@@ -340,3 +340,75 @@
})
}
}
+
+func TestDirectorySortedPaths(t *testing.T) {
+ makePaths := func() Paths {
+ return Paths{
+ PathForTesting("a.txt"),
+ PathForTesting("a/txt"),
+ PathForTesting("a/b/c"),
+ PathForTesting("a/b/d"),
+ PathForTesting("b"),
+ PathForTesting("b/b.txt"),
+ PathForTesting("a/a.txt"),
+ }
+ }
+
+ expected := []string{
+ "a.txt",
+ "a/a.txt",
+ "a/b/c",
+ "a/b/d",
+ "a/txt",
+ "b",
+ "b/b.txt",
+ }
+
+ paths := makePaths()
+ reversePaths := make(Paths, len(paths))
+ for i, v := range paths {
+ reversePaths[len(paths)-i-1] = v
+ }
+
+ sortedPaths := PathsToDirectorySortedPaths(paths)
+ reverseSortedPaths := PathsToDirectorySortedPaths(reversePaths)
+
+ if !reflect.DeepEqual(Paths(sortedPaths).Strings(), expected) {
+ t.Fatalf("sorted paths:\n %#v\n != \n %#v", paths.Strings(), expected)
+ }
+
+ if !reflect.DeepEqual(Paths(reverseSortedPaths).Strings(), expected) {
+ t.Fatalf("sorted reversed paths:\n %#v\n !=\n %#v", reversePaths.Strings(), expected)
+ }
+
+ expectedA := []string{
+ "a/a.txt",
+ "a/b/c",
+ "a/b/d",
+ "a/txt",
+ }
+
+ inA := sortedPaths.PathsInDirectory("a")
+ if !reflect.DeepEqual(inA.Strings(), expectedA) {
+ t.Errorf("FilesInDirectory(a):\n %#v\n != \n %#v", inA.Strings(), expectedA)
+ }
+
+ expectedA_B := []string{
+ "a/b/c",
+ "a/b/d",
+ }
+
+ inA_B := sortedPaths.PathsInDirectory("a/b")
+ if !reflect.DeepEqual(inA_B.Strings(), expectedA_B) {
+ t.Errorf("FilesInDirectory(a/b):\n %#v\n != \n %#v", inA_B.Strings(), expectedA_B)
+ }
+
+ expectedB := []string{
+ "b/b.txt",
+ }
+
+ inB := sortedPaths.PathsInDirectory("b")
+ if !reflect.DeepEqual(inB.Strings(), expectedB) {
+ t.Errorf("FilesInDirectory(b):\n %#v\n != \n %#v", inA.Strings(), expectedA)
+ }
+}