// IFSDirLookup.bcpl -- Lookup names in IFS directory
// Copyright Xerox Corporation 1979, 1980, 1981, 1982

// Last modified July 12, 1982  4:13 PM by Taft

get "Ifs.decl"
get "IfsFiles.decl"
get "IfsDirs.decl"
get "BTree.decl"

external
[
// Outgoing procedures
LookupIFSFile; LookupFD; NextFD; InstallDR
LockDirFD; UnlockDirFD; ModifyDirFD

// Incoming procedures -- IFSDirs
CreateFD; DestroyFD; ParseFD; UpdateFD; IFSAppendVersion
NamesMatch; DirCompareKey

// Incoming procedures -- B-Tree
ReadRecLE; MapTree

// Incoming procedures -- rest of IFS
IFSError; CopyString; FreePointer; MatchKPMTemplate
Lock; Unlock; Block; Yield; LockCell; UnlockCell; NoticeDirectoryChange

// Incoming procedures -- operating system
DefaultArgs; SysAllocate; SysAllocateZero; SysFree; MoveBlock

// Incoming statics
CtxRunning
]

manifest
[
// assumed maximum size of PathStk: existing IFS directory B-Trees
// never exceed 3 levels, so leave room for 4 levels to be ultra-conservative.
lenPathStk = (offset PS.PSE↑5)/16
]

//----------------------------------------------------------------------------
let LookupIFSFile(name, lc, lvErrorCode, fs, dirName; numargs na) = valof
//----------------------------------------------------------------------------
// Combines the operations of CreateFD and LookupFD.
// Returns the fd if successful and zero if unsuccessful.
// The error code is stored in @lvErrorCode; zero is stored upon success.
// The directory should not be locked by the caller and is not locked
// upon return.
[
DefaultArgs(lv na, -2, lv na, 0, 0)
let fd = CreateFD(name, lc, lvErrorCode, fs, dirName)
if fd ne 0 then
   [
   @lvErrorCode = LookupFD(fd)
   if @lvErrorCode ne 0 then fd = DestroyFD(fd)
   ]
resultis fd
]

