Category : Files from Magazines
Archive   : BYTE0189.ZIP
Filename : BTREE.LST

LISTING 1

{ This routine scans the key node --
{ represented by the array KEY[] --
{ for a match with the target key,
{ CURRENT_KEY
SCANKEY:
KEYOFFSET := 0;
IFLAG := 0;
WHILE KEYOFFSET < NUMBER_KEYS
BEGIN
IF KEY[KEYOFFSET] = CURRENT_KEY
RETURN;
IF KEY[KEYOFFSET] > CURRENT_KEY
BEGIN
IFLAG := 1;
RETURN;
END
KEYOFFSET := KEYOFFSET + 1;
END
IFLAG :=1;
RETURN



LISTING 2

{ This routine searches for a key.
{ If the key is found, CURRENT_KEY_SECTOR
{ holds the key node that key is on,
{ KEYOFFSET points to the key, and
{ IFLAG is set to 0. Otherwhise, IFLAG
{ is set to 1, and CURRENT_KEY_SECTOR and
{ KEYOFFSET show where the key *would*
{ have been.
{ NOTE: GET() and PUT() read and write
{ key sectors to and from the disk file.
SEEK_KEY:
IF number of keys in file = 0
RETURN file empty error;
Clear Pseudo stack;
CURRENT_KEY_SECTOR := Root;
REPEAT
GET( CURRENT_KEY_SECTOR );
CALL SCANKEY;
IF key found RETURN;
{ If the key pointer is empty,
{ the search has encountered
{ a leaf.
IF KEY_POINTER[KEYOFFSET] = 0
RETURN key not found error;
{ Push CURRENT_KEY_SECTOR and }
{ KEYOFFSET onto pseudo stack }
PUSH( CURRENT_KEY,SECTOR,
KEYOFFSET );
{ Search down the subtree }
CURRENT_KEY_SECTOR :=
KEY_POINTER[KEYOFFSET];
END REPEAT




LISTING 3

{ Add a new key to the key file.
CREATE_KEY:
SFLAG = 0;
IF number of keys in file = 0
BEGIN
GET_NEW_KEY_SECTOR;
Root := new key node;
Load CURRENT_KEY value;
END
ELSE
BEGIN
CALL SEEK_KEY;
IF key found
RETURN key already exists error;
END
FLOATING_KEY := CURRENT_KEY;


{ ** Code to handle creating a new
{ ** data record goes here.
L1:
Move CURRENT_KEY_SECTOR to WORKING_KEY buffer;
Move all keys -- in WORKING_KEY buffer
-- starting at KEYOFFSET 1 key position
to the right;
Move FLOATING_KEY into WORKING_KEY buffer at
location given by KEYOFFSET;
Increment WORKING_KEY buffer's keycount;
IF WORKING_KEY buffer's keycount > maximum
keys per key sector
BEGIN
(Note: keycount refers to the number of
keys in WORKING_KEY_BUFFER.)
FLOATING_KEY := WORKING_KEY[keycount/2];
FLOATING_KEY's left key pointer :=
CURRENT_KEY_SECTOR;
Move leftmost keycount/2 keys from WORKING_
KEY buffer to CURRENT_KEY_SECTOR;
PUT(CURRENT_KEY_SECTOR);
GET a new key node;
CURRENT_KEY_SECTOR := new key node.
FLOATING_KEY's right key pointer :=
CURRENT_KEY_SECTOR;
IF keycount is ODD i:=keycount/2
ELSE i:=keycount/2 - 1;
Move rightmost i keys from WORKING_
KEY buffer to CURRENT_KEY_SECTOR;
PUT(CURRENT_KEY_SECTOR);
POP (CURRENT_KEY_SECTOR,
KEYOFFSET);
IF POP() failed
BEGIN
GET a new key node;
ROOT := new key node;
END
GO TO L1;
END
ELSE
PUT(CURRENT_KEY_SECTOR);
IF SFLAG = 1
CALL SEEK_KEY;
IFLAG=0;
RETURN no error;
END;


LISTING 4

{ This routine searches for the
{ current key's inorder successor.
{ If it hits the end of file, the
{ key file is rewound and an error
{ is returned.
SEEK_NEXT_KEY:
IF number of keys in file = 0
RETURN file empty error;
IF file is rewound
BEGIN
CURRENT_KEY_SECTOR := Root;
IFLAG := 1;
GOTO L1;
END
GET(CURRENT_KEY_SECTOR);
REPEAT
IF IFLAG NOT = 0
BEGIN
IF KEYOFFSET NOT = number of
keys on node
BEGIN
IFLAG = 0;
RETURN;
END
IF Pseudo stack is empty
BEGIN
REWINDKEY;
RETURN end of file error;
END
POP(CURRENT_KEY_SECTOR,
KEYOFFSET);
GET(CURRENT_KEY_SECTOR);
END
ELSE
{ The following code executes if this
{ file's keypointer currently points to
{ a key. This means we have to advance
{ to that key's right keypointer, and
{ search that subtree -- if it exists --
{ for the "lowest and leftmost" key.
BEGIN
KEYOFFSET := KEYOFFSET + 1;
IFLAG = 1;
WHILE KEYPOINTER[KEYOFFSET] NOT = 0
BEGIN
TEMP := KEYPOINTER[KEYOFFSET];
PUSH(CURRENT_KEY_SECTOR,
KEYOFFSET);
CURRENT_KEY_SECTOR:=TEMP;
L2:KEYOFFSET := 0;
GET(CURRENT_KEY_SECTOR);
END
END
END REPEAT


LISTING 5

{ Rewind a key file.
{ This sets the roving pointer
{ given by CURRENT_KEY_SECTOR and
{ KEYOFFSET to the file's logical
{ start.
REWINDKEY:
CURRENT_KEY_SECTOR := 0;
KEYOFFSET := 0;
Clear Pseudo stack;
RETURN;