Dec 072017
 
B-Tree routines for Turbo Pascal V4.0.
File BTREE4V1.ZIP from The Programmer’s Corner in
Category Pascal Source Code
B-Tree routines for Turbo Pascal V4.0.
File Name File Size Zip Size Zip Type
BTREE4.DOC 19087 4989 deflated
BTREE4.TPU 18032 7257 deflated

Download File BTREE4V1.ZIP Here

Contents of the BTREE4.DOC file


{$I-,V-}

unit btree4; { VERSION 1.0 }
{ Copyright (c) 1988 by W. Lee Passey }
interface

type
MaxString = string[255];
bufarray = array [1..80] of byte;
Str80 = string[80];

PagePtr = ^PageHeader;
KeyListPtr = ^KeyList;

DataFile = record
case byte of
0 : (F : file);
1 : (Handle,
Mode,
RecSize : word;
Private : array [1..26] of byte; { reserved by TP4 }
FirstFree, { the first available record in the file }
NumberFree : longint; { the number of records deleted and
therefore available for use }
RecLength : word; { the length of records in this file }
KeysPerPage, { if an index file, the maximum number
of keys which may be put on a page }
KeyLength : byte; { if an index file, the maximum
length of a key }
FirstPage : longint; { if an index file, the number of the
record which is the root page }
FileName : array [1..80] of char;
Buffer : ^BufArray);{ pointer to a buffer on the heap,
used with this file, whose size is
identical to the record length }
end;

IndexFile = record
DF : DataFile;
RootPage : PagePtr; { a pointer to the root page, if it
is in memory }
KeySize, { the size of a key record, on the
heap, for keys in this file }
ItemSize : word; { the size of a key, its reference
and record pointer, in this file }
SavePage : PagePtr;
SaveKey : KeyListPtr;
SaveRec : longint;
PageBuffer: ^BufArray; { pointer to a buffer on the heap,
used with this file, whose size is
identical to the record length, and
which is used for packing and
unpacking pages to and from the disk
and memory. }
end;

(* Like Borland's Database Toolbook, each file use by BTree4 must be
declared either as a DataFile or an IndexFile. *)

PageHeader = record
NextPage, { these two pointers link the pages }
PrevPage, { into a two-way linked list in memory
each time a page is used it is placed
back at the head of this list }
ParentPage, { a pointer to this page's parent page
which should be in memory }
GreaterPage : PagePtr; { a pointer to a page on a lower level
containing keys greater than all
keys on this page, if in memory }
GreaterRec, { the disk record number of the page
which goes in GreaterPage }
RecNum : longint; { the disk record number of this page }
FilePtr : ^IndexFile; { points to the file variable of the
file which this page comes from }
ParentKey, { the key record from the parent page
which contains the key which is one
greater than all the keys on this
page. if this pointer is nil, you
must go up another page; if this is
not possible you are in the root
page. }
KeyList, { pointer to the first key on page }
ListEnd : KeyListPtr; { pointer to the last key on page }
KeysOnPage : byte; { the number of keys actually in the
key list and on the page }
end;

KeyList = record
NextKey, { these are the link pointers for the }
PrevKey : KeyListPtr; { list of keys }
LesserPage : PagePtr; { a pointer to a page on a lower level
containing keys less than all keys
on this page, if in memory }
LesserRec, { the disk record number of the page
which goes into LesserPage }
Reference : longint; { the data reference associated with
this key which usually is, but need
not be, the record number of a record
in a data file }
Key : MaxString; { this is the key. Although declared
as a string of length 255, the actual
space available is only as much as the
keylength specified when making the
file }
end;

const
MaxPageMem : word = 16384; { Maximum memory which will be allo-
cated for the page stack -- see above.
This variable is dynamic, and can be
adjusted by a calling program if need
be. }
MinPageMem : word = 2048; { Minimum heap memory which MUST be
available for the page stack. This
amount should be at least equal to the
amount of memory required to hold one
page from each level of the tree plus
one page, each with its full comple-
ment of keys. }

var
OK : boolean; { status variable, true if all went
well, false otherwise. }
IOError : integer; { if an IO error occured, this variable
will contain the error number, or -1
if the error is due to lack of
memory. }

procedure MakeFile (var DatF : DataFile;
FileName : Str80;
RecLen : word);

