
Description
===========

"WB" is a disk based (sorted) associative-array C library.  These
associative arrays consist of variable length (0 to 255 byte) keys and
values.  Functions are provided to:

   * create, destroy, open and close disk-files and associative arrays;

   * insert, delete, retrieve, find next, and find previous (with
     respect to dictionary order of keys); and

   * The atomic `put' and `rem' operations allow associations to be
     used for process mutexs.

   * apply functions, delete, or modify values over a range of
     consecutive key values.

The WB implementation has a file size limit of 2^32 * block size
(default 2048) = 2^43 bytes (8796 Gbytes).  WB routinely runs with
databases of several hundred Megabytes.  WB does its own memory and disk
management and maintains a RAM cache of recently used blocks.

Multiple associative arrays can reside in one disk file.  Simultaneous
access to multiple disk files is supported.  A structure checking and
garbage collecting program and a viewer are provided.  Compiled, WB
occupies approximately 66 kilobytes.

WB is implemented using a variant of B-tree structure.  B-trees give
slower access than hashing but are dynamic and provide an efficient
determination of successor and predecessor keys.  All operations are
O(log(n)) in the size of the database.  B-trees are commonly used by
database systems for implementing index structures.  B-trees are
optimized for using the minimum number of disk operations for large data
structures.  Prefix and suffix key compression are used for storage
efficiency in WB.


Copying
=======

  WB-tree File Based Associative String Data Base System.
  Copyright (c) 1991, 1992, 1993, 2000 Free Software Foundation, Inc.

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2, or (at your option)
  any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this software; see the file COPYING.  If not, write to
  the Free Software Foundation, 59 Temple Place, Suite 330, Boston, MA
  02111, USA.

  As a special exception, the Free Software Foundation gives permission
  for additional uses of the text contained in its release of GUILE.

  The exception is that, if you link the GUILE library with other files
  to produce an executable, this does not by itself cause the
  resulting executable to be covered by the GNU General Public License.
  Your use of that executable is in no way restricted on account of
  linking the GUILE library code into it.

  This exception does not however invalidate any other reasons why
  the executable file might be covered by the GNU General Public License.

  This exception applies only to the code released by the
  Free Software Foundation under the name GUILE.  If you copy
  code from other Free Software Foundation releases into a copy of
  GUILE, as the General Public License permits, the exception does
  not apply to the code that you add in this way.  To avoid misleading
  anyone as to the status of such modified files, you must delete
  this exception notice from them.

  If you write modifications of your own for GUILE, it is your choice
  whether to permit this exception to apply to your modifications.
  If you do not wish that, delete this exception notice.


Permissions
===========

           Copyright (C)  1991, 1992, 1993, 1996, 1999, 2000

                    Free Software Foundation, Inc.

           59 Temple Place, Suite 330, Boston, MA 02111, USA

Permission to use, copy, modify, distribute, and sell this software and
its documentation for any purpose is hereby granted without fee,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation.

                              NO WARRANTY

BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR
THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE
ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH
YOU.  SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL
NECESSARY SERVICING, REPAIR OR CORRECTION.

IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR
DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL
DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM
(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED
INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF
THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR
OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.


History
=======

The origination of B-trees is credited to [BM72] R. Bayer and E.
McCreight in 1972.

Working at Holland Mark Martin between 1991 and 1993, Roland Zito-Wolf,
Jonathan Finger, and Aubrey Jaffer wrote the "Wanna B-tree" system
described here.

Jonathan Finger wrote a MUMPS-like byte-coded interpreter "Sliced
Bread" using WB.  The integrated system was heavily used by Holland Mark
Martin for the rest of the decade.

WB's Authors are Aubrey Jaffer, Jonathan Finger, and Roland Zito-Wolf.
Please send bug-reports and enhancements to agj @ alum.mit.edu.


Organization
============

The primary C include file for using the WB layer is is <wbsys.h>,
which includes several other files from the directory.  <wbsys.h> also
defines WB's internal data types.

WB comes with a utility program for database files stored on disk.

 - Program: wbcheck path
     Checks the structure of the database named by PATH and reclaims
     temporary trees to the freelist.

WB source is translated from SCM to (K&R) C and TeXinfo by
<schlep.scm>.  <make.scm> coordinates the translations.  After
translation to C, the source is compiled with a native compiler for the
platform.


Manifest
--------

`wb.info'
     documents the theory, data formats, and algorithms; the C and SCM
     interfaces to WB-tree.

`ChangeLog'
     documents changes to the WB.

`example.scm'
     example program using WB-tree in SCM.

`defs.scm'
     SCM configuration code which gets compiled into defs.h.

`handle.scm'
`blink.scm'
`prev.scm'
`del.scm'
`ent.scm'
`scan.scm'
`stats.scm'
     SCM code for WB-trees which is compiled into C code with suffixes
     ".c" and ".h".

`blkio.scm'
     wimpy POSIX interface to the disk.  Replace this if you have a more
     direct interface to the disk.

`wbsys.h'
     The primary C include file for using the WB layer.

`wbsys.c'
     Shared data and low-level C accessors.

`wbsys.scm'
     Shared data and low-level accessors for debugging in SCM.

`db.c'
     C code for the SCM interface to WB-trees.

`db.scm'
     code for SCM interface when debugging in SCM.

`schlep.scm'
     SCM code which translates SCM code into C.

`schlep.typ'
     rules relating variable names to types in generated C.

`test.scm'
     file for testing WB-tree system.

`test2.scm'
     more tests for WB-tree system.

`Makefile'
     Unix makefile

`VMSBUILD.COM'
     command script for compiling under VMS.

`make.scm'
     SCM program for translating and compiling WB-tree system.

`all.scm'
     loads all the SCM files for debugging.

`wbtab.scm'
     SCM code allowing WB to implement SLIB relational databases.

`wbcheck.c'
     program for checking, repairing, and garbage collecting WB-tree
     databases.


Installation
============

WB unzips into a directory called `wb'.  If you plan to use WB with
SCM, the directories `scm' and `wb' should be in the same directory.

On VMS systems, the `VMSBUILD.COM' script will build wbcheck and db
(SCM).

For unix:

`make all'
     Compiles libwb, wbscm.so, and the wbcheck executable.

`make install'
     Installs libwb, wbscm.so, and wbcheck in the `$(prefix)' tree, as
     assigned in the `Makefile'.
