Programmer 7500

home *** CD-ROM | disk | FTP | other *** search

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

Wrap

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 (801) 486-9239 (voice) (801) 485-7211 (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, (801) 485-7211, 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.