C.BTPFIND

001 SUBROUTINE BTPFIND(ROOT,BFILE,DFILE,ID,ITEM,NODE.ID,NODE.POS)

002 * Find node containing key, with nodes in following format:

003 *   AMC 0:  Arbitrary node number.

004 *   AMC 1:  Count of keys in node.

005 *   AMC 2:  Keys, stored as a subvalue list.

006 *   AMC 3:  (number of keys)+1 pointers to next nodes.

007 *   AMC 4:  Pointer to parent if any.

008 CALL BTPKEY(ROOT,ID,ITEM,FINDKEY) ;* Get sort string for comparing to rest of tree

009 READ NODE.ID FROM BFILE, ROOT ELSE STOP "No root"

010 100 READ NODE FROM BFILE, NODE.ID ELSE STOP "Can't find node"

011 LEFT = 0 ; RIGHT = NODE<1>+1 ;* Boundaries for binary search of keys in node

012 IF RIGHT = 1 THEN NODE.POS = 1 ELSE ;* Not an empty root

013   LOOP

014     NODE.POS = INT((LEFT+RIGHT)/2) ;* Find position midway between boundaries

015     COMPARE.ID = NODE<2,NODE.POS> ;* Get that key

016     IF COMPARE.ID = ID THEN RETURN ;* Key is already in node

017     READ COMPARE.ITEM FROM DFILE, COMPARE.ID ELSE STOP "Can't read"

018     CALL BTPKEY(ROOT,COMPARE.ID,COMPARE.ITEM,KEY) ;* Convert COMPARE.ITEM to KEY for comparison

019     IS.GREATER = (FINDKEY > KEY) ;* Is our key greater than node key?

020     IF IS.GREATER THEN LEFT = NODE.POS ELSE RIGHT = NODE.POS ;* Adjust search boundaries

021   UNTIL (RIGHT-LEFT) <= 1 DO REPEAT

022   IF IS.GREATER THEN NODE.POS = RIGHT ;* Else NODE.POS already OK

023   END

024 NEXT.NODE.ID = NODE<3, NODE.POS> ;* Get id of next node

025 IF NEXT.NODE.ID # "" THEN ;* There's another node, keep looking for leaf

026   NODE.ID = NEXT.NODE.ID

027   GO TO 100

028   END

029 IF NODE.POS <= NODE<1> THEN ID = NODE<2,NODE.POS> ; RETURN

030 * At end of node, get next id like Branches #5 describes

031 NODE.POS = NODE<1> ; LAST.NODE.ID = NODE.ID

032 CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"NEXT",ID)

033 IF ID = "" THEN ;* Past end of tree, use last id

034   NODE.POS = NODE<1>

035   ID = NODE<2,NODE.POS>

036   NODE.ID = LAST.NODE.ID

037   END

038 RETURN

039 END