jacksonallan / verstable Goto Github PK

A versatile, performance-oriented generic hash table library for C.

License: MIT License

C 100.00%

c generics hashmaps hashtables maps sets

verstable's Introduction

Verstable

Verstable is a versatile generic hash table intended to bring the speed and memory efficiency of state-of-the-art C++ hash tables such as Abseil/Swiss, Boost, and Bytell to C.

Its features include:

API:

Type safety.
Customizable hash, comparison, and destructor functions.
Single header.
C99 compatibility.
Generic API in C11 and later.

Performance:

High speed mostly impervious to load factor.
Only two bytes of overhead per bucket.
Tombstone-free deletion.

Extensive benchmarks comparing Verstable to a range of other C and C++ hash tables, including Robin Hood tables and SIMD-accelerated tables, are available here.

Verstable is distributed under the MIT license.

Try it online here.

A variation of Verstable is also available as part of the broader generic data-structure library Convenient Containers.

Installation

Just download verstable.h and place it in your project's directory or your common header directory.

Example

Using the generic macro API (C11 and later):

#include <stdio.h>

// Instantiating a set template.
#define NAME int_set
#define KEY_TY int
#include "verstable.h"

// Instantiating a map template.
#define NAME int_int_map
#define KEY_TY int
#define VAL_TY int
#include "verstable.h"

int main( void )
{
  // Set.

  int_set our_set;
  vt_init( &our_set );

  // Inserting keys.
  for( int i = 0; i < 10; ++i )
  {
    int_set_itr itr = vt_insert( &our_set, i );
    if( vt_is_end( itr ) )
    {
      // Out of memory, so abort.
      vt_cleanup( &our_set );
      return 1;
    }
  }

  // Erasing keys.
  for( int i = 0; i < 10; i += 3 )
    vt_erase( &our_set, i );

  // Retrieving keys.
  for( int i = 0; i < 10; ++i )
  {
    int_set_itr itr = vt_get( &our_set, i );
    if( !vt_is_end( itr ) )
      printf( "%d ", itr.data->key );
  }
  // Printed: 1 2 4 5 7 8

  // Iteration.
  for(
    int_set_itr itr = vt_first( &our_set );
    !vt_is_end( itr );
    itr = vt_next( itr )
  )
    printf( "%d ", itr.data->key );
  // Printed: 2 4 7 1 5 8

  vt_cleanup( &our_set );

  // Map.

  int_int_map our_map;
  vt_init( &our_map );

  // Inserting keys and values.
  for( int i = 0; i < 10; ++i )
  {
    int_int_map_itr itr =
      vt_insert( &our_map, i, i + 1 );
    if( vt_is_end( itr ) )
    {
      // Out of memory, so abort.
      vt_cleanup( &our_map );
      return 1;
    }
  }

  // Erasing keys and values.
  for( int i = 0; i < 10; i += 3 )
    vt_erase( &our_map, i );

  // Retrieving keys and values.
  for( int i = 0; i < 10; ++i )
  {
    int_int_map_itr itr = vt_get( &our_map, i );
    if( !vt_is_end( itr ) )
      printf(
        "%d:%d ",
        itr.data->key,
        itr.data->val
      );
  }
  // Printed: 1:2 2:3 4:5 5:6 7:8 8:9

  // Iteration.
  for(
    int_int_map_itr itr = vt_first( &our_map );
    !vt_is_end( itr );
    itr = vt_next( itr )
  )
    printf(
      "%d:%d ",
      itr.data->key,
      itr.data->val
    );
  // Printed: 2:3 4:5 7:8 1:2 5:6 8:9

  vt_cleanup( &our_map );
}

Using the prefixed functions API (C99 and later):

#include <stdio.h>

// Instantiating a set template.
#define NAME int_set
#define KEY_TY int
#define HASH_FN vt_hash_integer
#define CMPR_FN vt_cmpr_integer
#include "verstable.h"

// Instantiating a map template.
#define NAME int_int_map
#define KEY_TY int
#define VAL_TY int
#define HASH_FN vt_hash_integer
#define CMPR_FN vt_cmpr_integer
#include "verstable.h"

