home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Simtel MSDOS 1992 September
/
Simtel20_Sept92.cdr
/
msdos
/
qbasic
/
qbtree42.arc
/
QBTREE42.DOC
< prev
next >
Wrap
Text File
|
1989-10-19
|
44KB
|
1,079 lines
A B-Tree Access Method
for QuickBASIC Programmers.
QBTREE (C)1989 Cornel Huth
The QBTREE package is a shareware product. You may try this
software to see if it fits your needs. You may copy and distribute
this package freely. If you continue to use it, fill out the
registration form and send it along with payment of $45 to:
Cornel Huth
ATTN: QBTREE 4.20 REGISTRATION
6402 Ingram Rd.
San Antonio, TX 78238
Source code for the QBTREE interface will be sent upon
registration. This interface is all that is needed to
modify QBTREE for most situations since all I/O is performed
at this level (QuickBASIC). If you also need the low-level
btree routine, I'll make it available. It's written in MASM
assembly. (Contact me for more details.)
QBTREE requires QuickBASIC 4.x or above. For file and
record locking functions, DOS 3.0 or above, is needed.
-----------------------------------------------------------------
QBTREE is a keyed-file system based on the b-tree sorting method.
It maintains up to 10 key files and also 10 data files. In
addition to finding any particular key and its associated
data record very quickly, QBTREE allows sequential access to
the data file. QBTREE automatically maintains the data file.
QBTREE automatically balances the tree at assembly language
speed.
The following files should be found on the disk:
QBTREE42.LIB QBTREE42.DOC QBTREE42.BI
SPEEDCHK.BAS SPEEDCHK.EXE SPEEDCHK.DOC
MAILAB.BAS MAILAB.EXE MAILAB.DOC
CONVERT.BAS CONVERT.DOC
TREETEST.BAS TREETEST.DOC
MEMCOPY.ASM
Add QBTREE42.LIB to your standard library if you like, and then
LINK /QU it into a QLB library for the environment.
C>lib yourstd.lib + QBTREE42.lib;
C>link /qu yourstd.lib,qb.qlb,nul,bqlb41.lib
You may prefer to keep QBTREE42.LIB as a separate library, instead.
C>link /qu yourstd.lib+QBTREE42.lib,qb.qlb,nul,bqlb41.lib
The networking functions are included in the library as a
separate module and thus will only be included in your
applications if you use them. The QuickBASIC source code
for them is included with registration.
Note that INTERRUPT and INTERRUPTX are defined in the module
INTRPT within QBTREE42.LIB. If you prefer to not have it there
but instead in your own library, remove it from QBTREE.LIB, e.g.,
C>lib QBTREE42.lib -INTRPT;
-----------------------------------------------------------------
Interface summary:
All QBTREE routines are FUNCTIONs and return an integer code
which is detailed in Error Codes. These must be DECLAREd.
1) CreateKeyFile% (filename$, keyl%)
2) CreateDataFile% (filename$, recl%)
3) OpenKeyFile% (filename$, fileno%)
4) OpenDataFile% (filename$, fileno%)
5) LockKeyFile% (kfile%)
6) UnlockKeyFile% (kfile%)
7) LockDataHeader% (dfile%)
8) LockRecord% (dfile%, recno&)
9) UnlockRecord% (dfile%, recno&)
10) AddRecord% (kfile%, dfile%, Qkey$, Qrec$)
11) GetEqual% (kfile%, dfile%, Qkey$, Qrec$)
12) GetFirst% (kfile%, dfile%, Qkey$, Qrec$)
13) GetLast% (kfile%, dfile%, Qkey$, Qrec$)
14) GetNext% (kfile%, dfile%, Qkey$, Qrec$)
15) GetPrev% (kfile%, dfile%, Qkey$, Qrec$)
16) GetPosition% (kfile%, recno&)
17) GetDirect% (dfile%, recno&, Qrec$)
18) PutKey% (kfile%, dfile%, Qkey$)
19) UpdateRecord% (dfile%, Qrec$)
20) RewindKeyFile% (fileno%)
21) DeleteKey% (kfile%, Qkey$)
22) DeleteRecord% (kfile%, dfile%, Qkey$)
23) StatKeyFile% (kfile%, keyl%, keys&, bfileno%)
24) StatDataFile% (dfile%, recl%, recs&, bfileno%)
25) FlushKeyFile% (kfile%, dup%)
26) FlushDataFile% (dfile%, dup%)
27) CloseKeyFile% (fileno%)
28) CloseDataFile% (fileno%)
29) QBTreeVer (ver%)
-----------------------------------------------------------------
Interface detail:
1) CreateKeyFile(filename$,keylen)
Create a new key file. filename$ must not already
exist.
filename$ - string. Pathname of key file to create.
Any valid DOS drive/path/filename can be used.
keylen - integer. Length of key for this key file.
Valid range is 1 to 64 bytes.
DEFINT A-Z
filename$ = "C:\HIST\AR89.KEY"
keylen = 16
stat = CreateKeyFile(filename$,keylen)
2) CreateDataFile(filename$,reclen)
Create a new data file. filename$ must not already.
filename$ - string. Pathname of data file to create.
Any valid DOS drive/path/filename can be used.
reclen - integer. Length of record for this data file.
Valid range is 3 to 32767 bytes, though QB's
string space will be the limiting factor.
filename$ = "C:\HIST\AR89.DAT"
reclen = 128
stat = CreateDataFile(filename$,reclen)
3) OpenKeyFile(filename$,fileno)
Open an EXISTING key file and associate it with fileno.
Before USING the key file, a data file will also need
to be opened. You may have multiple index files opened for
a data file.
The fileno is an arbitrary number, 0 to 9. It does
not reflect either a BASIC or DOS handle. It is used
to reference the key file in any later operation.
QBTREE uses the QuickBASIC FREEFILE function to obtain an
available channel but hides this from the application.
Use StatKeyFile() for information on the key file.
If version 3.0 or greater of DOS is detected then the open
is performed with a READ/WRITE access and a DENY NONE
sharing. Older versions of DOS will have a normal
open call. What this means is that other processes may
read from and write to the key file, filename$. See the
LockKeyFile() and UnlockKeyFile() functions for details
on locking the key file. To perform these DOS LAN functions
the DOS program SHARE.EXE needs to be run.
filename$ - string. Pathname of existing key file.
fileno - integer. Number to associate the key file
with for future operations. Valid range is
0 to 9.
filename$ = "C:\HIST\AR89."
ARKEY = 0
ARDAT = 0
stat = OpenKeyFile(filename$+"KEY",ARKEY)
if stat = 0 then stat = OpenDataFile(filename$+"DAT",ARDAT)
if stat <> 0 then DoErrorProc stat
4) OpenDataFile(filename$,fileno)
Open an EXISTING data file and associate it with fileno
and allocate a data buffer. The buffer will be the size
of the record length.
The fileno is an arbitrary number, 0 to 9. It does
not reflect either a BASIC or DOS handle. It is used
to reference the data file in any later operation.
QBTREE uses the QuickBASIC FREEFILE function to obtain an
available channel but hides this from the application.
Use StatDataFile() for information on the data file.
If version 3.0 or greater of DOS is detected then the open
is performed with a READ/WRITE access and a DENY NONE
sharing. Older versions of DOS will have a normal
open call. What this means is that other processes may
read from and write to the data file, filename$. See the
LockRecord() and UnlockRecord() functions for details on
locking records. To perform these DOS LAN functions the
DOS program SHARE.EXE needs to be run.
filename$ - string. Pathname of existing data file.
fileno - integer. Number to associate the data file
with for future operations. Valid range is
0 to 9.
{see OpenKeyFile() for an example}
5) LockKeyFile(kfile)
Lock the key file, kfile, to the current process. Any
other process requesting access to kfile will be denied
permission. It is recommended that this be used, in LAN
applications, prior to AddRecord(), PutKey(), DeleteKey(),
DeleteRecord(). To perform this DOS LAN function, the
DOS program SHARE.EXE needs to be run.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
kfile = 0
stat = LockKeyFile(kfile)
if stat = 229 then
print "Lock already in force"
elseif stat = 232 then
print "SHARE.EXE has not been run"
6) UnlockKeyFile(kfile)
Unlock the key file, kfile. You should do this as soon as
you have finished the AddRecord(), PutKey(), DeleteKey(),
DeleteRecord() operation. To perform this DOS LAN function,
the DOS program SHARE.EXE needs to be run.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
kfile = 0
stat = UnlockKeyFile(kfile)
if stat = 232 then
print "SHARE.EXE has not been run"
7) LockDataHeader(dfile)
Lock the data header in dfile to the current process. Any
other process requesting access to the header will be denied
permission. This function should be used before adding or
deleting a data record, though not needed for updating an
existing record. To perform this DOS LAN function, the DOS
program SHARE.EXE must be run.
dfile - integer. Number that was used as fileno in
OpenDataFile().
dfile = 0
stat = LockDataHeader(dfile)
if stat = 229 then
print "Lock already in force"
elseif stat = 232 then
print "SHARE.EXE needs to be run"
8) LockRecord(dfile,recno&)
Lock a specific record, recno&, in dfile, to the current
process. Any other process requesting access to recno&
will be denied permission. If recno&=0& then all records
in dfile will be locked (records 1 to EOF plus). To
perform this DOS LAN function, the DOS program SHARE.EXE
must be run.
dfile - integer. Number that was used as fileno in
OpenDataFile().
recno& - long. Data record number in data file to
lock.
dfile = 0
recno& = 1& '{lock the first record in dfile}
stat = LockRecord(dfile,recno&)
if stat = 229 then
print "Lock already in force"
elseif stat = 232 then
print "SHARE.EXE needs to be run"
9) UnlockRecord(dfile,recno&)
Unlock a specific record, recno&, in dfile. Once the record
that was locked is no longer needed, you should unlock it.
If a process terminates without releasing active locks on
a file, the result is undefined. If recno&=0& then all
records in dfile will be unlocked (records 1 to EOF plus).
To perform this DOS LAN function, the DOS program SHARE.EXE
must be installed.
dfile - integer. Number that was used as fileno in
OpenDataFile().
recno& - long. Data record number in data file to
unlock.
dfile = 0
recno& = 1& '{unlock the first record in dfile}
stat = UnlockRecord(dfile,recno&)
if stat = 232 then
print "SHARE.EXE has not been run"
10) AddRecord(kfile,dfile,Qkey$,Qrec$)
Add the key, Qkey$, to the key file, kfile, and the data
record, Qrec$, to the data file, dfile. Qkey$ must
not already exist. QBTREE is case-sensative so it is
recommended that keys be made upper-case (or lower) unless
there is a reason not to do this.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Key to add to key file.
Qrec$ - string. Data record to add to the data file
that is indexed by Qkey$.
kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
Qrec$ = xaction$
stat = AddRecord(kfile,dfile,Qkey$,Qrec$)
11) GetEqual(kfile,dfile,Qkey$,Qrec$)
Search for key, Qkey$, in kfile, and if found, retrieve
the data record from dfile, and place it in Qrec$. If
not found, the internal pointers indicate where it would
have been. By using GetNext(), GetPrev(), the next or
previous ordered key and data can be obtained.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Key for which to search in key file.
Qrec$ - string. Returned data record associated with
Qkey$.
kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = GetEqual(kfile,dfile,Qkey$,Qrec$)
'{Qrec$ is read}
if stat = 200 then
stat = GetNext(kfile,dfile,Qkey$,Qrec$)
'{Qkey$ & Qrec$ are read}
12) GetFirst(kfile,dfile,Qkey$,Qrec$)
Retrieve the first ordered key in kfile, placing it in
Qkey$, and place its data record from dfile into Qrec$.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Returned first ordered key.
Qrec$ - string. Returned data record associated with
the returned key, Qkey$.
kfile = 0
dfile = 0
stat = GetFirst(kfile,dfile,Qkey$,Qrec$)
13) GetLast(kfile,dfile,Qkey$,Qrec$)
Retrieve the last ordered key in kfile, placing it in
Qkey$, and place its data record from dfile into Qrec$.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Returned last ordered key.
Qrec$ - string. Returned data record associated with
the returned key, Qkey$.
kfile = 0
dfile = 0
stat = GetLast(kfile,dfile,Qkey$,Qrec$)
14) GetNext(kfile,dfile,Qkey$,Qrec$)
Retrieve the next ordered key in kfile, placing it in Qkey$,
and place its data record from dfile into Qrec$. This
function allows for sequential processing of the data file.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Returned key which immediately follows
the key found (or not found) in GetEqual() file.
Or the first key if the key file is rewound.
Qrec$ - string. Returned data record associated with
the returned key, Qkey$.
kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = GetNext(kfile,dfile,Qkey$,Qrec$)
15) GetPrev(kfile,dfile,Qkey$,Qrec$)
Retrieve the prev ordered key in kfile, placing it in Qkey$,
and place its data record from dfile into Qrec$. This
function allows for sequential processing of the data file
in reverse order.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Returned key which immediately precedes
the key found (or not found) in GetEqual() file.
Qrec$ - string. Returned data record associated with
the returned key, Qkey$.
kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = GetPrevl(kfile,dfile,Qkey$,Qrec$)
16) GetPosition(kfile,recno&)
Return the logical record number of the current record
pointed to by the last key FOUND in kfile.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
recno& - long. Returned current record number in the
last used (current) data file.
kfile = 0
stat = GetPosition(kfile,recno&)
if stat = 0 then
print "Current data record of kfile";kfile;" is";recno&
17) GetDirect(dfile,recno&,Qrec$)
Return the data in dfile at the logical record number,
recno&. This is especially useful for reindexing data
files, provided that the key is imbedded in the data
record. It is possible to retrieve deleted records from
the data file; records are not physically deleted but are
marked 'available' for a new data record. It is also
possible to give recno& a value past the true end of file.
This function does not affect the index file's internal
pointers.
dfile - integer. Number that was used as fileno in
OpenDataFile().
recno& - long. Record number to seek.
Qrec$ - string. Returned record data.
dfile = 0
recno& = 456&
stat = GetDirect(dfile,recno&,Qrec$)
if stat = 0 then
print "Record#";recno&;" =";Qrec$
18) PutKey(kfile,dfile,Qkey$)
After having found a key, insert the key Qkey$ into the
key file, kfile, (which most likely is an index file
other than the one where the key was found, though it can
be the same) and have associated with it the data record
that was indexed by the found key. This allows you have
multiple indexes per data file.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Key for which you want to add to the
key file, kfile, and have it also point to
the data record in dfile whose key was last
found.
kfile = 0
dfile = 0
Qkey$ = namekey$
stat = GetEqual(kfile,dfile,Qkey$,Qrec$)
if stat = 0 then
kfile = 1
Qkey$ = SSNkey$
stat = PutKey(kfile,dfile,Qkey$)
19) UpdateRecord(dfile,Qrec$)
Overwrite the current data record in dfile with Qrec$.
This allows you to update the contents of a record
in a data file.
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qrec$ - string. Data to use in replacing the previous
data in dfile.
kfile = 0
dfile = 0
Qkey$ = acctid$
stat = GetEqual(kfile,dfile,Qkey$,Qrec$)
if stat = 0 then
Qrec$ = newQrec$
stat = UpdateRecord(dfile,Qrec$)
20) RewindKeyFile(kfile)
Position the key file, kfile, to the first ordered key.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
kfile = 0
stat = RewindKeyFile(kfile)
21) DeleteKey(kfile,Qkey$)
Delete the key, Qkey$, from kfile. The data record
associated with Qkey$ is not affected. This is necessary
since you may have multiple indexes per data file.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
Qkey$ - string. Key to remove from kfile.
kfile = 0
Qkey$ = acctid$ + acctxn$
stat = DeleteKey(kfile,Qkey$)
22) DeleteRecord(kfile,dfile,Qkey$)
Delete the key, Qkey$, from file kfile and also delete
the associated record from dfile. Any other index files
keying to this record should have DeleteKey() performed
before using DeleteRecord() since the record space will
have been made 'available' for a new data record.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
dfile - integer. Number that was used as fileno in
OpenDataFile().
Qkey$ - string. Key for which you want to delete from
the key file, kfile, and also delete its
associated data record in dfile.
kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = DeleteRecord(kfile,dfile,Qkey$)
23) StatKeyFile(kfile,keylen,keys&,bfileno)
Return information about the key file, kfile.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
keylen - integer. Returned length of keys for kfile.
keys& - long. Returned number of keys in kfile.
bfileno - integer. Returned BASIC's file number for kfile.
kfile = 0
stat = StatKeyFile(kfile,keylen,keys&,bfileno)
24) StatDataFile(dfile,reclen,recs&,bfileno)
Return information about the data file, dfile.
dfile - integer. Number that was used as fileno in
OpenDataFile().
reclen - integer. Returned length of records for dfile.
recs& - long. Returned number of records in dfile.
bfileno - integer. Returned BASIC's file number for dfile.
dfile = 0
stat = StatDataFile(dfile,reclen,recs&,bfileno)
25) FlushKeyFile(kfile,dup)
Updates the key header information and, if dup is non-zero,
causes DOS to update the directory entry for kfile. This
is done by writing the key header out, having DOS duplicate
kfile's handle, then closing the duplicate handle.
This does not have the overhead of having to re-open
the key file. This also flushes DOS's internal buffers.
In LAN applications you should perform this function before
releasing a key file lock, but dup must be equal to 0.
If you force DOS to update the directory entry, UnlockKeyFile()
will return error 229 - Lock already in force. Not flushing
the buffers is not a problem in LAN applications since the
SHARE.EXE will not allow 'local buffer' problems to occur.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
kfile = 0
dup = -1 'dup must be 0 for LAN applications
stat = FlushKeyFile(kfile,dup)
26) FlushDataFile(dfile,dup)
Updates the data header information and, if dup is non-zero,
causes DOS to update the directory entry for dfile. This
is done by writing the data header out, having DOS duplicate
dfile's handle, then closing the duplicate handle.
This does not have the overhead of having to re-open
the data file. This also flushes DOS's internal buffers.
In LAN applications you should perform this function before
releasing a data record lock, but dup must be equal to 0.
If you force DOS to update the directory entry, UnlockRecord()
will return error 229 - Lock already in force. Not flushing
the buffers is not a problem in LAN applications since the
SHARE.EXE will not allow 'local buffer' problems to occur.
dfile - integer. Number that was used as fileno in
OpenDataFile().
dfile = 0
dup = -1 'dup must be 0 for LAN applications
stat = FlushDataFile(dfile,dup)
27) CloseKeyFile(kfile)
Close the key file, kfile. This is essential for proper
termination in QBTREE. Header information is written only
when the file is closed, or flushed. Release any active
locks first.
kfile - integer. Number that was used as fileno in
OpenKeyFile().
kfile = 0
stat = CloseKeyFile(kfile)
28) CloseDataFile(dfile)
Close the data file, dfile, releasing the data buffer
allocated to it. This function is essential for proper
termination in QBTREE. Release any active locks first.
dfile - integer. Number that was used as fileno in
OpenDataFile().
dfile = 0
stat = CloseDataFile(dfile)
29) QBTreeVer(ver)
Returns the version of the QBTREE access method (X100).
ver - integer. Returned version number * 100.
stat = QBTreeVer(ver)
print "QBTREE version";ver\100
-----------------------------------------------------------------
Error Codes:
200 Key not found
- the key is not in the index file. This will occur
during a GetEqual(), DeleteKey(), DeleteRecord().
201 Key already exists
- duplicate keys are not allowed in QBTREE. This
will occur during AddRecord(), PutKey().
202 End of file
- GetNext() has reached the end of file.
203 Top of file
- GetPrev() has reached the top of file.
204 Empty file
- there are no keys in the index file. This will
occur when you attempt to perform functions that
would require a non-empty file.
205 Disk full
- if the key file drive and the data file drive are the
same a minimum of 2 clusters are needed for the key
file plus the clusters required to completely hold the
data record before you can AddRecord() or PutKey().
If they are separate drives, the key file needs at
least 2 clusters free on its disk and the data file
disk as many clusters as needed to hold the data record.
This will also occur during CreateKeyFile(),
CreateDataFile().
206 Data pointer invalid
- a valid QBTREE key access, either GetEqual(), GetNext(),
GetPrev(), GetFirst(), GetLast() but NOT RewindKeyFile(),
must occur right before a data record can be updated.
207-
209 reserved
210 Stack overflow (10 levels)
- the internal tracking stack exceeds capacity. This
will probably never occur.
211 Function not implemented
- this won't happen unless you call the low-level
driver.
212-
219 reserved
220 Data record length invalid
- data record length must be from 3 to 32767 bytes
when creating data file.
221 Key length invalid
- key length must be from 1 to 64 bytes when creating
key file.
222 File not open
- the file number for StatKeyFile(), StatDataFile(),
FlushKeyFile(), FlushDataFile(), GetDirect(), or
any of the locking functions is not valid. If other
QBTREE functions are used to access an unopen file,
QuickBASIC will handle the error since all disk I/O
is done by QuickBASIC.
223 Invalid null key assignment
- a null key cannot be used. Null is defined in QBTREE
as either ASCII 0 or ASCII 255. This will occur in
AddRecord(), DeleteKey(), DeleteRecord(), GetEqual(),
PutKey().
224 Invalid record number
- a record number less than 1 was used in GetDirect().
Upper bounds is not validated.
225 No handle available for DUP
- no DOS handles are available to flush files. Use a
greater value in config.sys FILES= (FILES=20).
226 Invalid drive specifier
- the drive specified in CreateKeyFile(),
CreateDataFile() is not a valid DOS drive.
227 File needs to be converted
- QBTREE version 4.2 uses a new key file format. A
utility program is included to convert QSAM versions
1 to 3.xx, and BTREE 4.0x to QBTREE 4.20. Previous
versions of this program should no longer be used since
a coding error causes DeleteKey() & DeleteRecord() to
fail. This error will occur only at OpenKeyFile() or
OpenDataFile() functions.
228 File not QBTREE
- the filename in OpenKeyFile() or OpenDataFile() is not
recognized as a QBTREE file.
229 Lock already in force
- the lock requested cannot be made because an existing
lock of the header, record or file is in force.
See FlushKeyFile() and FlushDataFile() also.
230 File already exists
- the CreateKeyFile() or CreateDataFile() filename
already exists. Delete the filename if you really
want to use the same filename. Note that the create
functions do not explicitly check for valid pathnames.
If an invalid pathname is given, QuickBASIC will report
then error.
231 File not found
- the filename$ specified in OpenKeyFile() or
OpenDataFile() does not exist or is not valid.
232 General lock failure
- usually means that SHARE.EXE was not run before using
LockDataHeader(), LockRecord(), UnlockRecord(),
LockKeyFile(), UnlockKeyFile().
233-
255 reserved
-----------------------------------------------------------------
Technical Specifications:
Key length: 1 - 64 bytes (ASCII sort), constant
Record length: 3 - 32767 bytes, constant (avail near memory)
Node size: 512 bytes
Keys per node: 7 - 84 keys, (512-3)\(key length+5)
Max keys/file: 16 million keys
Max data/file: 16 million bytes
Max key files: 10 opened at one time (avail DOS files)
Max data files: 10 opened at one time (avail DOS files)
Key file header format (first sector (512 bytes) of key file):
filetype char ; 0 file type, "*", ASCII 42
rootnode int ; 1 sector in file of root node
nokeyslo int ; 3 number of keys (low word)
nokeyshi byte ; 5 number of keys (high byte)
keyavsec int ; 6 key available list head
nxkeysec int ; 8 next free sector
keylen byte ; 10 length of key
maxkeys byte ; 11 maximum keys per node
ackysc int ; 12 actual key sector in buffer
cukysc int ; 14 current key sector
cukyof byte ; 16 current key offset
iflag byte ; 17 internal flag
stkcnt byte ; 18 tree level count
pstack long ; 19 - 58 tree stack (4 bytes per level)
reserved any ; 59 - 255
free use any ; 256 - 383
reserved any ; 384 - 511
Data file header format (first 32 bytes of data file):
filetype char ; 0 file type, "S"
reclen int ; 1 length of record
norecslo int ; 3 number of records (low word)
norecshi byte ; 5 number of records (high byte)
datavlo int ; 6 data available list (low word)
datavhi byte ; 8 data available list (high byte)
nxdalo int ; 9 next data record avail (low word)
nxdahi byte ; 11 next data record avail (high byte)
internal byte ; 12
cudalo int ; 13 current data record (low word)
cudahi byte ; 15 current data record (high byte)
internal any ; 16 - 31 reserved
Key format:
There is an internal first key with a null value immediately
following the key header.
Beginning each node (sector) is a count key byte. This
is the count of keys on that sector. Then for each key
is a 16-bit previous node pointer, the key itself, the
24-bit data pointer for that key, and a 16-bit next node
pointer (node pointers are zero at the leaf nodes).
02 00 00 000000 00 00 00 00 00 KEY001 01 00 00 00 00 ...
1. 2. 3. 4. 5. 6. 7. 8. 9.
1. Key count for that node
2. Node back pointer (for non-leaf nodes)
3. The internal null key
4. The 24-bit data record pointer (zero)
5. Fwd ptr/back ptr (for non-leaf nodes)
6. First logical key
7. Its data pointer (record number in data file)
8. Its forward pointer (for non-leaf nodes)
9. Unused space to end of sector
Data record format:
Straight data after the header. Logical record #1 follows
the header.
BTREE42.BAS, the I/O and interface portion of QBTREE was written
and compiled with QuickBASIC 4.00b. The BTREE42.BAS file was
compiled with the /O option only. If using QuickBASIC 4.00b+,
which has a better error handling algorithm than 4.0, you can trap
I/O errors with QB even though the BTREE42 module was compiled
without the /E or /X options. Version 4.00, however, will instead
dump the program to DOS, so you need to perform common I/O checks
such as checking to see if a file exists, etc., before using
QBTREE functions with QB/BC 4.0.
One check that is not handled well by QBTREE42 is an open
drive door. It is thus necessary to check for a ready drive
if the media is removable (not a problem with hard disks).
For those of you still using version 4.00, contact Microsoft
Customer Support (it's toll-free) for a free maintenance
upgrade to 4.00b. All you need are the original disk serial
numbers. Within a week you'll get it.
Storage for the data buffers and headers are allocated in the
default data area of QB. BTREE42.BAS storage allocation is
as follows:
2 integer arrays (0 to 9) for file handles.
1 key hdr array (0 to 9) for key file headers, ea 62 bytes.
1 data hdr array (0 to 9) for data file headers, ea 32 bytes.
1 key node array (0 to 9) for node buffers, ea 512 bytes.
1 data buffer array$ (0 to 9) for data record I/O, size
allocated is equal to that dfile's record length (var-len$).
1 long integer array (0 to 9) to track current record numbers.
2 integer arrays (0 to 9) to track file drives
1 type variable for interfacing with QBTREE low-level, 18 bytes.
... and other miscellaneous variables
Tip 1: QBTREE uses a simple variable, namely a var-len string,
to get and put data in the data file. To work around this,
you may want to use the method below. Go ahead and set up your
TYPEd variable, then allocate enough space in a var-len
string to copy to and from it.
TYPE dataTYPE
whatis AS INTEGER
whatbe AS STRING * 8
whaton AS LONG
END TYPE
DIM whatit AS dataTYPE
whatit.whatis = 2
whatit.whatbe = "right on"
whatit.whaton = 6&
DIM SHARED thatit$
thatit$ = SPACE$(LEN(whatit))
FromSec = VARSEG(whatit.whatis)
FromOff = VARPTR(whatit.whatis)
ToSec = VARSEG(thatit$) '{we want the offset to the string's}
ToOff = SADD(thatit$) '{address, not the string descriptor's}
count = len(thatit$)
dir = 1
MemCopy FromSec,FromOff,ToSec,ToOff,count,dir
'{You now have the TYPEd variable data in a var-len string that}
'{can be used as the Qrec$. To put Qrec$ in the typed variable,}
'{reverse the from/to assignments.}
'{MemCopy is included in the QBTREE42.LIB and QBTREE42.BI}
TIP 2: QBTREE does not allow duplicate keys (this may be an
inconvenience in some data base programming) but this can easily
be worked around by adding to each key an additional byte. This
byte would act to differentiate up to 256 'identical' keys. E.g.,
If the needed key length is 16 bytes, make it 17.
Reserve the 17th byte so that you can enumerate
identical keys. When adding a key that does not
already exist, place an ASCII 0 in byte 17 of the
key. If the key already exists (error 201), use
ASCII 1, and so on, until no error is returned.
By adding a 2-byte enumerator, 65536 identical keys
can be used.
****************** QBTREE REGISTRATION FORM ********** 420 **
Name of registrant: __________________________________________
Amount paid: $ ____________ ($45 ea.) If you want me to send
the interface source
code, fill out the non-
release form below.
Comments: ___________________________________________________
___________________________________________________
Contact: ________________________ Phone:( )____-__________
Would you like to be added to our mailing list? ___
Mail to: ___________________________________________________
___________________________________________________
___________________________________________________
Send payment to: Cornel Huth
ATTN: QBTREE 4.20 REGISTRATION
6402 Ingram Rd.
San Antonio, TX 78238
*** NON-RELEASE FORM for QBTREE 4.20 INTERFACE SOURCE CODE ****
I, _______________________________________, hereby agree not
to distribute, nor claim ownership of, QBTREE source code, or
any modification, to the QBTREE interface, and not remove the
copyright notice of Cornel Huth from any part of QBTREE.
DATE:__________________
_______________________
(If you would like the interface source code in QB 4.00b,
print your name in the first blank, date the second, and
sign the third.)