/* bucket.c - The routines for playing with hash buckets. */

/* This file is part of GDBM, the GNU data base manager.
   Copyright (C) 1990-2023 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"
#include <stdint.h>
#include <limits.h>

#define GDBM_MAX_DIR_SIZE INT32_MAX
#define GDBM_MAX_DIR_HALF (GDBM_MAX_DIR_SIZE / 2)

/* Initializing a new hash buckets sets all bucket entries to -1 hash value. */
void
_gdbm_new_bucket (GDBM_FILE dbf, hash_bucket *bucket, int bits)
{
  int index;

  /* Initialize the avail block. */
  bucket->av_count = 0;

  /* Set the information fields first. */
  bucket->bucket_bits = bits;
  bucket->count = 0;
  
  /* Initialize all bucket elements. */
  for (index = 0; index < dbf->header->bucket_elems; index++)
    bucket->h_table[index].hash_value = -1;
}

/* Bucket cache table functions */

/* Hash an off_t word into an index of width NBITS. */
static size_t
adrhash (off_t adr, size_t nbits)
{
  adr ^= adr >> (GDBM_HASH_BITS + 1 - nbits); 
  return ((265443576910ul * adr) & 0xffffffff) >> (GDBM_HASH_BITS + 1 - nbits);
}

/*
 * Return a pointer to the cache table slot for bucket address ADR.
 * Never returns NULL.
 */
static cache_elem **
cache_tab_lookup_slot (GDBM_FILE dbf, off_t adr)
{
  cache_elem **cache = dbf->cache;
  size_t h = adrhash (adr, dbf->cache_bits);

  if (cache[h])
    {
      if (cache[h]->ca_adr != adr)
	{
	  cache_elem *prev = cache[h], *p = prev->ca_coll;
	  while (p)
	    {
	      if (p->ca_adr == adr)
		break;
	      prev = p;
	      p = prev->ca_coll;
	    }
	  return &prev->ca_coll;
	}
    }
  return &cache[h];
}

/* LRU list management */

/*
 * Link ELEM after REF in DBF cache.  If REF is NULL, link at head and
 * set DBF->bucket to point to the ca_bucket of ELEM.
 */
static void
lru_link_elem (GDBM_FILE dbf, cache_elem *elem, cache_elem *ref)
{
  if (!ref)
    {
      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;
      dbf->bucket = dbf->cache_mru->ca_bucket;
    }
  else
    {
      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.
 * If cache_mru gets updated, update DBF->bucket accordingly.
 */
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;
      dbf->bucket = dbf->cache_mru ? dbf->cache_mru->ca_bucket : NULL;
    }
  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 = elem->ca_coll = NULL;
  elem->ca_hits = 0;
  
  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)
{
  size_t h = adrhash (elem->ca_adr, dbf->cache_bits);
  cache_elem **pp;
  
  lru_unlink_elem (dbf, elem);

  elem->ca_next = dbf->cache_avail;
  dbf->cache_avail = elem;
  dbf->cache_num--;

  pp = &dbf->cache[h];
  while (*pp)
    {
      if (*pp == elem)
	{
	  *pp = (*pp)->ca_coll;
	  break;
	}
      pp = &(*pp)->ca_coll;
    }      
}

/* 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;
}

/*
 * Round up V to the next highest power of 2 and compute log2 of
 * it using De Brujin sequences.
 * See http://supertech.csail.mit.edu/papers/debruijn.pdf
 */
