8000 Merge "Commonize FastSafeIterableMap" into androidx-main · androidx/androidx@12e5cc0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 12e5cc0

Browse files
Treehugger RobotGerrit Code Review
Treehugger Robot
authored and
Gerrit Code Review
committed
Merge "Commonize FastSafeIterableMap" into androidx-main
2 parents ad0d903 + 4f07f10 commit 12e5cc0

File tree

5 files changed

+256
-63
lines changed

5 files changed

+256
-63
lines changed

‎lifecycle/lifecycle-runtime/src/commonMain/kotlin/androidx/lifecycle/FastSafeIterableMap.kt‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
* Copyright 2025 The Android Open Source Project
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
package androidx.lifecycle
18+
19+
internal expect class FastSafeIterableMap<K : Any, V : Any>() {
20+
21+
fun contains(key: K): Boolean
22+
23+
fun putIfAbsent(key: K, value: V): V?
24+
25+
fun remove(key: K): V?
26+
27+
fun ceil(key: K): Map.Entry<K, V>?
28+
29+
fun first(): Map.Entry<K, V>
30+
31+
fun last(): Map.Entry<K, V>
32+
33+
fun lastOrNull(): Map.Entry<K, V>?
34+
35+
fun size(): Int
36+
37+
fun forEachWithAdditions(action: (Map.Entry<K, V>) -> Unit)
38+
39+
fun forEachReversed(action: (Map.Entry<K, V>) -> Unit)
40+
}

