001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.map; 018 019import java.util.AbstractCollection; 020import java.util.AbstractSet; 021import java.util.ArrayList; 022import java.util.Collection; 023import java.util.Iterator; 024import java.util.Map; 025import java.util.NoSuchElementException; 026import java.util.Objects; 027import java.util.Set; 028 029import org.apache.commons.collections4.KeyValue; 030 031/** 032 * A StaticBucketMap is an efficient, thread-safe implementation of 033 * {@link java.util.Map} that performs well in a highly 034 * thread-contentious environment. The map supports very efficient 035 * {@link #get(Object) get}, {@link #put(Object,Object) put}, 036 * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey} 037 * operations, assuming (approximate) uniform hashing and 038 * that the number of entries does not exceed the number of buckets. If the 039 * number of entries exceeds the number of buckets or if the hash codes of the 040 * objects are not uniformly distributed, these operations have a worst case 041 * scenario that is proportional to the number of elements in the map 042 * (<i>O(n)</i>).<p> 043 * 044 * Each bucket in the hash table has its own monitor, so two threads can 045 * safely operate on the map at the same time, often without incurring any 046 * monitor contention. This means that you don't have to wrap instances 047 * of this class with {@link java.util.Collections#synchronizedMap(Map)}; 048 * instances are already thread-safe. Unfortunately, however, this means 049 * that this map implementation behaves in ways you may find disconcerting. 050 * Bulk operations, such as {@link #putAll(Map) putAll} or the 051 * {@link Collection#retainAll(Collection) retainAll} operation in collection 052 * views, are <i>not</i> atomic. If two threads are simultaneously 053 * executing 054 * 055 * <pre> 056 * staticBucketMapInstance.putAll(map); 057 * </pre> 058 * 059 * and 060 * 061 * <pre> 062 * staticBucketMapInstance.entrySet().removeAll(map.entrySet()); 063 * </pre> 064 * 065 * then the results are generally random. Those two statement could cancel 066 * each other out, leaving {@code staticBucketMapInstance} essentially 067 * unchanged, or they could leave some random subset of {@code map} in 068 * {@code staticBucketMapInstance}.<p> 069 * 070 * Also, much like an encyclopedia, the results of {@link #size()} and 071 * {@link #isEmpty()} are out-of-date as soon as they are produced.<p> 072 * 073 * The iterators returned by the collection views of this class are <i>not</i> 074 * fail-fast. They will <i>never</i> raise a 075 * {@link java.util.ConcurrentModificationException}. Keys and values 076 * added to the map after the iterator is created do not necessarily appear 077 * during iteration. Similarly, the iterator does not necessarily fail to 078 * return keys and values that were removed after the iterator was created.<p> 079 * 080 * Finally, unlike {@link java.util.HashMap}-style implementations, this 081 * class <i>never</i> rehashes the map. The number of buckets is fixed 082 * at construction time and never altered. Performance may degrade if 083 * you do not allocate enough buckets upfront.<p> 084 * 085 * The {@link #atomic(Runnable)} method is provided to allow atomic iterations 086 * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic} 087 * will basically result in a map that's slower than an ordinary synchronized 088 * {@link java.util.HashMap}. 089 * 090 * Use this class if you do not require reliable bulk operations and 091 * iterations, or if you can make your own guarantees about how bulk 092 * operations will affect the map.<p> 093 * 094 * @param <K> the type of the keys in this map 095 * @param <V> the type of the values in this map 096 * @since 3.0 (previously in main package v2.1) 097 */ 098public final class StaticBucketMap<K, V> extends AbstractIterableMap<K, V> { 099 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 * The lock object, which also includes a count of the nodes in this lock. 250 */ 251 private static final class Lock { 252 public int size; 253 } 254 255 /** 256 * The Map.Entry for the StaticBucketMap. 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 /** The default number of buckets to use */ 330 private static final int DEFAULT_BUCKETS = 255; 331 332 /** The array of buckets, where the actual data is held */ 333 private final Node<K, V>[] buckets; 334 335 /** The matching array of locks */ 336 private final Lock[] locks; 337 338 /** 339 * Initializes the map with the default number of buckets (255). 340 */ 341 public StaticBucketMap() { 342 this(DEFAULT_BUCKETS); 343 } 344 345 /** 346 * Initializes the map with a specified number of buckets. The number 347 * of buckets is never below 17, and is always an odd number (StaticBucketMap 348 * ensures this). The number of buckets is inversely proportional to the 349 * chances for thread contention. The fewer buckets, the more chances for 350 * thread contention. The more buckets the fewer chances for thread 351 * contention. 352 * 353 * @param numBuckets the number of buckets for this map 354 */ 355 @SuppressWarnings("unchecked") 356 public StaticBucketMap(final int numBuckets) { 357 int size = Math.max(17, numBuckets); 358 359 // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution) 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 * Prevents any operations from occurring on this map while the 374 * given {@link Runnable} executes. This method can be used, for 375 * instance, to execute a bulk operation atomically: 376 * 377 * <pre> 378 * staticBucketMapInstance.atomic(new Runnable() { 379 * public void run() { 380 * staticBucketMapInstance.putAll(map); 381 * } 382 * }); 383 * </pre> 384 * 385 * It can also be used if you need a reliable iterator: 386 * 387 * <pre> 388 * staticBucketMapInstance.atomic(new Runnable() { 389 * public void run() { 390 * Iterator iterator = staticBucketMapInstance.iterator(); 391 * while (iterator.hasNext()) { 392 * foo(iterator.next(); 393 * } 394 * } 395 * }); 396 * </pre> 397 * 398 * <b>Implementation note:</b> This method requires a lot of time 399 * and a ton of stack space. Essentially a recursive algorithm is used 400 * to enter each bucket's monitor. If you have twenty thousand buckets 401 * in your map, then the recursive method will be invoked twenty thousand 402 * times. You have been warned. 403 * 404 * @param runnable the code to execute atomically 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 * Clears the map of all entries. 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 * Checks if the map contains the specified key. 436 * 437 * @param key the key to check 438 * @return true if found 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 * Checks if the map contains the specified value. 460 * 461 * @param value the value to check 462 * @return true if found 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 * Gets the entry set. 484 * 485 * @return the entry set 486 */ 487 @Override 488 public Set<Map.Entry<K, V>> entrySet() { 489 return new EntrySet(); 490 } 491 492 /** 493 * Compares this map to another, as per the Map specification. 494 * 495 * @param obj the object to compare to 496 * @return true if equal 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 * Gets the value associated with the key. 512 * 513 * @param key the key to retrieve 514 * @return the associated value 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 * Determine the exact hash entry for the key. The hash algorithm 536 * is rather simplistic, but it does the job: 537 * 538 * <pre> 539 * He = |Hk mod n| 540 * </pre> 541 * 542 * <p> 543 * He is the entry's hashCode, Hk is the key's hashCode, and n is 544 * the number of buckets. 545 * </p> 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 * Gets the hash code, as per the Map specification. 564 * 565 * @return the hash code 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 * Checks if the size is currently zero. 586 * 587 * @return true if empty 588 */ 589 @Override 590 public boolean isEmpty() { 591 return size() == 0; 592 } 593 594 /** 595 * Gets the key set. 596 * 597 * @return the key set 598 */ 599 @Override 600 public Set<K> keySet() { 601 return new KeySet(); 602 } 603 604 /** 605 * Puts a new key value mapping into the map. 606 * 607 * @param key the key to use 608 * @param value the value to use 609 * @return the previous mapping for the key 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 // Set n to the last node in the linked list. Check each key along the way 628 // If the key is found, then change the value of that node and return 629 // the old value. 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 // The key was not found in the current list of nodes, add it to the end 641 // in a new node. 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 * Puts all the entries from the specified map into this map. 653 * This operation is <b>not atomic</b> and may have undesired effects. 654 * 655 * @param map the map of entries to add 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 * Removes the specified key from the map. 666 * 667 * @param key the key to remove 668 * @return the previous value at this key 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 // Remove this node from the linked list of nodes. 681 if (null == prev) { 682 // This node was the head, set the next node to be the new head. 683 buckets[hash] = n.next; 684 } else { 685 // Set the next node of the previous node to be the node after this one. 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 * Gets the current size of the map. 701 * The value is computed fresh each time the method is called. 702 * 703 * @return the current size 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 * Gets the values. 719 * 720 * @return the values 721 */ 722 @Override 723 public Collection<V> values() { 724 return new Values(); 725 } 726 727}