1 /*
2 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.nashorn.internal.runtime;
27
28 import java.util.Arrays;
29 import java.util.Collection;
30 import java.util.Collections;
31 import java.util.HashSet;
32 import java.util.Map;
33 import java.util.Set;
34 import jdk.nashorn.internal.runtime.options.Options;
35
36 /**
37 * Immutable hash map implementation for properties. Properties are keyed on strings
38 * or symbols (ES6). Copying and cloning is avoided by relying on immutability.
39 * <p>
40 * When adding an element to a hash table, only the head of a bin list is updated, thus
41 * an add only requires the cloning of the bins array and adding an element to the head
42 * of the bin list. Similarly for removal, only a portion of a bin list is updated.
43 * <p>
44 * For large tables with hundreds or thousands of elements, even just cloning the bins
45 * array when adding properties is an expensive operation. For this case, we put new
46 * elements in a separate list called {@link ElementQueue}.
47 * The list component is merged into the hash table at regular intervals during element
48 * insertion to keep it from growing too long. Also, when a map with a queue component
49 * is queried repeatedly, the map will replace itself with a pure hash table version
50 * of itself to optimize lookup performance.
51 * <p>
52 * A separate chronological list is kept for quick generation of keys and values, and,
53 * for rehashing. For very small maps where the overhead of the hash table would
54 * outweigh its benefits we deliberately avoid creating a hash structure and use the
55 * chronological list alone for element storage.
56 * <p>
57 * Details:
58 * <p>
59 * The main goal is to be able to retrieve properties from a map quickly, keying on
60 * the property name (String or Symbol). A secondary, but important goal, is to keep
61 * maps immutable, so that a map can be shared by multiple objects in a context.
62 * Sharing maps allows objects to be categorized as having similar properties, a
63 * fact that call site guards rely on. In this discussion, immutability allows us
64 * to significantly reduce the amount of duplication we have in our maps.
65 * <p>
66 * The simplest of immutable maps is a basic singly linked list. New properties
67 * are simply added to the head of the list. Ancestor maps are not affected by the
68 * addition, since they continue to refer to their own head. Searching is done by
69 * walking linearly though the elements until a match is found, O(N).
70 * <p>
71 * A hash map can be thought of as an optimization of a linked list map, where the
72 * linked list is broken into fragments based on hashCode(key) . An array is use
73 * to quickly reference these fragments, indexing on hashCode(key) mod tableSize
74 * (tableSize is typically a power of 2 so that the mod is a fast masking
75 * operation.) If the size of the table is sufficient large, then search time
76 * approaches O(1). In fact, most bins in a hash table are typically empty or
77 * contain a one element list.
78 * <p>
79 * For immutable hash maps, we can think of the hash map as an array of the shorter
80 * linked list maps. If we add an element to the head of one of those lists, it
81 * doesn't affect any ancestor maps. Thus adding an element to an immutable hash
82 * map only requires cloning the array and inserting an element at the head of one
83 * of the bins.
84 * <p>
85 * Using Java HashMaps we don't have enough control over the entries to allow us to
86 * implement this technique, so we are forced to clone the entire hash map.
87 * <p>
88 * Removing elements is done similarly. We clone the array and then only modify
89 * the bin containing the removed element. More often than not, the list contains
90 * only one element (or is very short), so this is not very costly. When the list
91 * has several items, we need to clone the list portion prior to the removed item.
92 * <p>
93 * Another requirement of property maps is that we need to be able to gather all
94 * properties in chronological (add) order. We have been using LinkedHashMap to
95 * provide this. For the implementation of immutable hash map, we use a singly
96 * linked list that is linked in reverse chronological order. This means we simply
97 * add new entries to the head of the list. If we need to work with the list in
98 * forward order, it's simply a matter of allocating an array (size is known) and
99 * back filling in reverse order. Removal of elements from the chronological list
100 * is trickier. LinkedHashMap uses a doubly linked list to give constant time
101 * removal. Immutable hash maps can't do that and maintain immutability. So we
102 * manage the chronological list the same way we manage the bins, cloning up to the
103 * point of removal. Don't panic. This cost is more than offset by the cost of
104 * cloning an entire LinkedHashMap. Plus removal is far more rare than addition.
105 * <p>
106 * One more optimization. Maps with a small number of entries don't use the hash
107 * map at all, the chronological list is used instead.
108 * <p>
109 * So the benefits from immutable arrays are; fewer objects and less copying. For
110 * immutable hash map, when no removal is involved, the number of elements per
111 * property is two (bin + chronological elements). For LinkedHashMap it is one
112 * (larger element) times the number of maps that refer to the property. For
113 * immutable hash map, addition is constant time. For LinkedHashMap it's O(N+C)
114 * since we have to clone the older map.
115 */
116 public final class PropertyHashMap implements Map <Object, Property> {
117 /** Number of initial bins. Power of 2. */
118 private static final int INITIAL_BINS = 32;
119
120 /** Threshold before using bins. */
121 private static final int LIST_THRESHOLD = 8;
122
123 /** Threshold before adding new elements to queue instead of directly adding to hash bins. */
124 private static final int QUEUE_THRESHOLD = Options.getIntProperty("nashorn.propmap.queue.threshold", 500);
125
126 /** Initial map. */
127 public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();
128
129 /** Number of properties in the map. */
130 private final int size;
131
132 /** Threshold before growing the bins. */
133 private final int threshold;
134
135 /** Reverse list of all properties. */
136 private final Element list;
137
138 /** Hash map bins. */
139 private Element[] bins;
140
141 /** Queue for adding elements to large maps with delayed hashing. */
142 private ElementQueue queue;
143
144 /** All properties as an array (lazy). */
145 private Property[] properties;
146
147 /**
148 * Empty map constructor.
149 */
150 private PropertyHashMap() {
151 this.size = 0;
152 this.threshold = 0;
153 this.bins = null;
154 this.queue = null;
155 this.list = null;
156 }
157
158 /**
159 * Constructor used internally to create new maps
160 *
161 * @param map the new map
162 */
163 private PropertyHashMap(final MapBuilder map) {
164 this.size = map.size;
165 if (map.qhead == null) {
166 this.bins = map.bins;
167 this.queue = null;
168 } else {
169 this.bins = null;
170 this.queue = new ElementQueue(map.qhead, map.bins);
171 }
172 this.list = map.list;
173 this.threshold = map.bins != null ? threeQuarters(map.bins.length) : 0;
174 }
175
176 /**
177 * Clone a property map, replacing a property with a new one in the same place,
178 * which is important for property iterations if a property changes types
179 * @param property old property
180 * @param newProperty new property
181 * @return new property map
182 */
183 public PropertyHashMap immutableReplace(final Property property, final Property newProperty) {
184 assert property.getKey().equals(newProperty.getKey()) : "replacing properties with different keys: '" + property.getKey() + "' != '" + newProperty.getKey() + "'";
185 assert findElement(property.getKey()) != null : "replacing property that doesn't exist in map: '" + property.getKey() + "'";
186 final MapBuilder builder = newMapBuilder(size);
187 builder.replaceProperty(property.getKey(), newProperty);
188 return new PropertyHashMap(builder);
189 }
190
191 /**
192 * Clone a {@link PropertyHashMap} and add a {@link Property}.
193 *
194 * @param property {@link Property} to add.
195 *
196 * @return New {@link PropertyHashMap}.
197 */
198 public PropertyHashMap immutableAdd(final Property property) {
199 final int newSize = size + 1;
200 MapBuilder builder = newMapBuilder(newSize);
201 builder.addProperty(property);
202 return new PropertyHashMap(builder);
203 }
204
205 /**
206 * Clone a {@link PropertyHashMap} and add an array of properties.
207 *
208 * @param newProperties Properties to add.
209 *
210 * @return New {@link PropertyHashMap}.
211 */
212 public PropertyHashMap immutableAdd(final Property... newProperties) {
213 final int newSize = size + newProperties.length;
214 MapBuilder builder = newMapBuilder(newSize);
215 for (final Property property : newProperties) {
216 builder.addProperty(property);
217 }
218 return new PropertyHashMap(builder);
219 }
220
221 /**
222 * Clone a {@link PropertyHashMap} and add a collection of properties.
223 *
224 * @param newProperties Properties to add.
225 *
226 * @return New {@link PropertyHashMap}.
227 */
228 public PropertyHashMap immutableAdd(final Collection<Property> newProperties) {
229 if (newProperties != null) {
230 final int newSize = size + newProperties.size();
231 MapBuilder builder = newMapBuilder(newSize);
232 for (final Property property : newProperties) {
233 builder.addProperty(property);
234 }
235 return new PropertyHashMap(builder);
236 }
237 return this;
238 }
239
240 /**
241 * Clone a {@link PropertyHashMap} and remove a {@link Property} based on its key.
242 *
243 * @param key Key of {@link Property} to remove.
244 *
245 * @return New {@link PropertyHashMap}.
246 */
247 public PropertyHashMap immutableRemove(final Object key) {
248 MapBuilder builder = newMapBuilder(size);
249 builder.removeProperty(key);
250 if (builder.size < size) {
251 return builder.size != 0 ? new PropertyHashMap(builder) : EMPTY_HASHMAP;
252 }
253 return this;
254 }
255
256 /**
257 * Find a {@link Property} in the {@link PropertyHashMap}.
258 *
259 * @param key Key of {@link Property} to find.
260 *
261 * @return {@link Property} matching key or {@code null} if not found.
262 */
263 public Property find(final Object key) {
264 final Element element = findElement(key);
265 return element != null ? element.getProperty() : null;
266 }
267
268 /**
269 * Return an array of properties in chronological order of adding.
270 *
271 * @return Array of all properties.
272 */
273 Property[] getProperties() {
274 if (properties == null) {
275 final Property[] array = new Property[size];
276 int i = size;
277 for (Element element = list; element != null; element = element.getLink()) {
278 array[--i] = element.getProperty();
279 }
280 properties = array;
281 }
282 return properties;
283 }
284
285 /**
286 * Returns the bin index from the key.
287 *
288 * @param bins The bins array.
289 * @param key {@link Property} key.
290 *
291 * @return The bin index.
292 */
293 private static int binIndex(final Element[] bins, final Object key) {
294 return key.hashCode() & bins.length - 1;
295 }
296
297 /**
298 * Calculate the number of bins needed to contain n properties.
299 *
300 * @param n Number of elements.
301 *
302 * @return Number of bins required.
303 */
304 private static int binsNeeded(final int n) {
305 // 50% padding
306 return 1 << 32 - Integer.numberOfLeadingZeros(n + (n >>> 1) | INITIAL_BINS - 1);
307 }
308
309 /**
310 * Used to calculate the current capacity of the bins.
311 *
312 * @param n Number of bin slots.
313 *
314 * @return 75% of n.
315 */
316 private static int threeQuarters(final int n) {
317 return (n >>> 1) + (n >>> 2);
318 }
319
320 /**
321 * Regenerate the bin table after changing the number of bins.
322 *
323 * @param list // List of all properties.
324 * @param binSize // New size of bins.
325 *
326 * @return Populated bins.
327 */
328 private static Element[] rehash(final Element list, final int binSize) {
329 final Element[] newBins = new Element[binSize];
330 for (Element element = list; element != null; element = element.getLink()) {
331 final Property property = element.getProperty();
332 final Object key = property.getKey();
333 final int binIndex = binIndex(newBins, key);
334
335 newBins[binIndex] = new Element(newBins[binIndex], property);
336 }
337 return newBins;
338 }
339
340 /**
341 * Locate an element based on key.
342 *
343 * @param key {@link Element} key.
344 *
345 * @return {@link Element} matching key or {@code null} if not found.
346 */
347 private Element findElement(final Object key) {
348 if (queue != null) {
349 return queue.find(key);
350 } else if (bins != null) {
351 final int binIndex = binIndex(bins, key);
352 return findElement(bins[binIndex], key);
353 }
354 return findElement(list, key);
355 }
356
357 /**
358 * Locate an {@link Element} based on key from a specific list.
359 *
360 * @param elementList Head of {@link Element} list
361 * @param key {@link Element} key.
362 * @return {@link Element} matching key or {@code null} if not found.
363 */
364 private static Element findElement(final Element elementList, final Object key) {
365 final int hashCode = key.hashCode();
366 for (Element element = elementList; element != null; element = element.getLink()) {
367 if (element.match(key, hashCode)) {
368 return element;
369 }
370 }
371 return null;
372 }
373
374 /**
375 * Create a {@code MapBuilder} to add new elements to.
376 *
377 * @param newSize New size of {@link PropertyHashMap}.
378 *
379 * @return {@link MapBuilder} for the new size.
380 */
381 private MapBuilder newMapBuilder(final int newSize) {
382 if (bins == null && newSize < LIST_THRESHOLD) {
383 return new MapBuilder(bins, list, size, false);
384 } else if (newSize > threshold) {
385 return new MapBuilder(rehash(list, binsNeeded(newSize)), list, size, true);
386 } else if (shouldCloneBins(size, newSize)) {
387 return new MapBuilder(cloneBins(), list, size, true);
388 } else if (queue == null) {
389 return new MapBuilder(bins, list, size, false);
390 } else {
391 return new MapBuilder(queue, list, size, false);
392 }
393 }
394
395 /**
396 * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
397 *
398 * @return the cloned bins array
399 */
400 private Element[] cloneBins() {
401 if (queue != null) {
402 return queue.cloneAndMergeBins();
403 }
404
405 return bins.clone();
406 }
407
408 /**
409 * Used on insertion to determine whether the bins array should be cloned, or we should keep
410 * using the ancestor's bins array and put new elements into the queue.
411 *
412 * @param oldSize the old map size
413 * @param newSize the new map size
414 * @return whether to clone the bins array
415 */
416 private boolean shouldCloneBins(final int oldSize, final int newSize) {
417 // For maps with less than QUEUE_THRESHOLD elements we clone the bins array on every insertion.
418 // Above that threshold we put new elements into the queue and only merge every 512 elements.
419 return newSize < QUEUE_THRESHOLD || (newSize >>> 9) > (oldSize >>> 9);
420 }
421
422 /**
423 * Removes an {@link Element} from a specific list, avoiding duplication.
424 *
425 * @param list List to remove from.
426 * @param key Key of {@link Element} to remove.
427 *
428 * @return New list with {@link Element} removed.
429 */
430 private static Element removeFromList(final Element list, final Object key) {
431 if (list == null) {
432 return null;
433 }
434 final int hashCode = key.hashCode();
435 if (list.match(key, hashCode)) {
436 return list.getLink();
437 }
438 final Element head = new Element(null, list.getProperty());
439 Element previous = head;
440 for (Element element = list.getLink(); element != null; element = element.getLink()) {
441 if (element.match(key, hashCode)) {
442 previous.setLink(element.getLink());
443 return head;
444 }
445 final Element next = new Element(null, element.getProperty());
446 previous.setLink(next);
447 previous = next;
448 }
449 return list;
450 }
451
452 // for element x. if x get link matches,
453 private static Element replaceInList(final Element list, final Object key, final Property property) {
454 assert list != null;
455 final int hashCode = key.hashCode();
456
457 if (list.match(key, hashCode)) {
458 return new Element(list.getLink(), property);
459 }
460
461 final Element head = new Element(null, list.getProperty());
462 Element previous = head;
463 for (Element element = list.getLink(); element != null; element = element.getLink()) {
464 if (element.match(key, hashCode)) {
465 previous.setLink(new Element(element.getLink(), property));
466 return head;
467 }
468 final Element next = new Element(null, element.getProperty());
469 previous.setLink(next);
470 previous = next;
471 }
472 return list;
473 }
474
475
476 /*
477 * Map implementation
478 */
479
480 @Override
481 public int size() {
482 return size;
483 }
484
485 @Override
486 public boolean isEmpty() {
487 return size == 0;
488 }
489
490 @Override
491 public boolean containsKey(final Object key) {
492 assert key instanceof String || key instanceof Symbol;
493 return findElement(key) != null;
494 }
495
496 @Override
497 public boolean containsValue(final Object value) {
498 if (value instanceof Property) {
499 final Property property = (Property) value;
500 final Element element = findElement(property.getKey());
501 return element != null && element.getProperty().equals(value);
502 }
503 return false;
504 }
505
506 @Override
507 public Property get(final Object key) {
508 assert key instanceof String || key instanceof Symbol;
509 final Element element = findElement(key);
510 return element != null ? element.getProperty() : null;
511 }
512
513 @Override
514 public Property put(final Object key, final Property value) {
515 throw new UnsupportedOperationException("Immutable map.");
516 }
517
518 @Override
519 public Property remove(final Object key) {
520 throw new UnsupportedOperationException("Immutable map.");
521 }
522
523 @Override
524 public void putAll(final Map<? extends Object, ? extends Property> m) {
525 throw new UnsupportedOperationException("Immutable map.");
526 }
527
528 @Override
529 public void clear() {
530 throw new UnsupportedOperationException("Immutable map.");
531 }
532
533 @Override
534 public Set<Object> keySet() {
535 final HashSet<Object> set = new HashSet<>();
536 for (Element element = list; element != null; element = element.getLink()) {
537 set.add(element.getKey());
538 }
539 return Collections.unmodifiableSet(set);
540 }
541
542 @Override
543 public Collection<Property> values() {
544 return Collections.unmodifiableList(Arrays.asList(getProperties()));
545 }
546
547 @Override
548 public Set<Entry<Object, Property>> entrySet() {
549 final HashSet<Entry<Object, Property>> set = new HashSet<>();
550 for (Element element = list; element != null; element = element.getLink()) {
551 set.add(element);
552 }
553 return Collections.unmodifiableSet(set);
554 }
555
556 /**
557 * List map element.
558 */
559 static final class Element implements Entry<Object, Property> {
560 /** Link for list construction. */
561 private Element link;
562
563 /** Element property. */
564 private final Property property;
565
566 /** Element key. Kept separate for performance.) */
567 private final Object key;
568
569 /** Element key hash code. */
570 private final int hashCode;
571
572 /*
573 * Constructors
574 */
575
576 Element(final Element link, final Property property) {
577 this.link = link;
578 this.property = property;
579 this.key = property.getKey();
580 this.hashCode = this.key.hashCode();
581 }
582
583 boolean match(final Object otherKey, final int otherHashCode) {
584 return this.hashCode == otherHashCode && this.key.equals(otherKey);
585 }
586
587 /*
588 * Entry implmentation.
589 */
590
591 @Override
592 public boolean equals(final Object other) {
593 assert property != null && other != null;
594 return other instanceof Element && property.equals(((Element)other).property);
595 }
596
597 @Override
598 public Object getKey() {
599 return key;
600 }
601
602 @Override
603 public Property getValue() {
604 return property;
605 }
606
607 @Override
608 public int hashCode() {
609 return hashCode;
610 }
611
612 @Override
613 public Property setValue(final Property value) {
614 throw new UnsupportedOperationException("Immutable map.");
615 }
616
617 @Override
618 public String toString() {
619 final StringBuffer sb = new StringBuffer();
620
621 sb.append('[');
622
623 Element elem = this;
624 do {
625 sb.append(elem.getValue());
626 elem = elem.link;
627 if (elem != null) {
628 sb.append(" -> ");
629 }
630 } while (elem != null);
631
632 sb.append(']');
633
634 return sb.toString();
635 }
636
637 /*
638 * Accessors
639 */
640
641 Element getLink() {
642 return link;
643 }
644
645 void setLink(final Element link) {
646 this.link = link;
647 }
648
649 Property getProperty() {
650 return property;
651 }
652 }
653
654 /**
655 * A hybrid map/list structure to add elements to the map without the need to clone and rehash the main table.
656 * This is used for large maps to reduce the overhead of adding elements. Instances of this class can replace
657 * themselves with a pure hash map version of themselves to optimize query performance.
658 */
659 private class ElementQueue {
660
661 /** List of elements not merged into bins */
662 private final Element qhead;
663
664 /** Our own bins array. Differs from original PropertyHashMap bins when queue is merged. */
665 private final Element[] qbins;
666
667 /** Count searches to trigger merging of queue into bins. */
668 int searchCount = 0;
669
670 ElementQueue(final Element qhead, final Element[] qbins) {
671 this.qhead = qhead;
672 this.qbins = qbins;
673 }
674
675 Element find(final Object key) {
676 final int binIndex = binIndex(qbins, key);
677 final Element element = findElement(qbins[binIndex], key);
678 if (element != null) {
679 return element;
680 }
681 if (qhead != null) {
682 if (++searchCount > 2) {
683 // Merge the queue into the hash bins if this map is queried more than a few times
684 final Element[] newBins = cloneAndMergeBins();
685 assert newBins != qbins;
686 PropertyHashMap.this.queue = new ElementQueue(null, newBins);
687 return PropertyHashMap.this.queue.find(key);
688 }
689 return findElement(qhead, key);
690 }
691 return null;
692 }
693
694 /**
695 * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
696 *
697 * @return the cloned bins array
698 */
699 private Element[] cloneAndMergeBins() {
700 if (qhead == null) {
701 return qbins;
702 }
703
704 final Element[] newBins = qbins.clone();
705
706 for (Element element = qhead; element != null; element = element.getLink()) {
707 final Property property = element.getProperty();
708 final Object key = property.getKey();
709 final int binIndex = binIndex(newBins, key);
710
711 newBins[binIndex] = new Element(newBins[binIndex], property);
712 }
713
714 return newBins;
715 }
716
717 }
718
719 /**
720 * A builder class used for adding, replacing, or removing elements.
721 */
722 private static class MapBuilder {
723
724 /** Bins array - may be shared with map that created us. */
725 private Element[] bins;
726 /** Whether our bins are shared */
727 private boolean hasOwnBins;
728
729 /** Queue of unmerged elements */
730 private Element qhead;
731
732 /** Full property list. */
733 private Element list;
734
735 /** Number of properties. */
736 private int size;
737
738 MapBuilder(final Element[] bins, final Element list, final int size, final boolean hasOwnBins) {
739 this.bins = bins;
740 this.hasOwnBins = hasOwnBins;
741 this.list = list;
742 this.qhead = null;
743 this.size = size;
744 }
745
746 MapBuilder(final ElementQueue queue, final Element list, final int size, final boolean hasOwnBins) {
747 this.bins = queue.qbins;
748 this.hasOwnBins = hasOwnBins;
749 this.list = list;
750 this.qhead = queue.qhead;
751 this.size = size;
752 }
753
754 /**
755 * Add a {@link Property}. Removes duplicates if necessary.
756 *
757 * @param property {@link Property} to add.
758 */
759 private void addProperty(final Property property) {
760 final Object key = property.getKey();
761
762 if (bins != null) {
763 final int binIndex = binIndex(bins, key);
764 if (findElement(bins[binIndex], key) != null) {
765 ensureOwnBins();
766 bins[binIndex] = removeExistingElement(bins[binIndex], key);
767 } else if (findElement(qhead, key) != null) {
768 qhead = removeExistingElement(qhead, key);
769 }
770 if (hasOwnBins) {
771 bins[binIndex] = new Element(bins[binIndex], property);
772 } else {
773 qhead = new Element(qhead, property);
774 }
775 } else {
776 if (findElement(list, key) != null) {
777 list = removeFromList(list, key);
778 size--;
779 }
780 }
781
782 list = new Element(list, property);
783 size++;
784 }
785
786 /**
787 * Replace an existing {@link Property} with a new one with the same key.
788 *
789 * @param key the property key
790 * @param property the property to replace the old one with
791 */
792 private void replaceProperty(final Object key, final Property property) {
793
794 if (bins != null) {
795 final int binIndex = binIndex(bins, key);
796 Element bin = bins[binIndex];
797 if (findElement(bin, key) != null) {
798 ensureOwnBins();
799 bins[binIndex] = replaceInList(bin, key, property);
800 } else if (qhead != null) {
801 qhead = replaceInList(qhead, key, property);
802 }
803 }
804
805 list = replaceInList(list, key, property);
806 }
807
808 /**
809 * Remove a {@link Property} based on its key.
810 *
811 * @param key Key of {@link Property} to remove.
812 */
813 void removeProperty(final Object key) {
814
815 if (bins != null) {
816 final int binIndex = binIndex(bins, key);
817 final Element bin = bins[binIndex];
818 if (findElement(bin, key) != null) { ;
819 if (size >= LIST_THRESHOLD) {
820 ensureOwnBins();
821 bins[binIndex] = removeFromList(bin, key);
822 } else {
823 // Go back to list-only representation for small maps
824 bins = null;
825 qhead = null;
826 }
827 } else if (findElement(qhead, key) != null) {
828 qhead = removeFromList(qhead, key);
829 }
830 }
831
832 list = removeFromList(list, key);
833 size--;
834 }
835
836 /**
837 * Removes an element known to exist from an element list and the main {@code list} and decreases {@code size}.
838 *
839 * @param element the element list
840 * @param key the key to remove
841 * @return the new element list
842 */
843 private Element removeExistingElement(Element element, Object key) {
844 size--;
845 list = removeFromList(list, key);
846 return removeFromList(element, key);
847 }
848
849 /**
850 * Make sure we own the bins we have, cloning them if necessary.
851 */
852 private void ensureOwnBins() {
853 if (!hasOwnBins) {
854 bins = bins.clone();
855 }
856 hasOwnBins = true;
857 }
858 }
859
860 }