1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.dfs;
12
13
14
15
16
17
18
19 final class DeltaBaseCache {
20 private static final int TABLE_BITS = 10;
21
22 private static final int MASK_BITS = 32 - TABLE_BITS;
23
24 private static int hash(long position) {
25 return (((int) position) << MASK_BITS) >>> MASK_BITS;
26 }
27
28 private int maxByteCount;
29 private int curByteCount;
30
31 private final Entry[] table;
32
33 private Entry lruHead;
34 private Entry lruTail;
35
36 DeltaBaseCache(DfsReader reader) {
37 this(reader.getOptions().getDeltaBaseCacheLimit());
38 }
39
40 DeltaBaseCache(int maxBytes) {
41 maxByteCount = maxBytes;
42 table = new Entry[1 << TABLE_BITS];
43 }
44
45 Entry get(DfsStreamKey key, long position) {
46 Entry e = table[hash(position)];
47 for (; e != null; e = e.tableNext) {
48 if (e.offset == position && key.equals(e.pack)) {
49 moveToHead(e);
50 return e;
51 }
52 }
53 return null;
54 }
55
56 void put(DfsStreamKey key, long offset, int objectType, byte[] data) {
57 if (data.length > maxByteCount)
58 return;
59
60 curByteCount += data.length;
61 releaseMemory();
62
63 int tableIdx = hash(offset);
64 Entry e = new Entry(key, offset, objectType, data);
65 e.tableNext = table[tableIdx];
66 table[tableIdx] = e;
67 lruPushHead(e);
68 }
69
70 private void releaseMemory() {
71 while (curByteCount > maxByteCount && lruTail != null) {
72 Entry e = lruTail;
73 curByteCount -= e.data.length;
74 lruRemove(e);
75 removeFromTable(e);
76 }
77 }
78
79 private void removeFromTable(Entry e) {
80 int tableIdx = hash(e.offset);
81 Entry p = table[tableIdx];
82
83 if (p == e) {
84 table[tableIdx] = e.tableNext;
85 return;
86 }
87
88 for (; p != null; p = p.tableNext) {
89 if (p.tableNext == e) {
90 p.tableNext = e.tableNext;
91 return;
92 }
93 }
94
95 throw new IllegalStateException(String.format(
96 "entry for %s:%d not in table",
97 e.pack, Long.valueOf(e.offset)));
98 }
99
100 private void moveToHead(Entry e) {
101 if (e != lruHead) {
102 lruRemove(e);
103 lruPushHead(e);
104 }
105 }
106
107 private void lruRemove(Entry e) {
108 Entry p = e.lruPrev;
109 Entry n = e.lruNext;
110
111 if (p != null) {
112 p.lruNext = n;
113 } else {
114 lruHead = n;
115 }
116
117 if (n != null) {
118 n.lruPrev = p;
119 } else {
120 lruTail = p;
121 }
122 }
123
124 private void lruPushHead(Entry e) {
125 Entry n = lruHead;
126 e.lruNext = n;
127 if (n != null)
128 n.lruPrev = e;
129 else
130 lruTail = e;
131
132 e.lruPrev = null;
133 lruHead = e;
134 }
135
136 int getMemoryUsed() {
137 return curByteCount;
138 }
139
140 int getMemoryUsedByLruChainForTest() {
141 int r = 0;
142 for (Entry e = lruHead; e != null; e = e.lruNext) {
143 r += e.data.length;
144 }
145 return r;
146 }
147
148 int getMemoryUsedByTableForTest() {
149 int r = 0;
150 for (Entry t : table) {
151 for (Entry e = t; e != null; e = e.tableNext) {
152 r += e.data.length;
153 }
154 }
155 return r;
156 }
157
158 static class Entry {
159 final DfsStreamKey pack;
160 final long offset;
161 final int type;
162 final byte[] data;
163
164 Entry tableNext;
165 Entry lruPrev;
166 Entry lruNext;
167
168 Entry(DfsStreamKey key, long offset, int type, byte[] data) {
169 this.pack = key;
170 this.offset = offset;
171 this.type = type;
172 this.data = data;
173 }
174 }
175 }