static unsigned
log2i (unsigned v)
{
  static const int dbp[32] =
    {
      0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

  v--;
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v++;
  return dbp[(uint32_t)(v * 0x077CB531U) >> 27];
}

static int
cache_tab_resize (GDBM_FILE dbf, int bits)
{
  size_t size = 1 << bits;

  if (!dbf->cache || size != dbf->cache_size)
    {
      size_t n = size * sizeof (dbf->cache[0]);
      cache_elem **p, *elem;
      
      /* Flush existing cache */
      if (_gdbm_cache_flush (dbf))
	return -1;

      /* Reallocate it */
      p = realloc (dbf->cache, n);
      if (!p)
	{
	  GDBM_SET_ERRNO (dbf, GDBM_MALLOC_ERROR, FALSE);
	  return -1;
	}
      dbf->cache = p;
      dbf->cache_size = size;
      dbf->cache_bits = bits;

      memset (dbf->cache, 0, n);

      /* Rehash and free surplus elements */
      for (elem = dbf->cache_lru; elem; )
	{
	  cache_elem *prev = elem->ca_prev;
	  elem->ca_coll = NULL;
	  if (size < dbf->cache_num)
	    {
	      cache_elem_free (dbf, elem);
	    }
	  else
	    {
	      p = cache_tab_lookup_slot (dbf, elem->ca_adr);
	      if (*p)
		abort ();// shouldn't happen
	      *p = elem;
	    }
	  elem = prev;
	}
    }
  return 0;
}

enum
  {
    cache_found,
    cache_new,
    cache_failure
  };

static int
cache_lookup (GDBM_FILE dbf, off_t adr, cache_elem *ref, cache_elem **ret_elem)
{
  int rc;
  cache_elem **elp, *elem;
  
  dbf->cache_access_count++;

  elp = cache_tab_lookup_slot (dbf, adr);
  
  if (*elp != NULL)
    {
      elem = *elp;
      elem->ca_hits++;
      dbf->cache_hits++;
      lru_unlink_elem (dbf, elem);
      rc = cache_found;
    }
  else if ((elem = cache_elem_new (dbf, adr)) == NULL)
    return cache_failure;
  else
    {
      rc = cache_new;

      if (dbf->cache_num == dbf->cache_size)
	{
	  if (dbf->cache_auto && dbf->cache_bits < dbf->header->dir_bits &&
	      cache_tab_resize (dbf, dbf->cache_bits + 1) == 0)
	    {
	      /* Table has been reallocated, recompute the slot. */
	      elp = cache_tab_lookup_slot (dbf, adr);
	    }
	  else if (cache_lru_free (dbf))
	    {
	      rc = cache_failure;
	    }
	}
      
      if (rc == cache_new)
	{
	  *elp = elem;
	  dbf->cache_num++;
	}
    }

  /*
   * If the obtained bucket is not changed and is going to become current,
   * flush all changed cache elements.  This ensures that changed cache
   * elements form a contiguous sequence at the head of the cache list (see
   * _gdbm_cache_flush).
   */
  if (ref == NULL && !elem->ca_changed)
    _gdbm_cache_flush (dbf);
  
  lru_link_elem (dbf, elem, ref);
  if (rc != cache_failure)
    *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, the last recently used bucket may be
 * tossed (if the cache is full) to read the new bucket.
 *
 * On success, the cached entry with the requested bucket is placed at
 * the head of the cache list (cache_mru) and the requested bucket becomes
 * "current".
 *
 * On error, the current bucket remains unchanged.
 */
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. */
  hash_bucket *bucket;
  cache_elem *elem;
  
  if (!gdbm_dir_entry_valid_p (dbf, dir_index))
    {
      /* FIXME: negative caching? */
      GDBM_SET_ERRNO (dbf, GDBM_BAD_DIR_ENTRY, TRUE);
      return -1;
    }
  
  /* Initial set up. */
  dbf->bucket_dir = dir_index;
  bucket_adr = dbf->dir[dir_index];

  switch (cache_lookup (dbf, bucket_adr, NULL, &elem))
    {
    case cache_found:
      break;
      
    case cache_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 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;
	}

      /* 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))
	{
	  GDBM_SET_ERRNO (dbf, GDBM_BAD_BUCKET, TRUE);
	  cache_elem_free (dbf, elem);
	  return -1;
	}
      /* Validate bucket_avail table */
      if (gdbm_bucket_avail_table_validate (dbf, bucket))
	{
	  cache_elem_free (dbf, elem);
	  return -1;
	}
      
      /* Update the cache */
      elem->ca_adr = bucket_adr;
      elem->ca_data.elem_loc = -1;
      elem->ca_changed = FALSE;
      
      break;
      
    case cache_failure:
      return -1;
    }
  
  return 0;
}

/* Split the current bucket.  This includes moving all items in the bucket to
   a new bucket.  This doesn't require any disk reads because all hash values
   are stored in the buckets.  Splitting the current bucket may require
   doubling the size of the hash directory.  */
