1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License
15 */
16
17package com.android.providers.contacts;
18
19import android.content.Context;
20import android.content.SharedPreferences;
21import android.database.Cursor;
22import android.net.Uri;
23import android.os.Bundle;
24import android.preference.PreferenceManager;
25import android.provider.ContactsContract.ContactCounts;
26import android.text.TextUtils;
27import android.util.Log;
28
29import com.google.android.collect.Maps;
30import com.google.common.annotations.VisibleForTesting;
31
32import java.util.Map;
33import java.util.regex.Pattern;
34
35/**
36 * Cache for the "fast scrolling index".
37 *
38 * It's a cache from "keys" and "bundles" (see {@link #mCache} for what they are).  The cache
39 * content is also persisted in the shared preferences, so it'll survive even if the process
40 * is killed or the device reboots.
41 *
42 * All the content will be invalidated when the provider detects an operation that could potentially
43 * change the index.
44 *
45 * There's no maximum number for cached entries.  It's okay because we store keys and values in
46 * a compact form in both the in-memory cache and the preferences.  Also the query in question
47 * (the query for contact lists) has relatively low number of variations.
48 *
49 * This class is thread-safe.
50 */
51public class FastScrollingIndexCache {
52    private static final String TAG = "LetterCountCache";
53
54    @VisibleForTesting
55    static final String PREFERENCE_KEY = "LetterCountCache";
56
57    /**
58     * Separator used for in-memory structure.
59     */
60    private static final String SEPARATOR = "\u0001";
61    private static final Pattern SEPARATOR_PATTERN = Pattern.compile(SEPARATOR);
62
63    /**
64     * Separator used for serializing values for preferences.
65     */
66    private static final String SAVE_SEPARATOR = "\u0002";
67    private static final Pattern SAVE_SEPARATOR_PATTERN = Pattern.compile(SAVE_SEPARATOR);
68
69    private final SharedPreferences mPrefs;
70
71    private boolean mPreferenceLoaded;
72
73    /**
74     * In-memory cache.
75     *
76     * It's essentially a map from keys, which are query parameters passed to {@link #get}, to
77     * values, which are {@link Bundle}s that will be appended to a {@link Cursor} as extras.
78     *
79     * However, in order to save memory, we store stringified keys and values in the cache.
80     * Key strings are generated by {@link #buildCacheKey} and values are generated by
81     * {@link #buildCacheValue}.
82     *
83     * We store those strings joined with {@link #SAVE_SEPARATOR} as the separator when saving
84     * to shared preferences.
85     */
86    private final Map<String, String> mCache = Maps.newHashMap();
87
88    public FastScrollingIndexCache(Context context) {
89        this(PreferenceManager.getDefaultSharedPreferences(context));
90
91        // At this point, the SharedPreferences might just have been generated and may still be
92        // loading from the file, in which case loading from the preferences would be blocked.
93        // To avoid that, we load lazily.
94    }
95
96    @VisibleForTesting
97    FastScrollingIndexCache(SharedPreferences prefs) {
98        mPrefs = prefs;
99    }
100
101    /**
102     * Append a {@link String} to a {@link StringBuilder}.
103     *
104     * Unlike the original {@link StringBuilder#append}, it does *not* append the string "null" if
105     * {@code value} is null.
106     */
107    private static void appendIfNotNull(StringBuilder sb, Object value) {
108        if (value != null) {
109            sb.append(value.toString());
110        }
111    }
112
113    private static String buildCacheKey(Uri queryUri, String selection, String[] selectionArgs,
114            String sortOrder, String countExpression) {
115        final StringBuilder sb = new StringBuilder();
116
117        appendIfNotNull(sb, queryUri);
118        appendIfNotNull(sb, SEPARATOR);
119        appendIfNotNull(sb, selection);
120        appendIfNotNull(sb, SEPARATOR);
121        appendIfNotNull(sb, sortOrder);
122        appendIfNotNull(sb, SEPARATOR);
123        appendIfNotNull(sb, countExpression);
124
125        if (selectionArgs != null) {
126            for (int i = 0; i < selectionArgs.length; i++) {
127                appendIfNotNull(sb, SEPARATOR);
128                appendIfNotNull(sb, selectionArgs[i]);
129            }
130        }
131        return sb.toString();
132    }
133
134    @VisibleForTesting
135    static String buildCacheValue(String[] titles, int[] counts) {
136        final StringBuilder sb = new StringBuilder();
137
138        for (int i = 0; i < titles.length; i++) {
139            if (i > 0) {
140                appendIfNotNull(sb, SEPARATOR);
141            }
142            appendIfNotNull(sb, titles[i]);
143            appendIfNotNull(sb, SEPARATOR);
144            appendIfNotNull(sb, Integer.toString(counts[i]));
145        }
146
147        return sb.toString();
148    }
149
150    /**
151     * Creates and returns a {@link Bundle} that is appended to a {@link Cursor} as extras.
152     */
153    public static final Bundle buildExtraBundle(String[] titles, int[] counts) {
154        Bundle bundle = new Bundle();
155        bundle.putStringArray(ContactCounts.EXTRA_ADDRESS_BOOK_INDEX_TITLES, titles);
156        bundle.putIntArray(ContactCounts.EXTRA_ADDRESS_BOOK_INDEX_COUNTS, counts);
157        return bundle;
158    }
159
160    @VisibleForTesting
161    static Bundle buildExtraBundleFromValue(String value) {
162        final String[] values;
163        if (TextUtils.isEmpty(value)) {
164            values = new String[0];
165        } else {
166            values = SEPARATOR_PATTERN.split(value);
167        }
168
169        if ((values.length) % 2 != 0) {
170            return null; // malformed
171        }
172
173        try {
174            final int numTitles = values.length / 2;
175            final String[] titles = new String[numTitles];
176            final int[] counts = new int[numTitles];
177
178            for (int i = 0; i < numTitles; i++) {
179                titles[i] = values[i * 2];
180                counts[i] = Integer.parseInt(values[i * 2 + 1]);
181            }
182
183            return buildExtraBundle(titles, counts);
184        } catch (RuntimeException e) {
185            Log.w(TAG, "Failed to parse cached value", e);
186            return null; // malformed
187        }
188    }
189
190    public Bundle get(Uri queryUri, String selection, String[] selectionArgs, String sortOrder,
191            String countExpression) {
192        synchronized (mCache) {
193            ensureLoaded();
194            final String key = buildCacheKey(queryUri, selection, selectionArgs, sortOrder,
195                    countExpression);
196            final String value = mCache.get(key);
197            if (value == null) {
198                if (Log.isLoggable(TAG, Log.VERBOSE)) {
199                    Log.v(TAG, "Miss: " + key);
200                }
201                return null;
202            }
203
204            final Bundle b = buildExtraBundleFromValue(value);
205            if (b == null) {
206                // Value was malformed for whatever reason.
207                mCache.remove(key);
208                save();
209            } else {
210                if (Log.isLoggable(TAG, Log.VERBOSE)) {
211                    Log.v(TAG, "Hit:  " + key);
212                }
213            }
214            return b;
215        }
216    }
217
218    /**
219     * Put a {@link Bundle} into the cache.  {@link Bundle} MUST be built with
220     * {@link #buildExtraBundle(String[], int[])}.
221     */
222    public void put(Uri queryUri, String selection, String[] selectionArgs, String sortOrder,
223            String countExpression, Bundle bundle) {
224        synchronized (mCache) {
225            ensureLoaded();
226            final String key = buildCacheKey(queryUri, selection, selectionArgs, sortOrder,
227                    countExpression);
228            mCache.put(key, buildCacheValue(
229                    bundle.getStringArray(ContactCounts.EXTRA_ADDRESS_BOOK_INDEX_TITLES),
230                    bundle.getIntArray(ContactCounts.EXTRA_ADDRESS_BOOK_INDEX_COUNTS)));
231            save();
232
233            if (Log.isLoggable(TAG, Log.VERBOSE)) {
234                Log.v(TAG, "Put: " + key);
235            }
236        }
237    }
238
239    public void invalidate() {
240        synchronized (mCache) {
241            mPrefs.edit().remove(PREFERENCE_KEY).apply();
242            mCache.clear();
243            mPreferenceLoaded = true;
244
245            if (Log.isLoggable(TAG, Log.VERBOSE)) {
246                Log.v(TAG, "Invalidated");
247            }
248        }
249    }
250
251    /**
252     * Store the cache to the preferences.
253     *
254     * We concatenate all key+value pairs into one string and save it.
255     */
256    private void save() {
257        final StringBuilder sb = new StringBuilder();
258        for (String key : mCache.keySet()) {
259            if (sb.length() > 0) {
260                appendIfNotNull(sb, SAVE_SEPARATOR);
261            }
262            appendIfNotNull(sb, key);
263            appendIfNotNull(sb, SAVE_SEPARATOR);
264            appendIfNotNull(sb, mCache.get(key));
265        }
266        mPrefs.edit().putString(PREFERENCE_KEY, sb.toString()).apply();
267    }
268
269    private void ensureLoaded() {
270        if (mPreferenceLoaded) return;
271
272        if (Log.isLoggable(TAG, Log.VERBOSE)) {
273            Log.v(TAG, "Loading...");
274        }
275
276        // Even when we fail to load, don't retry loading again.
277        mPreferenceLoaded = true;
278
279        boolean successfullyLoaded = false;
280        try {
281            final String savedValue = mPrefs.getString(PREFERENCE_KEY, null);
282
283            if (!TextUtils.isEmpty(savedValue)) {
284
285                final String[] keysAndValues = SAVE_SEPARATOR_PATTERN.split(savedValue);
286
287                if ((keysAndValues.length % 2) != 0) {
288                    return; // malformed
289                }
290
291                for (int i = 1; i < keysAndValues.length; i += 2) {
292                    final String key = keysAndValues[i - 1];
293                    final String value = keysAndValues[i];
294
295                    if (Log.isLoggable(TAG, Log.VERBOSE)) {
296                        Log.v(TAG, "Loaded: " + key);
297                    }
298
299                    mCache.put(key, value);
300                }
301            }
302            successfullyLoaded = true;
303        } catch (RuntimeException e) {
304            Log.w(TAG, "Failed to load from preferences", e);
305            // But don't crash apps!
306        } finally {
307            if (!successfullyLoaded) {
308                invalidate();
309            }
310        }
311    }
312}
313