int main( void )
{
  // Set.

  int_set our_set;
  int_set_init( &our_set );

  // Inserting keys.
  for( int i = 0; i < 10; ++i )
  {
    int_set_itr itr =
      int_set_insert( &our_set, i );
    if( int_set_is_end( itr ) )
    {
      // Out of memory, so abort.
      int_set_cleanup( &our_set );
      return 1;
    }
  }

  // Erasing keys.
  for( int i = 0; i < 10; i += 3 )
    int_set_erase( &our_set, i );

  // Retrieving keys.
  for( int i = 0; i < 10; ++i )
  {
    int_set_itr itr = int_set_get( &our_set, i );
    if( !int_set_is_end( itr ) )
      printf( "%d ", itr.data->key );
  }
  // Printed: 1 2 4 5 7 8

  // Iteration.
  for(
    int_set_itr itr =
      int_set_first( &our_set );
    !int_set_is_end( itr );
    itr = int_set_next( itr )
  )
    printf( "%d ", itr.data->key );
  // Printed: 2 4 7 1 5 8

  int_set_cleanup( &our_set );

  // Map.

  int_int_map our_map;
  int_int_map_init( &our_map );

  // Inserting keys and values.
  for( int i = 0; i < 10; ++i )
  {
    int_int_map_itr itr =
      int_int_map_insert( &our_map, i, i + 1 );
    if( int_int_map_is_end( itr ) )
    {
      // Out of memory, so abort.
      int_int_map_cleanup( &our_map );
      return 1;
    }
  }

  // Erasing keys and values.
  for( int i = 0; i < 10; i += 3 )
    int_int_map_erase( &our_map, i );

  // Retrieving keys and values.
  for( int i = 0; i < 10; ++i )
  {
    int_int_map_itr itr =
      int_int_map_get( &our_map, i );
    if( !int_int_map_is_end( itr ) )
      printf(
      	"%d:%d ",
      	itr.data->key,
      	itr.data->val
    );
  }
  // Printed: 1:2 2:3 4:5 5:6 7:8 8:9

  // Iteration.
  for(
    int_int_map_itr itr =
      int_int_map_first( &our_map );
    !int_int_map_is_end( itr );
    itr = int_int_map_next( itr )
  )
    printf(
      "%d:%d ",
      itr.data->key,
      itr.data->val
    );
  // Printed: 2:3 4:5 7:8 1:2 5:6 8:9

  int_int_map_cleanup( &our_map );
}

API

Full API documentation is available here.

FAQ

How does it work?

Verstable is an open-addressing hash table using quadratic probing and the following additions:

All keys that hash (i.e. "belong") to the same bucket (their "home bucket") are linked together by an 11-bit integer specifying the quadratic displacement, relative to that bucket, of the next key in the chain.
If a chain of keys exists for a given bucket, then it always begins at that bucket. To maintain this policy, a 1-bit flag is used to mark whether the key occupying a bucket belongs there. When inserting a new key, if the bucket it belongs to is occupied by a key that does not belong there, then the occupying key is evicted and the new key takes the bucket.
A 4-bit fragment of each key's hash code is also stored.
The aforementioned metadata associated with each bucket (the 4-bit hash fragment, the 1-bit flag, and the 11-bit link to the next key in the chain) are stored together in a uint16_t array rather than in the bucket alongside the key and (optionally) the value.

One way to conceptualize this scheme is as a chained hash table in which overflowing keys are stored not in separate memory allocations but in otherwise unused buckets. In this regard, it shares similarities with Malte Skarupke’s Bytell hash table and traditional "coalesced hashing".

Advantages of this scheme include:

Fast lookups impervious to load factor: If the table contains any key belonging to the lookup key's home bucket, then that bucket contains the first in a traversable chain of all keys belonging to it. Hence, only the home bucket and other buckets containing keys belonging to it are ever probed. Moreover, the stored hash fragments allow skipping most non-matching keys in the chain without accessing the actual buckets array or calling the (potentially expensive) key comparison function.
Fast insertions: Insertions are faster than they are in other schemes that move keys around (e.g. Robin Hood) because they only move, at most, one existing key.
Fast, tombstone-free deletions: Deletions, which usually require tombstones in quadratic-probing hash tables, are tombstone-free and only move, at most, one existing key.
Fast iteration: The separate metadata array allows keys in sparsely populated tables to be found without incurring the frequent cache misses that would result from traversing the buckets array.

The generic macro API available in C11 is based on the extendible-_Generic mechanism detailed here.

How is it tested?

Verstable has been tested under GCC, Clang, MinGW, and MSVC. tests/unit_tests.c includes unit tests for sets and maps, with an emphasis on corner cases. tests/tests_against_stl.cpp includes randomized tests that perform the same operations on Verstable sets and maps, on one hand, and C++'s std::unordered_set and std::unordered_map, on the other, and then check that they remain in sync. Both test suites use a tracking and randomly failing memory allocator in order to detect memory leaks and test out-of-memory conditions.

Why the name?

The name is a contraction of "versatile table". Verstable handles various conditions that strain other hash table schemes—such as large keys or values that are expensive to move, high load factors, expensive hash or comparison functions, and frequent deletions, iteration, and unsuccessful lookups—without significant performance loss. In other words, it is designed to be a good default choice of hash table for most use cases.

