/*
* @file
* Code for a cache table, or equivalently a transposition table.
*
* Last Modified: Sat Dec 27 09:15:25 PST 2014
* @author Jim Meyering
* @author Kevin O'Gorman
*/
/* cache - hashing table processing.
Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007 Free
Software Foundation, Inc.
Copyright 2013-2014 Kevin O'Gorman
Written by Jim Meyering, 1992.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software Foundation,
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
/**
* @file
* Code for a cache table, or equivalently a transposition table.
*
* Code for a cache table, or equivalently a transposition table.
* This file is based on hash.c from GNULIB commit 5861339993f3014cfad1b94fc7fe366fc2573598
* so that its licensing agrees with that of Qubist. The functions and code are as similar
* as possible to the original hash.c.
*
* This is a generic cache table package. As used here, a cache table is organized much like
* a hash table, but collisions are handled quite differently. On collision in a cache table,
* a decision is made about which entry to retain; the other is discarded from the cache. Thus, the table never grows or
* shrinks or runs out of space, and more importantly the speed is somewhat better than a hash table and remains so.
* Unlike the original hash package, the cache table size
* is precisely the size requested in the call to cache_initialize(), or else the request
* is rejected. Hash table sizes must be at least 11, and not cause memory allocation to
* fail.
*
* Apropos of the comment "About hashings" in the code, these cache tables' sizes need not be prime,
* partly because of the referenced article's refutation of the common belief that prime
* sizes are optimal for hashtables. It is also in hopes that loosing this restriction allows the
* hash function to be carefully tuned to the exact size.
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "cache.h"
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#ifndef SIZE_MAX
/** A replacement value in case the system does not have it. This is the
* maximum value of a size_t object. It's specified as -1, but is actually
* regarded by the compiler as unsigned, because size_t is an unsigned type.
*/
# define SIZE_MAX ((size_t) -1)
#endif
/**
* Information for the memoization of game positions. This is much like a hash table,
* but simpler because there is no chaining when entries collide; the existing entry
* is simply replaced.
*/
struct cache_table
{
/* Unlike the hash tables on which this code is based, there is no struct
declaration for entries. There's just an array of pointers. They point
to whatever the user considers to be an entry. */
/* The array of bucket pointers starts at BUCKET and extends to BUCKET_LIMIT-1,
for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets
are not empty, there are N_ENTRIES active entries in the table, and
those numbers are identical unless multi-way associativity has been
implemented. */
void **bucket; /**< pointer to an array of bucket pointers */
void **bucket_limit; /**< pointer to the ending bucket */
size_t n_buckets; /**< the number of buckets */
size_t n_entries; /**< the number of buckets with something in them */
size_t tweak; /**< for further development */
/* Three functions are given to `cache_initialize', see the documentation
block for this function. In a word, HASHER randomizes a user entry
into a number up from 0 up to some maximum minus 1; COMPARATOR returns
true if two user entries compare equally; and DATA_FREER is the cleanup
function for a user entry. Data_FREER may be NULL. */
Cache_hasher hasher; /**< pointer to the hash function */
Cache_comparator comparator; /**< pointer to the comparison fumction */
Cache_data_freer data_freer; /**< pointer to the function that frees an entry */
};
/* Information and lookup.
These functions provide information about the overall cache
table organization: the number of entries, number of buckets and maximum
length of buckets. */
/**
* Return the number of buckets in this cache.
* The table size, the total
* number of buckets (used plus unused), or the maximum number of slots, are
* the same quantity.
* @param table a pointer to a cache table.
* @return the number of buckets in this cache.
*/
size_t
cache_get_n_buckets (const Cache_table *table)
{
return table->n_buckets;
}
/** Return the number of active entries.
* @param table a pointer to the cache table.
* @return the number of active entries.
*/
size_t
cache_get_n_entries (const Cache_table *table)
{
return table->n_entries;
}
/**
* Do a mild validation of a cache table, by traversing it and checking two
* statistics.
* @param table a pointer to the cache table.
* @return TRUE if all is okay, otherwise FALSE.
*/
bool
cache_table_ok (const Cache_table *table)
{
void **bucket;
size_t n_entries = 0;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
if (*bucket)
n_entries++;
return n_entries == table->n_entries;
}
/**
* Print statistics on a cache table.
* @param table a pointer to the cache table.
* @param stream the filestream to receive the printout.
*/
void
cache_print_statistics (const Cache_table *table, FILE *stream)
{
/* size_t n_entries = cache_get_n_entries (table); */
size_t n_buckets = cache_get_n_buckets (table);
size_t n_entries = cache_get_n_entries (table);
fprintf (stream, "# buckets: %lu\n", (unsigned long int) n_buckets);
fprintf (stream, "# entries: %lu (%.2f%%)\n",
(unsigned long int) n_entries,
(100.0 * n_entries) / n_buckets);
}
/**
* Return the pointer corresponding to ENTRY, possibly NULL.
* @param table a pointer to the cache table.
* @param entry a pointer to a candidate entry.
* @return a pointer to the current entry, or NULL.
*/
void *
cache_find_bucket(const Cache_table *table, const void *entry)
{
void **bucket
= table->bucket + table->hasher(entry);
if (! (bucket < table->bucket_limit))
abort ();
return *bucket;
}
/**
* If ENTRY matches an entry already in the cache table, return the
* entry from the table. Otherwise, return NULL.
* @param table a pointer to the cache table.
* @param entry a pointer to a candidate entry.
* @return the mathching entry, or NULL.
*/
void *
cache_lookup (const Cache_table *table, const void *entry)
{
void **bucket
= table->bucket + table->hasher(entry);
if (! (bucket < table->bucket_limit))
abort ();
if (!*bucket)
return NULL;
if (table->comparator (entry, *bucket))
return *bucket;
return NULL;
}
/* Walking.
The functions in this page traverse the cache table and process the
contained entries. For the traversal to work properly, the cache table
should not be modified while any particular entry is being
processed. In particular, entries should not be added or removed. */
/**
* Return the first data in the table, or NULL if the table is empty.
* @param table a pointer to the cache table.
* @return a pointer to the first entry.
*/
void *
cache_get_first (const Cache_table *table)
{
void **bucket;
if (table->n_entries == 0)
return NULL;
for (bucket = table->bucket; ; bucket++)
if (! (bucket < table->bucket_limit))
abort ();
else if (*bucket)
return *bucket;
}
/**
* Return the user data for the entry following ENTRY, where ENTRY has been
* returned by a previous call to either `cache_get_first' or `cache_get_next'.
* Return NULL if there are no more entries.
* @param table a pointer to the cache table.
* @param entry a pointer to the current candidate entry.
* @return a pointer to the next entry.
*/
void *
cache_get_next (const Cache_table *table, const void *entry)
{
void **bucket
= table->bucket + table->hasher(entry);
if (! (bucket < table->bucket_limit))
abort ();
/* Find first entry in any subsequent bucket. */
while (++bucket < table->bucket_limit)
if (*bucket)
return *bucket;
/* None found. */
return NULL;
}
/**
* Get a specific entry.
* @param table a pointer to the cache table.
* @param num the index of the desired entry.
* @return a pointer to the entry at index NUM, or NULL if NUM is invalid.
*/
void *
cache_get_entry(const Cache_table *table, int num)
{
if (num < 0 || num >= table->n_buckets) {
return NULL;
} else {
return table->bucket[num];
}
}
/**
* Fill BUFFER with pointers to active user entries in the cache table, then
* return the number of pointers copied. Do not copy more than BUFFER_SIZE
* pointers.
* @param table a pointer to the cache table.
* @param buffer a pointer to the beginning of the memory area to fill.
* @param buffer_size the maximum number of entries to copy.
* @return the number of entries actually copied.
*/
size_t
cache_get_entries (const Cache_table *table, void **buffer,
size_t buffer_size)
{
size_t counter = 0;
void **bucket;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (*bucket)
{
buffer[counter++] = *bucket;
}
}
return counter;
}
/**
* Call a PROCESSOR function for each entry of a cache table, and return the
* number of entries for which the processor function returned success. A
* pointer to some PROCESSOR_DATA which will be made available to each call to
* the processor function. The PROCESSOR accepts two arguments: the first is
* the user entry being walked into, the second is the value of PROCESSOR_DATA
* as received. The walking continue for as long as the PROCESSOR function
* returns nonzero. When it returns zero, the walking is interrupted.
* @param table a pointer to the cache table.
* @param processor a pointer to the function that should be called with each entry.
* @param processor_data a pointer to the data provided.
* @return the number of entries actually processed.
*/
size_t
cache_do_for_each (const Cache_table *table, Cache_processor processor,
void *processor_data)
{
size_t counter = 0;
void **bucket;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (*bucket)
{
if (!(*processor) (*bucket, processor_data))
return counter;
counter++;
}
}
return counter;
}
/* Allocation and clean-up. */
/**
* Allocate and return a new cache table, or NULL upon failure. The number of
* buckets set to the BUCKETS parameter and does not change.
*
* The user-supplied HASHER function should be provided. It accepts one
* argument, ENTRY. It computes, by hashing ENTRY
* contents, a slot number for that entry which should be in the range
* 0..BUCKETS-1. This slot number is then returned. The function must itself
* conform to the allowed range of result values.
*
* The user-supplied COMPARATOR function must be provided. It accepts two
* arguments pointing to user data, it then returns true for a pair of entries
* that compare equal, or false otherwise. This function is internally called
* on entries which are already known to hash to the same bucket index.
*
* The user-supplied DATA_FREER function, when not NULL, may be later called
* with the user data as an argument, just before the entry containing the
* data gets freed. This happens from within `cache_free' or `cache_clear'.
* You should specify this function only if you want these functions to free
* all of your `data' data. This is typically the case when your data is
* simply an auxiliary struct that you have malloc'd to aggregate several
* values, or have allocated from some special memory pool.
* @param buckets the number of buckets to allocate
* @param hasher a pointer to the hash function to use for this table.
* @param comparator a pointer to the function to determine if two entries have the same key.
* @param data_freer a pointer to the function to call with entries that are discarded. May be NULL.
* @return a pointer to the created table.
*/
Cache_table *
cache_initialize (size_t buckets,
Cache_hasher hasher, Cache_comparator comparator,
Cache_data_freer data_freer)
{
Cache_table *table;
/* if (xalloc_oversized (buckets, sizeof *table->bucket)) */
/* test copied from xalloc.h, since I'm otherwise not using xalloc */
if ((size_t) (sizeof (ptrdiff_t) <= sizeof (size_t) ? -1 : -2) / buckets
< (sizeof *table->bucket))
return NULL;
if (hasher == NULL || comparator == NULL)
return NULL;
table = malloc (sizeof *table);
if (table == NULL)
return NULL;
table->n_buckets = buckets;
table->bucket = calloc (table->n_buckets, sizeof(*table->bucket));
if (table->bucket == NULL) {
free (table);
return NULL;
}
table->bucket_limit = table->bucket + buckets;
table->n_entries = 0;
table->hasher = hasher;
table->comparator = comparator;
table->data_freer = data_freer;
return table;
}
/**
* Allocate and return a new cache table, or NULL upon failure. The number of
* buckets set to the BUCKETS parameter and does not change.
*
* The user-supplied HASHER function should be provided. It accepts one
* argument, ENTRY. It computes, by hashing ENTRY
* contents, a slot number for that entry which should be in the range
* 0..BUCKETS-1. This slot number is then returned. The function must itself
* conform to the allowed range of result values.
*
* The user-supplied COMPARATOR function must be provided. It accepts two
* arguments pointing to user data, it then returns true for a pair of entries
* that compare equal, or false otherwise. This function is internally called
* on entries which are already known to hash to the same bucket index.
*
* The user-supplied DATA_FREER function, when not NULL, may be later called
* with the user data as an argument, just before the entry containing the
* data gets freed. This happens from within `cache_free' or `cache_clear'.
* You should specify this function only if you want these functions to free
* all of your `data' data. This is typically the case when your data is
* simply an auxiliary struct that you have malloc'd to aggregate several
* values, or have allocated from some special memory pool.
* @param buckets the number of buckets to allocate
* @param hasher a pointer to the hash function to use for this table.
* @param comparator a pointer to the function to determine if two entries have the same key.
* @param data_freer a pointer to the function to call with entries that are discarded. May be NULL.
* @param vector a pointer to a memory area to use for pointers to entries. This must have a size
* at least (sizeof(void *) * BUCKETS).
* @return a pointer to the created table.
*/
Cache_table *
cache_initialize_with_vector (size_t buckets,
Cache_hasher hasher, Cache_comparator comparator,
Cache_data_freer data_freer,
void *vector)
{
Cache_table *table;
/* if (xalloc_oversized (buckets, sizeof *table->bucket)) */
/* test copied from xalloc.h, since I'm otherwise not using xalloc */
if ((size_t) (sizeof (ptrdiff_t) <= sizeof (size_t) ? -1 : -2) / buckets
< (sizeof *table->bucket))
return NULL;
if (hasher == NULL || comparator == NULL || vector == NULL)
return NULL;
table = malloc (sizeof *table);
if (table == NULL)
return NULL;
table->n_buckets = buckets;
table->bucket = vector;
table->bucket_limit = table->bucket + buckets;
table->n_entries = 0;
table->hasher = hasher;
table->comparator = comparator;
table->data_freer = data_freer;
return table;
}
/** Make all buckets empty. Apply the user-specified function data_freer (if any) to the
* values of any affected entries.
* @param table a pointer to the cache table.
*/
void
cache_clear (Cache_table *table)
{
void **bucket;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (*bucket)
{
/* Free the bucket head. */
if (table->data_freer)
(*table->data_freer) (*bucket);
*bucket = NULL;
}
}
table->n_entries = 0;
table->n_entries = 0;
}
/** Reclaim all storage associated with a cache table. If a data_freer
* function has been supplied by the user when the cache table was created,
* this function applies it to the data of each entry before freeing that
* entry.
* @param table a pointer to the cache table.
*/
void
cache_free (Cache_table *table)
{
void **bucket;
/* Call the user data_freer function. */
if (table->data_freer && table->n_entries)
{
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (*bucket)
{
(*table->data_freer) (*bucket);
}
}
}
/* Free the remainder of the cache table structure. */
free (table->bucket);
free (table);
}
/* Insertion and deletion. */
/**
* Clear a bucket for this entry and insert it.
* If an entry is already present, it is sent
* to the data_freer function.
* @param table a pointer to the cache table.
* @param entry a pointer to the new entry.
*/
void
cache_miss(Cache_table *table, const void *entry)
{
void *data;
void **bucket;
/* The caller may not insert a NULL entry. */
if (! entry)
abort ();
bucket = table->bucket + table->hasher(entry);
if (! (bucket < table->bucket_limit))
abort ();
data = *bucket;
if (data) { /* free any existing entry */
if (*table->data_freer) {
(*table->data_freer) (data);
}
} else {
table->n_entries++;
}
*bucket = (void *)entry; /* insert the new one */
return;
}
/**
* Remove an entry. If ENTRY is already in the table, remove it.
* If ENTRY is not in the table, don't modify the table.
* @param table a pointer to the cache table.
* @param entry a pointer to the entry to invalidate.
*/
void
cache_invalidate(Cache_table *table, const void *entry)
{
void **bucket;
bucket = table->bucket + table->hasher(entry);
if (! (bucket < table->bucket_limit))
abort ();
/* See if the entry is here, delete it. */
if (*bucket && (*table->comparator) (entry, *bucket))
{
void *data = *bucket;
*bucket = NULL;
table->n_entries--;
if (*table->data_freer) {
(*table->data_freer) (data);
}
}
return;
}