Speed up Uri.getQueryParameter by allocating less.

Sample hierarchial URL, from my ContactsProvider test case:

content://com.android.contacts/data?account_name=braddroid%40gmail.com&account_type=com.google.GAIA&caller_is_syncadapter=true

Without this patch:  (fetching the "account_name" parameter)

10000 iters: 0.5293 ms average
10000 iters: 0.5119 ms average
10000 iters: 0.5158 ms average

With this patch, rewriting it to not allocate memory (no implicit
StringBuilder), but still no caching:

1) when it needs to decode something (i.e account_name above;
   allocates memory)

  50000 iters: 0.28724 ms average
  50000 iters: 0.31774 ms average
  50000 iters: 0.28764 ms average

2) when it doesn't need to decode (and thus allocate memory,
   i.e. account_type above)

  50000 iters: 0.0954 ms average
  50000 iters: 0.09124 ms average
  50000 iters: 0.09088 ms average

2 files changed, 54 insertions, 36 deletions

diff --git a/core/java/android/net/Uri.java b/core/java/android/net/Uri.java
index 9a1b65d..f2ea539 100644
--- a/core/java/android/net/Uri.java
+++ b/core/java/android/net/Uri.java
@@ -1567,51 +1567,40 @@ public abstract class Uri implements Parcelable, Comparable<Uri> {
         if (isOpaque()) {
             throw new UnsupportedOperationException(NOT_HIERARCHICAL);
         }
+        if (key == null) {
+          throw new NullPointerException("key");
+        }
 
-        String query = getEncodedQuery();
-
+        final String query = getEncodedQuery();
         if (query == null) {
             return null;
         }
 
-        String encodedKey;
-        try {
-            encodedKey = URLEncoder.encode(key, DEFAULT_ENCODING);
-        } catch (UnsupportedEncodingException e) {
-            throw new AssertionError(e);
-        }
-
-        String prefix = encodedKey + "=";
+        final String encodedKey = encode(key, null);
+        final int encodedKeyLength = encodedKey.length();
 
-        if (query.length() < prefix.length()) {
-            return null;
-        }
+        int encodedKeySearchIndex = 0;
+        final int encodedKeySearchEnd = query.length() - (encodedKeyLength + 1);
 
-        int start;
-        if (query.startsWith(prefix)) {
-            // It's the first parameter.
-            start = prefix.length();
-        } else {
-            // It must be later in the query string.
-            prefix = "&" + prefix;
-            start = query.indexOf(prefix);
-
-            if (start == -1) {
-                // Not found.
-                return null;
+        while (encodedKeySearchIndex <= encodedKeySearchEnd) {
+            int keyIndex = query.indexOf(encodedKey, encodedKeySearchIndex);
+            if (keyIndex == -1) {
+                break;
+            }
+            final int equalsIndex = keyIndex + encodedKeyLength;
+            if (query.charAt(equalsIndex) != '=') {
+                encodedKeySearchIndex = equalsIndex + 1;
+                continue;
+            }
+            if (keyIndex == 0 || query.charAt(keyIndex - 1) == '&') {
+                int end = query.indexOf('&', equalsIndex);
+                if (end == -1) {
+                    end = query.length();
+                }
+                return decode(query.substring(equalsIndex + 1, end));
             }
-
-            start += prefix.length();
-        }
-
-        // Find end of value.
-        int end = query.indexOf('&', start);
-        if (end == -1) {
-            end = query.length();
         }
-
-        String value = query.substring(start, end);
-        return decode(value);
+        return null;
     }
 
     /** Identifies a null parcelled Uri. */
diff --git a/tests/AndroidTests/src/com/android/unit_tests/UriTest.java b/tests/AndroidTests/src/com/android/unit_tests/UriTest.java
index d17e2c3..42066d9 100644
--- a/tests/AndroidTests/src/com/android/unit_tests/UriTest.java
+++ b/tests/AndroidTests/src/com/android/unit_tests/UriTest.java
@@ -541,4 +541,33 @@ public class UriTest extends TestCase {
         assertEquals(nestedUrl,
                 Uri.decode(uri.getQueryParameters("nested").get(0)));
     }
+
+    public void testGetQueryParameterEdgeCases() {
+        Uri uri;
+
+        // key at beginning of URL
+        uri = Uri.parse("http://test/").buildUpon()
+            .appendQueryParameter("key", "a b")
+            .appendQueryParameter("keya", "c d")
+            .appendQueryParameter("bkey", "e f")
+            .build();
+        assertEquals("a b", uri.getQueryParameter("key"));
+
+        // key in middle of URL
+        uri = Uri.parse("http://test/").buildUpon()
+            .appendQueryParameter("akeyb", "a b")
+            .appendQueryParameter("keya", "c d")
+            .appendQueryParameter("key", "e f")
+            .appendQueryParameter("bkey", "g h")
+            .build();
+        assertEquals("e f", uri.getQueryParameter("key"));
+
+        // key at end of URL
+        uri = Uri.parse("http://test/").buildUpon()
+            .appendQueryParameter("akeyb", "a b")
+            .appendQueryParameter("keya", "c d")
+            .appendQueryParameter("key", "y z")
+            .build();
+        assertEquals("y z", uri.getQueryParameter("key"));
+    }
 }