1 files changed, 39 insertions, 0 deletions
diff --git a/android/paths.go b/android/paths.go
index 5a41cf16f..0238a3fcf 100644
--- a/android/paths.go
+++ b/android/paths.go
@@ -542,6 +542,45 @@ func firstUniquePathsMap(list Paths) Paths {
 	return list[:k]
 }
 
+// FirstUniqueInstallPaths returns all unique elements of an InstallPaths, keeping the first copy of each.  It
+// modifies the InstallPaths slice contents in place, and returns a subslice of the original slice.
+func FirstUniqueInstallPaths(list InstallPaths) InstallPaths {
+	// 128 was chosen based on BenchmarkFirstUniquePaths results.
+	if len(list) > 128 {
+		return firstUniqueInstallPathsMap(list)
+	}
+	return firstUniqueInstallPathsList(list)
+}
+
+func firstUniqueInstallPathsList(list InstallPaths) InstallPaths {
+	k := 0
+outer:
+	for i := 0; i < len(list); i++ {
+		for j := 0; j < k; j++ {
+			if list[i] == list[j] {
+				continue outer
+			}
+		}
+		list[k] = list[i]
+		k++
+	}
+	return list[:k]
+}
+
+func firstUniqueInstallPathsMap(list InstallPaths) InstallPaths {
+	k := 0
+	seen := make(map[InstallPath]bool, len(list))
+	for i := 0; i < len(list); i++ {
+		if seen[list[i]] {
+			continue
+		}
+		seen[list[i]] = true
+		list[k] = list[i]
+		k++
+	}
+	return list[:k]
+}
+
 // LastUniquePaths returns all unique elements of a Paths, keeping the last copy of each.  It
 // modifies the Paths slice contents in place, and returns a subslice of the original slice.
 func LastUniquePaths(list Paths) Paths {