BaBiT - Documentation
Very simple implementation of balanced binary tree.
Features:
Pure C language - platform independent
No pointers (but offsets)
No recursion (except the consistency check function)
No hidden data-structures - join-record is nested into the user-record
All memory allocation/deallocation must be done by the user
Record-Record and Key-Record comparison functions must be written
by the user
User should:
* Read the header file (babit.h) and the attached example program
(babtest.c)
* Insert connector-record (BabitConnector) into her own record
* Write compare-functions: one for record-record comparison (BabitCmpFun)
and one for key-record comparison (BabitFndFun)
* Create struct BabitControlBlock which is required by all Babit function
calls
* Allocate and deallacte records - there are no "hidden" or "shadow"
structures
* Have a root for the tree (type BABIT_ROOT)
User can:
* Predefine offset type (BABIT_OFFSET) to long (default is int).
Recompile babit.c too!
* Predefine object type (BABITED_OBJECT) to her own record (default is
void). See the example in babit.h
* Predefine object key type (BABIT_KEY) to her own key type (default is
void).
BaBiT's functions:
* Initialize the root of the tree (BabitInit)
* Insert a new record to the tree (BabitInsert)
* Delete a record from the tree (BabitDelete)
* Replace a record with an other (with the same key!) (BabitReplace)
* Find a record by key (BabitFind)
* Find a record around the specified key (BabitFindEx). See babit.h and
babtest.c for details!
* Get the minimum/maximum/middle element of the tree (BabitGetMin)
* Get the previous/next element of tree (BabitGetNext)
* Walk the tree pre/in/postorder (BabitWalk)
* Check the consistency of the tree (BabitCheck)
Changes
* Version 1.6: BabitFindEx now works correctly, test routine added to
babtest.c (BabitFindExTest).
