RFR: 8266571: Sequenced Collections [v5]

[Stuart Marks]

On Tue, 28 Mar 2023 01:28:16 GMT, Stuart Marks <smarks at openjdk.org> wrote:

>> src/java.base/share/classes/java/util/LinkedHashMap.java line 1123:
>> 
>>> 1121: 
>>> 1122:         public V put(K key, V value) {
>>> 1123:             return base.put(key, value);
>> 
>> Why `put()` simply delegates to `base.put()` while `putAll()` below does more complex containsKey-put-putFirst procedure? I think that `putAll()` should be equivalent to `for(var e : m.entrySet()) put(e.getKey(), e.getValue());`. Am I missing something?
>
> I think you're right, you're not missing anything. The entry that is put() should always go at the end of this view, and since this is the reversed view, it should go at the front of the base map. And putAll() should follow.

OK, it turns out that it was I who was missing something. My intent was that put() on the reversed view should go "at the end." But I implemented this only for putAll() and not for put() itself. However, revisiting this, I think my intent was wrong, and the implementation was doubly wrong, because it didn't even implement the (incorrect) intent correctly.

Elsewhere you had asked whether SequencedCollection.add should be specified to go "at the end" and I demurred. In fact I think the semantics of SequencedCollection.add and for SequencedMap.put should be to add the element or entry "at the right place." For List and Deque, the right place is the end. For NavigableSet/Map the right place is in the right sorting order. For LinkedHashSet/Map, the right place is either insertion order or access order. For an insertion-ordered map or set, the order is from oldest to newest, that is, from least to most recently inserted. Therefore, the reversed view should be in the _opposite_ order, from newest to oldest.

Therefore, my statement above "put() should always go at the end of this view" is wrong.

Adding an element to the backing map should go at the end, which is the front of the reversed view. Adding an element to the reversed view should also go at the end of the backing map but the front of the reversed view.

The fix is to take out the special-case of containsKey-put-putFirst from LinkedHashMap's reversed view and to take out similar logic from LinkedHashSet's reversed view. The methods should all just end up delegating to the backing map.

(It turns out that access-ordered maps already behave correctly; an access moves the entry to the end of a LHM and to the front of the reversed view, regardless of whether the access occurred via the backing map or the reversed view.)

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/7387#discussion_r1169359933