verstable's People

Contributors

Stargazers

Watchers

Forkers

skeeto lzralbu incrediblejr yrashk rsmarples fuxfork joshinnis kovidgoyal fonghou

verstable's Issues

Use of memory after it is freed

Reproduer:

// Instantiating a map template.
#define NAME int_int_map
#define KEY_TY int
#define VAL_TY int
#include "verstable.h"

int main(void)
{
    int_int_map our_map;
    int_int_map_itr itr;

    int_int_map_init(&our_map);
    itr = int_int_map_insert(&our_map, 1, 1);
    if (int_int_map_is_end(itr))
    {
        exit(1);
    }
    int_int_map_cleanup(&our_map);
    exit(0);
}

$ clang-tidy -checks=cert-* repro.c
verstable.h:1299:11: note: Use of memory after it is freed
 1299 |           FREE_FN(
      |           ^
 1300 |             new_table.buckets,

cast discards 'const' qualifier from pointer target type

../vendor/verstable/verstable.h: In function 'vt_first_nonzero_uint16':
../vendor/verstable/verstable.h:474:8: error: cast discards 'const' qualifier from pointer target type [-Werror=cast-qual]
  474 |   if( *(char *)&endian_checker ) // Little-endian (the compiler will optimize away the check at -O1 and above).
      |        ^
../vendor/verstable/verstable.h: In function 'path_access_map_init':
../vendor/verstable/verstable.h:902:21: error: cast discards 'const' qualifier from pointer target type [-Werror=cast-qual]
  902 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../vendor/verstable/verstable.h: In function 'path_access_map_init_clone':
../vendor/verstable/verstable.h:948:23: error: cast discards 'const' qualifier from pointer target type [-Werror=cast-qual]
  948 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../vendor/verstable/verstable.h: In function 'path_access_map_shrink':
../vendor/verstable/verstable.h:1627:23: error: cast discards 'const' qualifier from pointer target type [-Werror=cast-qual]
 1627 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^

Support for Clang-Tidy

In parallel with #10, it might be nice for Verstable to “support” Clang-Tidy by raising as few diagnostic warnings as possible.

Currently, Clang-Tidy is detecting many false positive NULL-dereferences regarding the buckets array pointer. This might be because it is not following the logic of the metadata “placeholder” mechanism and implicit guarantees it provides ensuring that buckets, when accessed, is not NULL.

These and other warnings could be silenced via liberal use of // NOLINT, although I am unsure about adding to the library any comments (or other content) whose purpose isn’t obvious. Such comments could perhaps be qualified with further comments explaining why they are necessary.

I’m opening this issue to keep a record and remind myself to investigate the matter further.

Relevant issues and pull requests:
#8
#9

Support for optional compiler diagnostics

Currently, Verstable specifically supports the following compiler diagnostics settings: -Wall -Wextra -pedantic in GCC and Clang and /W4 in MSVC. However, it could be beneficial, from the standpoint of user experience and stricter quality control, to support some commonly used additional warnings. For example, @rsmarples has indicated that in addition to the above GCC/Clang warnings, he uses the following:

-Wundef
-Wmissing-prototypes
-Wmissing-declarations
-Wmissing-format-attribute
-Wnested-externs
-Wcast-align
-Wpointer-arith
-Wreturn-type
-Wswitch
-Wshadow
-Wcast-qual
-Wwrite-strings
-Wformat=2
-Wpointer-sign
-Wmissing-noreturn

With these settings, unit_tests.c generates the following warnings:

unit_tests.c:53:7: warning: no previous prototype for 'unreliable_tracking_malloc' [-Wmissing-prototypes]
   53 | void *unreliable_tracking_malloc( size_t size )
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~
unit_tests.c:71:6: warning: no previous prototype for 'tracking_free' [-Wmissing-prototypes]
   71 | void tracking_free( void *ptr, size_t size )
      |      ^~~~~~~~~~~~~
unit_tests.c:90:7: warning: no previous prototype for 'unreliable_tracking_malloc_with_ctx' [-Wmissing-prototypes]
   90 | void *unreliable_tracking_malloc_with_ctx( size_t size, context *ctx )
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
unit_tests.c:101:6: warning: no previous prototype for 'tracking_free_with_ctx' [-Wmissing-prototypes]
  101 | void tracking_free_with_ctx( void *ptr, size_t size, context *ctx )
      |      ^~~~~~~~~~~~~~~~~~~~~~
unit_tests.c:111:6: warning: no previous prototype for 'dtor' [-Wmissing-prototypes]
  111 | void dtor( uint64_t key_or_val )
      |      ^~~~
unit_tests.c:116:6: warning: no previous prototype for 'check_dtors_arr' [-Wmissing-prototypes]
  116 | void check_dtors_arr( void )
      |      ^~~~~~~~~~~~~~~
In file included from unit_tests.c:137:
../verstable.h: In function 'integer_map_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'integer_map_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'integer_map_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:147:
../verstable.h: In function 'integer_dtors_map_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'integer_dtors_map_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'integer_dtors_map_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:155:
../verstable.h: In function 'string_map_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'string_map_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'string_map_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:162:
../verstable.h: In function 'integer_set_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'integer_set_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'integer_set_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:170:
../verstable.h: In function 'integer_dtors_set_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'integer_dtors_set_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'integer_dtors_set_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:177:
../verstable.h: In function 'string_set_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'string_set_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'string_set_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:186:
../verstable.h: In function 'integer_map_with_ctx_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'integer_map_with_ctx_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'integer_map_with_ctx_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
In file included from unit_tests.c:194:
../verstable.h: In function 'integer_set_with_ctx_init':
../verstable.h:906:21: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  906 |   table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                     ^
../verstable.h: In function 'integer_set_with_ctx_init_clone':
../verstable.h:952:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
  952 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
../verstable.h: In function 'integer_set_with_ctx_shrink':
../verstable.h:1637:23: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
 1637 |     table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum;
      |                       ^
unit_tests.c: At top level:
unit_tests.c:198:6: warning: no previous prototype for 'test_map_reserve' [-Wmissing-prototypes]
  198 | void test_map_reserve( void )
      |      ^~~~~~~~~~~~~~~~
unit_tests.c:240:6: warning: no previous prototype for 'test_map_shrink' [-Wmissing-prototypes]
  240 | void test_map_shrink( void )
      |      ^~~~~~~~~~~~~~~
unit_tests.c:287:6: warning: no previous prototype for 'test_map_insert' [-Wmissing-prototypes]
  287 | void test_map_insert( void )
      |      ^~~~~~~~~~~~~~~
unit_tests.c:319:6: warning: no previous prototype for 'test_map_get_or_insert' [-Wmissing-prototypes]
  319 | void test_map_get_or_insert( void )
      |      ^~~~~~~~~~~~~~~~~~~~~~
unit_tests.c:354:6: warning: no previous prototype for 'test_map_get' [-Wmissing-prototypes]
  354 | void test_map_get( void )
      |      ^~~~~~~~~~~~
unit_tests.c:380:6: warning: no previous prototype for 'test_map_erase' [-Wmissing-prototypes]
  380 | void test_map_erase( void )
      |      ^~~~~~~~~~~~~~
unit_tests.c:414:6: warning: no previous prototype for 'test_map_erase_itr' [-Wmissing-prototypes]
  414 | void test_map_erase_itr( void )
      |      ^~~~~~~~~~~~~~~~~~
unit_tests.c:473:6: warning: no previous prototype for 'test_map_clear' [-Wmissing-prototypes]
  473 | void test_map_clear( void )
      |      ^~~~~~~~~~~~~~
unit_tests.c:504:6: warning: no previous prototype for 'test_map_cleanup' [-Wmissing-prototypes]
  504 | void test_map_cleanup( void )
      |      ^~~~~~~~~~~~~~~~
unit_tests.c:534:6: warning: no previous prototype for 'test_map_init_clone' [-Wmissing-prototypes]
  534 | void test_map_init_clone( void )
      |      ^~~~~~~~~~~~~~~~~~~
unit_tests.c:563:6: warning: no previous prototype for 'test_map_iteration' [-Wmissing-prototypes]
  563 | void test_map_iteration( void )
      |      ^~~~~~~~~~~~~~~~~~
unit_tests.c:600:6: warning: no previous prototype for 'test_map_dtors' [-Wmissing-prototypes]
  600 | void test_map_dtors( void )
      |      ^~~~~~~~~~~~~~
unit_tests.c:638:6: warning: no previous prototype for 'test_map_strings' [-Wmissing-prototypes]
  638 | void test_map_strings( void )
      |      ^~~~~~~~~~~~~~~~
unit_tests.c: In function 'test_map_strings':
unit_tests.c:646:57: warning: passing argument 2 of 'vt_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                                         ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:646:19: note: in expansion of macro 'vt_is_end'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:646:36: note: in expansion of macro 'vt_insert'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:646:65: warning: passing argument 3 of 'vt_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                                                 ^~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:646:19: note: in expansion of macro 'vt_is_end'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:646:36: note: in expansion of macro 'vt_insert'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1767:12: note: expected 'char *' but argument is of type 'const char *'
 1767 |   , VAL_TY val
unit_tests.c:646:57: warning: passing argument 2 of 'vt_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                                         ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:646:19: note: in expansion of macro 'vt_is_end'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:646:36: note: in expansion of macro 'vt_insert'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:646:65: warning: passing argument 3 of 'vt_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                                                 ^~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:646:19: note: in expansion of macro 'vt_is_end'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:646:36: note: in expansion of macro 'vt_insert'
  646 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_map, "This", "is" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1767:12: note: expected 'char *' but argument is of type 'const char *'
 1767 |   , VAL_TY val
unit_tests.c:648:64: warning: passing argument 2 of 'vt_get_or_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                                                ^~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:648:19: note: in expansion of macro 'vt_is_end'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:648:36: note: in expansion of macro 'vt_get_or_insert'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                    ^~~~~~~~~~~~~~~~
../verstable.h:1782:10: note: expected 'char *' but argument is of type 'const char *'
 1782 |   KEY_TY key
unit_tests.c:648:69: warning: passing argument 3 of 'vt_get_or_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                                                     ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:648:19: note: in expansion of macro 'vt_is_end'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:648:36: note: in expansion of macro 'vt_get_or_insert'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                    ^~~~~~~~~~~~~~~~
../verstable.h:1784:12: note: expected 'char *' but argument is of type 'const char *'
 1784 |   , VAL_TY val
unit_tests.c:648:64: warning: passing argument 2 of 'vt_get_or_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                                                ^~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:648:19: note: in expansion of macro 'vt_is_end'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:648:36: note: in expansion of macro 'vt_get_or_insert'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                    ^~~~~~~~~~~~~~~~
../verstable.h:1782:10: note: expected 'char *' but argument is of type 'const char *'
 1782 |   KEY_TY key
unit_tests.c:648:69: warning: passing argument 3 of 'vt_get_or_insert_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                                                     ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:648:19: note: in expansion of macro 'vt_is_end'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:648:36: note: in expansion of macro 'vt_get_or_insert'
  648 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_get_or_insert( &our_map, "a", "test" ) ) );
      |                                    ^~~~~~~~~~~~~~~~
