// DiskFindHole.bcpl -- For creating sequential files
// Copyright Xerox Corporation 1979, 1982
// Last modified July 26, 1982  9:38 AM by Taft

// to compile statictics-gathering code:
// Bcpl/o 1/v stats/m DiskFindHole.bcpl

get "AltoFileSys.d"
get "Disks.d"

external
[
// outgoing procedure
DiskFindHole

// incoming procedures
AssignDiskPage; ReleaseDiskPage

// outgoing statics (only if stats = true)
bitTableProbes; findNextHoleCalls; findNextHoleIterations
]

structure State:
[
base word
largestHoleSize word
largestHoleVDA word
maxVDA word
]

compileif newname stats then [ manifest [ stats = false ]]

compileif stats then
   [ static [ bitTableProbes; findNextHoleCalls; findNextHoleIterations ]]

//----------------------------------------------------------------------------
let DiskFindHole(disk, nPages, lvHoleSize; numargs na) = valof
//----------------------------------------------------------------------------
// Attempts to find a contiguous hole nPages long in disk.
// If successful, returns the VDA of the first page of the hole; if lvHoleSize
// is supplied, stores nPages in @lvHoleSize.
// If unsuccessful and lvHoleSize is not supplied, returns eofDA.
// If unsuccessful and lvHoleSize is supplied, returns the VDA of the largest
// hole less than nPages long, and stores the size of that hole in @lvHoleSize
// (unless the disk is completely full, in which case returns -1). 
[
if na ls 3 then lvHoleSize = 0

// The following 4 declarations must parallel the State structure:
let base, largestHoleSize, largestHoleVDA = 0, 0, nil
let maxVDA = disk>>DSK.diskKd>>KDH.diskBTsize*16

// First just try to find the hole the caller wants
base = FindNextHole(disk, nPages, lv base)
if lvHoleSize eq 0 resultis base  // may be eofDA
if base ne eofDA then
   [ @lvHoleSize = nPages; resultis base ]

// No hole was big enough.  However, as a side-effect, we will usually have
// discovered SOME hole, which can be used as a lower bound for hole size in
// subsequent searches.
base = 0
if largestHoleSize eq 0 then
   [
   // No hole was found during the initial search.  (This should be an unusual
   // situation, but must be handled.)  Simply find the lowest free VDA on
   // the disk and treat it as a hole of size 1.
   largestHoleVDA = AssignDiskPage(disk, 0)
   if largestHoleVDA eq eofDA resultis eofDA
   ReleaseDiskPage(disk, largestHoleVDA)
   largestHoleSize = 1
   base = largestHoleVDA
   ]

// Now scan the bit table once more looking for larger holes.
// Note that we will go around this loop an arbitrary number of times, but
// will examine the bit table at most once for each VDA.
   [ // repeat
   // Invariant: there is no hole larger than largestHoleSize starting at
   // a VDA less than base.
   // Starting where we previously left off, look for a hole one page larger
   // than the one we know we already have.
   base = FindNextHole(disk, largestHoleSize+1, lv base)
   if base eq eofDA then
      // No larger holes.  Return the one we have now.
      [ @lvHoleSize = largestHoleSize; resultis largestHoleVDA ]

   // A hole of at least largestHoleSize+1 begins at base.
   // Scan past the end to see how long it really is.
   let vda = base+largestHoleSize+1
   while vda uls maxVDA & AssignDiskPage(disk, vda-1, nil) do
      [
      vda = vda+1
      compileif stats then [ bitTableProbes = bitTableProbes+1 ]
      ]

   // vda is not free, so the hole ends at vda-1.  This is the new largest hole.
   largestHoleSize = vda-base
   largestHoleVDA = base
   base = vda+1
   ] repeat
]

//----------------------------------------------------------------------------
and FindNextHole(disk, nPages, state) = valof
//----------------------------------------------------------------------------
// Internal procedure: attempts to find a contiguous hole nPages long in disk
// beginning at a VDA greater than or equal to state.base.
// If successful, returns the VDA of the first page of the hole;
// if unsuccessful, returns eofDA.
// Stores in state.largestHoleVDA and state.largestHoleSize the starting VDA and
// size of the largest hole less than nPages long that was encountered while
// scanning the bit table.  Note, however, that not all bit table bits are scanned,
// so there is no guarantee that the hole described is actually the largest such
// hole in the region scanned.
[
compileif stats then [ findNextHoleCalls = findNextHoleCalls+1 ]
if nPages ugr state>>State.maxVDA resultis eofDA
let base = state>>State.base
let exBase = base
let maxVDA = state>>State.maxVDA - nPages

// n.b.: the 3-argument form of AssignDiskPage determines whether the page at
// vda+1 (!) is free, but without assigning it.
until base ugr maxVDA do
   [
   // invariants at top of loop:
   // 1.  exBase ge base
   // 2.  [base .. exBase) have been searched exhaustively and are known
   //     to be free, if that interval is non-empty.
   compileif stats then [ findNextHoleIterations = findNextHoleIterations+1 ]
   let top = base+nPages-1
   let vda = top

      [ // repeat
      // Scan backward from top to exBase; stop if encounter a page that's not free.
      compileif stats then [ bitTableProbes = bitTableProbes+1 ]
      unless AssignDiskPage(disk, vda-1, nil) break  // not free
      if vda eq exBase resultis base  // found hole
      vda = vda-1
      ] repeat

   // vda is not free.  Try for a new hole starting at vda+1.
   // (vda .. top] are known to be free, since we just searched them.
   if top-vda ugr state>>State.largestHoleSize then
      [ state>>State.largestHoleSize = top-vda; state>>State.largestHoleVDA = vda+1 ]
   base = vda+1
   exBase = top+1
   ]

// no hole of size nPages was found.
resultis eofDA
]