TopSpeed Modula-2 B-tree Toolkit V3.0 Release Notes This document provides corrections and additions to the TopSpeed Modula-2 B-tree Toolkit manual. Notation 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� Within this document, the term B-tree refers to the entire B-tree Toolkit, while the term Btree refers to the single module by the same name. Also within this document, certain file names and partial file names may contain the meta-symbols %O% and %M%. The %O% symbol refers to the operating system, and should be replaced with either R or P (for real- or protected-mode i.e. DOS or OS/2). The %M% symbol refers to the memory model, and should be replaced with S, C, M, L, X, or MT (for Small, Compact, Medium, Large, Extra-Large, and Multi-Thread). These are standard conventions within the TopSpeed product line, and are used primarily within project files. (Within project files, the meta-symbols will automatically be converted to the appropriate characters. See your language User's Manual for details.) Libraries supplied with version 3.0 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� The following pre-compiled libraries are supplied with the B-Tree toolkit Model Calling conv. Language OS Name =================================================== Small, JPI M2 DOS RS_BT.LIB Large, JPI M2 DOS RL_BT.LIB XLarge, JPI M2 DOS RX_BT.LIB MThread, JPI M2 DOS RT_BT.LIB Small, JPI M2 OS2 PS_BT.LIB Large, JPI M2 OS2 PL_BT.LIB XLarge, JPI M2 OS2 PX_BT.LIB MThread, JPI M2 OS2 PT_BT.LIB Large, Stack M2 DOS RLFBT.LIB Large, Stack M2 OS2 PLFBT.LIB Small, JPI C DOS RS_BTC.LIB Large, JPI C DOS RL_BTC.LIB XLarge, JPI C DOS RX_BTC.LIB Large, JPI C OS2 PL_BTC.LIB XLarge, JPI C OS2 PX_BTC.LIB Large, Stack C DOS RLFBTC.LIB Large, Stack C OS2 PLFBTC.LIB Other variations can be made by making the project MKBTREE with the appropriate settings. Data Compression with version 3.0 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� This version of the TopSpeed Modula-2 B-tree Toolkit provides optional automatic data compression. See the section Using Data Compression for details. (All users should read this section, since data compression has a large effect on an application's memory usage.) This version of the Toolkit differs from V2.1 primarily in the organization of functions within libraries. This re-organization reduces the amount of redundant code between the libraries for different options, as well as making it possible to rebuild large portions of the Toolkit without owning the Extended Edition of TopSpeed Modula-2.. This version of the Toolkit is able to read data files created with V2.0. It is unable to read data files from versions before V2.0. For backwards compatability, data files created with this version may be accessed using V2.0 with one exception: V2.0 will not recognize data files created using the new data compression option. Data files created with this version cannot not be accessed using any versions prior to V2.0. See the section Converting File Formats for details. The FreeIHandle procedure has been changed from V2.1 and earlier: in some cases, FreeIHandle may now be used for handles in a shared file. See the Errata section for details. Installation 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� The B-tree Toolkit is installed by running the INSTALL program located on the installation disk. The INSTALL program must be used - it is not possible to use the files directly off of the disks. The INSTALL program will place the files into the appropriate subdirectories for your TopSpeed installation - you simply provide it with the name of the directory into which you installed your compiler. A number of installation options are provided by the INSTALL program. These options provide the ability to install support for DOS and OS/2, as well as support for TopSpeed C. Another option installs Modula-2 example programs. Finally, an option is provided for installing the B-tree Modula-2 source code. Using With TopSpeed Modula-2 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� The Btree.DEF file provides all of the Modula-2 definitions needed for an application to use the B-tree Toolkit. The FIOx.DEF, Pack.DEF, and apack2.DEF files provide definition used by the Btree module. Changes must be made to an application's project file in order to link to the B-tree Toolkit routines. Modula-2 user's may link to the Toolkit in one of two ways: 1) By importing the pre-compiled libraries into the application's project: this requires an import statement to be added to the project file; 2) By implicitly including the object modules into the link step: this requires override statements to be added to the project file. 1) An example project file which imports the B-tree library into a Modula-2 program might look like this: #system auto exe #model mthread jpi #compile %main #pragma link(%O%%M%_bt.lib) -- link in btree library #link %prjname Note that you must have installed support for the appropriate operating system, in order to have the necessary libraries available. 2) An example project file which implicitly includes the B- tree object modules might look like this: #system auto exe #model mthread jpi #compile %main #link %prjname Note that you must install the B-tree source code to use this method. The main reason for using the second method is to be able to perform source-level debugging with the Btree, FIOx, and Pack modules. If this debugging ability isn't needed, then using the first method will make development easier (since the compiler won't need to recompile the Toolkit source code). Using With TopSpeed C 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� The Btree.H file provides all of the C definitions needed to use the B-tree Toolkit. (It contains all of the definitions from Btree.DEF, FIOx.DEF, and apack2.DEF.) Since the Toolkit User's Manual documents all of the definitions using Modula-2 syntax, the Btree.H file provides the best reference for determining the C syntax for the same definitions. Since the C language does not provide a notation for automatic initialization of sub-systems, a C program using the Toolkit must explicitly call the initialization code. This is accomplished by executing the statement InitModules(Btree$,NULL); before any calls are made into the Toolkit. The InitModules() function is declared in mlang.H. The Btree$ structure is declared in Btree.H. Note that if data compression is to be used, then the statement must be changed to InitModules(Btree$,Pack$,NULL); in order to initialize the packing routines. See the section Using Data Compression for details. TopSpeed C user's must import the B-tree library into their application's project files. In addition, a special support library called %O%%M%_btc must be imported. An example project file might look like this: #system auto exe #model large jpi #compile %main #pragma link(%O%%M%_bt.lib) -- link in btree library #pragma link(%O%%M%_btc.lib) -- library for C #link %prjname Note that the support libraries must have been installed with the INSTALL program. The CBT.C program (and CBT.PRJ project file) serve as an an example of using the B-tree Toolkit with TopSpeed C. CBT accepts a single command-line parameter: the name of an input text file. It uses a B-tree file (named CBT.DAT) to sort the lines in the input file, and writes the result to standard output. While this is not necessarily a good illustration of the Toolkit's strengths (since there are much faster ways to sort a text file), it does illustrate how to interface to the Toolkit from C. On the other hand, this example program does use the Toolkit's data compression capabilities. Using With Both TopSpeed Modula-2 and TopSpeed C 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� User's with both TopSpeed Modula-2 and TopSpeed C can use either of the any of the above methods in their application's project files. For mixed-language projects, If the main module is written in C, then Btree$ (and possibly Pack$) must be added to the InitModules() statement in the programs main() function. An example program which uses a Modula-2 main module and two C files might look like this: #system auto exe #model large jpi #compile mprog.mod #compile cproga.c #compile cprogb.c #pragma link(%O%%M%_bt.lib) -- link in btree library #link %prjname Using Data Compression 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� This version of the Toolkit provides optional automatic data compression. Data compression is available only in memory models which use far data pointers (i.e. Compact, Large, Extra-Large, and Multi-Thread). Since data compression adds an overhead of 62K of data space (regardless of whether it is used or not), the default behavior is to not provide data compression. Data compression is only enabled when the initialization code of the Pack module is executed. Data compression is performed on any variable-length data files which are within physical files having an access mode of Compress. Thus, to use data compression, follow these steps: 1) Import the Pack module into one of the Modula-2 modules (or include Pack$ in the InitModules() statement of the C main() function). The Pack module will generate compilation errors if it is imported in the Small and Medium memory models. 2) Open the physical file with an access mode of Compress. Note that not importing Pack into a Modula-2 module will cause the error BadOpen to be generated at run-time if this access mode is used. 3) Open the logical data files as variable-length (i.e. specify a record length of 0 to Btree.OpenData()). 4) Always pass the correct (uncompressed) record length in calls to Btree.Add(). (If you are converting an existing program from fixed-length records to variable-length records with compression, be sure to check all of the calls your program makes to Btree.Add().) Apart from these three requirements, data compression is completely transparent. Data compression has a neglible effect on the speed of file access. Optimal compression ratios can be achieved by filling all used portions of records with a common byte value (preferably 0). Any call to Btree.Change() for a record in a data-compressed table will result in a BadSize run-time error. Any attempt to open a physical file created as Compress with a mode other than Compress (including attempting to open the file from the V2.0 Toolkit) will result in a BadOpen run-time error. Converting File Formats 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� Any data files created with a version of the Toolkit prior to V2.0 must be converted in order to be used with V2.0 or V2.1. This conversion must be performed by programs which has information on the format of the data records within the file (i.e. by programs written by the user of the Toolkit). Converting the file involves two steps. The first step is to use the older Toolkit to read all of the data records from the B-tree file and write them out in an intermediate non-B-tree file. The second step is to read the records from the intermediate non-B- tree file and write them to a new B-tree file using the new Toolkit. Skeleton programs might look like this: MODULE Step1; IMPORT Btree, FIO; CONST Access = Btree.FixedSize; (* modify as appropriate *) Slots = 2; (* modify as appropriate *) DataSlot = 1; (* modify as appropriate *) IndexSlot = 1; (* modify as appropriate *) Dup = TRUE; (* modify as appropriate *) TYPE Dat = RECORD (* modify as appropriate *) END; Key = RECORD (* modify as appropriate *) END; PROCEDURE CompProc(a,b : ADDRESS) : Btree.CmpRes; BEGIN (* modify as appropriate *) END CompProc; PROCEDURE KeyProc(k,d : ADDRESS); BEGIN (* modify as appropriate *) END KeyProc; VAR fH : Btree.FHandle; dH,iH : Btree.IHandle; rec : Dat; tmp : FIO.File; BEGIN fH := Btree.Open('Data.OLD',Slots,Access,FALSE,FALSE,FALSE); dH := Btree.OpenData(fH,DataSlot,SIZE(Dat),FALSE); iH := Btree.OpenIndex(fH,dH,IndexSlot,CompProc,KeyProc,SIZE(Key), Dup,FALSE); tmp := FIO.Create('Data.TMP'); Btree.Reset(dH); WHILE Btree.Next(iH,rec) DO FIO.WrBin(tmp,rec,SIZE(rec)); END; FIO.Close(tmp) Btree.Close(fH); END Step1. MODULE Step2; IMPORT Btree, FIO; CONST Access = Btree.FixedSize; (* modify as appropriate *) Slots = 2; (* modify as appropriate *) DataSlot = 1; (* modify as appropriate *) IndexSlot = 1; (* modify as appropriate *) Dup = TRUE; (* modify as appropriate *) TYPE Dat = RECORD (* modify as appropriate *) END; Key = RECORD (* modify as appropriate *) END; PROCEDURE CompProc(a,b : ADDRESS) : Btree.CmpRes; BEGIN (* modify as appropriate *) END CompProc; PROCEDURE KeyProc(k,d : ADDRESS); BEGIN (* modify as appropriate *) END KeyProc; VAR fH : Btree.FHandle; dH,iH : Btree.IHandle; rec : Dat; tmp : FIO.File; BEGIN fH := Btree.Open('Data.NEW',Slots,Access,FALSE,FALSE,TRUE); dH := Btree.OpenData(fH,DataSlot,SIZE(Dat)tl,TRUE); iH := Btree.OpenIndex(fH,dH,IndexSlot,CompProc,KeyProc,SIZE(Key), Dup,TRUE); tmp := FIO.Open('Data.TMP'); WHILE FIO.RdBin(tmp,rec,SIZE(rec))=SIZE(rec) DO Btree.Add(dH,rec,SIZE(rec)); END; FIO.Close(tmp) Btree.Close(fH); END Step2. Again, the Step1 program must be linked using the older version of the Toolkit, and the Step2 program must be linked using the newer version of the Toolkit. Rebuilding the Toolkit 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� The Toolkit source code is in the following files: Btree.DEF/.MOD - b-tree routines FIOx.DEF/.MOD - file i/o routines Pack.DEF/.MOD - high-level packing routines apack2.DEF/.A - low-level assembly packing routines The B-tree Toolkit libries can be made with the project file: MKBTREE.PR The model, operating system, whether C support is required, and whether packing is required should be set in this project file before making any particular library. Rebuilding the Toolkit libraries requires TopSpeed Modula-2. Errata 컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� The B-tree Toolkit uses mixed-model programming to overcome limitations of the Small and Medium memory models. Even so, manipulating large index files from within Small or Medium model programs may cause the B-tree system to exhaust all of heap memory. If this happens, the application may not terminate gracefully! ----------------------------------------------------------------- The Btree.SetSyncMode documentation is incorrect. It should read as follows: PROCEDURE SetSyncMode(D: IHandle; On: BOOLEAN); Normally, each index maintains an independent "current record" pointer. If the SetSyncMode procedure is called with its second parameter set to TRUE, then these index operations will cause all indexes related to that data file to be moved to the located record: Find, Search, Next, Prev. (The result from any other index operations is undefined.) The procedure may be called with the second parameter as FALSE, to disable index syncronization. This procedure always calls Reset() with the data file handle. This means that whenever synchronization starts or ends, all of the indexes for the data file are set so that a Next or Prev call returns the first or last record, respectively. This procedure may only be called for data file handles. Error condition Last Error Value ErrorHandler Called =============== ================ =================== Not a data handle NotData yes ----------------------------------------------------------------- When the Next and Prev procedures fail due to the data file being locked, they leave the location pointer for that index unchanged from its state before the call. The following algorithm is recommended for scanning through a data file sequentially, when other processes may be locking data records: LOOP IF Next(IndexFile,Record) THEN (* A *) (* process the record *) ELSE CASE LastError(IndexFile) OF OK : EXIT; (* past end of index *) | Locked : IF NextIndex(IndexFile,Location) THEN (* B *) (* either the index was briefly locked, or the data record was locked *) ELSE CASE LastError(IndexFile) OF OK : HALT; (* this should never happen *) | Locked : EXIT; (* the index is locked *) ELSE EXIT; (* some other error occured *) END; END; ELSE (* some other error occured *) END; END; END; This algorithm is useful for providing a list of records to the user. The application could print the contents of the records returned by the Next call (location A), and could print a line saying that the record is locked for records returned by the NextIndex call (location B). ----------------------------------------------------------------- When the ClearIndex procedure is called for an index in a shared file, the last error value is BadFree, and the error handler procedure is called. ----------------------------------------------------------------- In some cases, it is illegal to call the FreeIHandle procedure for an IHandle stored within a shared file. If this happens, the last error value is BadFree, and the error handler procedure is called. Specifically, any attempt to FreeIHandle for an index handle which is associated with a data handle is illegal. Note that it is legal to FreeIHandle for a data handle (in which case all of the index handles are also freed), as well as for an index handle which is not associated with a data handle. ----------------------------------------------------------------- Since all of the file locking primitives are isolated in the FIOX module, it is fairly simple to customize the package for a particular environment. For example, under VM/386 file locking is always available, regardless of whether SHARE is loaded or not. The FIOx.Multi() procedure could be modified to return TRUE if the program is running under VM/386. Additionally, the locking calls can be easily customized for a particular network's API. You must have TopSpeed Modula-2 in order to recompile the source code after making these changes. ----------------------------------------------------------------- The B-tree Toolkit may be freely used in a (DOS or OS/2) multi- threaded program. All operating system calls are locked as necessary, and the B-tree internal least-recently-used buffer and packing buffer are protected by locking. In a multi-threaded environment, each thread wishing to access a file must open its own handles for the file, specifying that the file is to be shared. This will ensure that the threads do not corrupt each other's file information. Alternatively, the application must ensure that while one thread is performing any operations on an FHandle(or any IHandles within it), that no other threads attempt to use that same FHandle (or any IHandles within it). ----------------------------------------------------------------- The Btree.LastRef procedure has been added: PROCEDURE LastRef(I: IHandle): LONGCARD; This procedure returns the last data position referenced by a data or index handle. For instance, after an Add() operation, LastRef() for the data handle or any of its associated index handles will return the postion that the data record was written to. After a Find() operation, LastRef() will return the position that the record was read from. ----------------------------------------------------------------- The Btree.RecordCount procedure has been added: PROCEDURE RecordCount(I: IHandle): LONGCARD; This procedure returns the number of records in a data handle or the number of keys in an index handle. For shared files, the handle must already be locked and will not be unlocked by this call. For shared files, the record count could change at any time that the process does not have a lock on the handle. Error condition Last Error Value ErrorHandler Called =============== ================ =================== Not an IHandle NotIHandle yes Not locked NotLocked yes ----------------------------------------------------------------- The B-tree Toolkit attempts to intelligently determine whether files should be buffered or not, based upon the user's specification or whether file sharing should be allowed, and whether the file resides in a location where multi-access is possible. If both sharing and multi-access are enabled, then the file will *not* be buffered (because other processes could cause the in-memory buffer to become out-of-date). If either sharing or multi-access is disabled, then no other processes may access the file, and buffering will occur. The OS/2 FIOx module always allows multi-access. The DOS version of the FIOx module determines whether multi- access is available using the following algorithm: if the environment variable "multi" = "yes", then multi is available, elsif the environment variable "multi" = "no" then multi is no available, elsif the DOS version is 3.x+ and SHARE is installed, then multi is available, else multi is done on a file-by-file basis end If multi is done on a file-by-file basis (i.e. the last case of the above algorithm), and an application attempts to open a file in shared mode, then FIOx will attempt to determine if the file resides on a network drive: attempt to open file in ReadOnly DenyNone mode if file is opened and IOCTL signals that the file is remote, then attempt to open file with sharing, and return result end end attempt to open file without sharing, and return result Applications should follow these guidelines: 1) Applications which are designed to share files, which are run in a sharing environment, will share files. 2) Applications which are designed to share files, which are run in a *non*-sharing environment, will have exclusive use of the files. 3) Applications which are designed to *not* share files will always open the files in non-sharing mode, thus preventing all other processes from using them concurrently. Users should follow these guidelines: 1) If you are not using file sharing, you don't have to do anything special - just open the files in non-shared mode. 2) If you are using file sharing on a LAN that loades SHARE.EXE, you don't have to do anything special - Btree will detect that SHARE is loaded, and will share files that you open in shared mode. 3) If you are using file sharing on a LAN that supports IOCTL detection that the file is on a remote device (this include Novell's NetWare v2.1x), you don't have to do anything special - just open the files in shared mode. 4) If you want to always prevent sharing, then before your programs load, use SET MULTI=NO from the DOS command line. This will cause all files opened (in sharing mode or not) to be opened for exclusive access (regardless of whether SHARE is loaded or the file is on a network device). 5) If you want to always allow sharing, then before your programs load, use SET MULTI=YES from the DOS command line. This will cause all files opened in sharing mode to be opened for sharing (regardless of whether SHARE is loaded or the file is on a network device). Note that this may be incompatible in environments where the DOS file locking calls are not always available. ----------------------------------------------------------------- The FIOx.Multi procedure has been changed: TYPE MultiMode = (_multi_yes,_multi_no,_multi_file); PROCEDURE Multi(): MultiMode; This procedure will return _multi_yes if multi-access is always available (i.e. SHARE is loaded, multi=yes in the environment, or OS/2 is being used),_multi_no if multi-access is disallowed (i.e. multi=no in the environment), or _multi_file if multi-access should be done on a file-by-file basis. The FIOx.MultiFile procedure has been added: PROCEDURE MultiFile(f: File): BOOLEAN; This procedure returns TRUE if the file should be used in multi- access mode. It is closely related to the Multi() procedure: 1) Multi() = _multi_yes ==> MultiFile() = TRUE 2) Multi() = _multi_no ==> MultiFile() = FALSE 3) Multi() = _multi_file ==> MultiFile() = TRUE if file is on net device Note that Btree does not provide a procedure for determing if an FHandle is actually being shared - applications should be written to be ignorant of the actual sharing mode of the file.