1package com.bumptech.glide.load.engine.bitmap_recycle;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.List;
6import java.util.Map;
7
8/**
9 * Similar to {@link java.util.LinkedHashMap} when access ordered except that it is access ordered on groups
10 * of bitmaps rather than individual objects. The idea is to be able to find the LRU bitmap size, rather than the
11 * LRU bitmap object. We can then remove bitmaps from the least recently used size of bitmap when we need to
12 * reduce our cache size.
13 *
14 * For the purposes of the LRU, we count gets for a particular size of bitmap as an access, even if no bitmaps
15 * of that size are present. We do not count addition or removal of bitmaps as an access.
16 */
17class GroupedLinkedMap<K extends Poolable, V> {
18    private final LinkedEntry<K, V> head = new LinkedEntry<K, V>();
19    private final Map<K, LinkedEntry<K, V>> keyToEntry = new HashMap<K, LinkedEntry<K, V>>();
20
21    public void put(K key, V value) {
22        LinkedEntry<K, V> entry = keyToEntry.get(key);
23
24        if (entry == null) {
25            entry = new LinkedEntry<K, V>(key);
26            makeTail(entry);
27            keyToEntry.put(key, entry);
28        } else {
29            key.offer();
30        }
31
32        entry.add(value);
33    }
34
35    public V get(K key) {
36        LinkedEntry<K, V> entry = keyToEntry.get(key);
37        if (entry == null) {
38            entry = new LinkedEntry<K, V>(key);
39            keyToEntry.put(key, entry);
40        } else {
41            key.offer();
42        }
43
44        makeHead(entry);
45
46        return entry.removeLast();
47    }
48
49    public V removeLast() {
50        LinkedEntry<K, V> last = head.prev;
51
52        while (!last.equals(head)) {
53            V removed = last.removeLast();
54            if (removed != null) {
55                return removed;
56            } else {
57                // We will clean up empty lru entries since they are likely to have been one off or unusual sizes and
58                // are not likely to be requested again so the gc thrash should be minimal. Doing so will speed up our
59                // removeLast operation in the future and prevent our linked list from growing to arbitrarily large
60                // sizes.
61                removeEntry(last);
62                keyToEntry.remove(last.key);
63                last.key.offer();
64            }
65
66            last = last.prev;
67        }
68
69        return null;
70    }
71
72    @Override
73    public String toString() {
74        StringBuilder sb = new StringBuilder("GroupedLinkedMap( ");
75        LinkedEntry<K, V> current = head.next;
76        boolean hadAtLeastOneItem = false;
77        while (!current.equals(head)) {
78            hadAtLeastOneItem = true;
79            sb.append('{').append(current.key).append(':').append(current.size()).append("}, ");
80            current = current.next;
81        }
82        if (hadAtLeastOneItem) {
83            sb.delete(sb.length() - 2, sb.length());
84        }
85        return sb.append(" )").toString();
86    }
87
88    // Make the entry the most recently used item.
89    private void makeHead(LinkedEntry<K, V> entry) {
90        removeEntry(entry);
91        entry.prev = head;
92        entry.next = head.next;
93        updateEntry(entry);
94    }
95
96    // Make the entry the least recently used item.
97    private void makeTail(LinkedEntry<K, V> entry) {
98        removeEntry(entry);
99        entry.prev = head.prev;
100        entry.next = head;
101        updateEntry(entry);
102    }
103
104    private static <K, V> void updateEntry(LinkedEntry<K, V> entry) {
105        entry.next.prev = entry;
106        entry.prev.next = entry;
107    }
108
109    private static <K, V> void removeEntry(LinkedEntry<K, V> entry) {
110        entry.prev.next = entry.next;
111        entry.next.prev = entry.prev;
112    }
113
114    private static class LinkedEntry<K, V> {
115        private final K key;
116        private List<V> values;
117        LinkedEntry<K, V> next;
118        LinkedEntry<K, V> prev;
119
120        // Used only for the first item in the list which we will treat specially and which will not contain a value.
121        public LinkedEntry() {
122            this(null);
123        }
124
125        public LinkedEntry(K key) {
126            next = prev = this;
127            this.key = key;
128        }
129
130        public V removeLast() {
131            final int valueSize = size();
132            return valueSize > 0 ? values.remove(valueSize - 1) : null;
133        }
134
135        public int size() {
136            return values != null ? values.size() : 0;
137        }
138
139        public void add(V value) {
140            if (values == null) {
141                values = new ArrayList<V>();
142            }
143            values.add(value);
144        }
145    }
146}
147