1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.map;
18
19 import java.util.AbstractCollection;
20 import java.util.AbstractSet;
21 import java.util.ArrayList;
22 import java.util.Collection;
23 import java.util.Iterator;
24 import java.util.Map;
25 import java.util.NoSuchElementException;
26 import java.util.Objects;
27 import java.util.Set;
28
29 import org.apache.commons.collections4.KeyValue;
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 public final class StaticBucketMap<K, V> extends AbstractIterableMap<K, V> {
110
111 class BaseIterator {
112 private final ArrayList<Map.Entry<K, V>> current = new ArrayList<>();
113 private int bucket;
114 private Map.Entry<K, V> last;
115
116 public boolean hasNext() {
117 if (!current.isEmpty()) {
118 return true;
119 }
120 while (bucket < buckets.length) {
121 synchronized (locks[bucket]) {
122 Node<K, V> n = buckets[bucket];
123 while (n != null) {
124 current.add(n);
125 n = n.next;
126 }
127 bucket++;
128 if (!current.isEmpty()) {
129 return true;
130 }
131 }
132 }
133 return false;
134 }
135
136 protected Map.Entry<K, V> nextEntry() {
137 if (!hasNext()) {
138 throw new NoSuchElementException();
139 }
140 last = current.remove(current.size() - 1);
141 return last;
142 }
143
144 public void remove() {
145 if (last == null) {
146 throw new IllegalStateException();
147 }
148 StaticBucketMap.this.remove(last.getKey());
149 last = null;
150 }
151 }
152
153 private final class EntryIterator extends BaseIterator implements Iterator<Map.Entry<K, V>> {
154
155 @Override
156 public Map.Entry<K, V> next() {
157 return nextEntry();
158 }
159
160 }
161
162 private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
163
164 @Override
165 public void clear() {
166 StaticBucketMap.this.clear();
167 }
168
169 @Override
170 public boolean contains(final Object obj) {
171 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
172 final int hash = getHash(entry.getKey());
173 synchronized (locks[hash]) {
174 for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
175 if (n.equals(entry)) {
176 return true;
177 }
178 }
179 }
180 return false;
181 }
182
183 @Override
184 public Iterator<Map.Entry<K, V>> iterator() {
185 return new EntryIterator();
186 }
187
188 @Override
189 public boolean remove(final Object obj) {
190 if (!(obj instanceof Map.Entry<?, ?>)) {
191 return false;
192 }
193 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
194 final int hash = getHash(entry.getKey());
195 synchronized (locks[hash]) {
196 for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
197 if (n.equals(entry)) {
198 StaticBucketMap.this.remove(n.getKey());
199 return true;
200 }
201 }
202 }
203 return false;
204 }
205
206 @Override
207 public int size() {
208 return StaticBucketMap.this.size();
209 }
210
211 }
212
213 private final class KeyIterator extends BaseIterator implements Iterator<K> {
214
215 @Override
216 public K next() {
217 return nextEntry().getKey();
218 }
219
220 }
221
222 private final class KeySet extends AbstractSet<K> {
223
224 @Override
225 public void clear() {
226 StaticBucketMap.this.clear();
227 }
228
229 @Override
230 public boolean contains(final Object obj) {
231 return StaticBucketMap.this.containsKey(obj);
232 }
233
234 @Override
235 public Iterator<K> iterator() {
236 return new KeyIterator();
237 }
238
239 @Override
240 public boolean remove(final Object obj) {
241 final int hash = getHash(obj);
242 synchronized (locks[hash]) {
243 for (Node<K, V> n = buckets[hash]; n != null; n = n.next) {
244 final Object k = n.getKey();
245 if (Objects.equals(k, obj)) {
246 StaticBucketMap.this.remove(k);
247 return true;
248 }
249 }
250 }
251 return false;
252 }
253
254 @Override
255 public int size() {
256 return StaticBucketMap.this.size();
257 }
258
259 }
260
261
262
263
264 private static final class Lock {
265 public int size;
266 }
267
268
269
270
271 private static final class Node<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
272 protected K key;
273 protected V value;
274 protected Node<K, V> next;
275
276 @Override
277 public boolean equals(final Object obj) {
278 if (obj == this) {
279 return true;
280 }
281 if (!(obj instanceof Map.Entry<?, ?>)) {
282 return false;
283 }
284
285 final Map.Entry<?, ?> e2 = (Map.Entry<?, ?>) obj;
286 return (key == null ? e2.getKey() == null : key.equals(e2.getKey())) &&
287 (value == null ? e2.getValue() == null : value.equals(e2.getValue()));
288 }
289
290 @Override
291 public K getKey() {
292 return key;
293 }
294
295 @Override
296 public V getValue() {
297 return value;
298 }
299
300 @Override
301 public int hashCode() {
302 return (key == null ? 0 : key.hashCode()) ^
303 (value == null ? 0 : value.hashCode());
304 }
305
306 @Override
307 public V setValue(final V obj) {
308 final V retVal = value;
309 value = obj;
310 return retVal;
311 }
312 }
313
314 private final class ValueIterator extends BaseIterator implements Iterator<V> {
315
316 @Override
317 public V next() {
318 return nextEntry().getValue();
319 }
320
321 }
322
323 private final class Values extends AbstractCollection<V> {
324
325 @Override
326 public void clear() {
327 StaticBucketMap.this.clear();
328 }
329
330 @Override
331 public Iterator<V> iterator() {
332 return new ValueIterator();
333 }
334
335 @Override
336 public int size() {
337 return StaticBucketMap.this.size();
338 }
339
340 }
341
342
343 private static final int DEFAULT_BUCKETS = 255;
344
345
346 private final Node<K, V>[] buckets;
347
348
349 private final Lock[] locks;
350
351
352
353
354 public StaticBucketMap() {
355 this(DEFAULT_BUCKETS);
356 }
357
358
359
360
361
362
363
364
365
366
367
368 @SuppressWarnings("unchecked")
369 public StaticBucketMap(final int numBuckets) {
370 int size = Math.max(17, numBuckets);
371
372
373 if (size % 2 == 0) {
374 size--;
375 }
376
377 buckets = new Node[size];
378 locks = new Lock[size];
379
380 for (int i = 0; i < size; i++) {
381 locks[i] = new Lock();
382 }
383 }
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419 public void atomic(final Runnable runnable) {
420 atomic(Objects.requireNonNull(runnable, "runnable"), 0);
421 }
422
423 private void atomic(final Runnable r, final int bucket) {
424 if (bucket >= buckets.length) {
425 r.run();
426 return;
427 }
428 synchronized (locks[bucket]) {
429 atomic(r, bucket + 1);
430 }
431 }
432
433
434
435
436 @Override
437 public void clear() {
438 for (int i = 0; i < buckets.length; i++) {
439 final Lock lock = locks[i];
440 synchronized (lock) {
441 buckets[i] = null;
442 lock.size = 0;
443 }
444 }
445 }
446
447
448
449
450
451
452
453 @Override
454 public boolean containsKey(final Object key) {
455 final int hash = getHash(key);
456
457 synchronized (locks[hash]) {
458 Node<K, V> n = buckets[hash];
459
460 while (n != null) {
461 if (Objects.equals(n.key, key)) {
462 return true;
463 }
464
465 n = n.next;
466 }
467 }
468 return false;
469 }
470
471
472
473
474
475
476
477 @Override
478 public boolean containsValue(final Object value) {
479 for (int i = 0; i < buckets.length; i++) {
480 synchronized (locks[i]) {
481 Node<K, V> n = buckets[i];
482
483 while (n != null) {
484 if (Objects.equals(n.value, value)) {
485 return true;
486 }
487
488 n = n.next;
489 }
490 }
491 }
492 return false;
493 }
494
495
496
497
498
499
500 @Override
501 public Set<Map.Entry<K, V>> entrySet() {
502 return new EntrySet();
503 }
504
505
506
507
508
509
510
511 @Override
512 public boolean equals(final Object obj) {
513 if (obj == this) {
514 return true;
515 }
516 if (!(obj instanceof Map<?, ?>)) {
517 return false;
518 }
519 final Map<?, ?> other = (Map<?, ?>) obj;
520 return entrySet().equals(other.entrySet());
521 }
522
523
524
525
526
527
528
529 @Override
530 public V get(final Object key) {
531 final int hash = getHash(key);
532
533 synchronized (locks[hash]) {
534 Node<K, V> n = buckets[hash];
535
536 while (n != null) {
537 if (Objects.equals(n.key, key)) {
538 return n.value;
539 }
540
541 n = n.next;
542 }
543 }
544 return null;
545 }
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560 private int getHash(final Object key) {
561 if (key == null) {
562 return 0;
563 }
564 int hash = key.hashCode();
565 hash += ~(hash << 15);
566 hash ^= hash >>> 10;
567 hash += hash << 3;
568 hash ^= hash >>> 6;
569 hash += ~(hash << 11);
570 hash ^= hash >>> 16;
571 hash %= buckets.length;
572 return hash < 0 ? hash * -1 : hash;
573 }
574
575
576
577
578
579
580 @Override
581 public int hashCode() {
582 int hashCode = 0;
583
584 for (int i = 0; i < buckets.length; i++) {
585 synchronized (locks[i]) {
586 Node<K, V> n = buckets[i];
587
588 while (n != null) {
589 hashCode += n.hashCode();
590 n = n.next;
591 }
592 }
593 }
594 return hashCode;
595 }
596
597
598
599
600
601
602 @Override
603 public boolean isEmpty() {
604 return size() == 0;
605 }
606
607
608
609
610
611
612 @Override
613 public Set<K> keySet() {
614 return new KeySet();
615 }
616
617
618
619
620
621
622
623
624 @Override
625 public V put(final K key, final V value) {
626 final int hash = getHash(key);
627
628 synchronized (locks[hash]) {
629 Node<K, V> n = buckets[hash];
630
631 if (n == null) {
632 n = new Node<>();
633 n.key = key;
634 n.value = value;
635 buckets[hash] = n;
636 locks[hash].size++;
637 return null;
638 }
639
640
641
642
643 for (Node<K, V> next = n; next != null; next = next.next) {
644 n = next;
645
646 if (Objects.equals(n.key, key)) {
647 final V returnVal = n.value;
648 n.value = value;
649 return returnVal;
650 }
651 }
652
653
654
655 final Node<K, V> newNode = new Node<>();
656 newNode.key = key;
657 newNode.value = value;
658 n.next = newNode;
659 locks[hash].size++;
660 }
661 return null;
662 }
663
664
665
666
667
668
669
670 @Override
671 public void putAll(final Map<? extends K, ? extends V> map) {
672 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
673 put(entry.getKey(), entry.getValue());
674 }
675 }
676
677
678
679
680
681
682
683 @Override
684 public V remove(final Object key) {
685 final int hash = getHash(key);
686
687 synchronized (locks[hash]) {
688 Node<K, V> n = buckets[hash];
689 Node<K, V> prev = null;
690
691 while (n != null) {
692 if (Objects.equals(n.key, key)) {
693
694 if (null == prev) {
695
696 buckets[hash] = n.next;
697 } else {
698
699 prev.next = n.next;
700 }
701 locks[hash].size--;
702 return n.value;
703 }
704
705 prev = n;
706 n = n.next;
707 }
708 }
709 return null;
710 }
711
712
713
714
715
716
717
718 @Override
719 public int size() {
720 int cnt = 0;
721
722 for (int i = 0; i < buckets.length; i++) {
723 synchronized (locks[i]) {
724 cnt += locks[i].size;
725 }
726 }
727 return cnt;
728 }
729
730
731
732
733
734
735 @Override
736 public Collection<V> values() {
737 return new Values();
738 }
739
740 }