../verstable.h:1784:12: note: expected 'char *' but argument is of type 'const char *'
 1784 |   , VAL_TY val
unit_tests.c:664:44: warning: passing argument 2 of 'vt_get_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  664 |   ALWAYS_ASSERT( strcmp( vt_get( &our_map, "This" ).data->val, "is" ) == 0 );
      |                                            ^~~~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:664:26: note: in expansion of macro 'vt_get'
  664 |   ALWAYS_ASSERT( strcmp( vt_get( &our_map, "This" ).data->val, "is" ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:665:44: warning: passing argument 2 of 'vt_get_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  665 |   ALWAYS_ASSERT( strcmp( vt_get( &our_map, "a" ).data->val, "test" ) == 0 );
      |                                            ^~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:665:26: note: in expansion of macro 'vt_get'
  665 |   ALWAYS_ASSERT( strcmp( vt_get( &our_map, "a" ).data->val, "test" ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:673:23: warning: passing argument 2 of 'vt_erase_0002' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  673 |   vt_erase( &our_map, "This" );
      |                       ^~~~~~
../verstable.h:672:104: note: in definition of macro 'vt_erase'
  672 | #define vt_erase( table, ... ) _Generic( *( table ) VT_GENERIC_SLOTS( vt_table_, vt_erase_ ) )( table, __VA_ARGS__ )
      |                                                                                                        ^~~~~~~~~~~
../verstable.h:1802:80: note: expected 'char *' but argument is of type 'const char *'
 1802 | static inline bool VT_CAT( vt_erase_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c: At top level:
unit_tests.c:688:6: warning: no previous prototype for 'test_map_with_ctx' [-Wmissing-prototypes]
  688 | void test_map_with_ctx( void )
      |      ^~~~~~~~~~~~~~~~~
unit_tests.c:727:6: warning: no previous prototype for 'test_set_reserve' [-Wmissing-prototypes]
  727 | void test_set_reserve( void )
      |      ^~~~~~~~~~~~~~~~
unit_tests.c:769:6: warning: no previous prototype for 'test_set_shrink' [-Wmissing-prototypes]
  769 | void test_set_shrink( void )
      |      ^~~~~~~~~~~~~~~
unit_tests.c:816:6: warning: no previous prototype for 'test_set_insert' [-Wmissing-prototypes]
  816 | void test_set_insert( void )
      |      ^~~~~~~~~~~~~~~
unit_tests.c:848:6: warning: no previous prototype for 'test_set_get_or_insert' [-Wmissing-prototypes]
  848 | void test_set_get_or_insert( void )
      |      ^~~~~~~~~~~~~~~~~~~~~~
unit_tests.c:883:6: warning: no previous prototype for 'test_set_get' [-Wmissing-prototypes]
  883 | void test_set_get( void )
      |      ^~~~~~~~~~~~
unit_tests.c:909:6: warning: no previous prototype for 'test_set_erase' [-Wmissing-prototypes]
  909 | void test_set_erase( void )
      |      ^~~~~~~~~~~~~~
unit_tests.c:943:6: warning: no previous prototype for 'test_set_erase_itr' [-Wmissing-prototypes]
  943 | void test_set_erase_itr( void )
      |      ^~~~~~~~~~~~~~~~~~
unit_tests.c:1002:6: warning: no previous prototype for 'test_set_clear' [-Wmissing-prototypes]
 1002 | void test_set_clear( void )
      |      ^~~~~~~~~~~~~~
unit_tests.c:1033:6: warning: no previous prototype for 'test_set_cleanup' [-Wmissing-prototypes]
 1033 | void test_set_cleanup( void )
      |      ^~~~~~~~~~~~~~~~
unit_tests.c:1063:6: warning: no previous prototype for 'test_set_init_clone' [-Wmissing-prototypes]
 1063 | void test_set_init_clone( void )
      |      ^~~~~~~~~~~~~~~~~~~
unit_tests.c:1092:6: warning: no previous prototype for 'test_set_iteration' [-Wmissing-prototypes]
 1092 | void test_set_iteration( void )
      |      ^~~~~~~~~~~~~~~~~~
unit_tests.c:1129:6: warning: no previous prototype for 'test_set_dtors' [-Wmissing-prototypes]
 1129 | void test_set_dtors( void )
      |      ^~~~~~~~~~~~~~
unit_tests.c:1166:6: warning: no previous prototype for 'test_set_strings' [-Wmissing-prototypes]
 1166 | void test_set_strings( void )
      |      ^~~~~~~~~~~~~~~~
unit_tests.c: In function 'test_set_strings':
unit_tests.c:1174:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1174 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "This" ) ) );
      |                                                         ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1174:19: note: in expansion of macro 'vt_is_end'
 1174 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "This" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1174:36: note: in expansion of macro 'vt_insert'
 1174 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "This" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1174:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1174 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "This" ) ) );
      |                                                         ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1174:19: note: in expansion of macro 'vt_is_end'
 1174 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "This" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1174:36: note: in expansion of macro 'vt_insert'
 1174 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "This" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1176:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1176 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "is" ) ) );
      |                                                         ^~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1176:19: note: in expansion of macro 'vt_is_end'
 1176 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "is" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1176:36: note: in expansion of macro 'vt_insert'
 1176 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "is" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1176:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1176 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "is" ) ) );
      |                                                         ^~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1176:19: note: in expansion of macro 'vt_is_end'
 1176 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "is" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1176:36: note: in expansion of macro 'vt_insert'
 1176 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "is" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1178:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1178 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "a" ) ) );
      |                                                         ^~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1178:19: note: in expansion of macro 'vt_is_end'
 1178 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "a" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1178:36: note: in expansion of macro 'vt_insert'
 1178 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "a" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1178:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1178 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "a" ) ) );
      |                                                         ^~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1178:19: note: in expansion of macro 'vt_is_end'
 1178 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "a" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1178:36: note: in expansion of macro 'vt_insert'
 1178 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "a" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1180:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1180 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "test" ) ) );
      |                                                         ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1180:19: note: in expansion of macro 'vt_is_end'
 1180 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "test" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1180:36: note: in expansion of macro 'vt_insert'
 1180 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "test" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1180:57: warning: passing argument 2 of 'vt_insert_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1180 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "test" ) ) );
      |                                                         ^~~~~~
