// 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
		[
		InitSpruceFile(QueueFile, 4, 5)
		s = WindowCreateStream(QueueFile, ksTypeReadWrite, wordItem)
		]
	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)
		// compress SpoolVec
		MoveBlock(lv (SpoolVec!pos), lv (SpoolVec!(pos+1)), len-pos)
		]
	 or
		[
		doc>>DocG.available = false
		if firstPage then numFree = Min(numFree, firstPage-1)
		]

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

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

// ------------------------------------------------------
and InitializeQueue() be
// ------------------------------------------------------
//	Create an empty queue and a freeFile that encompasses SpoolFile.
	[
	numFilesSpooled, qDirty = 0, false
	SproullerQ = FSGetX(2, SpruceZone, 0)
	InitSpruceFile(SpoolFile) // Buffers will all be in subfiles
	unless freeFile do
		[
		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)
	// save state of freeFile
	CheckPoint(LEVRun, LEVRun)
	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
// 
(635)\266b9B140b17B59b9B79b12B2b38B97b18B90b11B12b40B7134b75B212b2B100b2B26b2B17b2B32b160v15V118B107b2B223b64B198b2B74b191B103b30B15b15B4b59B203b1B33b18B374b19B1b4B13b3B68b2B45b4B900b422B44b3B46b13B170b3B96b43B768b118B456b75B2b53B303b43B5056b72B