Warning, file /utilities/okteta/core/piecetable/piecetable.cpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 /* 0002 This file is part of the Okteta Core library, made within the KDE community. 0003 0004 SPDX-FileCopyrightText: 2008 Friedrich W. H. Kossebau <kossebau@kde.org> 0005 0006 SPDX-License-Identifier: LGPL-2.1-only OR LGPL-3.0-only OR LicenseRef-KDE-Accepted-LGPL 0007 */ 0008 0009 #include "piecetable.hpp" 0010 0011 // lib 0012 #include <logging.hpp> 0013 // Qt 0014 #include <QMutableLinkedListIterator> 0015 0016 namespace KPieceTable { 0017 0018 PieceTable::PieceTable(Size size) 0019 { 0020 init(size); 0021 } 0022 0023 void PieceTable::init(Size size) 0024 { 0025 mList.clear(); 0026 if (size > 0) { 0027 mList.append(Piece(0, size, Piece::OriginalStorage)); 0028 } 0029 0030 mSize = size; 0031 } 0032 0033 bool PieceTable::getStorageData(int* storageId, Address* storageOffset, Address dataOffset) const 0034 { 0035 bool result = false; 0036 0037 // TODO: use width or offset from current and next? 0038 AddressRange dataRange(0, -1); 0039 for (const Piece& piece : mList) { 0040 dataRange.setEndByWidth(piece.width()); 0041 0042 if (dataRange.includes(dataOffset)) { 0043 *storageId = piece.storageId(); 0044 // qCDebug(LOG_OKTETA_CORE) <<piece.start()<<"+"<<dataRange.localIndex( dataOffset ); 0045 *storageOffset = piece.start() + dataRange.localIndex(dataOffset); 0046 result = true; 0047 break; 0048 } 0049 dataRange.setStart(dataRange.nextBehindEnd()); 0050 } 0051 0052 return result; 0053 } 0054 0055 // TODO: optimize search from behind if dataOffset is large (perhaps by counting total size 0056 // TODO: combine sucsequenting inserts, also on other changes if possible link neighbors 0057 void PieceTable::insert(Address insertDataOffset, Size insertLength, Address storageOffset) 0058 { 0059 const int storageId = Piece::ChangeStorage; 0060 QMutableLinkedListIterator<Piece> it(mList); 0061 0062 const Piece insertPiece(storageOffset, insertLength, storageId); 0063 0064 // TODO: use width or offset from current and next? 0065 AddressRange dataRange(0, -1); 0066 while (it.hasNext()) { 0067 Piece& piece = it.peekNext(); 0068 dataRange.setEndByWidth(piece.width()); 0069 0070 // piece starts at offset? 0071 if (dataRange.start() == insertDataOffset) { 0072 it.insert(insertPiece); 0073 break; 0074 } 0075 if (dataRange.nextBehindEnd() == insertDataOffset) { 0076 if (piece.append(insertPiece)) { 0077 break; 0078 } 0079 } 0080 it.next(); 0081 if (dataRange.includes(insertDataOffset)) { 0082 const Piece secondPiece = piece.splitAtLocal(dataRange.localIndex(insertDataOffset)); 0083 it.insert(insertPiece); 0084 it.insert(secondPiece); 0085 break; 0086 } 0087 0088 dataRange.setStart(dataRange.nextBehindEnd()); 0089 } 0090 if (!it.hasNext() && (dataRange.start() == insertDataOffset)) { 0091 it.insert(insertPiece); 0092 } 0093 0094 mSize += insertLength; 0095 } 0096 0097 void PieceTable::insert(Address insertDataOffset, const PieceList& insertPieceList) 0098 { 0099 if (insertPieceList.isEmpty()) { 0100 return; 0101 } 0102 0103 bool isInserted = false; 0104 QMutableLinkedListIterator<Piece> it(mList); 0105 0106 // TODO: use width or offset from current and next? 0107 AddressRange dataRange(0, -1); 0108 while (it.hasNext()) { 0109 Piece& piece = it.peekNext(); 0110 dataRange.setEndByWidth(piece.width()); 0111 0112 // piece starts at offset? 0113 if (dataRange.start() == insertDataOffset) { 0114 int i = 0; 0115 if (it.hasPrevious()) { 0116 Piece& previousPiece = it.peekPrevious(); 0117 if (previousPiece.append(insertPieceList.at(0))) { 0118 if (insertPieceList.size() == 1) { 0119 if (previousPiece.append(piece)) { 0120 it.next(); 0121 it.remove(); 0122 } 0123 isInserted = true; 0124 break; 0125 } 0126 ++i; 0127 } 0128 } 0129 0130 const int lastIndex = insertPieceList.size() - 1; 0131 for (; i < lastIndex; ++i) { 0132 it.insert(insertPieceList.at(i)); 0133 } 0134 0135 const Piece& lastInsertPiece = insertPieceList.at(lastIndex); 0136 if (!piece.prepend(lastInsertPiece)) { 0137 it.insert(lastInsertPiece); 0138 } 0139 isInserted = true; 0140 break; 0141 } 0142 it.next(); 0143 if (dataRange.includes(insertDataOffset)) { 0144 const Piece secondPiece = piece.splitAtLocal(dataRange.localIndex(insertDataOffset)); 0145 for (int i = 0; i < insertPieceList.size(); ++i) { 0146 it.insert(insertPieceList.at(i)); 0147 } 0148 0149 it.insert(secondPiece); 0150 isInserted = true; 0151 break; 0152 } 0153 0154 dataRange.setStart(dataRange.nextBehindEnd()); 0155 } 0156 if (!isInserted && (dataRange.start() == insertDataOffset)) { 0157 int i = 0; 0158 if (it.hasPrevious()) { 0159 Piece& previousPiece = it.peekPrevious(); 0160 if (previousPiece.append(insertPieceList.at(0))) { 0161 ++i; 0162 } 0163 } 0164 for (; i < insertPieceList.size(); ++i) { 0165 it.insert(insertPieceList.at(i)); 0166 } 0167 } 0168 0169 mSize += insertPieceList.totalLength(); 0170 } 0171 0172 // TODO: make algorithm simpler 0173 PieceList PieceTable::remove(const AddressRange& removeRange) 0174 { 0175 PieceList removedPieceList; 0176 0177 AddressRange dataRange(0, -1); 0178 0179 QLinkedList<Piece>::Iterator it = mList.begin(); 0180 while (it != mList.end()) { 0181 Piece* piece = &*it; 0182 dataRange.setEndByWidth(piece->width()); 0183 0184 if (dataRange.includes(removeRange.start())) { 0185 QLinkedList<Piece>::Iterator firstRemoved = it; 0186 const Address firstDataRangeStart = dataRange.start(); 0187 // int sections = 1; 0188 0189 if (dataRange.includesInside(removeRange)) { 0190 const AddressRange localRange = dataRange.localRange(removeRange); 0191 const Piece removedPiece = piece->subPiece(localRange); 0192 const Piece secondPiece = piece->removeLocal(localRange); 0193 0194 mList.insert(++it, secondPiece); 0195 removedPieceList.append(removedPiece); 0196 // qCDebug(LOG_OKTETA_CORE) << "removed intern"; 0197 break; 0198 } 0199 do { 0200 if (dataRange.includes(removeRange.end())) { 0201 QLinkedList<Piece>::Iterator lastRemoved = it; 0202 // qCDebug(LOG_OKTETA_CORE) << removeRange.start() << removeRange.end() << firstDataRangeStart << dataRange.end(); 0203 // cut from first section if not all 0204 bool onlyCompletePiecesRemoved = true; 0205 if (firstDataRangeStart < removeRange.start()) { 0206 const Address newLocalEnd = removeRange.start() - firstDataRangeStart - 1; 0207 const Piece removedPiece = (*firstRemoved).removeEndBehindLocal(newLocalEnd); 0208 removedPieceList.append(removedPiece); 0209 0210 ++firstRemoved; 0211 onlyCompletePiecesRemoved = false; 0212 // qCDebug(LOG_OKTETA_CORE) << "end of first removed"<<piece->start()<<piece->end()<<"->"<<removedPiece.start()<<removedPiece.end(); 0213 // --sections; 0214 } 0215 0216 Piece removedPartialPieceFromLast; 0217 // cut from last section if not all 0218 if (removeRange.end() < dataRange.end()) { 0219 const Address newLocalStart = dataRange.localIndex(removeRange.end()) + 1; 0220 removedPartialPieceFromLast = piece->removeStartBeforeLocal(newLocalStart); 0221 0222 onlyCompletePiecesRemoved = false; 0223 // qCDebug(LOG_OKTETA_CORE) << "start of last removed"<<piece->start()<<piece->end()<<"->"<<removedPartialPieceFromLast.start()<<removedPartialPieceFromLast.end(); 0224 // --sections; 0225 } else { 0226 ++lastRemoved; 0227 } 0228 0229 std::for_each(firstRemoved, lastRemoved, [&removedPieceList](const Piece& piece) mutable { 0230 removedPieceList.append(piece); 0231 }); 0232 0233 if (removedPartialPieceFromLast.isValid()) { 0234 removedPieceList.append(removedPartialPieceFromLast); 0235 } 0236 0237 if (onlyCompletePiecesRemoved) { 0238 if (firstRemoved != mList.begin() && lastRemoved != mList.end()) { 0239 QLinkedList<Piece>::Iterator beforeFirstRemoved = firstRemoved - 1; 0240 if ((*beforeFirstRemoved).append(*lastRemoved)) { 0241 ++lastRemoved; 0242 } 0243 } 0244 } 0245 0246 mList.erase(firstRemoved, lastRemoved); 0247 // qCDebug(LOG_OKTETA_CORE) << "removed "<<sections; 0248 break; 0249 } 0250 dataRange.setStart(dataRange.nextBehindEnd()); 0251 ++it; 0252 // ++sections; 0253 // removeRange is longer than content TODO: just quit or at least remove till the end? 0254 if (it == mList.end()) { 0255 break; 0256 } 0257 piece = &*it; 0258 dataRange.setEndByWidth(piece->width()); 0259 } while (it != mList.end()); 0260 break; 0261 } 0262 0263 dataRange.setStart(dataRange.nextBehindEnd()); 0264 ++it; 0265 } 0266 0267 mSize -= removeRange.width(); 0268 0269 // qCDebug(LOG_OKTETA_CORE)<<"end:"<<asStringList(mList); 0270 return removedPieceList; 0271 } 0272 0273 PieceList PieceTable::replace(const AddressRange& removeRange, Size insertLength, Address storageOffset) 0274 { 0275 PieceList removedPieceList = remove(removeRange); 0276 insert(removeRange.start(), insertLength, storageOffset); 0277 return removedPieceList; 0278 } 0279 void PieceTable::replace(const AddressRange& removeRange, const PieceList& insertPieceList) 0280 { 0281 remove(removeRange); 0282 insert(removeRange.start(), insertPieceList); 0283 } 0284 0285 void PieceTable::swap(Address firstStart, const AddressRange& secondRange) 0286 { 0287 AddressRange dataRange(0, -1); 0288 0289 QLinkedList<Piece>::Iterator it = mList.begin(); 0290 while (it != mList.end()) { 0291 Piece* piece = &*it; 0292 dataRange.setEndByWidth(piece->width()); 0293 0294 if (dataRange.includes(firstStart)) { 0295 // piece does not start at offset? 0296 if (dataRange.start() < firstStart) { 0297 // well, split and insert second piece, even if we move it later, just make it work for now 0298 const Piece secondPiece = piece->splitAtLocal(dataRange.localIndex(firstStart)); 0299 it = mList.insert(++it, secondPiece); 0300 piece = &*it; 0301 dataRange.setStart(firstStart); 0302 } 0303 QLinkedList<Piece>::Iterator firstIt = it; 0304 0305 do { 0306 if (dataRange.includes(secondRange.start())) { 0307 // piece does not start at source? 0308 if (dataRange.start() < secondRange.start()) { 0309 // well, split and insert second piece, even if we move it later, just make it work for now 0310 const Piece secondPiece = piece->splitAtLocal(dataRange.localIndex(secondRange.start())); 0311 it = mList.insert(++it, secondPiece); 0312 piece = &*it; 0313 dataRange.setStart(secondRange.start()); 0314 } 0315 QLinkedList<Piece>::Iterator firstSecondIt = it; 0316 0317 do { 0318 if (dataRange.includes(secondRange.end())) { 0319 // piece does not start at source? 0320 if (secondRange.end() < dataRange.end()) { 0321 // well, split and insert second piece, even if we move it later, just make it work for now 0322 const Piece secondPiece = piece->splitAtLocal(dataRange.localIndex(secondRange.nextBehindEnd())); 0323 it = mList.insert(++it, secondPiece); 0324 } else { 0325 ++it; 0326 } 0327 QLinkedList<Piece>::Iterator behindLastSecondIt = it; 0328 0329 for (it = firstSecondIt; it != behindLastSecondIt; ++it) { 0330 firstIt = mList.insert(firstIt, *it) + 1; 0331 } 0332 0333 mList.erase(firstSecondIt, behindLastSecondIt); 0334 0335 // done, move out of here 0336 it = mList.end(); 0337 break; 0338 } 0339 dataRange.setStart(dataRange.nextBehindEnd()); 0340 ++it; 0341 0342 // removeRange is longer than content TODO: just quit or at least remove till the end? 0343 if (it == mList.end()) { 0344 break; 0345 } 0346 piece = &*it; 0347 dataRange.setEndByWidth(piece->width()); 0348 } while (it != mList.end()); 0349 } else { 0350 dataRange.setStart(dataRange.nextBehindEnd()); 0351 ++it; 0352 0353 // removeRange is longer than content TODO: just quit or at least remove till the end? 0354 if (it == mList.end()) { 0355 break; 0356 } 0357 piece = &*it; 0358 dataRange.setEndByWidth(piece->width()); 0359 } 0360 } while (it != mList.end()); 0361 break; 0362 } 0363 0364 dataRange.setStart(dataRange.nextBehindEnd()); 0365 ++it; 0366 } 0367 } 0368 0369 Piece PieceTable::replaceOne(Address dataOffset, Address storageOffset, int storageId) 0370 { 0371 int replacedStorageId = Piece::OriginalStorage; 0372 Address replacedStorageOffset = -1; 0373 0374 QMutableLinkedListIterator<Piece> it(mList); 0375 0376 AddressRange dataRange(0, -1); 0377 while (it.hasNext()) { 0378 Piece* piece = &it.peekNext(); 0379 dataRange.setEndByWidth(piece->width()); 0380 if (dataRange.includes(dataOffset)) { 0381 replacedStorageId = piece->storageId(); 0382 0383 const Piece replacePiece(storageOffset, 1, storageId); 0384 // piece starts at offset? 0385 if (dataRange.start() == dataOffset) { 0386 replacedStorageOffset = piece->start(); 0387 if (dataRange.width() == 1) { 0388 piece->set(storageOffset, storageOffset); 0389 piece->setStorageId(storageId); 0390 } else { 0391 it.insert(replacePiece); 0392 piece->moveStartBy(1); 0393 } 0394 } else if (dataRange.end() == dataOffset) { 0395 replacedStorageOffset = piece->end(); 0396 piece->moveEndBy(-1); 0397 it.next(); 0398 it.insert(replacePiece); 0399 } else { 0400 const Address localIndex = dataRange.localIndex(dataOffset); 0401 replacedStorageOffset = piece->start() + localIndex; 0402 0403 const Piece secondPiece = piece->removeLocal(AddressRange::fromWidth(localIndex, 1)); 0404 it.next(); 0405 it.insert(replacePiece); 0406 it.insert(secondPiece); 0407 } 0408 break; 0409 } 0410 it.next(); 0411 dataRange.setStart(dataRange.nextBehindEnd()); 0412 } 0413 return Piece(replacedStorageOffset, 1, replacedStorageId); 0414 } 0415 0416 }