1 package com.bumptech.glide.load.engine.bitmap_recycle; 2 3 import java.util.ArrayList; 4 import java.util.HashMap; 5 import java.util.List; 6 import 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 */ 17 class 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 put(K key, V value)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 get(K key)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 removeLast()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 toString()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. makeHead(LinkedEntry<K, V> entry)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. makeTail(LinkedEntry<K, V> entry)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 updateEntry(LinkedEntry<K, V> entry)104 private static <K, V> void updateEntry(LinkedEntry<K, V> entry) { 105 entry.next.prev = entry; 106 entry.prev.next = entry; 107 } 108 removeEntry(LinkedEntry<K, V> entry)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. LinkedEntry()121 public LinkedEntry() { 122 this(null); 123 } 124 LinkedEntry(K key)125 public LinkedEntry(K key) { 126 next = prev = this; 127 this.key = key; 128 } 129 removeLast()130 public V removeLast() { 131 final int valueSize = size(); 132 return valueSize > 0 ? values.remove(valueSize - 1) : null; 133 } 134 size()135 public int size() { 136 return values != null ? values.size() : 0; 137 } 138 add(V value)139 public void add(V value) { 140 if (values == null) { 141 values = new ArrayList<V>(); 142 } 143 values.add(value); 144 } 145 } 146 } 147