// SpruceQueue.Bcpl
//
// Manages spooling queue and related values -- maintains important invariants

get "Spruce.d"
get "SpruceFiles.d"

// defined here
external
[
AddToQueue
CheckPointQueue
CleanupQueue
FullQueue
InitializeQueue
MarkQueueEntry
SortQueue

zoneOK
]

external // external
[
// SpruceUser
Post

// SpruceFiles
CreateSpruceSubfile
ForgetSpruceFile
InitSpruceFile
InitSpruceSubfile
ResetSpruceFile

// SpruceUtils
ForEach
FSGetX; FSPut
Max; Min; MulDiv
Reclaim
RpageToVpage
SpruceCondition
Ugt
VpageToRpage

// SpruceCheck
CheckPoint
ActOnEntry

// SpruceStreams
WindowCreateStream

// Queue
Dequeue
Enqueue
InsertAfter
InsertBefore
QueueLength

// Context
Block

// OS
Closes
CheckZone
MoveBlock
Zero

// statics
freeFile
maxQueued
numFilesSpooled
queueLock
SpoolFile
QueueFile
SproullerQ
SpoolVec
printDoc; mapTemp; PressFile
SpruceZone
]

static [ sortWeight = 50; sortStrategy = 0 ] // see fePriority
static [ qDirty = false ]
manifest [ nbfSpool = 4; ncbSpool = 3 ]

// ------------------------------------------------------
// Queueing Philosophy:
// ------------------------------------------------------

// This module manages the spooling queue and its corresponding structures within the SpoolFile.
// It is the heart of Spruce Spooling management.

// The spooling queue (SproullerQ) is implemented in memory using the Alto queue package. It is
// queue of DocG structures defining all Press files and print commands currently available. This means
// the files or commands are awaiting execution (a state formally known as "pending"), have been
// executed ("printed"), or are in progress ("inProgress", Sprint execution was suspended with an
// entry in progress).
// The spooler normally maintains SproullerQ in arrival, or FIFO, order. Before calling Sprint, the
// queue is sorted into a print priority order, with any in-progress document at the head, unprinted
// documents ordered by priority in the middle, and completed entries at the end. The queue is then
// stored in the LEVRunDocs region of the checkpoint file (see SpruceCheck), where Sprint fetches the
// entries one by one. On return, the queue is restored from the checkpoint region, entries are modified
// based on a progress report from Sprint, and the queue is resorted in arrival order.
// Spruce can support a queue of limited length (maxSpooled). When that limit has been reached, if
// the oldest entry has been executed (a state formally known as "available") it is deleted, accompanied
// by appropriate file actions (see below), when a new spooling request arrives. Otherwise, the new
// request must be rejected.
// A DocG entry can represent a printer command (e.g., Power On), a Press file stored in the local
// Alto file system (stand-alone printing), or a spooled Press file which has arrived on the Ethernet.
// The first two cases are dealt with simply, here and in SpruceInit (queueing the entries initially). The
// remainder of this discussion deals with spooled files.

// Files, as they are received, are stored contiguously, in arrival order, as subfiles of the file
// SpoolFile. They are given file indices (in the range #1000-#1777) to serve as temporary names. Thus,
// when SproullerQ is sorted in arrival order, its entries are in the same order as the batch of spooled
// subfiles.
// Typically, a number of files at the head of this list have been printed. These are known as
// "available" files, which means that their space may be supplanted by new arrivals. These files are
// held as long as possible, so that they may be reprinted if desired, but never longer than the queue
// entries that describe them. Files that have been printed, but are insulated from the head of the arrival
// list by unprinted files, are not candidates for replacement because the scheme requires that there be
// a single available and a single unavailable region of the SpoolFile.
// As the system operates, the group of files comprising the occupied SpoolFile region migrate
// towards the end of the file (files are deleted from the head and appended to the tail.) The subfiles
// are allowed to "wrap around" (see SpruceFilesInit), so the SpoolFile behaves like a ring buffer.
// In addition to subfiles representing the spooled files, the implementation uses another subfile,
// called freeFile, that fills the unoccupied space. It begins with the first page following the last
// unoccupied page (modulo the SpoolFile’s length), and terminates with the page preceding the first
// unavailable subfile. Thus, the freeFile overlaps all the available subfiles, if there are any. The
// available subfiles occupy a contiguous region at the end of the freeFile.
// The spooling functions (see SpruceSpool) are given freeFile to fill from the beginning. If it fills
// completely, the network transfer is aborted, since unavailable files would subsequently be damaged.
// Otherwise, once the transfer is complete, any available subfiles that have been overwritten to any
// degree are removed from the queue. Then a new subfile is created from the head of the freeFile, the
// freeFile is diminished, and a new entry joins the end of SproullerQ.

