484 this.loadFactor = DEFAULT_LOAD_FACTOR; 485 putMapEntries(m, false); 486 } 487 488 /** 489 * Implements Map.putAll and Map constructor. 490 * 491 * @param m the map 492 * @param evict false when initially constructing this map, else 493 * true (relayed to method afterNodeInsertion). 494 */ 495 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 496 int s = m.size(); 497 if (s > 0) { 498 if (table == null) { // pre-size 499 float ft = ((float)s / loadFactor) + 1.0F; 500 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 501 (int)ft : MAXIMUM_CAPACITY); 502 if (t > threshold) 503 threshold = tableSizeFor(t); 504 } 505 else if (s > threshold) 506 resize(); 507 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 508 K key = e.getKey(); 509 V value = e.getValue(); 510 putVal(hash(key), key, value, false, evict); 511 } 512 } 513 } 514 515 /** 516 * Returns the number of key-value mappings in this map. 517 * 518 * @return the number of key-value mappings in this map 519 */ 520 public int size() { 521 return size; 522 } 523 524 /** 525 * Returns {@code true} if this map contains no key-value mappings. 526 * 644 break; 645 p = e; 646 } 647 } 648 if (e != null) { // existing mapping for key 649 V oldValue = e.value; 650 if (!onlyIfAbsent || oldValue == null) 651 e.value = value; 652 afterNodeAccess(e); 653 return oldValue; 654 } 655 } 656 ++modCount; 657 if (++size > threshold) 658 resize(); 659 afterNodeInsertion(evict); 660 return null; 661 } 662 663 /** 664 * Initializes or doubles table size. If null, allocates in 665 * accord with initial capacity target held in field threshold. 666 * Otherwise, because we are using power-of-two expansion, the 667 * elements from each bin must either stay at same index, or move 668 * with a power of two offset in the new table. 669 * 670 * @return the table 671 */ 672 final Node<K,V>[] resize() { 673 Node<K,V>[] oldTab = table; 674 int oldCap = (oldTab == null) ? 0 : oldTab.length; 675 int oldThr = threshold; 676 int newCap, newThr = 0; 677 if (oldCap > 0) { 678 if (oldCap >= MAXIMUM_CAPACITY) { 679 threshold = Integer.MAX_VALUE; 680 return oldTab; 681 } 682 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 683 oldCap >= DEFAULT_INITIAL_CAPACITY) 684 newThr = oldThr << 1; // double threshold 685 } 686 else if (oldThr > 0) // initial capacity was placed in threshold 687 newCap = oldThr; 688 else { // zero initial threshold signifies using defaults 689 newCap = DEFAULT_INITIAL_CAPACITY; 690 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 691 } 692 if (newThr == 0) { 693 float ft = (float)newCap * loadFactor; 694 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 695 (int)ft : Integer.MAX_VALUE); 696 } 697 threshold = newThr; 698 @SuppressWarnings({"rawtypes","unchecked"}) 699 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 700 table = newTab; 701 if (oldTab != null) { 702 for (int j = 0; j < oldCap; ++j) { 703 Node<K,V> e; 704 if ((e = oldTab[j]) != null) { 705 oldTab[j] = null; 706 if (e.next == null) 707 newTab[e.hash & (newCap - 1)] = e; 708 else if (e instanceof TreeNode) 709 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 710 else { // preserve order 711 Node<K,V> loHead = null, loTail = null; 712 Node<K,V> hiHead = null, hiTail = null; 713 Node<K,V> next; 714 do { 715 next = e.next; 716 if ((e.hash & oldCap) == 0) { 717 if (loTail == null) 718 loHead = e; 719 else 720 loTail.next = e; 721 loTail = e; 722 } 723 else { 724 if (hiTail == null) 725 hiHead = e; 726 else 727 hiTail.next = e; 728 hiTail = e; 729 } 730 } while ((e = next) != null); 731 if (loTail != null) { 732 loTail.next = null; 733 newTab[j] = loHead; 734 } 735 if (hiTail != null) { 736 hiTail.next = null; 737 newTab[j + oldCap] = hiHead; 738 } 739 } 740 } 741 } 742 } 743 return newTab; 744 } 745 746 /** 747 * Replaces all linked nodes in bin at index for given hash unless | 484 this.loadFactor = DEFAULT_LOAD_FACTOR; 485 putMapEntries(m, false); 486 } 487 488 /** 489 * Implements Map.putAll and Map constructor. 490 * 491 * @param m the map 492 * @param evict false when initially constructing this map, else 493 * true (relayed to method afterNodeInsertion). 494 */ 495 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 496 int s = m.size(); 497 if (s > 0) { 498 if (table == null) { // pre-size 499 float ft = ((float)s / loadFactor) + 1.0F; 500 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 501 (int)ft : MAXIMUM_CAPACITY); 502 if (t > threshold) 503 threshold = tableSizeFor(t); 504 } else if (s > threshold) { 505 resize(s); 506 } 507 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 508 K key = e.getKey(); 509 V value = e.getValue(); 510 putVal(hash(key), key, value, false, evict); 511 } 512 } 513 } 514 515 /** 516 * Returns the number of key-value mappings in this map. 517 * 518 * @return the number of key-value mappings in this map 519 */ 520 public int size() { 521 return size; 522 } 523 524 /** 525 * Returns {@code true} if this map contains no key-value mappings. 526 * 644 break; 645 p = e; 646 } 647 } 648 if (e != null) { // existing mapping for key 649 V oldValue = e.value; 650 if (!onlyIfAbsent || oldValue == null) 651 e.value = value; 652 afterNodeAccess(e); 653 return oldValue; 654 } 655 } 656 ++modCount; 657 if (++size > threshold) 658 resize(); 659 afterNodeInsertion(evict); 660 return null; 661 } 662 663 /** 664 * Resize the table to the nearest power of two to {@code size}. Moves all items to the new table. 665 * 666 * @param size expected number of elements in the new table 667 * @return the table 668 */ 669 final Node<K, V>[] resize(int size) { 670 if (size < 0) { 671 throw new IllegalArgumentException("Negative number of elements does not make sense."); 672 } 673 Node<K, V>[] oldTable = table; 674 int oldCapacity = (oldTable == null) ? 0 : oldTable.length; 675 int newCapacity = tableSizeFor(size); 676 677 // need to resize? 678 if (newCapacity > oldCapacity) { 679 threshold = (int) ((float) newCapacity * loadFactor); 680 return createTableAndMoveElements(newCapacity, oldCapacity, oldTable); 681 } else { 682 return oldTable; 683 } 684 } 685 686 /** 687 * Initializes or doubles table size. If null, allocates in 688 * accord with initial capacity target held in field threshold. 689 * Otherwise, because we are using power-of-two expansion, the 690 * elements from each bin must either stay at same index, or move 691 * with a power of two offset in the new table. 692 * 693 * @return the table 694 */ 695 final Node<K,V>[] resize() { 696 Node<K,V>[] oldTab = table; 697 int oldCap = (oldTab == null) ? 0 : oldTab.length; 698 int oldThr = threshold; 699 int newCap, newThr = 0; 700 if (oldCap > 0) { 701 if (oldCap >= MAXIMUM_CAPACITY) { 702 threshold = Integer.MAX_VALUE; 703 return oldTab; 704 } 705 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 706 oldCap >= DEFAULT_INITIAL_CAPACITY) 707 newThr = oldThr << 1; // double threshold 708 } 709 else if (oldThr > 0) // initial capacity was placed in threshold 710 newCap = oldThr; 711 else { // zero initial threshold signifies using defaults 712 newCap = DEFAULT_INITIAL_CAPACITY; 713 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 714 } 715 if (newThr == 0) { 716 float ft = (float)newCap * loadFactor; 717 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 718 (int)ft : Integer.MAX_VALUE); 719 } 720 threshold = newThr; 721 722 return createTableAndMoveElements(newCap, oldCap, oldTab); 723 } 724 725 private Node<K, V>[] createTableAndMoveElements(int newCap, int oldCap, Node<K, V>[] oldTab) { 726 @SuppressWarnings({"rawtypes", "unchecked"}) 727 Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; 728 table = newTab; 729 if (oldTab != null) { 730 for (int j = 0; j < oldCap; ++j) { 731 Node<K, V> e; 732 if ((e = oldTab[j]) != null) { 733 oldTab[j] = null; 734 if (e.next == null) { 735 newTab[e.hash & (newCap - 1)] = e; 736 } else if (e instanceof TreeNode) { 737 ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); 738 } else { // preserve order 739 Node<K, V> loHead = null, loTail = null; 740 Node<K, V> hiHead = null, hiTail = null; 741 Node<K, V> next; 742 do { 743 next = e.next; 744 if ((e.hash & oldCap) == 0) { 745 if (loTail == null) { 746 loHead = e; 747 } else { 748 loTail.next = e; 749 } 750 loTail = e; 751 } else { 752 if (hiTail == null) { 753 hiHead = e; 754 } else { 755 hiTail.next = e; 756 } 757 hiTail = e; 758 } 759 } while ((e = next) != null); 760 if (loTail != null) { 761 loTail.next = null; 762 newTab[j] = loHead; 763 } 764 if (hiTail != null) { 765 hiTail.next = null; 766 newTab[j + oldCap] = hiHead; 767 } 768 } 769 } 770 } 771 } 772 return newTab; 773 } 774 775 /** 776 * Replaces all linked nodes in bin at index for given hash unless |