1 /* 2 * Copyright (C) 2020 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 com.android.timezone.location.storage.tzs2range.write; 18 19 import com.android.timezone.location.storage.block.write.BlockFileWriter; 20 import com.android.timezone.location.storage.block.write.BlockWriter; 21 import com.android.timezone.location.storage.block.write.EmptyBlockWriter; 22 import com.android.timezone.location.storage.s2.S2Support; 23 import com.android.timezone.location.storage.tzs2range.SuffixTableRange; 24 import com.android.timezone.location.storage.tzs2range.SuffixTableSharedData; 25 import com.android.timezone.location.storage.tzs2range.TzS2Range; 26 import com.android.timezone.location.storage.tzs2range.TzS2RangeFileFormat; 27 28 import java.io.File; 29 import java.io.IOException; 30 import java.util.ArrayDeque; 31 import java.util.ArrayList; 32 import java.util.Deque; 33 import java.util.Iterator; 34 import java.util.List; 35 36 /** Writes a TZ S2 data file. */ 37 public final class TzS2RangeFileWriter implements AutoCloseable { 38 39 private final HeaderBlockWriter mHeaderBlockWriter; 40 41 private final List<BlockWriter> mSuffixTableBlockWriters = new ArrayList<>(); 42 43 private final BlockFileWriter mBlockFileWriter; 44 45 private final BankedTzIdSetsPacker mBankedTzIdSetsPacker; 46 47 private final TzS2RangeFileFormat mFileFormat; 48 TzS2RangeFileWriter(TzS2RangeFileFormat fileFormat, BlockFileWriter blockFileWriter)49 private TzS2RangeFileWriter(TzS2RangeFileFormat fileFormat, BlockFileWriter blockFileWriter) 50 throws IOException { 51 mBlockFileWriter = blockFileWriter; 52 mFileFormat = fileFormat; 53 54 mHeaderBlockWriter = HeaderBlockWriter.create(fileFormat); 55 mBankedTzIdSetsPacker = mHeaderBlockWriter.getBankedTzIdSetsPacker(); 56 } 57 58 /** Opens a file for writing with the specified format. */ open(File outFile, TzS2RangeFileFormat fileFormat)59 public static TzS2RangeFileWriter open(File outFile, TzS2RangeFileFormat fileFormat) 60 throws IOException { 61 BlockFileWriter writer = BlockFileWriter.open( 62 TzS2RangeFileFormat.MAGIC, TzS2RangeFileFormat.VERSION, outFile); 63 return new TzS2RangeFileWriter(fileFormat, writer); 64 } 65 66 /** 67 * Process the set of ranges to store in the file, splitting ranges as needed to fit them into 68 * suffix tables. The ranges must be of the expected S2 level and ordered by cell ID. 69 */ processRanges(Iterator<TzS2Range> ranges)70 public void processRanges(Iterator<TzS2Range> ranges) throws IOException { 71 PushBackIterator<TzS2Range> pushBackIterator = new PushBackIterator<>(ranges); 72 73 // For each prefix value, collect all the ranges that match. 74 for (int currentPrefix = 0; 75 currentPrefix <= mFileFormat.getMaxPrefixValue(); 76 currentPrefix++) { 77 78 // Step 1: 79 // populate samePrefixRanges, which holds ranges that have a prefix of currentPrefix. 80 List<TzS2Range> samePrefixRanges = 81 collectSamePrefixRanges(pushBackIterator, currentPrefix); 82 83 // Step 2: Write samePrefixRanges to a suffix table. 84 BlockWriter blockWriter = writeSamePrefixRanges(currentPrefix, samePrefixRanges); 85 mSuffixTableBlockWriters.add(blockWriter); 86 } 87 88 // At this point there should be no data left. 89 if (pushBackIterator.hasNext()) { 90 throw new IllegalStateException("Unexpected ranges left at the end."); 91 } 92 } 93 collectSamePrefixRanges( PushBackIterator<TzS2Range> pushBackIterator, int currentPrefix)94 private List<TzS2Range> collectSamePrefixRanges( 95 PushBackIterator<TzS2Range> pushBackIterator, int currentPrefix) { 96 97 List<TzS2Range> samePrefixRanges = new ArrayList<>(); 98 99 while (pushBackIterator.hasNext()) { 100 TzS2Range currentRange = pushBackIterator.next(); 101 102 long startCellId = currentRange.getStartCellId(); 103 if (mFileFormat.getS2Level() != S2Support.getS2Level(startCellId)) { 104 throw new IllegalArgumentException( 105 "Input data level does not match file format level"); 106 } 107 int startCellPrefix = mFileFormat.extractPrefixValueFromCellId(startCellId); 108 if (startCellPrefix != currentPrefix) { 109 if (startCellPrefix < currentPrefix) { 110 throw new IllegalStateException("Prefix out of order:" 111 + " currentPrefixValue=" + currentPrefix 112 + " startCellPrefixValue=" + startCellPrefix); 113 } 114 // The next range is for a later prefix. Put it back and move to step 2. 115 pushBackIterator.pushBack(currentRange); 116 break; 117 } 118 119 long endCellId = currentRange.getEndCellId(); 120 if (mFileFormat.getS2Level() != S2Support.getS2Level(endCellId)) { 121 throw new IllegalArgumentException("endCellId in range " + currentRange 122 + " has the wrong S2 level"); 123 } 124 125 // Split ranges if they span a prefix. 126 int endCellPrefixValue = mFileFormat.extractPrefixValueFromCellId(endCellId); 127 if (startCellPrefix != endCellPrefixValue) { 128 // Create a range for the current prefix. 129 { 130 long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0); 131 TzS2Range tzS2Range = 132 new TzS2Range(startCellId, newEndCellId, currentRange.getTzIdSet()); 133 samePrefixRanges.add(tzS2Range); 134 } 135 136 Deque<TzS2Range> otherRanges = new ArrayDeque<>(); 137 // Intermediate prefixes. 138 startCellPrefix = startCellPrefix + 1; 139 while (startCellPrefix != endCellPrefixValue) { 140 long newStartCellId = mFileFormat.createCellId(startCellPrefix, 0); 141 long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0); 142 TzS2Range tzS2Range = new TzS2Range( 143 newStartCellId, newEndCellId, currentRange.getTzIdSet()); 144 otherRanges.add(tzS2Range); 145 startCellPrefix++; 146 } 147 148 // Final prefix. 149 { 150 long newStartCellId = mFileFormat.createCellId(endCellPrefixValue, 0); 151 if (newStartCellId != endCellId) { 152 TzS2Range tzS2Range = new TzS2Range( 153 newStartCellId, endCellId, currentRange.getTzIdSet()); 154 otherRanges.add(tzS2Range); 155 } 156 } 157 158 // Push back the ranges in reverse order so they come back out in sorted order. 159 while (!otherRanges.isEmpty()) { 160 pushBackIterator.pushBack(otherRanges.removeLast()); 161 } 162 break; 163 } else { 164 samePrefixRanges.add(currentRange); 165 } 166 } 167 return samePrefixRanges; 168 } 169 writeSamePrefixRanges(int currentPrefix, List<TzS2Range> samePrefixRanges)170 private BlockWriter writeSamePrefixRanges(int currentPrefix, List<TzS2Range> samePrefixRanges) 171 throws IOException { 172 BlockWriter blockWriter; 173 if (samePrefixRanges.size() == 0) { 174 // Add an empty block. 175 blockWriter = SuffixTableWriter.createEmptyBlockWriter(); 176 } else { 177 // Create a suffix table block. 178 179 // Handle the TZ IDs sets to store. 180 List<List<String>> uniqueIdSets = 181 BankedTzIdSetsPacker.extractUniqueTzIdSets(samePrefixRanges); 182 BankedTzIdSetsPacker.BankHelper bankHelper = 183 mBankedTzIdSetsPacker.addTzIdSets(uniqueIdSets); 184 185 SuffixTableSharedData sharedData = 186 new SuffixTableSharedData(currentPrefix, bankHelper.getId()); 187 SuffixTableWriter suffixTableWriter = 188 SuffixTableWriter.createPopulated(mFileFormat, sharedData); 189 TzS2Range lastRange = null; 190 for (TzS2Range currentRange : samePrefixRanges) { 191 // Validate ranges don't overlap. 192 if (lastRange != null) { 193 if (lastRange.overlaps(currentRange)) { 194 throw new IllegalStateException("lastRange=" + lastRange + " overlaps" 195 + " currentRange=" + currentRange); 196 } 197 } 198 lastRange = currentRange; 199 int tzIdSetId = bankHelper.getTzIdSetId(currentRange.getTzIdSet()); 200 201 // Split the range so it fits. 202 final int maxRangeLength = mFileFormat.getTableEntryMaxRangeLengthValue(); 203 long startCellId = currentRange.getStartCellId(); 204 long endCellId = currentRange.getEndCellId(); 205 int rangeLength = mFileFormat.calculateRangeLength(startCellId, endCellId); 206 while (rangeLength > maxRangeLength) { 207 long newEndCellId = S2Support.offsetCellId(startCellId, maxRangeLength); 208 SuffixTableRange suffixTableRange = 209 new SuffixTableRange(startCellId, newEndCellId, tzIdSetId); 210 suffixTableWriter.addRange(suffixTableRange); 211 startCellId = newEndCellId; 212 rangeLength = mFileFormat.calculateRangeLength(startCellId, endCellId); 213 } 214 SuffixTableRange suffixTableRange = 215 new SuffixTableRange(startCellId, endCellId, tzIdSetId); 216 suffixTableWriter.addRange(suffixTableRange); 217 } 218 blockWriter = suffixTableWriter; 219 } 220 return blockWriter; 221 } 222 223 @Override close()224 public void close() throws IOException { 225 try { 226 BlockWriter.ReadBack headerReadBack = mHeaderBlockWriter.close(); 227 mBlockFileWriter.addBlock(headerReadBack.getType(), headerReadBack.getExtraBytes(), 228 headerReadBack.getBlockData()); 229 230 // Add empty blocks padding. 231 EmptyBlockWriter emptyBlockWriterHelper = 232 new EmptyBlockWriter(TzS2RangeFileFormat.BLOCK_TYPE_PADDING); 233 BlockWriter.ReadBack emptyBlockReadBack = emptyBlockWriterHelper.close(); 234 for (int i = 0; i < mFileFormat.getSuffixTableBlockIdOffset() - 1; i++) { 235 mBlockFileWriter.addBlock( 236 emptyBlockReadBack.getType(), emptyBlockReadBack.getExtraBytes(), 237 emptyBlockReadBack.getBlockData()); 238 } 239 240 // Add the suffix tables. 241 for (BlockWriter blockWriter : mSuffixTableBlockWriters) { 242 BlockWriter.ReadBack readBack = blockWriter.close(); 243 244 mBlockFileWriter.addBlock(readBack.getType(), readBack.getExtraBytes(), 245 readBack.getBlockData()); 246 } 247 } finally { 248 mBlockFileWriter.close(); 249 } 250 } 251 252 /** Returns the{@link TzS2RangeFileFormat} for the file being written. */ getFileFormat()253 public TzS2RangeFileFormat getFileFormat() { 254 return mFileFormat; 255 } 256 } 257