1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mobile/android/base/favicons/cache/FaviconCache.java Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,630 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +package org.mozilla.gecko.favicons.cache;
1.9 +
1.10 +import android.graphics.Bitmap;
1.11 +import android.util.Log;
1.12 +import org.mozilla.gecko.favicons.Favicons;
1.13 +
1.14 +import java.util.Iterator;
1.15 +import java.util.LinkedList;
1.16 +import java.util.concurrent.ConcurrentHashMap;
1.17 +import java.util.concurrent.Semaphore;
1.18 +import java.util.concurrent.atomic.AtomicInteger;
1.19 +
1.20 +/**
1.21 + * Implements a Least-Recently-Used cache for Favicons, keyed by Favicon URL.
1.22 + *
1.23 + * When a favicon at a particular URL is decoded, it will yield one or more bitmaps.
1.24 + * While in memory, these bitmaps are stored in a list, sorted in ascending order of size, in a
1.25 + * FaviconsForURL object.
1.26 + * The collection of FaviconsForURL objects currently in the cache is stored in backingMap, keyed
1.27 + * by favicon URL.
1.28 + *
1.29 + * A second map exists for permanent cache entries -- ones that are never expired. These entries
1.30 + * are assumed to be disjoint from those in the normal cache, and this map is checked first.
1.31 + *
1.32 + * FaviconsForURL provides a method for obtaining the smallest icon larger than a given size - the
1.33 + * most appropriate icon for a particular size.
1.34 + * It also distinguishes between "primary" favicons (Ones that have merely been extracted from a
1.35 + * file downloaded from the website) and "secondary" favicons (Ones that have been computed locally
1.36 + * as resized versions of primary favicons.).
1.37 + *
1.38 + * FaviconsForURL is also responsible for storing URL-specific, as opposed to favicon-specific,
1.39 + * information. For the purposes of this cache, the simplifying assumption that the dominant colour
1.40 + * for all favicons served from a particular favicon URL shall be the same is made. (To violate this
1.41 + * would mandate serving an ICO or similar file with multiple radically different images in it - an
1.42 + * ill-advised and extremely uncommon use-case, for sure.)
1.43 + * The dominant colour information is updated as the element is being added to the cache - typically
1.44 + * on the background thread.
1.45 + * Also present here are the download timestamp and isFailed flag. Upon failure, the flag is set.
1.46 + * A constant exists in this file to specify the maximum time permitted between failures before
1.47 + * a retry is again permitted.
1.48 + *
1.49 + * TODO: Expiry of Favicons from the favicon database cache is not implemented. (Bug 914296)
1.50 + *
1.51 + * A typical request to the cache will consist of a Favicon URL and a target size. The FaviconsForURL
1.52 + * object for that URL will be obtained, queried for a favicon matching exactly the needed size, and
1.53 + * if successful, the result is returned.
1.54 + * If unsuccessful, the object is asked to return the smallest available primary favicon larger than
1.55 + * the target size. If this step works, the result is downscaled to create a new secondary favicon,
1.56 + * which is then stored (So subsequent requests will succeed at the first step) and returned.
1.57 + * If that step fails, the object finally walks backwards through its sequence of favicons until it
1.58 + * finds the largest primary favicon smaller than the target. This is then upscaled by a maximum of
1.59 + * 2x towards the target size, and the result cached and returned as above.
1.60 + *
1.61 + * The bitmaps themselves are encapsulated inside FaviconCacheElement objects. These objects contain,
1.62 + * as well as the bitmap, a pointer to the encapsulating FaviconsForURL object (Used by the LRU
1.63 + * culler), the size of the encapsulated image, a flag indicating if this is a primary favicon, and
1.64 + * a flag indicating if the entry is invalid.
1.65 + * All FaviconCacheElement objects are tracked in the ordering LinkedList. This is used to record
1.66 + * LRU information about FaviconCacheElements. In particular, the most recently used FaviconCacheElement
1.67 + * will be at the start of the list, the least recently used at the end of the list.
1.68 + *
1.69 + * When the cache runs out of space, it removes FaviconCacheElements starting from the end of the list
1.70 + * until a sufficient amount of space has been freed.
1.71 + * When a secondary favicon is removed in this way, it is simply deleted from its parent FaviconsForURLs
1.72 + * object's list of available favicons.
1.73 + * The backpointer field on the FaviconCacheElement is used to remove the element from the encapsulating
1.74 + * FaviconsForURL object, when this is required.
1.75 + * When a primary favicon is removed, its invalid flag is set to true and its bitmap payload is set
1.76 + * to null (So it is available for freeing by the garbage collector). This reduces the memory footprint
1.77 + * of the icon to essentially zero, but keeps track of which primary favicons exist for this favicon
1.78 + * URL.
1.79 + * If a subsequent request comes in for that favicon URL, it is then known that a primary of those
1.80 + * dimensions is available, just that it is not in the cache. The system is then able to load the
1.81 + * primary back into the cache from the database (Where the entirety of the initially encapsulating
1.82 + * container-formatted image file is stored).
1.83 + * If this were not done, then when processing requests after the culling of primary favicons it would
1.84 + * be impossible to distinguish between the nonexistence of a primary and the nonexistence of a primary
1.85 + * in the cache without querying the database.
1.86 + *
1.87 + * The implementation is safe to use from multiple threads and, while is it not entirely strongly
1.88 + * consistent all of the time, you almost certainly don't care.
1.89 + * The thread-safety implementation used is approximately MRSW with semaphores. An extra semaphore
1.90 + * is used to grant mutual exclusion over reordering operations from reader threads (Who thus gain
1.91 + * a quasi-writer status to do such limited mutation as is necessary).
1.92 + *
1.93 + * Reads which race with writes are liable to not see the ongoing write. The cache may return a
1.94 + * stale or now-removed value to the caller. Returned values are never invalid, even in the face
1.95 + * of concurrent reading and culling.
1.96 + */
1.97 +public class FaviconCache {
1.98 + private static final String LOGTAG = "FaviconCache";
1.99 +
1.100 + // The number of spaces to allocate for favicons in each node.
1.101 + private static final int NUM_FAVICON_SIZES = 4;
1.102 +
1.103 + // Dimensions of the largest favicon to store in the cache. Everything is downscaled to this.
1.104 + public final int maxCachedWidth;
1.105 +
1.106 + // Retry failed favicons after 20 minutes.
1.107 + public static final long FAILURE_RETRY_MILLISECONDS = 1000 * 60 * 20;
1.108 +
1.109 + // Map relating Favicon URLs with objects representing decoded favicons.
1.110 + // Since favicons may be container formats holding multiple icons, the underlying type holds a
1.111 + // sorted list of bitmap payloads in ascending order of size. The underlying type may be queried
1.112 + // for the least larger payload currently present.
1.113 + private final ConcurrentHashMap<String, FaviconsForURL> backingMap = new ConcurrentHashMap<String, FaviconsForURL>();
1.114 +
1.115 + // And the same, but never evicted.
1.116 + private final ConcurrentHashMap<String, FaviconsForURL> permanentBackingMap = new ConcurrentHashMap<String, FaviconsForURL>();
1.117 +
1.118 + // A linked list used to implement a queue, defining the LRU properties of the cache. Elements
1.119 + // contained within the various FaviconsForURL objects are held here, the least recently used
1.120 + // of which at the end of the list. When space needs to be reclaimed, the appropriate bitmap is
1.121 + // culled.
1.122 + private final LinkedList<FaviconCacheElement> ordering = new LinkedList<FaviconCacheElement>();
1.123 +
1.124 + // The above structures, if used correctly, enable this cache to exhibit LRU semantics across all
1.125 + // favicon payloads in the system, as well as enabling the dynamic selection from the cache of
1.126 + // the primary bitmap most suited to the requested size (in cases where multiple primary bitmaps
1.127 + // are provided by the underlying file format).
1.128 +
1.129 + // Current size, in bytes, of the bitmap data present in the LRU cache.
1.130 + private final AtomicInteger currentSize = new AtomicInteger(0);
1.131 +
1.132 + // The maximum quantity, in bytes, of bitmap data which may be stored in the cache.
1.133 + private final int maxSizeBytes;
1.134 +
1.135 + // Tracks the number of ongoing read operations. Enables the first one in to lock writers out and
1.136 + // the last one out to let them in.
1.137 + private final AtomicInteger ongoingReads = new AtomicInteger(0);
1.138 +
1.139 + // Used to ensure transaction fairness - each txn acquires and releases this as the first operation.
1.140 + // The effect is an orderly, inexpensive ordering enforced on txns to prevent writer starvation.
1.141 + private final Semaphore turnSemaphore = new Semaphore(1);
1.142 +
1.143 + // A deviation from the usual MRSW solution - this semaphore is used to guard modification to the
1.144 + // ordering map. This allows for read transactions to update the most-recently-used value without
1.145 + // needing to take out the write lock.
1.146 + private final Semaphore reorderingSemaphore = new Semaphore(1);
1.147 +
1.148 + // The semaphore one must acquire in order to perform a write.
1.149 + private final Semaphore writeLock = new Semaphore(1);
1.150 +
1.151 + /**
1.152 + * Called by txns performing only reads as they start. Prevents writer starvation with a turn
1.153 + * semaphore and locks writers out if this is the first concurrent reader txn starting up.
1.154 + */
1.155 + private void startRead() {
1.156 + turnSemaphore.acquireUninterruptibly();
1.157 + turnSemaphore.release();
1.158 +
1.159 + if (ongoingReads.incrementAndGet() == 1) {
1.160 + // First one in. Wait for writers to finish and lock them out.
1.161 + writeLock.acquireUninterruptibly();
1.162 + }
1.163 + }
1.164 +
1.165 + /**
1.166 + * Called by transactions performing only reads as they finish. Ensures that if this is the last
1.167 + * concluding read transaction then then writers are subsequently allowed in.
1.168 + */
1.169 + private void finishRead() {
1.170 + if (ongoingReads.decrementAndGet() == 0) {
1.171 + writeLock.release();
1.172 + }
1.173 + }
1.174 +
1.175 + /**
1.176 + * Called by writer transactions upon start. Ensures fairness and then obtains the write lock.
1.177 + * Upon return, no other txns will be executing concurrently.
1.178 + */
1.179 + private void startWrite() {
1.180 + turnSemaphore.acquireUninterruptibly();
1.181 + writeLock.acquireUninterruptibly();
1.182 + }
1.183 +
1.184 + /**
1.185 + * Called by a concluding write transaction - unlocks the structure.
1.186 + */
1.187 + private void finishWrite() {
1.188 + turnSemaphore.release();
1.189 + writeLock.release();
1.190 + }
1.191 +
1.192 + public FaviconCache(int maxSize, int maxWidthToCache) {
1.193 + maxSizeBytes = maxSize;
1.194 + maxCachedWidth = maxWidthToCache;
1.195 + }
1.196 +
1.197 + /**
1.198 + * Determine if the provided favicon URL is marked as a failure (Has failed to load before -
1.199 + * such icons get blacklisted for a time to prevent us endlessly retrying.)
1.200 + *
1.201 + * @param faviconURL Favicon URL to check if failed in memcache.
1.202 + * @return true if this favicon is blacklisted, false otherwise.
1.203 + */
1.204 + public boolean isFailedFavicon(String faviconURL) {
1.205 + if (faviconURL == null) {
1.206 + return true;
1.207 + }
1.208 +
1.209 + startRead();
1.210 +
1.211 + try {
1.212 + // If we don't have it in the cache, it certainly isn't a known failure.
1.213 + // Non-evictable favicons are never failed, so we don't need to
1.214 + // check permanentBackingMap.
1.215 + if (!backingMap.containsKey(faviconURL)) {
1.216 + return false;
1.217 + }
1.218 +
1.219 + FaviconsForURL container = backingMap.get(faviconURL);
1.220 +
1.221 + // If the has failed flag is not set, it's certainly not a known failure.
1.222 + if (!container.hasFailed) {
1.223 + return false;
1.224 + }
1.225 +
1.226 + final long failureTimestamp = container.downloadTimestamp;
1.227 +
1.228 + // Calculate elapsed time since the failing download.
1.229 + final long failureDiff = System.currentTimeMillis() - failureTimestamp;
1.230 +
1.231 + // If the expiry is still in effect, return. Otherwise, continue and unmark the failure.
1.232 + if (failureDiff < FAILURE_RETRY_MILLISECONDS) {
1.233 + return true;
1.234 + }
1.235 + } catch (Exception unhandled) {
1.236 + Log.e(LOGTAG, "FaviconCache exception!", unhandled);
1.237 + return true;
1.238 + } finally {
1.239 + finishRead();
1.240 + }
1.241 +
1.242 + startWrite();
1.243 +
1.244 + // If the entry is no longer failed, remove the record of it from the cache.
1.245 + try {
1.246 + recordRemoved(backingMap.remove(faviconURL));
1.247 + return false;
1.248 + } finally {
1.249 + finishWrite();
1.250 + }
1.251 + }
1.252 +
1.253 + /**
1.254 + * Mark the indicated page URL as a failed Favicon until the provided time.
1.255 + *
1.256 + * @param faviconURL Page URL for which a Favicon load has failed.
1.257 + */
1.258 + public void putFailed(String faviconURL) {
1.259 + startWrite();
1.260 +
1.261 + try {
1.262 + FaviconsForURL container = new FaviconsForURL(0, true);
1.263 + recordRemoved(backingMap.put(faviconURL, container));
1.264 + } finally {
1.265 + finishWrite();
1.266 + }
1.267 + }
1.268 +
1.269 + /**
1.270 + * Fetch a Favicon for the given URL as close as possible to the size provided.
1.271 + * If an icon of the given size is already in the cache, it is returned.
1.272 + * If an icon of the given size is not in the cache but a larger unscaled image does exist in
1.273 + * the cache, we downscale the larger image to the target size and cache the result.
1.274 + * If there is no image of the required size, null is returned.
1.275 + *
1.276 + * @param faviconURL The URL for which a Favicon is desired. Must not be null.
1.277 + * @param targetSize The size of the desired favicon.
1.278 + * @return A favicon of the requested size for the requested URL, or null if none cached.
1.279 + */
1.280 + public Bitmap getFaviconForDimensions(String faviconURL, int targetSize) {
1.281 + if (faviconURL == null) {
1.282 + Log.e(LOGTAG, "You passed a null faviconURL to getFaviconForDimensions. Don't.");
1.283 + return null;
1.284 + }
1.285 +
1.286 + boolean shouldComputeColour = false;
1.287 + boolean wasPermanent = false;
1.288 + FaviconsForURL container;
1.289 + final Bitmap newBitmap;
1.290 +
1.291 + startRead();
1.292 +
1.293 + try {
1.294 + container = permanentBackingMap.get(faviconURL);
1.295 + if (container == null) {
1.296 + container = backingMap.get(faviconURL);
1.297 + if (container == null) {
1.298 + // We don't have it!
1.299 + return null;
1.300 + }
1.301 + } else {
1.302 + wasPermanent = true;
1.303 + }
1.304 +
1.305 + FaviconCacheElement cacheElement;
1.306 +
1.307 + // If targetSize is -1, it means we want the largest possible icon.
1.308 + int cacheElementIndex = (targetSize == -1) ? -1 : container.getNextHighestIndex(targetSize);
1.309 +
1.310 + // cacheElementIndex now holds either the index of the next least largest bitmap from
1.311 + // targetSize, or -1 if targetSize > all bitmaps.
1.312 + if (cacheElementIndex != -1) {
1.313 + // If cacheElementIndex is not the sentinel value, then it is a valid index into favicons.
1.314 + cacheElement = container.favicons.get(cacheElementIndex);
1.315 +
1.316 + if (cacheElement.invalidated) {
1.317 + return null;
1.318 + }
1.319 +
1.320 + // If we found exactly what we wanted - we're done.
1.321 + if (cacheElement.imageSize == targetSize) {
1.322 + setMostRecentlyUsedWithinRead(cacheElement);
1.323 + return cacheElement.faviconPayload;
1.324 + }
1.325 + } else {
1.326 + // We requested an image larger than all primaries. Set the element to start the search
1.327 + // from to the element beyond the end of the array, so the search runs backwards.
1.328 + cacheElementIndex = container.favicons.size();
1.329 + }
1.330 +
1.331 + // We did not find exactly what we wanted, but now have set cacheElementIndex to the index
1.332 + // where what we want should live in the list. We now request the next least larger primary
1.333 + // from the cache. We will downscale this to our target size.
1.334 +
1.335 + // If there is no such primary, we'll upscale the next least smaller one instead.
1.336 + cacheElement = container.getNextPrimary(cacheElementIndex);
1.337 +
1.338 + if (cacheElement == null) {
1.339 + // The primary has been invalidated! Fail! Need to get it back from the database.
1.340 + return null;
1.341 + }
1.342 +
1.343 + if (targetSize == -1) {
1.344 + // We got the biggest primary, so that's what we'll return.
1.345 + return cacheElement.faviconPayload;
1.346 + }
1.347 +
1.348 + // Scaling logic...
1.349 + Bitmap largestElementBitmap = cacheElement.faviconPayload;
1.350 + int largestSize = cacheElement.imageSize;
1.351 +
1.352 + if (largestSize >= targetSize) {
1.353 + // The largest we have is larger than the target - downsize to target.
1.354 + newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);
1.355 + } else {
1.356 + // Our largest primary is smaller than the desired size. Upscale by a maximum of 2x.
1.357 + // largestSize now reflects the maximum size we can upscale to.
1.358 + largestSize *= 2;
1.359 +
1.360 + if (largestSize >= targetSize) {
1.361 + // Perfect! We can upscale by less than 2x and reach the needed size. Do it.
1.362 + newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, targetSize, targetSize, true);
1.363 + } else {
1.364 + // We don't have enough information to make the target size look nonterrible. Best effort:
1.365 + newBitmap = Bitmap.createScaledBitmap(largestElementBitmap, largestSize, largestSize, true);
1.366 +
1.367 + shouldComputeColour = true;
1.368 + }
1.369 + }
1.370 + } catch (Exception unhandled) {
1.371 + // Handle any exception thrown and return the locks to a sensible state.
1.372 +
1.373 + // Flag to prevent finally from doubly-unlocking.
1.374 + Log.e(LOGTAG, "FaviconCache exception!", unhandled);
1.375 + return null;
1.376 + } finally {
1.377 + finishRead();
1.378 + }
1.379 +
1.380 + startWrite();
1.381 + try {
1.382 + if (shouldComputeColour) {
1.383 + // And since we failed, we'll need the dominant colour.
1.384 + container.ensureDominantColor();
1.385 + }
1.386 +
1.387 + // While the image might not actually BE that size, we set the size field to the target
1.388 + // because this is the best image you can get for a request of that size using the Favicon
1.389 + // information provided by this website.
1.390 + // This way, subsequent requests hit straight away.
1.391 + FaviconCacheElement newElement = container.addSecondary(newBitmap, targetSize);
1.392 +
1.393 + if (!wasPermanent) {
1.394 + if (setMostRecentlyUsedWithinWrite(newElement)) {
1.395 + currentSize.addAndGet(newElement.sizeOf());
1.396 + }
1.397 + }
1.398 + } finally {
1.399 + finishWrite();
1.400 + }
1.401 +
1.402 + return newBitmap;
1.403 + }
1.404 +
1.405 + /**
1.406 + * Query the cache for the dominant colour stored for the Favicon URL provided, if any.
1.407 + *
1.408 + * @param key The URL of the Favicon for which a dominant colour is desired.
1.409 + * @return The cached dominant colour, or null if none is cached.
1.410 + */
1.411 + public int getDominantColor(String key) {
1.412 + startRead();
1.413 +
1.414 + try {
1.415 + FaviconsForURL element = permanentBackingMap.get(key);
1.416 + if (element == null) {
1.417 + element = backingMap.get(key);
1.418 + }
1.419 +
1.420 + if (element == null) {
1.421 + Log.w(LOGTAG, "Cannot compute dominant color of non-cached favicon. Cache fullness " +
1.422 + currentSize.get() + '/' + maxSizeBytes);
1.423 + return 0xFFFFFF;
1.424 + }
1.425 +
1.426 + return element.ensureDominantColor();
1.427 + } finally {
1.428 + finishRead();
1.429 + }
1.430 + }
1.431 +
1.432 + /**
1.433 + * Remove all payloads stored in the given container from the LRU cache.
1.434 + * Must be called while holding the write lock.
1.435 + *
1.436 + * @param wasRemoved The container to purge from the cache.
1.437 + */
1.438 + private void recordRemoved(FaviconsForURL wasRemoved) {
1.439 + // If there was an existing value, strip it from the insertion-order cache.
1.440 + if (wasRemoved == null) {
1.441 + return;
1.442 + }
1.443 +
1.444 + int sizeRemoved = 0;
1.445 +
1.446 + for (FaviconCacheElement e : wasRemoved.favicons) {
1.447 + sizeRemoved += e.sizeOf();
1.448 + ordering.remove(e);
1.449 + }
1.450 +
1.451 + currentSize.addAndGet(-sizeRemoved);
1.452 + }
1.453 +
1.454 + private Bitmap produceCacheableBitmap(Bitmap favicon) {
1.455 + // Never cache the default Favicon, or the null Favicon.
1.456 + if (favicon == Favicons.defaultFavicon || favicon == null) {
1.457 + return null;
1.458 + }
1.459 +
1.460 + // Some sites serve up insanely huge Favicons (Seen 512x512 ones...)
1.461 + // While we want to cache nice big icons, we apply a limit based on screen density for the
1.462 + // sake of space.
1.463 + if (favicon.getWidth() > maxCachedWidth) {
1.464 + return Bitmap.createScaledBitmap(favicon, maxCachedWidth, maxCachedWidth, true);
1.465 + }
1.466 +
1.467 + return favicon;
1.468 + }
1.469 +
1.470 + /**
1.471 + * Set an existing element as the most recently used element. Intended for use from read transactions. While
1.472 + * write transactions may safely use this method, it will perform slightly worse than its unsafe counterpart below.
1.473 + *
1.474 + * @param element The element that is to become the most recently used one.
1.475 + * @return true if this element already existed in the list, false otherwise. (Useful for preventing multiple-insertion.)
1.476 + */
1.477 + private boolean setMostRecentlyUsedWithinRead(FaviconCacheElement element) {
1.478 + reorderingSemaphore.acquireUninterruptibly();
1.479 + try {
1.480 + boolean contained = ordering.remove(element);
1.481 + ordering.offer(element);
1.482 + return contained;
1.483 + } finally {
1.484 + reorderingSemaphore.release();
1.485 + }
1.486 + }
1.487 +
1.488 + /**
1.489 + * Functionally equivalent to setMostRecentlyUsedWithinRead, but operates without taking the reordering semaphore.
1.490 + * Only safe for use when called from a write transaction, or there is a risk of concurrent modification.
1.491 + *
1.492 + * @param element The element that is to become the most recently used one.
1.493 + * @return true if this element already existed in the list, false otherwise. (Useful for preventing multiple-insertion.)
1.494 + */
1.495 + private boolean setMostRecentlyUsedWithinWrite(FaviconCacheElement element) {
1.496 + boolean contained = ordering.remove(element);
1.497 + ordering.offer(element);
1.498 + return contained;
1.499 + }
1.500 +
1.501 + /**
1.502 + * Add the provided bitmap to the cache as the only available primary for this URL.
1.503 + * Should never be called with scaled Favicons. The input is assumed to be an unscaled Favicon.
1.504 + *
1.505 + * @param faviconURL The URL of the Favicon being stored.
1.506 + * @param aFavicon The Favicon to store.
1.507 + */
1.508 + public void putSingleFavicon(String faviconURL, Bitmap aFavicon) {
1.509 + Bitmap favicon = produceCacheableBitmap(aFavicon);
1.510 + if (favicon == null) {
1.511 + return;
1.512 + }
1.513 +
1.514 + // Create a fresh container for the favicons associated with this URL. Allocate extra slots
1.515 + // in the underlying ArrayList in case multiple secondary favicons are later created.
1.516 + // Currently set to the number of favicon sizes used in the UI, plus 1, at time of writing.
1.517 + // Ought to be tuned as things change for maximal performance.
1.518 + FaviconsForURL toInsert = new FaviconsForURL(NUM_FAVICON_SIZES);
1.519 +
1.520 + // Create the cache element for the single element we are inserting, and configure it.
1.521 + FaviconCacheElement newElement = toInsert.addPrimary(favicon);
1.522 +
1.523 + startWrite();
1.524 + try {
1.525 + // Set the new element as the most recently used one.
1.526 + setMostRecentlyUsedWithinWrite(newElement);
1.527 +
1.528 + currentSize.addAndGet(newElement.sizeOf());
1.529 +
1.530 + // Update the value in the LruCache...
1.531 + FaviconsForURL wasRemoved;
1.532 + wasRemoved = backingMap.put(faviconURL, toInsert);
1.533 +
1.534 + recordRemoved(wasRemoved);
1.535 + } finally {
1.536 + finishWrite();
1.537 + }
1.538 +
1.539 + cullIfRequired();
1.540 + }
1.541 +
1.542 + /**
1.543 + * Set the collection of primary favicons for the given URL to the provided collection of bitmaps.
1.544 + *
1.545 + * @param faviconURL The URL from which the favicons originate.
1.546 + * @param favicons A List of favicons decoded from this URL.
1.547 + * @param permanently If true, the added favicons are never subject to eviction.
1.548 + */
1.549 + public void putFavicons(String faviconURL, Iterator<Bitmap> favicons, boolean permanently) {
1.550 + // We don't know how many icons we'll have - let's just take a guess.
1.551 + FaviconsForURL toInsert = new FaviconsForURL(5 * NUM_FAVICON_SIZES);
1.552 + int sizeGained = 0;
1.553 +
1.554 + while (favicons.hasNext()) {
1.555 + Bitmap favicon = produceCacheableBitmap(favicons.next());
1.556 + if (favicon == null) {
1.557 + continue;
1.558 + }
1.559 +
1.560 + FaviconCacheElement newElement = toInsert.addPrimary(favicon);
1.561 + sizeGained += newElement.sizeOf();
1.562 + }
1.563 +
1.564 + startWrite();
1.565 + try {
1.566 + if (permanently) {
1.567 + permanentBackingMap.put(faviconURL, toInsert);
1.568 + return;
1.569 + }
1.570 +
1.571 + for (FaviconCacheElement newElement : toInsert.favicons) {
1.572 + setMostRecentlyUsedWithinWrite(newElement);
1.573 + }
1.574 +
1.575 + // In the event this insertion is being made to a key that already held a value, the subsequent recordRemoved
1.576 + // call will subtract the size of the old value, preventing double-counting.
1.577 + currentSize.addAndGet(sizeGained);
1.578 +
1.579 + // Update the value in the LruCache...
1.580 + recordRemoved(backingMap.put(faviconURL, toInsert));
1.581 + } finally {
1.582 + finishWrite();
1.583 + }
1.584 +
1.585 + cullIfRequired();
1.586 + }
1.587 +
1.588 + /**
1.589 + * If cache too large, drop stuff from the cache to get the size back into the acceptable range.
1.590 + * Otherwise, do nothing.
1.591 + */
1.592 + private void cullIfRequired() {
1.593 + Log.d(LOGTAG, "Favicon cache fullness: " + currentSize.get() + '/' + maxSizeBytes);
1.594 +
1.595 + if (currentSize.get() <= maxSizeBytes) {
1.596 + return;
1.597 + }
1.598 +
1.599 + startWrite();
1.600 + try {
1.601 + while (currentSize.get() > maxSizeBytes) {
1.602 + // Cull the least recently used element.
1.603 +
1.604 + FaviconCacheElement victim;
1.605 + victim = ordering.poll();
1.606 +
1.607 + currentSize.addAndGet(-victim.sizeOf());
1.608 + victim.onEvictedFromCache();
1.609 +
1.610 + Log.d(LOGTAG, "After cull: " + currentSize.get() + '/' + maxSizeBytes);
1.611 + }
1.612 + } finally {
1.613 + finishWrite();
1.614 + }
1.615 + }
1.616 +
1.617 + /**
1.618 + * Purge all elements from the FaviconCache. Handy if you want to reclaim some memory.
1.619 + */
1.620 + public void evictAll() {
1.621 + startWrite();
1.622 +
1.623 + // Note that we neither clear, nor track the size of, the permanent map.
1.624 + try {
1.625 + currentSize.set(0);
1.626 + backingMap.clear();
1.627 + ordering.clear();
1.628 +
1.629 + } finally {
1.630 + finishWrite();
1.631 + }
1.632 + }
1.633 +}
