sht-ts.h File Reference

Generates type-safe wrappers for the SHT API. More...

#include "sht.h"

Go to the source code of this file.

Macros
#define	SHT_TABLE_TYPE(ttspec, ktype, etype, hfspec, efspec, ...)
	Generate types and functions for a type-safe hash table type.

Detailed Description

Generates type-safe wrappers for the SHT API.

The SHT_TABLE_TYPE() macro generates a strongly typed front-end to the generic SHT hash table implementation. The underlying library (sht.h) operates on void pointers, but the type-safe layer ensures that each instance of a table is associated with specific key and entry types, eliminating unsafe casts, mismatched callback signatures, and logic errors. All errors related to type mismatch are detected at compile time, not runtime.

Core concepts

A type-safe table instance is parameterized by the following.

• The table type spec (ttspec). This is a 1- or 2-member tuple that contains an optional storage class modifier and a required prefix.

  • If specified, the storage class modifier changes the storage class of the type-safe functions that are generated. By default, all of the generated functions have a static storage class, but this can be overridden by specifying a different storage class. The special value extern can be specified to remove any storage class specifier from the generated functions. (Generated hash, equality, and free functions are always static.)
  • The prefix is used to construct the names of the generated types and functions. For example, a prefix of foo will generate functions named foo_new(), foo_init(), foo_add(), etc.

  The tuple must be parenthesized if a storage class modified is specified; otherwise, parentheses are optional, so the following formats are all valid — prefix, (prefix), and (storage_class, prefix).

• The key type (ktype). The base type of the keys that will be stored in the table. For example, if the application-supplied hash and equality functions accept const char * as their key arguments, then the ktype would be char.
• The entry type (etype). The base type of the entries that will be stored in the table. If the application-supplied equality function accepts a const struct foo_entry * as its entry argument, then the etype would be struct foo_entry.

• The hash function spec (hfspec). This is a 1- or 2-member tuple that that contains a required type-safe hash function name and an optional context type.

  Note that unlike the key and entry types, context types are not const-qualified by default. This allows application-supplied hash, equality, and free functions to modify their contexts, if needed. If the supplied function does expect a const-qualified pointer as its context argument, then const should be included in the context type — e.g., const uint32_t.

  The tuple must be parenthesized if a context type is specified; otherwise, parentheses are optional, so the following formats are all valid — hash_function, (hash_function), and (hash_function, context_type).

• The equality function spec (efspec). A 1- or 2-member tuple that contains a required type-safe equality function name and an optional context type.
• Optionally, a free function spec — a 1- or 2-member tuple that contains a type-safe free function name and an optional context type.

Based on these parameters, SHT_TABLE_TYPE() generates:

• A distinct opaque table type (e.g., struct foo_ht),
• A corresponding opaque iterator type (e.g., struct foo_iter),
• Wrapper functions for the application-provided hash, equality, and (if specified) free functions. The generated functions accept void pointers as their key, entry, and context arguments, as required by the library API.
• Type-safe context setter functions for any context types that are specified. (If no context type is specified for a hash, equality, or free function, then no setter function will be generated for that context.)
• Type-safe wrappers for all of the library API functions (except sht_msg()).

Examples

Integer set

This example shows a simple set of integers. No values are stored, so no entry structure or free function is required. XXH3_64bits() is used as a hash function, and it does not require a seed, so no context is needed by either the hash or equality functions.

#include <sht-ts.h>
#include <xxhash.h>
 
static int_hash(const int *key)
{
    return (uint32_t)XXH3_64bits(key, sizeof *key);
}
 
static int_eq(const int *restrict key, const int *restrict entry)
{
    return *key == *entry;
}
 
SHT_TABLE_TYPE(int, int, int, int_hash, int_eq)

NOTE

The type-safe hash, equality, and (if needed) free functions should almost always be static, so that they can be inlined within the generated callback wrappers.

A simplified subset of the code generated by this SHT_TABLE_TYPE() invocation is shown below for illustrative purposes. See the next example for a complete SHT_TABLE_TYPE() expansion.

static uint32_t int_hash_wrapper_(const void *restrict key,
                              void *restrict context)
{
    (void)context;
    return int_hash(key);
}
 
static bool int_eq_wrapper_(const void *restrict key,
                        const void *restrict entry, void *restrict context)
{
    (void)context;
    return int_eq(key, entry);
}