‎lifecycle/lifecycle-runtime/src/jvmAndAndroidMain/kotlin/androidx/lifecycle/FastSafeIterableMap.kt‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/*
2+
* Copyright 2025 The Android Open Source Project
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
package androidx.lifecycle
18+
19+
@Suppress("RestrictedApi")
20+
internal actual class FastSafeIterableMap<K : Any, V : Any> {
21+
22+
private val delegate = androidx.arch.core.internal.FastSafeIterableMap<K, V>()
23+
24+
actual fun contains(key: K): Boolean {
25+
return delegate.contains(key)
26+
}
27+
28+
actual fun putIfAbsent(key: K, value: V): V? {
29+
return delegate.putIfAbsent(key, value)
30+
}
31+
32+
actual fun remove(key: K): V? {
33+
return delegate.remove(key)
34+
}
35+
36+
actual fun ceil(key: K): Map.Entry<K, V>? {
37+
return delegate.ceil(key)
38+
}
39+
40+
actual fun first(): Map.Entry<K, V> {
41+
return requireNotNull(delegate.eldest())
42+
}
43+
44+
actual fun last(): Map.Entry<K, V> {
45+
return requireNotNull(delegate.newest())
46+
}
47+
48+
actual fun lastOrNull(): Map.Entry<K, V>? {
49+
return delegate.newest()
50+
}
51+
52+
actual fun size(): Int {
53+
return delegate.size()
54+
}
55+
56+
actual fun forEachWithAdditions(action: (Map.Entry<K, V>) -> Unit) {
57+
delegate.iteratorWithAdditions().forEach(action)
58+
}
59+
60+
actual fun forEachReversed(action: (Map.Entry<K, V>) -> Unit) {
61+
delegate.descendingIterator().forEach(action)
62+
}
63+
}

‎lifecycle/lifecycle-runtime/src/jvmAndAndroidMain/kotlin/androidx/lifecycle/LifecycleRegistry.jvmAndAndroid.kt‎

Lines changed: 6 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,6 @@ package androidx.lifecycle
1717

1818
import androidx.annotation.MainThread
1919
import androidx.annotation.VisibleForTesting
20-
import androidx.arch.core.internal.FastSafeIterableMap
2120
import kotlinx.coroutines.flow.MutableStateFlow
2221
import kotlinx.coroutines.flow.StateFlow
2322
import kotlinx.coroutines.flow.asStateFlow
@@ -140,8 +139,8 @@ private constructor(provider: LifecycleOwner, private val enforceMainThread: Boo
140139
if (observerMap.size() == 0) {
141140
return true
142141
}
143-
val eldestObserverState = observerMap.eldest()!!.value.state
144-
val newestObserverState = observerMap.newest()!!.value.state
142+
val eldestObserverState = observerMap.first().value.state
143+
val newestObserverState = observerMap.last().value.state
145144
return eldestObserverState == newestObserverState && state == newestObserverState
146145
}
147146

@@ -235,11 +234,7 @@ private constructor(provider: LifecycleOwner, private val enforceMainThread: Boo
235234
}
236235

237236
private fun forwardPass(lifecycleOwner: LifecycleOwner) {
238-
@Suppress()
239-
val ascendingIterator: Iterator<Map.Entry<LifecycleObserver, ObserverWithState>> =
240-
observerMap.iteratorWithAdditions()
241-
while (ascendingIterator.hasNext() && !newEventOccurred) {
242-
val (key, observer) = ascendingIterator.next()
237+
observerMap.forEachWithAdditions { (key, observer) ->
243238
while (observer.state < state && !newEventOccurred && observerMap.contains(key)) {
244239
pushParentState(observer.state)
245240
val event =
@@ -252,9 +247,7 @@ private constructor(provider: LifecycleOwner, private val enforceMainThread: Boo
252247
}
253248

254249
private fun backwardPass(lifecycleOwner: LifecycleOwner) {
255-
val descendingIterator = observerMap.descendingIterator()
256-
while (descendingIterator.hasNext() && !newEventOccurred) {
257-
val (key, observer) = descendingIterator.next()
250+
observerMap.forEachReversed { (key, observer) ->
258251
while (observer.state > state && !newEventOccurred && observerMap.contains(key)) {
259252
val event =
260253
Event.downFrom(observer.state)
@@ -278,10 +271,10 @@ private constructor(provider: LifecycleOwner, private val enforceMainThread: Boo
278271
)
279272
while (!isSynced) {
280273
newEventOccurred = false
281-
if (state < observerMap.eldest()!!.value.state) {
274+
if (state < observerMap.first().value.state) {
282275
backwardPass(lifecycleOwner)
283276
}
284-
val newest = observerMap.newest()
277+
val newest = observerMap.lastOrNull()
285278
if (!newEventOccurred && newest != null && state > newest.value.state) {
286279
forwardPass(lifecycleOwner)
287280
}

‎lifecycle/lifecycle-runtime/src/nonJvmMain/kotlin/androidx/lifecycle/FastSafeIterableMap.kt‎

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
/*
2+
* Copyright 2025 The Android Open Source Project
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
package androidx.lifecycle
18+
19+
internal actual class FastSafeIterableMap<K : Any, V : Any> {
20+
21+
private val delegate = linkedMapOf<K, V>()
22+
23+
actual fun contains(key: K): Boolean {
24+
return delegate.containsKey(key)
25+
}
26+
27+
actual fun putIfAbsent(key: K, value: V): V? {
28+
val existing = delegate[key]
29+
if (existing != null) {
30+
return existing
31+
}
32+
delegate[key] = value
33+
return null
34+
}
35+
36+
actual fun remove(key: K): V? {
37+
return delegate.remove(key)
38+
}
39+
40+
/**
41+
* In FastSafeIterableMap (Android), `ceil` returns the PREVIOUS entry. We replicate that
42+
* behavior here.
43+
*/
44+
actual fun ceil(key: K): Map.Entry<K, V>? {
45+
if (!contains(key)) return null
46+
47+
var previous: Map.Entry<K, V>? = null
48+
49+
// Iterate over keys to avoid holding invalidatable Entry references.
50+
for (currentKey in delegate.keys) {
51+
if (currentKey == key) {
52+
return previous
53+
}
54+
// Snapshot the value to ensure we return a stable entry
55+
val value = delegate[currentKey]
56+
if (value != null) {
57+
previous = Entry(currentKey, value)
58+
}
59+
}
60+
return null
61+
}
62+
63+
actual fun first(): Map.Entry<K, V> {
64+
return delegate.entries.first()
65+
}
66+
67+
actual fun last(): Map.Entry<K, V> {
68+
return delegate.entries.last()
69+
}
70+
71+
actual fun lastOrNull(): Map.Entry<K, V>? {
72+
return delegate.entries.lastOrNull()
73+
}
74+
75+
actual fun size(): Int {
76+
return delegate.size
77+
}
78+
79+
actual fun forEachWithAdditions(action: (Map.Entry<K, V>) -> Unit) {
80+
val visited = mutableSetOf<K>()
81+
82+
// Snapshot KEYS, not entries. Keys are safe immutable references.
83+
// Copying to a list prevents CME on the iterator itself.
84+
var candidates = delegate.keys.toList()
85+
86+
while (candidates.isNotEmpty()) {
87+
for (key in candidates) {
88+
// Check if we already visited this key (optimization)
89+
if (visited.add(key)) {
90+
// Re-fetch value from the live map.
91+
// If returns null, the item was removed during the loop -> skip it.
92+
val value = delegate[key]
93+
if (value != null) {
94+
action(Entry(key, value))
95+
}
96+
}
97+
}
98+
99+
// If the map grew while we were looping, we need to process the new additions.
100+
if (delegate.size > visited.size) {
101+
candidates = delegate.keys.filter { !visited.contains(it) }
102+
} else {
103+
break
104+
}
105+
}
106+
}
107+
108+
actual fun forEachReversed(action: (Map.Entry<K, V>) -> Unit) {
109+
// Start with a safe snapshot of the current keys
110+
val keys = delegate.keys.toList()
111+
112+
// Iterate by index to avoid iterator allocation
113+
var index = keys.size - 1
114+
while (index >= 0) {
115+
val key = keys[index]
116+
117+
// Re-fetch value safely and guard against removal during iteration
118+
val value = delegate[key]
119+
if (value != null) {
120+
action(Entry(key, value))
121+
}
122+
123+
index--
124+
}
125+
}
126+
127+
/**
128+
* A simple immutable implementation of Map.Entry. Used to pass safe snapshots to callers,
129+
* preventing crashes if the backing map changes.
130+
*/
131+
private data class Entry<K, V>(override val key: K, override val value: V) : Map.Entry<K, V>
132+
}

0 commit comments

Comments
 (0)
0