(* This procedure creates a new data file named 'FileName' and having
a record length of 'RecLen.' Note that 'RecLen' is declared as type
word, and thus the maximum record size allowed for a BTree4 data file
is 65535 bytes. Because of possible inaccuracies in counting the size
of record variables it is recommended that programmers us the 'sizeof'
function to pass the record length. The specified record length is
stored in the file header in record 0, and will always be used when the
file is opened. The minimum record length is 16 bytes and if 'RecLen'
is less than this, a record length of 16 will be used. If OK is false
on return, an IO error occured. *)

procedure OpenFile (var DatF : DataFile;
FileName : Str80);

(* This procedure opens the fles specified by 'FileName' as a data file
and assigns the file to the variable 'DatF.' Note that unlike the Data-
base Toolbox, no record length is passed, as the record length is fixed
when making the file, and is extracted when the file is opened. If OK
is false on return, an IO error occured. *)

procedure PutRec (var DatF : DataFile;
RecNum : longint;
var Buffer );

(* This procedure takes 'RecLen' number of bytes from the variable
'Buffer' and writes it to the file as record number 'RecNum.' If
'Buffer' is not large enough to fill the disk record, extra garbage
will also be written. If OK is false on return, an IO error occured. *)

procedure AddRec (var DatF : DataFile;
var RecNum : longint;
var Buffer );

(* This procedure will add a record to the file 'DatF' containing the
data from the variable 'Buffer.' 'RecNum' will return the number of the
record added. The new record may be at the end of the file, but need not
be. As records are deleted from the file they are not physically removed
byt are simply put in a list of available records, and when a new record
is needed the most recently deleted record is used. The free list is
maintained by a linked list which uses the first four bytes of each
deleted file record. It is recommended that these four bytes be reserved
specifically for this use, so that a non-zero number in this position
would indicate a free record, and a zero value would indicate a record in
use. This is useful both in "packing" a data file, and in re-creating
an index file. If OK is false upon return an IO error occured. *)

procedure GetRec (var DatF : DataFile;
RecNum : longint;
var Buffer );

(* This procedure reads the record number RecNum from the previously
opened file DatF and places it into 'Buffer.' It is the programmer's
responsibility to insure that the variable passed as 'Buffer' is long
enough to hold all the data, otherwise the procedure will possibly over-
write other variables. If OK is false upon return, an IO error occured.
*)

procedure DeleteRec (var DatF : DataFile;
RecNum : longint);

(* This procedure places the record specified by 'RecNum' on the list
of available records, and fills the first four bytes of the record with
$FFFFFFFF. The next time a new record is added to the file, one of the
from the available list will be used, and overwritten. If OK is false
upon return, an IO error has occurred. *)

procedure CloseFile (var DatF : DataFile);

(* This procedure updates the file header information and closes the
file. The file is closed even if an IO error occured while trying to
save the header information. The information remains, of course, in the
file variable, until it is re-used, and may be extracted by an error
handling routine. If OK is false upon return, an IO error occured. *)

function FileLen (var DatF : DataFile) : longint;

(* Similar to the Database Toolbox, this function returns the number of
records in DatF, both used and available. This function is equivilent to
"FileSize (DatF.F)" which can be used alternatively with less overhead.
*)

function UsedRecs (var DatF : DataFile) : longint;

(* Included primarily for compatability with the Database Toolbox, this
function returns the number of used (non-available) records in the file.
It is functionally equivilent to "FileSize (DatF.F) - DatF.NumberFree."
*)

procedure MakeIndex (var IdxF : IndexFile;
FileName : Str80;
KeyLength,
KeysPerPage : byte);

(* This procedure will create a new index file named 'FileName.' It is
similar to the procedure MakeFile, but instead of specifying the record
length the programmer specifies the maximum length of a key ('KeyLength')
and the maximum number of keys that can be placed on one page. This
information is used to calculate the record length which is
5 + (KeysPerPage * (KeyLength + 9)). In addition to calculating the
record length, this procedure initializes other data necessary to use
as an index file. Note that unlike the Database Toolbox it is not neces-
sary to indicate if duplicate keys are allowed, as duplicate keys are
always allowed in BTree4. If OK is false upon return, an IO error occured.
*)

procedure OpenIndex (var IdxF : IndexFile;
FileName : Str80);

(* This procedure opens the index specified by 'FileName' and initial-
izes certain necessary data elements. Note than information about the
keys is not required as this information has been saved in the header
in record 0. *)

procedure CheckMem (Needed : word);

(* This procedure checks the amount of memory on the heap used by the
page stack, and if it is greater than that specified in the global vari-
able 'MaxPageMem' plus that specified by 'Needed', little used pages, and
their children, are removed from memory. If the amount needed does not
exceed 'MaxPageSize', but does exceed the maximum available memory, little
used pages will be removed, until the amount needed is available, or until
the stack size reaches 'MinPageMem'. If the amount of memory needed
cannot be made available, OK will be set to false, and IOError will be set
to -1. *)

