module import { Map , List } from "immutable" ; type BlockMapType = Map < string , List < number > > ; param { int } state param { int } initial returns { Array } export function increment ( state , initial = 0 ) { const next = ( state || initial ) + 1 ; return [ next , next ] ; } param { int } initialSize returns { Immutable . Map } export function initialBlockState ( initialSize ) { const blank = Map < List < number > > ( { } ) ; return freeBlock ( blank , 0 , initialSize ) ; } param { Immutable . Map } state param { int } blockSize returns { Array } export function allocBlock ( state , blockSize ) { const keys = state . keySeq ( ) . sortBy ( ( value , key ) => parseInt ( value || "0" , 10 ) > ( key || 0 ) ) ; let ret ; keys . forEach ( ( sizeKey ) : void | false => { if ( typeof sizeKey !== "undefined" ) { const size = parseInt ( sizeKey , 10 ) ; if ( size >= blockSize ) { const blocks = state . get ( sizeKey ) ; if ( blocks . size ) { if ( size === blockSize ) { ret = [ blocks . last ( ) , state . set ( sizeKey , blocks . butLast ( ) . toList ( ) ) ] ; return false ; } else { const lastBlock = blocks . last ( ) ; ret = [ lastBlock , splitFreeBlock ( state , lastBlock , size , lastBlock , blockSize ) ] ; return false ; } } } } } ) ; if ( ! ret ) { throw new Error ( "No free block" ) ; } return ret ; } /**
 * Return a previously allocated block back to the free list.
 *
 * Defragments by merging with adjoining neighbors where possible
 *
 */ export function freeBlock ( state , addr , blockSize ) { state = pushFreeBlock ( state , addr , blockSize ) ; return mergeNeighbors ( state , addr , blockSize ) ; } param { Immutable . Map } state param { int } addr param { int } blockSize returns { Immutable . Map } throws export function reserveBlock ( state , addr , blockSize ) { const removed = state . update ( String ( blockSize ) , blks => ( blks ? blks . filter ( x => x !== addr ) . toList ( ) : blks ) ) ; if ( removed !== state ) { return removed ; } const enc = findEnclosingFreeBlock ( state , addr , blockSize ) ; if ( enc === NOT_FOUND ) { throw new Error ( `Block is already allocated! addr:${ addr } blockSize:${ blockSize } state:${ state }` ) ; } return splitFreeBlock ( state , enc [ 0 ] , enc [ 1 ] , addr , blockSize ) ; } param { Immutable . Map } state returns { Array } export function freeBlockList ( state ) { const list = [ ] ; state . forEach ( ( blks , sizeKey ) => { if ( blks !== undefined ) { blks . forEach ( addr => { if ( addr !== undefined ) { list . push ( [ addr , parseInt ( sizeKey || "0" , 10 ) ] ) ; } } ) ; } } ) ; list . sort ( ( a , b ) => a [ 0 ] - b [ 0 ] ) ; return list ; } /************ private *****************************************/ type FreeBlock = [ number , number ] ; const NOT_FOUND = [ - 1 , - 1 ] ; param { Immutable . Map } state param { int } addr param { int } blockSize returns { Array } function findEnclosingFreeBlock ( state , addr , blockSize ) { let found = NOT_FOUND ; state . forEach ( ( blks , sizeKey ) : void | false => { if ( blks !== undefined && sizeKey ) { const freeBlockSize = parseInt ( sizeKey , 10 ) ; blks . forEach ( ( fblock ) : void | false => { if ( fblock !== undefined && blockEncloses ( addr , blockSize , fblock , freeBlockSize ) ) { found = [ fblock , freeBlockSize ] ; return false ; } } ) ; if ( found !== NOT_FOUND ) { return false ; } } } ) ; return found ; } param { int } addr param { int } size param { int } encBlock param { int } encSize returns { Boolean } function blockEncloses ( addr , size , encBlock , encSize ) { return addr >= encBlock && addr + size <= encBlock + encSize ; } param { Immutable . Map } state param { int } addr param { int } blockSize returns { Immutable . Map } function popFreeBlock ( state , addr , blockSize ) { return state . update ( String ( blockSize ) , blks => ( blks ? blks . filter ( x => x !== addr ) . toList ( ) : blks ) ) ; } param { Immutable . Map } state param { int } addr param { int } blockSize returns { Immutable . Map } function pushFreeBlock ( state , addr , blockSize ) { return state . update ( String ( blockSize ) , blks => ( blks || List ( ) ) . push ( addr ) ) ; } param { Immutable . Map } state param { int } addr param { int } blockSize param { int } splitAddr param { int } splitSize returns { Immutable . Map } function splitFreeBlock ( state , addr , blockSize , splitAddr , splitSize ) { const bottomGap = splitAddr - addr ; const topGap = endAddr ( addr , blockSize ) - endAddr ( splitAddr , splitSize ) ; if ( bottomGap > 0 && topGap === 0 ) { return resizeFreeBlock ( state , addr , blockSize , addr , bottomGap ) ; } if ( topGap > 0 && bottomGap === 0 ) { return resizeFreeBlock ( state , addr , blockSize , endAddr ( addr , blockSize ) - topGap , topGap ) ; } if ( topGap > 0 && bottomGap > 0 ) { state = popFreeBlock ( state , addr , blockSize ) ; state = pushFreeBlock ( state , addr , bottomGap ) ; state = pushFreeBlock ( state , endAddr ( addr , blockSize ) - topGap , topGap ) ; return state ; } return state ; } function resizeFreeBlock ( state , addr , blockSize , newAddr , newSize ) { state = popFreeBlock ( state , addr , blockSize ) ; state = pushFreeBlock ( state , newAddr , newSize ) ; return state ; } function endAddr ( addr , blockSize ) { return addr + blockSize ; } function mergeNeighbors ( state , addr , blockSize ) { const blockEnd = endAddr ( addr , blockSize ) ; let nextState = state ; freeBlockList ( state ) . forEach ( fb => { if ( endAddr ( fb [ 0 ] , fb [ 1 ] ) === addr ) { nextState = popFreeBlock ( nextState , fb [ 0 ] , fb [ 1 ] ) ; nextState = popFreeBlock ( nextState , addr , blockSize ) ; addr = fb [ 0 ] ; blockSize = fb [ 1 ] + blockSize ; nextState = pushFreeBlock ( nextState , addr , blockSize ) ; } if ( fb [ 0 ] === blockEnd ) { nextState = popFreeBlock ( nextState , fb [ 0 ] , fb [ 1 ] ) ; nextState = popFreeBlock ( nextState , addr , blockSize ) ; blockSize = blockSize + fb [ 1 ] ; nextState = pushFreeBlock ( nextState , addr , blockSize ) ; } } ) ; return nextState ; }