Documentation fix

Version 2.2.1 merely fixes the incorrect signature of NAME_is_end provided by the in-header documentation and the API Reference.

Thanks go to @ThobiasKnudsen for identifying the issue.

Wyhash, const strings, const function parameters

Version 2.2.0 introduces the following improvements:

• Default support for const char * strings (users no longer need to define their own hash and comparison functions for this type).

• const-qualified table parameter in functions that do not mutate the table.

• Support for -Wextra in GCC and Clang, and explicit documentation of the compiler warning settings that the library supports.

• Wyhash, rather than FNV-1a, as the default hash function for strings. In testing, Wyhash proved to be faster for all but the shortest strings:

  Time to insert and look up 1 million strings (AMD Ryzen 7 5800H)

  strlen	With FNV-1a (old)	With Wyhash (new)	Performance difference
  4	142ms	159ms	1.1x slower
  8	168ms	151ms	1.1x faster
  16	267ms	205ms	1.3x faster
  32	395ms	225ms	1.8x faster
  64	626ms	317ms	2.0x faster
  128	924ms	453ms	2.0x faster

Special thanks go to @kovidgoyal for helping with const char * support.

Big-endian MSVC iteration fix

Version 2.1.1 patches a bug affecting iteration on big-endian platforms when the library is compiled using MSVC. Since big-endian machines running Windows are rare, it is unlikely that any current users are affected. The library has now been specifically tested on a big-endian platform under GCC and Clang (via emulation).

The README has also been updated to link to the recently published article benchmarking Verstable against a range of other C and C++ hash tables.

New integer hash function, rehash bug fix

Version 2.1.0 version introduces two significant changes:

• It replaces the default integer (which was murmur3) to a slightly weaker one (fast-hash) that proved to perform better in benchmarks.
• It fixes a bug that could theoretically cause a crash when the NAME_shrink function prompts a full-table rehash. In testing, I managed to trigger this bug using an (illegal) maximum load factor higher than 1.0.

Extended custom allocator support, destructor bug fix

Version 2.0.0 improves support for custom memory allocators via the introduction of an optional ctx (context) member in the hash table struct.

To enable and specify the type of the ctx member, define CTX_TY before including verstable.h.

When the ctx member is enabled, the custom allocation and free functions supplied via MALLOC_FN and FREE_FN should each take an extra argument, namely a pointer to the table's ctx member: void *( size_t size, CTX_TY *ctx ) for MALLOC_FN and void ( void *ptr, size_t size, CTX_TY *ctx ) and for FREE_FN.

Likewise, init and init_clone should each take an extra argument that sets the ctx member on the newly initialized table struct.

Here is how enabling and using the ctx member might look in practice:

#include <stddef.h>

// Example context data as a struct.
typedef struct
{
  // Context data...
} context;

void *malloc_with_ctx( size_t size, context *ctx )
{
  // Allocate size bytes, taking into account ctx, and return a pointer to the allocated memory or NULL in the case of
  // failure...
}

void free_with_ctx( void *ptr, size_t size, context *ctx )
{
  // Free size bytes, taking into account ctx...
}

#define NAME int_int_map
#define KEY_TY int
#define VAL_TY int
#define CTX_TY context
#define MALLOC_FN malloc_with_ctx
#define FREE_FN free_with_ctx
#include "verstable.h"

int main( void )
{
  context our_ctx;

  // Initialize our_ctx...

  int_int_map our_map;
  vt_init( &our_map, our_ctx );

  // Do things with our_map...

  vt_cleanup( &our_map );
}

This version also introduces various optimizations affecting insertions and lookups and fixes a bug that caused a key to be used after destruction during erasure.

Initial release

This initial release includes the header, two sets of tests, and preliminary benchmarks against several high-performance C++ hash tables.