//----------------------------------------------------------------------------
and LookupFD(fd, lockMode, requireExists; numargs na) = valof
//----------------------------------------------------------------------------
// Looks up the file described by the FD structure "fd", applying
// the lookup control parameters in the fd as appropriate.
// If the file already exists, the directory record (dr) in the
// fd is replaced by the actual entry that was found.
// If the file does not exist and the lookup control says that
// a new file may be created, a directory record is generated
// which may be used in creating the file (however, the new file
// is not actually created by LookupFD).  This procedure should
// ordinarily be called with the directory unlocked, and returns with
// the directory unlocked; however, other lock actions may be specified
// by lockMode (see IfsDirs.decl).  Returns zero if successful and
// an error code if unsuccessful.  If the lookup is successful,
// the code in fd>>FD.lookupStatus describes the outcome:
//  lsNonexistent:  the file does not exist and no other version
//	exists either.  to create the file, directory-default
//	properties must be used.
//  lsOtherVersion:  the specified version doesn't exist, but
//	another version does.  the FP of that version is stored
//	in the dr for use in obtaining its properties.
//  lsExists:  the specified file exists, and its dr is stored
//	in the fd.
// Note that it is ok to call LookupFD multiple times on the same
// fd.  This is necessary to "re-validate" an fd that has become
// invalid due to the directory being unlocked.
// If requireExists is true the file is required to exist, regardless of
// the lookup control; if false or omitted, a nonexistent file is
// acceptable if the lookup control permits.
[
if na eq 1 then lockMode = lockNone

// If the fd designates multiple files and this is the first
// lookup, just advance to the first existing file matching
// the template and return it.
if fd>>FD.lookupStatus eq lsNoLookup & fd>>FD.template ne 0 then
   resultis (NextFD(fd, lockMode)? 0, ecFileNotFound)

// If a lookup has already been done on this fd and the directory
// has not been modified in the meantime, just return ok.
unless lockMode eq lockAlready do LockDirFD(fd, lockMode eq lockWrite)
let fs = fd>>FD.fs
let vc = fd>>FD.lc.vc
if fd>>FD.lookupStatus ne lsNoLookup then
   [
   if fd>>FD.dirVersion eq fs>>IFS.dirVersion then
      [
      unless lockMode ge lockRead do UnlockDirFD(fd)
      resultis 0
      ]
   vc = lcVExplicit  // force exact match during revalidation
   ]

// Single file lookup case.
// First, find the best candidate entry in the directory.
// If the version control is vcHighest, vcNext, or vcExplicit,
// this is the greatest entry less than or equal to the key;
// if vcLowest, this is the key's successor (recall that vcHighest
// and vcNext set version to 65535, and vcLowest sets version to 0)
let record = vc eq lcVLowest? DirSuccessor(fs>>IFS.dirBTree, fd),
 ReadRecLE(fs>>IFS.dirBTree, fd, 0, 0, fd>>FD.pathStk, true)
if record ne 0 & (record>>DR.header & drHeaderMask) ne 0 then
   IFSError(ecBadDR)

// Discover how good a match this was
let version = nil  // the real version of the file that was found
let code = (record eq 0? 0, NamesMatch(fd, record, lv version))

// LookupFD (cont'd)

// Branch on the cross product of match code and version control
let ec = 0  // no error yet
switchon 4*vc+code into
   [
   case 4*lcVHighest+0: case 4*lcVNext+0:
   case 4*lcVLowest+0: case 4*lcVExplicit+0:
      [  // no such directory
      fd>>FD.lookupStatus = lsNonexistent; ec = ecDirNotFound; endcase
      ]
   case 4*lcVHighest+1: case 4*lcVNext+1: case 4*lcVLowest+1:
      [  // no such file exists, create version 1
      fd>>FD.version = 1  //fall into next case
      ]
   case 4*lcVExplicit+1:
      [  // no version of file exists, explicit version requested
      fd>>FD.lookupStatus = lsNonexistent; endcase
      ]
   case 4*lcVHighest+2: case 4*lcVHighest+3:
   case 4*lcVLowest+2: case 4*lcVExplicit+3:
      [  // body matched and highest or lowest requested, or
         // exact match and highest or explicit requested,
         // return that version
      fd>>FD.version = version
      fd>>FD.lookupStatus = lsExists
      InstallDR(fd, record)
      endcase
      ]
   case 4*lcVNext+2:
      [  // body matched and next requested, create version+1
      fd>>FD.version = version+1  // fall into next case
      ]
   case 4*lcVExplicit+2:
      [  // a previous version exists, explicit version requested
      fd>>FD.lookupStatus = lsOtherVersion
      InstallDR(fd, record)
      endcase
      ]
   case 4*lcVNext+3:
      [  // exact match and next was requested, version overflow
      ec = ecIllegalVersion; endcase
      ]
   default:
      IFSError(ecLookupImpossibleCase)
   ]

FreePointer(lv record)
unless fd>>FD.lookupStatus eq lsExists do FreePointer(lv fd>>FD.pathStk)

if ec eq 0 then
   [
   IFSAppendVersion(fd)  // in case new version number computed
   if fd>>FD.dr>>DR.pathName.length gr maxPathNameChars then
      ec = ecNameTooLong
   if fd>>FD.lookupStatus ne lsExists then
      if (na ge 3 & requireExists) % not fd>>FD.lc.create then
         ec = ecFileNotFound
   ]

// Remember directory version for which this fd is valid
fd>>FD.dirVersion = fs>>IFS.dirVersion
unless lockMode ge lockRead do UnlockDirFD(fd)
resultis ec
]

