1d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov/* 2d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Copyright (C) 2009 The Android Open Source Project 3d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * 4d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Licensed under the Apache License, Version 2.0 (the "License"); 5d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * you may not use this file except in compliance with the License. 6d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * You may obtain a copy of the License at 7d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * 8d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * http://www.apache.org/licenses/LICENSE-2.0 9d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * 10d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Unless required by applicable law or agreed to in writing, software 11d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * distributed under the License is distributed on an "AS IS" BASIS, 12d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * See the License for the specific language governing permissions and 14d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * limitations under the License 15d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov */ 16d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 1781567f4a0f7c9c338506bd82f4d33e83c2ccf159Makoto Onukipackage com.android.providers.contacts.aggregation.util; 18d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 1938210445730ee04c351c7cc1b3800cfe23e34325Makoto Onukiimport android.database.Cursor; 2038210445730ee04c351c7cc1b3800cfe23e34325Makoto Onukiimport android.database.sqlite.SQLiteDatabase; 2138210445730ee04c351c7cc1b3800cfe23e34325Makoto Onuki 22d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovimport com.android.providers.contacts.ContactsDatabaseHelper.NicknameLookupColumns; 23d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovimport com.android.providers.contacts.ContactsDatabaseHelper.Tables; 24d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovimport com.google.android.collect.Maps; 25d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 26d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovimport java.lang.ref.SoftReference; 27d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovimport java.util.BitSet; 28d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovimport java.util.HashMap; 29d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 30d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov/** 31d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Cache for common nicknames. 32d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov */ 33d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikovpublic class CommonNicknameCache { 34d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 35d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov // We will use this much memory (in bits) to optimize the nickname cluster lookup 36d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov private static final int NICKNAME_BLOOM_FILTER_SIZE = 0x1FFF; // =long[128] 37d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov private BitSet mNicknameBloomFilter; 38d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 39d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov private HashMap<String, SoftReference<String[]>> mNicknameClusterCache = Maps.newHashMap(); 40d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 41d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov private final SQLiteDatabase mDb; 42d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 43d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov public CommonNicknameCache(SQLiteDatabase db) { 44d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov mDb = db; 45d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 46d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 47d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov private final static class NicknameLookupPreloadQuery { 48d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov public final static String TABLE = Tables.NICKNAME_LOOKUP; 49d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 50d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov public final static String[] COLUMNS = new String[] { 51d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov NicknameLookupColumns.NAME 52d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov }; 53d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 54d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov public final static int NAME = 0; 55d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 56d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 57d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov /** 58d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Read all known common nicknames from the database and populate a Bloom 59d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * filter using the corresponding hash codes. The idea is to eliminate most 60d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * of unnecessary database lookups for nicknames. Given a name, we will take 61d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * its hash code and see if it is set in the Bloom filter. If not, we will know 62d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * that the name is not in the database. If it is, we still need to run a 63d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * query. 64d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * <p> 65d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Given the size of the filter and the expected size of the nickname table, 66d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * we should expect the combination of the Bloom filter and cache will 67d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * prevent around 98-99% of unnecessary queries from running. 68d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov */ 6904b7ce026c73077d9d982742bc662ea4b3ac74e7Dmitri Plotnikov private void preloadNicknameBloomFilter() { 70d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov mNicknameBloomFilter = new BitSet(NICKNAME_BLOOM_FILTER_SIZE + 1); 71d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov Cursor cursor = mDb.query(NicknameLookupPreloadQuery.TABLE, 72d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov NicknameLookupPreloadQuery.COLUMNS, 73d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov null, null, null, null, null); 74d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov try { 75d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov int count = cursor.getCount(); 76d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov for (int i = 0; i < count; i++) { 77d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov cursor.moveToNext(); 78d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov String normalizedName = cursor.getString(NicknameLookupPreloadQuery.NAME); 79d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov int hashCode = normalizedName.hashCode(); 80d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov mNicknameBloomFilter.set(hashCode & NICKNAME_BLOOM_FILTER_SIZE); 81d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 82d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } finally { 83d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov cursor.close(); 84d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 85d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 86d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 87d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov /** 88d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov * Returns nickname cluster IDs or null. Maintains cache. 89d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov */ 9049ed71913609193a00059df944f6259e9397b0bdMakoto Onuki public String[] getCommonNicknameClusters(String normalizedName) { 9104b7ce026c73077d9d982742bc662ea4b3ac74e7Dmitri Plotnikov if (mNicknameBloomFilter == null) { 9204b7ce026c73077d9d982742bc662ea4b3ac74e7Dmitri Plotnikov preloadNicknameBloomFilter(); 9304b7ce026c73077d9d982742bc662ea4b3ac74e7Dmitri Plotnikov } 9404b7ce026c73077d9d982742bc662ea4b3ac74e7Dmitri Plotnikov 95d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov int hashCode = normalizedName.hashCode(); 96d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov if (!mNicknameBloomFilter.get(hashCode & NICKNAME_BLOOM_FILTER_SIZE)) { 97d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov return null; 98d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 99d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 100d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov SoftReference<String[]> ref; 101d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov String[] clusters = null; 102d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov synchronized (mNicknameClusterCache) { 103d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov if (mNicknameClusterCache.containsKey(normalizedName)) { 104d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov ref = mNicknameClusterCache.get(normalizedName); 105d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov if (ref == null) { 106d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov return null; 107d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 108d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov clusters = ref.get(); 109d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 110d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 111d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 112d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov if (clusters == null) { 113d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov clusters = loadNicknameClusters(normalizedName); 114d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov ref = clusters == null ? null : new SoftReference<String[]>(clusters); 115d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov synchronized (mNicknameClusterCache) { 116d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov mNicknameClusterCache.put(normalizedName, ref); 117d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 118d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 119d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov return clusters; 120d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 121d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 122d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov private interface NicknameLookupQuery { 123d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov String TABLE = Tables.NICKNAME_LOOKUP; 124d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 125d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov String[] COLUMNS = new String[] { 126d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov NicknameLookupColumns.CLUSTER 127d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov }; 128d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 129d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov int CLUSTER = 0; 130d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 131d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov 132d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov protected String[] loadNicknameClusters(String normalizedName) { 133d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov String[] clusters = null; 134d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov Cursor cursor = mDb.query(NicknameLookupQuery.TABLE, NicknameLookupQuery.COLUMNS, 135d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov NicknameLookupColumns.NAME + "=?", new String[] { normalizedName }, 136d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov null, null, null); 137d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov try { 138d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov int count = cursor.getCount(); 139d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov if (count > 0) { 140d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov clusters = new String[count]; 141d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov for (int i = 0; i < count; i++) { 142d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov cursor.moveToNext(); 143d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov clusters[i] = cursor.getString(NicknameLookupQuery.CLUSTER); 144d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 145d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 146d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } finally { 147d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov cursor.close(); 148d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 149d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov return clusters; 150d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov } 151d0569511c4b9eb961d5a73be16edb9767fa9c2ebDmitri Plotnikov} 152