A B-Tree Access Method
for QuickBASIC Programmers.

QSAM 3.0 (C)1989 Cornel Huth


Feel free to use QSAM in any program of yours. No registration
or payment is required. If you want the source code send $20.00
to:

Cornel Huth
ATTN: QSAM SOURCE
6402 Ingram Rd.
San Antonio, TX 78238


I will send you the latest version of QSAM source on
5" DS/DD IBM-readable diskette. The source includes
the QSAM low-level stuff (written in MASM-compatible
assembly) and the QuickBASIC 4.0 I/O and interface.


-----------------------------------------------------------------
QSAM is a keyed-file system based on the b-tree sorting method.
In addition to finding any particular key and its associated
data record very quickly, QSAM allows sequential access to
the data file (not usually found in b-tree access programs).

This program was originally created by Rick Grehan for Turbo-C.
He has submitted it to the public domain and I thank him for that
and the nice work he did on the very readable assembly code.

What you should find in the QSAM package is the QSAM300.LIB,
QSAM300.DOC, and QSTEST.BAS and QSAM300.BI.

Add QSAM300.LIB to your standard library if you like, and then
LINK /QU it into a QLB library for the environment.

C>lib yourstd.lib +qsam300.lib;

C>link /qu yourstd.lib,qb.qlb,nul,bqlb40.lib




-----------------------------------------------------------------
Interface summary:

All QSAM routines are FUNCTIONs and return an integer code
which is detailed in Error Codes. These must be DECLAREd.

1) Qcreatkf%(filename$,keylen%,kftype$)
2) Qcreatdf%(filename$,reclen%)
3) Qopenk%(filename$,fileno%)
4) Qopend%(filename$,fileno%)
5) Qcreatkr%(kfile%,dfile%,Qkey$,Qrec$)
6) Qreadkr%(kfile%,dfile%,Qkey%,Qrec$)
7) Qreadnkr%(kfile%,dfile%,Qkey$,Qrec$)
8) Qinsertk%(kfile%,dfile%,Qkey$)
9) Qwritedr%(dfile%,Qrec$)
10) Qrewindk%(kfile%)
11) Qdelk%(kfile%,Qkey$)
12) Qdelkr%(kfile%,dfile%,Qkey$)
13) Qclosek%(kfile%)
14) Qclosed%(dfile%)
15) Qfileattrk%(kfile%,keylen%,keys&,bfileno%,kftype$)
16) Qfileattrd%(dfile%,reclen%,recs&,bfileno%,dftype$)

-----------------------------------------------------------------
Interface detail:

1) Qcreatkf(filename$,keylen,kftype$)

Create a new, empty key file. If filename$ exists, its
header will be overwritten by null data.

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.

kftype$ - string. For a sorting-only file, kftype$="O".
For an indexing file, kftype$ = "K". "O" is
key-Only and has no associated data file (and
data records). It can be used as a sorting
method. For "K" files, you should create a
data file.

filename$ = "C:\HIST\AR89.KEY"
keylen = 16
kftype$ = "K"
stat = Qcreatkf(filename$,keylen,kftype$)


2) Qcreatdf(filename$,reclen)

Create a new data file. If filename$ exists, its header
will be overwritten by null data.

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.

filename$ = "C:\HIST\AR89.DAT"
reclen = 128
stat = Qcreatdf(filename$,reclen)


3) Qopenk(filename$,fileno)

Open an existing key file and associate it with fileno.
If the file is a 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. It does
not reflect either a BASIC handle nor a DOS handle. It is,
however, used to reference the key file in any later operation.
QSAM uses the BASIC FREEFILE function to obtain an
available channel but hides this from the application.
Use Qfileattrk() for information on the key file.

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 = Qopenk(filename$+"KEY",ARKEY)
if stat = 0 then
kfile = fileno
stat = Qopend(filename$+"DAT",ARDAT)


4) Qopend(filename$,fileno)

Open an existing data file and associate it with fileno.
The fileno is an arbitrary number. It does not reflect
either a BASIC handle nor a DOS handle. It is, however,
used to reference the data file in any later operation.
Use Qfileattrd() for information on the data file.

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 Qopenk() for an example}


5) Qcreatkr(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. QSAM 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
openk().

dfile - integer. Number that was used as fileno in
opend().

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 = Qcreatkr(kfile,dfile,Qkey$,Qrec$)


6) Qreadkr(kfile,dfile,Qkey$,Qrec$)

Search for key, Qkey$, in kfile, and if found, retrieve
the data record from dfile, and place it in Qrec$.

kfile - integer. Number that was used as fileno in
openk().

dfile - integer. Number that was used as fileno in
opend().

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 = Qreadkr(kfile,dfile,Qkey$,Qrec$)


7) Qreadnkr(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.

kfile - integer. Number that was used as fileno in
openk().

dfile - integer. Number that was used as fileno in
opend().

Qkey$ - string. Returned key which immediately follows
the key found in Qreadkr() file.

Qrec$ - string. Returned data record associated with
the returned key, Qkey$.

kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
if stat = 0 then
stat = Qreadnkr(kfile,dfile,Qkey$,Qrec$)


8) Qinsertk(kfile,dfile,Qkey$)

After having found a key, insert the key Qkey$ into the
key file, kfile, and have associated with it the data
record that was indexed by the found key. This allows
you to add another key to index a particular data record,
including that from another kfile (multiple indicies per
data record).

kfile - integer. Number that was used as fileno in
openk().

dfile - integer. Number that was used as fileno in
opend().

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 of that last found
Qkey$ in kfile.

