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 package org.eclipse.jgit.internal.storage.dfs;
45
46
47
48
49
50
51
52 final class DeltaBaseCache {
53 private static final int TABLE_BITS = 10;
54
55 private static final int MASK_BITS = 32 - TABLE_BITS;
56
57 private static int hash(long position) {
58 return (((int) position) << MASK_BITS) >>> MASK_BITS;
59 }
60
61 private int maxByteCount;
62 private int curByteCount;
63
64 private final Entry[] table;
65
66 private Entry lruHead;
67 private Entry lruTail;
68
69 DeltaBaseCache(DfsReader reader) {
70 this(reader.getOptions().getDeltaBaseCacheLimit());
71 }
72
73 DeltaBaseCache(int maxBytes) {
74 maxByteCount = maxBytes;
75 table = new Entry[1 << TABLE_BITS];
76 }
77
78 Entry get(DfsStreamKey key, long position) {
79 Entry e = table[hash(position)];
80 for (; e != null; e = e.tableNext) {
81 if (e.offset == position && key.equals(e.pack)) {
82 moveToHead(e);
83 return e;
84 }
85 }
86 return null;
87 }
88
89 void put(DfsStreamKey key, long offset, int objectType, byte[] data) {
90 if (data.length > maxByteCount)
91 return;
92
93 curByteCount += data.length;
94 releaseMemory();
95
96 int tableIdx = hash(offset);
97 Entry e = new Entry(key, offset, objectType, data);
98 e.tableNext = table[tableIdx];
99 table[tableIdx] = e;
100 lruPushHead(e);
101 }
102
103 private void releaseMemory() {
104 while (curByteCount > maxByteCount && lruTail != null) {
105 Entry e = lruTail;
106 curByteCount -= e.data.length;
107 lruRemove(e);
108 removeFromTable(e);
109 }
110 }
111
112 private void removeFromTable(Entry e) {
113 int tableIdx = hash(e.offset);
114 Entry p = table[tableIdx];
115
116 if (p == e) {
117 table[tableIdx] = e.tableNext;
118 return;
119 }
120
121 for (; p != null; p = p.tableNext) {
122 if (p.tableNext == e) {
123 p.tableNext = e.tableNext;
124 return;
125 }
126 }
127
128 throw new IllegalStateException(String.format(
129 "entry for %s:%d not in table",
130 e.pack, Long.valueOf(e.offset)));
131 }
132
133 private void moveToHead(Entry e) {
134 if (e != lruHead) {
135 lruRemove(e);
136 lruPushHead(e);
137 }
138 }
139
140 private void lruRemove(Entry e) {
141 Entry p = e.lruPrev;
142 Entry n = e.lruNext;
143
144 if (p != null) {
145 p.lruNext = n;
146 } else {
147 lruHead = n;
148 }
149
150 if (n != null) {
151 n.lruPrev = p;
152 } else {
153 lruTail = p;
154 }
155 }
156
157 private void lruPushHead(Entry e) {
158 Entry n = lruHead;
159 e.lruNext = n;
160 if (n != null)
161 n.lruPrev = e;
162 else
163 lruTail = e;
164
165 e.lruPrev = null;
166 lruHead = e;
167 }
168
169 int getMemoryUsed() {
170 return curByteCount;
171 }
172
173 int getMemoryUsedByLruChainForTest() {
174 int r = 0;
175 for (Entry e = lruHead; e != null; e = e.lruNext) {
176 r += e.data.length;
177 }
178 return r;
179 }
180
181 int getMemoryUsedByTableForTest() {
182 int r = 0;
183 for (int i = 0; i < table.length; i++) {
184 for (Entry e = table[i]; e != null; e = e.tableNext) {
185 r += e.data.length;
186 }
187 }
188 return r;
189 }
190
191 static class Entry {
192 final DfsStreamKey pack;
193 final long offset;
194 final int type;
195 final byte[] data;
196
197 Entry tableNext;
198 Entry lruPrev;
199 Entry lruNext;
200
201 Entry(DfsStreamKey key, long offset, int type, byte[] data) {
202 this.pack = key;
203 this.offset = offset;
204 this.type = type;
205 this.data = data;
206 }
207 }
208 }