Merge branch 'newcache': Bucket cache rewritten from scratch.

23 files changed, 1496 insertions, 584 deletions

diff --git a/NEWS b/NEWS
index aad8e49..fe36106 100644
--- a/NEWS
+++ b/NEWS
@@ -1,8 +1,18 @@
-GNU dbm NEWS -- history of user-visible changes. 2020-12-23
+GNU dbm NEWS -- history of user-visible changes. 2021-03-21
+Copyright (C) 1990-2021 Free Software Foundation, Inc.
 See the end of file for copying conditions.
 
 Please send gdbm bug reports to <bug-gdbm@gnu.org>.
 
+Version 1.19.90 (git)
+
+* New bucket cache
+
+The bucket cache support has been rewritten from scratch.  The new
+bucket cache code provides for significant speed up of search
+operations.
+
+
 Version 1.19 - 2020-12-23
 
 * Pre-read the memory mapped regions on systems that support it.
diff --git a/README b/README
index 48a2f5d..cfac716 100644
--- a/README
+++ b/README
@@ -1,6 +1,12 @@
 GNU dbm README
 See the end of file for copying conditions.
 
+* Note
+
+This is an experimental branch of GNU DBM.  Its goal is to evaluate
+possibilities of improving the caching scheme.  Please don't use it
+in production.
+
 * Introduction
 
 This file contains brief information about configuring, testing
diff --git a/configure.ac b/configure.ac
index 4d956d9..7abd0bc 100644
--- a/configure.ac
+++ b/configure.ac
@@ -16,7 +16,7 @@
 
 m4_define([_GDBM_VERSION_MAJOR], 1)
 m4_define([_GDBM_VERSION_MINOR], 19)
-m4_dnl m4_define([_GDBM_VERSION_PATCH], 0)
+m4_define([_GDBM_VERSION_PATCH], 90)
 
 AC_INIT([gdbm],
         _GDBM_VERSION_MAJOR._GDBM_VERSION_MINOR[]m4_ifdef([_GDBM_VERSION_PATCH],._GDBM_VERSION_PATCH),
diff --git a/doc/fdl.texi b/doc/fdl.texi
index c6c9d40..d0ff5f2 100644
--- a/doc/fdl.texi
+++ b/doc/fdl.texi
@@ -5,7 +5,7 @@
 @c hence no sectioning command or @node.
 
 @display
-Copyright @copyright{} 2000-2002, 2007-2008, 2011, 2017-2020 Free
+Copyright @copyright{} 2000-2002, 2007-2008, 2011, 2017-2021 Free
 Software Foundation, Inc.
 @uref{http://fsf.org/}
 
diff --git a/doc/gdbm.3 b/doc/gdbm.3
index 6525112..cfef634 100644
--- a/doc/gdbm.3
+++ b/doc/gdbm.3
@@ -13,7 +13,7 @@
 .\"
 .\" You should have received a copy of the GNU General Public License
 .\" along with GDBM. If not, see <http://www.gnu.org/licenses/>. */
-.TH GDBM 3 "January 27, 2020" "GDBM" "GDBM User Reference"
+.TH GDBM 3 "March 21, 2021" "GDBM" "GDBM User Reference"
 .SH NAME
 GDBM \- The GNU database manager.  Includes \fBdbm\fR and \fBndbm\fR
 compatibility.
@@ -33,28 +33,35 @@ compatibility.
 .br
 .BI "int gdbm_close (GDBM_FILE " dbf ");"
 .br
-.BI "int gdbm_store (GDBM_FILE " dbf ", datum " key ", datum " content ", int " flag );
+.BI "int gdbm_store (GDBM_FILE " dbf ", datum " key ", datum " content ", int " flag ");"
 .br
-.BI "datum gdbm_fetch (GDBM_FILE " dbf ", datum " key );
+.BI "datum gdbm_fetch (GDBM_FILE " dbf ", datum " key ");"
 .br
-.BI "int gdbm_delete (GDBM_FILE " dbf ", datum " key );
+.BI "int gdbm_delete (GDBM_FILE " dbf ", datum " key ");"
 .br
 .BI "datum gdbm_firstkey (GDBM_FILE " dbf ");"
 .br
-.BI "datum gdbm_nextkey (GDBM_FILE " dbf ", datum " key );
+.BI "datum gdbm_nextkey (GDBM_FILE " dbf ", datum " key ");"
+.br
+.BI "int gdbm_recover (GDBM_FILE " dbf ", gdbm_recovery *" rcvr ", int" flags ");"
 .br
 .BI "int gdbm_reorganize (GDBM_FILE " dbf ");"
 .br
 .BI "int gdbm_sync (GDBM_FILE " dbf ");"
 .br
-.BI "int gdbm_exists (GDBM_FILE " dbf ", datum " key );
+.BI "int gdbm_exists (GDBM_FILE " dbf ", datum " key ");"
 .br
-.BI "const char *gdbm_strerror (gdbm_error " errno );
+.BI "const char *gdbm_strerror (gdbm_error " errno ");"
 .br
 .BI "int gdbm_setopt (GDBM_FILE " dbf ", int " option ", int " value ", int " size );
 .br
 .BI "int gdbm_fdesc (GDBM_FILE " dbf );
 .br
+.BI "int gdbm_count (GDBM_FILE " dbf ", gdbm_count_t *" pcount ");"
+.br
+.BI "int gdbm_bucket_count (GDBM_FILE " dbf ", size_t *" pcount ");"
+.br
+.BI "int gdbm_avail_verify (GDBM_FILE " dbf ");"
 .PP
 .SS DBM Compatibility routines:
 .PP
@@ -161,6 +168,15 @@ Causes all database operations to be synchronized to the disk,
 .TP
 .B GDBM_NOLOCK
 Prevents the library from performing any locking on the database file.
+.TP
+.B GDBM_CLOEXEC
+Set the close-on-exec flag on the database file descriptor.
+.TP
+.B GDBM_XVERIFY
+Enable additional consistency checks.  With this flag, eventual
+corruptions of the database are discovered when opening it, instead of
+when a corrupted structure is read during normal operation.  However,
+on large databases, it can slow down the opening process.
 .PP
 The option
 .B GDBM_FAST
@@ -327,9 +343,13 @@ and \fIoption\fR specifies which option to set.  The valid options are
 currently:
 .TP
 .B GDBM_CACHESIZE
-Set the size of the internal bucket cache. This option may only be set once
-on each \fIGDBM_FILE\fR descriptor, and is set automatically to 100 upon the
-first access to the database.
+Set the size of the internal bucket cache.  By default, the cache size
+is selected to provide for the optimal performance.  Use this option,
+if you wish to limit the memory usage at the expense of performance.
+.sp
+Use the
+.B GDBM_CACHE_AUTO
+constant to return to the default.
 .TP
 .B GDBM_FASTMODE
  Set \fBfast mode\fR to either on or off.  This allows \fBfast mode\fR to
diff --git a/doc/gdbm.texi b/doc/gdbm.texi
index 81765a1..5f42ced 100644
--- a/doc/gdbm.texi
+++ b/doc/gdbm.texi
@@ -68,7 +68,7 @@ Documentation License.''
 @sp 1
 @center Edition @value{EDITION}
 @sp 1
-@center for GNU @code{dbm}, Version @value{VERSION}
+@center for GNU @command{dbm}, Version @value{VERSION}
 @page
 @vskip 0pt plus 1filll
 @insertcopying
@@ -85,8 +85,8 @@ Documentation License.''
 @node Top
 @top The GNU database manager.
 
-GNU @code{dbm} is a library of functions implementing a hashed database
-on a disk file.  This manual documents GNU @code{dbm} Version @value{VERSION}
+GNU @command{dbm} is a library of functions implementing a hashed database
+on a disk file.  This manual documents GNU @command{dbm} Version @value{VERSION}
 (@code{gdbm}).  The software was originally written by Philip A.@:
 Nelson.  This document was originally written by Pierre Gaumond from
 texts written by Phil.
@@ -115,7 +115,7 @@ Functions:
 * Options::                    Setting internal options.
 * Locking::                    File locking.
 * Variables::                  Useful global variables.
-
+* Additional functions::
 * Error codes::                Error codes returned by @code{gdbm} calls.
 * Compatibility::              Compatibility with UNIX dbm and ndbm.
 
@@ -143,8 +143,8 @@ Other topics:
 @node Copying
 @chapter Copying Conditions.
 This library is @dfn{free}; this means that everyone is free to use
-it and free to redistribute it on a free basis.  GNU @code{dbm} (@code{gdbm})
-is not in the public domain; it is copyrighted and there
+it and free to redistribute it on a free basis.  GNU @command{dbm}
+(@code{gdbm}) is not in the public domain; it is copyrighted and there
 are restrictions on its distribution, but these restrictions are
 designed to permit everything that a good cooperating citizen would want
 to do.  What is not allowed is to try to prevent others from further
@@ -176,10 +176,10 @@ Public License.)  A copy the GNU General Public License is included with
 the distribution of @code{gdbm}.
 
 @node Intro
-@chapter Introduction to GNU @code{dbm}.
+@chapter Introduction to GNU @command{dbm}.
 
-GNU @code{dbm} (@code{gdbm}) is a library of database functions that use
-extensible hashing and works similar to the standard UNIX @code{dbm}
+GNU @command{dbm} (@code{gdbm}) is a library of database functions that use
+extensible hashing and works similar to the standard UNIX @command{dbm}
 functions.  These routines are provided to a programmer needing to
 create and manipulate a hashed database. (@code{gdbm} is @emph{NOT} a
 complete database package for an end user.)
@@ -344,7 +344,7 @@ no such key
 @cindex opening the database
 @cindex database, opening or creating
 @deftypefn {gdbm interface} GDBM_FILE gdbm_open (const char *@var{name}, int @var{block_size}, @
-  int @var{flags}, int @var{mode}, void (*fatal_func)(const char *))
+  int @var{flags}, int @var{mode}, void (*@var{fatal_func})(const char *))
 Initializes @code{gdbm} system.  If the file has a size of zero bytes, a file
 initialization procedure is performed, setting up the initial structure in the
 file.
@@ -363,61 +363,91 @@ initialized.  If the value is less than 512, the file system block
 size is used instead.  The size is adjusted so that the block can hold
 exact number of directory entries, so that the effective block size
 can be slightly greater than requested.  However, if the 
-@samp{GDBM_BSEXACT} flag is set and the size needs to be adjusted, the
-function will return with error status, setting the @samp{gdbm_errno}
-variable to @samp{GDBM_BLOCK_SIZE_ERROR}.
+@code{GDBM_BSEXACT} flag is set and the size needs to be adjusted, the
+function will return with error status, setting the @code{gdbm_errno}
+variable to @code{GDBM_BLOCK_SIZE_ERROR}.
 
 @item flags
 @kwindex GDBM_READER
 @kwindex GDBM_WRITER
 @kwindex GDBM_WRCREAT
 @kwindex GDBM_NEWDB
-If @code{flags} is set to @samp{GDBM_READER}, the user wants to just read the
+If @code{flags} is set to @code{GDBM_READER}, the user wants to just read the
 database and any call to @code{gdbm_store} or @code{gdbm_delete} will fail.
 Many readers can access the database at the same time.  If @code{flags} is
-set to @samp{GDBM_WRITER}, the user wants both read and write access
+set to @code{GDBM_WRITER}, the user wants both read and write access
 to the database and requires exclusive access.  If @code{flags} is set
-to @samp{GDBM_WRCREAT}, the user wants both read and write access to
+to @code{GDBM_WRCREAT}, the user wants both read and write access to
 the database and wants it created if it does not already exist.  If
-@code{flags} is set to @samp{GDBM_NEWDB}, the user want a new database
+@code{flags} is set to @code{GDBM_NEWDB}, the user want a new database
 created, regardless of whether one existed, and wants read and write
 access to the new database.
 
 @kwindex GDBM_SYNC
 @kwindex GDBM_NOLOCK
 @kwindex GDBM_NOMMAP
-The following may also be logically or'd into the database flags:
-@samp{GDBM_SYNC}, which causes all database operations to be
-synchronized to the disk, @samp{GDBM_NOLOCK}, which prevents the library 
-from performing any locking on the database file, and @samp{GDBM_NOMMAP},
-which disables the memory mapping mechanism.  The option @samp{GDBM_FAST} is
-now obsolete, since @code{gdbm} defaults to no-sync mode.
+The following constants may also be logically or'd into the database
+flags:
+
+@table @code
+@kwindex GDBM_SYNC
+@item GDBM_SYNC
+Synchronize all database operations to disk immediately.  This
+provides for the best database consistency at the expense of severe
+performance degradation.
+
+@kwindex GDBM_FAST
+@item GDBM_FAST
+A reverse of @code{GDBM_SYNC}.  Synchronize writes only when needed.
+This is the default.  The flag is provided for compatibility with
+previous versions of @command{GDBM}.
+
+@kwindex GDBM_NOLOCK
+@item GDBM_NOLOCK
+Don't lock the database file.  Use this flag if you intend to do
+locking separately.
+
+@kwindex GDBM_NOMMAP
+@item GDBM_NOMMAP
+Disable memory mapping mechanism.  This degrades performance.
 
 @kwindex GDBM_BSEXACT
+@item GDBM_BSEXACT
 If this flag is set and the requested @var{block_size} cannot be used
 without adjustment, @code{gdbm_open} will refuse to create the
-databases.  In this case it will set the @samp{gdbm_errno}
-variable to @samp{GDBM_BLOCK_SIZE_ERROR} and return @samp{NULL}.
+databases.  In this case it will set the @code{gdbm_errno}
+variable to @code{GDBM_BLOCK_SIZE_ERROR} and return @code{NULL}.
 
 @kwindex GDBM_CLOEXEC
 @cindex close-on-exec