kfile = 1 '{1 of n opened index files to dfile}
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
if stat = 0 then
Qkey$ = acctid$ + timestamp$
stat = Qinsertk(kfile,dfile,Qkey$)


9) Qwritedr(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
opend().

Qrec$ - string. Data to use in replacing the previous
data in dfile.

kfile = 0
dfile = 0
Qkey$ = acctid$ + acctxn$
stat = Qreadkr(kfile,dfile,Qkey$,Qrec$)
if stat = 0 then
Qrec$ = Qrec$ + note$
stat = Qwritedr(dfile,Qrec$)


10) Qrewindk(kfile)

Position the key file, kfile, to the first key.

kfile - integer. Number that was used as fileno in
openk().

kfile = 0
stat = Qrewindk(kfile)


11) Qdelk(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 keys pointing to the same
data record.

kfile - integer. Number that was used as fileno in
openk().

Qkey$ - string. Key to remove from kfile.

kfile = 0
Qkey$ = acctid$ + acctxn$
stat = Qdelk(kfile,Qkey$)


12) Qdelkr(kfile,dfile,Qkey$)

Delete the key, Qkey$, from file kfile and also delete
the associated record from dfile. Any other keys that
are also tagged to that record will be invalid.

kfile - integer. Number that was used as fileno in
openk().

dfile - integer. Number that was used as fileno in
opend().

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 = Qdelkr(kfile,dfile,Qkey$)


13) Qclosek(kfile)

Close the key file, kfile. This is essential for proper
termination in QSAM. Header information is written only
when the file is closed. Do not rely on QuickBASIC to do
this, since it won't.

kfile - integer. Number that was used as fileno in
openk().

kfile = 0
stat = Qclosek(kfile)


14) Qclosed(dfile)

Close the data file, dfile. This is essential for proper
termination in QSAM.

dfile - integer. Number that was used as fileno in
opend().

dfile = 0
stat = Qclosed(dfile)


15) Qfileattrk(kfile,keylen,keys&,bfileno,kftype$)

Return information about the key file, kfile.

kfile - integer. Number that was used as fileno in
openk().

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.

kftype$ - string. Returned file type, "K" or "O".

kfile = 0
stat = Qfileattrk(kfile,keylen,keys&,bfileno,kftype$)


16) Qfileattrd(dfile,reclen,recs&,bfileno,dftype$)

Return information about the data file, dfile.

dfile - integer. Number that was used as fileno in
opend().

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.

dftype$ - string. Returned file type, always "S".

dfile = 0
stat = Qfileattrd(dfile,reclen,recs&,bfileno,dftype$)


-----------------------------------------------------------------
Error Codes:

200 Key not found 206 Data pointer invalid
201 Key already exists 207 Key pointer invalid
202 End of file 208 File not QSAM
203 reserved 209 reserved
204 Empty file 210 QSAM stack overflow (20 levels)
205 reserved 211 Function not implemented

220 Data record length invalid
221 Key length invalid
222 Invalid key file type

-----------------------------------------------------------------
Technical Specifications:

Key length: 1 - 64 bytes (ASCII sort), constant
Record length: 3 - 32767 bytes, constant (avail memory)
Node size: 512 bytes
Keys per node: 7 - 84 keys, (512-3)\(keylen+5)
Max keys/file: 16 million keys
Max data/file: 16 million bytes
Max key files: 10 opened at one time
Max data files: 10 opened at one time


Key file header format (first sector (512 bytes) of key file):

filetype char ; 0 file type, "K" or "O"
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
filler any ; 12 - 511 transient data


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)
filler any ; 12 - 31 transient data


Key format:

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.

02 00 00 KEY001 01 00 00 00 00 KEY002 02 00 00 00 00 ...
1. 2. 3. 4. 5. 6. 7. 8. 9.

1. Key count for that node
2. Back pointer (in this case there is no previous node)
3. The 6-byte ASCII key.
4. The 24-bit data record pointer (record 1)
5. Forward ptr to next node/back ptr to previous node of KEY002
6. The next key
7. Its data pointer
8. Forward pointer
9. unused space to end of sector


Data record format:

Straight data after the header.



QSAM3B.BAS, the I/O and interface portion of QSAM was written
and compiled with QuickBASIC 4.0. The QSAM3B.BAS file was
compiled with the /O option only. This means that it is
left to the programmer to ensure that adequate disk space
is available prior to writting. If worst comes to worst,
you can always get the source code and make any adjustments
that you like.

File I/O is performed by QB code called from QSAM. Storage
for the data buffers and headers are allocated in the
default data area of QB. QSAM3B.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 type variable for interfacing with QSAM low-level.

QSAM3A.ASM, the low-level, blood-and-guts of QSAM, was written
by Rick Grehan. The QB implementation was modified by me.
It is similar to Grehan's ZSAM however it does not use record
sets. I found ZSAM's multiple-record sets unreliable. Many
bench checks and runs where made but never successful. However,
the single-record code I have found to be bug-free except for
a typo; at PUTKS, he moves BP into ACKYSC. Should be AX.

-----------------------------------------------------------------
Tip: QSAM uses a simple variable, namely a var-len string,
to get and put data in the data file. To overcome this,
you may want to try this trick. 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))

MOVMEM VARPTR(whatit.whatis), SADD(thatit$)
'{or something similar since MOVMEM is not standard QuickBASIC}
'{now you have the TYPEd variable data in a var-len string that}
'{can be used as the Qrec$.}