Uh oh!
There was an error while loading. Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCoarseSet.java
More file actions
Latest commit
122 lines (111 loc) · 3.26 KB
/
Copy pathCoarseSet.java
File metadata and controls
122 lines (111 loc) · 3.26 KB
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
importjava.util.*;
importjava.util.concurrent.locks.*;
importjava.util.concurrent.atomic.*;
// Coarse Set is a collection of unique elements
// maintained as a linked list. The list of nodes
// are arranged in ascending order by their key,
// which is obtained using `hashCode()`. This
// facilitates the search of a item within the
// list. When the list is empty, it contains two
// sentinel nodes `head` and `tail` with minimum
// and maximum key values respectively. These
// sentinel nodes are not part of the set.
//
// It uses a common, coarse-grained lock, for all
// method calls. This set performs well only when
// contention is low. If however, contention is
// high, despite the performance of lock, all
// methods calls will be essential sequential. The
// main advantage of this algorithms is that its
// obviously correct.
classCoarseSet<T> extendsAbstractSet<T> {
finalLocklock;
finalAtomicIntegersize;
finalNode<T> head;
// lock: common (coarse) lock for set
// size: number of items in set
// head: points to begin of nodes in set
publicCoarseSet() {
lock = newReentrantLock();
size = newAtomicInteger(0);
head = newNode<>(null, Integer.MIN_VALUE);
head.next = newNode<>(null, Integer.MAX_VALUE);
}
// 1. Create new node beforehand.
// 2. Acquire lock before any action.
// 3. Find node after which to insert.
// 4. Add node, only if key is unique.
// 5. Increment size if node was added.
// 6. Release the lock.
@Override
publicbooleanadd(Tv) {
Node<T> x = newNode<>(v); // 1
lock.lock(); // 2
Node<T> p = findNode(x.key); // 3
booleandone = addNode(p, x); // 4
if (done) size.incrementAndGet(); // 5
lock.unlock(); // 6
returndone;
}
// 1. Acquire lock before any action.
// 2. Find node after which to remove.
// 3. Remove node, only if key matches.
// 4. Decrement size if node was removed.
// 5. Release the lock.
@Override
publicbooleanremove(Objectv) {
intk = v.hashCode();
lock.lock(); // 1
Node<T> p = findNode(k); // 2
booleandone = removeNode(p, k); // 3
if (done) size.decrementAndGet(); // 4
lock.unlock(); // 5
returndone;
}
// 1. Acquire lock before any action.
// 2. Find node previous to search key.
// 3. Check if next node matches search key.
// 4. Release the lock.
@Override
publicbooleancontains(Objectv) {
intk = v.hashCode();
lock.lock(); // 1
Node<T> p = findNode(k); // 2
booleanhas = p.next.key == k; // 3
lock.unlock(); // 4
returnhas;
}
privatebooleanaddNode(Node<T> p, Node<T> x) {
Node<T> q = p.next;
if (q.key == x.key) returnfalse;
x.next = q;
p.next = x;
returntrue;
}
privatebooleanremoveNode(Node<T> p, intk) {
Node<T> q = p.next;
if (q.key != k) returnfalse;
p.next = q.next;
returntrue;
}
privateNode<T> findNode(intk) {
Node<T> p = head;
while (p.next.key < k)
p = p.next;
returnp;
}
@Override
publicIterator<T> iterator() {
Collection<T> a = newArrayList<>();
Node<T> p = head.next;
while (p.next != null) {
a.add(p.value);
p = p.next;
}
returna.iterator();
}
@Override
publicintsize() {
returnsize.get();
}
}