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 77 if (entries.start >= entries.end) { 78 return undefined; 79 } 80 81 const startFrame = this.getStartFrameOfFirstGreaterOrEqualMappedEntry( 82 entries.start, 83 ); 84 const endFrame = this.getEndFrameOfLastLowerOrEqualMappedEntry( 85 entries.end - 1, 86 ); 87 88 if ( 89 startFrame === undefined || 90 endFrame === undefined || 91 startFrame >= endFrame 92 ) { 93 return undefined; 94 } 95 96 return {start: startFrame, end: endFrame}; 97 } 98 99 getFullTraceFramesRange(): FramesRange | undefined { 100 return this.getFramesRange({start: 0, end: this.lengthEntries}); 101 } 102 103 getEntriesRange(frames: FramesRange): EntriesRange | undefined { 104 frames = this.clampFramesRangeToFitBounds(frames); 105 if (frames.start >= frames.end) { 106 return undefined; 107 } 108 109 const startEntry = this.getStartEntryOfFirstGreaterOrEqualMappedFrame( 110 frames.start, 111 ); 112 const endEntry = this.getEndEntryOfLastLowerOrEqualMappedFrame( 113 frames.end - 1, 114 ); 115 116 if ( 117 startEntry === undefined || 118 endEntry === undefined || 119 startEntry >= endEntry 120 ) { 121 return undefined; 122 } 123 124 return {start: startEntry, end: endEntry}; 125 } 126 127 private getStartFrameOfFirstGreaterOrEqualMappedEntry( 128 entry: AbsoluteEntryIndex, 129 ): AbsoluteFrameIndex | undefined { 130 if (entry < 0 || entry >= this.lengthEntries) { 131 throw new Error(`Entry index out of bounds: ${entry}`); 132 } 133 return this.entryToStartFrame[entry]; 134 } 135 136 private getEndFrameOfLastLowerOrEqualMappedEntry( 137 entry: AbsoluteEntryIndex, 138 ): AbsoluteFrameIndex | undefined { 139 if (entry < 0 || entry >= this.lengthEntries) { 140 throw new Error(`Entry index out of bounds: ${entry}`); 141 } 142 return this.entryToEndFrame[entry]; 143 } 144 145 private getStartEntryOfFirstGreaterOrEqualMappedFrame( 146 frame: AbsoluteFrameIndex, 147 ): AbsoluteEntryIndex | undefined { 148 if (frame < 0 || frame >= this.lengthFrames) { 149 throw new Error(`Frame index out of bounds: ${frame}`); 150 } 151 return this.frameToStartEntry[frame]; 152 } 153 154 private getEndEntryOfLastLowerOrEqualMappedFrame( 155 frame: AbsoluteFrameIndex, 156 ): AbsoluteEntryIndex | undefined { 157 if (frame < 0 || frame >= this.lengthFrames) { 158 throw new Error(`Frame index out of bounds: ${frame}`); 159 } 160 return this.frameToEndEntry[frame]; 161 } 162 163 private clampEntriesRangeToFitBounds(entries: EntriesRange): EntriesRange { 164 return { 165 start: Math.max(entries.start, 0), 166 end: Math.min(entries.end, this.lengthEntries), 167 }; 168 } 169 170 private clampFramesRangeToFitBounds(frames: FramesRange): FramesRange { 171 return { 172 start: Math.max(frames.start, 0), 173 end: Math.min(frames.end, this.lengthFrames), 174 }; 175 } 176} 177