//	B-Tree Maintenance Routines
// Copyright Xerox Corporation 1979, 1981

//	BTREE.DECL -- Structure definitions

//	last modified May 9, 1982  1:40 PM by Taft


structure TS:	// Tree State

	[ LogPageLength word	// log2 of page length in words
	RootPage word		// B-Page containing the root
	GreatestPage word	// Greatest known B-page in the tree
	FirstFreePage word	// Head of list of free B-pages le
				// GreatestPage, 0 if empty
	RecordCount word	// Record count mod 2^16 for checking
	]

manifest [ lTS = size TS/16 ]

structure TREE:	// Tree Descriptor

	[ BVRRP word		// Procedure which reads a B-Tree page
	BVWRP word		// Procedure which reads a B-Tree page
				// but sets its dirty bit on
	BLockCell word		// Procedure which locks a cell
	BUnlockCell word	// Procedure which unlocks a previously-locked cell
	BVAP word		// Procedure which allocates a new B-Tree page
	BVFP word		// Procedure which accepts back a
				// previously-allocated B-Tree page
	BTBug word		// Error-handling procedure
	BTClose word		// Procedure to close this tree

	CompareKeyRtn word	// Procedure which compares the key in a
				// record with an isolated key
	LengthRtn word		// Procedure which returns the length of a
				// record in words

	PageLength word		// B-Page length in words (should be power of 2)

	Zone word		// Pointer to a free storage zone object

	StateDirty word		// True if state in core ne state on disk
	Version word		// Number of updates to the tree


	TS @TS			// Permanent tree state
	=
	@TS

	vmd word		// virtual memory descriptor (for IFS environment)
	]


manifest [
	Empty = 0
	maxRecordsPerPage = 1022/8  // assuming 8-word entries in 1024-word page
	maxLevelsInTree = 6	// maximum depth of tree
	]


structure BTE:	// B-Tree Entry

	[ GrPtr word		// Page containing sons greater
				//	than this entry but less
				//	than the next
	Record word 10		// The record corresponding to this
				//	entry, containing a key
	]


structure ESLE:	// Entry Sequence List Entry

	[ FwdP word
	EntSeqP word		// Pointer to a sequence of entries
	EntSeqLen word		// Length of sequence in words
	EntSeq word 10		// Sequence goes here
	]


structure ELE:	// Entry List Element
		// Gives cumulative length and pointer to heap entry
	[ CumEntLen word
	HeapPos word
	]


structure ELL: // Block of Entry List Elements

	[ [ ELE^0,3*maxRecordsPerPage + 2 @ELE ] =
	@ELE^0,3*maxRecordsPerPage + 2
	]



structure HP:	// Heap of entries contending for father block

	[ HeapEnt^1,256 word
	]


structure BTP:	// B-Tree Page

	[ FreeWords word	// Number of free words this page
	MinPtr word		// Page containing smallest son of this page
	BTEBlock word 1		// The BTE entries on this page
	]


manifest [
	PageOverhead = offset BTP.BTEBlock/16
	Rec0Offset = offset BTP.MinPtr/16
	Rec1Offset = offset BTP.BTEBlock/16
	]


structure PSE:	// Path Stack Entry

	[ PageNo word 		// also appears as GrPtr field of BTE indexed
				// by LastOffset in previous stack level

	Offset word
	LastOffset word
	NextToLastOffset word

	ESLFront word		// Added blocks of entries that go between
				// LastOffset and Offset
	ESLRear word

	LeastSon word
	]


// PathStk structure
// Note that level 0 is dummy; it is used only when the root page splits
// and a new root page must be created.
structure PS:
	[ Version word		// value of TREE.Version for which this PS is valid
	PathStkTop word
	PSE^0,maxLevelsInTree : @PSE
	]

structure IS:	// Insertion/deletion algorithm auxiliary state
	[ Tree word		// Ptr to tree handle

	MaxFreeWords word	// non-overhead words per page
	AwfullyFull word	// words in 9/10 full page
	PrettyFull word		// words in 2/3 full page
	FairlyFull word		// words in 1/2 full page
	BreathingSpace word	// words in 1/10 page

	PathStk word

	ELLPtr word		// Ptr to vector of cumulative lengths of
				// ESL entries
	ELLLen word		// Number of ESL entries

	HeapPtr word
	HeapSize word
	]


manifest [  // error codes, keying messages in Sys.errors
	ecRecGenReturnedWrongKey = 2100
	ecMcCreightWasWrong = 2101
	ecDepositESLWrong = 2102
	ecEntryListTooShort = 2103
	ecWritePageWrong = 2104
	ecTwoBrothersNotEnough = 2105
	ecNewRootOverflow = 2106
	ecRecordCountsDisagree = 2107
	ecRecordsOutOfOrder = 2108
	]