keii.dev
A game framework written with osu! in mind.
1// Copyright (c) ppy Pty Ltd <contact@ppy.sh>. Licensed under the MIT Licence.
2// See the LICENCE file in the repository root for full licence text.
3
4using System;
5using System.Collections.Generic;
6using System.Diagnostics;
7using JetBrains.Annotations;
8using osu.Framework.Extensions.ObjectExtensions;
9using osu.Framework.Graphics.Containers;
10using osu.Framework.Statistics;
11
12namespace osu.Framework.Graphics.Performance
13{
14 /// <summary>
15 /// Provides time-optimised updates for lifetime change notifications.
16 /// This is used in specialised <see cref="CompositeDrawable"/>s to optimise lifetime changes (see: <see cref="LifetimeManagementContainer"/>).
17 /// </summary>
18 /// <remarks>
19 /// The time complexity of updating lifetimes is O(number of alive items).
20 /// </remarks>
21 public class LifetimeEntryManager
22 {
23 /// <summary>
24 /// Invoked immediately when a <see cref="LifetimeEntry"/> becomes alive.
25 /// </summary>
26 public event Action<LifetimeEntry> EntryBecameAlive;
27
28 /// <summary>
29 /// Invoked immediately when a <see cref="LifetimeEntry"/> becomes dead.
30 /// </summary>
31 public event Action<LifetimeEntry> EntryBecameDead;
32
33 /// <summary>
34 /// Invoked when a <see cref="LifetimeEntry"/> crosses a lifetime boundary.
35 /// </summary>
36 public event Action<LifetimeEntry, LifetimeBoundaryKind, LifetimeBoundaryCrossingDirection> EntryCrossedBoundary;
37
38 /// <summary>
39 /// Contains all the newly-added (but not yet processed) entries.
40 /// </summary>
41 private readonly List<LifetimeEntry> newEntries = new List<LifetimeEntry>();
42
43 /// <summary>
44 /// Contains all the currently-alive entries.
45 /// </summary>
46 private readonly List<LifetimeEntry> activeEntries = new List<LifetimeEntry>();
47
48 /// <summary>
49 /// Contains all entries that should come alive in the future.
50 /// </summary>
51 private readonly SortedSet<LifetimeEntry> futureEntries = new SortedSet<LifetimeEntry>(new LifetimeStartComparator());
52
53 /// <summary>
54 /// Contains all entries that were alive in the past.
55 /// </summary>
56 private readonly SortedSet<LifetimeEntry> pastEntries = new SortedSet<LifetimeEntry>(new LifetimeEndComparator());
57
58 private readonly Queue<(LifetimeEntry, LifetimeBoundaryKind, LifetimeBoundaryCrossingDirection)> eventQueue =
59 new Queue<(LifetimeEntry, LifetimeBoundaryKind, LifetimeBoundaryCrossingDirection)>();
60
61 /// <summary>
62 /// Used to ensure a stable sort if multiple entries with the same lifetime are added.
63 /// </summary>
64 private ulong currentChildId;
65
66 /// <summary>
67 /// Adds an entry.
68 /// </summary>
69 /// <param name="entry">The <see cref="LifetimeEntry"/> to add.</param>
70 public void AddEntry(LifetimeEntry entry)
71 {
72 entry.RequestLifetimeUpdate += requestLifetimeUpdate;
73 entry.ChildId = ++currentChildId;
74 entry.State = LifetimeEntryState.New;
75
76 newEntries.Add(entry);
77 }
78
79 /// <summary>
80 /// Removes an entry.
81 /// </summary>
82 /// <param name="entry">The <see cref="LifetimeEntry"/> to remove.</param>
83 /// <returns>Whether <paramref name="entry"/> was contained by this <see cref="LifetimeEntryManager"/>.</returns>
84 public bool RemoveEntry(LifetimeEntry entry)
85 {
86 entry.RequestLifetimeUpdate -= requestLifetimeUpdate;
87
88 bool removed = false;
89
90 switch (entry.State)
91 {
92 case LifetimeEntryState.New:
93 removed = newEntries.Remove(entry);
94 break;
95
96 case LifetimeEntryState.Current:
97 removed = activeEntries.Remove(entry);
98
99 if (removed)
100 EntryBecameDead?.Invoke(entry);
101
102 break;
103
104 case LifetimeEntryState.Past:
105 // Past entries may be found in the newEntries set after a lifetime change (see requestLifetimeUpdate).
106 removed = pastEntries.Remove(entry) || newEntries.Remove(entry);
107 break;
108
109 case LifetimeEntryState.Future:
110 // Future entries may be found in the newEntries set after a lifetime change (see requestLifetimeUpdate).
111 removed = futureEntries.Remove(entry) || newEntries.Remove(entry);
112 break;
113 }
114
115 if (!removed)
116 return false;
117
118 entry.ChildId = 0;
119 return true;
120 }
121
122 /// <summary>
123 /// Removes all entries.
124 /// </summary>
125 public void ClearEntries()
126 {
127 foreach (var entry in newEntries)
128 {
129 entry.RequestLifetimeUpdate -= requestLifetimeUpdate;
130 entry.ChildId = 0;
131 }
132
133 foreach (var entry in pastEntries)
134 {
135 entry.RequestLifetimeUpdate -= requestLifetimeUpdate;
136 entry.ChildId = 0;
137 }
138
139 foreach (var entry in activeEntries)
140 {
141 entry.RequestLifetimeUpdate -= requestLifetimeUpdate;
142 EntryBecameDead?.Invoke(entry);
143 entry.ChildId = 0;
144 }
145
146 foreach (var entry in futureEntries)
147 {
148 entry.RequestLifetimeUpdate -= requestLifetimeUpdate;
149 entry.ChildId = 0;
150 }
151
152 newEntries.Clear();
153 pastEntries.Clear();
154 activeEntries.Clear();
155 futureEntries.Clear();
156 }
157
158 /// <summary>
159 /// Invoked when the lifetime of an entry is going to changed.
160 /// </summary>
161 private void requestLifetimeUpdate(LifetimeEntry entry)
162 {
163 // Entries in the past/future sets need to be re-sorted to prevent the comparer from becoming unstable.
164 // To prevent, e.g. CompositeDrawable alive children changing during enumeration, the entry's state must not be updated immediately.
165 //
166 // In order to achieve the above, the entry is first removed from the past/future set (resolving the comparator stability issues)
167 // and then re-queued back onto the new entries list to be re-processed in the next Update().
168 //
169 // Note that this does not apply to entries that are in the current set, as they don't utilise a lifetime comparer.
170
171 var futureOrPastSet = futureOrPastEntries(entry.State);
172
173 if (futureOrPastSet?.Remove(entry) == true)
174 {
175 // Enqueue the entry to be processed in the next Update().
176 newEntries.Add(entry);
177 }
178 }
179
180 /// <summary>
181 /// Retrieves the sorted set for a <see cref="LifetimeEntryState"/>.
182 /// </summary>
183 /// <param name="state">The <see cref="LifetimeEntryState"/>.</param>
184 /// <returns>Either <see cref="futureEntries"/>, <see cref="pastEntries"/>, or null.</returns>
185 [CanBeNull]
186 private SortedSet<LifetimeEntry> futureOrPastEntries(LifetimeEntryState state)
187 {
188 switch (state)
189 {
190 case LifetimeEntryState.Future:
191 return futureEntries;
192
193 case LifetimeEntryState.Past:
194 return pastEntries;
195
196 default:
197 return null;
198 }
199 }
200
201 /// <summary>
202 /// Updates the lifetime of entries at a single time value.
203 /// </summary>
204 /// <param name="time">The time to update at.</param>
205 /// <returns>Whether the state of any entries changed.</returns>
206 public bool Update(double time) => Update(time, time);
207
208 /// <summary>
209 /// Updates the lifetime of entries within a given time range.
210 /// </summary>
211 /// <param name="startTime">The start of the time range.</param>
212 /// <param name="endTime">The end of the time range.</param>
213 /// <returns>Whether the state of any entries changed.</returns>
214 public bool Update(double startTime, double endTime)
215 {
216 endTime = Math.Max(endTime, startTime);
217
218 bool aliveChildrenChanged = false;
219
220 // Check for newly-added entries.
221 foreach (var entry in newEntries)
222 aliveChildrenChanged |= updateChildEntry(entry, startTime, endTime, true, true);
223 newEntries.Clear();
224
225 // Check for newly alive entries when time is increased.
226 while (futureEntries.Count > 0)
227 {
228 FrameStatistics.Increment(StatisticsCounterType.CCL);
229
230 var entry = futureEntries.Min.AsNonNull(); // guaranteed by the .Count > 0 guard.
231 Debug.Assert(entry.State == LifetimeEntryState.Future);
232
233 if (getState(entry, startTime, endTime) == LifetimeEntryState.Future)
234 break;
235
236 futureEntries.Remove(entry);
237 aliveChildrenChanged |= updateChildEntry(entry, startTime, endTime, false, true);
238 }
239
240 // Check for newly alive entries when time is decreased.
241 while (pastEntries.Count > 0)
242 {
243 FrameStatistics.Increment(StatisticsCounterType.CCL);
244
245 var entry = pastEntries.Max.AsNonNull(); // guaranteed by the .Count > 0 guard.
246 Debug.Assert(entry.State == LifetimeEntryState.Past);
247
248 if (getState(entry, startTime, endTime) == LifetimeEntryState.Past)
249 break;
250
251 pastEntries.Remove(entry);
252 aliveChildrenChanged |= updateChildEntry(entry, startTime, endTime, false, true);
253 }
254
255 // Checks for newly dead entries when time is increased/decreased.
256 foreach (var entry in activeEntries)
257 {
258 FrameStatistics.Increment(StatisticsCounterType.CCL);
259 aliveChildrenChanged |= updateChildEntry(entry, startTime, endTime, false, false);
260 }
261
262 // Remove all newly-dead entries.
263 activeEntries.RemoveAll(e => e.State != LifetimeEntryState.Current);
264
265 while (eventQueue.Count != 0)
266 {
267 var (entry, kind, direction) = eventQueue.Dequeue();
268 EntryCrossedBoundary?.Invoke(entry, kind, direction);
269 }
270
271 return aliveChildrenChanged;
272 }
273
274 /// <summary>
275 /// Updates the state of a single <see cref="LifetimeEntry"/>.
276 /// </summary>
277 /// <param name="entry">The <see cref="LifetimeEntry"/> to update.</param>
278 /// <param name="startTime">The start of the time range.</param>
279 /// <param name="endTime">The end of the time range.</param>
280 /// <param name="isNewEntry">Whether <paramref name="entry"/> is part of the new entries set.
281 /// The state may be "new" or "past"/"future", in which case it will undergo further processing to return it to the correct set.</param>
282 /// <param name="mutateActiveEntries">Whether <see cref="activeEntries"/> should be mutated by this invocation.
283 /// If <c>false</c>, the caller is expected to handle mutation of <see cref="activeEntries"/> based on any changes to the entry's state.</param>
284 /// <returns>Whether the state of <paramref name="entry"/> has changed.</returns>
285 private bool updateChildEntry(LifetimeEntry entry, double startTime, double endTime, bool isNewEntry, bool mutateActiveEntries)
286 {
287 LifetimeEntryState oldState = entry.State;
288
289 // Past/future sets don't call this function unless a state change is guaranteed.
290 Debug.Assert(!futureEntries.Contains(entry) && !pastEntries.Contains(entry));
291
292 // The entry can be in one of three states:
293 // 1. The entry was previously in the past/future sets but a lifetime change was requested. Its state is currently "past"/"future".
294 // 2. The entry is a completely new entry. Its state is currently "new".
295 // 3. The entry is currently-active. Its state is "current" but it's also in the active set.
296 Debug.Assert(oldState != LifetimeEntryState.Current || activeEntries.Contains(entry));
297
298 LifetimeEntryState newState = getState(entry, startTime, endTime);
299 Debug.Assert(newState != LifetimeEntryState.New);
300
301 if (newState == oldState)
302 {
303 // If the state hasn't changed, then there's two possibilities:
304 // 1. The entry was in the past/future sets and a lifetime change was requested. The entry needs to be added back to the past/future sets.
305 // 2. The entry is and continues to remain active.
306 if (isNewEntry)
307 futureOrPastEntries(newState)?.Add(entry);
308 else
309 Debug.Assert(newState == LifetimeEntryState.Current);
310
311 // In both cases, the entry doesn't need to be processed further as it's already in the correct state.
312 return false;
313 }
314
315 bool aliveEntriesChanged = false;
316
317 if (newState == LifetimeEntryState.Current)
318 {
319 if (mutateActiveEntries)
320 activeEntries.Add(entry);
321
322 EntryBecameAlive?.Invoke(entry);
323 aliveEntriesChanged = true;
324 }
325 else if (oldState == LifetimeEntryState.Current)
326 {
327 if (mutateActiveEntries)
328 activeEntries.Remove(entry);
329
330 EntryBecameDead?.Invoke(entry);
331 aliveEntriesChanged = true;
332 }
333
334 entry.State = newState;
335 futureOrPastEntries(newState)?.Add(entry);
336 enqueueEvents(entry, oldState, newState);
337
338 return aliveEntriesChanged;
339 }
340
341 /// <summary>
342 /// Retrieves the new state for an entry.
343 /// </summary>
344 /// <param name="entry">The <see cref="LifetimeEntry"/>.</param>
345 /// <param name="startTime">The start of the time range.</param>
346 /// <param name="endTime">The end of the time range.</param>
347 /// <returns>The state of <paramref name="entry"/>. Can be either <see cref="LifetimeEntryState.Past"/>, <see cref="LifetimeEntryState.Current"/>, or <see cref="LifetimeEntryState.Future"/>.</returns>
348 private LifetimeEntryState getState(LifetimeEntry entry, double startTime, double endTime)
349 {
350 // Consider a static entry and a moving time range:
351 // [-----------Entry-----------]
352 // [----Range----] | | (not alive)
353 // [----Range----] | (alive)
354 // | [----Range----] (alive)
355 // | [----Range----] (not alive)
356 // | | [----Range----] (not alive)
357 // | |
358
359 if (endTime < entry.LifetimeStart)
360 return LifetimeEntryState.Future;
361
362 if (startTime >= entry.LifetimeEnd)
363 return LifetimeEntryState.Past;
364
365 return LifetimeEntryState.Current;
366 }
367
368 private void enqueueEvents(LifetimeEntry entry, LifetimeEntryState oldState, LifetimeEntryState newState)
369 {
370 Debug.Assert(oldState != newState);
371
372 switch (oldState)
373 {
374 case LifetimeEntryState.Future:
375 eventQueue.Enqueue((entry, LifetimeBoundaryKind.Start, LifetimeBoundaryCrossingDirection.Forward));
376 if (newState == LifetimeEntryState.Past)
377 eventQueue.Enqueue((entry, LifetimeBoundaryKind.End, LifetimeBoundaryCrossingDirection.Forward));
378 break;
379
380 case LifetimeEntryState.Current:
381 eventQueue.Enqueue(newState == LifetimeEntryState.Past
382 ? (entry, LifetimeBoundaryKind.End, LifetimeBoundaryCrossingDirection.Forward)
383 : (entry, LifetimeBoundaryKind.Start, LifetimeBoundaryCrossingDirection.Backward));
384 break;
385
386 case LifetimeEntryState.Past:
387 eventQueue.Enqueue((entry, LifetimeBoundaryKind.End, LifetimeBoundaryCrossingDirection.Backward));
388 if (newState == LifetimeEntryState.Future)
389 eventQueue.Enqueue((entry, LifetimeBoundaryKind.Start, LifetimeBoundaryCrossingDirection.Backward));
390 break;
391 }
392 }
393
394 /// <summary>
395 /// Compares by <see cref="LifetimeEntry.LifetimeStart"/>.
396 /// </summary>
397 private sealed class LifetimeStartComparator : IComparer<LifetimeEntry>
398 {
399 public int Compare(LifetimeEntry x, LifetimeEntry y)
400 {
401 if (x == null) throw new ArgumentNullException(nameof(x));
402 if (y == null) throw new ArgumentNullException(nameof(y));
403
404 int c = x.LifetimeStart.CompareTo(y.LifetimeStart);
405 return c != 0 ? c : x.ChildId.CompareTo(y.ChildId);
406 }
407 }
408
409 /// <summary>
410 /// Compares by <see cref="LifetimeEntry.LifetimeEnd"/>.
411 /// </summary>
412 private sealed class LifetimeEndComparator : IComparer<LifetimeEntry>
413 {
414 public int Compare(LifetimeEntry x, LifetimeEntry y)
415 {
416 if (x == null) throw new ArgumentNullException(nameof(x));
417 if (y == null) throw new ArgumentNullException(nameof(y));
418
419 int c = x.LifetimeEnd.CompareTo(y.LifetimeEnd);
420 return c != 0 ? c : x.ChildId.CompareTo(y.ChildId);
421 }
422 }
423 }
424}