// Whenever the structures that implement this scheme are not being changed, the following
// invariants must hold:
// Consider the extension of the freeFile to the size of the SpoolFile. The available and unavailable
// subfiles represented in the arrival-order SproullerQ must be contiguous and increasing page-order,
// using freeFile’s page coordinates (via VpageToVpage, see below).
// The available (printed, at the head of arrival-order queue) files must occupy the final pages of
// freeFile (using freeFile’s page coordinates).
// freeFile and the unavailable files occupy the entirety of SpoolFile.
// SproullerQ does not exceed maxQueued in length.

// The routines herein manage the queue, freeFile, and the spooled subfiles, maintaining the above
// invariants (mainly through the good offices of CleanupQueue()). Functions in Spruce also carry out
// specialized queue management activities related to the processing of the Sprint’s printing report,
// whenever Sprint suspends and defers to Spruce.
//The init routine marks the queue clean, and other routines that change its structure mark it dirty.
// The CheckPointQueue() routine writes the queue, in current (probably arrival) order, into the
// checkpoint file, and marks the queue clean. See Sprouller() in Spruce for (only) call.

// ------- Client-called routines -------

// ------------------------------------------------------
let CleanupQueue(numUsed, freeAdjust) be
// ------------------------------------------------------

// SproullerQ MUST be in FIFO order whenever this function is called!
// The main task is to build the freeFile and mark the "available" state
// of documents to attain the spooler invariants (see above). Also, aided
// by numUsed argument, detect available subfiles whose pages have been
// overwritten, delete them and their queue entries. numUsed contains the
// number of pages that have been removed from the head of freeFile during
// a spooling operation, successful or not.
//
// If freeAdjust is false, this is simply a call to eliminate any overwritten subfiles;
// freeFile’s origin will not change. If freeAdjust is true, this is a call to adjust
// the origin of freeFile to accommodate a newly-spooled file.
// CleanupQueue(numUsed, false) should already have been called to eliminate
// damaged files. It is almost certain that no good will come of attempting to perform
// both functions in the same call. These functions lock each other out because
// multiple contexts (e.g., the user context to gain information) may be calling them
// concurrently, resulting in invalid state, real or apparent.
[
LockQueue(true) // enter if lock off or coming from one of above functions
let numSpooled = 0
freeAdjust = freeAdjust? numUsed+1, 0
if freeAdjust then
// Adjust the origin of the freeFile to accomodate a newly-spooled file.
// readjust page 1, temporarily has size 1 until new free computed
[ InitSpruceSubfile(freeFile, VpageToRpage(freeFile, freeAdjust), 1); numUsed=0 ]
let firstFree, numFree = 1, freeFile>>SPruceFile.maxPages
// ForEach(SproullerQ, FirstRelFree, lv firstFree) // find first page of first queued file, if any
// let doc = @SproullerQ
// while doc do
//[ let nextDoc = doc>>DocG.link
let s, len, pos = 0, SpoolVec!0, 1
if pos le len then// create stream if necessary
s = WindowCreateStream(QueueFile, ksTypeReadWrite, wordItem, 4)
while pos le len do
[
ActOnEntry(SpoolVec!pos, true, s)//read entry into core
let doc = printDoc
let f = doc>>DocG.PressFile
let firstPage = 0; FirstRelFree(doc, lv firstPage)
if firstPage then
[
// unless firstPage eq firstFree do SpruceCondition(162, ECSpoolTerminate)
firstFree = VpageToVpage(freeFile, firstPage+f>>SPruceFile.numPages, freeFile)
]
unless doc>>DocG.printed do numSpooled = numSpooled+1
// Free up ’printed’ files if they are contiguous with freeFile
test numSpooled eq 0 & doc>>DocG.printed then
[
doc>>DocG.available = true
if FullQueue() % (firstPage & numUsed ge firstPage) then
[
Post(doc, 0, "No longer available"); qDirty = true
//FSPut(Dequeue(SproullerQ))
if f ne -1 then ForgetSpruceFile(f)

// Invalidate and then save this entry
doc>>DocG.invalid = true
ActOnEntry(SpoolVec!pos, false, s)
// reset the pointer in SpoolVec
SpoolVec!pos = 0
]
]
or
[
doc>>DocG.available = false
if firstPage then numFree = Min(numFree, firstPage-1)
]

// Reclaim core
Reclaim()
//doc = nextDoc
pos = pos + 1
]

// purge SpoolVec of null entries

// clean up stream if necessary
if s ne 0 then[ Closes(s); ResetSpruceFile(QueueFile) ]
unless firstFree eq 1 & numFree ge 0 & numFree le freeFile>>SPruceFile.maxPages do
SpruceCondition(164, ECSpoolTerminate)
InitSpruceSubfile(freeFile, VpageToRpage(freeFile, firstFree), numFree)
numFilesSpooled = numSpooled
queueLock = 0
]