These wrapper functions conform to the SHT API for hash and equality functions.

• No free function wrapper was generated, because the SHT_TABLE_TYPE() invocation did not include a free function spec.
• Neither the hash function spec nor the equality function spec included a context type, so the generated wrappers do not include that argument in their calls to the type-safe functions. (The (void)context; statements suppress unused argument warnings.)

struct int_ht;
struct int_iter;

These incomplete types will be used in the type-safe wrapper functions.

static_assert(sizeof(int) <= 16384, "Entry type (int) too large");
 
static struct int_ht *int_new(void)
{
    return (struct int_ht *)sht_new_(int_hash_wrapper_, int_eq_wrapper_,
                                     nullptr, sizeof(int), alignof(int),
                                     nullptr);
}

Note the compile-time check of the entry size (int in this case). Because of this check, the only possible failure mode of int_new() is a memory allocation failure (SHT_ERR_ALLOC), so there is no need to pass an error code output pointer to sht_new_().

This function simply calls sht_new_() and casts its return value to the generated table type. Like all of the generated wrappers (except the callback wrappers), it will almost always be "optimized away," and generate no actual code.

static void int_set_lft(struct int_ht *ht, uint8_t lft)
{
    sht_set_lft((struct sht_ht *)ht, lft);
}
 
static void int_set_psl_limit(struct int_ht *ht, uint8_t limit)
{
    sht_set_psl_limit((struct sht_ht *)ht, limit);
}

The macro generates setters for the load factor threshold (LFT) and the probe sequence length (PSL) limit, but it doesn't generate any context setters, because no context types were specified.

static int int_set(struct int_ht *ht, const int *key, const int *entry)
{
    return sht_set((struct sht_ht *)ht, key, entry);
}
 
static const int *int_get(struct int_ht *ht, const int *key)
{
    return sht_get((struct sht_ht *)ht, key);
}

These wrappers accept and return pointers to the key and entry types (both int), rather than the void pointers used by the underlying API. (Conversions between void pointers and other object pointer types do not require explicit casts.)

static struct int_iter *int_iter_new(struct int_ht *ht, enum sht_iter_type type)
{
    return (struct int_iter *)sht_iter_new((struct sht_ht *)ht, type);
}

This wrapper returns the incomplete type-safe iterator type that was declared earlier.

static const int *int_iter_next(struct int_iter *iter)
{
    return sht_iter_next((struct sht_iter *)iter);
}
 
static bool int_iter_replace(struct int_iter *iter, const int *entry)
{
    return sht_iter_replace((struct sht_iter *)iter, entry);
}

These wrappers operate on the type-safe iterator (struct int_iter *) and entry (int) types.

String/string map

This example shows a map that uses C strings as both its key and value types.

#include <sht-ts.h>
#include <xxhash.h>
#include <string.h>
 
struct map_entry {
    char *key;
    char *value;
}
 
static uint64_t map_eq_called = 0;
static uint64_t map_free_called = 0;
 
static uint32_t map_hash(const char *restrict key, const XXH64_hash_t *seed)
{
    return (uint32_t)XXH3_64bits_withSeed(key, strlen(key), *seed)
}
 
static bool map_eq(const char *key, const struct map_entry *entry,
                   uint64_t *called)
{
    ++(*called);
    return strcmp(key, entry->key) == 0;
}
 
static void map_free(const struct map_entry *entry, uint64_t *called)
{
    ++(*called);
    free(entry->key);
    free(entry->value);
}
 
SHT_TABLE_TYPE(
    (extern, map),
    char,
    struct map_entry,
    (map_hash, const XXH64_hash_t),
    (map_eq, uint64_t),
    (map_free, uint64_t)
)

This example is constructed to show as many options as possible.

• The table type spec includes the special extern storage class, which causes all of the generated functions (except the callbacks) to have no explicit storage class. (This is probably not a good idea, because it will prevent the compiler from optimizing these functions away.)
• The underlying hash function (XXH3_64bits_withSeed()) requires a seed, which is passed to the type-safe hash function as a const-qualified pointer.
• The type-safe equality and free functions both use a mutable context to count the number of times that they are called.

The complete expansion of this SHT_TABLE_TYPE() invocation is shown below. It was produced by running the following command. (The .clang-format file used can be found in the root directory of this repository.)

