Reduce memory usage of GpsStatus objects.

A simple GpsStatus object uses 9K of space, given that it initializes an array
of 255 GpsSatellite objects.
This change reduces the memory footprint in the average case, and keeps the
semantics of the API and its GpsSatellite sibling objects without any changes.
In a best case scenario it brings the memory usage per object to 1K.
It's likely in most cases that only 20-50 satellites will be in view. So the
usage should not exceeed half of the original memory usage.
It was considered to keep the internal array but a SparseArray provided bigger
memory savings in the test scenario of ~700B.

Change-Id: Ie2d2144d776a74d4904a08c0d6c5aec6d3bba7cc

3 files changed, 435 insertions, 36 deletions

diff --git a/location/java/android/location/GpsSatellite.java b/location/java/android/location/GpsSatellite.java
index 17af4a6..820f574 100644
--- a/location/java/android/location/GpsSatellite.java
+++ b/location/java/android/location/GpsSatellite.java
@@ -40,13 +40,17 @@ public final class GpsSatellite {
      * cached GpsStatus instance to the client's copy.
      */
     void setStatus(GpsSatellite satellite) {
-        mValid = satellite.mValid;
-        mHasEphemeris = satellite.mHasEphemeris;
-        mHasAlmanac = satellite.mHasAlmanac;
-        mUsedInFix = satellite.mUsedInFix;
-        mSnr = satellite.mSnr;
-        mElevation = satellite.mElevation;
-        mAzimuth = satellite.mAzimuth;
+        if (satellite == null) {
+            mValid = false;
+        } else {
+            mValid = satellite.mValid;
+            mHasEphemeris = satellite.mHasEphemeris;
+            mHasAlmanac = satellite.mHasAlmanac;
+            mUsedInFix = satellite.mUsedInFix;
+            mSnr = satellite.mSnr;
+            mElevation = satellite.mElevation;
+            mAzimuth = satellite.mAzimuth;
+        }
     }
 
     /**
diff --git a/location/java/android/location/GpsStatus.java b/location/java/android/location/GpsStatus.java
index 4af55a6..323f326 100644
--- a/location/java/android/location/GpsStatus.java
+++ b/location/java/android/location/GpsStatus.java
@@ -16,6 +16,8 @@
 
 package android.location;
 
+import android.util.SparseArray;
+
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 
@@ -29,20 +31,24 @@ public final class GpsStatus {
 
     /* These package private values are modified by the LocationManager class */
     private int mTimeToFirstFix;
-    private GpsSatellite mSatellites[] = new GpsSatellite[NUM_SATELLITES];
+    private final SparseArray<GpsSatellite> mSatellites = new SparseArray<>();
 
     private final class SatelliteIterator implements Iterator<GpsSatellite> {
 
-        private GpsSatellite[] mSatellites;
-        int mIndex = 0;
+        private final SparseArray<GpsSatellite> mSatellites;
+        private final int mSatellitesCount;
+
+        private int mIndex = 0;
 
-        SatelliteIterator(GpsSatellite[] satellites) {
+        SatelliteIterator(SparseArray<GpsSatellite> satellites) {
             mSatellites = satellites;
+            mSatellitesCount = satellites.size();
         }
 
         public boolean hasNext() {
-            for (int i = mIndex; i < mSatellites.length; i++) {
-                if (mSatellites[i].mValid) {
+            for (; mIndex < mSatellitesCount; ++mIndex) {
+                GpsSatellite satellite = mSatellites.valueAt(mIndex);
+                if (satellite.mValid) {
                     return true;
                 }
             }
@@ -50,8 +56,9 @@ public final class GpsStatus {
         }
 
         public GpsSatellite next() {
-            while (mIndex < mSatellites.length) {
-                GpsSatellite satellite = mSatellites[mIndex++];
+            while (mIndex < mSatellitesCount) {
+                GpsSatellite satellite = mSatellites.valueAt(mIndex);
+                ++mIndex;
                 if (satellite.mValid) {
                     return satellite;
                 }
@@ -106,7 +113,7 @@ public final class GpsStatus {
          * <li> {@link GpsStatus#GPS_EVENT_SATELLITE_STATUS}
          * </ul>
          *
-         * When this method is called, the client should call 
+         * When this method is called, the client should call
          * {@link LocationManager#getGpsStatus} to get additional
          * status information.
          *
@@ -127,11 +134,8 @@ public final class GpsStatus {
         void onNmeaReceived(long timestamp, String nmea);
     }
 
-    GpsStatus() {
-        for (int i = 0; i < mSatellites.length; i++) {
-            mSatellites[i] = new GpsSatellite(i + 1);
-        }
-    }
+    // For API-compat a public ctor() is not available
+    GpsStatus() {}
 
     /**
      * Used internally within {@link LocationManager} to copy GPS status
@@ -141,18 +145,17 @@ public final class GpsStatus {
     synchronized void setStatus(int svCount, int[] prns, float[] snrs,
             float[] elevations, float[] azimuths, int ephemerisMask,
             int almanacMask, int usedInFixMask) {
-        int i;
+        clearSatellites();
+        for (int i = 0; i < svCount; i++) {
+            int prn = prns[i];
+            int prnShift = (1 << (prn - 1));
+            if (prn > 0 && prn <= NUM_SATELLITES) {
+                GpsSatellite satellite = mSatellites.get(prn);
+                if (satellite == null) {
+                    satellite = new GpsSatellite(prn);
+                    mSatellites.put(prn, satellite);
+                }
 
-        for (i = 0; i < mSatellites.length; i++) {
-            mSatellites[i].mValid = false;
-        }
-        
-        for (i = 0; i < svCount; i++) {
-            int prn = prns[i] - 1;
-            int prnShift = (1 << prn);
-            if (prn >= 0 && prn < mSatellites.length) {
-                GpsSatellite satellite = mSatellites[prn];
-    
                 satellite.mValid = true;
                 satellite.mSnr = snrs[i];
                 satellite.mElevation = elevations[i];
@@ -172,10 +175,38 @@ public final class GpsStatus {
      */
     void setStatus(GpsStatus status) {
         mTimeToFirstFix = status.getTimeToFirstFix();
+        clearSatellites();
+
+        SparseArray<GpsSatellite> otherSatellites = status.mSatellites;
+        int otherSatellitesCount = otherSatellites.size();
+        int satelliteIndex = 0;
+        // merge both sparse arrays, note that we have already invalidated the elements in the
+        // receiver array
+        for (int i = 0; i < otherSatellitesCount; ++i) {
+            GpsSatellite otherSatellite = otherSatellites.valueAt(i);
+            int otherSatellitePrn = otherSatellite.getPrn();
+
+            int satellitesCount = mSatellites.size();
+            while (satelliteIndex < satellitesCount
+                    && mSatellites.valueAt(satelliteIndex).getPrn() < otherSatellitePrn) {
+                ++satelliteIndex;
+            }
 
-        for (int i = 0; i < mSatellites.length; i++) {
-            mSatellites[i].setStatus(status.mSatellites[i]);
-        } 
+            if (satelliteIndex < mSatellites.size()) {
+                GpsSatellite satellite = mSatellites.valueAt(satelliteIndex);
+                if (satellite.getPrn() == otherSatellitePrn) {
+                    satellite.setStatus(otherSatellite);
+                } else {
+                    satellite = new GpsSatellite(otherSatellitePrn);
+                    satellite.setStatus(otherSatellite);
+                    mSatellites.put(otherSatellitePrn, satellite);
+                }
+            } else {
+                GpsSatellite satellite = new GpsSatellite(otherSatellitePrn);
+                satellite.setStatus(otherSatellite);
+                mSatellites.append(otherSatellitePrn, satellite);
+            }
+        }
     }
 
     void setTimeToFirstFix(int ttff) {
@@ -183,7 +214,7 @@ public final class GpsStatus {
     }
 
     /**
-     * Returns the time required to receive the first fix since the most recent 
+     * Returns the time required to receive the first fix since the most recent
      * restart of the GPS engine.
      *
      * @return time to first fix in milliseconds
@@ -211,4 +242,12 @@ public final class GpsStatus {
     public int getMaxSatellites() {
         return NUM_SATELLITES;
     }
+
+    private void clearSatellites() {
+        int satellitesCount = mSatellites.size();
+        for (int i = 0; i < satellitesCount; i++) {
+            GpsSatellite satellite = mSatellites.valueAt(i);
+            satellite.mValid = false;
+        }
+    }
 }
diff --git a/location/tests/locationtests/src/android/location/GpsStatusTest.java b/location/tests/locationtests/src/android/location/GpsStatusTest.java
new file mode 100644
index 0000000..4808faf
--- /dev/null
+++ b/location/tests/locationtests/src/android/location/GpsStatusTest.java
@@ -0,0 +1,356 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package android.location;
+
+import junit.framework.TestCase;
+
+import android.test.suitebuilder.annotation.SmallTest;
+
+import java.lang.reflect.Constructor;
+import java.lang.reflect.Method;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Random;
+import java.util.Set;
+
+/**
+ * Unit tests for {@link GpsStatus}.
+ */
+@SmallTest
+public class GpsStatusTest extends TestCase {
+
+    private static final int MAX_VALUE = 250;
+
+    private final Random mRandom = new Random();
+
+    private GpsStatus mStatus;
+    private int mCount;
+    private int[] mPrns;
+    private float[] mSnrs;
+    private float[] mElevations;
+    private float[] mAzimuth;
+    private int mEphemerisMask;
+    private int mAlmanacMask;
+    private int mUsedInFixMask;
+
+    public void setUp() throws Exception {
+        super.setUp();
+        mStatus = createGpsStatus();
+        generateSatellitesData(generateInt());
+    }
+
+    public void testEmptyGpsStatus() throws Exception {
+        verifyIsEmpty(mStatus);
+    }
+
+    public void testGpsStatusIterator() throws Exception {
+        generateSatellitesData(2);
+        setSatellites(mStatus);
+        Iterator<GpsSatellite> iterator = mStatus.getSatellites().iterator();
+        assertTrue("hasNext(1)", iterator.hasNext());
+        assertTrue("hasNext(1) does not overflow", iterator.hasNext());
+        GpsSatellite satellite1 = iterator.next();
+        assertNotNull("satellite", satellite1);
+        assertTrue("hasNext(2)", iterator.hasNext());
+        assertTrue("hasNext(2) does not overflow", iterator.hasNext());
+        GpsSatellite satellite2 = iterator.next();
+        assertNotNull("satellite", satellite2);
+        assertFalse("hasNext() no elements", iterator.hasNext());
+    }
+
+    public void testTtff() throws Exception {
+        int testTtff = generateInt();
+        set(mStatus, testTtff);
+        verifyTtff(mStatus, testTtff);
+    }
+
+    public void testCopyTtff() throws Exception {
+        int testTtff = generateInt();
+        verifyTtff(mStatus, 0);
+
+        GpsStatus otherStatus = createGpsStatus();
+        set(otherStatus, testTtff);
+        verifyTtff(otherStatus, testTtff);
+
+        set(mStatus, otherStatus);
+        verifyTtff(mStatus, testTtff);
+    }
+
+    public void testSetSatellites() throws Exception {
+        setSatellites(mStatus);
+        verifySatellites(mStatus);
+    }
+
+    public void testCopySatellites() throws Exception {
+        verifyIsEmpty(mStatus);
+
+        GpsStatus otherStatus = createGpsStatus();
+        setSatellites(otherStatus);
+        verifySatellites(otherStatus);
+
+        set(mStatus, otherStatus);
+        verifySatellites(mStatus);
+    }
+
+    public void testOverrideSatellites() throws Exception {
+        setSatellites(mStatus);
+        verifySatellites(mStatus);
+
+        GpsStatus otherStatus = createGpsStatus();
+        generateSatellitesData(mCount, true /* reusePrns */);
+        setSatellites(otherStatus);
+        verifySatellites(otherStatus);
+
+        set(mStatus, otherStatus);
+        verifySatellites(mStatus);
+    }
+
+    public void testAddSatellites() throws Exception {
+        int count = 10;
+        generateSatellitesData(count);
+        setSatellites(mStatus);
+        verifySatellites(mStatus);
+
+        GpsStatus otherStatus = createGpsStatus();
+        generateSatellitesData(count);
+        setSatellites(otherStatus);
+        verifySatellites(otherStatus);
+
+        set(mStatus, otherStatus);
+        verifySatellites(mStatus);
+    }
+
+    public void testAddMoreSatellites() throws Exception {
+        int count = 25;
+        generateSatellitesData(count);
+        setSatellites(mStatus);
+        verifySatellites(mStatus);
+
+        GpsStatus otherStatus = createGpsStatus();
+        generateSatellitesData(count * 2);
+        setSatellites(otherStatus);
+        verifySatellites(otherStatus);
+
+        set(mStatus, otherStatus);
+        verifySatellites(mStatus);
+    }
+
+    public void testAddLessSatellites() throws Exception {
+        int count = 25;
+        generateSatellitesData(count * 2);
+        setSatellites(mStatus);
+        verifySatellites(mStatus);
+
+        GpsStatus otherStatus = createGpsStatus();
+        generateSatellitesData(count);
+        setSatellites(otherStatus);
+        verifySatellites(otherStatus);
+
+        set(mStatus, otherStatus);
+        verifySatellites(mStatus);
+    }
+
+    private static void verifyIsEmpty(GpsStatus status) {
+        verifySatelliteCount(status, 0);
+        verifyTtff(status, 0);
+    }
+
+    private static void verifySatelliteCount(GpsStatus status, int expectedCount) {
+        int satellites = 0;
+        for (GpsSatellite s : status.getSatellites()) {
+            ++satellites;
+        }
+        assertEquals("GpsStatus::SatelliteCount", expectedCount, satellites);
+    }
+
+    private void verifySatellites(GpsStatus status) {
+        verifySatelliteCount(status, mCount);
+        verifySatellites(status, mCount, mPrns, mSnrs, mElevations, mAzimuth, mEphemerisMask,
+                mAlmanacMask, mUsedInFixMask);
+    }
+
+    private static void verifySatellites(
+            GpsStatus status,
+            int count,
+            int[] prns,
+            float[] snrs,
+            float[] elevations,
+            float[] azimuth,
+            int ephemerisMask,
+            int almanacMask,
+            int usedInFixMask) {
+        for (int i = 0; i < count; ++i) {
+            int prn = prns[i];
+            GpsSatellite satellite = getSatellite(status, prn);
+            assertNotNull(getSatelliteAssertInfo(i, prn, "non-null"), satellite);
+            assertEquals(getSatelliteAssertInfo(i, prn, "Snr"), snrs[i], satellite.getSnr());
+            assertEquals(
+                    getSatelliteAssertInfo(i, prn, "Elevation"),
+                    elevations[i],
+                    satellite.getElevation());
+            assertEquals(
+                    getSatelliteAssertInfo(i, prn, "Azimuth"),
+                    azimuth[i],
+                    satellite.getAzimuth());
+            int prnShift = 1 << (prn - 1);
+            assertEquals(
+                    getSatelliteAssertInfo(i, prn, "ephemeris"),
+                    (ephemerisMask & prnShift) != 0,
+                    satellite.hasEphemeris());
+            assertEquals(
+                    getSatelliteAssertInfo(i, prn, "almanac"),
+                    (almanacMask & prnShift) != 0,
+                    satellite.hasAlmanac());
+            assertEquals(
+                    getSatelliteAssertInfo(i, prn, "usedInFix"),
+                    (usedInFixMask & prnShift) != 0,
+                    satellite.usedInFix());
+        }
+    }
+
+    private static void verifyTtff(GpsStatus status, int expectedTtff) {
+        assertEquals("GpsStatus::TTFF", expectedTtff, status.getTimeToFirstFix());
+    }
+
+    private static GpsStatus createGpsStatus() throws Exception {
+        Constructor<GpsStatus>  ctor = GpsStatus.class.getDeclaredConstructor();
+        ctor.setAccessible(true);
+        return ctor.newInstance();
+    }
+
+    private static void set(GpsStatus status, int ttff) throws Exception {
+        Class<?> statusClass = status.getClass();
+        Method setTtff = statusClass.getDeclaredMethod("setTimeToFirstFix", Integer.TYPE);
+        setTtff.setAccessible(true);
+        setTtff.invoke(status, ttff);
+    }
+
+    private static void set(GpsStatus status, GpsStatus statusToSet) throws Exception {
+        Class<?> statusClass = status.getClass();
+        Method setStatus = statusClass.getDeclaredMethod("setStatus", statusClass);
+        setStatus.setAccessible(true);
+        setStatus.invoke(status, statusToSet);
+    }
+
+    private void setSatellites(GpsStatus status) throws Exception {
+        set(status, mCount, mPrns, mSnrs, mElevations, mAzimuth, mEphemerisMask, mAlmanacMask,
+                mUsedInFixMask);
+    }
+
+    private static void set(
+            GpsStatus status,
+            int count,
+            int[] prns,
+            float[] snrs,
+            float[] elevations,
+            float[] azimuth,
+            int ephemerisMask,
+            int almanacMask,
+            int usedInFixMask) throws Exception {
+        Class<?> statusClass = status.getClass();
+        Class<?> intClass = Integer.TYPE;
+        Class<?> floatArrayClass = Class.forName("[F");
+        Method setStatus = statusClass.getDeclaredMethod(
+                "setStatus",
+                intClass,
+                Class.forName("[I"),
+                floatArrayClass,
+                floatArrayClass,
+                floatArrayClass,
+                intClass,
+                intClass,
+                intClass);
+        setStatus.setAccessible(true);
+        setStatus.invoke(
+                status,
+                count,
+                prns,
+                snrs,
+                elevations,
+                azimuth,
+                ephemerisMask,
+                almanacMask,
+                usedInFixMask);
+    }
+
+    private int generateInt() {
+        return mRandom.nextInt(MAX_VALUE) + 1;
+    }
+
+    private int[] generateIntArray(int count) {
+        Set<Integer> generatedPrns = new HashSet<>();
+        int[] array = new int[count];
+        for(int i = 0; i < count; ++i) {
+            int generated;
+            do {
+                generated = generateInt();
+            } while (generatedPrns.contains(generated));
+            array[i] = generated;
+            generatedPrns.add(generated);
+        }
+        return array;
+    }
+
+    private float[] generateFloatArray(int count) {
+        float[] array = new float[count];
+        for(int i = 0; i < count; ++i) {
+            array[i] = generateInt();
+        }
+        return array;
+    }
+
+    private int generateMask(int[] prns) {
+        int mask = 0;
+        int prnsLength = prns.length;
+        for (int i = 0; i < prnsLength; ++i) {
+            if (mRandom.nextBoolean()) {
+                mask |= 1 << (prns[i] - 1);
+            }
+        }
+        return mask;
+    }
+
+    private void generateSatellitesData(int count) {
+        generateSatellitesData(count, false /* reusePrns */);
+    }
+
+    private void generateSatellitesData(int count, boolean reusePrns) {
+        mCount = count;
+        if (!reusePrns) {
+            mPrns = generateIntArray(count);
+        }
+        mSnrs = generateFloatArray(count);
+        mElevations = generateFloatArray(count);
+        mAzimuth = generateFloatArray(count);
+        mEphemerisMask = generateMask(mPrns);
+        mAlmanacMask = generateMask(mPrns);
+        mUsedInFixMask = generateMask(mPrns);
+    }
+
+    private static GpsSatellite getSatellite(GpsStatus status, int prn) {
+        for (GpsSatellite satellite : status.getSatellites()) {
+            if (satellite.getPrn() == prn) {
+                return satellite;
+            }
+        }
+        return null;
+    }
+
+    private static String getSatelliteAssertInfo(int index, int prn, String param) {
+        return String.format("Satellite::%s [i=%d, prn=%d]", param, index, prn);
+    }
+}