This is version 2 of a shareware implementation of Btree algorithms in Turbo C.
A memory overlap bug, not apparent if a small index is used, in the taunpack
function was removed. The other changes are cosmetic as well as to better
illustrate what info the user must provide to make use of these modules. An
extra sample program requiring different size index keys and data record
reinforces this. The implementation of these modules is patterned in the
fashion of Borland's Pascal 3.0 Btree and Nicklaus Wirth's excellent present-
ation in his book, Algorithm + Data Structure = Programs. The author herewith
authorizes any noncommercial use of this software for no fee and disclaims any
responsibility for any untoward consequences therefrom. The routines contained
herein have been extensively checked and have met the performance criteria
that they do what they are supposed to do. If any irregularity is found by
any user of this software, the author would appreciate being informed of same.

Author: Fook H. Eng
428-B South Ramona Ave.
Monterey Park, CA 91754 (818) 572-9220

The files prog1.mak and prog2.mak are my MAKE files for the sample programs,
PROG1 and PROG2. I simply compile the program by
make -fprog1 or make -fprog2
Of course, you must have the Turbo C executable files, include files,
and TURBOC.CFG in the proper directories on your system.

The syntax for running PROG1 and PROG2 are and
respectively, where filename is the database file name
without the extension .DAT. The seed is optional, used only for
initializing the random number generator. The database file does not have
to exist, but a name must be supplied.

A database file may exist alone without any index files. Both programs
will recognize this and provide a choice to reconstruct the index files.
CAUTION: Your database file itself will most likely be altered by
the reconstruction option. Make a backup copy first if you don't want this
to occur. The reason is that even if your database is corrupted to the
extent that 'deleted' records are misrecorded, the database can still be
salvaged, complete with holes in a correctly organized manner.

In running PROG1, if a database file does not exist, you will have the option
of generating the database by selecting 'CREATE' to rapidly, imaginatively,
and randomly create the database as you are presented with a dynamic view of
complete content of the pages of the btree index structure as each entry is
entered. It is educationally worthwhile to take a moment to study the candi-
date entry and try to predict what changes to which page will occur if you
indicate acceptance of the entry. You may also just as rapidly, though less
creatively, delete records from the database from the main menu by selecting
'DELETE'. Either of these tasks, however, you may perform more slowly by
choosing the 'UPDATE' option and then more specifically create or delete a
record. The educational aspect of each method is different, though.

The program file PROG2.EXE is merely a practical cardfile database to track
addresses and phone numbers. It is extremely rudimentary, leaving much room
for further development.

The 'LIST' option from the main menu provides three ways to list the database
a screenful at a time. If you have a large database, many screens of display
must elapse before you see what you may be interested in. The 'UPDATE'
option provides a 'FIND' suboption which in turn provide a 'LIST' suboption.
This latter option will list the database starting from the 'found' record
either in an customer name order or customer code order, depending on
whether the record was found by name or code. The list option is circular.
It will terminate when the whole database is listed once.

The 'EDIT' suboption under 'UPDATE' after a 'FIND' is performed permits
editing the found record. If the customer code is modified, it will be
check for validity as the customer code must be unique. The customer
data record will be deleted and added regardless of whether the editing
session produced any real changes or not. The index files will be modified
only if the associated index changed.

Your downloaded file BTREE.EXE self extracts to contain all the source codes
and header files. These codes adheres very closely to the algorithms of
Borland's Pascal v3.0 btree database toolkit and that of the aforementioned
Niklaus Wirth's book. Since you are reading this file, you have already run
BTREE.EXE. You should the following files:

Name Length Stowage SF Size now Date Time CRC
================= ======== ======== ==== ======== ========= ====== ====
ACCESS.C 8403 Crunched 59% 3497 17 Mar 89 11:00a e831
ACCESS.H 3737 Crunched 53% 1768 26 Feb 89 10:39p cdab
ADDKEY.C 4940 Crunched 57% 2145 17 Mar 89 11:00a b867
ADDKEY.H 429 Crunched 23% 332 8 Feb 89 10:22p 989a
BTREE.DOC 8716 Crunched 45% 4862 21 Mar 89 9:03p 42ec
CSTRUCT.H 2043 Crunched 54% 952 1 Feb 89 7:16p eb3a
DELKEY.C 8703 Crunched 63% 3266 17 Mar 89 11:01a 3c58
DELKEY.H 339 Crunched 17% 282 8 Feb 89 10:33p b929
GETKEY.C 6034 Crunched 62% 2302 17 Mar 89 11:01a dbc7
GETKEY.H 721 Crunched 40% 433 28 Feb 89 10:03a a8c4
GLOBALS.H 422 Crunched 35% 275 20 Mar 89 11:46p f91d
NAMES.H 6048 Crunched 56% 2678 3 Feb 89 10:12a 10c2
PROG1.C 2222 Crunched 48% 1172 16 Mar 89 3:25p 3ee8
PROG1.MAK 333 Crunched 28% 242 16 Mar 89 3:19p fc18
PROG1DAT.H 592 Crunched 49% 306 13 Mar 89 8:47a c131
PROG1INC.C 18449 Crunched 62% 7028 17 Mar 89 11:15a b711
PROG1INC.H 157 Crunched 20% 127 4 Feb 89 3:24p e8f4
PROG2.C 2007 Crunched 47% 1075 16 Mar 89 2:36p 0171
PROG2.MAK 362 Crunched 31% 250 16 Mar 89 2:32p 81e1
PROG2DAT.H 409 Crunched 41% 245 14 Mar 89 11:29a 71bd
PROG2INC.C 13154 Crunched 62% 5108 16 Mar 89 2:35p f743
PROG2INC.H 109 Crunched 2% 107 14 Mar 89 1:24p cd2e
UTIL.C 4624 Crunched 55% 2127 14 Mar 89 4:33p b418
UTIL.H 740 Crunched 45% 410 12 Mar 89 11:45p f859
==== ======== ==== ========
Total 24 93693 57% 40991

The library functions of BTREE.LIB are all prototyped in the header files
access.h, addkey.h, delkey.h, getkey.h, and util.h. These files are somewhat
commented to, hopefully, shed some light on its usages. If more thorough
insight is required, you may investigate the source code directly. The file
cstruct.h file divulges the nature of the data structures used and how they
are interlinked. The globals.h header specifies the global variables seen
by all those modules that "#include"s it. The files PROG1.C, PROG1INC.C, and
PROG1DAT.H in conjunction with the header files and BTREE.LIB are all that's
required to generate PROG1.EXE. Similarly, PROG2.C, PROG2INC.C, and
PROG2DAT.H together with the headers and BTREE.LIB are required to generate
PROG2.EXE.

The next task is for you to compile these source files to object codes by
tcc -c access addkey delkey getkey util
and then build the BTREE.LIB by
tlib btree +access +addkey +delkey +getkey +util
then you are ready to generate PROG1.EXE by
make -fprog1

Please use these programs freely and pass them on to your friends and BBSs.
If you find them enjoyable, useful, or in any fashion worthwhile, and if
you are so inclined, please send $20.00 to the author in order to become
a registered user for support and future updates to the source codes to
BTREE.LIB as they become available. More than just the measly sum of
$20.00, it establishes a sincere line of communication between me and
those of you who share with me the interest in developing an elegant and
efficient implementation database programs. By all means, study the codes,
learn from them, and give me your feedback as to how some features may be
more efficiently or elegantly implemented.

These program files are uploaded to Compuserve Borland's C program forum
in the year of the Snake, March 1989.