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