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

//	BTREE.DECL -- Structure definitions

//	last modified November 29, 1981  10:24 AM 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	// Address of a routine which reads a B-Tree page
	BVWRP word	// Address of a routine which reads a B-Tree page
			// but sets its dirty bit on
	BLockCell word	// Address of a routine which locks a
			// cell
	BUnlockCell word	// Address of a routine which unlocks a
			// previously-locked cell
	BVAP word	// Address of a routine which
			// allocates a new B-Tree page
	BVFP word	// Address of a routine which accepts
			// back a previously-allocated B-Tree page
	BTBug word	// Address of error-handling routine
	BTClose word	// Address of routine to close this tree

	CompareKeyRtn word	// Address of a routine which
				//	compares the key in a
				//	record with an isolated
				//	key
	LengthRtn word		// Address of a routine 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


	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:
	[ Tree word
	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
	]