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