1/*
2 * Copyright (C) 2023 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
17import {
18  AbsoluteEntryIndex,
19  AbsoluteFrameIndex,
20  EntriesRange,
21  FramesRange,
22} from './index_types';
23
24export class FrameMap {
25  readonly lengthEntries: number;
26  readonly lengthFrames: number;
27
28  // These lookup tables allow to convert a "[start_entry; end_entry[" range
29  // to "[start_frame; end_frame[" in O(1) time.
30  //
31  // entryToStartFrame[i] is:
32  // - start_frame of entry_i
33  // - start_frame of the first entry_j (j > i), if entry_i has no associated frames
34  // - undefined, if all the entries with index >= i have no associated frames
35  //
36  // entryToEndFrame[i] is:
37  // - end_frame of entry_i
38  // - end_frame of the last entry_j (j < i), if entry_i has no associated frames
39  // - undefined, if all the entries with index <= i have no associated frames
40  private readonly entryToStartFrame: Array<AbsoluteFrameIndex | undefined>;
41  private readonly entryToEndFrame: Array<AbsoluteFrameIndex | undefined>;
42
43  // These lookup tables allow to convert a "[start_frame; end_frame[" range
44  // to "[start_entry; end_entry[" in O(1) time.
45  //
46  // frameToStartEntry[i] is:
47  // - start_entry of frame_i
48  // - start_entry of the first frame_j (j > i), if frame_i has no associated entries
49  // - undefined, if all the frames with index >= i have no associated entries
50  //
51  // frameToEndEntry[i] is:
52  // - end_entry of frame_i
53  // - end_entry of the last frame_j (j < i), if frame_i has no associated entries
54  // - undefined, if all the frames with index <= i have no associated entries
55  private readonly frameToStartEntry: Array<AbsoluteEntryIndex | undefined>;
56  private readonly frameToEndEntry: Array<AbsoluteEntryIndex | undefined>;
57
58  constructor(
59    lengthEntries: number,
60    lengthFrames: number,
61    entryToStartFrame: Array<AbsoluteFrameIndex | undefined>,
62    entryToEndFrame: Array<AbsoluteFrameIndex | undefined>,
63    frameToStartEntry: Array<AbsoluteEntryIndex | undefined>,
64    frameToEndEntry: Array<AbsoluteEntryIndex | undefined>,
65  ) {
66    this.lengthEntries = lengthEntries;
67    this.lengthFrames = lengthFrames;
68    this.entryToStartFrame = entryToStartFrame;
69    this.entryToEndFrame = entryToEndFrame;
70    this.frameToStartEntry = frameToStartEntry;
71    this.frameToEndEntry = frameToEndEntry;
72  }
73
74  getFramesRange(entries: EntriesRange): FramesRange | undefined {
75    entries = this.clampEntriesRangeToFitBounds(entries);
76    if (entries.start >= entries.end) {
77      return undefined;
78    }
79
80    const startFrame = this.getStartFrameOfFirstGreaterOrEqualMappedEntry(
81      entries.start,
82    );
83    const endFrame = this.getEndFrameOfLastLowerOrEqualMappedEntry(
84      entries.end - 1,
85    );
86
87    if (
88      startFrame === undefined ||
89      endFrame === undefined ||
90      startFrame >= endFrame
91    ) {
92      return undefined;
93    }
94
95    return {start: startFrame, end: endFrame};
96  }
97
98  getFullTraceFramesRange(): FramesRange | undefined {
99    return this.getFramesRange({start: 0, end: this.lengthEntries});
100  }
101
102  getEntriesRange(frames: FramesRange): EntriesRange | undefined {
103    frames = this.clampFramesRangeToFitBounds(frames);
104    if (frames.start >= frames.end) {
105      return undefined;
106    }
107
108    const startEntry = this.getStartEntryOfFirstGreaterOrEqualMappedFrame(
109      frames.start,
110    );
111    const endEntry = this.getEndEntryOfLastLowerOrEqualMappedFrame(
112      frames.end - 1,
113    );
114
115    if (
116      startEntry === undefined ||
117      endEntry === undefined ||
118      startEntry >= endEntry
119    ) {
120      return undefined;
121    }
122
123    return {start: startEntry, end: endEntry};
124  }
125
126  private getStartFrameOfFirstGreaterOrEqualMappedEntry(
127    entry: AbsoluteEntryIndex,
128  ): AbsoluteFrameIndex | undefined {
129    if (entry < 0 || entry >= this.lengthEntries) {
130      throw Error(`Entry index out of bounds: ${entry}`);
131    }
132    return this.entryToStartFrame[entry];
133  }
134
135  private getEndFrameOfLastLowerOrEqualMappedEntry(
136    entry: AbsoluteEntryIndex,
137  ): AbsoluteFrameIndex | undefined {
138    if (entry < 0 || entry >= this.lengthEntries) {
139      throw Error(`Entry index out of bounds: ${entry}`);
140    }
141    return this.entryToEndFrame[entry];
142  }
143
144  private getStartEntryOfFirstGreaterOrEqualMappedFrame(
145    frame: AbsoluteFrameIndex,
146  ): AbsoluteEntryIndex | undefined {
147    if (frame < 0 || frame >= this.lengthFrames) {
148      throw Error(`Frame index out of bounds: ${frame}`);
149    }
150    return this.frameToStartEntry[frame];
151  }
152
153  private getEndEntryOfLastLowerOrEqualMappedFrame(
154    frame: AbsoluteFrameIndex,
155  ): AbsoluteEntryIndex | undefined {
156    if (frame < 0 || frame >= this.lengthFrames) {
157      throw Error(`Frame index out of bounds: ${frame}`);
158    }
159    return this.frameToEndEntry[frame];
160  }
161
162  private clampEntriesRangeToFitBounds(entries: EntriesRange): EntriesRange {
163    return {
164      start: Math.max(entries.start, 0),
165      end: Math.min(entries.end, this.lengthEntries),
166    };
167  }
168
169  private clampFramesRangeToFitBounds(frames: FramesRange): FramesRange {
170    return {
171      start: Math.max(frames.start, 0),
172      end: Math.min(frames.end, this.lengthFrames),
173    };
174  }
175}
176