(FILECREATED "11-Oct-84 13:56:01" {ERIS}<STANSBURY>VAM>VOLUMEFILEMAP.;3
 49472  

      changes to:  (FNS \DFSVFMDelete \DFSVFMGet \DFSVFMInsert \DFSVFMMerge \DFSVFMSplit)

      previous date: "11-Oct-84 11:38:24" {ERIS}<STANSBURY>VAM>VOLUMEFILEMAP.;2)


(* Copyright (c) 1984 by Xerox Corporation. All rights reserved.)

(PRETTYCOMPRINT VOLUMEFILEMAPCOMS)

(RPAQQ VOLUMEFILEMAPCOMS
 ((* * Implements {idun}<apilot100>pilot>private>VolFileMapImpl.mesa. Decided 
			     not to maintain a bufferPool (a cache of leaf BTree pages))
	(* * Updated to run on Klamath (Mesa 11)
	   formatted disks. Might not be quite Klamath-Pilot compatible.)
	(DECLARE: EVAL@COMPILE DONTCOPY (COMS * VOLUMEFILEMAPCOMPILECOMS))
	(DECLARE: (LOCALVARS . T))
	(* * Initialization routines)
	(FNS \DFSVFMInit \DFSVFMInitMap)
	(* * The following are public entry points to the volume file map module)
	(FNS \DFSVFMDeletePageGroup \DFSVFMGetPageGroup \DFSVFMInsertPageGroup \DFSVFMGenerateFileIDs)
	(* * The following are routines internal to the volume file map module.)
	(FNS \DFSVFMContextSet \DFSVFMGetBufferFor \DFSVFMCreateVPage \DFSVFMDelete \DFSVFMDelete1 
	     \DFSVFMDelete2 \DFSVFMFind \DFSVFMFreeVPage \DFSVFMGet \DFSVFMGet1 \DFSVFMInsert 
	     \DFSVFMInsert1 \DFSVFMLower \DFSVFMMerge \DFSVFMMerge1 \DFSVFMMerge2 \DFSVFMPutNext 
	     \DFSVFMReadNext \DFSVFMSplit \DFSVFMSplit1 \DFSVFMSplit2 \DFSVFMXtra)
	(GLOBALVARS \DFSVFMmaxID \DFSVFMmaxKey \DFSVFMnullKey \DFSVFMvolumeHandle \DFSVFMbuffer 
		    \DFSVFMbufferVolume \DFSVFMbufferVolumePage \DFSVFMxtraBuffer \DFSVFMinterval 
		    \DFSVFMold \DFSVFMlow \DFSVFMhigh \DFSVFMmonitor)
	(* * Interval cache interface)
	(FNS \DFSVFMCreateIntervals \DFSVFMClearIntervals \DFSVFMGetInterval \DFSVFMBlankInterval)
	(GLOBALVARS \DFSVFMintervals)
	(* * BLT routine that doesn't stomp on itself for overlapping intervals)
	(FNS \DFSSmartBLT)
	(* * Loading initialization)
	(FNS \DFSVFMAtLoad)
	(P (\DFSVFMAtLoad))))
(* * Implements {idun}<apilot100>pilot>private>VolFileMapImpl.mesa. Decided not to maintain a 
bufferPool (a cache of leaf BTree pages))


(* * Updated to run on Klamath (Mesa 11) formatted disks. Might not be quite Klamath-Pilot 
compatible.)


(DECLARE: EVAL@COMPILE DONTCOPY 

(RPAQQ VOLUMEFILEMAPCOMPILECOMS
 ((FILES (LOADCOMP)
					DLIONFS)
				 (RECORDS Index BufferArray Buffer)
				 (CONSTANTS (maxReadPtr (SUB1 (MESASIZE Buffer)))
					    (treeDepth 5))))
(FILESLOAD (LOADCOMP)
	   DLIONFS)
[DECLARE: EVAL@COMPILE 

(MESARECORD Index
 ((key Key)
		   (volumePage SWAPPEDFIXP)
		   (ptr WORD)))

(MESAARRAY BufferArray
 [(0 (
SUB1
 (
IQUOTIENT
 WORDSPERPAGE (MESASIZE Index]
		       Index)

(MESARECORD Buffer
 ((data BufferArray)
		    (used WORD))                             (* This is the structure for a BTree page)

		   (CREATE
 (create
 Page))
		   (TYPE?
 (type?
 Page DATUM)))
]
(DECLARE: EVAL@COMPILE 

(RPAQ maxReadPtr
 (SUB1 (MESASIZE Buffer)))

(RPAQQ treeDepth
 5)

(CONSTANTS (maxReadPtr (SUB1 (MESASIZE Buffer)))
	   (treeDepth 5))
)
)
(DECLARE: 
(DECLARE: DOEVAL@COMPILE DONTCOPY

(LOCALVARS)
)
)
(* * Initialization routines)


(DEFINEQ

(\DFSVFMInit

  [LAMBDA NIL                                                (* hts: "17-Jul-84 20:30")


          (* * Minimally reinitialize the volume file map state variables)



    (WITH.MONITOR \DFSVFMmonitor (UNINTERRUPTABLY

          (* * Clear out the BTree interval cache)



				     (\DFSVFMClearIntervals
)

          (* * if bufferVolumePage is NIL, then GetBufferFor will not try to flush the last buffer page)



				     (
SETQ
 \DFSVFMbufferVolumePage))])

(\DFSVFMInitMap

  [LAMBDA (vol)                                              (* hts: "20-Sep-84 14:05")

                                                             (* vol: LogicalVolumeDescriptor)

                                                             (* Public)

    (WITH.MONITOR \DFSVFMmonitor (UNINTERRUPTABLY
                                     (
PROG
 (level (oldVfmStart (fetch
 (LogicalVolumeDescriptor 
											 vfmStart)
								  of
 vol)))
				           (\DFSVFMContextSet
 vol)
				           (\DFSVFMBlankInterval
)
				           (replace
 (LogicalVolumeDescriptor vfmStart) of
 vol
					      with
 (\DFSVFMCreateVPage
))
				           (Assert (
ILESSP
 oldVfmStart (fetch
 (LogicalVolumeDescriptor
										vfmStart)
									  of
 vol)))
				           (for
 level from
 treeDepth to
 0 by
 -1
					      do
             (* init the tree)

						 (\DFSVFMInsert
 \DFSVFMnullKey (if
 (
ZEROP
 level)
										   then
 
										   nullVolumePage
										 else
 (
\DFSVFMCreateVPage
))
								level)))
				     (
PROGN
 

          (* * This block is not part of the Mesa 10.0 code)




          (* * Write out \DFSVFMbuffer)



					    (
\LvPutPage
 vol \DFSVFMbufferVolumePage \DFSVFMbuffer)))])
)
(* * The following are public entry points to the volume file map module)


(DEFINEQ

(\DFSVFMDeletePageGroup

  [LAMBDA (vol filePtr groupPtr)                             (* edited: "17-Jul-84 23:32")

                                                             (* vol: LogicalVolumeDescriptor, filePtr: 

							     FileDescriptor, groupPtr: PageGroup)


          (* Deletes all or part of a single page group from the volume file map. The page group requested to be deleted need 

	  not correspond to a single run of pages on the disk. It can be part of a single run of pages or stretch over several

	  runs of pages. In particular it is possible to delete a page or pages out of the middle of a run of pages 

	  (the scavenger uses this capability). The actual page group deleted is returned in the group pointed to by GroupPtr.

	  Thus GroupPtr points to a modifiable hint. Care must be taken by the caller to insure that the page group to be 

	  deleted exists. If it doesn't, Bug (pageGroupNotFound) is raised. This procedure implements the following funny 

	  features:)




          (* 1.0 If the page group to be deleted includes parts of more than one run of pages on the disk, only the last run 

	  (or that part of the last run requested to be deleted) will be deleted.)




          (* 2.0 If the page group to be deleted is the last page group left for the file and includes page zero of the file 

	  and at least one following page, page zero will not be deleted. This is a special case that facilitates shrinking a 

	  file to a zero-length file. VolAllocMapImpl has special case code in FreePageGroup for this also.

	  You can delete this last page of the file by specifying page group "[0..0)".)




          (* 3.0 A hole at the beginning of a file is represented as follows: if file F is missing pages 

	  (0..n) and the preceding file in the lexicographic ordering is file E of size m, then the interval in the file map 

	  representing the hole looks like this: (key: (E, m), volumePage: nullVolumePage, nextKey: (F, n)).)




          (* 4.0 A hole in the middle of the file (e.g. missing pages (m..n)) looks like this: (key: (F, m), volumePage: 

	  nullVolumePage, nextKey: (F, n)).)




          (* 5.0 This procedure does not care whether the page group being deleted corresponds to a hole in a file or to a 

	  real run of pages on the volume, with the exception of a hole at the beginning of a file. If the page group to be 

	  deleted is fully contained in a hole at the beginning of the file, Bug (pageGroupNotFound) is raised.)



    (WITH.MONITOR \DFSVFMmonitor
		  (UNINTERRUPTABLY
                      (
PROG
 ([key (create
 Key
					  fileID ←(fetch
 (FileDescriptor fileID) of
 filePtr)
					  filePage ←(
IDIFFERENCE
 (fetch
 (PageGroup nextFilePage)
								    of
 groupPtr)
								 (if
 (
EQP
 (fetch
 (PageGroup 
										     nextFilePage)
									     of
 groupPtr)
									  0)
								     then
 0
								   else
 1]
			     (interval (create
 Interval))
			     fileSize)
			    [with
 FileDescriptor filePtr (if
 (
EQ
 location (
QUOTE
 local))
							     then
 (
SETQ
 fileSize size)
							   else
 (
SHOULDNT
 (
QUOTE
 remoteFile]
			    (if
 (
IGREATERP
 (fetch
 (PageGroup nextFilePage) of
 groupPtr)
					   fileSize)
				then
 (
SHOULDNT
 (
QUOTE
 conflictingFileSize&PageGroup)))
			    (\DFSVFMContextSet
 vol)
			    (MESASETQ interval (\DFSVFMGet
 key 0)
				      Interval)              (* get interval containing last page of group)

			    (if
 (
OR
 (
NOT
 (
EQP
 (fetch
 (Key fileID) of
 (fetch
 (Interval key)
									of
 interval))
					      (fetch
 (FileDescriptor fileID) of
 filePtr)))
				    (
AND
 (
NOT
 (
EQP
 (fetch
 (Key fileID) of
 (fetch
 (Interval nextKey)
									     of
 interval))
						   (fetch
 (FileDescriptor fileID) of
 filePtr)))
					 (
EQP
 (fetch
 (Interval volumePage) of
 interval)
					      nullVolumePage)))
				then
 (
SHOULDNT
 (
QUOTE
 pageGroupNotFound)))
                                                             (* for a zero-length file, interval.nextKey.fileID # 

							     filePtr.fileID BUT interval.volumePage # 

							     nullVolumePage)

			    [replace
 (PageGroup filePage) of
 groupPtr
			       with
 (replace
 (Key filePage) of
 key
				       with
 (
MAX
 (fetch
 (Key filePage) of
 (fetch
 (Interval key)
									     of
 interval))
						 (fetch
 (PageGroup filePage) of
 groupPtr]
			    [replace
 (PageGroup volumePage) of
 groupPtr
			       with
 (if
 (
EQP
 (fetch
 (Interval volumePage) of
 interval)
					     nullVolumePage)
					then
 nullVolumePage
				      else
 (
IPLUS
 (fetch
 (Interval volumePage) of
 interval)
						  (
IDIFFERENCE
 (fetch
 (PageGroup filePage)
								  of
 groupPtr)
							       (fetch
 (Key filePage)
								  of
 (fetch
 (Interval key)
									of
 interval]
			    (replace
 (PageGroup nextFilePage) of
 groupPtr
			       with
 (
MIN
 (fetch
 (Key filePage) of
 (fetch
 (Interval nextKey)
								     of
 interval))
					 (fetch
 (PageGroup nextFilePage) of
 groupPtr)))
                                                             (* deal with the starting page of the page group first)

			    (if
 [
AND
 (MESAEQUAL key (fetch
 (Interval key) of
 interval)
						Key)
				     (
OR
 (
NOT
 (
EQP
 (fetch
 (PageGroup nextFilePage) of
 groupPtr)
						   fileSize))
					 (
NOT
 (
ZEROP
 (fetch
 (Key filePage) of
 key]
				then
 (\DFSVFMDelete
 key 0))
			    [if
 (
NOT
 (
ZEROP
 (fetch
 (Key filePage) of
 key)))
				then
 (
PROG
 [(previousKey (create
 Key
								 fileID ←(fetch
 (FileDescriptor
										  fileID)
									    of
 filePtr)
								 filePage ←(
SUB1
 (fetch
 (Key filePage)
										    of
 key]
				           (if
 (
EQP
 (fetch
 (Key fileID)
						       of
 (fetch
 (Interval key)
							     of
 (\DFSVFMGet
 previousKey 0)))
						    (fetch
 (FileDescriptor fileID) of
 filePtr))
					       then
          (* key.filePage is not the first 

							     (existing) page of the file)

						    (\DFSVFMInsert
 key nullVolumePage 0]
                                                             (* now deal with the ending page of the page group)

			    (replace
 (Key filePage) of
 key with
 (fetch
 (PageGroup nextFilePage)
								   of
 groupPtr))
			    (if
 (
EQP
 (fetch
 (Key filePage) of
 key)
				     fileSize)
				then
 (\DFSVFMDelete
 key 0))
			    (if
 [
AND
 [
NOT
 (
EQP
 (fetch
 (Key filePage) of
 key)
					       (fetch
 (Key filePage) of
 (fetch
 (Interval nextKey)
									   of
 interval]
				     (
EQP
 (fetch
 (Key fileID) of
 key)
					  (fetch
 (Key fileID) of
 (fetch
 (Interval nextKey)
								    of
 interval]
				then
 (\DFSVFMInsert
 key [if
 (
EQP
 (fetch
 (PageGroup volumePage)
								    of
 groupPtr)
								 nullVolumePage)
							    then
 nullVolumePage
							  else
 (
IPLUS
 (fetch
 (PageGroup volumePage)
									 of
 groupPtr)
								      (
IDIFFERENCE

									(fetch
 (PageGroup 
										     nextFilePage)
									   of
 groupPtr)
									(fetch
 (PageGroup filePage)
									   of
 groupPtr]
						    0)))
		      (
PROGN
                                 (* This block is not part of the Mesa 10.0 code)

			     (
\LvPutPage
 \DFSVFMvolumeHandle \DFSVFMbufferVolumePage \DFSVFMbuffer)
                                                             (* Write out \DFSVFMbuffer in case it is dirty)

			     ))])

(\DFSVFMGetPageGroup

  [LAMBDA (vol filePtr filePage)                             (* edited: "17-Jul-84 23:23")

                                                             (* vol: LogicalVolumeDescriptor, filePtr: 

							     FileDescriptor, filePage: SWAPPEDFIXP)

                                                             (* RETURNS (BOOLEAN, PageGroup))

                                                             (* Public)


          (* * finds page group containing key ((filePage = nextFilePage = size) when off end of file))



    (WITH.MONITOR \DFSVFMmonitor
		  (UNINTERRUPTABLY
                      (
PROG
 ((key (create
 Key
					  fileID ←(fetch
 (FileDescriptor fileID) of
 filePtr)
					  filePage ← filePage))
			     (interval (create
 Interval)))
			    (\DFSVFMContextSet
 vol)
			    (MESASETQ interval (\DFSVFMGet
 key 0)
				      Interval)
			    [
RETURN
 (
CONS
 (
EQP
 (fetch
 (Key fileID) of
 (fetch
 (Interval key)
									 of
 interval))
					       (fetch
 (FileDescriptor fileID) of
 filePtr))
					  (create
 PageGroup
						  filePage ←(fetch
 (Key filePage)
							       of
 (fetch
 (Interval key) of
 interval))
						  volumePage ←(fetch
 (Interval volumePage)
								 of
 interval)
						  nextFilePage ←(fetch
 (Key filePage)
								   of

								    (if

								      (
EQP

									(fetch
 (Key fileID)
									   of
 (fetch
 (Interval 
											  nextKey)
										 of
 interval))
									(fetch
 (FileDescriptor fileID)
									   of
 filePtr))
									then
 (fetch
 (Interval nextKey)
										of
 interval)
								      else
 (fetch
 (Interval key)
									      of
 interval]
                                                             (* covers page zero and size requests)

			))])

(\DFSVFMInsertPageGroup

  [LAMBDA (vol filePtr groupPtr)                             (* edited: "18-Jul-84 13:25")

                                                             (* vol: LogicalVolumeDescriptor, filePtr: 

							     FileDescriptor, groupPtr: PageGroup)

                                                             (* public)


          (* * inserts a pageGroup into B-tree (unordered inserts are merged for rebuild))



    (WITH.MONITOR \DFSVFMmonitor
		  (UNINTERRUPTABLY
                      (
PROG
 ((key (create
 Key
					  fileID ←(fetch
 (FileDescriptor fileID) of
 filePtr)
					  filePage ←(fetch
 (PageGroup filePage) of
 groupPtr)))
			     (interval (create
 Interval)))
			    (\DFSVFMContextSet
 vol)
			    (MESASETQ interval (\DFSVFMGet
 key 0)
				      Interval)
			    (if
 (MESAEQUAL (fetch
 (Interval key) of
 interval)
					   key Key)
				then
 (\DFSVFMDelete
 key 0)
				     (MESASETQ interval (\DFSVFMGet
 key 0)
					       Interval))
			    (if
 [
OR
 [
NOT
 (
EQP
 (
IDIFFERENCE
 (fetch
 (Key filePage) of
 key)
							   (fetch
 (Key filePage)
							      of
 (fetch
 (Interval key) of
 interval)))
					      (
IDIFFERENCE
 (fetch
 (PageGroup volumePage)
							      of
 groupPtr)
							   (fetch
 (Interval volumePage) of
 interval]
				    (
NOT
 (
EQP
 (fetch
 (Key fileID) of
 key)
					      (fetch
 (Key fileID) of
 (fetch
 (Interval key)
									of
 interval]
				then
                         (* don't merge with previous)

				     (\DFSVFMInsert
 key (fetch
 (PageGroup volumePage) of
 groupPtr)
						    0)
				     (MESASETQ interval (\DFSVFMGet
 key 0)
					       Interval))
			    (replace
 (Key filePage) of
 key with
 (fetch
 (PageGroup nextFilePage)
								   of
 groupPtr))
			    (if
 [
AND
 (
NOT
 (MESAEQUAL (fetch
 (Interval nextKey) of
 interval)
						     key Key))
				     (
NOT
 (
EQP
 (fetch
 (PageGroup filePage) of
 groupPtr)
					       (fetch
 (PageGroup nextFilePage) of
 groupPtr]
				then
 (\DFSVFMInsert
 key nullVolumePage 0))
			    (if
 [
AND
 (MESAEQUAL (fetch
 (Interval nextKey) of
 interval)
						key Key)
				     (
EQP
 (fetch
 (Interval volumePage) of
 (\DFSVFMGet
 key 0))
					  (
IPLUS
 (fetch
 (Interval volumePage) of
 interval)
						 (
IDIFFERENCE
 (fetch
 (Key filePage)
								 of
 (fetch
 (Interval nextKey)
								       of
 interval))
							      (fetch
 (Key filePage)
								 of
 (fetch
 (Interval key)
								       of
 interval]
				then
 (\DFSVFMDelete
 key 0) 
                                                             (* merge with following)
))
		      (
PROGN
 

          (* * This block is not part of the Mesa 10.0 code)




          (* * Write out \DFSVFMbuffer in case it is dirty)



			     (
\LvPutPage
 \DFSVFMvolumeHandle \DFSVFMbufferVolumePage \DFSVFMbuffer)))]
)

(\DFSVFMGenerateFileIDs

  [LAMBDA (vol)                                              (* hts: "17-Jul-84 20:45")

                                                             (* vol: LogicalVolumeDescriptor)

                                                             (* Returns all the fileIDs currently in the BTree)

    (WITH.MONITOR \DFSVFMmonitor (UNINTERRUPTABLY
                                     (\DFSVFMContextSet
 vol)
				     (bind
 (currentKey ←(create
 Key))
					until
 (
PROGN
 (replace
 (Key filePage) of
 currentKey
							with
 MAX.FIXP)
						     (MESASETQ currentKey (fetch
 (Interval nextKey)
									     of
 (\DFSVFMGet
 
										       currentKey 0))
							       Key)
						     (
EQP
 (fetch
 (Key fileID) of
 currentKey)
							  \DFSVFMmaxID))
					collect
 (fetch
 (Key fileID) of
 currentKey)))])
)
(* * The following are routines internal to the volume file map module.)


(DEFINEQ

(\DFSVFMContextSet

  [LAMBDA (vol)                                              (* hts: "17-Jul-84 21:20")

                                                             (* vol: LogicalVolumeDescriptor)

                                                             (* Internal)

    (
SETQ
 \DFSVFMvolumeHandle vol])

(\DFSVFMGetBufferFor

  [LAMBDA (page)                                             (* edited: "23-Jul-84 10:10")

                                                             (* page: SWAPPEDFIXP)

                                                             (* Internal)


          (* * Reads page# page into \DFSVFMbuffer (if it isn't already there). Flushes old buffer (if any) first)



    (if
 (
NOT
 (
AND
 \DFSVFMbufferVolumePage (LVEqual \DFSVFMvolumeHandle \DFSVFMbufferVolume)
		  (
EQP
 page \DFSVFMbufferVolumePage)))
	then
 (if
 \DFSVFMbufferVolumePage
		 then
                                        (* Write out old \DFSVFMbuffer page in case it is 

							     dirty.)

		      (
\LvPutPage
 \DFSVFMbufferVolume \DFSVFMbufferVolumePage \DFSVFMbuffer))
	     (UNINTERRUPTABLY                                (* Record what volume the buffer comes from)

		 (
SETQ
 \DFSVFMbufferVolume \DFSVFMvolumeHandle)
                                                             (* Remember what page the \DFSVFMbuffer came from)

		 (
SETQ
 \DFSVFMbufferVolumePage page)         (* and read it in)

		 (
\LvGetPage
 \DFSVFMvolumeHandle \DFSVFMbufferVolumePage \DFSVFMbuffer))])

(\DFSVFMCreateVPage

  [LAMBDA NIL                                                (* edited: "17-Jul-84 23:04")

                                                             (* Returns SWAPPEDFIXP)

                                                             (* Internal)


          (* * Calls VolAllocMap.AllocPageGroup to get a new page for the vfm B-tree. Returns its volume-relative page 

	  number.)



    (with
 LogicalVolumeDescriptor \DFSVFMvolumeHandle
	  (
PROG
 ((group (create
 PageGroup
				filePage ← 0
				volumePage ← 0
				nextFilePage ← 1))
		 (vfmFileD (create
 FileDescriptor
				   fileID ←(Vfm \DFSVFMvolumeHandle)
				   volumeID ← vID
				   location ←(
QUOTE
 local)
				   immutable ← NIL
				   temporary ← NIL
				   type ← tVolumeFileMap)))
	        (
\DFSVAMAllocPageGroup
 \DFSVFMvolumeHandle vfmFileD group T)
	        (
RETURN
 (fetch
 (PageGroup volumePage) of
 group])

(\DFSVFMDelete

  [LAMBDA (deleteKey deleteLevel)                            (* hts: "11-Oct-84 13:29")

                                                             (* key: Key, level: SMALLP)

                                                             (* Internal)

                                                             (* Deletes the index = key, error if no such index 

							     (Merge is called from \DFSVFMFind))

    (DECLARE
 (
SPECVARS
 deleteKey deleteLevel))
    (
PROG
 (firstFlag lastFlag volumePage (nextKey (create
 Key)))
                                                             (* volumePage is the page holding the key 

							     (delete if firstFlag AND lastFlag))

                                                             (* nextKey is the following key;

							     must be slid down over deleted key)

          (DECLARE
 (
SPECVARS
 firstFlag lastFlag volumePage nextKey))
          (\DFSVFMFind
 deleteKey deleteLevel (
FUNCTION
 \DFSVFMDelete1))
                                                             (* Get the preceding index)

          [if
 firstFlag
	      then
 (\DFSVFMDelete
 deleteKey (
ADD1
 deleteLevel))
		   (if
 lastFlag
		       then
 (\DFSVFMFreeVPage
 volumePage)
		     else
 (\DFSVFMInsert
 nextKey volumePage (
ADD1
 deleteLevel]
          (\DFSVFMFind
 deleteKey deleteLevel (
FUNCTION
 \DFSVFMDelete2)))
                                                             (* Get the preceding index)

    ])

(\DFSVFMDelete1

  [LAMBDA NIL                                                (* hts: " 6-Jun-84 14:19")

                                                             (* Internal)

    (
SETQ
 firstFlag (
EQP
 (fetch
 (Index ptr) of
 \DFSVFMlow)
			 0))
    (
SETQ
 lastFlag (
EQP
 (fetch
 (Index ptr) of
 \DFSVFMhigh)
			(fetch
 (Buffer used) of
 \DFSVFMbuffer)))
    (
SETQ
 volumePage (fetch
 (Interval volumePage) of
 \DFSVFMinterval))
    (MESASETQ nextKey (fetch
 (Index key) of
 \DFSVFMhigh)
	      Key)
    (if
 (
NOT
 (MESAEQUAL (fetch
 (Index key) of
 \DFSVFMlow)
			deleteKey Key))
	then
 (
SHOULDNT
 "DeleteError"))
    (if
 (
AND
 firstFlag (
NOT
 lastFlag))
	then
 (\DFSSmartBLT
 \DFSVFMbuffer (
\ADDBASE
 \DFSVFMbuffer (fetch
 (Index ptr) of
 \DFSVFMhigh))
			   (replace
 (Buffer used) of
 \DFSVFMbuffer with
 (
IDIFFERENCE

									  (fetch
 (Buffer used)
									     of
 \DFSVFMbuffer)
									  (fetch
 (Index ptr)
									     of
 \DFSVFMhigh])

(\DFSVFMDelete2

  [LAMBDA NIL                                                (* hts: " 6-Jun-84 14:19")

                                                             (* Internal)

    (replace
 (Index key) of
 \DFSVFMhigh with
 nextKey)
    (replace
 (Index volumePage) of
 \DFSVFMhigh with
 (fetch
 (Index volumePage) of
 \DFSVFMlow))
    (MESASETQ \DFSVFMlow \DFSVFMold Index)
    (\DFSSmartBLT
 (
\ADDBASE
 \DFSVFMbuffer (
IPLUS
 (fetch
 (Index ptr) of
 \DFSVFMlow)
						 (MESASIZE Index)))
		  (
\ADDBASE
 \DFSVFMbuffer (fetch
 (Index ptr) of
 \DFSVFMhigh))
		  (
IDIFFERENCE
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
			       (fetch
 (Index ptr) of
 \DFSVFMhigh)))
    (\DFSVFMPutNext
 (fetch
 (Index key) of
 \DFSVFMhigh)
		    (fetch
 (Index volumePage) of
 \DFSVFMhigh)
		    deleteLevel)
    (replace
 (Buffer used) of
 \DFSVFMbuffer with
 (
IDIFFERENCE
 (
IPLUS
 (fetch
 (Index ptr) of
 \DFSVFMlow)
								     (fetch
 (Buffer used)
									of
 \DFSVFMbuffer))
							      (fetch
 (Index ptr) of
 \DFSVFMhigh])

(\DFSVFMFind

  [LAMBDA (key level proc)                                   (* hts: " 6-Jun-84 13:42")

                                                             (* key: Key, level: SMALLP, proc: FUNCTION)

                                                             (* Internal)

                                                             (* executes proc with context 

							     (buffer, low, \DFSVFMhigh) surrounding key 

							     (merges too))

    (MESASETQ \DFSVFMinterval (\DFSVFMGet
 key (
ADD1
 level))
	      Interval)
    (\DFSVFMGetBufferFor
 (fetch
 (Interval volumePage) of
 \DFSVFMinterval))
    (replace
 (Index key) of
 \DFSVFMold with
 (fetch
 (Interval key) of
 \DFSVFMinterval))
    (replace
 (Index volumePage) of
 \DFSVFMold with
 nullVolumePage)
    (replace
 (Index ptr) of
 \DFSVFMold with
 0)
    (MESASETQ \DFSVFMlow \DFSVFMold Index)
    (MESASETQ \DFSVFMhigh \DFSVFMlow Index)                  (* Initialize reader)

    (repeatuntil
 (\DFSVFMLower
 key (fetch
 (Index key) of
 \DFSVFMhigh)) do
 (\DFSVFMReadNext
))
                                                             (* Scan this page till key is passed)

    (
APPLY
 proc)
    (if
 (
AND
 (
ILEQ
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
		   (
IQUOTIENT
 (MESASIZE Buffer)
			      3))
	     (
NOT
 (MESAEQUAL (fetch
 (Interval nextKey) of
 \DFSVFMinterval)
			     \DFSVFMmaxKey Key)))
	then
 (\DFSVFMMerge
 (fetch
 (Index key) of
 \DFSVFMold)
			   level])

(\DFSVFMFreeVPage

  [LAMBDA (volumePage)                                       (* edited: "17-Jul-84 23:07")

                                                             (* volumePage: SWAPPEDFIXP)

                                                             (* Internal)


          (* * calls VolAllocMap.FreePageGroup to free a page of the vfm BTree)



    (with
 LogicalVolumeDescriptor \DFSVFMvolumeHandle
	  (
PROG
 ((group (create
 PageGroup
				filePage ← volumePage
				volumePage ← volumePage
				nextFilePage ←(
ADD1
 volumePage)))
		 (vfmFileD (create
 FileDescriptor
				   fileID ←(Vfm \DFSVFMvolumeHandle)
				   volumeID ← vID
				   location ←(
QUOTE
 local)
				   immutable ← NIL
				   temporary ← NIL
				   type ← tVolumeFileMap)))
	        (
\DFSVAMFreePageGroup
 \DFSVFMvolumeHandle vfmFileD group T])

(\DFSVFMGet

  [LAMBDA (getKey getLevel)                                  (* hts: "11-Oct-84 13:28")

                                                             (* key: Key, level: SMALLP; returns Interval)

                                                             (* Internal)

    (DECLARE
 (
SPECVARS
 getKey getLevel))
    (
PROG
 NIL
          (if
 (
IGREATERP
 getLevel (
ADD1
 treeDepth))
	      then
 (
SHOULDNT
 (
QUOTE
 manThisHereIntervalCacheItBeFuckedUp)))
          (if
 (
EQP
 getLevel (
ADD1
 treeDepth))
	      then
 (
RETURN
 (create
 Interval
				   key ← \DFSVFMnullKey
				   volumePage ←(fetch
 (LogicalVolumeDescriptor vfmStart)
						  of
 \DFSVFMvolumeHandle)
				   nextKey ← \DFSVFMmaxKey)))
          (MESASETQ \DFSVFMinterval (
ELT
 (\DFSVFMGetInterval
)
					 getLevel)
		    Interval)
          (if
 [
OR
 (\DFSVFMLower
 getKey (fetch
 (Interval key) of
 \DFSVFMinterval))
		  (
NOT
 (\DFSVFMLower
 getKey (fetch
 (Interval nextKey) of
 \DFSVFMinterval]
	      then
 (\DFSVFMFind
 getKey getLevel (
FUNCTION
 \DFSVFMGet1)))
          (
RETURN
 (
ELT
 (\DFSVFMGetInterval
)
		       getLevel])

(\DFSVFMGet1

  [LAMBDA NIL                                                (* hts: "17-Jul-84 21:40")

                                                             (* Internal)

    (
SETA
 (\DFSVFMGetInterval
)
	  getLevel
	  (create
 Interval
		  key ←(fetch
 (Interval key) of
 \DFSVFMlow)
		  volumePage ←(fetch
 (Interval volumePage) of
 \DFSVFMhigh)
		  nextKey ←(fetch
 (Interval key) of
 \DFSVFMhigh])

(\DFSVFMInsert

  [LAMBDA (insertKey insertVolumePage insertLevel)           (* hts: "11-Oct-84 13:27")

                                                             (* key: Key, volumePage: PageNumber, level: Level)

                                                             (* Internal)

                                                             (* Inserts insertKey into insertVolumePage 

							     (including duplicates) calling split if necessary)

    (DECLARE
 (
SPECVARS
 insertKey insertVolumePage insertLevel))
    (
PROG
 (splitFlag)
          (DECLARE
 (
SPECVARS
 splitFlag))
          (\DFSVFMFind
 insertKey insertLevel (
FUNCTION
 \DFSVFMInsert1))
          (if
 splitFlag
	      then
 (\DFSVFMSplit
 insertKey insertLevel)
		   (\DFSVFMFind
 insertKey insertLevel (
FUNCTION
 \DFSVFMInsert1])

(\DFSVFMInsert1

  [LAMBDA NIL                                                (* hts: " 6-Jun-84 15:15")

                                                             (* Internal)

    (
PROG
 NIL
          (if
 [
SETQ
 splitFlag (
IGREATERP
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
					 (
IDIFFERENCE
 maxReadPtr (MESASIZE Index]
	      then
 (
RETURN
))
          [if
 (
ILESSP
 (fetch
 (Index ptr) of
 \DFSVFMlow)
		      (fetch
 (Buffer used) of
 \DFSVFMbuffer))
	      then
 (\DFSSmartBLT
 (
\ADDBASE
 \DFSVFMbuffer (
IPLUS
 (fetch
 (Index ptr) of
 \DFSVFMlow)
								(
ITIMES
 (MESASIZE Index)
									2)))
				 (
\ADDBASE
 \DFSVFMbuffer (fetch
 (Index ptr) of
 \DFSVFMhigh))
				 (
IDIFFERENCE
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
					      (fetch
 (Index ptr) of
 \DFSVFMhigh)))
		   (\DFSVFMPutNext
 insertKey (fetch
 (Index volumePage) of
 \DFSVFMhigh)
				   insertLevel)
	    else
 (\DFSSmartBLT
 (
\ADDBASE
 \DFSVFMbuffer (
IPLUS
 (fetch
 (Index ptr) of
 \DFSVFMlow)
							      (MESASIZE Index)))
			       (
\ADDBASE
 \DFSVFMbuffer (fetch
 (Index ptr) of
 \DFSVFMhigh))
			       (
IDIFFERENCE
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
					    (fetch
 (Index ptr) of
 \DFSVFMhigh]
          (\DFSVFMPutNext
 (fetch
 (Index key) of
 \DFSVFMhigh)
			  insertVolumePage insertLevel)
          (replace
 (Buffer used) of
 \DFSVFMbuffer with
 (
IDIFFERENCE
 (
IPLUS
 (fetch
 (Index ptr)
									      of
 \DFSVFMlow)
									   (fetch
 (Buffer used)
									      of
 \DFSVFMbuffer))
								    (fetch
 (Index ptr) of
 \DFSVFMhigh]
)

(\DFSVFMLower

  [LAMBDA (a b)                                              (* hts: "17-Jul-84 22:09")

                                                             (* a: Key, b: Key; returns BOOLEAN)

                                                             (* Internal)


          (* * Compares two keys for ordering; maxKey < maxKey to close key space)



    (
OR
 (
ILESSP
 (fetch
 (Key fileID) of
 a)
		(fetch
 (Key fileID) of
 b))
	(
AND
 (
EQP
 (fetch
 (Key fileID) of
 a)
		  (fetch
 (Key fileID) of
 b))
	     (
OR
 (
ILESSP
 (fetch
 (Key filePage) of
 a)
			 (fetch
 (Key filePage) of
 b))
		 (MESAEQUAL b \DFSVFMmaxKey Key])

(\DFSVFMMerge

  [LAMBDA (mergeKey mergeLevel)                              (* hts: "11-Oct-84 13:30")

                                                             (* key: Key, level: SMALLP)

                                                             (* Internal)

                                                             (* Tries to merge page of oldIntervalwith next page at 

							     same mergeLevel or with root;

							     cannot merge last page of any mergeLevel except 

							     rootlevel)

    (DECLARE
 (
SPECVARS
 mergeKey mergeLevel))
    (
PROG
 (mergeFlag (leftInterval (create
 Interval))
		     (rightInterval (create
 Interval)))
          (DECLARE
 (
SPECVARS
 mergeFlag leftInterval rightInterval))
          (MESASETQ leftInterval (\DFSVFMGet
 mergeKey (
ADD1
 mergeLevel))
		    Interval)                                (* so as to get a valid volumePage)

          (\DFSVFMFind
 (fetch
 (Interval nextKey) of
 leftInterval)
		       mergeLevel
		       (
FUNCTION
 \DFSVFMMerge1))             (* beware the merging)

          (\DFSVFMDelete
 (fetch
 (Interval nextKey) of
 leftInterval)
			 (
ADD1
 mergeLevel))
          (if
 mergeFlag
	      then
 (\DFSVFMFreeVPage
 (fetch
 (Interval volumePage) of
 rightInterval))
	    else
 (\DFSVFMInsert
 (fetch
 (Interval key) of
 rightInterval)
				(fetch
 (Interval volumePage) of
 rightInterval)
				(
ADD1
 mergeLevel)))          (* insert new index)

      ])

(\DFSVFMMerge1

  [LAMBDA NIL                                                (* hts: " 5-Apr-84 00:58")

                                                             (* Internal)

    (MESASETQ rightInterval \DFSVFMinterval Interval)
    (\DFSVFMXtra
 (fetch
 (Interval volumePage) of
 leftInterval)
		 (
FUNCTION
 \DFSVFMMerge2])

(\DFSVFMMerge2

  [LAMBDA NIL                                                (* edited: "17-Jul-84 23:11")

                                                             (* Internal)

    (
PROG
 ((xtraBufferUsed (fetch
 (Buffer used) of
 \DFSVFMxtraBuffer)))
                                                             (* xtraBufferUsed used to solve stack modeling error)

          (if
 (
EQP
 mergeLevel treeDepth)
	      then
 (replace
 (Buffer used) of
 \DFSVFMxtraBuffer with
 0))
                                                             (* clear now instead of deleteing later)

          (if
 (
SETQ
 mergeFlag (
ILESSP
 (
IPLUS
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
					     (fetch
 (Buffer used) of
 \DFSVFMxtraBuffer))
				      (MESASIZE Buffer)))
	      then
                                           (* If merging possible then merge pages)

		   (\DFSSmartBLT
 (
\ADDBASE
 \DFSVFMxtraBuffer xtraBufferUsed)
				 \DFSVFMbuffer
				 (fetch
 (Buffer used) of
 \DFSVFMbuffer))
                                                             (* merge \DFSVFMbuffer with xtra)

		   (replace
 (Buffer used) of
 \DFSVFMxtraBuffer with
 (
IPLUS
 (fetch
 (Buffer used)
									      of
 \DFSVFMxtraBuffer)
									   (fetch
 (Buffer used)
									      of
 \DFSVFMbuffer)))
                                                             (* buffer.used remains to prevent Find from attempting 

							     a merge)

		   
	    else
                                             (* balance pages simply to provide hysteresis against 

							     futile merge attempts)

		 (while
 (
ILESSP
 (fetch
 (Index ptr) of
 \DFSVFMlow)
				(
IQUOTIENT
 (
IDIFFERENCE
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
							(fetch
 (Buffer used) of
 \DFSVFMxtraBuffer))
					   2))
		    do
 (\DFSVFMReadNext
))                    (* find middle)

		 (\DFSSmartBLT
 (
\ADDBASE
 \DFSVFMxtraBuffer xtraBufferUsed)
			       \DFSVFMbuffer
			       (fetch
 (Index ptr) of
 \DFSVFMlow))
                                                             (* move first of \DFSVFMbuffer to xtra)

		 (\DFSSmartBLT
 \DFSVFMbuffer (
\ADDBASE
 \DFSVFMbuffer (fetch
 (Index ptr) of
 \DFSVFMlow)
						       )
			       (
IDIFFERENCE
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
					    (fetch
 (Index ptr) of
 \DFSVFMlow)))
                                                             (* slide down the rest of \DFSVFMbuffer)

		 (replace
 (Buffer used) of
 \DFSVFMxtraBuffer with
 (
IPLUS
 (fetch
 (Buffer used)
									    of
 \DFSVFMxtraBuffer)
									 (fetch
 (Index ptr)
									    of
 \DFSVFMlow)))
		 (replace
 (Buffer used) of
 \DFSVFMbuffer with
 (
IDIFFERENCE
 (fetch
 (Buffer used)
									      of
 \DFSVFMbuffer)
									   (fetch
 (Index ptr)
									      of
 \DFSVFMlow)))
                                                             (* use \DFSVFMlow to insert while it is still valid)

		 (replace
 (Interval key) of
 rightInterval with
 (fetch
 (Index key) of
 \DFSVFMlow])

(\DFSVFMPutNext

  [LAMBDA (key volumePage level)                             (* edited: "17-Jul-84 23:43")

                                                             (* key: Key, volumePage: SWAPPEDFIXP, level: SMALLP)

                                                             (* Internal)


          (* Compresses item in the context of low. Note the side effect on \DFSVFMlow but not on high!! No compression is 

	  implemented in this version, but useful one would include: front compression (especially to shrink page groups back 

	  to 2 fields))



    (MESASETQ \DFSVFMold \DFSVFMlow Index)
    (
PROG
 ((lowPtr (fetch
 (Index ptr) of
 \DFSVFMlow)))
          (MESASETQ \DFSVFMlow (create
 Index
				       key ← key
				       volumePage ← volumePage
				       ptr ←(MESASIZE Index))
		    Index)
          (MESASETQ (
\ADDBASE
 (fetch
 (Buffer data) of
 \DFSVFMbuffer)
			      lowPtr)
		    \DFSVFMlow Index))
    (replace
 (Index ptr) of
 \DFSVFMlow with
 (
IPLUS
 (fetch
 (Index ptr) of
 \DFSVFMlow)
						   (fetch
 (Index ptr) of
 \DFSVFMold)))
                                                             (* ptr is just an increment)

                                                             (* low:Index.ptr was just an increment)

    (
SETA
 (\DFSVFMGetInterval
)
	  level
	  (create
 Interval
		  key ←(fetch
 (Index key) of
 \DFSVFMold)
		  volumePage ←(fetch
 (Index volumePage) of
 \DFSVFMlow)
		  nextKey ←(fetch
 (Index key) of
 \DFSVFMlow)))
                                                             (* keep cache up to date in the face of changes)

    ])

(\DFSVFMReadNext

  [LAMBDA NIL                                                (* edited: "17-Jul-84 23:13")

                                                             (* Internal)


          (* Decompresses item at \DFSVFMhigh to become \DFSVFMlow & bumps high. Note the side effect on \DFSVFMlow and high!!

	  No compression is implemented in this version)



    (if
 (
IGREATERP
 (fetch
 (Index ptr) of
 \DFSVFMhigh)
		   (fetch
 (Buffer used) of
 \DFSVFMbuffer))
	then
 (
SHOULDNT
 (
QUOTE
 nonexistentInterval)))
    (MESASETQ \DFSVFMold \DFSVFMlow Index)
    (MESASETQ \DFSVFMlow \DFSVFMhigh Index)
    (MESASETQ \DFSVFMhigh (if
 (
ILESSP
 (fetch
 (Index ptr) of
 \DFSVFMhigh)
				      (fetch
 (Buffer used) of
 \DFSVFMbuffer))
			      then
                           (* Loophole)

				   (
\ADDBASE
 (fetch
 (Buffer data) of
 \DFSVFMbuffer)
					     (fetch
 (Index ptr) of
 \DFSVFMhigh))
			    else
 (create
 Index
					 key ← \DFSVFMmaxKey
					 volumePage ← nullVolumePage
					 ptr ← 0))
	      Index)
    (replace
 (Index ptr) of
 \DFSVFMhigh with
 (
IPLUS
 (fetch
 (Index ptr) of
 \DFSVFMhigh)
						    (fetch
 (Index ptr) of
 \DFSVFMlow)))
                                                             (* high:Index.ptr was just an increment)

    ])

(\DFSVFMSplit

  [LAMBDA (splitKey splitLevel)                              (* hts: "11-Oct-84 13:31")

                                                             (* key: Key, level: SMALLP)

                                                             (* Internal)


          (* * moves half of \DFSVFMbuffer (or root) to xtraBuffer, creating new page of tree)



    (DECLARE
 (
SPECVARS
 splitKey splitLevel))
    (
PROG
 ((keyStone (create
 Key))
	   (page (\DFSVFMCreateVPage
)))                      (* keyStone is the half way mark)

          (DECLARE
 (
SPECVARS
 keyStone page))
          (\DFSVFMFind
 splitKey splitLevel (
FUNCTION
 \DFSVFMSplit1))
          (\DFSVFMInsert
 keyStone page (
ADD1
 splitLevel])

(\DFSVFMSplit1

  [LAMBDA NIL                                                (* hts: " 5-Apr-84 00:58")

                                                             (* Internal)

    (\DFSVFMXtra
 page (
FUNCTION
 \DFSVFMSplit2])

(\DFSVFMSplit2

  [LAMBDA NIL                                                (* hts: " 6-Jun-84 14:46")

                                                             (* Internal)

    (MESASETQ \DFSVFMhigh (create
 Index
				  key ←(fetch
 (Interval key) of
 \DFSVFMinterval)
				  volumePage ← nullVolumePage
				  ptr ← 0)
	      Index)                                         (* quick readReset)

    (repeatuntil
 (
IGREATERP
 (fetch
 (Index ptr) of
 \DFSVFMhigh)
			    (
IQUOTIENT
 (fetch
 (Buffer used) of
 \DFSVFMbuffer)
				       2))
       do
 (\DFSVFMReadNext
))
    [
\BLT
 \DFSVFMxtraBuffer (
\ADDBASE
 (fetch
 (Buffer data) of
 \DFSVFMbuffer)
				      (fetch
 (Index ptr) of
 \DFSVFMlow))
	  (replace
 (Buffer used) of
 \DFSVFMxtraBuffer with
 (
IDIFFERENCE
 (fetch
 (Buffer used)
									   of
 \DFSVFMbuffer)
									(fetch
 (Index ptr)
									   of
 \DFSVFMlow]
                                                             (* split)

    (replace
 (Buffer used) of
 \DFSVFMbuffer with
 (fetch
 (Index ptr) of
 \DFSVFMlow))
    (MESASETQ keyStone (fetch
 (Index key) of
 \DFSVFMlow)
	      Key])

(\DFSVFMXtra

  [LAMBDA (page proc)                                        (* edited: "17-Jul-84 22:58")

                                                             (* page: SWAPPEDFIXP, proc: FUNCTION)

                                                             (* Internal)

                                                             (* maps, operates, unmaps \DFSVFMxtraBuffer)

    (
\LvGetPage
 \DFSVFMvolumeHandle page \DFSVFMxtraBuffer)
    (
APPLY
 proc)
    (
\LvPutPage
 \DFSVFMvolumeHandle page \DFSVFMxtraBuffer])
)
(DECLARE: DOEVAL@COMPILE DONTCOPY

(GLOBALVARS \DFSVFMmaxID \DFSVFMmaxKey \DFSVFMnullKey \DFSVFMvolumeHandle \DFSVFMbuffer 
	    \DFSVFMbufferVolume \DFSVFMbufferVolumePage \DFSVFMxtraBuffer \DFSVFMinterval \DFSVFMold 
	    \DFSVFMlow \DFSVFMhigh \DFSVFMmonitor)
)
(* * Interval cache interface)


(DEFINEQ

(\DFSVFMCreateIntervals

  [LAMBDA NIL                                                (* hts: "17-Jul-84 21:04")


          (* * Conditionally create array to hold interval cache for each volume. Conditional so that loadfroming this file 

	  will not destroy state.)




          (* * Interval cache for each volume keeps a finger into the BTree: traces a correct path through the BTree, which 

	  need be only partially backtracked (if at all) to find any given interval in the BTree. Saves reading one page at 

	  each level of the BTree every time you want to look for an interval.)



    (if
 [
NOT
 (
AND
 (
BOUNDP
 (
QUOTE
 \DFSVFMintervals))
		  (type?
 ARRAYP \DFSVFMintervals)
		  (
ZEROP
 (
ARRAYORIG
 \DFSVFMintervals))
		  (
EQ
 maxLogicalVolumes (
ARRAYSIZE
 \DFSVFMintervals]
	then
 (
SETQ
 \DFSVFMintervals (
ARRAY
 maxLogicalVolumes NIL NIL 0])

(\DFSVFMClearIntervals

  [LAMBDA NIL                                                (* hts: "17-Jul-84 20:51")


          (* * Clears the BTree interval cache so that it will be correctly reinitialized should this lisp image wake up on an

	  alien machine)



    (for
 volume from
 0 to
 (
SUB1
 maxLogicalVolumes) do
 (
SETA
 \DFSVFMintervals volume NIL])

(\DFSVFMGetInterval

  [LAMBDA NIL                                                (* hts: "30-Jul-84 21:46")


          (* * Returns the interval cache for the current volume. If this interval cache is empty, initializes with a leftmost

	  path through the BTree for that volume.)



    (
PROG
 ((volNum (VolumeNumber \DFSVFMvolumeHandle)))
          (
RETURN
 (
OR
 (
ELT
 \DFSVFMintervals volNum)
		      (
SETA
 \DFSVFMintervals volNum (bind
 intervalCache BTreePageNum BTreePage 
							  interval
						       first
 (
SETQ
 intervalCache (
ARRAY
 (
ADD1
 
											treeDepth)
											NIL NIL 0))
							     (
SETQ
 BTreePageNum (fetch
 (
LogicalVolumeDescriptor vfmStart) of
 \DFSVFMvolumeHandle))
						       for
 level from
 treeDepth to
 0 by
 -1
						       do
 (
SETQ
 interval (create
 Interval))
							  (
SETQ
 BTreePage (
\LvGetPage
 vol 
										     BTreePageNum))
							  (replace
 (Interval volumePage)
							     of
 interval with
 (fetch
 (Index 
										       volumePage)
										 of
 BTreePage))
							  (replace
 (Interval nextKey) of
 interval
							     with
 (fetch
 (Index key) of
 BTreePage))
							  (
SETQ
 BTreePageNum (fetch
 (Interval 
										       volumePage)
										of
 interval))
							  (
SETA
 intervalCache level interval)
						       finally
 (
RETURN
 intervalCache])

(\DFSVFMBlankInterval

  [LAMBDA NIL                                                (* hts: "30-Jul-84 21:45")


          (* * Returns the interval cache for the current volume. If this interval cache is empty, initializes with a blank 

	  set of intervals with InitMap will fill with a leftmost path through the BTree for that volume.)




          (* * Should be called by InitMap only.)



    (
PROG
 ((volNum (VolumeNumber \DFSVFMvolumeHandle)))
          (
RETURN
 (
OR
 (
ELT
 \DFSVFMintervals volNum)
		      (
SETA
 \DFSVFMintervals volNum (
PROG
 ((intervalCache (
ARRAY
 (
ADD1
 treeDepth)
										 NIL NIL 0)))
						          (for
 level from
 0 to
 treeDepth
							     do
 (
SETA
 intervalCache level
								      (create
 Interval)))
						          (
RETURN
 intervalCache])
)
(DECLARE: DOEVAL@COMPILE DONTCOPY

(GLOBALVARS \DFSVFMintervals)
)
(* * BLT routine that doesn't stomp on itself for overlapping intervals)


(DEFINEQ

(\DFSSmartBLT

  [LAMBDA (DBASE SBASE NWORDS)                               (* hts: "24-Jun-84 15:57")

                                                             (* This is necessary because \BLT will not copy 

							     overlapping intervals correctly in one direction.)

    (if
 (
AND
 (PTRGTP SBASE DBASE)
	     (PTRGTP (
\ADDBASE
 DBASE NWORDS)
		     SBASE))
	then
 (for
 i from
 0 to
 (
SUB1
 NWORDS) do
 (
\PUTBASE
 DBASE i (
\GETBASE
 SBASE i)))
	     DBASE
      else
 (
\BLT
 DBASE SBASE NWORDS])
)
(* * Loading initialization)


(DEFINEQ

(\DFSVFMAtLoad

  [LAMBDA NIL                                                (* hts: "17-Jul-84 21:19")


          (* * Initialize global variables for the volume file map)



    (
SETQ
 \DFSVFMmaxID MAX.FIXP)
    (
SETQ
 \DFSVFMmaxKey (create
 Key
				fileID ← \DFSVFMmaxID
				filePage ← lastPageNumber))
    (
SETQ
 \DFSVFMnullKey (create
 Key))
    (
SETQ
 \DFSVFMvolumeHandle)
    (
SETQ
 \DFSVFMbuffer (create
 Buffer))
    (
SETQ
 \DFSVFMbufferVolume)
    (
SETQ
 \DFSVFMbufferVolumePage)
    (
SETQ
 \DFSVFMxtraBuffer (create
 Buffer))
    (
SETQ
 \DFSVFMinterval (create
 Interval))
    (
SETQ
 \DFSVFMold (create
 Index))
    (
SETQ
 \DFSVFMlow (create
 Index))
    (
SETQ
 \DFSVFMhigh (create
 Index))
    (\DFSVFMCreateIntervals
)
    (
SETQ
 \DFSVFMmonitor (
CREATE.MONITORLOCK
 (
QUOTE
 \DFSVFMmonitor])
)
(\DFSVFMAtLoad)
(PUTPROPS VOLUMEFILEMAP COPYRIGHT ("Xerox Corporation" 1984))
(DECLARE: DONTCOPY
  (FILEMAP (NIL (3162 4998 (\DFSVFMInit 3172 . 3666) (\DFSVFMInitMap 3668 . 4996)) (5079 18909 (
\DFSVFMDeletePageGroup 5089 . 13026) (\DFSVFMGetPageGroup 13028 . 14923) (\DFSVFMInsertPageGroup 14925
 . 18007) (\DFSVFMGenerateFileIDs 18009 . 18907)) (18989 43796 (\DFSVFMContextSet 18999 . 19329) (
\DFSVFMGetBufferFor 19331 . 20570) (\DFSVFMCreateVPage 20572 . 21520) (\DFSVFMDelete 21522 . 23089) (
\DFSVFMDelete1 23091 . 24169) (\DFSVFMDelete2 24171 . 25311) (\DFSVFMFind 25313 . 26904) (
\DFSVFMFreeVPage 26906 . 27767) (\DFSVFMGet 27769 . 28997) (\DFSVFMGet1 28999 . 29443) (\DFSVFMInsert 
29445 . 30312) (\DFSVFMInsert1 30314 . 32048) (\DFSVFMLower 32050 . 32754) (\DFSVFMMerge 32756 . 34316
) (\DFSVFMMerge1 34318 . 34668) (\DFSVFMMerge2 34670 . 37911) (\DFSVFMPutNext 37913 . 39611) (
\DFSVFMReadNext 39613 . 40994) (\DFSVFMSplit 40996 . 41766) (\DFSVFMSplit1 41768 . 42012) (
\DFSVFMSplit2 42014 . 43240) (\DFSVFMXtra 43242 . 43794)) (44099 47722 (\DFSVFMCreateIntervals 44109
 . 45025) (\DFSVFMClearIntervals 45027 . 45415) (\DFSVFMGetInterval 45417 . 46870) (
\DFSVFMBlankInterval 46872 . 47720)) (47869 48439 (\DFSSmartBLT 47879 . 48437)) (48475 49372 (
\DFSVFMAtLoad 48485 . 49370)))))
STOP