/**
 * Copyright (c) 2018-present, heineiuo.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */ import { assert } from "./DBHelper" ; import { Buffer } from "./Buffer" ; import Slice from "./Slice" ; import { FileMetaData , BySmallestKey , GetStats } from "./VersionFormat" ; import VersionSet from "./VersionSet" ; import { Config , InternalKey , ValueType , InternalKeyComparator , parseInternalKey , ParsedInternalKey , kValueTypeForSeek , LookupKey , } from "./Format" ; import Compaction from "./Compaction" ; import Status from "./Status" ; import { Comparator } from "./Comparator" ; import { ReadOptions } from "./Options" ; import { encodeFixed64 } from "./Coding" ; enum SaverState { kNotFound , kFound , kDeleted , kCorrupt } class Saver { state ! : SaverState ; ucmp ! : Comparator ; userKey ! : Slice ; value ! : Buffer ; } class State { s ! : Status ; vset ! : VersionSet ; options ! : ReadOptions ; ikey ! : Slice ; lastFileRead ! : FileMetaData ; lastFileReadLevel ! : number ; stats ! : GetStats ; found ! : boolean ; saver : Saver = new Saver ( ) ; static async match ( state , level , f ) { if ( ! ( state instanceof State ) ) return Promise . resolve ( false ) ; if ( ! state . stats . seekFile && ! ! state . lastFileRead ) { state . stats . seekFile = state . lastFileRead ; state . stats . seekFileLevel = state . lastFileReadLevel ; } state . lastFileRead = f ; state . lastFileReadLevel = level ; state . s = await state . vset . tableCache . get ( state . options , f . number , f . fileSize , state . ikey , state . saver , Version . saveValue ) ; if ( ! ( await state . s . ok ( ) ) ) { if ( ! state . s . isNotFound ( ) ) { return false ; } else { state . s = new Status ( ) ; } } switch ( state . saver . state ) { case SaverState . kNotFound : return true ; case SaverState . kFound : state . found = true ; return false ; case SaverState . kDeleted : return false ; case SaverState . kCorrupt : state . s = Status . createCorruption ( `corrupted key for ${ state . saver . userKey . toString ( ) }` ) ; state . found = true ; return false ; } return false ; } } interface FileEntry { key : InternalKey ; value : Slice ; } export default class Version { static saveValue ( saver , ikey , v ) { if ( ! ( saver instanceof Saver ) ) return ; const parsedKey = new ParsedInternalKey ( ) ; if ( ! parseInternalKey ( ikey , parsedKey ) ) { saver . state = SaverState . kCorrupt ; } else { if ( saver . ucmp . compare ( parsedKey . userKey , saver . userKey ) == 0 ) { saver . state = parsedKey . valueType == ValueType . kTypeValue ? SaverState . kFound : SaverState . kDeleted ; if ( saver . state == SaverState . kFound ) { saver . value = Buffer . concat ( [ v . buffer ] ) ; } } } } static * levelFileNumIterator ( icmp , files ) { for ( const file of files ) { const valueBuf = Buffer . alloc ( 16 ) ; valueBuf . fillBuffer ( encodeFixed64 ( file . number ) , 0 , 8 ) ; valueBuf . fillBuffer ( encodeFixed64 ( file . fileSize ) , 8 , 16 ) ; yield { key : file . largest , value : new Slice ( valueBuf ) , } as FileEntry ; } } static afterFile ( ucmp , userKey , f ) { return ! ! userKey && ucmp . compare ( userKey , f . largest . userKey ) > 0 ; } static beforeFile ( ucmp , userKey , f ) { return ! ! userKey && ucmp . compare ( userKey , f . smallest . userKey ) < 0 ; } versionSet : VersionSet ; next : Version ; prev : Version ; refs : number ; fileToCompact ! : FileMetaData ; fileToCompactLevel : number ; compactionScore : number ; compactionLevel : number ; public files : FileMetaData [ ] [ ] ; constructor ( versionSet ) { this . versionSet = versionSet ; this . next = this ; this . prev = this ; this . refs = 0 ; this . fileToCompactLevel = - 1 ; this . compactionScore = - 1 ; this . compactionLevel = - 1 ; const cmp = new BySmallestKey ( versionSet . internalKeyComparator ) ; this . files = Array . from ( { length : Config . kNumLevels } , ( ) => [ ] ) ; } public ref ( ) { this . refs ++ ; } public unref ( ) { assert ( this . refs >= 1 ) ; this . refs -- ; if ( this . refs === 0 ) { } } public async get ( lkey , stats ) { delete stats . seekFile ; stats . seekFileLevel = - 1 ; const state = new State ( ) ; state . found = false ; state . stats = stats ; state . lastFileReadLevel = - 1 ; state . options = { } as ReadOptions ; state . ikey = lkey . internalKey ; state . vset = this . versionSet ; state . saver . state = SaverState . kNotFound ; state . saver . ucmp = this . versionSet . internalKeyComparator . userComparator ; state . saver . userKey = lkey . userKey ; await this . forEachOverlapping ( lkey . userKey , lkey . internalKey , state , State . match ) ; if ( ! state . found ) { return Status . createNotFound ( ) ; } return new Status ( Promise . resolve ( state . saver . value ) ) ; } public async forEachOverlapping ( userKey , internalKey , arg , match ) { const ucmp = this . versionSet . internalKeyComparator . userComparator ; const tmp = [ ] as FileMetaData [ ] ; for ( let i = 0 ; i < this . files [ 0 ] . length ; i ++ ) { const f = this . files [ 0 ] [ i ] ; if ( ucmp . compare ( userKey , f . smallest . userKey ) >= 0 && ucmp . compare ( userKey , f . largest . userKey ) <= 0 ) { tmp . push ( f ) ; } } if ( tmp . length > 0 ) { tmp . sort ( ( a , b ) => ( a . number > b . number ? - 1 : 1 ) ) ; for ( let i = 0 ; i < tmp . length ; i ++ ) { if ( ! ( await match ( arg , 0 , tmp [ i ] ) ) ) { return ; } } } for ( let level = 0 ; level < Config . kNumLevels ; level ++ ) { const numFiles = this . files [ level ] . length ; if ( numFiles === 0 ) continue ; const index = this . findFile ( this . versionSet . internalKeyComparator , this . files [ level ] , internalKey ) ; if ( index < numFiles ) { const f = this . files [ level ] [ index ] ; if ( ucmp . compare ( userKey , f . smallest . userKey ) < 0 ) { } else { if ( ! ( await match ( arg , level , f ) ) ) { return ; } } } } } private someFileOverlapsRange ( icmp , disjointSortedFile , files , smallestUserKey , largestUserKey ) { const ucmp = icmp . userComparator ; if ( ! disjointSortedFile ) { for ( let i = 0 ; i < files . length ; i ++ ) { const f = files [ i ] ; if ( Version . afterFile ( ucmp , smallestUserKey , f ) || Version . beforeFile ( ucmp , largestUserKey , f ) ) { } else { return true ; } } return false ; } let index = 0 ; if ( ! ! smallestUserKey ) { const smallkey = new InternalKey ( smallestUserKey , InternalKey . kMaxSequenceNumber , kValueTypeForSeek ) ; index = this . findFile ( icmp , files , smallkey ) ; } if ( index >= files . length ) { return false ; } return ! Version . beforeFile ( ucmp , largestUserKey , files [ index ] ) ; } private findFile ( icmp , files , key ) { let left = 0 ; let right = files . length ; while ( left < right ) { const mid = Math . floor ( ( left + right ) / 2 ) ; const file = files [ mid ] ; if ( icmp . compare ( file . largest , key ) < 0 ) { left = mid + 1 ; } else { right = mid ; } } return right ; } public overlapInLevel ( level , smallestUserKey , largestUserKey ) { return this . someFileOverlapsRange ( this . versionSet . internalKeyComparator , level > 0 , this . files [ level ] , smallestUserKey , largestUserKey ) ; } public getOverlappingInputs ( level , begin , end ) { assert ( level >= 0 ) ; assert ( level < Config . kNumLevels ) ; let inputs = [ ] ; let userBegin = begin ? begin . userKey : new Slice ( ) ; let userEnd = end ? end . userKey : new Slice ( ) ; const userComparator = this . versionSet . internalKeyComparator . userComparator ; for ( let i = 0 ; i < this . files [ level ] . length ; ) { const fileMetaData = this . files [ level ] [ i ++ ] ; const fileStart = fileMetaData . smallest . userKey ; const fileLimit = fileMetaData . largest . userKey ; if ( ! ! begin && userComparator . compare ( fileLimit , userBegin ) < 0 ) { } else if ( ! ! end && userComparator . compare ( fileStart , userEnd ) > 0 ) { } else { inputs . push ( fileMetaData ) ; if ( level === 0 ) { if ( ! ! begin && userComparator . compare ( fileStart , userBegin ) < 0 ) { userBegin = fileStart ; inputs = [ ] ; i = 0 ; } else if ( ! ! end && userComparator . compare ( fileLimit , userEnd ) > 0 ) { userEnd = fileLimit ; inputs = [ ] ; i = 0 ; } } } } return inputs ; } public pickLevelForMemTableOutput ( minUserKey , maxUserKey ) { let level = 0 ; if ( ! this . overlapInLevel ( 0 , minUserKey , maxUserKey ) ) { const start = new InternalKey ( minUserKey , InternalKey . kMaxSequenceNumber , kValueTypeForSeek ) ; const limit = new InternalKey ( maxUserKey , 0n , ValueType . kTypeValue ) ; let overlaps = [ ] as FileMetaData [ ] ; while ( level < Config . kMaxMemCompactLevel ) { if ( this . overlapInLevel ( level + 1 , minUserKey , maxUserKey ) ) { break ; } if ( level + 2 < Config . kNumLevels ) { overlaps = this . getOverlappingInputs ( level + 2 , start , limit ) ; const sum = Compaction . totalFileSize ( overlaps ) ; if ( sum > Compaction . maxGrandParentOverlapBytes ( this . versionSet . _options ) ) { break ; } } level ++ ; } } return level ; } public updateStats ( stats ) { return false ; } }