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
17package com.android.photos.data;
18
19import android.graphics.Bitmap;
20import android.util.SparseArray;
21
22import android.util.Pools.Pool;
23import android.util.Pools.SimplePool;
24
25/**
26 * Bitmap pool backed by a sparse array indexing linked lists of bitmaps
27 * sharing the same width. Performance will degrade if using this to store
28 * many bitmaps with the same width but many different heights.
29 */
30public class SparseArrayBitmapPool {
31
32    private int mCapacityBytes;
33    private SparseArray<Node> mStore = new SparseArray<Node>();
34    private int mSizeBytes = 0;
35
36    private Pool<Node> mNodePool;
37    private Node mPoolNodesHead = null;
38    private Node mPoolNodesTail = null;
39
40    protected static class Node {
41        Bitmap bitmap;
42
43        // Each node is part of two doubly linked lists:
44        // - A pool-level list (accessed by mPoolNodesHead and mPoolNodesTail)
45        //   that is used for FIFO eviction of nodes when the pool gets full.
46        // - A bucket-level list for each index of the sparse array, so that
47        //   each index can store more than one item.
48        Node prevInBucket;
49        Node nextInBucket;
50        Node nextInPool;
51        Node prevInPool;
52    }
53
54    /**
55     * @param capacityBytes Maximum capacity of the pool in bytes.
56     * @param nodePool Shared pool to use for recycling linked list nodes, or null.
57     */
58    public SparseArrayBitmapPool(int capacityBytes, Pool<Node> nodePool) {
59        mCapacityBytes = capacityBytes;
60        if (nodePool == null) {
61            mNodePool = new SimplePool<Node>(32);
62        } else {
63            mNodePool = nodePool;
64        }
65    }
66
67    /**
68     * Set the maximum capacity of the pool, and if necessary trim it down to size.
69     */
70    public synchronized void setCapacity(int capacityBytes) {
71        mCapacityBytes = capacityBytes;
72
73        // No-op unless current size exceeds the new capacity.
74        freeUpCapacity(0);
75    }
76
77    private void freeUpCapacity(int bytesNeeded) {
78        int targetSize = mCapacityBytes - bytesNeeded;
79        // Repeatedly remove the oldest node until we have freed up at least bytesNeeded.
80        while (mPoolNodesTail != null && mSizeBytes > targetSize) {
81            unlinkAndRecycleNode(mPoolNodesTail, true);
82        }
83    }
84
85    private void unlinkAndRecycleNode(Node n, boolean recycleBitmap) {
86        // Unlink the node from its sparse array bucket list.
87        if (n.prevInBucket != null) {
88            // This wasn't the head, update the previous node.
89            n.prevInBucket.nextInBucket = n.nextInBucket;
90        } else {
91            // This was the head of the bucket, replace it with the next node.
92            mStore.put(n.bitmap.getWidth(), n.nextInBucket);
93        }
94        if (n.nextInBucket != null) {
95            // This wasn't the tail, update the next node.
96            n.nextInBucket.prevInBucket = n.prevInBucket;
97        }
98
99        // Unlink the node from the pool-wide list.
100        if (n.prevInPool != null) {
101            // This wasn't the head, update the previous node.
102            n.prevInPool.nextInPool = n.nextInPool;
103        } else {
104            // This was the head of the pool-wide list, update the head pointer.
105            mPoolNodesHead = n.nextInPool;
106        }
107        if (n.nextInPool != null) {
108            // This wasn't the tail, update the next node.
109            n.nextInPool.prevInPool = n.prevInPool;
110        } else {
111            // This was the tail, update the tail pointer.
112            mPoolNodesTail = n.prevInPool;
113        }
114
115        // Recycle the node.
116        n.nextInBucket = null;
117        n.nextInPool = null;
118        n.prevInBucket = null;
119        n.prevInPool = null;
120        mSizeBytes -= n.bitmap.getByteCount();
121        if (recycleBitmap) n.bitmap.recycle();
122        n.bitmap = null;
123        mNodePool.release(n);
124    }
125
126    /**
127     * @return Capacity of the pool in bytes.
128     */
129    public synchronized int getCapacity() {
130        return mCapacityBytes;
131    }
132
133    /**
134     * @return Total size in bytes of the bitmaps stored in the pool.
135     */
136    public synchronized int getSize() {
137        return mSizeBytes;
138    }
139
140    /**
141     * @return Bitmap from the pool with the desired height/width or null if none available.
142     */
143    public synchronized Bitmap get(int width, int height) {
144        Node cur = mStore.get(width);
145
146        // Traverse the list corresponding to the width bucket in the
147        // sparse array, and unlink and return the first bitmap that
148        // also has the correct height.
149        while (cur != null) {
150            if (cur.bitmap.getHeight() == height) {
151                Bitmap b = cur.bitmap;
152                unlinkAndRecycleNode(cur, false);
153                return b;
154            }
155            cur = cur.nextInBucket;
156        }
157        return null;
158    }
159
160    /**
161     * Adds the given bitmap to the pool.
162     * @return Whether the bitmap was added to the pool.
163     */
164    public synchronized boolean put(Bitmap b) {
165        if (b == null) {
166            return false;
167        }
168
169        // Ensure there is enough room to contain the new bitmap.
170        int bytes = b.getByteCount();
171        freeUpCapacity(bytes);
172
173        Node newNode = mNodePool.acquire();
174        if (newNode == null) {
175            newNode = new Node();
176        }
177        newNode.bitmap = b;
178
179        // We append to the head, and freeUpCapacity clears from the tail,
180        // resulting in FIFO eviction.
181        newNode.prevInBucket = null;
182        newNode.prevInPool = null;
183        newNode.nextInPool = mPoolNodesHead;
184        mPoolNodesHead = newNode;
185
186        // Insert the node into its appropriate bucket based on width.
187        int key = b.getWidth();
188        newNode.nextInBucket = mStore.get(key);
189        if (newNode.nextInBucket != null) {
190            // The bucket already had nodes, update the old head.
191            newNode.nextInBucket.prevInBucket = newNode;
192        }
193        mStore.put(key, newNode);
194
195        if (newNode.nextInPool == null) {
196            // This is the only node in the list, update the tail pointer.
197            mPoolNodesTail = newNode;
198        } else {
199            newNode.nextInPool.prevInPool = newNode;
200        }
201        mSizeBytes += bytes;
202        return true;
203    }
204
205    /**
206     * Empty the pool, recycling all the bitmaps currently in it.
207     */
208    public synchronized void clear() {
209        // Clearing is equivalent to ensuring all the capacity is available.
210        freeUpCapacity(mCapacityBytes);
211    }
212}
213