Guarding collisions in TimeSparseArray

TimeSparseArray - used to store UsageEvents - can keep at most one event
per millisecond, which can result in an event being replaced by another
event that occurred close enough that the system records it at the same
millisecond.

Test: atest android.app.usage.TimeSparseArrayTest

Fixes: 73832306
Change-Id: I860a101ab098f65d5c5832758832f43572865690

1 files changed, 22 insertions, 0 deletions

diff --git a/core/java/android/app/usage/TimeSparseArray.java b/core/java/android/app/usage/TimeSparseArray.java
index 7974fa706285..5764fa85579c 100644
--- a/core/java/android/app/usage/TimeSparseArray.java
+++ b/core/java/android/app/usage/TimeSparseArray.java
@@ -17,6 +17,7 @@
 package android.app.usage;
 
 import android.util.LongSparseArray;
+import android.util.Slog;
 
 /**
  * An array that indexes by a long timestamp, representing milliseconds since the epoch.
@@ -24,6 +25,8 @@ import android.util.LongSparseArray;
  * {@hide}
  */
 public class TimeSparseArray<E> extends LongSparseArray<E> {
+    private static final String TAG = TimeSparseArray.class.getSimpleName();
+
     public TimeSparseArray() {
         super();
     }
@@ -70,6 +73,25 @@ public class TimeSparseArray<E> extends LongSparseArray<E> {
     }
 
     /**
+     * {@inheritDoc}
+     *
+     * Overridden to ensure no collisions. The key (time in milliseconds) is incremented till an
+     * empty place is found.
+     */
+    @Override
+    public void put(long key, E value) {
+        final long origKey = key;
+        while (indexOfKey(key) >= 0) {
+            key++;
+        }
+        if (origKey != key) {
+            Slog.w(TAG, "Value " + value + " supposed to be inserted at " + origKey
+                    + " displaced to " + key);
+        }
+        super.put(key, value);
+    }
+
+    /**
      * Finds the index of the first element whose timestamp is less than or equal to
      * the given time.
      *