c Xerox Corporation 1979Inter-Office MemorandumToAlto Bcpl ProgrammersDate October 12, 1977FromEd McCreightLocation Palo AltoSubjectB-Tree PackageOrganization CSLXEROXThe file BTREE.DM contains the five BCPL code modules BTreeRead.bcpl,BTreeWrtMS0.bcpl, BTreeWrtMS1.bcpl, BTreeWrtMS2.bcpl, and BTreeDel.bcpl, plus a declarationsmodule BTree.decl (plus BTreeCheck.bcpl and some other model Bcpl code). These modules, withconsiderable support from user-supplied routines, implement B-Trees with variable-length records forthe Alto. (If you don't know what a B-Tree is, put this memo down for a while and read section 6.2.4of Knuth's The Art of Computer Programming, volume 3.) Subroutines are assigned to modules in sucha way that if one only reads from the B-Tree, only one modules is required; writing requires up tofour; deleting may require all five.The B-Tree package infers the lengths of B-Tree records and order among B-Tree records by askingquestions of user-supplied routines. It also assigns responsibility for storing and recalling B-Tree pagesto/from a disk (or whatever) to user-supplied routines. These routines are provided to the B-Treeprocedures via a tree handle, a block of memory that is supplied as a parameter in all calls to the B-Tree package. This tree handle must be initialized before calling the B-Tree package. The package isre-entrant (if the user-supplied routines are), and can be working on several tree handles at once.What the Package NeedsThe user must supply the following routines in the tree handle (see BTree.decl for the exact format ofthe tree handle: it's the structure called TREE):ReadBTreePage(BTreeHandle, pageNumber) = core addressThe routine must read the desired page into core somewhere and return the address of whereit was put. The page may be flushed from core at any later time (within reason) except if it islocked (see below).WriteBTreePage(BTreeHandle, pageNumber) = core addressThe routine must read the desired page into core somewhere and returns the address of whereit was put. In addition, the B-Tree routines will immediately alter the page in core, so that itmust subsequently be written out before being flushed from core.LockBTreePtr(BTreeHandle, lv pointer)This call notifies that pointer must be checked before flushing any B-Tree page from core. Ifpointer points into a B-Tree page, that page may not be moved or removed.UnlockBTreePtr(BTreeHandle, lv pointer)Notification that pointer need not be checked any more.AllocateBTreePage(BTreeHandle) = pageNumberThis routine must return the number of a page not currently being used in the B-Tree.",pqX ]r Xusq*sq2` Uksq *sq2` Rasq *s q2`L+t Eq&+ DL9# BK ABH ?A$ >8 uq8 <uq+uq ;.uq 8$N 6P 5E 3u q'# 2 W 0E -r +qN *w1'mr5%q+/$cO"r6OqBZE@;r%qrq'1rqB'r'qrq r+ q(- B?YK%2FreeBTreePage(BTreeHandle, pageNumber)Notification that the numbered page is now no longer being used in the B-Tree.CompareKeyRtn(Key, Record) = {-1, 0, 1}This routine must compare an isolated key (whatever that is) with a record and say whetherthe key is less than, equal to, or greater than the record.LengthRtn(Record) = lengthThis routine must return the length of the record in words.It is no coincidence that the first four routines mesh hand in glove with four nearly identical routinesin the VMEM package. I shall eventually make a nice stand-alone OpenTree procedure that uses theISF and VMEM packages in the simplest possible ways and creates a proper tree handle. For themoment, alas, users must follow the models in IFSBTREERES and IFSBTREESWAP, which are alsoincluded in the dump file for inspirational purposes only. I know that this puts a pretty high potentialbarrier in front of somebody who wants to use B-Trees in a simple application, but the onlyapplications to appear thus far have been far from simple, and ultimately needed the full generality ofthe IFS environment.What The Package Will DoThe following routines are part of the BTREEREAD module. In these routines, CompareKeyRtn is anoptional comparison routine which, if present, is used in preference to the comparison routine specifiedin the tree handle. The ordering relation R' used to search the tree must be a weakening of the relationR used to create the tree. That is, if ab in R', then a>b in R.This feature can be useful, for example, when one wishes to store capitalizations distinctly whilesometimes having a search match any capitalization. In this case R would sort first on letter content,and then (if all letters were the same) on capitalization. R' would simply sort on letter content and callall keys containing the same letters in the same order equal. ReadRecLE(TreeHandle, Key, CompareKeyRtn) = record copyThis returns either 0 or a pointer to a copy of the tree record with the greatest key less than orequal to Key. When the user is finished with the record copy, he must FREE it intoTreeHandle>>TREE.Zone.MapTree(TreeHandle, StartKey, Function, Param, CompareKeyRtn, dontCopy)This function is similar to ReadRecLE. However, instead of returning a pointer to a copy ofthe tree record, it passes that pointer to the user-supplied Function which should take threearguments. The first one will be a pointer to a copy of the record, or to the live record itself ifdontCopy is true, the second one will be Param, and the third will be uninteresting. When it isfinished, Function is responsible for FREEing the record copy into TreeHandle>>TREE.Zone.If Function returns the value true, then it is called again on the next larger record in the tree,and so on until either Function returns the value false or the largest record in the tree hasbeen processed. MapTree itself returns the value false if Function returned false, and true ifthere are no more records to process. The following external subroutine is contained in the BTREEWRTMS0 module:UpdateRecord(TreeHandle, Key, RecordGenerator, Param, CompareKeyRtn)The user-supplied function RecordGenerator is called with two parameters. The first parameteris either 0 or a pointer to a copy of a record in the tree whose key is equal (according toCompareKeyRtn or the key-comparison routine specified by the tree handle) to Key. Thesecond parameter is Param. RecordGenerator is expected to produce a record whose key isequal to Key (this is checked). That new record will replace the original one (if any) in thetree. Finally the record produced by RecordGenerator will be FREEd intoTreeHandle>>TREE.Zone.The following external subroutine is contained in the BTREEDEL module:Nfqbr&`qN]r'\ q)1Z;W{rUq; R>* Qg'rq O%8 N]G L ] KSrq% IY HI E?r CqLr q B5M @1uq ?+&B =8* 6 r74qH3rq71~r q .trG,q:!+j=rq)`(`rq!rq& rq1r q %Vrquq:#rq uq&"Lrq uqrququq % 8I.rXDqrq2$Hr q/rqrqrq-rqM%rq r q F :?\3DeleteKey(TreeHandle, Key, CompareKeyRtn)The record whose key is equal to Key is deleted from the tree. The value returned is true ifthis was done, and false if no such record was contained in the tree.Nfq`r)_q!rq!uq]uq- Z>: *MATH  TIMESROMAN  TIMESROMAN  TIMESROMANLOGO TIMESROMAN  zj/Vbtreememo.bravo SwinehartSeptember 7, 1979 5:08 PM