-If the host @samp{open} call
+@item GDBM_CLOEXEC
+Set the close-on-exec flag on the database file descriptor.  The
+@code{libc} must support the @code{O_CLOEXEC} flag@footnote{
 @ifhtml
 (@uref{http://www.manpagez.com/man/2/open, open(2)})
 @end ifhtml
 @ifnothtml
-(@pxref{open,,,open(2),open(2) man page})
+@xref{open,,,open(2),open(2) man page}
 @end ifnothtml
-supports the @samp{O_CLOEXEC} flag, the @samp{GDBM_CLOEXEC} can be
-or'd into the flags, to enable the close-on-exec flag for the
-database file descriptor.
+}
+
+@kwindex GDBM_XVERIFY
+@item GDBM_XVERIFY
+Enable additional consistency checks.  With this flag, eventual
+corruptions of the database are discovered when opening it, instead of
+when a corrupted structure is read during normal operation.  However,
+on large databases, it can slow down the opening process.
+
+@xref{Additional functions}.
+@end table
+
 @item mode
-File mode (see
+File mode@footnote{See
 @ifhtml
 @uref{http://www.manpagez.com/man/2/chmod, chmod(2)},
 @end ifhtml
 @ifnothtml
-@ref{chmod,,change permissions of a file,chmod(2),
+@xref{chmod,,change permissions of a file,chmod(2),
 chmod(2) man page},
 @end ifnothtml
 and
@@ -425,17 +455,17 @@ and
 @uref{http://www.manpagez.com/man/2/open, open(2)}),
 @end ifhtml
 @ifnothtml
-@pxref{open,,open a file,open(2), open(2) man page}),
+@ref{open,,open a file,open(2), open(2) man page}.},
 @end ifnothtml
-which is used if the file is created).
+which is used if the file is created.
 @item fatal_func
 A function for @code{gdbm} to call if it detects a fatal error.  The only
-parameter of this function is a string.  If the value of @samp{NULL} is
+parameter of this function is a string.  If the value of @code{NULL} is
 provided, @code{gdbm} will use a default function.
 @end table
 
 The return value, is the pointer needed by all other functions to
-access that @code{gdbm} file.  If the return is the @samp{NULL} pointer,
+access that @code{gdbm} file.  If the return is the @code{NULL} pointer,
 @code{gdbm_open} was not successful.  The errors can be found in
 @code{gdbm_errno} variable (@pxref{Variables, gdbm_errno}).  Available
 error codes are discussed in @ref{Error codes}.
@@ -446,7 +476,7 @@ returned from @code{gdbm_open}.
 
 @deftypefn {gdbm interface} GDBM_FILE gdbm_fd_open (int @var{fd},@
   const char *@var{name}, int @var{block_size}, @
-  int @var{flags}, int @var{mode}, void (*fatal_func)(const char *))
+  int @var{flags}, int @var{mode}, void (*@var{fatal_func})(const char *))
 
 Alternative function for opening a GDBM database.  The @var{fd}
 argument is the file descriptor of the database file obtained by a
@@ -493,6 +523,14 @@ stores it in the memory location pointed to by @var{pcount} and returns
 and returns -1.
 @end deftypefn
 
+@deftypefn {gdbm interface} int gdbm_bucket_count (GDBM_FILE @var{dbf}, @
+  size_t *@var{pcount})
+Counts number of buckets in the database @var{dbf}.  On success,
+stores it in the memory location pointed to by @var{pcount} and return
+0.  On error, sets @code{gdbm_errno} (if relevant, also @code{errno})
+and returns -1.
+@end deftypefn
+
 @node Store
 @chapter Inserting and replacing records in the database.
 @cindex storing records
@@ -515,8 +553,8 @@ The data to be associated with the key.
 @kwindex GDBM_REPLACE
 @kwindex GDBM_INSERT
 Defines the action to take when the key is already in the database.  The value
-@samp{GDBM_REPLACE} (defined in @file{gdbm.h}) asks that the old data
-be replaced by the new @var{content}.  The value @samp{GDBM_INSERT}
+@code{GDBM_REPLACE} (defined in @file{gdbm.h}) asks that the old data
+be replaced by the new @var{content}.  The value @code{GDBM_INSERT}
 asks that an error be returned and no action taken if the @var{key}
 already exists.
 @end table
@@ -530,20 +568,20 @@ database.
 @item -1
 The item was not stored in the database because the caller was not an
 official writer or either @var{key} or @var{content} have a
-@samp{NULL} @samp{dptr} field.
+@code{NULL} @code{dptr} field.
 
-Both @var{key} and @var{content} must have the @samp{dptr} field be a
-non-@samp{NULL} value.  Since a @samp{NULL} @samp{dptr} field is used by
+Both @var{key} and @var{content} must have the @code{dptr} field be a
+non-@code{NULL} value.  Since a @code{NULL} @code{dptr} field is used by
 other functions to indicate an error, it cannot be valid data.
 @item +1
 The item was not stored because the argument @var{flag} was
-@samp{GDBM_INSERT} and the @var{key} was already in the database.
+@code{GDBM_INSERT} and the @var{key} was already in the database.
 @end table
 @end deftypefn
 
 If you store data for a @var{key} that is already in the data base,
 @code{gdbm} replaces the old data with the new data if called with
-@samp{GDBM_REPLACE}.  You do not get two data items for the same
+@code{GDBM_REPLACE}.  You do not get two data items for the same
 @code{key} and you do not get an error from @code{gdbm_store}.
 
 The size of datum in @code{gdbm} is restricted only by the maximum
@@ -558,13 +596,13 @@ value for an object of type @code{int} (type of the @code{dsize} member of
 
 @deftypefn {gdbm interface} datum gdbm_fetch (GDBM_FILE @var{dbf}, datum @var{key})
 Looks up a given @var{key} and returns the information associated with it.
-The @samp{dptr} field in the structure that is returned points to a
+The @code{dptr} field in the structure that is returned points to a
 memory block allocated by @code{malloc}.  It is the caller's
 responsibility to free it when no longer needed.
 
-If the @samp{dptr} is @samp{NULL}, inspect the value of the
+If the @code{dptr} is @code{NULL}, inspect the value of the
 @code{gdbm_errno} variable (@pxref{Variables,gdbm_errno}).  If it is
-@samp{GDBM_ITEM_NOT_FOUND}, no data was found.  Any other value means an
+@code{GDBM_ITEM_NOT_FOUND}, no data was found.  Any other value means an
 error occurred.  Use @code{gdbm_strerror} function to convert
 @code{gdbm_errno} to a human-readable string.
 
@@ -598,12 +636,12 @@ You may also search for a particular key without retrieving it:
 @deftypefn {gdbm interface} int gdbm_exists (GDBM_FILE @var{dbf}, datum @var{key})
 Checks whether the @var{key} exists in the database @var{dbf}.
 
-If @var{key} is found, returns @samp{true} (@samp{1}).  If it is not
-found, returns @samp{false} (@samp{0}) and sets @code{gdbm_errno} to
-@samp{GDBM_NO_ERROR} (@samp{0}).
+If @var{key} is found, returns @code{true} (@code{1}).  If it is not
+found, returns @code{false} (@code{0}) and sets @code{gdbm_errno} to
+@code{GDBM_NO_ERROR} (@code{0}).
 
-On error, returns @samp{0} and sets @code{gdbm_errno} to a
-non-@samp{0} error code.
+On error, returns @code{0} and sets @code{gdbm_errno} to a
+non-@code{0} error code.
 
 The parameters are:
 
@@ -636,8 +674,8 @@ The pointer returned by @code{gdbm_open}.
 The search key.
 @end table
 
-The function returns @samp{-1} if the item is not present or the
-requester is a reader.  The return of @samp{0} marks a successful delete.
+The function returns @code{-1} if the item is not present or the
+requester is a reader.  The return of @code{0} marks a successful delete.
 @end deftypefn
 
 @node Sequential
@@ -655,13 +693,13 @@ access is not @code{key} sequential, but it is guaranteed to visit every
 
 @deftypefn {gdbm interface} datum gdbm_firstkey (GDBM_FILE @var{dbf})
 Initiate sequential access to the database @var{dbf}.  The returned
-value is the first key accessed in the database.  If the @samp{dptr}
-field in the returned datum is @samp{NULL}, inspect the
+value is the first key accessed in the database.  If the @code{dptr}
+field in the returned datum is @code{NULL}, inspect the
 @code{gdbm_errno} variable (@pxref{Variables, gdbm_errno}).  The value
 of @code{GDBM_ITEM_NOT_FOUND} means that the database contains no
 data.  Other value means an error occurred.
 
-On success, @samp{dptr} points to a memory block obtained from
+On success, @code{dptr} points to a memory block obtained from
 @code{malloc}, which holds the key value.  The caller is responsible
 for freeing this memory block when no longer needed.
 @end deftypefn
@@ -672,13 +710,13 @@ initiated by @code{gdbm_firstkey}.  The parameter @var{prev} holds the
 value returned from a previous call to @code{gdbm_nextkey} or
 @code{gdbm_firstkey}.
 
-The function returns next key from the database.  If the @samp{dptr}
-field in the returned datum is @samp{NULL} inspect the
+The function returns next key from the database.  If the @code{dptr}
+field in the returned datum is @code{NULL} inspect the
 @code{gdbm_errno} variable (@pxref{Variables, gdbm_errno}).  The value
 of @code{GDBM_ITEM_NOT_FOUND} means that all keys in the database
 has been visited.  Any other value means an error occurred.
 
-Otherwise, @samp{dptr} points to a memory block obtained from
+Otherwise, @code{dptr} points to a memory block obtained from
 @code{malloc}, which holds the key value.  The caller is responsible
 for freeing this memory block when no longer needed.
 @end deftypefn
@@ -772,7 +810,7 @@ reorganization.
 @cindex synchronization, database
 
 @kwindex GDBM_SYNC
-Unless your database was opened with the @samp{GDBM_SYNC} flag,
+Unless your database was opened with the @code{GDBM_SYNC} flag,
 @code{gdbm} does not wait for writes to be flushed to the disk before
 continuing.  This allows for faster writing of databases at the risk
 of having a corrupted database if the application terminates in an
@@ -857,16 +895,16 @@ A pointer to the source database, returned by a prior call to
 Name of the dump file.
 
 @item format
-Output file format.  Allowed values are: @samp{GDBM_DUMP_FMT_BINARY} to
-create a binary dump and @samp{GDBM_DUMP_FMT_ASCII} to create an ASCII
+Output file format.  Allowed values are: @code{GDBM_DUMP_FMT_BINARY} to
+create a binary dump and @code{GDBM_DUMP_FMT_ASCII} to create an ASCII
 dump file.
 
 @item open_flags
-How to create the output file.  If @var{flag} is @samp{GDBM_WRCREAT}
+How to create the output file.  If @var{flag} is @code{GDBM_WRCREAT}
 the file will be created if it does not exist.  If it does exist,
 the @code{gdbm_dump} will fail.
 
-If @var{flag} is @samp{GDBM_NEWDB}, the function will create a new
+If @var{flag} is @code{GDBM_NEWDB}, the function will create a new
 output file, replacing it if it already exists.
 
 @item mode
@@ -887,13 +925,13 @@ for a detailed discussion.
     int @var{meta_mask}, @
     unsigned long *@var{errline})
 Loads data from the dump file @var{filename} into the database pointed
-to by @var{pdbf}.  The latter can point to @samp{NULL}, in which case 
+to by @var{pdbf}.  The latter can point to @code{NULL}, in which case 
 the function will try to create a new database.  If it succeeds, the
 function will return, in the memory location pointed to by @var{pdbf},
 a pointer to the newly created database.  If the dump file carries no 
 information about the original database file name, the function will
-set @code{gdbm_errno} to @samp{GDBM_NO_DBNAME} and return
-@samp{-1}, indicating failure.
+set @code{gdbm_errno} to @code{GDBM_NO_DBNAME} and return
+@code{-1}, indicating failure.
 
 The @var{flag} has the same meaning as the @var{flag} argument
 to the @code{gdbm_store} function (@pxref{Store}).
@@ -935,7 +973,7 @@ Input contained some illegal data.
 This error can occur only when the input file is in ASCII format.  It
 indicates that the data part of the record about to be read lacked
 length specification.  Application developers are advised to treat
-this error equally as @samp{GDBM_ILLEGAL_DATA}.
+this error equally as @code{GDBM_ILLEGAL_DATA}.
 @end table
 
 Mild errors mean that the function was able to successfully load and
@@ -956,10 +994,10 @@ The function was unable to restore database file mode (permission bits).
 If an error occurs while loading data from an input file in ASCII
 format, the number of line in which the error occurred will be stored
 in the location pointed to by the @var{errline} parameter, unless it
-is @samp{NULL}.
+is @code{NULL}.
 
 If the line information is not available or applicable, @var{errline}
-will be set to @samp{0}.
+will be set to @code{0}.
 @end deftypefn
 
 @deftypefn {gdbm interface} int gdbm_dump_to_file (GDBM_FILE @var{dbf}, @
@@ -1082,6 +1120,10 @@ code.  The following are the ones that have:
 @item GDBM_FILE_READ_ERROR
 @item GDBM_FILE_STAT_ERROR
 @item GDBM_BACKUP_FAILED
+@item GDBM_BACKUP_FAILED
+@item GDBM_FILE_CLOSE_ERROR
+@item GDBM_FILE_SYNC_ERROR
+@item GDBM_FILE_TRUNCATE_ERROR
 @end itemize
 
 For other errors, @code{gdbm_last_syserr} will return 0.
@@ -1089,7 +1131,7 @@ For other errors, @code{gdbm_last_syserr} will return 0.
 
 @anchor{gdbm_check_syserr}
 @deftypefn {gdbm interface} {int} gdbm_check_syserr (gdbm_errno @var{err})
-Returns @code{1}, if system errno value should be checked to get more
+Returns @code{1}, if system @code{errno} value should be checked to get more
 info on the error described by GDBM code @var{err}.
 @end deftypefn
 
@@ -1100,7 +1142,7 @@ particular database file, use the @code{gdbm_db_strerror} function:
 Returns textual description of the most recent error encountered when
 operating on the database @var{dbf}.  The resulting string is often
 more informative than what would be returned by
-@samp{gdbm_strerror(gdbm_last_errno(@var{dbf}))}.  In particular, if
+@code{gdbm_strerror(gdbm_last_errno(@var{dbf}))}.  In particular, if
 there is a system error associated with the recent failure, it will be
 described as well.
 @end deftypefn
@@ -1283,7 +1325,7 @@ place the option value (depending on the option).
 The length of the data pointed to by @var{value}.
 @end table
 
-The return value will be @samp{-1} upon failure, or @samp{0} upon
+The return value will be @code{-1} upon failure, or @code{0} upon
 success.  The global variable @code{gdbm_errno} will be set upon failure.
 @end deftypefn
 
@@ -1294,23 +1336,33 @@ The valid options are:
 @kwindex GDBM_SETCACHESIZE
 @item GDBM_SETCACHESIZE
 @itemx GDBM_CACHESIZE
-Set the size of the internal bucket cache.  This option may only be
-set once on each GDBM_FILE descriptor, and is set automatically to 100
-upon the first access to the database.  The @var{value} should point
-to a @code{size_t} holding the desired cache size.
+@kwindex GDBM_CACHE_AUTO
+Set the size of the internal bucket cache.  The @var{value} should
+point to a @code{size_t} holding the desired cache size, or the
+constant @code{GDBM_CACHE_AUTO}, to set the best cache size
+automatically.
+
+By default, a newly open database is configured to adapt the cache
+size to the number of index buckets in the database file.  This
+provides for the best performance.
+
+Use this option if you wish to limit the memory usage at the expense
+of performance.  If you chose to do so, please bear in mind that cache
+becomes effective when its size is greater then 2/3 of the number of
+index bucket counts in the database.  The best performance results are
+achieved when cache size equals the number of buckets.  For example:
 
-The @samp{GDBM_CACHESIZE} option is provided for compatibility with
-earlier versions.
+@example
+size_t bn;
+gdbm_bucket_count (dbf, &bn);
+ret = gdbm_setopt (dbf, GDBM_SETCACHESIZE, &bn, sizeof (bn));
+@end example
 
-For instance, to set a database to use a cache of 10, after opening it
-with @code{gdbm_open}, but prior to accessing it in any way, the following
-code could be used:
+To set the best cache size, use the constant @code{GDBM_CACHE_AUTO}:
 
 @example
-@group
-int value = 10;
-ret = gdbm_setopt (dbf, GDBM_SETCACHESIZE, &value, sizeof (int));
-@end group
+size_t bn = GDBM_CACHE_AUTO;
+ret = gdbm_setopt (dbf, GDBM_SETCACHESIZE, &bn, sizeof (bn));
 @end example
 
 @kwindex GDBM_GETCACHESIZE
@@ -1330,7 +1382,7 @@ its value will be similar to the flags used when opening the database
 @item GDBM_FASTMODE
 Enable or disable the @dfn{fast writes mode}, i.e.@: writes without
 subsequent synchronization.  The @var{value} should point
-to an integer: @samp{TRUE} to enable fast mode, and @samp{FALSE} to
+to an integer: @code{TRUE} to enable fast mode, and @code{FALSE} to
 disable it.
 
 This option is retained for compatibility with previous versions of
@@ -1343,14 +1395,14 @@ This option is retained for compatibility with previous versions of
 @itemx GDBM_SYNCMODE
 Turn on or off file system synchronization operations.  This
 setting defaults to off.  The @var{value} should point
-to an integer: @samp{TRUE} to turn synchronization on, and @samp{FALSE} to
+to an integer: @code{TRUE} to turn synchronization on, and @code{FALSE} to
 turn it off.
 
 Note, that this option is a reverse of @code{GDBM_FASTMODE},
-i.e.@: calling @code{GDBM_SETSYNCMODE} with @samp{TRUE} has the same effect
-as calling @code{GDBM_FASTMODE} with @samp{FALSE}.
+i.e.@: calling @code{GDBM_SETSYNCMODE} with @code{TRUE} has the same effect
+as calling @code{GDBM_FASTMODE} with @code{FALSE}.
 
-The @samp{GDBM_SYNCMODE} option is provided for compatibility with
+The @code{GDBM_SYNCMODE} option is provided for compatibility with
 earlier versions.
 
 @kwindex GDBM_GETSYNCMODE
@@ -1368,10 +1420,10 @@ Set central free block pool to either on or off.  The default is off,
 which is how previous versions of @code{gdbm} handled free blocks.  If
 set, this option causes all subsequent free blocks to be placed in the
 @emph{global} pool, allowing (in theory) more file space to be reused
-more quickly.  The @var{value} should point to an integer: @samp{TRUE} to
-turn central block pool on, and @samp{FALSE} to turn it off.
+more quickly.  The @var{value} should point to an integer: @code{TRUE} to
+turn central block pool on, and @code{FALSE} to turn it off.
 
-The @samp{GDBM_CENTFREE} option is provided for compatibility with
+The @code{GDBM_CENTFREE} option is provided for compatibility with
 earlier versions.
 
 @kwindex GDBM_SETCOALESCEBLKS
@@ -1385,7 +1437,7 @@ is how previous versions of @code{gdbm} handled free blocks.  If set,
 this option causes adjacent free blocks to be merged.  This can become
 a @acronym{CPU} expensive process with time, though, especially if
 used in conjunction with GDBM_CENTFREE.  The @var{value} should point
-to an integer: @samp{TRUE} to turn free block merging on, and @samp{FALSE} to
+to an integer: @code{TRUE} to turn free block merging on, and @code{FALSE} to
 turn it off.
 
 @kwindex GDBM_GETCOALESCEBLKS
@@ -1409,7 +1461,7 @@ point to a value of type @code{size_t} where to return the data.
 @kwindex GDBM_SETMMAP
 @item GDBM_SETMMAP
 Enable or disable memory mapping mode.  The @var{value} should point
-to an integer: @samp{TRUE} to enable memory mapping or @samp{FALSE} to
+to an integer: @code{TRUE} to enable memory mapping or @code{FALSE} to
 disable it.
 
 @kwindex GDBM_GETMMAP
@@ -1451,7 +1503,7 @@ Return the block size in bytes.  The @var{value} should point to @code{int}.
 @cindex locking
 
 @kwindex GDBM_NOLOCK
-With locking disabled (if @code{gdbm_open} was called with @samp{GDBM_NOLOCK}),
+With locking disabled (if @code{gdbm_open} was called with @code{GDBM_NOLOCK}),
 the user may want to perform their own file locking on the database file
 in order to prevent multiple writers operating on the same file
 simultaneously.
@@ -1540,8 +1592,8 @@ To compare two split-out version numbers, use the following function:
 
 @deftypefn {gdbm interface} int gdbm_version_cmp (int const @var{a}[3], @
                                                   int const @var{b}[3])
-Compare two version numbers.  Return @samp{-1} if @var{a} is less than
-@var{b}, @samp{1} if @var{a} is greater than @var{b} and @samp{0} if
+Compare two version numbers.  Return @code{-1} if @var{a} is less than
+@var{b}, @code{1} if @var{a} is greater than @var{b} and @code{0} if
 they are equal.
 
 Comparison is done from left to right, so that:
@@ -1561,6 +1613,16 @@ gdbm_version_cmp (a, b) @result{} -1
 @end example
 @end deftypefn
 
+@node Additional functions
+@chapter Additional functions
+
+@deftypefn {gdbm interface} int gdbm_avail_verify (GDBM_FILE @var{dbf})
+Verify if the available block stack is in consistent state.  On
+success, returns 0.  If any errors are encountered, sets the
+@code{gdbm_errno} to @code{GDBM_BAD_AVAIL}, marks the database as
+needing recovery (@pxref{Recovery}) and return -1.
+@end deftypefn
+
 @node Error codes
 @chapter Error codes
 @cindex error codes
@@ -1582,7 +1644,7 @@ Memory allocation failed.  Not enough memory.
 @item GDBM_BLOCK_SIZE_ERROR
 This error is set by the @code{gdbm_open} function (@pxref{Open}), if
 the value of its @var{block_size} argument is incorrect and the
-@samp{GDBM_BSEXACT} flag is set.
+@code{GDBM_BSEXACT} flag is set.
 
 @kwindex GDBM_FILE_OPEN_ERROR
 @item GDBM_FILE_OPEN_ERROR
@@ -1632,7 +1694,7 @@ The file given as argument to @code{gdbm_open} function is not a valid
 @kwindex GDBM_CANT_BE_READER
 @item GDBM_CANT_BE_READER
 This error code is set by the @code{gdbm_open} function if it is not
-able to lock file when called in @samp{GDBM_READER} mode (@pxref{Open,
+able to lock file when called in @code{GDBM_READER} mode (@pxref{Open,
 GDBM_READER}).
 
 @kwindex GDBM_CANT_BE_WRITER
@@ -1673,7 +1735,7 @@ able to create a temporary database.  @xref{Reorganization}.
 @item GDBM_CANNOT_REPLACE
 Cannot replace existing item.  This error is set by the
 @code{gdbm_store} if the requested @var{key} value is found in the
-database and the @var{flag} parameter is not @samp{GDBM_REPLACE}.
+database and the @var{flag} parameter is not @code{GDBM_REPLACE}.
 @xref{Store}, for a detailed discussion.
 
 @kwindex GDBM_ILLEGAL_DATA
@@ -1683,9 +1745,10 @@ to @code{gdbm_store} (@pxref{Store}).
 
 @kwindex GDBM_OPT_ALREADY_SET
 @item GDBM_OPT_ALREADY_SET      
-Requested option can be set only once and was already set.  This error
-is returned by the @code{gdbm_setopt} function.  @xref{Options,
-GDBM_CACHESIZE}.
+Requested option can be set only once and was already set.  As of
+version @value{VERSION}, this error code is no longer used.  In prior
+versions it could have been returned by the @code{gdbm_setopt}
+function when setting the @code{GDBM_CACHESIZE} value.
 
 @kwindex GDBM_OPT_ILLEGAL
 @item GDBM_OPT_ILLEGAL
@@ -1732,7 +1795,7 @@ these functions are: @code{gdbm_delete}, @code{gdbm_exists},
 @item GDBM_NO_DBNAME
 Output database name is not specified.  This error code is set by
 @code{gdbm_load} (@pxref{gdbm_load function,,gdbm_load}) if the first
-argument points to @samp{NULL} and the input file does not specify the
+argument points to @code{NULL} and the input file does not specify the
 database name.
 
 @kwindex GDBM_ERR_FILE_OWNER
@@ -1764,15 +1827,84 @@ The GDBM engine is unable to create backup copy of the file.
 @kwindex GDBM_DIR_OVERFLOW
 @item GDBM_DIR_OVERFLOW
 Bucket directory would overflow the size limit during an attempt to split
-hash bucket.  This error can occur while storing a new key. 
+hash bucket.  This error can occur while storing a new key.
+
+@kwindex GDBM_BAD_BUCKET
+@item GDBM_BAD_BUCKET
+Invalid index bucket is encountered in the database.  Database
+recovery is needed (@pxref{Recovery}).
+
+@kwindex GDBM_BAD_HEADER
+@item GDBM_BAD_HEADER
+This error is set by @code{gdbm_open} and @code{gdbm_fd_open}, if the
+first block read from the database file does not contain a valid GDBM
+header.
+
+@kwindex GDBM_BAD_AVAIL
+@item GDBM_BAD_AVAIL
+The available space stack is invalid.  This error can be set by 
+@code{gdbm_open} and @code{gdbm_fd_open}, if the extended database
+verification was requested (@code{GDBM_XVERIFY}).  It is also set
+by the @code{gdbm_avail_verify} function (@pxref{Additional
+functions}).
+
+Database recovery is needed (@pxref{Recovery}).
+
+@kwindex GDBM_BAD_HASH_TABLE
+@item GDBM_BAD_HASH_TABLE
+Hash table in a bucket is invalid.  This error can be set by the
+following functions: @code{gdbm_delete}, @code{gdbm_exists},
+@code{gdbm_fetch}, @code{gdbm_firstkey}, @code{gdbm_nextkey}, and
+@code{gdbm_store}.
+
+Database recovery is needed (@pxref{Recovery}).
+
+@kwindex GDBM_BAD_DIR_ENTRY
+@item GDBM_BAD_DIR_ENTRY
+Bad directory entry found in the bucket.  The database recovery is
+needed (@pxref{Recovery}).
+
+@kwindex GDBM_FILE_CLOSE_ERROR
+@item GDBM_FILE_CLOSE_ERROR
+The @code{gdbm_close} function was unable to close the database file
+descriptor.  The system @code{errno} variable contains the
+corresponding error code.
+
+@kwindex GDBM_FILE_SYNC_ERROR
+@item GDBM_FILE_SYNC_ERROR
+Cached content couldn't be synchronized to disk.  Examine the
+@code{errno} variable to get more info,
+
+Database recovery is needed (@pxref{Recovery}).
+
+@kwindex GDBM_FILE_TRUNCATE_ERROR
+@item GDBM_FILE_TRUNCATE_ERROR
+File cannot be truncated.  Examine the @code{errno} variable to get
+more info,
+
+This error is set by @code{gdbm_open} and @code{gdbm_fd_open} when
+called with the @code{GDBM_NEWDB} flag.
+
+@kwindex GDBM_BUCKET_CACHE_CORRUPTED
+@item GDBM_BUCKET_CACHE_CORRUPTED
+The bucket cache structure is corrupted.  Database recovery is needed
+(@pxref{Recovery}).
+
+@kwindex GDBM_BAD_HASH_ENTRY
+@kwindex GDBM_BAD_HASH_ENTRY
+This error is set during sequential access (@pxref{Sequential}), if
+the next hash table entry does not contain the expected key.  This
+means that the bucket is malformed or corrupted and the database needs
+recovery (@pxref{Recovery}).
+
 @end table
 
 @node Compatibility
-@chapter Compatibility with standard @code{dbm} and @code{ndbm}.
+@chapter Compatibility with standard @command{dbm} and @command{ndbm}.
 
 @cindex compatibility layer
-@code{Gdbm} includes a compatibility layer, which provides traditional
-@samp{ndbm} and older @samp{dbm} functions.  The layer is compiled and
+@command{Gdbm} includes a compatibility layer, which provides traditional
+@command{ndbm} and older @command{dbm} functions.  The layer is compiled and
 installed if the @option{--enable-libgdbm-compat} option is used when
 configuring the package.
 
@@ -1782,7 +1914,7 @@ configuring the package.
 The compatibility layer consists of two header files: @file{ndbm.h}
 and @file{dbm.h} and the @file{libgdbm_compat} library.
 
-Older programs using @code{ndbm} or @code{dbm} interfaces can
+Older programs using @command{ndbm} or @command{dbm} interfaces can
 use @file{libgdbm_compat} without any changes.  To link a program with
 the compatibility library, add the following two options to the
 @command{cc} invocation: @option{-lgdbm -lgdbm_compat}.  The @option{-L}
@@ -1801,11 +1933,11 @@ consist of two different files: @file{@var{file}.dir} and
 specification and corresponds to the traditional usage.  Note,
 however, that despite the similarity of the naming convention,
 actual data stored in these files has not the same format as
-in the databases created by other @code{dbm} or @code{ndbm}
+in the databases created by other @command{dbm} or @command{ndbm}
 libraries.  In other words, you cannot access a standard UNIX
-@code{dbm} file with GNU @code{dbm}!
+@command{dbm} file with GNU @command{dbm}!
 
-GNU @code{dbm} files are not @code{sparse}.  You can copy them with
+GNU @command{dbm} files are not @code{sparse}.  You can copy them with
 the usual @code{cp} command and they will not expand in the copying
 process.
 
@@ -1818,7 +1950,7 @@ process.
 @section NDBM interface functions.
 @cindex NDBM functions
 
-The functions below implement the @acronym{POSIX} @samp{ndbm} interface:
+The functions below implement the @acronym{POSIX} @command{ndbm} interface:
 
 @deftypefn {ndbm} {DBM *} dbm_open (char *@var{file}, int @var{flags}, int @var{mode})
 Opens a database.  The @var{file} argument is the full name of the
@@ -1840,7 +1972,7 @@ The function returns a pointer to the @code{DBM} structure describing
 the database.  This pointer is used to refer to this database in all
 operations described below.
 
-Any error detected will cause a return value of @samp{NULL} and an
+Any error detected will cause a return value of @code{NULL} and an
 appropriate value will be stored in @code{gdbm_errno}
 (@pxref{Variables}).
 @end deftypefn
@@ -1855,7 +1987,7 @@ Reads a record from the database with the matching key.  The @var{key}
 argument supplies the key that is being looked for.
 
 If no matching record is found, the @code{dptr} member of the returned
-datum is @samp{NULL}.  Otherwise, the @code{dptr} member of the
+datum is @code{NULL}.  Otherwise, the @code{dptr} member of the
 returned datum points to the memory managed by the compatibility
 library.  The application should never free it.
 @end deftypefn
@@ -1877,7 +2009,7 @@ Replace existing record with the new one.
 @kwindex DBM_INSERT
 @item DBM_INSERT
 The existing record is left unchanged, and the function returns
-@samp{1}.
+@code{1}.
 @end table
 
 If no matching record exists in the database, new record will be
@@ -1886,8 +2018,8 @@ inserted no matter what the value of the @var{mode} is.
                                  
 @deftypefn {ndbm} int dbm_delete (DBM *@var{dbf}, datum @var{key})
 Deletes the record with the matching key from the database.  If the
-function succeeds, @samp{0} is returned.  Otherwise, if no matching
-record is found or if an error occurs, @samp{-1} is returned.
+function succeeds, @code{0} is returned.  Otherwise, if no matching
+record is found or if an error occurs, @code{-1} is returned.
 @end deftypefn
 
 @deftypefn {ndbm} datum dbm_firstkey (DBM *@var{dbf})
@@ -1896,7 +2028,7 @@ the first key.  Note, that the word @samp{first} does not imply any
 specific ordering of the keys.
 
 If there are no records in the database, the @code{dptr} member of the
-returned datum is @samp{NULL}.  Otherwise, the @code{dptr} member of
+returned datum is @code{NULL}.  Otherwise, the @code{dptr} member of
 the returned datum points to the memory managed by the compatibility
 library.  The application should never free it.
 @end deftypefn
@@ -1904,7 +2036,7 @@ library.  The application should never free it.
 @deftypefn {ndbm} datum dbm_nextkey (DBM *@var{dbf})
 Continues the iteration started by @code{dbm_firstkey}.  Returns the
 next key in the database.  If the iteration covered all keys in the
-database, the @code{dptr} member of the returned datum is @samp{NULL}.
+database, the @code{dptr} member of the returned datum is @code{NULL}.
 Otherwise, the @code{dptr} member of the returned datum points to the
 memory managed by the compatibility library.  The application should
 never free it.
@@ -1926,7 +2058,7 @@ otherwise the iteration is not guaranteed to cover all the keys.
 @end deftypefn
 
 @deftypefn {ndbm} int dbm_error (DBM *@var{dbf})
-Returns the error condition of the database: @samp{0} if no errors
+Returns the error condition of the database: @code{0} if no errors
 occurred so far while manipulating the database, and a non-zero value
 otherwise.
 @end deftypefn
@@ -1950,8 +2082,8 @@ See also @code{dbm_dirfno}.
 @end deftypefn
 
 @deftypefn {ndbm} int dbm_rdonly (DBM *@var{dbf})
-Returns @samp{1} if the database @var{dbf} is open in a read-only mode
-and @samp{0} otherwise.
+Returns @code{1} if the database @var{dbf} is open in a read-only mode
+and @code{0} otherwise.
 @end deftypefn
 
 @node dbm
@@ -1985,7 +2117,7 @@ Reads a record from the database with the matching key.  The @var{key}
 argument supplies the key that is being looked for.
 
 If no matching record is found, the @code{dptr} member of the returned
-datum is @samp{NULL}.  Otherwise, the @code{dptr} member of the
+datum is @code{NULL}.  Otherwise, the @code{dptr} member of the
 returned datum points to the memory managed by the compatibility
 library.  The application should never free it.
 @end deftypefn
@@ -1995,14 +2127,14 @@ Stores the key/value pair in the database.  If a record with the
 matching key already exists, its content will be replaced with the new
 one.
 
-Returns @samp{0} on success and @samp{-1} on error.
+Returns @code{0} on success and @code{-1} on error.
 @end deftypefn
 
 @deftypefn {dbm} int delete (datum @var{key})
 Deletes a record with the matching key. 
 
-If the function succeeds, @samp{0} is returned.  Otherwise, if no
-matching record is found or if an error occurs, @samp{-1} is
+If the function succeeds, @code{0} is returned.  Otherwise, if no
+matching record is found or if an error occurs, @code{-1} is
 returned.
 @end deftypefn
 
@@ -2012,7 +2144,7 @@ the first key.  Note, that the word @samp{first} does not imply any
 specific ordering of the keys.
 
 If there are no records in the database, the @code{dptr} member of the
-returned datum is @samp{NULL}.  Otherwise, the @code{dptr} member of
+returned datum is @code{NULL}.  Otherwise, the @code{dptr} member of
 the returned datum points to the memory managed by the compatibility
 library.  The application should never free it.
 @end deftypefn
@@ -2020,7 +2152,7 @@ library.  The application should never free it.
 @deftypefn {dbm} datum nextkey (datum @var{key})
 Continues the iteration started by a call to @code{firstkey}.  Returns
 the next key in the database.  If the iteration covered all keys in the
-database, the @code{dptr} member of the returned datum is @samp{NULL}.
+database, the @code{dptr} member of the returned datum is @code{NULL}.
 Otherwise, the @code{dptr} member of the returned datum points to the
 memory managed by the compatibility library.  The application should
 never free it.
@@ -2118,7 +2250,7 @@ Disable memory mapping.
 @item -q
 @itemx --quiet
 Don't print the usual welcome banner at startup.  This is the same as
-setting the variable @samp{quiet} in the startup file.  @xref{quiet}.
+setting the variable @code{quiet} in the startup file.  @xref{quiet}.
 @item -r
 @itemx --read-only
 Open the database in read-only mode.
@@ -2147,7 +2279,7 @@ indicated by its @dfn{prompt}:
 gdbmtool> _
 @end example
 
-The utility finishes when it reads the @samp{quit} command (see below) or
+The utility finishes when it reads the @code{quit} command (see below) or
 detects end-of-file on its standard input, whichever occurs first.
 
 A @command{gdbmtool} command consists of a @dfn{command verb},
@@ -2155,8 +2287,8 @@ optionally followed by @dfn{arguments}, separated by any
 amount of white space and terminated with a newline or semicolon.
 A command verb can be entered either in full or in an abbreviated
 form, as long as that abbreviation does not match any other verb.  For
-example, @samp{co} can be used instead of @samp{count} and @samp{ca}
-instead of @samp{cache}.
+example, @code{co} can be used instead of @code{count} and @code{ca}
+instead of @code{cache}.
 
 Any sequence of non-whitespace characters appearing after the command
 verb forms an argument.  If the argument contains whitespace or
@@ -2187,7 +2319,7 @@ arguments over several input lines.
 Command parameters may be optional or mandatory.  If the number of
 actual arguments is less than the number of mandatory parameters,
 @command{gdbmtool} will prompt you to supply missing arguments.  For
-example, the @samp{store} command takes two mandatory parameters, so
+example, the @code{store} command takes two mandatory parameters, so
 if you invoked it with no arguments, you would be prompted twice to
 supply the necessary data, as shown in  example below:
 
@@ -2226,7 +2358,7 @@ variables.  To examine or modify variables, use the @code{set} command
 Whether to ask for confirmation before certain destructive operations,
 such as truncating the existing database.
 
-Default is @samp{true}.
+Default is @code{true}.
 @end deftypevr
 
 @deftypevr {gdbmtool variable} string ps1
@@ -2239,7 +2371,7 @@ follows:
 @headitem Sequence @tab Expansion
 @item %f @tab name of the current database file
 @item %p @tab program invocation name
-@item %P @tab package name (@samp{GDBM})
+@item %P @tab package name (@code{GDBM})
 @item %v @tab program version
 @item %_ @tab single space character
 @item %% @tab %
@@ -2250,7 +2382,7 @@ a ``greater than'' sign, followed by a single space.
 @end deftypevr
 
 @deftypevr {gdbmtool variable} string ps2
-Secondary prompt.  See @samp{ps1} for a description of its value.
+Secondary prompt.  See @code{ps1} for a description of its value.
 This prompt is displayed before reading the second and subsequent
 lines of a multi-line command.
 
@@ -2308,21 +2440,21 @@ Open mode.  The following values are allowed:
 Truncate the database if it exists or create a new one.  Open it in
 read-write mode.
 
-Technically, this sets the @samp{GDBM_NEWDB} flag in call to @samp{gdbm_open}.
+Technically, this sets the @code{GDBM_NEWDB} flag in call to @code{gdbm_open}.
 @xref{Open, GDBM_NEWDB}.
 @item wrcreat
 @itemx rw
 Open the database in read-write mode.  Create it if it does not
 exist.  This is the default.
 
-Technically speaking, it sets the @samp{GDBM_WRCREAT} flag in call to
+Technically speaking, it sets the @code{GDBM_WRCREAT} flag in call to
 @code{gdbm_open}.  @xref{Open, GDBM_WRCREAT}.
 @item reader
 @itemx readonly
 Open the database in read-only mode.  Signal an error if it does not
 exist.
 
-This sets the @samp{GDBM_READER} flag (@pxref{Open, GDBM_READER}).
+This sets the @code{GDBM_READER} flag (@pxref{Open, GDBM_READER}).
 @end table
 
 Attempting to set any other value or to unset this variable results
@@ -2339,14 +2471,14 @@ dumps.
 Lock the database.  This is the default.
 
 Setting this variable to false or unsetting it results in passing
-@samp{GDBM_NOLOCK} flag to @code{gdbm_open} (@pxref{Open, GDBM_NOLOCK}).
+@code{GDBM_NOLOCK} flag to @code{gdbm_open} (@pxref{Open, GDBM_NOLOCK}).
 @end deftypevr
 
 @deftypevr {gdbmtool variable} bool mmap
 Use memory mapping.  This is the default.
 
 Setting this variable to false or unsetting it results in passing
-@samp{GDBM_NOMMAP} flag to @code{gdbm_open} (@pxref{Open, GDBM_NOMMAP}).
+@code{GDBM_NOMMAP} flag to @code{gdbm_open} (@pxref{Open, GDBM_NOMMAP}).
 @end deftypevr
 
 @deftypevr {gdbmtool variable} bool sync
@@ -2366,7 +2498,7 @@ before invoking it.
 @end deftypevr
 
 @deftypevr {gdbmtool variable} bool centfree
-Set to @samp{true}, enables the use of central free block pool in
+Set to @code{true}, enables the use of central free block pool in
 newly opened databases. @xref{Options, GDBM_SETCENTFREE}.
 
 This variable affects the @command{open} command and should be set
@@ -2381,7 +2513,7 @@ When used without arguments, lists all variables and their values.
 Unset variables are shown after a comment sign (@samp{#}).  For string
 and numeric variables, values are shown after an equals sign.  For
 boolean variables, only the variable name is displayed if the variable
-is @samp{true}.  If it is @samp{false}, its name is prefixed with
+is @code{true}.  If it is @code{false}, its name is prefixed with
 @samp{no}. 
 
 For example:
@@ -2407,15 +2539,15 @@ pager="less"
 If used with arguments, the @code{set} command alters the specified
 variables.  In this case, arguments are variable assignments in the
 form @samp{@var{name}=@var{value}}.  For boolean variables, the
-@var{value} is interpreted as follows: if it is numeric, @samp{0}
-stands for @samp{false}, any non-zero value stands for @samp{true}.
-Otherwise, the values @samp{on}, @samp{true}, and @samp{yes} denote
-@samp{true}, and @samp{off}, @samp{false}, @samp{no} stand for
-@samp{false}.  Alternatively, only the name of a boolean variable can be
-supplied to set it to @samp{true}, and its name prefixed with
-@samp{no} can be used to set it to false.  For example, the following
-command sets the @samp{delim2} variable to @samp{;} and the
-@samp{confirm} variable to @samp{false}:
+@var{value} is interpreted as follows: if it is numeric, @code{0}
+stands for @code{false}, any non-zero value stands for @code{true}.
+Otherwise, the values @code{on}, @code{true}, and @code{yes} denote
+@code{true}, and @code{off}, @code{false}, @code{no} stand for
+@code{false}.  Alternatively, only the name of a boolean variable can be
+supplied to set it to @code{true}, and its name prefixed with
+@code{no} can be used to set it to false.  For example, the following
+command sets the @code{delim2} variable to @samp{;} and the
+@code{confirm} variable to @code{false}:
 
 @example
 set delim2=";" noconfirm
@@ -2426,7 +2558,7 @@ set delim2=";" noconfirm
 Unsets the listed variables.  The effect of unsetting depends on the
 variable.  Unless explicitly described in the discussion of the
 variables above, unsetting a boolean variable is equivalent to setting it to
-@samp{false}.  Unsetting a string variable is equivalent to assigning it
+@code{false}.  Unsetting a string variable is equivalent to assigning it
 an empty string.
 @end deffn
 
@@ -2567,11 +2699,11 @@ variables:
 The database access mode.  @xref{openvar,, The @var{open} variable},
 for a list of its values.
 @item lock
-Whether or not to lock the database.  Default is @samp{on}.
+Whether or not to lock the database.  Default is @code{on}.
 @item mmap
-Use the memory mapping.  Default is @samp{on}.
+Use the memory mapping.  Default is @code{on}.
 @item sync
-Synchronize after each write.  Default is @samp{off}.
+Synchronize after each write.  Default is @code{off}.
 @item filemode
 Specifies the permissions to use in case a new file is created.
 @end table
@@ -2629,7 +2761,7 @@ define key string
 define content string
 @end example
 
-The two @samp{define} strings show the defined formats for key and
+The two @code{define} strings show the defined formats for key and
 content data.  @xref{definitions}, for a detailed discussion of their
 meaning.
 @end deffn
@@ -2659,8 +2791,8 @@ define @var{what} @var{definition}
 @end example
 
 @noindent
-where @var{what} is @samp{key} to defining the structure of key data and
-@samp{content} to define the structure of the content records.
+where @var{what} is @code{key} to defining the structure of key data and
+@code{content} to define the structure of the content records.
 
 The @var{definition} can be of two distinct formats.  In the simplest
 case it is a single data type.  For example,
@@ -2707,7 +2839,7 @@ All numeric data types (integer as well as floating point) have the
 same respective widths as in C language on the host where the database
 file resides.
 
-The @samp{string} and @samp{stringz} are special.  Both define a
+The @code{string} and @code{stringz} are special.  Both define a
 string of bytes, similar to @samp{char x[]} in C.  The former
 defines an array of bytes, the latter - a null-terminated string.
 This makes a difference, in particular, when the string is the only
@@ -2763,16 +2895,16 @@ define content @{
 @}        
 @end example
 
-@emph{NOTE}: The @samp{string} type can reasonably be used only if it
+@emph{NOTE}: The @code{string} type can reasonably be used only if it
 is the last or the only member of the data structure.  That's because it
 provides no information about the number of elements in the array, so
 it is interpreted to contain all bytes up to the end of the datum.
 
 When displaying the structured data, @command{gdbmtool} precedes each
 value with the corresponding field name and delimits parts of the
-structure with the string defined in the @samp{delim1} variable
+structure with the string defined in the @code{delim1} variable
 (@pxref{variables}).  Array elements are delimited using the string from
-@samp{delim2}.  For example:
+@code{delim2}.  For example:
 
 @example
 gdbmtool> fetch foo
@@ -2817,7 +2949,7 @@ gdbmtool> store newkey @{ 2, @{a,u,x@}, "quux" @}
 @cindex init file, gdbmtool
 @flindex .gdbmtoolrc
 Upon startup @command{gdbmtool} looks for a file named
-@samp{.gdbmtoolrc} first in the current working directory and, if not
+@file{.gdbmtoolrc} first in the current working directory and, if not
 found, in the home directory of the user who started the command.
 
 If found, this file is read and interpreted as a list of
@@ -2869,8 +3001,8 @@ options:
 @table @option
 @item -H @var{fmt}
 @itemx --format=@var{fmt}
-Select output format.  Valid values for @var{fmt} are: @samp{binary}
-or @samp{0} to select binary dump format, and @samp{ascii} or @samp{1}
+Select output format.  Valid values for @var{fmt} are: @code{binary}
+or @code{0} to select binary dump format, and @code{ascii} or @code{1}
 to select ASCII format.
 
 @item -h
diff --git a/src/Makefile.am b/src/Makefile.am
index edcb4b9..0d10f23 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -41,6 +41,7 @@ lib_LTLIBRARIES = libgdbm.la
 libgdbm_la_LIBADD = @LTLIBINTL@
 
 libgdbm_la_SOURCES = \
+ cachetree.c\
  gdbmclose.c\
  gdbmcount.c\
  gdbmdelete.c\
diff --git a/src/bucket.c b/src/bucket.c
index 34e3a5e..dd72954 100644
--- a/src/bucket.c
+++ b/src/bucket.c
@@ -48,7 +48,7 @@ _gdbm_new_bucket (GDBM_FILE dbf, hash_bucket *bucket, int bits)
    a valid bucket or data block at that offset. All this implies is that
    it is safe to use the offset for look up in the bucket cache and to
    attempt to read a block at that offset. */
-int
+static inline int
 gdbm_dir_entry_valid_p (GDBM_FILE dbf, int dir_index)
 {
   return dir_index >= 0
@@ -56,34 +56,187 @@ gdbm_dir_entry_valid_p (GDBM_FILE dbf, int dir_index)
          && dbf->dir[dir_index] >= dbf->header->block_size;
 }
 
-static int
-bucket_read (GDBM_FILE dbf, hash_bucket *bucket)
+static void
+set_cache_entry (GDBM_FILE dbf, cache_elem *elem)
 {
-  /* Read the bucket. */
-  if (_gdbm_full_read (dbf, bucket, dbf->header->bucket_size))
+  dbf->cache_entry = elem;
+  dbf->bucket = dbf->cache_entry->ca_bucket;
+}
+
+
+/* LRU list management */
+
+/* Link ELEM after REF in DBF cache.  If REF is NULL, link at head */
+static void
+lru_link_elem (GDBM_FILE dbf, cache_elem *elem, cache_elem *ref)
+{
+  if (!ref)
     {
-      GDBM_DEBUG (GDBM_DEBUG_ERR,
-		  "%s: error reading bucket: %s",
-		  dbf->name, gdbm_db_strerror (dbf));
-      dbf->need_recovery = TRUE;
-      _gdbm_fatal (dbf, gdbm_db_strerror (dbf));
-      return -1;
+      elem->ca_prev = NULL;
+      elem->ca_next = dbf->cache_mru;
+      if (dbf->cache_mru)
+	dbf->cache_mru->ca_prev = elem;
+      else
+	dbf->cache_lru = elem;
+      dbf->cache_mru = elem;
     }
-  
-  /* Validate the bucket */
-  if (!(bucket->count >= 0
-	&& bucket->count <= dbf->header->bucket_elems
-	&& bucket->bucket_bits >= 0
-	&& bucket->bucket_bits <= dbf->header->dir_bits))
+  else
     {
-      GDBM_SET_ERRNO (dbf, GDBM_BAD_BUCKET, TRUE);
-      return -1;
+      cache_elem *x;
+
+      elem->ca_prev = ref;
+      elem->ca_next = ref->ca_next;
+      if ((x = ref->ca_next))
+	x->ca_prev = elem;
+      else
+	dbf->cache_lru = elem;
+      ref->ca_next = elem;
     }
+}
+
+/* Unlink ELEM from the list of cache elements in DBF. */
+static void
+lru_unlink_elem (GDBM_FILE dbf, cache_elem *elem)
+{
+  cache_elem *x;
+
+  if ((x = elem->ca_prev))
+    x->ca_next = elem->ca_next;
+  else
+    dbf->cache_mru = elem->ca_next;
+  if ((x = elem->ca_next))
+    x->ca_prev = elem->ca_prev;
+  else
+    dbf->cache_lru = elem->ca_prev;
+  elem->ca_prev = elem->ca_next = NULL;
+}
+
+/* Creates and returns new cache element for DBF.  The element is initialized,
+   but not linked to the LRU list.
+   Return NULL on error.
+*/
+static cache_elem *
+cache_elem_new (GDBM_FILE dbf, off_t adr)
+{
+  cache_elem *elem;
+
+  elem = dbf->cache_avail;
+  if (elem)
+    {
+      dbf->cache_avail = elem->ca_next;
+    }
+  else
+    {
+      elem = calloc (1,
+		     sizeof (*elem) -
+		     sizeof (elem->ca_bucket[0]) +
+		     dbf->header->bucket_size);
+
+      if (!elem)
+	return NULL;
+    }
+
+  elem->ca_adr = adr;
+  elem->ca_changed = FALSE;
+  elem->ca_data.hash_val = -1;
+  elem->ca_data.elem_loc = -1;
+
+  elem->ca_prev = elem->ca_next = NULL;
+  elem->ca_hits = 0;
+  elem->ca_node = NULL;
   
-  /* Validate bucket_avail table */
-  return gdbm_bucket_avail_table_validate (dbf, bucket);
+  dbf->cache_num++;
+  
+  return elem;
+}
+
+/* Frees element ELEM.  Unlinks it from the cache tree and LRU list. */
+static void
+cache_elem_free (GDBM_FILE dbf, cache_elem *elem)
+{
+  _gdbm_cache_tree_delete (dbf->cache_tree, elem->ca_node);
+  lru_unlink_elem (dbf, elem);
+  elem->ca_next = dbf->cache_avail;
+  dbf->cache_avail = elem;
+  dbf->cache_num--;
 }
 
+/* Free the least recently used cache entry. */
+static inline int
+cache_lru_free (GDBM_FILE dbf)
+{
+  cache_elem *last = dbf->cache_lru;
+  if (last->ca_changed)
+    {
+      if (_gdbm_write_bucket (dbf, last))
+	return -1;
+    }
+  cache_elem_free (dbf, last);
+  return 0;
+}
+  
+static int
+cache_lookup (GDBM_FILE dbf, off_t adr, cache_elem *ref, cache_elem **ret_elem)
+{
+  int rc;
+  cache_node *node;
+  cache_elem *elem;
+  int retrying = 0;
+  
+  dbf->cache_access_count++;
+ retry:
+  rc = _gdbm_cache_tree_lookup (dbf->cache_tree, adr, &node);
+  switch (rc)
+    {
+    case node_found:
+      elem = node->elem;
+      elem->ca_hits++;
+      dbf->cache_hits++;
+      lru_unlink_elem (dbf, elem);
+      break;
+      
+    case node_new:
+      elem = cache_elem_new (dbf, adr);
+      if (!elem)
+	{
+	  _gdbm_cache_tree_delete (dbf->cache_tree, node);
+	  return node_failure;
+	}
+      elem->ca_node = node;
+      node->elem = elem;
+      
+      if (dbf->cache_size != GDBM_CACHE_AUTO
+	  && dbf->cache_num > dbf->cache_size
+	  && cache_lru_free (dbf))
+	{
+	  cache_elem_free (dbf, elem);
+	  return node_failure;
+	}
+      break;
+      
+    case node_failure:
+      if (!retrying)
+	{
+	  if (errno == ENOMEM)
+	    {
+	      /* Release the last recently used element and retry. */
+	      if (cache_lru_free (dbf))
+		return node_failure;
+	      retrying = 1;
+	      goto retry;
+	    }
+	}
+      return node_failure;
+
+    default:
+      abort ();
+    }
+  
+  lru_link_elem (dbf, elem, ref);
+  *ret_elem = elem;
+  return rc;
+}
+
 /* Find a bucket for DBF that is pointed to by the bucket directory from
    location DIR_INDEX.   The bucket cache is first checked to see if it
    is already in memory.  If not, a bucket may be tossed to read the new
@@ -94,10 +247,12 @@ bucket_read (GDBM_FILE dbf, hash_bucket *bucket)
 int
 _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
 {
+  int rc;
   off_t bucket_adr;	/* The address of the correct hash bucket.  */
   off_t	file_pos;	/* The return address for lseek. */
-  int   index;		/* Loop index. */
-
+  hash_bucket *bucket;
+  cache_elem *elem;
+  
   if (!gdbm_dir_entry_valid_p (dbf, dir_index))
     {
       /* FIXME: negative caching? */
@@ -108,108 +263,69 @@ _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
   /* Initial set up. */
   dbf->bucket_dir = dir_index;
   bucket_adr = dbf->dir[dir_index];
-  
-  if (dbf->bucket_cache == NULL)
-    {
-      if (_gdbm_init_cache (dbf, DEFAULT_CACHESIZE) == -1)
-	{
-	  _gdbm_fatal (dbf, _("couldn't init cache"));
-	  return -1;
-	}
-    }
 
-  /* If that one is not already current, we must find it. */
-  if (dbf->cache_entry->ca_adr != bucket_adr)
+  if (dbf->cache_entry && dbf->cache_entry->ca_adr == bucket_adr)
+    return 0;
+  
+  switch (cache_lookup (dbf, bucket_adr, NULL, &elem))
     {
-      size_t lru;
+    case node_found:
+      break;
       
-      /* Look in the cache. */
-      for (index = 0; index < dbf->cache_size; index++)
-        {
-	  if (dbf->bucket_cache[index].ca_adr == bucket_adr)
-	    {
-	      dbf->bucket = dbf->bucket_cache[index].ca_bucket;
-	      dbf->cache_entry = &dbf->bucket_cache[index];
-	      return 0;
-	    }
-        }
-
-      /* It is not in the cache, read it from the disk. */
-
+    case node_new:
       /* Position the file pointer */
       file_pos = gdbm_file_seek (dbf, bucket_adr, SEEK_SET);
       if (file_pos != bucket_adr)
 	{
 	  GDBM_SET_ERRNO (dbf, GDBM_FILE_SEEK_ERROR, TRUE);
+	  cache_elem_free (dbf, elem);
 	  _gdbm_fatal (dbf, _("lseek error"));
 	  return -1;
 	}
-      
-      /* Flush and drop the last recently used cache entry */
-      lru = (dbf->last_read + 1) % dbf->cache_size;
-      if (dbf->bucket_cache[lru].ca_changed)
+
+      /* Read the bucket. */
+      rc = _gdbm_full_read (dbf, elem->ca_bucket, dbf->header->bucket_size);
+      if (rc)
 	{
-	  if (_gdbm_write_bucket (dbf, &dbf->bucket_cache[lru]))
-	    return -1;
+	  GDBM_DEBUG (GDBM_DEBUG_ERR,
+		      "%s: error reading bucket: %s",
+		      dbf->name, gdbm_db_strerror (dbf));
+	  dbf->need_recovery = TRUE;
+	  cache_elem_free (dbf, elem);
+	  _gdbm_fatal (dbf, gdbm_db_strerror (dbf));
+	  return -1;
 	}
-      _gdbm_cache_entry_invalidate (dbf, lru);
 
-      if (bucket_read (dbf, dbf->bucket_cache[lru].ca_bucket))
+      /* Validate the bucket */
+      bucket = elem->ca_bucket;
+      if (!(bucket->count >= 0
+	    && bucket->count <= dbf->header->bucket_elems
+	    && bucket->bucket_bits >= 0
+	    && bucket->bucket_bits <= dbf->header->dir_bits))
 	{
-	  /* Invalidate the bucket */
-	  memset (dbf->bucket_cache[lru].ca_bucket, 0,
-		  dbf->header->bucket_size);
+	  GDBM_SET_ERRNO (dbf, GDBM_BAD_BUCKET, TRUE);
+	  cache_elem_free (dbf, elem);
 	  return -1;
 	}
-
-      /* Finally, store it in cache */
-      dbf->last_read = lru;
-      dbf->bucket_cache[lru].ca_adr = bucket_adr;
-      dbf->bucket = dbf->bucket_cache[lru].ca_bucket;
-      dbf->cache_entry = &dbf->bucket_cache[lru];
-      dbf->cache_entry->ca_data.elem_loc = -1;
-      dbf->cache_entry->ca_changed = FALSE;
-    }
-  return 0;
-}
-
-int
-_gdbm_read_bucket_at (GDBM_FILE dbf, off_t off, hash_bucket *bucket,
-		      size_t size)
-{
-  off_t file_pos;
-  int i;
-
-  if (dbf->cache_entry && dbf->cache_entry->ca_adr == off)
-    {
-      memcpy (bucket, dbf->bucket, size);
-      return 0;
-    }
-
-  /* Look in the cache. */
-  for (i = 0; i < dbf->cache_size; i++)
-    {
-      if (dbf->bucket_cache[i].ca_adr == off)
+      /* Validate bucket_avail table */
+      if (gdbm_bucket_avail_table_validate (dbf, bucket))
 	{
-	  memcpy (bucket, dbf->bucket_cache[i].ca_bucket, size);
-	  return 0;
+	  cache_elem_free (dbf, elem);
+	  return -1;
 	}
-    }
-
-  /* Read the bucket. */
-  file_pos = gdbm_file_seek (dbf, off, SEEK_SET);
-  if (file_pos != off)
-    {
-      GDBM_SET_ERRNO (dbf, GDBM_FILE_SEEK_ERROR, TRUE);
-      return -1;
-    }
-  if (_gdbm_full_read (dbf, bucket, size))
-    {
-      GDBM_DEBUG (GDBM_DEBUG_ERR,
-		  "%s: error reading bucket: %s",
-		  dbf->name, gdbm_db_strerror (dbf));
+      
+      /* Update the cache */
+      elem->ca_adr = bucket_adr;
+      elem->ca_data.elem_loc = -1;
+      elem->ca_changed = FALSE;
+      
+      break;
+      
+    case node_failure:
       return -1;
     }
+  set_cache_entry (dbf, elem);
+  
   return 0;
 }
 
@@ -220,86 +336,74 @@ _gdbm_read_bucket_at (GDBM_FILE dbf, off_t off, hash_bucket *bucket,
 int
 _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
 {
-  hash_bucket *bucket[2]; 	/* Pointers to the new buckets. */
-
-  int          new_bits;	/* The number of bits for the new buckets. */
-  int	       cache_0;		/* Location in the cache for the buckets. */
-  int	       cache_1;
-  off_t        adr_0;		/* File address of the new bucket 0. */
-  off_t        adr_1;		/* File address of the new bucket 1. */
-  avail_elem   old_bucket;	/* Avail Struct for the old bucket. */
-
-  off_t        dir_start0;	/* Used in updating the directory. */
-  off_t        dir_start1;
-  off_t        dir_end;
-
-  off_t       *new_dir;		/* Pointer to the new directory. */
-  off_t        dir_adr; 	/* Address of the new directory. */
-  int          dir_size;	/* Size of the new directory. */
   off_t        old_adr[GDBM_HASH_BITS];  /* Address of the old directories. */
   int          old_size[GDBM_HASH_BITS]; /* Size of the old directories. */
   int	       old_count;	/* Number of old directories. */
 
   int          index;		/* Used in array indexing. */
   int          index1;		/* Used in array indexing. */
-  int          elem_loc;	/* Location in new bucket to put element. */
-  bucket_element *old_el;	/* Pointer into the old bucket. */
-  int	       select;		/* Used to index bucket during movement. */
   
   /* No directories are yet old. */
   old_count = 0;
-
-  if (dbf->bucket_cache == NULL)
+  while (dbf->bucket->count == dbf->header->bucket_elems)
     {
-      if (_gdbm_init_cache (dbf, DEFAULT_CACHESIZE) == -1)
+      int          new_bits;	/* The number of bits for the new buckets. */
+      cache_elem  *newcache[2]; /* Location in the cache for the buckets. */
+      off_t        adr_0;	/* File address of the new bucket 0. */
+      off_t        adr_1;	/* File address of the new bucket 1. */
+      avail_elem   old_bucket;	/* Avail Struct for the old bucket. */
+      
+      off_t        dir_start0;	/* Used in updating the directory. */
+      off_t        dir_start1;
+      off_t        dir_end;
+
+      new_bits = dbf->bucket->bucket_bits + 1;
+      /* Allocate two new buckets */
+      adr_0 = _gdbm_alloc (dbf, dbf->header->bucket_size);
+      switch (cache_lookup (dbf, adr_0, dbf->cache_mru, &newcache[0]))
 	{
-	  _gdbm_fatal (dbf, _("couldn't init cache"));
+	case node_new:
+	  break;
+
+	case node_found:
+	  /* should not happen */
+	  GDBM_DEBUG (GDBM_DEBUG_ERR,
+		      "%s: bucket found where it should not",
+		      dbf->name);
+	  GDBM_SET_ERRNO (dbf, GDBM_BUCKET_CACHE_CORRUPTED, TRUE);
 	  return -1;
-	}
-    }
 
-  while (dbf->bucket->count == dbf->header->bucket_elems)
-    {
-      /* Initialize the "new" buckets in the cache. */
-      do
-	{
-	  dbf->last_read = (dbf->last_read + 1) % dbf->cache_size;
-	  cache_0 = dbf->last_read;
-	}      
-      while (dbf->bucket_cache[cache_0].ca_bucket == dbf->bucket);
-      bucket[0] = dbf->bucket_cache[cache_0].ca_bucket;
-      if (dbf->bucket_cache[cache_0].ca_changed)
-	{
-	  if (_gdbm_write_bucket (dbf, &dbf->bucket_cache[cache_0]))
-	    return -1;
+	case node_failure:
+	  return -1;
 	}
-      do
-	{
-	  dbf->last_read = (dbf->last_read + 1) % dbf->cache_size;
-	  cache_1 = dbf->last_read;
-	}      
-      while (dbf->bucket_cache[cache_1].ca_bucket == dbf->bucket);
-      bucket[1] = dbf->bucket_cache[cache_1].ca_bucket;
-      if (dbf->bucket_cache[cache_1].ca_changed)
+      _gdbm_new_bucket (dbf, newcache[0]->ca_bucket, new_bits);
+
+      adr_1 = _gdbm_alloc (dbf, dbf->header->bucket_size);
+      switch (cache_lookup (dbf, adr_1, newcache[0], &newcache[1]))
 	{
-	  if (_gdbm_write_bucket (dbf, &dbf->bucket_cache[cache_1]))
-	    return -1;
+	case node_new:
+	  break;
+
+	case node_found:
+	  /* should not happen */
+	  GDBM_DEBUG (GDBM_DEBUG_ERR,
+		      "%s: bucket found where it should not",
+		      dbf->name);
+	  GDBM_SET_ERRNO (dbf, GDBM_BUCKET_CACHE_CORRUPTED, TRUE);
+	  return -1;
+
+	case node_failure:
+	  return -1;
 	}
-      new_bits = dbf->bucket->bucket_bits + 1;
-      _gdbm_new_bucket (dbf, bucket[0], new_bits);
-      _gdbm_new_bucket (dbf, bucket[1], new_bits);
-      adr_0 = _gdbm_alloc (dbf, dbf->header->bucket_size);
-      if (adr_0 == 0)
-	return -1;
-      dbf->bucket_cache[cache_0].ca_adr = adr_0;
-      adr_1 = _gdbm_alloc (dbf, dbf->header->bucket_size);
-      if (adr_1 == 0)
-	return -1;
-      dbf->bucket_cache[cache_1].ca_adr = adr_1;
+      _gdbm_new_bucket (dbf, newcache[1]->ca_bucket, new_bits);
 
       /* Double the directory size if necessary. */
       if (dbf->header->dir_bits == dbf->bucket->bucket_bits)
 	{
+	  off_t       *new_dir;		/* Pointer to the new directory. */
+	  int          dir_size;	/* Size of the new directory. */
+	  off_t        dir_adr; 	/* Address of the new directory. */
+	  
 	  if (dbf->header->dir_size >= GDBM_MAX_DIR_HALF)
 	    {
 	      GDBM_SET_ERRNO (dbf, GDBM_DIR_OVERFLOW, TRUE);
@@ -342,40 +446,44 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
       /* Copy all elements in dbf->bucket into the new buckets. */
       for (index = 0; index < dbf->header->bucket_elems; index++)
 	{
-	  old_el = &dbf->bucket->h_table[index];
-	  select = (old_el->hash_value >> (GDBM_HASH_BITS - new_bits)) & 1;
-	  elem_loc = old_el->hash_value % dbf->header->bucket_elems;
-	  while (bucket[select]->h_table[elem_loc].hash_value != -1)
+	  bucket_element *old_el = &dbf->bucket->h_table[index];
+	  hash_bucket *bucket =
+	    newcache[(old_el->hash_value >> (GDBM_HASH_BITS - new_bits)) & 1]->ca_bucket;
+	  int elem_loc = old_el->hash_value % dbf->header->bucket_elems;
+	  while (bucket->h_table[elem_loc].hash_value != -1)
 	    elem_loc = (elem_loc + 1) % dbf->header->bucket_elems;
-	  bucket[select]->h_table[elem_loc] = *old_el;
-	  bucket[select]->count++;
+	  bucket->h_table[elem_loc] = *old_el;
+	  bucket->count++;
 	}
       
-      /* Allocate avail space for the bucket[1]. */
-      bucket[1]->bucket_avail[0].av_adr
+      /* Allocate avail space for the newcache[1]->ca_bucket. */
+      newcache[1]->ca_bucket->bucket_avail[0].av_adr
 	= _gdbm_alloc (dbf, dbf->header->block_size);
-      if (bucket[1]->bucket_avail[0].av_adr == 0)
+      if (newcache[1]->ca_bucket->bucket_avail[0].av_adr == 0)
 	return -1;
-      bucket[1]->bucket_avail[0].av_size = dbf->header->block_size;
-      bucket[1]->av_count = 1;
+      newcache[1]->ca_bucket->bucket_avail[0].av_size
+	= dbf->header->block_size;
+      newcache[1]->ca_bucket->av_count = 1;
       
-      /* Copy the avail elements in dbf->bucket to bucket[0]. */
-      bucket[0]->av_count = dbf->bucket->av_count;
+      /* Copy the avail elements in dbf->bucket to newcache[0]->ca_bucket. */
+      newcache[0]->ca_bucket->av_count = dbf->bucket->av_count;
       index = 0;
-      index1 = 0;
-      if (bucket[0]->av_count == BUCKET_AVAIL)
+      if (newcache[0]->ca_bucket->av_count == BUCKET_AVAIL)
 	{
-	  /* The avail is full, move the first one to bucket[1]. */
+	  /* The avail is full, move the first one to newcache[1]->ca_bucket.*/
 	  _gdbm_put_av_elem (dbf->bucket->bucket_avail[0],
-			     bucket[1]->bucket_avail,
-			     &bucket[1]->av_count, 
+			     newcache[1]->ca_bucket->bucket_avail,
+			     &newcache[1]->ca_bucket->av_count, 
                              dbf->coalesce_blocks);
 	  index = 1;
-	  bucket[0]->av_count--;
+	  newcache[0]->ca_bucket->av_count--;
 	}
+
+      index1 = 0;
       for (; index < dbf->bucket->av_count; index++)
 	{
-	  bucket[0]->bucket_avail[index1++] = dbf->bucket->bucket_avail[index];
+	  newcache[0]->ca_bucket->bucket_avail[index1++]
+	    = dbf->bucket->bucket_avail[index];
 	}
       
       /* Update the directory.  We have new file addresses for both buckets. */
@@ -388,10 +496,9 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
       for (index = dir_start1; index < dir_end; index++)
 	dbf->dir[index] = adr_1;
       
-      
       /* Set changed flags. */
-      dbf->bucket_cache[cache_0].ca_changed = TRUE;
-      dbf->bucket_cache[cache_1].ca_changed = TRUE;
+      newcache[0]->ca_changed = TRUE;
+      newcache[1]->ca_changed = TRUE;
       dbf->bucket_changed = TRUE;
       dbf->directory_changed = TRUE;
       dbf->second_changed = TRUE;
@@ -402,29 +509,23 @@ _gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
       /* Invalidate old cache entry. */
       old_bucket.av_adr  = dbf->cache_entry->ca_adr;
       old_bucket.av_size = dbf->header->bucket_size;
-      dbf->cache_entry->ca_adr = 0;
-      dbf->cache_entry->ca_changed = FALSE;
+      cache_elem_free (dbf, dbf->cache_entry);
       
       /* Set dbf->bucket to the proper bucket. */
-      if (dbf->dir[dbf->bucket_dir] == adr_0)
+      if (dbf->dir[dbf->bucket_dir] != adr_0)
 	{
-	  dbf->bucket = bucket[0];
-	  dbf->cache_entry = &dbf->bucket_cache[cache_0];
-	  _gdbm_put_av_elem (old_bucket,
-			     bucket[1]->bucket_avail,
-			     &bucket[1]->av_count, 
-                             dbf->coalesce_blocks);
+	  cache_elem *t = newcache[0];
+	  newcache[0] = newcache[1];
+	  newcache[1] = t;
 	}
-      else
-	{
-	  dbf->bucket = bucket[1];
-	  dbf->cache_entry = &dbf->bucket_cache[cache_1];
-	  _gdbm_put_av_elem (old_bucket,
-			     bucket[0]->bucket_avail,
-			     &bucket[0]->av_count, 
-                             dbf->coalesce_blocks);
-	}
-      
+
+      _gdbm_put_av_elem (old_bucket,
+			 newcache[1]->ca_bucket->bucket_avail,
+			 &newcache[1]->ca_bucket->av_count, 
+			 dbf->coalesce_blocks);
+      lru_unlink_elem (dbf, newcache[0]);
+      lru_link_elem (dbf, newcache[0], NULL);
+      set_cache_entry (dbf, newcache[0]);
     }
 
   /* Get rid of old directories. */
@@ -467,3 +568,158 @@ _gdbm_write_bucket (GDBM_FILE dbf, cache_elem *ca_entry)
   ca_entry->ca_data.elem_loc = -1;
   return 0;
 }
+
+/* Cache manipulation functions. */
+
+/* Initialize the bucket cache. */
+int
+_gdbm_cache_init (GDBM_FILE dbf, size_t size)
+{
+  if (size == dbf->cache_size)
+    return 0;
+
+  if (size != GDBM_CACHE_AUTO)
+    {
+      while (size < dbf->cache_num)
+	{
+	  /* Flush the least recently used element */
+	  cache_elem *elem = dbf->cache_lru;
+	  if (elem->ca_changed)
+	    {
+	      if (_gdbm_write_bucket (dbf, elem))
+		return -1;
+	    }
+	  cache_elem_free (dbf, elem);
+	}
+    }
+  
+  dbf->cache_size = size;
+
+  return 0;
+}
+
+/* Free the bucket cache */
+void
+_gdbm_cache_free (GDBM_FILE dbf)
+{
+  cache_elem *elem;
+
+  while (dbf->cache_lru)
+    cache_elem_free (dbf, dbf->cache_lru);
+  _gdbm_cache_tree_destroy (dbf->cache_tree);
+  while ((elem = dbf->cache_avail) != NULL)
+    {
+      dbf->cache_avail = elem->ca_next;
+      free (elem->ca_data.dptr);
+      free (elem);
+    }
+}
+
+/* Flush cache content to disk. */
+int
+_gdbm_cache_flush (GDBM_FILE dbf)
+{
+  cache_elem *elem;
+  for (elem = dbf->cache_lru; elem; elem = elem->ca_prev)
+    {
+      if (elem->ca_changed)
+	{
+	  if (_gdbm_write_bucket (dbf, elem))
+	    return -1;
+	}
+    }
+  return 0;
+}
+
+int
+_gdbm_fetch_data (GDBM_FILE dbf, off_t off, size_t size, void *buf)
+{
+  off_t bucket_adr;
+  off_t file_pos;
+  int rc;
+  cache_elem *elem;
+  char *dst = buf;
+
+  bucket_adr = (off / dbf->header->bucket_size)
+                 * dbf->header->bucket_size;
+  off -= bucket_adr;
+  while (size)
+    {
+      size_t nbytes;
+      
+      switch (cache_lookup (dbf, bucket_adr, dbf->cache_mru, &elem))
+	{
+	case node_found:
+	  break;
+	  
+	case node_new:
+	  /* Position the file pointer */
+	  file_pos = gdbm_file_seek (dbf, bucket_adr, SEEK_SET);
+	  if (file_pos != bucket_adr)
+	    {
+	      GDBM_SET_ERRNO (dbf, GDBM_FILE_SEEK_ERROR, TRUE);
+	      cache_elem_free (dbf, elem);
+	      _gdbm_fatal (dbf, _("lseek error"));
+	      return -1;
+	    }
+
+	  /* Read the bucket. */
+	  rc = _gdbm_full_read (dbf, elem->ca_bucket,
+				dbf->header->bucket_size);
+	  if (rc)
+	    {
+	      GDBM_DEBUG (GDBM_DEBUG_ERR,
+			  "%s: error reading data bucket: %s",
+			  dbf->name, gdbm_db_strerror (dbf));
+	      dbf->need_recovery = TRUE;
+	      cache_elem_free (dbf, elem);
+	      _gdbm_fatal (dbf, gdbm_db_strerror (dbf));
+	      return -1;
+	    }
+	  break;
+	  
+	case node_failure:
+	  return -1;
+	}
+
+      nbytes = dbf->header->bucket_size - off;
+      if (nbytes > size)
+	nbytes = size;
+      memcpy (dst, (char*) elem->ca_bucket + off, nbytes);
+      dst += nbytes;
+      size -= nbytes;
+      bucket_adr++;
+      off = 0;
+    }
+  return 0;
+}
+
+void
+gdbm_get_cache_stats (GDBM_FILE dbf,
+		      size_t *access_count,
+		      size_t *cache_hits,
+		      size_t *cache_count,
+		      struct gdbm_cache_stat *bstat,
+		      size_t nstat)
+{
+  if (access_count)
+    *access_count = dbf->cache_access_count;
+  if (cache_hits)
+    *cache_hits = dbf->cache_hits;
+  if (cache_count)
+    *cache_count = dbf->cache_num;
+  if (bstat)
+    {
+      size_t i;
+      cache_elem *elem;
+
+      if (nstat > dbf->cache_num)
+	nstat = dbf->cache_num;
+      
+      for (i = 0, elem = dbf->cache_mru; i < nstat; i++, elem = elem->ca_next)
+	{
+	  bstat[i].adr = elem->ca_adr;
+	  bstat[i].hits = elem->ca_hits;
+	}
+    }
+}
diff --git a/src/cachetree.c b/src/cachetree.c
new file mode 100644
index 0000000..de5a5c1
--- /dev/null
+++ b/src/cachetree.c
@@ -0,0 +1,484 @@
+/* cachetree.c - Implementation of the red-black tree for cache lookups. */
+
+/* This file is part of GDBM, the GNU data base manager.
+   Copyright (C) 2019-2021 Free Software Foundation, Inc.
+
+   GDBM 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 3, or (at your option)
+   any later version.
+
+   GDBM 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 GDBM. If not, see <http://www.gnu.org/licenses/>.   */
+
+#include "autoconf.h"
+#include "gdbmdefs.h"
+
+enum cache_node_color { RED, BLACK };
+
+struct cache_tree
+{
+  cache_node *root;   /* Root of the tree */
+  cache_node *avail;  /* List of available nodes, linked by parent field */
+};
+
+/* Allocate and return a new node.  Pick the head item from the avail
+   list and update the avail pointer.  If the list is empty, malloc
+   a new node.
+   All members in the returned node are filled with 0.
+*/
+static cache_node *
+rbt_node_alloc (cache_tree *tree)
+{
+  cache_node *n;
+
+  n = tree->avail;
+  if (n)
+    tree->avail = n->parent;
+  else
+    {
+      n = malloc (sizeof (*n));
+      if (!n)
+	return NULL;
+    }
+  memset (n, 0, sizeof (*n));
+  return n;
+}
+
+/* Return the node N to the avail list in TREE. */
+static void
+rbt_node_dealloc (cache_tree *tree, cache_node *n)
+{
+  n->parent = tree->avail;
+  tree->avail = n;
+}
+
+/* Red-black tree properties:
+     1. Each node is either red or black.
+     2. The root node is black.
+     3. All leaves are black and contain no data.
+     4. Every red node has two children, and both are black.
+        IOW, the parent of every red node is black.
+     5. All paths from any given node to its leaf nodes contain the same
+        number of black nodes.
+ */
+
+/* Auxiliary functions for accessing nodes. */
+
+/* Return the grandparent node of N.
+   Prerequisite: N may not be root.
+*/
+static inline cache_node *
+grandparent (cache_node *n)
+{
+  return n->parent->parent;
+}
+
+/* Return the sibling node of N.
+   Prerequisite: N may not be root.
+*/   
+static inline cache_node *
+sibling (cache_node *n)
+{
+  return (n == n->parent->left) ? n->parent->right : n->parent->left;
+}
+
+/* Return the uncle node of N.
+   Prerequisite: N must be at least 2 nodes away from root.
+*/   
+static inline cache_node *
+uncle (cache_node *n)
+{
+  return sibling (n->parent);
+}
+
+/* Returns the color of the node N.
+   Empty leaves are represented by NULL, therefore NULL is assumed to
+   be black (see property 3).
+*/
+static inline enum cache_node_color
+node_color (cache_node *n)
+{
+  return n == NULL ? BLACK : n->color;
+}
+
+/* Replace the OLDN with NEWN.
+   Does not modify OLDN. */
+static inline void
+replace_node (cache_tree *tree, cache_node *oldn, cache_node *newn)
+{
+  if (oldn->parent == NULL)
+    tree->root = newn;
+  else if (oldn == oldn->parent->left)
+    oldn->parent->left = newn;
+  else
+    oldn->parent->right = newn;
+
+  if (newn != NULL)
+    newn->parent = oldn->parent;
+}
+
+/* Rotate the TREE left over the node N. */
+static inline void
+rotate_left (cache_tree *tree, cache_node *n)
+{
+  cache_node *right = n->right;
+  replace_node (tree, n, right);
+  n->right = right->left;
+  if (right->left != NULL)
+    right->left->parent = n;
+  right->left = n;
+  n->parent = right;
+}
+
+/* Rotate the TREE right over the node N. */
+static inline void
+rotate_right (cache_tree *tree, cache_node *n)
+{
+  cache_node *left = n->left;
+  replace_node (tree, n, left);
+  n->left = left->right;
+  if (left->right != NULL)
+    left->right->parent = n;
+  left->right = n;
+  n->parent = left;
+}
+
+/* Node deletion */
+static inline void
+rbt_delete_fixup (cache_tree *tree, cache_node *n)
+{
+  while (1)
+    {
+      if (n->parent == NULL)
+	{
+	  /* If N has become the root node, deletion resulted in removing
+	     one black node (prior root) from every path, so all properties
+	     still hold.
+	  */
+	  return;
+	}
+      else
+	{
+	  /* If N has a red sibling, change the colors of the parent and
+	     sibling and rotate about the parent.  Thus, the sibling becomes
+	     grandparent and we can proceed to the next case.
+	  */
+	  if (node_color (sibling (n)) == RED)
+	    {
+	      n->parent->color = RED;
+	      sibling (n)->color = BLACK;
+	      if (n == n->parent->left)
+		rotate_left (tree, n->parent);
+	      else
+		rotate_right (tree, n->parent);
+	    }
+
+	  /* If the parent, sibling and nephews are all black, paint the
+	     sibling red.  This means one black node was removed from all
+	     paths passing through the parent, so we recurse to the beginning
+	     of the loop with parent as the argument to restore the properties.
+	     This is the only branch that loops.
+	  */
+	  if (node_color (n->parent) == BLACK
+	      && node_color (sibling (n)) == BLACK
+	      && node_color (sibling (n)->left) == BLACK
+	      && node_color (sibling (n)->right) == BLACK)
+	    {
+	      sibling (n)->color = RED;
+	      n = n->parent;
+	      continue;
+	    }
+	  else
+	    {
+	      /* If the sibling and nephews are black but the parent is red,
+		 swap the colors of the sibling and parent.  The properties
+		 are then restored.
+	      */
+	      if (node_color (n->parent) == RED
+		  && node_color (sibling (n)) == BLACK
+		  && node_color (sibling (n)->left) == BLACK
+		  && node_color (sibling (n)->right) == BLACK)
+		{
+		  sibling (n)->color = RED;
+		  n->parent->color = BLACK;
+		}
+	      else
+		{
+		  /* N is the left child of its parent, its sibling is black,
+		     and the sibling's right child is black. Swap the colors
+		     of the sibling and its left sibling and rotate right
+		     over the sibling.
+		  */
+		  if (n == n->parent->left
+		      && node_color (sibling (n)) == BLACK
+		      && node_color (sibling (n)->left) == RED
+		      && node_color (sibling (n)->right) == BLACK)
+		    {
+		      sibling (n)->color = RED;
+		      sibling (n)->left->color = BLACK;
+		      rotate_right (tree, sibling (n));
+		    }
+		  else if (n == n->parent->right
+			   && node_color (sibling (n)) == BLACK
+			   && node_color (sibling (n)->right) == RED
+			   && node_color (sibling (n)->left) == BLACK)
+		    {
+		      /* The mirror case is handled similarly. */
+		      sibling (n)->color = RED;
+		      sibling (n)->right->color = BLACK;
+		      rotate_left (tree, sibling (n));
+		    }
+		  /* N is the left child of its parent, its sibling is black
+		     and the sibling's right child is red.  Swap the colors
+		     of the parent and sibling, paint the sibling's right
+		     child black and rotate left at the parent.  Similarly
+		     for the mirror case.  This achieves the following:
+	     
+		     . A black node is added to all paths passing through N;
+		     . A black node is removed from all paths through the
+		       sibling's red child.
+		     . The latter is painted black which restores missing
+		       black node in all paths through the sibling's red child.
+
+		     Another sibling's child becomes a child of N's parent
+		     during the rotation and is therefore not affected.
+		  */
+		  sibling (n)->color = node_color (n->parent);
+		  n->parent->color = BLACK;
+		  if (n == n->parent->left)
+		    {
+		      sibling (n)->right->color = BLACK;
+		      rotate_left (tree, n->parent);
+		    }
+		  else
+		    {
+		      sibling (n)->left->color = BLACK;
+		      rotate_right (tree, n->parent);
+		    }
+		}
+	    }
+	}
+      break;
+    }
+}
+
+/* Remove N from the TREE. */
+void
+_gdbm_cache_tree_delete (cache_tree *tree, cache_node *n)
+{
+  cache_node *child;
+
+  /* If N has both left and right children, reduce the problem to
+     the node with only one child.  To do so, find the in-order
+     predecessor of N, copy its value (elem) to N and then delete
+     the predecessor. */
+  if (n->left != NULL && n->right != NULL)
+    {
+      cache_node *p;
+      for (p = n->left; p->right; p = p->right)
+        ;
+      n->adr = p->adr;
+      n->elem = p->elem;
+      n->elem->ca_node = n;
+      n = p;
+    }
+
+  /* N has only one child. Select it. */
+  child = n->left ? n->left : n->right;
+  if (node_color (n) == BLACK)
+    {
+      n->color = node_color (child);
+      rbt_delete_fixup (tree, n);
+    }
+  replace_node (tree, n, child);
+  if (n->parent == NULL && child != NULL)	/* root should be black */
+    child->color = BLACK;
+
+  /* Return N to the avail pool */
+  rbt_node_dealloc (tree, n);
+}
+
+/* Insertion */
+static inline void
+rbt_insert_fixup (cache_tree *tree, cache_node *n)
+{
+  while (1)
+    {
+      if (n->parent == NULL)
+	{
+	  /* Node was inserted at the root of the tree.
+	     The root node must be black (property 2).  Changing its color
+	     to black would add one black node to every path, which means
+	     the property 5 would remain satisfied.  So we simply paint the
+	     node black.
+	  */
+	  n->color = BLACK;
+	}
+      else if (node_color (n->parent) == BLACK)
+	{
+	  /* The node has black parent.
+	     All properties are satisfied.  There's no need to change anything.
+	  */
+	  return;
+	}
+      else if (node_color (uncle (n)) == RED)
+	{
+	  /* The uncle node is red.
+	     Repaint the parent and uncle black and the grandparent red.  This
+	     would satisfy 4.  However, if the grandparent is root, this would
+	     violate the property 2.  So we repaint the grandparent by
+	     re-entering the fixup loop with grandparent as the node.
+	     This is the only branch that loops.
+	  */
+	  n->parent->color = BLACK;
+	  uncle (n)->color = BLACK;
+	  n = grandparent (n);
+	  n->color = RED;
+	  continue;
+	}
+      else
+	{
+	  /* The new node is the right child of its parent and the parent is
+	     the left child of the grandparent.  Rotate left about the parent.
+	     Mirror case: The new node is the left child of its parent and the
+	     parent is the right child of the grandparent.  Rotate right about
+	     the parent.  This fixes the properties for the rbt_insert_5.
+	  */
+	  if (n == n->parent->right && n->parent == grandparent (n)->left)
+	    {
+	      rotate_left (tree, n->parent);
+	      n = n->left;
+	    }
+	  else if (n == n->parent->left && n->parent == grandparent (n)->right)
+	    {
+	      rotate_right (tree, n->parent);
+	      n = n->right;
+	    }
+
+	  /* The new node is the left child of its parent and the parent is the
+	     left child of the grandparent. Rotate right about the grandparent.
+	     Mirror case: The new node is the right child of its parent and the
+	     parent
+	     is the right child of the grandparent. Rotate left.
+	  */
+	  n->parent->color = BLACK;
+	  grandparent (n)->color = RED;
+	  if (n == n->parent->left && n->parent == grandparent (n)->left)
+	    {
+	      rotate_right (tree, grandparent (n));
+	    }
+	  else
+	    {
+	      rotate_left (tree, grandparent (n));
+	    }
+	}
+      break;
+    }
+}
+
+/* Look up the node with the given ADR.
+   If found, put it in *RETVAL and return node_found.
+
+   Otherwise, create a new node and insert it at the appropriate place in
+   the tree.  Store the address of the newly created node in *RETVAL and
+   return node_new.
+
+   If a new node cannot be created (memory exhausted), return node_failure.
+*/
+int
+_gdbm_cache_tree_lookup (cache_tree *tree, off_t adr, cache_node **retval)
+{
+  int res;
+  cache_node *node, *parent = NULL;
+
+  node = tree->root;
+  while (node)
+    {
+      if (adr == node->adr)
+	break;
+      parent = node;
+      if (adr < node->adr)
+	node = node->left;
+      else
+	node = node->right;
+    }
+  
+  if (node)
+    {
+      res = node_found;
+    }
+  else
+    {
+      node = rbt_node_alloc (tree);
+      if (!node)
+	return node_failure;
+      if (!parent)
+	tree->root = node;
+      else if (adr < parent->adr)
+	parent->left = node;
+      else
+	parent->right = node;
+      node->adr = adr;
+      node->parent = parent;
+      rbt_insert_fixup (tree, node);
+      res = node_new;
+    }
+  *retval = node;
+  return res;
+}
+
+/* Interface functions */
+
+/* Create a cache tree structure for the database file DBF. */
+cache_tree *
+_gdbm_cache_tree_alloc (void)
+{
+  cache_tree *t = malloc (sizeof (*t));
+  if (t)
+    {
+      t->root = NULL;
+      t->avail = NULL;
+    }
+  return t;
+}
+
+/* Free the memory used by the TREE. */
+void
+_gdbm_cache_tree_destroy (cache_tree *tree)
+{
+  cache_node *n;
+  
+  /* Free the allocated tree nodes.  Traverse the tree as if it were
+     a simple binary tree: there's no use preserving RBT properties now.
+  */
+  while ((n = tree->root) != NULL)
+    {
+      if (!n->left)
+	tree->root = n->right;
+      else if (!n->right)
+	tree->root = n->left;
+      else
+	{
+	  cache_node *p;
+	  for (p = n->left; p->right; p = p->right)
+	    ;
+	  p->right = n->right;
+	  tree->root = n->left;
+	}
+      free (n);
+    }
+  
+  /* Free the avail list */
+  while ((n = tree->avail) != NULL)
+    {
+      tree->avail = n->parent;
+      free (n);
+    }
+  free (tree);
+}
diff --git a/src/findkey.c b/src/findkey.c
index 513f2a8..ac777ed 100644
--- a/src/findkey.c
+++ b/src/findkey.c
@@ -60,10 +60,10 @@ char *
 _gdbm_read_entry (GDBM_FILE dbf, int elem_loc)
 {
   int rc;
+  off_t file_pos;
   int key_size;
   int data_size;
   size_t dsize;
-  off_t file_pos;
   data_cache_elem *data_ca;
 
   /* Is it already in the cache? */
@@ -116,21 +116,21 @@ _gdbm_read_entry (GDBM_FILE dbf, int elem_loc)
     }
 
   /* Read into the cache. */
-  file_pos = gdbm_file_seek (dbf, dbf->bucket->h_table[elem_loc].data_pointer, 
-		      SEEK_SET);
+  file_pos = gdbm_file_seek (dbf, dbf->bucket->h_table[elem_loc].data_pointer,
+                             SEEK_SET);
   if (file_pos != dbf->bucket->h_table[elem_loc].data_pointer)
     {
       GDBM_SET_ERRNO2 (dbf, GDBM_FILE_SEEK_ERROR, TRUE, GDBM_DEBUG_LOOKUP);
       _gdbm_fatal (dbf, _("lseek error"));
       return NULL;
     }
-  
+
   rc = _gdbm_full_read (dbf, data_ca->dptr, key_size+data_size);
   if (rc)
     {
       GDBM_DEBUG (GDBM_DEBUG_ERR|GDBM_DEBUG_LOOKUP|GDBM_DEBUG_READ,
-		  "%s: error reading entry: %s",
-		  dbf->name, gdbm_db_strerror (dbf));
+                 "%s: error reading entry: %s",
+                 dbf->name, gdbm_db_strerror (dbf));
       dbf->need_recovery = TRUE;
       _gdbm_fatal (dbf, gdbm_db_strerror (dbf));
       return NULL;
diff --git a/src/gdbm.h.in b/src/gdbm.h.in
index 5adf0bc..1cd54c4 100644
--- a/src/gdbm.h.in
+++ b/src/gdbm.h.in
@@ -53,7 +53,8 @@ extern "C" {
 				   GDBM_BLOCK_SIZE_ERROR error if unable to
 				   set it. */  
 # define GDBM_CLOERROR  0x400   /* Only for gdbm_fd_open: close fd on error. */
-  
+# define GDBM_XVERIFY   0x800   /* Additional consistency checks. */
+
 /* Parameters to gdbm_store for simple insertion or replacement in the
    case that the key is already in the database. */
 # define GDBM_INSERT	0	/* Never replace old data with new. */
@@ -84,6 +85,8 @@ extern "C" {
 # define GDBM_GETDBNAME       15 /* Return database file name */
 # define GDBM_GETBLOCKSIZE    16 /* Return block size */
 
+# define GDBM_CACHE_AUTO      0
+  
 typedef @GDBM_COUNT_T@ gdbm_count_t;
   
 /* The data and key structure. */
@@ -93,7 +96,6 @@ typedef struct
   int   dsize;
 } datum;
 
-
 /* A pointer to the GDBM file. */
 typedef struct gdbm_file_info *GDBM_FILE;
 
@@ -132,6 +134,7 @@ extern int gdbm_import (GDBM_FILE, const char *, int);
 extern int gdbm_import_from_file (GDBM_FILE dbf, FILE *fp, int flag);
 
 extern int gdbm_count (GDBM_FILE dbf, gdbm_count_t *pcount);
+extern int gdbm_bucket_count (GDBM_FILE dbf, size_t *pcount);
 
 extern int gdbm_avail_verify (GDBM_FILE dbf);
 
@@ -189,47 +192,52 @@ extern int gdbm_load_from_file (GDBM_FILE *, FILE *, int replace,
 
 extern int gdbm_copy_meta (GDBM_FILE dst, GDBM_FILE src);
 
-# define GDBM_NO_ERROR		         0
-# define GDBM_MALLOC_ERROR	         1
-# define GDBM_BLOCK_SIZE_ERROR	         2
-# define GDBM_FILE_OPEN_ERROR	         3
-# define GDBM_FILE_WRITE_ERROR	         4
-# define GDBM_FILE_SEEK_ERROR	         5
-# define GDBM_FILE_READ_ERROR	         6
-# define GDBM_BAD_MAGIC_NUMBER	         7
-# define GDBM_EMPTY_DATABASE	         8
-# define GDBM_CANT_BE_READER	         9
-# define GDBM_CANT_BE_WRITER	        10
-# define GDBM_READER_CANT_DELETE	11
-# define GDBM_READER_CANT_STORE	        12
-# define GDBM_READER_CANT_REORGANIZE	13
-# define GDBM_UNKNOWN_ERROR	        14
-# define GDBM_ITEM_NOT_FOUND	        15
-# define GDBM_REORGANIZE_FAILED	        16
-# define GDBM_CANNOT_REPLACE	        17
-# define GDBM_ILLEGAL_DATA	        18
-# define GDBM_OPT_ALREADY_SET	        19
-# define GDBM_OPT_ILLEGAL           	20
-# define GDBM_BYTE_SWAPPED	        21
-# define GDBM_BAD_FILE_OFFSET	        22
-# define GDBM_BAD_OPEN_FLAGS	        23
-# define GDBM_FILE_STAT_ERROR           24
-# define GDBM_FILE_EOF                  25
-# define GDBM_NO_DBNAME                 26
-# define GDBM_ERR_FILE_OWNER            27
-# define GDBM_ERR_FILE_MODE             28
-# define GDBM_NEED_RECOVERY             29
-# define GDBM_BACKUP_FAILED             30
-# define GDBM_DIR_OVERFLOW              31
-# define GDBM_BAD_BUCKET                32
-# define GDBM_BAD_HEADER                33
-# define GDBM_BAD_AVAIL                 34
-# define GDBM_BAD_HASH_TABLE            35
-# define GDBM_BAD_DIR_ENTRY             36
-# define GDBM_FILE_CLOSE_ERROR          37  
-# define GDBM_FILE_SYNC_ERROR           38
-# define GDBM_FILE_TRUNCATE_ERROR       39
-# define GDBM_BAD_HASH_ENTRY            40
+enum
+  {
+    GDBM_NO_ERROR		 = 0,
+    GDBM_MALLOC_ERROR	         = 1,
+    GDBM_BLOCK_SIZE_ERROR	 = 2,
+    GDBM_FILE_OPEN_ERROR	 = 3,
+    GDBM_FILE_WRITE_ERROR	 = 4,
+    GDBM_FILE_SEEK_ERROR	 = 5,
+    GDBM_FILE_READ_ERROR	 = 6,
+    GDBM_BAD_MAGIC_NUMBER	 = 7,
+    GDBM_EMPTY_DATABASE	         = 8,
+    GDBM_CANT_BE_READER	         = 9,
+    GDBM_CANT_BE_WRITER	         = 10, 
+    GDBM_READER_CANT_DELETE	 = 11,
+    GDBM_READER_CANT_STORE	 = 12,
+    GDBM_READER_CANT_REORGANIZE	 = 13,
+    GDBM_UNKNOWN_ERROR	         = 14,
+    GDBM_ITEM_NOT_FOUND	         = 15,
+    GDBM_REORGANIZE_FAILED	 = 16,
+    GDBM_CANNOT_REPLACE	         = 17,
+    GDBM_ILLEGAL_DATA	         = 18,
+    GDBM_OPT_ALREADY_SET	 = 19,
+    GDBM_OPT_ILLEGAL           	 = 20,
+    GDBM_BYTE_SWAPPED	         = 21,
+    GDBM_BAD_FILE_OFFSET	 = 22,
+    GDBM_BAD_OPEN_FLAGS	         = 23,
+    GDBM_FILE_STAT_ERROR         = 24,
+    GDBM_FILE_EOF                = 25,
+    GDBM_NO_DBNAME               = 26,
+    GDBM_ERR_FILE_OWNER          = 27,
+    GDBM_ERR_FILE_MODE           = 28,
+    GDBM_NEED_RECOVERY           = 29,
+    GDBM_BACKUP_FAILED           = 30,
+    GDBM_DIR_OVERFLOW            = 31,
+    GDBM_BAD_BUCKET              = 32,
+    GDBM_BAD_HEADER              = 33,
+    GDBM_BAD_AVAIL               = 34,
+    GDBM_BAD_HASH_TABLE          = 35,
+    GDBM_BAD_DIR_ENTRY           = 36,
+    GDBM_FILE_CLOSE_ERROR        = 37, 
+    GDBM_FILE_SYNC_ERROR         = 38,
+    GDBM_FILE_TRUNCATE_ERROR     = 39,
+    GDBM_BUCKET_CACHE_CORRUPTED  = 40,
+    GDBM_BAD_HASH_ENTRY          = 41,
+  };
+  
 # define _GDBM_MIN_ERRNO	0
 # define _GDBM_MAX_ERRNO	GDBM_BAD_HASH_ENTRY
 
@@ -276,8 +284,21 @@ extern void gdbm_debug_parse_state (int (*f) (void *, int, char const *),
 				    void *d);
   
 extern void gdbm_debug_datum (datum dat, char const *pfx);
-  
 #endif
+
+/* Cache statistics */  
+struct gdbm_cache_stat
+{
+  off_t adr;
+  size_t hits;
+};
+
+void gdbm_get_cache_stats (GDBM_FILE dbf,
+			   size_t *access_count,
+			   size_t *cache_hits,
+			   size_t *cache_count,
+			   struct gdbm_cache_stat *bstat,
+			   size_t nstat);
   
 # if defined(__cplusplus) || defined(c_plusplus)
 }
diff --git a/src/gdbmclose.c b/src/gdbmclose.c
index fbb1f01..c9e3749 100644
--- a/src/gdbmclose.c
+++ b/src/gdbmclose.c
@@ -22,13 +22,11 @@
 #include "gdbmdefs.h"
 
 /* Close the dbm file and free all memory associated with the file DBF.
-   Before freeing members of DBF, check and make sure that they were
-   allocated.  */
+ */
 
 int
 gdbm_close (GDBM_FILE dbf)
 {
-  int index;	/* For freeing the bucket cache. */
   int syserrno;
   
   gdbm_set_errno (dbf, GDBM_NO_ERROR, FALSE);
@@ -57,15 +55,8 @@ gdbm_close (GDBM_FILE dbf)
   free (dbf->name);
   free (dbf->dir);
 
-  if (dbf->bucket_cache != NULL)
-    {
-      for (index = 0; index < dbf->cache_size; index++)
-	{
-	  free (dbf->bucket_cache[index].ca_bucket);
-	  free (dbf->bucket_cache[index].ca_data.dptr);
-	}
-      free (dbf->bucket_cache);
-    }
+  _gdbm_cache_free (dbf);
+  
   free (dbf->header);
   free (dbf);
   if (gdbm_errno)
diff --git a/src/gdbmconst.h b/src/gdbmconst.h
index feae7f8..d466ac5 100644
--- a/src/gdbmconst.h
+++ b/src/gdbmconst.h
@@ -51,7 +51,7 @@
 #define BUCKET_AVAIL 6
 
 /* The size of the bucket cache. */
-#define DEFAULT_CACHESIZE  100
+#define DEFAULT_CACHESIZE  GDBM_CACHE_AUTO
 
 #ifndef SIZE_T_MAX
 /* Maximum size representable by a size_t variable */
diff --git a/src/gdbmcount.c b/src/gdbmcount.c
index d50e7ff..3e6bb06 100644
--- a/src/gdbmcount.c
+++ b/src/gdbmcount.c
@@ -39,3 +39,19 @@ gdbm_count (GDBM_FILE dbf, gdbm_count_t *pcount)
   *pcount = count;
   return 0;
 }
+
+int
+gdbm_bucket_count (GDBM_FILE dbf, size_t *pcount)
+{
+  int i;
+  size_t count = 0;
+  
+  GDBM_ASSERT_CONSISTENCY (dbf, -1);
+
+  for (i = 0; i < GDBM_DIR_COUNT (dbf); i = _gdbm_next_bucket_dir (dbf, i))
+    {
+      ++count;
+    }
+  *pcount = count;
+  return 0;
+}
diff --git a/src/gdbmdefs.h b/src/gdbmdefs.h
index 1ab4abb..c6df13d 100644
--- a/src/gdbmdefs.h
+++ b/src/gdbmdefs.h
@@ -142,13 +142,35 @@ typedef struct
   int     elem_loc;
 } data_cache_elem;
 
-typedef struct
+typedef struct cache_elem cache_elem;
+typedef struct cache_node cache_node;
+
+struct cache_node
+{
+  cache_node *left, *right, *parent; 
+  int color;
+  off_t adr;
+  cache_elem *elem;
+};
+
+struct cache_elem
 {
-  hash_bucket *   ca_bucket;
   off_t           ca_adr;
-  char            ca_changed;   /* Data in the bucket changed. */
-  data_cache_elem ca_data;
-} cache_elem;
+  char            ca_changed;  /* Data in the bucket changed. */
+  data_cache_elem ca_data;     /* Cached datum */
+  cache_elem      *ca_prev,    /* Previous element in LRU list. */
+                  *ca_next;    /* Next elements in LRU list.
+				  If the item is in cache_avail list, only
+				  ca_next is used.  It points to the next
+			          available element. */
+  size_t          ca_hits;     /* Number of times this element was requested */
+  cache_node      *ca_node;    /* Points back to the RBT node for this
+				  element. */
+  hash_bucket     ca_bucket[1];/* Associated  bucket (dbf->header->bucket_size
+				  bytes). */
+};
+
+typedef struct cache_tree cache_tree;
 
 /* This final structure contains all main memory based information for
    a gdbm file.  This allows multiple gdbm files to be opened at the same
@@ -184,7 +206,7 @@ struct gdbm_file_info
 
   /* Last error was fatal, the database needs recovery */
   unsigned need_recovery :1;
-  
+
   /* Last GDBM error number */
   gdbm_error last_error;
   /* Last system error number */
@@ -210,19 +232,28 @@ struct gdbm_file_info
   off_t *dir;
 
   /* The bucket cache. */
-  cache_elem *bucket_cache;
-  size_t cache_size;
-  size_t last_read;
-
+  size_t cache_size;       /* Cache capacity */
+  size_t cache_num;        /* Actual number of elements in cache */
+  /* Cache elements form a binary search tree. */
+  cache_tree *cache_tree;  
+  /* Cache elements are linked in a list sorted by relative access time */
+  cache_elem *cache_mru;   /* Most recently used element - head of the list */
+  cache_elem *cache_lru;   /* Last recently used element - tail of the list */ 
+  cache_elem *cache_avail; /* Pool of available elements (linked by prev, next)
+			    */
+  /* Pointer to the current bucket's cache entry. */
+  cache_elem *cache_entry;
+  
   /* Points to the current hash bucket in the cache. */
   hash_bucket *bucket;
-
+  
   /* The directory entry used to get the current hash bucket. */
   int bucket_dir;
 
-  /* Pointer to the current bucket's cache entry. */
-  cache_elem *cache_entry;
-
+  /* Cache statistics */
+  size_t cache_access_count; /* Number of cache accesses */
+  size_t cache_hits;         /* Number of cache hits */
+  
   /* Bookkeeping of things that need to be written back at the
      end of an update. */
   unsigned header_changed :1;
diff --git a/src/gdbmerrno.c b/src/gdbmerrno.c
index 309ebbc..9109bc2 100644
--- a/src/gdbmerrno.c
+++ b/src/gdbmerrno.c
@@ -140,6 +140,7 @@ const char * const gdbm_errlist[_GDBM_MAX_ERRNO+1] = {
   [GDBM_FILE_CLOSE_ERROR]       = N_("Error closing file"),
   [GDBM_FILE_SYNC_ERROR]        = N_("Error synchronizing file"),
   [GDBM_FILE_TRUNCATE_ERROR]    = N_("Error truncating file"),
+  [GDBM_BUCKET_CACHE_CORRUPTED] = N_("Bucket cache corrupted"),
   [GDBM_BAD_HASH_ENTRY]         = N_("Malformed bucket hash entry")
 };
 
diff --git a/src/gdbmopen.c b/src/gdbmopen.c
index 4f9d469..ca26792 100644
--- a/src/gdbmopen.c
+++ b/src/gdbmopen.c
@@ -200,11 +200,13 @@ gdbm_fd_open (int fd, const char *file_name, int block_size,
   dbf->dir  = NULL;
   dbf->bucket = NULL;
   dbf->header = NULL;
-  dbf->bucket_cache = NULL;
-  dbf->cache_size = 0;
+
+  /* Initialize cache */
+  dbf->cache_tree = _gdbm_cache_tree_alloc ();
+  _gdbm_cache_init (dbf, DEFAULT_CACHESIZE);
 
   dbf->file_size = -1;
-  
+
   dbf->memory_mapping = FALSE;
   dbf->mapped_size_max = SIZE_T_MAX;
   dbf->mapped_region = NULL;
@@ -570,15 +572,18 @@ gdbm_fd_open (int fd, const char *file_name, int block_size,
 #endif
 
   /* Finish initializing dbf. */
-  dbf->last_read = -1;
   dbf->bucket = NULL;
   dbf->bucket_dir = 0;
-  dbf->cache_entry = NULL;
   dbf->header_changed = FALSE;
   dbf->directory_changed = FALSE;
   dbf->bucket_changed = FALSE;
   dbf->second_changed = FALSE;
 
+  if (flags & GDBM_XVERIFY)
+    {
+      gdbm_avail_verify (dbf);
+    }
+  
   GDBM_DEBUG (GDBM_DEBUG_ALL, "%s: opened %s", dbf->name,
 	      dbf->need_recovery ? "for recovery" : "successfully");
 
@@ -648,50 +653,6 @@ gdbm_open (const char *file, int block_size, int flags, int mode,
 		       fatal_func);
 }
 
-/* Initialize the bucket cache. */
-int
-_gdbm_init_cache (GDBM_FILE dbf, size_t size)
-{
-  int index;
-
-  if (dbf->bucket_cache == NULL)
-    {
-      dbf->bucket_cache = calloc (size, sizeof(cache_elem));
-      if (dbf->bucket_cache == NULL)
-        {
-          GDBM_SET_ERRNO (dbf, GDBM_MALLOC_ERROR, TRUE);
-          return -1;
-        }
-      dbf->cache_size = size;
-
-      for (index = 0; index < size; index++)
-        {
-	  (dbf->bucket_cache[index]).ca_bucket =
-	    malloc (dbf->header->bucket_size);
-          if ((dbf->bucket_cache[index]).ca_bucket == NULL)
-	    {
-              GDBM_SET_ERRNO (dbf, GDBM_MALLOC_ERROR, TRUE);
-	      return -1;
-            }
-	  dbf->bucket_cache[index].ca_data.dptr = NULL;
-	  dbf->bucket_cache[index].ca_data.dsize = 0;
-	  _gdbm_cache_entry_invalidate (dbf, index);
-        }
-      dbf->bucket = dbf->bucket_cache[0].ca_bucket;
-      dbf->cache_entry = &dbf->bucket_cache[0];
-    }
-  return 0;
-}
-
-void
-_gdbm_cache_entry_invalidate (GDBM_FILE dbf, int index)
-{
-  dbf->bucket_cache[index].ca_adr = 0;
-  dbf->bucket_cache[index].ca_changed = FALSE;
-  dbf->bucket_cache[index].ca_data.hash_val = -1;
-  dbf->bucket_cache[index].ca_data.elem_loc = -1;
-}
-
 int
 _gdbm_file_size (GDBM_FILE dbf, off_t *psize)
 {
diff --git a/src/gdbmsetopt.c b/src/gdbmsetopt.c
index bb123ea..c6f2052 100644
--- a/src/gdbmsetopt.c
+++ b/src/gdbmsetopt.c
@@ -53,19 +53,13 @@ setopt_gdbm_setcachesize (GDBM_FILE dbf, void *optval, int optlen)
 {
   size_t sz;
 
-  if (dbf->bucket_cache != NULL)
-    {
-      GDBM_SET_ERRNO (dbf, GDBM_OPT_ALREADY_SET, FALSE);
-      return -1;
-    }
-  
   /* Optval will point to the new size of the cache. */
   if (get_size (optval, optlen, &sz))
     {     
       GDBM_SET_ERRNO (dbf, GDBM_OPT_ILLEGAL, FALSE);
       return -1;
     }  
-  return _gdbm_init_cache (dbf, (sz > 9) ? sz : 10);
+  return _gdbm_cache_init (dbf, sz);
 }
 
 static int
diff --git a/src/gdbmtool.c b/src/gdbmtool.c
index c5e84d0..7fbecc0 100644
--- a/src/gdbmtool.c
+++ b/src/gdbmtool.c
@@ -276,26 +276,25 @@ _gdbm_print_avail_list (FILE *fp, GDBM_FILE dbf)
 void
 _gdbm_print_bucket_cache (FILE *fp, GDBM_FILE dbf)
 {
-  int             index;
-  char            changed;
-
-  if (dbf->bucket_cache != NULL)
+  if (dbf->cache_num)
     {
+      int i;
+      cache_elem *elem;
+  
       fprintf (fp,
-	_("Bucket Cache (size %zu):\n  Index:         Address  Changed  Data_Hash \n"),
-	 dbf->cache_size);
-      for (index = 0; index < dbf->cache_size; index++)
+	_("Bucket Cache (size %zu/%zu):\n  Index:         Address  Changed  Data_Hash \n"),
+	       dbf->cache_num, dbf->cache_size);
+      for (elem = dbf->cache_entry, i = 0; elem; elem = elem->ca_next, i++)
 	{
-	  changed = dbf->bucket_cache[index].ca_changed;
 	  fprintf (fp, "  %5d:  %15lu %7s  %x\n",
-		   index,
-		   (unsigned long) dbf->bucket_cache[index].ca_adr,
-		   (changed ? _("True") : _("False")),
-		   dbf->bucket_cache[index].ca_data.hash_val);
+		   i,
+		   (unsigned long) elem->ca_adr,
+		   (elem->ca_changed ? _("True") : _("False")),
+		   elem->ca_data.hash_val);
 	}
     }
   else
-    fprintf (fp, _("Bucket cache has not been initialized.\n"));
+    fprintf (fp, _("Bucket cache is empty.\n"));
 }
 
 int
@@ -745,17 +744,11 @@ print_dir_begin (struct handler_param *param GDBM_ARG_UNUSED, size_t *exp_count)
 static size_t
 bucket_count (void)
 {
-  int i;
-  off_t last = 0;
   size_t count = 0;
-  
-  for (i = 0; i < GDBM_DIR_COUNT (gdbm_file); i++)
+
+  if (gdbm_bucket_count (gdbm_file, &count))
     {
-      if (gdbm_file->dir[i] != last)
-	{
-	  ++count;
-	  last = gdbm_file->dir[i];
-	}
+      terror ("gdbm_bucket_count: %s", gdbm_strerror (gdbm_errno));
     }
   return count;
 }
@@ -835,7 +828,7 @@ print_cache_begin (struct handler_param *param GDBM_ARG_UNUSED, size_t *exp_coun
   if (checkdb ())
     return 1;
   if (exp_count)
-    *exp_count = gdbm_file->bucket_cache ? gdbm_file->cache_size + 1 : 1;
+    *exp_count = gdbm_file->cache_num + 1;
   return 0;
 }
 
diff --git a/src/proto.h b/src/proto.h
index f81f7ac..7c03b9d 100644
--- a/src/proto.h
+++ b/src/proto.h
@@ -20,11 +20,13 @@
 /* From bucket.c */
 void _gdbm_new_bucket	(GDBM_FILE, hash_bucket *, int);
 int _gdbm_get_bucket	(GDBM_FILE, int);
-int _gdbm_read_bucket_at (GDBM_FILE dbf, off_t off, hash_bucket *bucket,
-			  size_t size);
+int _gdbm_fetch_data   (GDBM_FILE dbf, off_t off, size_t size, void *buf);
 
 int _gdbm_split_bucket (GDBM_FILE, int);
 int _gdbm_write_bucket (GDBM_FILE, cache_elem *);
+int _gdbm_cache_init   (GDBM_FILE, size_t);
+void _gdbm_cache_free  (GDBM_FILE dbf);
+int _gdbm_cache_flush  (GDBM_FILE dbf);
 
 /* From falloc.c */
 off_t _gdbm_alloc       (GDBM_FILE, int);
@@ -47,12 +49,6 @@ int _gdbm_end_update   (GDBM_FILE);
 void _gdbm_fatal	(GDBM_FILE, const char *);
 
 /* From gdbmopen.c */
-int _gdbm_init_cache	(GDBM_FILE, size_t);
-void _gdbm_cache_entry_invalidate (GDBM_FILE, int);
-
-int gdbm_avail_block_validate (GDBM_FILE dbf, avail_block *avblk, size_t size);
-int gdbm_bucket_avail_table_validate (GDBM_FILE dbf, hash_bucket *bucket);
-
 int _gdbm_validate_header (GDBM_FILE dbf);
 
 int _gdbm_file_size (GDBM_FILE dbf, off_t *psize);
@@ -88,12 +84,28 @@ int _gdbm_dump (GDBM_FILE dbf, FILE *fp);
 /* From recover.c */
 int _gdbm_next_bucket_dir (GDBM_FILE dbf, int bucket_dir);
 
+/* cachetree.c */
+cache_tree *_gdbm_cache_tree_alloc (void);
+void _gdbm_cache_tree_destroy (cache_tree *tree);
+void _gdbm_cache_tree_delete (cache_tree *tree, struct cache_node *n);
+
 /* avail.c */
 int gdbm_avail_block_validate (GDBM_FILE dbf, avail_block *avblk, size_t size);
 int gdbm_bucket_avail_table_validate (GDBM_FILE dbf, hash_bucket *bucket);
 int gdbm_avail_traverse (GDBM_FILE dbf,
-                         int (*cb) (avail_block *, off_t, void *),
-                         void *data);
+			 int (*cb) (avail_block *, off_t, void *),
+			 void *data);
+
+
+/* Return codes for _gdbm_cache_tree_lookup. */
+enum
+  {
+    node_found,   /* Returned element was found in cache. */
+    node_new,     /* Returned element has been created and inserted to cache */
+    node_failure  /* An error occurred. */
+  };
+
+int _gdbm_cache_tree_lookup (cache_tree *tree, off_t adr, cache_node **retval);
 
 /* I/O functions */
 static inline ssize_t
diff --git a/src/recover.c b/src/recover.c
index 45de923..b4b577c 100644
--- a/src/recover.c
+++ b/src/recover.c
@@ -91,8 +91,6 @@ static int
 _gdbm_finish_transfer (GDBM_FILE dbf, GDBM_FILE new_dbf,
 		       gdbm_recovery *rcvr, int flags)
 {
-  int i;
-  
   /* Write everything. */
   if (_gdbm_end_update (new_dbf))
     {
@@ -145,15 +143,8 @@ _gdbm_finish_transfer (GDBM_FILE dbf, GDBM_FILE new_dbf,
   free (dbf->header);
   free (dbf->dir);
 
-  if (dbf->bucket_cache != NULL)
-    {
-      for (i = 0; i < dbf->cache_size; i++)
-	 {
-	   free (dbf->bucket_cache[i].ca_bucket);
-	   free (dbf->bucket_cache[i].ca_data.dptr);
-	 }
-      free (dbf->bucket_cache);
-   }
+  _gdbm_cache_flush (dbf);
+  _gdbm_cache_free (dbf);
 
   dbf->lock_type         = new_dbf->lock_type;
   dbf->desc              = new_dbf->desc;
@@ -161,9 +152,14 @@ _gdbm_finish_transfer (GDBM_FILE dbf, GDBM_FILE new_dbf,
   dbf->dir               = new_dbf->dir;
   dbf->bucket            = new_dbf->bucket;
   dbf->bucket_dir        = new_dbf->bucket_dir;
-  dbf->last_read         = new_dbf->last_read;
-  dbf->bucket_cache      = new_dbf->bucket_cache;
-  dbf->cache_size        = new_dbf->cache_size;
+
+  dbf->cache_size        = new_dbf->cache_size;  
+  dbf->cache_num         = new_dbf->cache_num;   
+  dbf->cache_tree        = new_dbf->cache_tree;   
+  dbf->cache_entry       = new_dbf->cache_entry;  
+  dbf->cache_lru         = new_dbf->cache_lru;   
+  dbf->cache_avail       = new_dbf->cache_avail;
+  
   dbf->header_changed    = new_dbf->header_changed;
   dbf->directory_changed = new_dbf->directory_changed;
   dbf->bucket_changed    = new_dbf->bucket_changed;
@@ -184,7 +180,6 @@ _gdbm_finish_transfer (GDBM_FILE dbf, GDBM_FILE new_dbf,
   gdbm_file_sync (dbf);
   
   /* Force the right stuff for a correct bucket cache. */
-  dbf->cache_entry    = &dbf->bucket_cache[0];
   return _gdbm_get_bucket (dbf, 0);
 }
 
diff --git a/src/update.c b/src/update.c
index 02aa611..b7d28f9 100644
--- a/src/update.c
+++ b/src/update.c
@@ -74,19 +74,7 @@ _gdbm_end_update (GDBM_FILE dbf)
   /* Write the other changed buckets if there are any. */
   if (dbf->second_changed)
     {
-      if (dbf->bucket_cache != NULL)
-        {
-          int index;
-
-          for (index = 0; index < dbf->cache_size; index++)
-	    {
-	      if (dbf->bucket_cache[index].ca_changed)
-		{
-		  if (_gdbm_write_bucket (dbf, &dbf->bucket_cache[index]))
-		    return -1;
-		}
-            }
-        }
+      _gdbm_cache_flush (dbf);
       dbf->second_changed = FALSE;
     }
   
diff --git a/tests/setopt00.at b/tests/setopt00.at
index 74ee1ca..aee03e7 100644
--- a/tests/setopt00.at
+++ b/tests/setopt00.at
@@ -26,7 +26,7 @@ gtopt test.db '!MMAP'
 * CACHESIZE:
 initial GDBM_SETCACHESIZE: PASS
 GDBM_GETCACHESIZE: PASS
-second GDBM_SETCACHESIZE: XFAIL
+second GDBM_SETCACHESIZE: PASS
 * SYNCMODE:
 initial GDBM_GETSYNCMODE: PASS
 GDBM_SETSYNCMODE: PASS