int
_gdbm_split_bucket (GDBM_FILE dbf, int next_insert)
{
  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. */
  
  /* No directories are yet old. */
  old_count = 0;
  while (dbf->bucket->count == dbf->header->bucket_elems)
    {
      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.  They will be populated with the entries
       * from the current bucket (cache_mru->bucket), so make sure that
       * cache_mru remains unchanged until both buckets are fully formed.
       * Newly allocated buckets must be linked right after cache_mru, so
       * that all changed buckets form a contiguous sequence at the beginning
       * of the cache list (this is needed by _gdbm_cache_flush).
       */
      adr_0 = _gdbm_alloc (dbf, dbf->header->bucket_size);
      switch (cache_lookup (dbf, adr_0, dbf->cache_mru, &newcache[0]))
	{
	case cache_new:
	  break;

	case cache_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 cache_failure:
	  return -1;
	}
      _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]))
	{
	case cache_new:
	  break;

	case cache_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 cache_failure:
	  return -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);
	      _gdbm_fatal (dbf, _("directory overflow"));
	      return -1;
	    }
	  dir_size = dbf->header->dir_size * 2;
	  dir_adr  = _gdbm_alloc (dbf, dir_size);
	  if (dir_adr == 0)
	    return -1;
	  new_dir = malloc (dir_size);
	  if (new_dir == NULL)
	    {
	      GDBM_SET_ERRNO (dbf, GDBM_MALLOC_ERROR, TRUE);
	      _gdbm_fatal (dbf, _("malloc error"));
	      return -1;
	    }

	  for (index = 0; index < GDBM_DIR_COUNT (dbf); index++)
	    {
	      new_dir[2*index]   = dbf->dir[index];
	      new_dir[2*index+1] = dbf->dir[index];
	    }
	  
	  /* Update header. */
	  old_adr[old_count] = dbf->header->dir;
	  dbf->header->dir = dir_adr;
	  old_size[old_count] = dbf->header->dir_size;
	  dbf->header->dir_size = dir_size;
	  dbf->header->dir_bits = new_bits;
	  old_count++;
	  
	  /* Now update dbf.  */
	  dbf->header_changed = TRUE;
	  dbf->bucket_dir *= 2;
	  free (dbf->dir);
	  dbf->dir = new_dir;
	}

      /* Copy all elements in dbf->bucket into the new buckets. */
      for (index = 0; index < dbf->header->bucket_elems; index++)
	{
	  bucket_element *old_el = &dbf->bucket->h_table[index];
	  hash_bucket *bucket;
	  int elem_loc;
	  
	  if (old_el->hash_value < 0)
	    {
	      GDBM_SET_ERRNO (dbf, GDBM_BAD_BUCKET, TRUE);
	      return -1;
	    }

	  bucket =
	    newcache[(old_el->hash_value >> (GDBM_HASH_BITS - new_bits)) & 1]->ca_bucket;
	  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->h_table[elem_loc] = *old_el;
	  bucket->count++;
	}
      
      /* 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 (newcache[1]->ca_bucket->bucket_avail[0].av_adr == 0)
	return -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 newcache[0]->ca_bucket. */
      newcache[0]->ca_bucket->av_count = dbf->bucket->av_count;
      index = 0;
      if (newcache[0]->ca_bucket->av_count == BUCKET_AVAIL)
	{
	  /* The avail is full, move the first one to newcache[1]->ca_bucket.*/
	  _gdbm_put_av_elem (dbf->bucket->bucket_avail[0],
			     newcache[1]->ca_bucket->bucket_avail,
			     &newcache[1]->ca_bucket->av_count, 
                             dbf->coalesce_blocks);
	  index = 1;
	  newcache[0]->ca_bucket->av_count--;
	}

      index1 = 0;
      for (; index < dbf->bucket->av_count; index++)
	{
	  newcache[0]->ca_bucket->bucket_avail[index1++]
	    = dbf->bucket->bucket_avail[index];
	}
      
      /* Update the directory.  We have new file addresses for both buckets. */
      dir_start1 = (dbf->bucket_dir >> (dbf->header->dir_bits - new_bits)) | 1;
      dir_end = (dir_start1 + 1) << (dbf->header->dir_bits - new_bits);
      dir_start1 = dir_start1 << (dbf->header->dir_bits - new_bits);
      dir_start0 = dir_start1 - (dir_end - dir_start1);
      for (index = dir_start0; index < dir_start1; index++)
	dbf->dir[index] = adr_0;
      for (index = dir_start1; index < dir_end; index++)
	dbf->dir[index] = adr_1;
      
      /* Set changed flags. */
      newcache[0]->ca_changed = TRUE;
      newcache[1]->ca_changed = TRUE;
      dbf->directory_changed = TRUE;
      
      /* Update the cache! */
      dbf->bucket_dir = _gdbm_bucket_dir (dbf, next_insert);
      
      /* Invalidate old cache entry. */
      old_bucket.av_adr  = dbf->cache_mru->ca_adr;
      old_bucket.av_size = dbf->header->bucket_size;
      cache_elem_free (dbf, dbf->cache_mru);
      
      /* Set dbf->bucket to the proper bucket. */
      if (dbf->dir[dbf->bucket_dir] != adr_0)
	{
	  cache_elem *t = newcache[0];
	  newcache[0] = newcache[1];
	  newcache[1] = t;
	}

      _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);
    }

  /* Get rid of old directories. */
  for (index = 0; index < old_count; index++)
    if (_gdbm_free (dbf, old_adr[index], old_size[index]))
      return -1;

  return 0;
}