// ------------------------------------------------------
and InitializeQueue() be
// ------------------------------------------------------
//Create an empty queue and a freeFile that encompasses SpoolFile.
[
numFilesSpooled, qDirty = 0, false
// Allocate SpoolVec if it doesnt exist (no files spooled).
if SpoolVec ne 0 then SpoolVec = FSGetX(maxSpooled+1, SpruceZone, 0)
SproullerQ = FSGetX(2, SpruceZone, 0)
InitSpruceFile(SpoolFile) // Buffers will all be in subfiles
freeFile=CreateSpruceSubfile(lv SpoolFile,1, SpoolFile>>SPruceFile.maxPages)
InitSpruceFile(freeFile, nbfSpool, ncbSpool)
]

// ------- Client-called Routines . . .

// ------------------------------------------------------
and AddToQueue(pDoc) be // append new file entry
// ------------------------------------------------------
//Fill in spooler-related DocG fields. The spooled file described by pDoc,
//if not a local Alto file, is asserted to have been come from the head of freeFile,
//and damaged avaialable files are asserted to have been removed (see SpoolAFile() in
//SpruceSpool). Append the new entry and reestablish the invariants.
//Password-protected files are added in a "printed" state so they won’t add to
//numSpooled and will disappear if space is needed before someone comes to print them.
[
LockQueue() // only Cleanup can enter -- DO NOT BLOCK
pDoc>>DocG.spoolStatus = pDoc>>DocG.protected? STATNeedsPassword + STATPrinted, STATPending
qDirty = true
let spooledFile = pDoc>>DocG.PressFile
printDoc = pDoc
// Save entry in QueueFile at next available page
// check for overflow of SpoolVec
//if (SpoolVec!0) + 1 gr maxSpooled then //too many entries
SpoolVec!0 = (SpoolVec!0) + 1//Increment length
SpoolVec!(SpoolVec!0) = spooledFile>>SPruceFile.fileCode
//Are we overwriting a used page in the QueueFile (announce that it’s forgotten?)
ActOnEntry(SpoolVec!(SpoolVec!0), false)//write entry on disk
//Enqueue(SproullerQ, pDoc)
let isSpooled = 0
// is it in SpoolFile or is it local or cmd?
isSpooled = FirstRelFree(pDoc, lv isSpooled) ne 0
CleanupQueue((isSpooled? spooledFile>>SPruceFile.numPages, 0), true)
]

// ------------------------------------------------------
// and FullQueue() = QueueLength(SproullerQ) ge maxQueued// true if no more entries can be added.
and FullQueue() = SpoolVec!0 ge maxSpooled
// ------------------------------------------------------