unit_tests.c:42:38: note: in definition of macro 'UNTIL_SUCCESS'
   42 | #define UNTIL_SUCCESS( xp ) while( !(xp) )
      |                                      ^~
unit_tests.c:1180:19: note: in expansion of macro 'vt_is_end'
 1180 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "test" ) ) );
      |                   ^~~~~~~~~
unit_tests.c:1180:36: note: in expansion of macro 'vt_insert'
 1180 |   UNTIL_SUCCESS( !vt_is_end( itr = vt_insert( &our_set, "test" ) ) );
      |                                    ^~~~~~~~~
../verstable.h:1765:10: note: expected 'char *' but argument is of type 'const char *'
 1765 |   KEY_TY key
unit_tests.c:1200:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1200 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "This" ).data->key, "This" ) == 0 );
      |                                            ^~~~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1200:26: note: in expansion of macro 'vt_get'
 1200 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "This" ).data->key, "This" ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1201:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1201 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "is" ).data->key, "is" ) == 0 );
      |                                            ^~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1201:26: note: in expansion of macro 'vt_get'
 1201 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "is" ).data->key, "is" ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1202:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1202 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "a" ).data->key, "a" ) == 0 );
      |                                            ^~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1202:26: note: in expansion of macro 'vt_get'
 1202 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "a" ).data->key, "a" ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1203:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1203 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "test" ).data->key, "test" ) == 0 );
      |                                            ^~~~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1203:26: note: in expansion of macro 'vt_get'
 1203 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "test" ).data->key, "test" ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1204:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1204 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "of" ).data->key, str_1 ) == 0 );
      |                                            ^~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1204:26: note: in expansion of macro 'vt_get'
 1204 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "of" ).data->key, str_1 ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1205:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1205 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "sets" ).data->key, str_2 ) == 0 );
      |                                            ^~~~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1205:26: note: in expansion of macro 'vt_get'
 1205 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "sets" ).data->key, str_2 ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1206:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1206 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "with" ).data->key, str_3 ) == 0 );
      |                                            ^~~~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1206:26: note: in expansion of macro 'vt_get'
 1206 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "with" ).data->key, str_3 ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c:1207:44: warning: passing argument 2 of 'vt_get_0005' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
 1207 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "strings" ).data->key, str_4 ) == 0 );
      |                                            ^~~~~~~~~
