1 /*
2  * Copyright (C) 2013 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.bitmap;
18 
19 import android.util.Log;
20 import android.util.LruCache;
21 
22 import com.android.bitmap.util.Trace;
23 
24 import java.util.LinkedHashMap;
25 import java.util.Map;
26 import java.util.concurrent.LinkedBlockingQueue;
27 
28 /**
29  * An alternative implementation of a pool+cache. This implementation only counts
30  * unreferenced objects in its size calculation. Internally, it never evicts from
31  * its cache, and instead {@link #poll()} is allowed to return unreferenced cache
32  * entries.
33  * <p>
34  * You would only use this kind of cache if your objects are interchangeable and
35  * have significant allocation cost, and if your memory footprint is somewhat
36  * flexible.
37  * <p>
38  * Because this class only counts unreferenced objects toward targetSize,
39  * it will have a total memory footprint of:
40  * <code>(targetSize) + (# of threads concurrently writing to cache) +
41  * (total size of still-referenced entries)</code>
42  *
43  */
44 public class UnrefedPooledCache<K, V extends Poolable> implements PooledCache<K, V> {
45 
46     private final LinkedHashMap<K, V> mCache;
47     private final LinkedBlockingQueue<V> mPool;
48     private final int mTargetSize;
49     private final LruCache<K, V> mNonPooledCache;
50 
51     private static final boolean DEBUG = DecodeTask.DEBUG;
52     private static final String TAG = UnrefedPooledCache.class.getSimpleName();
53 
54     /**
55      * @param targetSize not exactly a max size in practice
56      * @param nonPooledFraction the fractional portion in the range [0.0,1.0] of targetSize to
57      * dedicate to non-poolable entries
58      */
UnrefedPooledCache(int targetSize, float nonPooledFraction)59     public UnrefedPooledCache(int targetSize, float nonPooledFraction) {
60         mCache = new LinkedHashMap<K, V>(0, 0.75f, true);
61         mPool = new LinkedBlockingQueue<V>();
62         final int nonPooledSize = Math.round(targetSize * nonPooledFraction);
63         if (nonPooledSize > 0) {
64             mNonPooledCache = new NonPooledCache(nonPooledSize);
65         } else {
66             mNonPooledCache = null;
67         }
68         mTargetSize = targetSize - nonPooledSize;
69     }
70 
71     @Override
get(K key, boolean incrementRefCount)72     public V get(K key, boolean incrementRefCount) {
73         Trace.beginSection("cache get");
74         synchronized (mCache) {
75             V result = mCache.get(key);
76             if (result == null && mNonPooledCache != null) {
77                 result = mNonPooledCache.get(key);
78             }
79             if (incrementRefCount && result != null) {
80                 result.acquireReference();
81             }
82             Trace.endSection();
83             return result;
84         }
85     }
86 
87     @Override
put(K key, V value)88     public V put(K key, V value) {
89         Trace.beginSection("cache put");
90         // Null values not supported.
91         if (value == null) {
92             Trace.endSection();
93             return null;
94         }
95         synchronized (mCache) {
96             final V prev;
97             if (value.isEligibleForPooling()) {
98                 prev = mCache.put(key, value);
99             } else if (mNonPooledCache != null) {
100                 prev = mNonPooledCache.put(key, value);
101             } else {
102                 prev = null;
103             }
104             Trace.endSection();
105             return prev;
106         }
107     }
108 
109     @Override
offer(V value)110     public void offer(V value) {
111         Trace.beginSection("pool offer");
112         if (value.getRefCount() != 0 || !value.isEligibleForPooling()) {
113             Trace.endSection();
114             throw new IllegalArgumentException("unexpected offer of an invalid object: " + value);
115         }
116         mPool.offer(value);
117         Trace.endSection();
118     }
119 
120     @Override
poll()121     public V poll() {
122         Trace.beginSection("pool poll");
123         final V pooled = mPool.poll();
124         if (pooled != null) {
125             Trace.endSection();
126             return pooled;
127         }
128 
129         synchronized (mCache) {
130             int unrefSize = 0;
131             Map.Entry<K, V> eldestUnref = null;
132             for (Map.Entry<K, V> entry : mCache.entrySet()) {
133                 final V value = entry.getValue();
134                 if (value.getRefCount() > 0 || !value.isEligibleForPooling()) {
135                     continue;
136                 }
137                 if (eldestUnref == null) {
138                     eldestUnref = entry;
139                 }
140                 unrefSize += sizeOf(value);
141                 if (unrefSize > mTargetSize) {
142                     break;
143                 }
144             }
145             // only return a scavenged cache entry if the cache has enough
146             // eligible (unreferenced) items
147             if (unrefSize <= mTargetSize) {
148                 if (DEBUG) {
149                     Log.e(TAG, "POOL SCAVENGE FAILED, cache not fully warm yet. szDelta="
150                             + (mTargetSize-unrefSize));
151                 }
152                 Trace.endSection();
153                 return null;
154             } else {
155                 mCache.remove(eldestUnref.getKey());
156                 if (DEBUG) {
157                     Log.e(TAG, "POOL SCAVENGE SUCCESS, oldKey=" + eldestUnref.getKey());
158                 }
159                 Trace.endSection();
160                 return eldestUnref.getValue();
161             }
162         }
163     }
164 
sizeOf(V value)165     protected int sizeOf(V value) {
166         return 1;
167     }
168 
169     @Override
toDebugString()170     public String toDebugString() {
171         if (DEBUG) {
172             final StringBuilder sb = new StringBuilder("[");
173             sb.append(super.toString());
174             int size = 0;
175             synchronized (mCache) {
176                 sb.append(" poolCount=");
177                 sb.append(mPool.size());
178                 sb.append(" cacheSize=");
179                 sb.append(mCache.size());
180                 if (mNonPooledCache != null) {
181                     sb.append(" nonPooledCacheSize=");
182                     sb.append(mNonPooledCache.size());
183                 }
184                 sb.append("\n---------------------");
185                 for (V val : mPool) {
186                     size += sizeOf(val);
187                     sb.append("\n\tpool item: ");
188                     sb.append(val);
189                 }
190                 sb.append("\n---------------------");
191                 for (Map.Entry<K, V> item : mCache.entrySet()) {
192                     final V val = item.getValue();
193                     sb.append("\n\tcache key=");
194                     sb.append(item.getKey());
195                     sb.append(" val=");
196                     sb.append(val);
197                     size += sizeOf(val);
198                 }
199                 sb.append("\n---------------------");
200                 if (mNonPooledCache != null) {
201                     for (Map.Entry<K, V> item : mNonPooledCache.snapshot().entrySet()) {
202                         final V val = item.getValue();
203                         sb.append("\n\tnon-pooled cache key=");
204                         sb.append(item.getKey());
205                         sb.append(" val=");
206                         sb.append(val);
207                         size += sizeOf(val);
208                     }
209                     sb.append("\n---------------------");
210                 }
211                 sb.append("\nTOTAL SIZE=" + size);
212             }
213             sb.append("]");
214             return sb.toString();
215         } else {
216             return null;
217         }
218     }
219 
220     private class NonPooledCache extends LruCache<K, V> {
221 
NonPooledCache(int maxSize)222         public NonPooledCache(int maxSize) {
223             super(maxSize);
224         }
225 
226         @Override
sizeOf(K key, V value)227         protected int sizeOf(K key, V value) {
228             return UnrefedPooledCache.this.sizeOf(value);
229         }
230 
231     }
232 
233     @Override
clear()234     public void clear() {
235         mCache.clear();
236         mPool.clear();
237     }
238 }
239