blob: a9b84a656640cf0f11d175aa8c59ce1da9b61ca8 (
plain)
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
152
153
154
155
156
157
158
159
160
161
162
|
// Copyright 2014 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.graph;
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
/**
* Wraps collection implementation. Automatically switches from one to another implementation
* depending on the number of storing elements.
*
* <p>Effective collection implementation depends on the size of collection.
* <ul>
* <li> For 1 - singleton immutable List.
* <li> For [2..6] - ArrayList.
* <li> For [7...) - CompactHasSet.
* </ul>
*
* @param <T>
*/
final class ConcurrentCollectionWrapper<T> {
private static final int ARRAYLIST_THRESHOLD = 6;
private static final int INITIAL_HASHSET_CAPACITY = 12;
// The succs and preds set representation changes depending on its size.
// It is implemented using the following collections:
// - null for size = 0.
// - Collections$SingletonList for size = 1.
// - ArrayList(6) for size = [2..6].
// - CompactHashSet(12) for size > 6.
// These numbers were chosen based on profiling.
// TODO(dbabkin): according to VCS history this profiling info was obtained for
// ArrayList/HashSet. Then HashSet had been replaced by CompactHashSet. Optimal threshold for
// ArrayList/CompactHashSet may differ from 6.
private volatile Collection<T> collection = null;
/**
* Returns {@code Collections.unmodifiableCollection} wrapper around collection. Iteration over
* returned collection at the same time with concurrent modification will cause {@code
* java.util.ConcurrentModificationException}
*/
public Collection<T> get() {
Collection<T> collection = this.collection;
return collection == null
? Collections.emptyList()
: Collections.unmodifiableCollection(collection);
}
synchronized Collection<T> clear() {
Collection<T> old = collection;
collection = null;
return old != null ? old : Collections.emptyList();
}
public int size() {
Collection<T> collection = this.collection;
return collection == null ? 0 : collection.size();
}
/**
* Adds 'value' to wrapped collection. Replacing this collection instance for CompactHashSet from
* ArrayList.
*
* @return {@code true} if the collection was modified; {@code false} if the collection was not
* modified
*/
public synchronized boolean add(T value) {
Collection<T> collection = this.collection;
if (collection == null) {
// null -> SingletonList
this.collection = Collections.singletonList(value);
return true;
}
if (collection.contains(value)) {
// already exists in this collection
return false;
}
int previousSize = collection.size();
if (previousSize == 1) {
// SingletonList -> ArrayList
Collection<T> newList = new ArrayList<>(ARRAYLIST_THRESHOLD);
newList.addAll(collection);
newList.add(value);
this.collection = newList;
} else if (previousSize < ARRAYLIST_THRESHOLD) {
// ArrayList
collection.add(value);
} else if (previousSize == ARRAYLIST_THRESHOLD) {
// ArrayList -> CompactHashSet
Collection<T> newSet = CompactHashSet.createWithExpectedSize(INITIAL_HASHSET_CAPACITY);
newSet.addAll(collection);
newSet.add(value);
this.collection = newSet;
} else {
// HashSet
collection.add(value);
}
return true;
}
/**
* Removes 'value' from wrapped collection. Replacing this collection instance for ArrayList from
* CompactHashSet.
*
* @return {@code true} if the collection was modified; {@code false} if the set collection not
* modified
*/
public synchronized boolean remove(T value) {
Collection<T> collection = this.collection;
if (collection == null) {
// null
return false;
}
int previousSize = collection.size();
if (previousSize == 1) {
if (collection.contains(value)) {
// -> null
this.collection = null;
return true;
} else {
return false;
}
}
// now remove the value
if (collection.remove(value)) {
// may need to change representation
if (previousSize == 2) {
// -> SingletonList
List<T> list = Collections.singletonList(collection.iterator().next());
this.collection = list;
return true;
} else if (previousSize == 1 + ARRAYLIST_THRESHOLD) {
// -> ArrayList
Collection<T> newArrayList = new ArrayList<>(ARRAYLIST_THRESHOLD);
newArrayList.addAll(collection);
this.collection = newArrayList;
return true;
}
return true;
}
return false;
}
}
|