//----------------------------------------------------------------------------
and NextFD(fd, lockMode; numargs na) = valof
//----------------------------------------------------------------------------
// Advances to the next file described by the FD.  If successful,
// updates the DR and the auxiliary lookup information (including
// lookupStatus) and returns true.  If unsuccessful, returns false.
// lockMode is treated as in LookupFD.
[
if na eq 1 then lockMode = lockNone
let fs = fd>>FD.fs
let vc = fd>>FD.lc.vc
unless lockMode eq lockAlready do LockDirFD(fd, lockMode eq lockWrite)

// scan directory starting at current file.
let result = valof
   [ // repeat
   if fd>>FD.template eq 0 resultis false  // not multiple-file FD

   // If version control is "lowest" or "highest", make sure we skip
   // over all remaining versions of the current file.
   // If we already have a PathStk then use it, else create a new one.
   let useExistingPath = false
   test vc eq lcVLowest % vc eq lcVHighest
      ifso fd>>FD.version = 177777B  // and don't use existing path
      ifnot test fd>>FD.pathStk eq 0
         ifso fd>>FD.pathStk = SysAllocateZero(lenPathStk)
         ifnot useExistingPath = true

   // following 3 variables must be contiguous and in this order
   let param = fd  // fd being passed down to MatchFD
   let code = 0  // code passed back up from MatchFD
   let count = 0  // count of records processed

   MapTree(fs>>IFS.dirBTree, fd, MatchFD, lv param, 0, true,
    fd>>FD.pathStk, useExistingPath)

   //figure out why MapTree terminated
   switchon code into
      [
      case 0:  // ran off end of tree or past last possible entry
         FreePointer(lv fd>>FD.template, lv fd>>FD.pathStk)
         resultis false

      case 1:  // someone else waiting to use dir, give him a chance
         [
         let lockedForWriting = fs>>IFS.dirLock.count ls 0
         UnlockDirFD(fd)
         LockDirFD(fd, lockedForWriting)
         UpdateFD(fd)
         endcase
         ]

      case 2:  // found matching record
         // In the case of all version controls besides "highest", we now
         // have the desired record.  In the case of "highest", we now have
         // the lowest version so we have to do a lookup to find the highest.
         if vc eq lcVHighest then
            [
            UpdateFD(fd)
            fd>>FD.version = 177777B
            // "true" as 4th arg means don't copy -- InstallDR will do it.
            // Must be no opportunity to block or fault beween ReadRecLE
            // and InstallDR, because ReadRecLE returns unlocked pointer.
            InstallDR(fd,
             ReadRecLE(fs>>IFS.dirBTree, fd, 0, true, fd>>FD.pathStk))
            ]
         UpdateFD(fd)
         resultis true
      ]
   ] repeat

// Update the auxiliary lookup information in the fd
fd>>FD.lookupStatus = result? lsExists, lsNonexistent
fd>>FD.dirVersion = fs>>IFS.dirVersion
unless lockMode ge lockRead do UnlockDirFD(fd)
resultis result
]

//----------------------------------------------------------------------------
and MatchFD(record, lvParam, nil) = valof
//----------------------------------------------------------------------------
// This procedure is called by MapTree with the next record for
// consideration.  If this record does not match the fd and there
// is no other reason to terminate, returns true, thereby causing
// MapTree to continue scanning the directory.  Otherwise, returns
// false, causing MapTree to terminate, after storing a code
// in the parameter vector denoting the reason for termination:
//  0 ran past the last possible entry in the directory
//    (note that NextFD initializes the code to 0, so MatchFD
//    doesn't have to set it to this value explicitly, and 0 is
//    also returned if MapTree returns without having called
//    MatchFD at all).
//  1 someone else is waiting to use the directory, give him
//    a chance and then resume scanning.  stores the current
//    record in the fd to use as the starting key.
//  2 found a matching record, which is now stored in the fd.
[
Yield()

// This check is now redundant because MapTree always calls DirEntryLength
// on each record before passing it to us, and DirEntryLength
// performs the same check.
// if (record>>DR.header & drHeaderMask) ne 0 then IFSError(ecBadDR)
let fd = lvParam!0
let i = MatchKPMTemplate(lv record>>DR.pathName, fd>>FD.template)
if i ne 0 then
   [
   // Doesn't match.  If the failing character preceded the first
   // "*" in the template then stop now, else continue scan.
   test i ls fd>>FD.iFirstStar & DirCompareKey(fd, record) ls 0
      ifso resultis false  // no further matches possible
      ifnot
         [
         // Terminate scan anyway if we have hogged the directory
         // for too long and someone else is waiting.
         lvParam!2 = lvParam!2+1  // count entries processed
         if fd>>FD.fs>>IFS.dirLockConflict & lvParam!2 gr 25 then
            [
            InstallDR(fd, record)
            lvParam!1 = 1
            resultis false
            ]
         resultis true
         ]
   ]

// The new record must be "greater than" the current name
unless DirCompareKey(fd, record) ls 0 resultis true

// Ok, pass back this record and terminate scan
InstallDR(fd, record)
lvParam!1 = 2  // signal success
resultis false  // stop scan
]

