xtc_chash(3)

---

xtc_chash(3)

RCU-protected concurrent hash table

XTC_CHASH(3) Library Functions Manual XTC_CHASH(3)

xtc_chash_create, xtc_chash_destroy, xtc_chash_get, xtc_chash_insert, xtc_chash_remove, xtc_chash_size, xtc_chash_set_auto_shrink, xtc_chash_get_auto_shrink — RCU-protected concurrent hash table

#include <xtc.h>
#include <xtc_chash.h>
#include <xtc_rcu.h>

int
xtc_chash_create(xtc_chash_cmp_fn cmp, xtc_chash_hash_fn hash, size_t initial_capacity, xtc_chash_t **out);

void
xtc_chash_destroy(xtc_chash_t *h);

int
xtc_chash_get(xtc_chash_t *h, const void *key, void **out_value);

int
xtc_chash_insert(xtc_chash_t *h, void *key, void *value, void **out_old_value);

int
xtc_chash_remove(xtc_chash_t *h, const void *key, void **out_value);

size_t
xtc_chash_size(const xtc_chash_t *h);

void
xtc_chash_set_auto_shrink(xtc_chash_t *h, int on);

int
xtc_chash_get_auto_shrink(const xtc_chash_t *h);

xtc_chash is a chained hash table built on xtc_rcu(3) so that lookups are wait-free -- no lock, no atomic compare-exchange, just acquire-ordered loads down a bucket chain -- while inserts and removes still support many concurrent writers. It is the primary consumer motivating xtc_rcu's existence in this tree.

Keys and values are caller-owned void * pointers stored verbatim, the same convention as xtc_chan(3) and xtc_pdict(3): the table never copies a key or value and never frees one. A caller-supplied comparator cmp (the qsort(3) convention -- only the == 0 vs. != 0 distinction matters here) and hash function hash make the table key-type-agnostic.

() allocates a table with initial_capacity buckets, rounded up to the next power of two (0 defaults to 16). () frees the table's own bookkeeping; it does not free caller-owned keys/values and is not safe to call concurrently with any other call on the same table -- quiesce first, exactly as xtc_rcu(3)'s () requires.

() must be called inside the caller's own ()/() bracket (nesting is fine, see xtc_rcu(3)). On a hit it writes the value pointer to *out_value and returns XTC_OK; the pointer is valid only until the caller's read-side ends. On a miss it returns XTC_E_NOTFOUND.

() and () take the read-side internally for their own traversal; the caller does not need an outer read-side to call them, though nesting inside one is harmless. xtc_chash_insert() replaces any existing entry for an equal key, writing the old value pointer to *out_old_value (NULL for a fresh insert; the argument itself may be NULL). It may trigger a resize (a grow). xtc_chash_remove() writes the removed value pointer to *out_value (may be NULL) and returns XTC_E_NOTFOUND on a miss.

() returns the approximate live entry count -- exact with no concurrent writers, a fresh-enough estimate otherwise.

() enables (on non-zero) or disables (on zero) automatic shrink on the table h; it is OFF by default. () returns the current setting as 0 or 1. Both take effect immediately and are safe to call from any thread (the flag is a single atomic field). See RESIZE.

Writers serialize through a fixed set of 64 stripe mutexes; a key's stripe is derived from its bucket index in the CURRENT array (so two keys in the same bucket always take the same stripe lock -- a correctness requirement, not just an optimisation), and two writers touching different buckets that happen to share a stripe only pay a false-sharing serialization cost, never a correctness one.

A removed node is unlinked by overwriting its predecessor's link with a single release-ordered store of the removed node's own (unchanged) successor -- the node's own next field is never touched, so a reader already parked inside it can finish walking the rest of the chain exactly as it stood when it arrived. The node itself is handed to (), never freed synchronously: a concurrent reader that already loaded a pointer to it keeps a fully valid node until it leaves its read-side.

A resize claims every stripe lock (blocking writers, never readers), duplicates every live node into a freshly allocated array of the new size, publishes the new array with a release store, and retires the old array and its original nodes via (). A reader that loaded the old array before the swap keeps working against a fully valid table -- larger or smaller than the new one -- until it leaves its read-side.

This module never calls () itself; as with every other xtc_rcu(3) consumer, actual reclamation of retired nodes happens on the caller's, a test's, or an application-installed reaper's schedule.

xtc_chash always GROWS: it doubles its bucket array past a 75% load factor. It SHRINKS only when auto-shrink is enabled via xtc_chash_set_auto_shrink() (OFF by default), in which case a xtc_chash_remove() that drops the load factor below 18.75% halves the bucket array -- never below the initial capacity passed to xtc_chash_create() (minimum 16). Shrink runs the identical RCU-swap machinery as grow, only in reverse (two old buckets merge into one, deterministic because sizes are) powers of two , so every invariant above holds in both directions.

The wide gap between the grow trigger (0.75) and the shrink trigger (0.1875) is deliberate hysteresis. A shrink halves the array, which doubles the load factor to below 0.375; climbing back to a grow then needs a roughly 2x increase in live entries and dropping back to another shrink a further roughly 2x decrease, so no single () or () near a boundary can make the table thrash grow<->shrink.

Grow is always-on because memory then tracks the true working-set peak monotonically. Shrink is opt-in because it adds a rehash to the remove path and reclaims memory a caller may have wanted stable: enable it if the workload has large delete phases and you want the memory reclaimed.

XTC_OK on success; XTC_E_INVAL for a NULL table/key or missing comparator/hash at create; XTC_E_NOTFOUND on a get/remove miss; XTC_E_NOMEM on allocation failure.

static int
str_cmp(const void *a, const void *b)
{
	return strcmp((const char *)a, (const char *)b);
}

static uint64_t
str_hash(const void *key)
{
	const char *s = key;
	uint64_t h = 1469598103934665603ULL;
	for (; *s != '\0'; s++) { h ^= (uint8_t)*s; h *= 1099511628211ULL; }
	return h;
}

xtc_chash_t *h;
xtc_chash_create(str_cmp, str_hash, 64, &h);
xtc_chash_insert(h, "answer", (void *)(intptr_t)42, NULL);

xtc_rcu_read_lock();
void *v;
if (xtc_chash_get(h, "answer", &v) == XTC_OK)
	printf("%ld\n", (intptr_t)v);
xtc_rcu_read_unlock();

xtc_chash_destroy(h);

xtc_rcu(3), xtc_cskip(3), xtc_chan(3), xtc_pdict(3), xtc(7)

Appeared in xtc 0.1, M13a.

July 13, 2026 Debian

View the mdoc source