procedure AddKey (var IdxF : IndexFile;
var RefAdded : longint;
KeyAdded : MaxString);

(* This procedure places the key passed as 'KeyAdded' into the index
tree at the proper place in order. If the length of the key passed is
greater than that allowed for the index file, the key passed will be
truncated. The procedure gives no warning if a duplicate key is added,
as duplicate keys are always allowed. If the data reference is the
same for both keys, the second one is not added, otherwise it is. If
you want to eliminate duplicate keys you must use the FindKey procedure
before adding a key. If OK is false upon return, an IO error has occured.
*)

procedure FindKey (var IdxF : IndexFile;
var RefFound : longint;
KeySought : MaxString);

(* This procedure searches the index file for the FIRST occurance of
the key sought. If the length of the key passed is greater than that
allowed for the index file, the key passed will be truncated. If the
key is found OK will be true upon return. If OK is false and IOError
is not zero then an IO error has occured. *)

procedure SearchKey (var IdxF : IndexFile;
var RefFound : longint;
var KeySought : MaxString);

(* Similar to FindKey, this procedure searches the index file for the
first key which is equal to OR greater than 'KeySought.' 'KeySought'
will return the value of the key found, and RefFound will return its
reference. If upon return OK is false and IOError is zero then there
are no keys in the index file greater than or equal to the key sought. *)

procedure NextKey (var IdxF : IndexFile;
var RefFound : longint;
var KeySought : MaxString);

(* This procedure will find the next key in the file after a call to
any of the search procedures. This procedure is used to perform a
sequential search of index file. To set the file to the beginning,
use the procedure ClearKey. After adding a record, a call to NextKey
will find the key immediately after the key added. 'KeySought' will
return the value of the key found, and RefFound will return its refer-
ence. If upon return OK is false but IOError is zero the end of the
file has been reached. Another call to NextKey at this point will
return the first key in the index. *)

procedure PrevKey (var IdxF : IndexFile;
var RefFound : longint;
var KeySought : MaxString);

(* This procedure will find the key in the index file which is previous
in order to the key last referenced. This procedure is used to perform
a reverse sequential search on the file. To set the file to the end of
the index use the the procedure ClearKey. After adding a record, a call
to PrevKey will find the key immediately prior to the key added.
'KeySought' will return the value of the key found, and RefFound will
return its reference. If upon return OK is false but IOError is zero,
the beginning of the file has been reached. Another call to PrevKey at
this point will return the last key in the index. *)

procedure ClearKey (var IdxF : IndexFile);

(* This procedure sets the current index file position to the beginning
(or end) of the index file. After calling clear key a call to NextKey
will return the first key in the index, and a call to PrevKey will return
the last key in the index. *)

procedure DeleteKey (var IdxF : IndexFile;
DataRef : longint;
Key : MaxString);

(* This procedure removes a key from the index file, if it matches
'Key' AND 'DataRef'. The double check is required because duplicate keys
may exist in the index file, but not duplicate keys with the same data
reference. If the deletion of a key causes a page to have fewer than
'KeysPerPage' divided by two keys on the page, the page will be merged
with a sibling. If all keys are removed from the entire indexfile it
will not be deleted, but will exist with only the header record. *)

procedure CloseIndex (var IdxF : IndexFile);

(* This procedure will update the header information and close the
index file specified. In addition, all pages currently in memory which
were read from this file are purged and the memory is returned to the
heap. Like CloseFile, the file is closed even if the header information
was not successfully saved, and an examination of the File variable will
be necessary to save the information. *)

procedure Unlink (var Link;
var Head;
var Tail);

(* This procedure is a special bonus. Unlink is used to maintain double
linked lists of records on the heap, where the first four bytes of the
record is a pointer to the next record, and the next four bytes is a
pointer to the previous record. The three parameters passed MUST be
pointer types; 'Link' is a pointer to the record to be unlinked; 'Head'
is the pointer to the head end of the linked list; and 'Tail' is the
pointer to the tail end of the list. Calling Unlink removes the record
pointed to by 'Link' from the linked list, re-establishing all links,
and updating the head pointer or tail pointer if necessary. None of
the pointers in 'Link^' are affected. *)

function Equals (var A;
var B;
Number : word) : boolean;

implementation



 December 7, 2017  Add comments

Leave a Reply