//----------------------------------------------------------------------------
and InstallDR(fd, record) be
//----------------------------------------------------------------------------
// Installs a copy of record as fd's DR.
// Enough extra space is allocated to permit appending a bigger version.
// InstallDR must be in the same overlay as the caller if the supplied
// record is contained in an unlocked B-Tree page.  NextFD (above) makes
// this assumption.
[
LockCell(lv record)  // protect across Allocate, which might conceivably block
FreePointer(lv fd>>FD.dr)
fd>>FD.dr = SysAllocate(record>>DR.length+3)
MoveBlock(fd>>FD.dr, record, record>>DR.length+3)
UnlockCell(lv record)
]

//----------------------------------------------------------------------------
and DirSuccessor(tree, fd) = valof
//----------------------------------------------------------------------------
// Looks up the FD "fd" in the specified "tree"
// and returns a copy of the directory record for its successor,
// or 0 if no successor exists.
[
let resultRecord = 0  // must immediately follow fd in frame
MapTree(tree, fd, SuccessorFn, lv fd, 0, false, fd>>FD.pathStk, true)
resultis resultRecord
]

//----------------------------------------------------------------------------
and SuccessorFn(record, lvParam, nil) = valof
//----------------------------------------------------------------------------
// This procedure is called by MapTree with the next record for
// consideration.  lvParam!0 points to the original key (fd),
// and lvParam!1 is where to put the result when the desired record
// has been reached.  Returns false when the correct record has
// been reached, to cause MapTree to stop, and leaves the record
// in lvParam!1.  Ordinarily, SuccessorFn is called twice,
// the first time with the original key and the second time with
// that key's successor.  However, if the original key is not
// found and is lower than any key in the directory, the record
// we want will be passed on the first call.  Hence we can't just
// count calls.
[
// see comment in MatchFD
// if (record>>DR.header & drHeaderMask) ne 0 then IFSError(ecBadDR)
test DirCompareKey(lvParam!0, record) ls 0
   ifso  // here is the record we want, save it and terminate
      [ lvParam!1 = record; resultis false ]
   ifnot  // not the desired one, turn the crank again
      [ SysFree(record); resultis true ]
]

//----------------------------------------------------------------------------
and LockDirFD(fd, write; numargs na) be
//----------------------------------------------------------------------------
// Locks directory given fd.  Sets write lock if "write" is true
// and read lock if false or absent.  If a lock conflict occurs,
// sets the dirLockConflict flag so that whoever has the lock will
// notice that we are waiting.
[
let fs = fd>>FD.fs
until Lock(lv fs>>IFS.dirLock, na gr 1 & write, true) do
   [ fs>>IFS.dirLockConflict = true; Block() ]
]

//----------------------------------------------------------------------------
and UnlockDirFD(fd) be
//----------------------------------------------------------------------------
// Unlocks directory given fd.
[
let fs = fd>>FD.fs
Unlock(lv fs>>IFS.dirLock)
if fs>>IFS.dirLockConflict then
   [ fs>>IFS.dirLockConflict = false; Block() ]
]

//----------------------------------------------------------------------------
and ModifyDirFD(fd) be
//----------------------------------------------------------------------------
// Marks directory designated by fd as having been modified,
// by incrementing its version number.
[
let fs = fd>>FD.fs
if fs>>IFS.dirLock.count ge 0 %
 fs>>IFS.dirLock.ctx ne CtxRunning then IFSError(ecDirNotLocked)
fs>>IFS.dirVersion = fs>>IFS.dirVersion+1
NoticeDirectoryChange(fd)
]