1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.file;
12
13 import java.util.concurrent.atomic.AtomicReferenceArray;
14
15 import org.eclipse.jgit.lib.AnyObjectId;
16 import org.eclipse.jgit.lib.ObjectId;
17
18
19 class UnpackedObjectCache {
20 private static final int INITIAL_BITS = 5;
21
22 private static final int MAX_BITS = 11;
23
24 private volatile Table table;
25
26 UnpackedObjectCache() {
27 table = new Table(INITIAL_BITS);
28 }
29
30 boolean isUnpacked(AnyObjectId objectId) {
31 return table.contains(objectId);
32 }
33
34 void add(AnyObjectId objectId) {
35 Table t = table;
36 if (t.add(objectId)) {
37
38
39
40 } else {
41
42
43
44
45 Table n = new Table(Math.min(t.bits + 1, MAX_BITS));
46 n.add(objectId);
47 table = n;
48 }
49 }
50
51 void remove(AnyObjectId objectId) {
52 if (isUnpacked(objectId))
53 clear();
54 }
55
56 void clear() {
57 table = new Table(INITIAL_BITS);
58 }
59
60 private static class Table {
61 private static final int MAX_CHAIN = 8;
62
63 private final AtomicReferenceArray<ObjectId> ids;
64
65 private final int shift;
66
67 final int bits;
68
69 Table(int bits) {
70 this.ids = new AtomicReferenceArray<>(1 << bits);
71 this.shift = 32 - bits;
72 this.bits = bits;
73 }
74
75 boolean contains(AnyObjectId toFind) {
76 int i = index(toFind);
77 for (int n = 0; n < MAX_CHAIN; n++) {
78 ObjectId obj = ids.get(i);
79 if (obj == null)
80 break;
81
82 if (AnyObjectId.isEqual(obj, toFind))
83 return true;
84
85 if (++i == ids.length())
86 i = 0;
87 }
88 return false;
89 }
90
91 boolean add(AnyObjectId toAdd) {
92 int i = index(toAdd);
93 for (int n = 0; n < MAX_CHAIN;) {
94 ObjectId obj = ids.get(i);
95 if (obj == null) {
96 if (ids.compareAndSet(i, null, toAdd.copy())) {
97 return true;
98 }
99 continue;
100 }
101
102 if (AnyObjectId.isEqual(obj, toAdd)) {
103 return true;
104 }
105
106 if (++i == ids.length()) {
107 i = 0;
108 }
109 n++;
110 }
111 return false;
112 }
113
114 private int index(AnyObjectId id) {
115 return id.hashCode() >>> shift;
116 }
117 }
118 }