import { PageRange } from "../generated/artifacts/models" ; import { PersistencyPageRange , ZERO_EXTENT_ID } from "../persistence/IBlobMetadataStore" ; import IPageBlobRangesManager from "./IPageBlobRangesManager" ; /********** Ranges Merging Strategy ************/ export default class PageBlobRangesManager implements IPageBlobRangesManager { public mergeRange ( ranges , range ) { const start = range . start ; const end = range . end ; const persistency = range . persistency ; const impactedScope = this . selectImpactedRanges ( ranges , start , end ) ; const impactedStartIndex = impactedScope [ 0 ] ; const impactedEndIndex = impactedScope [ 1 ] ; const impactedRangesCount = impactedStartIndex > impactedEndIndex ? 0 : impactedEndIndex - impactedStartIndex + 1 ; const newRange = { start , end , persistency } ; if ( impactedRangesCount === 0 ) { ranges . splice ( impactedStartIndex , 0 , newRange ) ; } else { const firstImpactedRange = ranges [ impactedStartIndex ] ; const lastImpactedRange = ranges [ impactedEndIndex ] ; const newRanges = [ ] ; if ( firstImpactedRange . end >= start && firstImpactedRange . start < start ) { newRanges . push ( { start : firstImpactedRange . start , end : start - 1 , persistency : { id : firstImpactedRange . persistency . id , offset : firstImpactedRange . persistency . offset , count : start - firstImpactedRange . start } } ) ; } newRanges . push ( newRange ) ; if ( end >= lastImpactedRange . start && end < lastImpactedRange . end ) { newRanges . push ( { start : end + 1 , end : lastImpactedRange . end , persistency : { id : lastImpactedRange . persistency . id , offset : lastImpactedRange . persistency . offset + ( end + 1 - lastImpactedRange . start ) , count : lastImpactedRange . end - end } } ) ; } ranges . splice ( impactedStartIndex , impactedRangesCount , ... newRanges ) ; } } public clearRange ( ranges , range ) { const start = range . start ; const end = range . end ; const impactedScope = this . selectImpactedRanges ( ranges , start , end ) ; const impactedStartIndex = impactedScope [ 0 ] ; const impactedEndIndex = impactedScope [ 1 ] ; const impactedRangesCount = impactedStartIndex > impactedEndIndex ? 0 : impactedEndIndex - impactedStartIndex + 1 ; if ( impactedRangesCount > 0 ) { const firstImpactedRange = ranges [ impactedStartIndex ] ; const lastImpactedRange = ranges [ impactedEndIndex ] ; const newRanges = [ ] ; if ( firstImpactedRange . end >= start && firstImpactedRange . start < start ) { newRanges . push ( { start : firstImpactedRange . start , end : start - 1 , persistency : { id : firstImpactedRange . persistency . id , offset : firstImpactedRange . persistency . offset , count : start - firstImpactedRange . start } } ) ; } if ( end >= lastImpactedRange . start && end < lastImpactedRange . end ) { newRanges . push ( { start : end + 1 , end : lastImpactedRange . end , persistency : { id : lastImpactedRange . persistency . id , offset : lastImpactedRange . persistency . offset + ( end + 1 - lastImpactedRange . start ) , count : lastImpactedRange . end - end } } ) ; } ranges . splice ( impactedStartIndex , impactedRangesCount , ... newRanges ) ; } } param { PersistencyPageRange [ ] } ranges param { PageRange } range returns { PersistencyPageRange [ ] } memberof public cutRanges ( ranges , range ) { const start = range . start ; const end = range . end ; const impactedScope = this . selectImpactedRanges ( ranges , start , end ) ; const impactedStartIndex = impactedScope [ 0 ] ; const impactedEndIndex = impactedScope [ 1 ] ; const impactedRangesCount = impactedStartIndex > impactedEndIndex ? 0 : impactedEndIndex - impactedStartIndex + 1 ; let impactedRanges = [ ] ; if ( impactedRangesCount > 0 ) { impactedRanges = ranges . slice ( impactedStartIndex , impactedEndIndex + 1 ) ; const firstImpactedRange = impactedRanges [ 0 ] ; if ( firstImpactedRange . end >= start && firstImpactedRange . start < start ) { impactedRanges [ 0 ] = { start , end : firstImpactedRange . end , persistency : { offset : start - firstImpactedRange . start + firstImpactedRange . persistency . offset , count : firstImpactedRange . persistency . count - ( start - firstImpactedRange . start ) , id : firstImpactedRange . persistency . id } } ; } const lastImpactedRange = impactedRanges [ impactedRanges . length - 1 ] ; if ( end >= lastImpactedRange . start && end < lastImpactedRange . end ) { impactedRanges [ impactedRanges . length - 1 ] = { start : lastImpactedRange . start , end , persistency : { offset : lastImpactedRange . persistency . offset , count : lastImpactedRange . persistency . count - ( lastImpactedRange . end - end ) , id : lastImpactedRange . persistency . id } } ; } } return impactedRanges ; } public fillZeroRanges ( ranges , range ) { ranges = this . cutRanges ( ranges , range ) ; const filledRanges = [ ] ; if ( ranges . length === 0 ) { return [ { start : range . start , end : range . end , persistency : { offset : 0 , count : range . end + 1 - range . start , id : ZERO_EXTENT_ID } } ] ; } const firstRange = ranges [ 0 ] ; const lastRange = ranges [ ranges . length - 1 ] ; if ( range . start < firstRange . start ) { filledRanges . push ( { start : range . start , end : firstRange . start - 1 , persistency : { offset : 0 , count : firstRange . start - range . start , id : ZERO_EXTENT_ID } } ) ; } for ( let i = 0 ; i < ranges . length - 1 ; i ++ ) { const nextRange = ranges [ i + 1 ] ; const currentRange = ranges [ i ] ; filledRanges . push ( currentRange ) ; const gap = nextRange . start - 1 - currentRange . end ; if ( gap > 0 ) { filledRanges . push ( { start : currentRange . end + 1 , end : nextRange . start - 1 , persistency : { offset : 0 , count : gap , id : ZERO_EXTENT_ID } } ) ; } } filledRanges . push ( ranges [ ranges . length - 1 ] ) ; if ( lastRange . end < range . end ) { filledRanges . push ( { start : lastRange . end + 1 , end : range . end , persistency : { offset : 0 , count : range . end - lastRange . end , id : ZERO_EXTENT_ID } } ) ; } return filledRanges ; } public param { PersistencyPageRange [ ] } ranges param { number } start param { number } end returns { [ number , number ] } memberof public selectImpactedRanges ( ranges , start , end ) { if ( ranges . length === 0 ) { return [ Infinity , - 1 ] ; } if ( start > end || start < 0 ) { throw new RangeError ( "PageBlobRangesManager:selectImpactedRanges() start must less equal than end parameter, start must larger equal than 0." ) ; } const impactedRangeStartIndex = this . locateFirstImpactedRange ( ranges , 0 , ranges . length , start ) ; const impactedRangesEndIndex = this . locateLastImpactedRange ( ranges , 0 , ranges . length , end ) ; return [ impactedRangeStartIndex , impactedRangesEndIndex ] ; } public param { PersistencyPageRange [ ] } ranges param { number } searchStart param { number } searchEnd param { number } position returns { number } memberof public locateFirstImpactedRange ( ranges , searchStart , searchEnd , position ) { searchStart = searchStart < 0 ? 0 : searchStart ; searchEnd = searchEnd > ranges . length ? searchEnd : searchEnd ; if ( ranges . length === 0 || searchStart >= searchEnd ) { return Infinity ; } if ( searchStart === searchEnd - 1 ) { return this . positionInRange ( ranges [ searchStart ] , position ) || position < ranges [ searchStart ] . start ? searchStart : Infinity ; } const searchMid = Math . floor ( ( searchStart + searchEnd ) / 2 ) ; const indexInLeft = this . locateFirstImpactedRange ( ranges , searchStart , searchMid , position ) ; if ( indexInLeft !== Infinity ) { return indexInLeft ; } if ( this . positionInRange ( ranges [ searchMid ] , position ) || position < ranges [ searchMid ] . start ) { return searchMid ; } else { return this . locateFirstImpactedRange ( ranges , searchMid + 1 , searchEnd , position ) ; } } public param { PersistencyPageRange [ ] } ranges param { number } searchStart param { number } searchEnd param { number } position returns { number } memberof public locateLastImpactedRange ( ranges , searchStart , searchEnd , position ) { searchStart = searchStart < 0 ? 0 : searchStart ; searchEnd = searchEnd > ranges . length ? searchEnd : searchEnd ; if ( ranges . length === 0 || searchStart >= searchEnd ) { return - 1 ; } if ( searchStart === searchEnd - 1 ) { return this . positionInRange ( ranges [ searchStart ] , position ) || position > ranges [ searchStart ] . end ? searchStart : - 1 ; } const searchMid = Math . floor ( ( searchStart + searchEnd ) / 2 ) ; const indexInRight = this . locateLastImpactedRange ( ranges , searchMid + 1 , searchEnd , position ) ; if ( indexInRight > - 1 ) { return indexInRight ; } if ( this . positionInRange ( ranges [ searchMid ] , position ) || position > ranges [ searchMid ] . end ) { return searchMid ; } else { return this . locateLastImpactedRange ( ranges , searchStart , searchMid , position ) ; } } public positionInRange ( range , position ) { return position >= range . start && position <= range . end ; } }