unit_tests.c:35:4: note: in definition of macro 'ALWAYS_ASSERT'
   35 | ( (xp) ? (void)0 : ( fprintf( stderr, "Assertion failed at line %d: %s\n", __LINE__, #xp ), exit( 0 ) ) ) \
      |    ^~
unit_tests.c:1207:26: note: in expansion of macro 'vt_get'
 1207 |   ALWAYS_ASSERT( strcmp( vt_get( &our_set, "strings" ).data->key, str_4 ) == 0 );
      |                          ^~~~~~
../verstable.h:1797:94: note: expected 'char *' but argument is of type 'const char *'
 1797 | static inline VT_CAT( NAME, _itr ) VT_CAT( vt_get_, VT_TEMPLATE_COUNT )( NAME *table, KEY_TY key )
unit_tests.c: At top level:
unit_tests.c:1212:6: warning: no previous prototype for 'test_set_with_ctx' [-Wmissing-prototypes]
 1212 | void test_set_with_ctx( void )
      |      ^~~~~~~~~~~~~~~~~

So at present and with these settings, GCC (and probably Clang) is complaining about the following:

-Wmissing-prototypes for functions in unit_tests.c. In my view, these warnings (and, by extension, this flag) are rather extreme. These functions are ordered such that they don't require prototypes. Nevertheless, the warnings could perhaps be silenced by (superfluously) defining these functions as static.
-Wcast-qual for the various occurrences of table->metadata = (uint16_t *)&vt_empty_placeholder_metadatum; in verstable.h. The uint16_t * cast here is included specifically for the purpose of discarding const. @rsmarples has suggested that the warning can be silenced via an intermediate cast to void *. However, if we are to support -Wcast-qual, I would prefer explicitly disabling the warning via #pragma GCC diagnostic ignored over the void * workaround, which isn't as clear and isn't guaranteed to work in the long term.
-Wdiscarded-qualifiers for the calls to hash-table functions in unit_tests.h when the key argument is an (implicitly const) string literal. This warning probably occurs when any const pointer is passed as a key or value into hash-table functions. Supporting it would require introducing const correctness into function parameters throughout the library (possibly also for the table argument), which would be a major quality improvement.

I've opened the issue to centralize discussion and create a space for users to request support for other diagnostic flags.

Relevant issues and pull requests:
#6
#7

Compile Error on gcc 4.8.5

#include <stdio.h>

#define NAME int_int_map
#define KEY_TY int 
#define VAL_TY int  
#include "verstable.h"

int main(int argc, char const *argv[])
{
    int_int_map htable;
    vt_init(&htable);

    return 0;
}

[root@DESKTOP-OAKHD5F src]# gcc -std=c11 main.c 
In file included from main.c:6:0:
verstable.h: In function ‘int_int_map_evict’:
verstable.h:894:3: warning: implicit declaration of function ‘_Generic’ [-Wimplicit-function-declaration]
   size_t home_bucket = HASH_FN( table->buckets[ bucket ].key ) & ( table->bucket_count - 1 );
   ^
verstable.h:763:44: error: expected expression before ‘char’
 #define HASH_FN _Generic( ( KEY_TY ){ 0 }, char *: vt_hash_string, default: vt_hash_integer )
                                            ^
verstable.h:894:24: note: in expansion of macro ‘HASH_FN’
   size_t home_bucket = HASH_FN( table->buckets[ bucket ].key ) & ( table->bucket_count - 1 );
                        ^
verstable.h: In function ‘int_int_map_insert_raw’:
verstable.h:763:44: error: expected expression before ‘char’
 #define HASH_FN _Generic( ( KEY_TY ){ 0 }, char *: vt_hash_string, default: vt_hash_integer )
                                            ^
verstable.h:966:19: note: in expansion of macro ‘HASH_FN’
   uint64_t hash = HASH_FN( key );
                   ^
verstable.h:772:44: error: expected expression before ‘char’
 #define CMPR_FN _Generic( ( KEY_TY ){ 0 }, char *: vt_cmpr_string, default: vt_cmpr_integer )
                                            ^
verstable.h:1007:9: note: in expansion of macro ‘CMPR_FN’
         CMPR_FN( table->buckets[ bucket ].key, key )
         ^
verstable.h: In function ‘int_int_map_get’:
verstable.h:763:44: error: expected expression before ‘char’
 #define HASH_FN _Generic( ( KEY_TY ){ 0 }, char *: vt_hash_string, default: vt_hash_integer )
                                            ^
verstable.h:1209:19: note: in expansion of macro ‘HASH_FN’
   uint64_t hash = HASH_FN( key );
                   ^
verstable.h:772:44: error: expected expression before ‘char’
 #define CMPR_FN _Generic( ( KEY_TY ){ 0 }, char *: vt_cmpr_string, default: vt_cmpr_integer )
                                            ^
verstable.h:1221:74: note: in expansion of macro ‘CMPR_FN’
     if( ( table->metadata[ bucket ] & VT_HASH_FRAG_MASK ) == hashfrag && CMPR_FN( table->buckets[ bucket ].key, key ) )
                                                                          ^
verstable.h: In function ‘int_int_map_erase_itr_raw’:
verstable.h:763:44: error: expected expression before ‘char’
 #define HASH_FN _Generic( ( KEY_TY ){ 0 }, char *: vt_hash_string, default: vt_hash_integer )
                                            ^
verstable.h:1277:25: note: in expansion of macro ‘HASH_FN’
       itr.home_bucket = HASH_FN( table->buckets[ itr_bucket ].key ) & ( table->bucket_count - 1 );
                         ^
In file included from main.c:6:0:
main.c: In function ‘main’:
verstable.h:579:65: error: expected expression before ‘vt_table_0000’
 #define vt_init( table ) _Generic( *( table ) VT_GENERIC_SLOTS( vt_table_, vt_init_ ) )( table )
                                                                 ^
verstable.h:405:25: note: in definition of macro ‘VT_CAT_’
 #define VT_CAT_( a, b ) a##b
                         ^
verstable.h:544:40: note: in expansion of macro ‘VT_CAT’
 #define VT_GENERIC_SLOT( ty, fn, n ) , VT_CAT( ty, n ): VT_CAT( fn, n )
                                        ^
verstable.h:546:35: note: in expansion of macro ‘VT_GENERIC_SLOT’
 #define VT_R1_1( ty, fn, d3, d2 ) VT_GENERIC_SLOT( ty, fn, VT_CAT_4( 0, d3, d2, 0 ) )
                                   ^
verstable.h:405:25: note: in expansion of macro ‘VT_R1_1’
 #define VT_CAT_( a, b ) a##b
                         ^
verstable.h:579:47: note: in expansion of macro ‘VT_GENERIC_SLOTS’
 #define vt_init( table ) _Generic( *( table ) VT_GENERIC_SLOTS( vt_table_, vt_init_ ) )( table )
                                               ^
main.c:13:5: note: in expansion of macro ‘vt_init’
     vt_init(&flow_table);
     ^

[root@DESKTOP-OAKHD5F src]# gcc --version
gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-44)
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Custom allocator context

Hi, thanks for sharing an awesome library. love the efficient design and clean api.

Regarding the topic of custom allocator context raised by @skeeto here https://old.reddit.com/r/C_Programming/comments/18gnxkd/verstable_a_versatile_highperformance_generic/kd25s9z/

Would you think the approach https://github.com/stclib/STC?tab=readme-ov-file#per-container-instance-customization fit Verstable well? It seems "zero cost" at runtime if not opted in, also less intrusive than what @skeeto's approach.

Regards!

Support const char* keys

Currently, vt_hash_string and vt_cmpr_string do not declare their arguments to be const. This makes them not useable with KEY_TY of const char*

Ideally, HASH_FN and CMPR_FN should be set automatically when KEY_TY is const char* just like they are for key type char*, but that is not so important.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.