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

23 files changed, 1466 insertions, 554 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