// ------------------------------------------------------
and MarkQueueEntry(doc, status, defer; numargs na) be
// ------------------------------------------------------
//Change entry’s status to "printed" or to "pending", from anything at all. It is an undetected
// mistake to change to "in Progress"; adding "available" is ineffective because Cleanupqueue() will
// revise.
// Don’t do the cleanup if defer, because a number of entries are being updated, and cleanup is
// expensive. CleanupQueue(), it is asserted, will be called when all entries have been modified.
//This function is called to record changes in status during normal operation, and in response to
// explicit user-initiated actions.
// Brute-force conversion of this routine (restore modify save) is probably not
// very efficient. Eventually remove.
[
if na<3 then defer = false; qDirty = true
LockQueue() // only Cleanup can enter -- DO NOT BLOCK
doc>>DocG.spoolStatus = status // could check validity
test defer then queueLock = 0 or CleanupQueue(0, false)
]

// ------------------------------------------------------
and CheckPointQueue() be if qDirty then
// ------------------------------------------------------
//if qDirty, flush queue, unsorted, and related statics to checkpoint regions
[
// save state of SpoolVec
CheckPoint(LEVEternalStatics, LEVEternalStatics)
qDirty = false
]

// ------------------------------------------------------
and SortQueue(sortCode) be
// ------------------------------------------------------
//Using an insertion sort, sort queue into FIFO or print priority order. ForEach() is a queue
// mapping function, found in SpruceUtils.
// If implemented, will be very different.
[
LockQueue(true); qDirty = true
let tempQ = vec 1
MoveBlock(tempQ, SproullerQ, 2)
Zero(SproullerQ, 2)
let unPrinted, inProg = SproullerQ, 0// used by feSort... routines
switchon sortCode into [
case SORTFifo: ForEach(tempQ, feSortFifo); endcase
case SORTPriority: ForEach(tempQ, feSortPriority, lv unPrinted) ]
queueLock = 0
]

// ------- Queue sort utilities -------