gcc -E test.c | grep -v '^# ' | clang-format'

The macro expansion is found at the end of the generated file.

// ...
 
static_assert(sizeof(struct map_entry) <= 16384,
              "Entry type (struct map_entry) too large");
struct map_ht;
struct map_iter;
 
static uint32_t map_hash_wrapper_(const void *restrict key,
                                  void *restrict context)
{
    typedef uint32_t (*ts_hashfn_t)(const char *restrict,
                                    const XXH64_hash_t *restrict);
    static_assert(
            _Generic((map_hash), ts_hashfn_t: 1, default: 0),
            "map_hash has incorrect signature; expected: uint32_t map_hash ( "
            "const char *restrict , const XXH64_hash_t *restrict )");
    (void)context;
    return map_hash(key, context);
}
 
static bool map_eq_wrapper_(const void *restrict key,
                            const void *restrict entry, void *restrict context)
{
    typedef bool (*ts_eqfn_t)(const char *restrict,
                              const struct map_entry *restrict,
                              uint64_t *restrict);
    static_assert(_Generic((map_eq), ts_eqfn_t: 1, default: 0),
                  "map_eq has incorrect signature; expected: bool map_eq ( "
                  "const char *restrict , const struct map_entry *restrict , "
                  "uint64_t *restrict )");
    (void)context;
    return map_eq(key, entry, context);
}
 
static void map_free_wrapper_(const void *restrict entry,
                              void *restrict context)
{
    typedef void (*ts_freefn_t)(const struct map_entry *restrict,
                                uint64_t *restrict);
    static_assert(_Generic((map_free), ts_freefn_t: 1, default: 0),
                  "map_free has incorrect signature; expected: void map_free ( "
                  "const struct map_entry *restrict , uint64_t *restrict )");
    (void)context;
    map_free(entry, context);
}
 
[[maybe_unused]]
struct map_ht *map_new(void)
{
    return (struct map_ht *)sht_new_(
            map_hash_wrapper_, map_eq_wrapper_, map_free_wrapper_,
            sizeof(struct map_entry), alignof(struct map_entry), nullptr);
}
 
[[maybe_unused, gnu::nonnull(1)]]
void map_set_hash_ctx(struct map_ht *ht, const XXH64_hash_t *context)
{
    sht_set_hash_ctx((struct sht_ht *)ht, sht_strip_const_(context));
}
 
[[maybe_unused, gnu::nonnull(1)]]
void map_set_eq_ctx(struct map_ht *ht, uint64_t *context)
{
    sht_set_eq_ctx((struct sht_ht *)ht, sht_strip_const_(context));
}
 
[[maybe_unused, gnu::nonnull(1)]]
void map_set_free_ctx(struct map_ht *ht, uint64_t *context)
{
    sht_set_free_ctx((struct sht_ht *)ht, sht_strip_const_(context));
}
 
[[maybe_unused, gnu::nonnull]]
void map_set_lft(struct map_ht *ht, uint8_t lft)
{
    sht_set_lft((struct sht_ht *)ht, lft);
}
 
