87 * forward order, it's simply a matter of allocating an array (size is known) and
88 * back filling in reverse order. Removal of elements from the chronological list
89 * is trickier. LinkedHashMap uses a doubly linked list to give constant time
90 * removal. Immutable hash maps can't do that and maintain immutability. So we
91 * manage the chronological list the same way we manage the bins, cloning up to the
92 * point of removal. Don't panic. This cost is more than offset by the cost of
93 * cloning an entire LinkedHashMap. Plus removal is far more rare than addition.
94 * <p>
95 * One more optimization. Maps with a small number of entries don't use the hash
96 * map at all, the chronological list is used instead.
97 * <p>
98 * So the benefits from immutable arrays are; fewer objects and less copying. For
99 * immutable hash map, when no removal is involved, the number of elements per
100 * property is two (bin + chronological elements). For LinkedHashMap it is one
101 * (larger element) times the number of maps that refer to the property. For
102 * immutable hash map, addition is constant time. For LinkedHashMap it's O(N+C)
103 * since we have to clone the older map.
104 */
105 public final class PropertyHashMap implements Map <String, Property> {
106 /** Number of initial bins. Power of 2. */
107 private static final int INITIAL_BINS = 32;
108
109 /** Threshold before using bins. */
110 private static final int LIST_THRESHOLD = 8;
111
112 /** Initial map. */
113 public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();
114
115 /** Number of properties in the map. */
116 private final int size;
117
118 /** Threshold before growing the bins. */
119 private final int threshold;
120
121 /** Reverse list of all properties. */
122 private final Element list;
123
124 /** Hash map bins. */
125 private final Element[] bins;
126
127 /** All properties as an array (lazy). */
376 if (element.match(key, hashCode)) {
377 return element;
378 }
379 }
380 return null;
381 }
382
383
384 private PropertyHashMap cloneMap() {
385 return new PropertyHashMap(size, bins == null ? null : bins.clone(), list);
386 }
387
388 /**
389 * Clone {@link PropertyHashMap} to accommodate new size.
390 *
391 * @param newSize New size of {@link PropertyHashMap}.
392 *
393 * @return Cloned {@link PropertyHashMap} with new size.
394 */
395 private PropertyHashMap cloneMap(final int newSize) {
396 Element[] newBins;
397 if (bins == null && newSize <= LIST_THRESHOLD) {
398 newBins = null;
399 } else if (newSize > threshold) {
400 newBins = rehash(list, binsNeeded(newSize));
401 } else {
402 newBins = bins.clone();
403 }
404 return new PropertyHashMap(newSize, newBins, list);
405 }
406
407
408
409 /**
410 * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has
411 * been already cloned. Removes duplicates if necessary.
412 *
413 * @param property {@link Property} to add.
414 *
415 * @return New {@link PropertyHashMap}.
416 */
417 private PropertyHashMap addNoClone(final Property property) {
418 int newSize = size;
419 final String key = property.getKey();
420 Element newList = list;
421 if (bins != null) {
422 final int binIndex = binIndex(bins, key);
423 Element bin = bins[binIndex];
424 if (findElement(bin, key) != null) {
425 newSize--;
426 bin = removeFromList(bin, key);
427 newList = removeFromList(list, key);
505
506 /*
507 * Map implementation
508 */
509
510 @Override
511 public int size() {
512 return size;
513 }
514
515 @Override
516 public boolean isEmpty() {
517 return size == 0;
518 }
519
520 @Override
521 public boolean containsKey(final Object key) {
522 if (key instanceof String) {
523 return findElement((String)key) != null;
524 }
525 assert key instanceof String;
526 return false;
527 }
528
529 /**
530 * Check if the map contains a key.
531 *
532 * @param key {@link Property} key.
533 *
534 * @return {@code true} of key is in {@link PropertyHashMap}.
535 */
536 public boolean containsKey(final String key) {
537 return findElement(key) != null;
538 }
539
540 @Override
541 public boolean containsValue(final Object value) {
542 if (value instanceof Property) {
543 final Property property = (Property) value;
544 final Element element = findElement(property.getKey());
545 return element != null && element.getProperty().equals(value);
606
607 @Override
608 public Set<Entry<String, Property>> entrySet() {
609 final HashSet<Entry<String, Property>> set = new HashSet<>();
610 for (Element element = list; element != null; element = element.getLink()) {
611 set.add(element);
612 }
613 return Collections.unmodifiableSet(set);
614 }
615
616 /**
617 * List map element.
618 */
619 static final class Element implements Entry<String, Property> {
620 /** Link for list construction. */
621 private Element link;
622
623 /** Element property. */
624 private final Property property;
625
626 /** Element key. Kept separate for performance.) */
627 private final String key;
628
629 /** Element key hash code. */
630 private final int hashCode;
631
632 /*
633 * Constructors
634 */
635
636 Element(final Element link, final Property property) {
637 this.link = link;
638 this.property = property;
639 this.key = property.getKey();
640 this.hashCode = this.key.hashCode();
641 }
642
643 boolean match(final String otherKey, final int otherHashCode) {
644 return this.hashCode == otherHashCode && this.key.equals(otherKey);
645 }
646
647 /*
648 * Entry implmentation.
649 */
650
651 @Override
652 public boolean equals(final Object other) {
653 assert property != null && other != null;
654 return other instanceof Element && property.equals(((Element)other).property);
655 }
656
657 @Override
658 public String getKey() {
659 return key;
660 }
661
662 @Override
663 public Property getValue() {
664 return property;
665 }
666
667 @Override
668 public int hashCode() {
669 return hashCode;
670 }
671
672 @Override
673 public Property setValue(final Property value) {
674 throw new UnsupportedOperationException("Immutable map.");
675 }
676
677 @Override
678 public String toString() {
679 final StringBuffer sb = new StringBuffer();
680
681 sb.append('[');
682
683 Element elem = this;
684 do {
685 sb.append(elem.getValue());
686 elem = elem.link;
687 if (elem != null) {
688 sb.append(" -> ");
689 }
|
87 * forward order, it's simply a matter of allocating an array (size is known) and
88 * back filling in reverse order. Removal of elements from the chronological list
89 * is trickier. LinkedHashMap uses a doubly linked list to give constant time
90 * removal. Immutable hash maps can't do that and maintain immutability. So we
91 * manage the chronological list the same way we manage the bins, cloning up to the
92 * point of removal. Don't panic. This cost is more than offset by the cost of
93 * cloning an entire LinkedHashMap. Plus removal is far more rare than addition.
94 * <p>
95 * One more optimization. Maps with a small number of entries don't use the hash
96 * map at all, the chronological list is used instead.
97 * <p>
98 * So the benefits from immutable arrays are; fewer objects and less copying. For
99 * immutable hash map, when no removal is involved, the number of elements per
100 * property is two (bin + chronological elements). For LinkedHashMap it is one
101 * (larger element) times the number of maps that refer to the property. For
102 * immutable hash map, addition is constant time. For LinkedHashMap it's O(N+C)
103 * since we have to clone the older map.
104 */
105 public final class PropertyHashMap implements Map <String, Property> {
106 /** Number of initial bins. Power of 2. */
107 private static final int INITIAL_BINS = 16;
108
109 /** Threshold before using bins. */
110 private static final int LIST_THRESHOLD = 8;
111
112 /** Initial map. */
113 public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();
114
115 /** Number of properties in the map. */
116 private final int size;
117
118 /** Threshold before growing the bins. */
119 private final int threshold;
120
121 /** Reverse list of all properties. */
122 private final Element list;
123
124 /** Hash map bins. */
125 private final Element[] bins;
126
127 /** All properties as an array (lazy). */
376 if (element.match(key, hashCode)) {
377 return element;
378 }
379 }
380 return null;
381 }
382
383
384 private PropertyHashMap cloneMap() {
385 return new PropertyHashMap(size, bins == null ? null : bins.clone(), list);
386 }
387
388 /**
389 * Clone {@link PropertyHashMap} to accommodate new size.
390 *
391 * @param newSize New size of {@link PropertyHashMap}.
392 *
393 * @return Cloned {@link PropertyHashMap} with new size.
394 */
395 private PropertyHashMap cloneMap(final int newSize) {
396 final Element[] newBins = cloneBins(newSize);
397 return new PropertyHashMap(newSize, newBins, list);
398 }
399
400 private Element[] cloneBins(final int newSize) {
401 if (bins == null && newSize <= LIST_THRESHOLD) {
402 return null;
403 } else if (newSize > threshold) {
404 return rehash(list, binsNeeded(newSize));
405 } else {
406 return bins == null ? null : bins.clone();
407 }
408 }
409
410 /**
411 * Create a property map containing the given <code>properties</code>. The collection must not
412 * contain properties with duplicate keys or keys that represent valid array indices as this
413 * method does not perform any sanity checks.
414 *
415 * @param properties collection of properties
416 * @return the property hash map
417 */
418 public static PropertyHashMap create(final Collection<Property> properties) {
419 if (properties == null) {
420 return EMPTY_HASHMAP;
421 }
422
423 final int size = properties.size();
424 final Element[] bins = EMPTY_HASHMAP.cloneBins(size);
425 Element list = null;
426
427 for (final Property property : properties) {
428 final String key = property.getKey();
429 if (bins != null) {
430 final int binIndex = binIndex(bins, key);
431 final Element bin = bins[binIndex];
432 bins[binIndex] = new Element(bin, property);
433 }
434 list = new Element(list, property);
435 }
436 return new PropertyHashMap(size, bins, list);
437 }
438
439 /**
440 * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has
441 * been already cloned. Removes duplicates if necessary.
442 *
443 * @param property {@link Property} to add.
444 *
445 * @return New {@link PropertyHashMap}.
446 */
447 private PropertyHashMap addNoClone(final Property property) {
448 int newSize = size;
449 final String key = property.getKey();
450 Element newList = list;
451 if (bins != null) {
452 final int binIndex = binIndex(bins, key);
453 Element bin = bins[binIndex];
454 if (findElement(bin, key) != null) {
455 newSize--;
456 bin = removeFromList(bin, key);
457 newList = removeFromList(list, key);
535
536 /*
537 * Map implementation
538 */
539
540 @Override
541 public int size() {
542 return size;
543 }
544
545 @Override
546 public boolean isEmpty() {
547 return size == 0;
548 }
549
550 @Override
551 public boolean containsKey(final Object key) {
552 if (key instanceof String) {
553 return findElement((String)key) != null;
554 }
555 return false;
556 }
557
558 /**
559 * Check if the map contains a key.
560 *
561 * @param key {@link Property} key.
562 *
563 * @return {@code true} of key is in {@link PropertyHashMap}.
564 */
565 public boolean containsKey(final String key) {
566 return findElement(key) != null;
567 }
568
569 @Override
570 public boolean containsValue(final Object value) {
571 if (value instanceof Property) {
572 final Property property = (Property) value;
573 final Element element = findElement(property.getKey());
574 return element != null && element.getProperty().equals(value);
635
636 @Override
637 public Set<Entry<String, Property>> entrySet() {
638 final HashSet<Entry<String, Property>> set = new HashSet<>();
639 for (Element element = list; element != null; element = element.getLink()) {
640 set.add(element);
641 }
642 return Collections.unmodifiableSet(set);
643 }
644
645 /**
646 * List map element.
647 */
648 static final class Element implements Entry<String, Property> {
649 /** Link for list construction. */
650 private Element link;
651
652 /** Element property. */
653 private final Property property;
654
655 /*
656 * Constructors
657 */
658
659 Element(final Element link, final Property property) {
660 this.link = link;
661 this.property = property;
662 }
663
664 boolean match(final String otherKey, final int otherHashCode) {
665 final String key = property.getKey();
666 return key.hashCode() == otherHashCode && key.equals(otherKey);
667 }
668
669 /*
670 * Entry implmentation.
671 */
672
673 @Override
674 public boolean equals(final Object other) {
675 assert property != null && other != null;
676 return other instanceof Element && property.equals(((Element)other).property);
677 }
678
679 @Override
680 public String getKey() {
681 return property.getKey();
682 }
683
684 @Override
685 public Property getValue() {
686 return property;
687 }
688
689 @Override
690 public int hashCode() {
691 return property.getKey().hashCode();
692 }
693
694 @Override
695 public Property setValue(final Property value) {
696 throw new UnsupportedOperationException("Immutable map.");
697 }
698
699 @Override
700 public String toString() {
701 final StringBuffer sb = new StringBuffer();
702
703 sb.append('[');
704
705 Element elem = this;
706 do {
707 sb.append(elem.getValue());
708 elem = elem.link;
709 if (elem != null) {
710 sb.append(" -> ");
711 }
|