From f9345e93db82adf8eaa2afc731933462d7876b13 Mon Sep 17 00:00:00 2001 From: Andreas Gampe Date: Wed, 4 Mar 2015 17:14:10 -0800 Subject: Frameworks/base: Add removeAll for ArraySet Add a simple ArraySet.removeAll(ArraySet) method. This avoids two allocations, a MapCollections helper and an Iterator object, over the removeAll(Collection) code. KeySetManagerService heavily calls removeAll during boot (about 9K times in AOSP). This reduces GC stress and optimizes the removal (about half the time the removed collection has only one element). The removal method in KeySetManagerService is also done under a lock, so that it gates parallelization efforts in PackageManagerService. Bug: 19498314 Change-Id: Ib0e483adfd09831cd66ab19a820ebf6544a2b66f --- core/java/android/util/ArraySet.java | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'core/java/android/util') diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java index 423e48b..3214b22 100644 --- a/core/java/android/util/ArraySet.java +++ b/core/java/android/util/ArraySet.java @@ -468,6 +468,26 @@ public final class ArraySet implements Collection, Set { } /** + * Perform a {@link #remove(Object)} of all values in array + * @param array The array whose contents are to be removed. + */ + public boolean removeAll(ArraySet array) { + // TODO: If array is sufficiently large, a marking approach might be beneficial. In a first + // pass, use the property that the sets are sorted by hash to make this linear passes + // (except for hash collisions, which means worst case still n*m), then do one + // collection pass into a new array. This avoids binary searches and excessive memcpy. + final int N = array.mSize; + + // Note: ArraySet does not make thread-safety guarantees. So instead of OR-ing together all + // the single results, compare size before and after. + final int originalSize = mSize; + for (int i = 0; i < N; i++) { + remove(array.valueAt(i)); + } + return originalSize != mSize; + } + + /** * Return the number of items in this array map. */ @Override -- cgit v1.1