[[maybe_unused, gnu::nonnull]]
void map_set_psl_limit(struct map_ht *ht, uint8_t limit)
{
    sht_set_psl_limit((struct sht_ht *)ht, limit);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_init(struct map_ht *ht, uint32_t capacity)
{
    return sht_init((struct sht_ht *)ht, capacity);
}
 
[[maybe_unused, gnu::nonnull]]
void map_free(struct map_ht *ht)
{
    sht_free((struct sht_ht *)ht);
}
 
[[maybe_unused, gnu::nonnull]]
int map_add(struct map_ht *ht, const char *key, const struct map_entry *entry)
{
    return sht_add((struct sht_ht *)ht, key, entry);
}
 
[[maybe_unused, gnu::nonnull]]
int map_set(struct map_ht *ht, const char *key, const struct map_entry *entry)
{
    return sht_set((struct sht_ht *)ht, key, entry);
}
 
[[maybe_unused, gnu::nonnull]]
const struct map_entry *map_get(struct map_ht *ht, const char *key)
{
    return sht_get((struct sht_ht *)ht, key);
}
 
[[maybe_unused, gnu::nonnull]]
uint32_t map_size(const struct map_ht *ht)
{
    return sht_size((const struct sht_ht *)ht);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_empty(const struct map_ht *ht)
{
    return sht_empty((const struct sht_ht *)ht);
}
 
[[maybe_unused, gnu::nonnull]]
uint8_t map_peak_psl(const struct map_ht *ht)
{
    return sht_peak_psl((const struct sht_ht *)ht);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_delete(struct map_ht *ht, const char *key)
{
    return sht_delete((struct sht_ht *)ht, key);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_pop(struct map_ht *ht, const char *restrict key,
             struct map_entry *restrict out)
{
    return sht_pop((struct sht_ht *)ht, key, out);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_replace(struct map_ht *ht, const char *key,
                 const struct map_entry *entry)
{
    return sht_replace((struct sht_ht *)ht, key, entry);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_swap(struct map_ht *ht, const char *key, const struct map_entry *entry,
              struct map_entry *out)
{
    return sht_swap((struct sht_ht *)ht, key, entry, out);
}
 
[[maybe_unused, gnu::nonnull]]
struct map_iter *map_iter_new(struct map_ht *ht, enum sht_iter_type type)
{
    return (struct map_iter *)sht_iter_new((struct sht_ht *)ht, type);
}
 
[[maybe_unused, gnu::nonnull]]
void map_iter_free(struct map_iter *iter)
{
    sht_iter_free((struct sht_iter *)iter);
}
 
[[maybe_unused, gnu::nonnull]]
const struct map_entry *map_iter_next(struct map_iter *iter)
{
    return sht_iter_next((struct sht_iter *)iter);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_iter_delete(struct map_iter *iter)
{
    return sht_iter_delete((struct sht_iter *)iter);
}
 
[[maybe_unused, gnu::nonnull]]
bool map_iter_replace(struct map_iter *iter, const struct map_entry *entry)
{
    return sht_iter_replace((struct sht_iter *)iter, entry);
}
 
[[maybe_unused, gnu::nonnull]]
enum sht_err map_get_err(struct map_ht *ht)
{
    return sht_get_err((struct sht_ht *)ht);
}
 
[[maybe_unused, gnu::nonnull]]
const char *map_get_msg(struct map_ht *ht)
{
    return sht_get_msg((struct sht_ht *)ht);
}
 
[[maybe_unused, gnu::nonnull]]
enum sht_err map_iter_err(struct map_iter *iter)
{
    return sht_iter_err((struct sht_iter *)iter);
}
 
[[maybe_unused, gnu::nonnull]]
const char *map_iter_msg(struct map_iter *iter)
{
    return sht_iter_msg((struct sht_iter *)iter);
}

Definition in file sht-ts.h.

Macro Definition Documentation

SHT_TABLE_TYPE

#define SHT_TABLE_TYPE	(		ttspec,
			ktype,
			etype,
			hfspec,
			efspec,
			... )

Generate types and functions for a type-safe hash table type.

Parameters

ttspec	Table type spec — a 1- or 2-member tuple that contains an optional storage class (e.g., static) followed by a required name prefix. If a storage class is specified, the tuple must be enclosed in parentheses. Thus, the following formats are allowed. prefix (prefix) (, prefix) (storage_class, prefix)
ktype	The type of the table's keys. For example, if the type-safe hash and equality functions accept a const char * as their key argument, then ktype should be char.
etype	The type of the table's entries. If the type-safe equality and free functions (if any) accept a const struct foo_entry *, then etype should be struct foo_entry.
hfspec	Hash function spec — a 1- or 2-member tuple that contains a required type-safe hash function name followed by an optional hash function context type. For example, if the type-safe hash function accepts a const uint32_t * as its context argument, then the context type should be const uint32_t. (Context pointers may be either const-qualified or non-const, depending on the needs of the application.) If a context type is specified, the tuple must be enclosed in parentheses. Thus, the following formats are allowed. function_name (function_name) (function_name, ) (function_name, context_type)
efspec	Equality function spec — a 1- or 2-member tuple that contains a required type-safe equality function name followed by an optional context type. (See hfspec for the allowed formats.)
...	Optional free function spec — a 1- or 2-member tuple that contains a required (if the spec if present) type-safe free function name followed by an optional context type. (See hfspec for the allowed formats.)

Definition at line 1162 of file sht-ts.h.