// ------------------------------------------------------
and feSortPriority(pDoc, nil) = valof
// ------------------------------------------------------
// ***1 Priority sort: Sort into print priority order for presentation to the printer.
// If there was a file in progress when the printer last suspended, it has highest priority. Following
//that are the unprinted files, in an order directly proportional to a function of the waiting time
//determined by sortStrategy, inversely proportional to length. Finally, the files that have been
//printed but not yet overwritten are included. The numSpooled count does not include this last
//category, so the printer will not reprocess them. sortStragegy is manually adjusted.
[
if pDoc>>DocG.inProgress then
[ InsertAfter(SproullerQ, SproullerQ, pDoc); resultis 0 ] // do them all
if pDoc>>DocG.printed then [ Enqueue(SproullerQ, pDoc); resultis 0 ] // do them all
let wT = pDoc>>DocG.waitTime
wT = selecton sortStrategy into [ case 0: ((wT*2)? wT*2, #40000); default: wT+1 ]
pDoc>>DocG.waitTime = wT
pDoc>>DocG.priority = Max(MulDiv(wT, sortWeight, pDoc>>DocG.nParts), 1)
unless ForEach(SproullerQ, fePendingPriority, pDoc) do Enqueue(SproullerQ, pDoc)
resultis 0 // do them all
]

// ------------------------------------------------------
and fePendingPriority(pDoc, newDoc) = valof
// ------------------------------------------------------
[
if pDoc>>DocG.inProgress resultis 0 // go on, inProgress has highest priority (this week)
if pDoc>>DocG.printed % newDoc>>DocG.priority > pDoc>>DocG.priority then
[ InsertBefore(SproullerQ, pDoc, newDoc); resultis 3 ]
resultis 0 // new has lower priority, go on
]

// ------------------------------------------------------
and feSortFifo(pDoc) = valof
// ------------------------------------------------------
// ***2 Fifo sort: Reestablish the original order of spooling -- this is done by sorting the files by
//ascending "virtual page number". This number is the page number the beginning of each file
//would have if it were a part of the current "free" file -- using freeFile’s page coordianates.
//If queue is not in FIFO order, this function must be called before CleanupQueue() will work.
[
unless ForEach(SproullerQ, feInsert, lv pDoc) do Enqueue(SproullerQ, pDoc)
resultis 0 // do them all
]

// ------------------------------------------------------
and feInsert(beforeDoc, pPDoc) = valof
// ------------------------------------------------------
[
let bFile = beforeDoc>>DocG.PressFile
let file = pPDoc=>DocG.PressFile
let bPage = bFile>>SPruceFile.isSubFile? VpageToVpage(bFile, 1, freeFile), 0
let page = file>>SPruceFile.isSubFile? VpageToVpage(file, 1, freeFile), 0
if page > bPage resultis 0 // keep going
InsertBefore(SproullerQ, beforeDoc, @pPDoc)
resultis 3 // quit and return beforeDoc
]

// ------- Queueing utilities -------

// ------------------------------------------------------
and FirstRelFree(doc, lvRes) = valof
// ------------------------------------------------------

// If doc contains a spooled subfile, and not a local file or a printer command,
// store the page number, in freeFile’s page coordinates, of the spooled subfile’s
// first page, and return 3. Otherwise, return 0.
// Intended to be called from within ForEach, to find the freeFile-relative
// page number of the first spooled subfile in the queue. The 0 result continues
// the search; the 3 result successfully terminates terminates it. Called directly
// from other places for either the page-mapping or subfile-detection effect.
[
let f = doc>>DocG.PressFile
unless Ugt(f+1, 1)&f>>SPruceFile.isSubFile resultis 0 // keep going if called by ForEach
@lvRes = VpageToVpage(f, 1, freeFile)
resultis 3 // stop if called by ForEach
]

// ------------------------------------------------------
and LockQueue(deadBolt; numargs na) be
// ------------------------------------------------------
//Locks other routines out of queue modification routines, Blocking() here until available. The two
// lock states allow locked routines to call CleanupQueue(), which can also be called directly and thus
// must perform a lock. There should be a timeout or something here to prevent deadlocks due to bugs.
// Since the low-frequency user context and the spooler context are the only competitors, no deadlocks
// will prevail if there are not bugs.
[
// locks with deadBolt value; if prev was 1, and current is -1, just strengthen lock
// otherwise if already locked, wait for unlock
if na<1 then deadBolt=1
if queueLock ne 1 % deadBolt eq 1 then while queueLock do Block() // should timeout here
queueLock = deadBolt
]

and ZoneOK() be
[
[
CheckZone(SpruceZone)
Block()
] repeat
]

// ------------------------------------------------------
and VpageToVpage(fromFile, page, toFile) = RpageToVpage(toFile, VpageToRpage(fromFile, page))
// ------------------------------------------------------
//Maps from the page coordinates of one subfile to those of another. It is asserted, but not checked,
// that both files have the same parent.

// ------- History . . .

// DCS, August 29, 1978 12:23 AM, created as extraction from Spruce, SpruceSpool, SpruceUser
// August 30, 1978 8:06 AM, add FullQueue
// August 31, 1978 7:28 AM, inherit SortSpooledFiles -> SortQueue
// September 1, 1978 8:19 AM, redo CleanupQueue -- now constructs values previously checked,
// thus simplifying maintenance of invariants!
// Call SpruceCondition(..., ECSpoolTerminate) to indicate queue inconsistencies.
// September 3, 1978 6:56 PM, subfile creation uses static address
// September 4, 1978 3:10 PM, repair lingering bugs in CleanupQueue
// September 5, 1978 8:20 AM, Mark... takes full status, defer arg defers Cleanup; Queue locks;
//fix full spool q bug
// September 5, 1978 5:23 PM, queue lock bug
// September 5, 1978 9:14 PM, institute true priority scheme
// September 20, 1978 11:43 AM, formatting, documentation
// October 16, 1978 9:26 AM, modify interfaces for fast files
// August 3, 1979 9:45 PM, mark "needs password" on protected files added to queue (AddToQueue)
// May 9, 1980, 2:28 PM, make sure feSortPriority doesn’t zero DocG.waitTime
//