Rewrite bucket cache

The new bucket cache uses the least recently used replacement
policy (instead of the least recently read, implemented previously).
It also allows for quick bucket lookups by the corresponding
disk address. To this effect the cache entries form a red-black
tree sorted by bucket address.

Additionally, data buckets are also cached.

* README: Describe the new branch.
* src/bucket.c: Rewrite cache support.
* src/cachetree.c: New file.
* src/Makefile.am: Add new file.
* src/findkey.c (_gdbm_read_entry): Use _gdbm_fetch_data.
This ensures data pages are cached as well as buckets.
* src/gdbm.h.in (GDBM_BUCKET_CACHE_CORRUPTED): New error code.
(gdbm_cache_stat): New struct.
(gdbm_get_cache_stats): New proto.
* src/gdbmclose.c (gdbm_close): Call _gdbm_cache_free to dispose
of the cache.
* src/gdbmdefs.h (cache_elem_color): New data type.
(cache_elem): New members: ca_left, ca_right, ca_node, and
ca_hits.
(cache_tree): New typedef.
(gdbm_file_info): Remove bucket_cache and last_read.
New fields: cache_num, cache_tree, cache_mru, cache_lru,
cache_avail, cache_access_count.
* src/gdbmerrno.c: Handle GDBM_BUCKET_CACHE_CORRUPTED.
* src/gdbmopen.c (gdbm_fd_open): Change cache initialization.
(_gdbm_init_cache, _gdbm_cache_entry_invalidate: Remove.
* src/gdbmsetopt.c (setopt_gdbm_setcachesize): Cache can be
re-initialized on the fly.
* src/gdbmtool.c: Change bucket printing routines.
* src/proto.h (_gdbm_read_bucket_at): Remove.
(_gdbm_fetch_data,_gdbm_cache_init,_gdbm_cache_free)
(_gdbm_cache_flush,_gdbm_cache_elem_new)
(_gdbm_cache_tree_alloc,_gdbm_cache_tree_destroy)
(_gdbm_cache_tree_delete,_gdbm_rbt_remove_node)
(_gdbm_cache_tree_lookup): New protos.
(_gdbm_init_cache,_gdbm_cache_entry_invalidate): Remove.
* src/recover.c (_gdbm_finish_transfer): Adapt to the new
cache structure.
* src/update.c: Likewise.
* tests/setopt00.at: Fix second GDBM_SETCACHESIZE test.

1 files changed, 16 insertions, 3 deletions

diff --git a/src/gdbm.h.in b/src/gdbm.h.in
index e537d54..6a23ea6 100644
--- a/src/gdbm.h.in
+++ b/src/gdbm.h.in
@@ -228,9 +228,10 @@ extern int gdbm_copy_meta (GDBM_FILE dst, GDBM_FILE src);
 # define GDBM_FILE_CLOSE_ERROR          37  
 # define GDBM_FILE_SYNC_ERROR           38
 # define GDBM_FILE_TRUNCATE_ERROR       39
-  
+# define GDBM_BUCKET_CACHE_CORRUPTED    40
+
 # define _GDBM_MIN_ERRNO	0
-# define _GDBM_MAX_ERRNO	GDBM_FILE_TRUNCATE_ERROR
+# define _GDBM_MAX_ERRNO	GDBM_BUCKET_CACHE_CORRUPTED
 
 /* This one was never used and will be removed in the future */
 # define GDBM_UNKNOWN_UPDATE GDBM_UNKNOWN_ERROR
@@ -275,8 +276,20 @@ 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_count,
+			   struct gdbm_cache_stat *bstat,
+			   size_t nstat);
   
 # if defined(__cplusplus) || defined(c_plusplus)
 }