BitmapPool
1.Glide对图片做了很好的缓存实现，也是基于Lru的思想来实现的。而主要的实现类在GroupedLinkedMap中，另外需要注意的是，这里保存的是Bitmap的尺寸信息并不是具体的Bitmap对象。注释里也给出了相应的说明。
2.接口BitmapPool的实现类LruBitmapPool处理了图片的缓存操作以及具体的逻辑，Lru思想的具体实现在GroupedLinkedMap中。
GroupedLinkedMap
1.官方注释中解释了保存的是Bitmap的尺寸位图信息，保存具体的Bitmap对象显然是不合适的：1
2
3
4
5
6
7
8
9
10/**
* Similar to {@link java.util.LinkedHashMap} when access ordered except that it is access ordered
* on groups of bitmaps rather than individual objects. The idea is to be able to find the LRU
* bitmap size, rather than the LRU bitmap object. We can then remove bitmaps from the least
* recently used size of bitmap when we need to reduce our cache size.
*
* <p>For the purposes of the LRU, we count gets for a particular size of bitmap as an access, even
* if no bitmaps of that size are present. We do not count addition or removal of bitmaps as an
* access.
*/
2.GroupedLinkedMap中维护了一个head头节点，实现了双向循环链表；并将节点的信息对应key的方式保存在Map中。看看具体实现来分析：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152interface Poolable {
void offer();
}
class GroupedLinkedMap<K extends Poolable, V> {
/**
* head节点的next与prev指向本身-->
* next = prev = head;key = null
*/
private final LinkedEntry<K, V> head = new LinkedEntry<>();
private final Map<K, LinkedEntry<K, V>> keyToEntry = new HashMap<>();
public void put(K key, V value) {
LinkedEntry<K, V> entry = keyToEntry.get(key);
if (entry == null) {
entry = new LinkedEntry<>(key);
makeTail(entry);
keyToEntry.put(key, entry);
} else {
key.offer();
}
entry.add(value);
}
public V get(K key) {
LinkedEntry<K, V> entry = keyToEntry.get(key);
if (entry == null) {
entry = new LinkedEntry<>(key);
keyToEntry.put(key, entry);
} else {
key.offer();
}
makeHead(entry);
return entry.removeLast();
}
public V removeLast() {
/**
* LinkedEntry->双向循环链表的结构，head.prev相当于tail节点
*/
LinkedEntry<K, V> last = head.prev;
while (!last.equals(head)) {
V removed = last.removeLast();
if (removed != null) {
return removed;
} else {
// We will clean up empty lru entries since they are likely to have been one off or
// unusual sizes and
// are not likely to be requested again so the gc thrash should be minimal. Doing so will
// speed up our
// removeLast operation in the future and prevent our linked list from growing to
// arbitrarily large
// sizes.
removeEntry(last);
keyToEntry.remove(last.key);
last.key.offer();
}
last = last.prev;
}
return null;
}
public String toString() {
StringBuilder sb = new StringBuilder("GroupedLinkedMap( ");
LinkedEntry<K, V> current = head.next;
boolean hadAtLeastOneItem = false;
while (!current.equals(head)) {
hadAtLeastOneItem = true;
sb.append('{').append(current.key).append(':').append(current.size()).append("}, ");
current = current.next;
}
if (hadAtLeastOneItem) {
sb.delete(sb.length() - 2, sb.length());
}
return sb.append(" )").toString();
}
// Make the entry the most recently used item.
private void makeHead(LinkedEntry<K, V> entry) {
removeEntry(entry);
entry.prev = head;
entry.next = head.next;
updateEntry(entry);
}
// Make the entry the least recently used item.
private void makeTail(LinkedEntry<K, V> entry) {
removeEntry(entry);
entry.prev = head.prev;
entry.next = head;
updateEntry(entry);
}
private static <K, V> void updateEntry(LinkedEntry<K, V> entry) {
entry.next.prev = entry;
entry.prev.next = entry;
}
private static <K, V> void removeEntry(LinkedEntry<K, V> entry) {
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
}
private static class LinkedEntry<K, V> {
final K key;
/**
* 以数组保存value的值，考虑key相同的情况，如果key相同value不同，也就是key对应多个value。
* 获取的时候从数组最后一个元素依次向前
*/
private List<V> values;
LinkedEntry<K, V> next;
LinkedEntry<K, V> prev;
// Used only for the first item in the list which we will treat specially and which will not
// contain a value.
LinkedEntry() {
this(null);
}
LinkedEntry(K key) {
next = prev = this;
this.key = key;
}
public V removeLast() {
final int valueSize = size();
return valueSize > 0 ? values.remove(valueSize - 1) : null;
}
public int size() {
return values != null ? values.size() : 0;
}
public void add(V value) {
if (values == null) {
values = new ArrayList<>();
}
values.add(value);
}
}
}
head节点
1 | private final LinkedEntry<K, V> head = new LinkedEntry<>(); |
1.关键信息，head节点(虚拟节点)next、prev指向本身且key为null。
put方法(put#makeTail)
1 | public void put(K key, V value) { |
put方法完成了什么操作
1.假设，我们现在需要添加第一个元素P，逐步分析。既然是新添加的那么entry=keyToEntry.get(key)=null，根据key新实例化了一个entry(P)。后续P被置为tail节点：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34// Make the entry the least recently used item.
//将entry设置为最近最少使用的条目，(放入GroupedLinkedMap中的图片是没在使用的，缓存用于重新使用)
public void put(K key, V value) {
LinkedEntry<K, V> entry = keyToEntry.get(key);
if (entry == null) {
entry = new LinkedEntry<>(key);
makeTail(entry);
keyToEntry.put(key, entry);
} else {
key.offer();
}
entry.add(value);
}
private void makeTail(LinkedEntry<K, V> entry) {
//entry = p；
removeEntry(entry);
entry.prev = head.prev;
entry.next = head;
updateEntry(entry);
}
private static <K, V> void removeEntry(LinkedEntry<K, V> entry) {
//新增的p-->next = prev = p.
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
}
private static <K, V> void updateEntry(LinkedEntry<K, V> entry) {
entry.next.prev = entry;
entry.prev.next = entry;
}
3.
因为head.prev = head，entry.prev = head.prev = head; entry.next = head.
updateEntry(entry)中：entry.next.prev = head.prev = entry; entry.prev.next = head.next = entry
总结得：head.prev = entry head.next = entry; entry.prev = head entry.next = head.由此形成环.
4.流程图：
5.每次执行put时，总会将新增的条目item添加head节点的前驱节点也即head.pre(tail)。形成了闭合的双向循环链表。如果key已经存在了，直接将value保存在LinkedEntry中的数组中，这个也很好理解，相同的key对应了不同value，跟map不同的时，这里没有采取覆盖的方式，而是都保存了起来。符合实际开发的场景。但这样做好不好就是具体业务来统一考虑了(key对应多value)。
get()
1 |
|
1.同样的，假设获取的资源P不存在：
entry.prev = head; entry.next = head.next;
entry.next.prev = entry;entry.prev.next = entry;
调用get时，即将entry(不存在则新建)放入了后继节点–>head.nnext.
2.流程图：
removeLast()
1 |
|
1.head在初始化的时候，我们是知道对应的key=null，也即head中是不保存的value的。
2.假设GroupedLinkedMap只有一个数据，也即head.prev，head的前驱节点，while循环中removed != null成立直接返回removed。此时删除的为LinkedEntry持有数组中的value，但是此时节点还是存在的。只是value被删除了。
3.在2的基础上再次删除，removed != null = false;走else中逻辑，处理节点，并且删除map中key。而last = last.prev;(假设只有一个数据)：
last = last.prev = head.此时跳出while循环。其实处理被删除节点中数据为空的情况(values数组为空)，循环删除前驱节点中数组的数据。