/* The only place where a bucket is written.  CA_ENTRY is the
   cache entry containing the bucket to be written. */

int
_gdbm_write_bucket (GDBM_FILE dbf, cache_elem *ca_entry)
{
  int rc;
  off_t file_pos;	/* The return value for lseek. */

  file_pos = gdbm_file_seek (dbf, ca_entry->ca_adr, SEEK_SET);
  if (file_pos != ca_entry->ca_adr)
    {
      GDBM_SET_ERRNO (dbf, GDBM_FILE_SEEK_ERROR, TRUE);
      _gdbm_fatal (dbf, _("lseek error"));
      return -1;
    }
  rc = _gdbm_full_write (dbf, ca_entry->ca_bucket, dbf->header->bucket_size);
  if (rc)
    {
      GDBM_DEBUG (GDBM_DEBUG_STORE|GDBM_DEBUG_ERR,
		  "%s: error writing bucket: %s",
		  dbf->name, gdbm_db_strerror (dbf));	  
      _gdbm_fatal (dbf, gdbm_strerror (rc));
      return -1;
    }

  ca_entry->ca_changed = FALSE;
  ca_entry->ca_data.hash_val = -1;
  ca_entry->ca_data.elem_loc = -1;
  return 0;
}

/* Cache manipulation interface functions. */

#define INIT_CACHE_BITS 9

/* Initialize the bucket cache. */
int
_gdbm_cache_init (GDBM_FILE dbf, size_t size)
{
  int bits;
  int cache_auto;
  
  if (size == GDBM_CACHE_AUTO)
    {
      cache_auto = TRUE;
      bits = dbf->cache ? dbf->cache_bits : INIT_CACHE_BITS;
    }
  else if (size > SIZE_T_MAX / sizeof (dbf->cache[0]))
    {
      GDBM_SET_ERRNO (dbf, GDBM_OPT_BADVAL, FALSE);
      return -1;
    }
  else
    {
      cache_auto = FALSE;
      bits = log2i (size < 4 ? 4 : size);
    }

  dbf->cache_auto = cache_auto;

  return cache_tab_resize (dbf, bits);
}

/* 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);
  free (dbf->cache);
  dbf->cache = NULL;
  while ((elem = dbf->cache_avail) != NULL)
    {
      dbf->cache_avail = elem->ca_next;
      free (elem->ca_data.dptr);
      free (elem);
    }
}

/*
 * Flush cache content to disk.
 * All cache elements with the changed buckets form a contiguous sequence
 * at the head of the cache list (starting with cache_mru).
 */
int
_gdbm_cache_flush (GDBM_FILE dbf)
{
  cache_elem *elem;
  for (elem = dbf->cache_mru; elem && elem->ca_changed; elem = elem->ca_next)
    {
      if (_gdbm_write_bucket (dbf, elem))
	return -1;
    }
  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;
	}
    }
}