Home | History | Annotate | Download | only in util 
      1 /*
      2  * Copyright (C) 2009 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 
     17 package com.android.providers.contacts.aggregation.util;
     18 
     19 import android.database.Cursor;
     20 import android.database.sqlite.SQLiteDatabase;
     21 
     22 import com.android.providers.contacts.ContactsDatabaseHelper.NicknameLookupColumns;
     23 import com.android.providers.contacts.ContactsDatabaseHelper.Tables;
     24 import com.google.android.collect.Maps;
     25 
     26 import java.lang.ref.SoftReference;
     27 import java.util.BitSet;
     28 import java.util.HashMap;
     29 
     30 /**
     31  * Cache for common nicknames.
     32  */
     33 public class CommonNicknameCache  {
     34 
     35     // We will use this much memory (in bits) to optimize the nickname cluster lookup
     36     private static final int NICKNAME_BLOOM_FILTER_SIZE = 0x1FFF;   // =long[128]
     37     private BitSet mNicknameBloomFilter;
     38 
     39     private HashMap<String, SoftReference<String[]>> mNicknameClusterCache = Maps.newHashMap();
     40 
     41     private final SQLiteDatabase mDb;
     42 
     43     public CommonNicknameCache(SQLiteDatabase db) {
     44         mDb = db;
     45     }
     46 
     47     private final static class NicknameLookupPreloadQuery {
     48         public final static String TABLE = Tables.NICKNAME_LOOKUP;
     49 
     50         public final static String[] COLUMNS = new String[] {
     51             NicknameLookupColumns.NAME
     52         };
     53 
     54         public final static int NAME = 0;
     55     }
     56 
     57     /**
     58      * Read all known common nicknames from the database and populate a Bloom
     59      * filter using the corresponding hash codes. The idea is to eliminate most
     60      * of unnecessary database lookups for nicknames. Given a name, we will take
     61      * its hash code and see if it is set in the Bloom filter. If not, we will know
     62      * that the name is not in the database. If it is, we still need to run a
     63      * query.
     64      * <p>
     65      * Given the size of the filter and the expected size of the nickname table,
     66      * we should expect the combination of the Bloom filter and cache will
     67      * prevent around 98-99% of unnecessary queries from running.
     68      */
     69     private void preloadNicknameBloomFilter() {
     70         mNicknameBloomFilter = new BitSet(NICKNAME_BLOOM_FILTER_SIZE + 1);
     71         Cursor cursor = mDb.query(NicknameLookupPreloadQuery.TABLE,
     72                 NicknameLookupPreloadQuery.COLUMNS,
     73                 null, null, null, null, null);
     74         try {
     75             int count = cursor.getCount();
     76             for (int i = 0; i < count; i++) {
     77                 cursor.moveToNext();
     78                 String normalizedName = cursor.getString(NicknameLookupPreloadQuery.NAME);
     79                 int hashCode = normalizedName.hashCode();
     80                 mNicknameBloomFilter.set(hashCode & NICKNAME_BLOOM_FILTER_SIZE);
     81             }
     82         } finally {
     83             cursor.close();
     84         }
     85     }
     86 
     87     /**
     88      * Returns nickname cluster IDs or null. Maintains cache.
     89      */
     90     public String[] getCommonNicknameClusters(String normalizedName) {
     91         if (mNicknameBloomFilter == null) {
     92             preloadNicknameBloomFilter();
     93         }
     94 
     95         int hashCode = normalizedName.hashCode();
     96         if (!mNicknameBloomFilter.get(hashCode & NICKNAME_BLOOM_FILTER_SIZE)) {
     97             return null;
     98         }
     99 
    100         SoftReference<String[]> ref;
    101         String[] clusters = null;
    102         synchronized (mNicknameClusterCache) {
    103             if (mNicknameClusterCache.containsKey(normalizedName)) {
    104                 ref = mNicknameClusterCache.get(normalizedName);
    105                 if (ref == null) {
    106                     return null;
    107                 }
    108                 clusters = ref.get();
    109             }
    110         }
    111 
    112         if (clusters == null) {
    113             clusters = loadNicknameClusters(normalizedName);
    114             ref = clusters == null ? null : new SoftReference<String[]>(clusters);
    115             synchronized (mNicknameClusterCache) {
    116                 mNicknameClusterCache.put(normalizedName, ref);
    117             }
    118         }
    119         return clusters;
    120     }
    121 
    122     private interface NicknameLookupQuery {
    123         String TABLE = Tables.NICKNAME_LOOKUP;
    124 
    125         String[] COLUMNS = new String[] {
    126             NicknameLookupColumns.CLUSTER
    127         };
    128 
    129         int CLUSTER = 0;
    130     }
    131 
    132     protected String[] loadNicknameClusters(String normalizedName) {
    133         String[] clusters = null;
    134         Cursor cursor = mDb.query(NicknameLookupQuery.TABLE, NicknameLookupQuery.COLUMNS,
    135                 NicknameLookupColumns.NAME + "=?", new String[] { normalizedName },
    136                 null, null, null);
    137         try {
    138             int count = cursor.getCount();
    139             if (count > 0) {
    140                 clusters = new String[count];
    141                 for (int i = 0; i < count; i++) {
    142                     cursor.moveToNext();
    143                     clusters[i] = cursor.getString(NicknameLookupQuery.CLUSTER);
    144                 }
    145             }
    146         } finally {
    147             cursor.close();
    148         }
    149         return clusters;
    150     }
    151 }
    152