Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/BTREE4.ZIP/BTREE4.DOC

Text File | 1988-01-17 | 25.3 KB | 661 lines

                                  BTREE4



                a Shareware Unit for Turbo Pascal ver. 4.0



                    for Data and Index file management





                    Copyright (c) 1988 by W. Lee Passey























                             Pass-Key Software

                            119 MacArthur Ave.

                         Salt Lake City, UT  84115

                          [phone] (voice)

                          [phone] (data)


























     BTree4 is  a separately  compiled unit  for Turbo  Pascal ver. 4.0 from

Borland International, Inc. BTree4  may be  linked to  a user's  source pro-

grams,  and  will  performs  all  of  the  same B-tree indexing functions as

Borland's Database Toolbox.



     This file contains general information about BTree4, an  annotated copy

of the  interface segment  describing all variables and procedures available

to calling procedures, and licensing and  registration information.   PLEASE

READ THIS FILE COMPLETELY BEFORE ATTEMPTING TO USE BTREE4.



BTree4  has  been  designed  to  be as compatible as possible with Borland's

Database Toolbox, but it  is not  a modification  of Borland's  source code;

rather it  is a whole new set of procedures and functions using a compatible

calling interface, but a wholly different memory storage  technique.  BTree4

does not require any pre-defined constants or initializaton sequence, as all

data storage, including the index page  stack, is  created as  needed on the

heap.



     For maximum  flexibility, the BTree4 routines will not halt the program

for any IO or heap full errors.  If an error is detected, the global boolean

variable 'OK'  is set to false, and the global integer variable 'IOError' is

set equal to the IO error code.   If the  error was  caused by  the unavail-

ability of heap memory, 'IOError' will be set to -1.



     Disk  IO  errors  must  be  resolved  by the programmer, however memory

allocation errors can usually  be  resolved  by  the  use  of  the procedure

'CheckMem'   in   conjunction   with   the   global  variable  'MaxPageMem.'

'MaxPageMem' should be set by the programmer to  the maximum  amount of heap

memory which  will be allocated for the index page stack.  If the page stack

attempts to exceed this amount of allocated memory,  little used  pages will

be discarded from memory until the page stack is again under the limit.  The

program expects that the amount of memory available will never  be less than

the value stored in 'MinPageMem', and the stack size will never be decreased

to less than that  value; thus,  'MaxPageMem' should  always be  larger than

'MinPageMem.'



     Both 'MaxPageMem'  and 'MinPageMem'  can be dynamically assigned values

at any time during the operation of the program.  If more  dynamic memory is

needed,  the  page  stack  can  be  reduced in size by reducing the value of

'MaxPageMem' (and 'MinPageMem', if necessary) and then calling CheckMem with

a zero  parameter.  The only restriction is that 'MinPageMem' must always be

large enough to hold one page from each  level of  the tree,  plus one extra

page.



     In  addition  to  the  page  stack,  each open data file and index file

allocates for itself an IO buffer equal in size to the file's record length,

and each  index file  allocates an extra page buffer which is the same size.

These buffers are de-allocated  only by  closing the  associated file.   The

record length  for index  files is  equal to  5 + (number of keys per page X

(key length + 9)).



     What follows is a copy  of  the  BTree4  interface  section,  with each

procedure and significant variable annotated as to its function and use.
















{$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.  *)





     BTree4 is  shareware, which  means that it, like most shareware, may be

freely copied and distributed so long  as no  consideration is  required for

its distribution,  except a  copying and  media charge  not to exceed $3.00,

including the cost of the means of distribution (i.e., diskette).  Users who

find the  program of  value to  them should  consider sending  a donation to

Pass-Key Software.



     Users sending a donation of $25.00 or more are registered, will receive

notification of upgrades and modifications to this product, and are entitled

to receive source code and future updates, upon request, for  the cost  of a

diskette and  postage.   Non-registered useres may not incorporate this unit

into  any  commercially  distributed  software,  including  shareware, while

registered users may do so freely.
















     BTree4 is  a copyrighted  program, and  is protected by the laws of the

United States and each of its several states.  A  licence is  hereby granted

to all  persons to  use this program according to the terms and restrictions

contained herein.  All programs which  incorporate all  or any  part of this

program must include the following phrase both in the source code and in any

accompanying documentation:



     Portions of this program Copyright (c) 1988 by W. Lee Passey.



     This program is distributed as is, and by its use each person agrees to

the  terms  and  conditions  of  this  license, and acknowledges that W. Lee

Passey and Pass-Key Software have  made  no  warranties,  either  express or

implied,  concerning  the  performance  of  this software, including that of

fitness for a particular purpose.



     Please send all comments,  suggestions, information  regarding possible

bugs, donations and registration information to:



                             Pass-Key Software

                            119 MacArthur Ave.

                         Salt Lake City, UT  84115



or use  your modem  to call The Motherboard, [phone], 8 data, 1 stop,

no parity, 300/1200/2400 baud, 24 hours/day, 7 days/week.



     I am also looking for a job in the data processing field, and this unit

is a good example of my programming skills.  If any employers are interested

in using me as an employee, please contact me in the same way.