xtc_cskip(3)

---

xtc_cskip(3)

RCU-protected concurrent ordered map (skiplist)

XTC_CSKIP(3) Library Functions Manual XTC_CSKIP(3)

xtc_cskip_create, xtc_cskip_destroy, xtc_cskip_get, xtc_cskip_insert, xtc_cskip_remove, xtc_cskip_min, xtc_cskip_floor, xtc_cskip_size — RCU-protected concurrent ordered map (skiplist)

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

int
xtc_cskip_create(xtc_cskip_cmp_fn cmp, xtc_cskip_t **out);

void
xtc_cskip_destroy(xtc_cskip_t *s);

int
xtc_cskip_get(xtc_cskip_t *s, const void *key, void **out_value);

int
xtc_cskip_insert(xtc_cskip_t *s, void *key, void *value, void **out_old_value);

int
xtc_cskip_remove(xtc_cskip_t *s, const void *key, void **out_value);

int
xtc_cskip_min(xtc_cskip_t *s, void **out_key, void **out_value);

int
xtc_cskip_floor(xtc_cskip_t *s, const void *key, void **out_key, void **out_value);

size_t
xtc_cskip_size(const xtc_cskip_t *s);

xtc_cskip is a concurrent ordered map -- a skiplist (Pugh 1990) built on xtc_rcu(3) so that lookups are lock-free, walking the tower with acquire-ordered loads and no lock at all, while writers still support concurrent readers. It is the sibling of xtc_chash(3): where the hash table answers only “is this exact key present”, xtc_cskip additionally keeps keys in sorted order, so it answers “what is the smallest key” (()) and “what is the largest key <= K” (()), the predecessor / range queries an unordered hash table cannot serve.

Keys and values are caller-owned void * pointers stored verbatim, the same convention as xtc_chash(3), xtc_chan(3), and xtc_pdict(3): the map never copies or frees a key or value. A caller-supplied comparator cmp imposes the ordering; unlike xtc_chash(3), which only tests equality, xtc_cskip uses the FULL qsort(3) ordering (<0, 0, >0), so cmp MUST be a total order over the key space.

() allocates an empty map. () frees the map's own node bookkeeping; it does not free caller-owned keys/values and is not safe to call concurrently with any other call on the same map -- quiesce first, exactly as xtc_rcu(3)'s () requires.

(), xtc_cskip_min(), and xtc_cskip_floor() must be called inside the caller's own ()/() bracket (nesting is fine). Each writes its result pointer(s) on a hit and returns XTC_OK, or returns XTC_E_NOTFOUND on a miss / empty map; the returned pointers are valid only until the caller's read-side ends. xtc_cskip_min() reports the entry with the smallest key; xtc_cskip_floor() reports the entry with the largest key <= key (and XTC_E_NOTFOUND if no key is <= key). Any of the out_* arguments may be NULL if the caller does not want that half.

() and () take the read-side internally; the caller does not need an outer read-side. xtc_cskip_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). xtc_cskip_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.

Readers are lock-free. Writers (xtc_cskip_insert(), xtc_cskip_remove()) serialize on a single per-map mutex in this version -- the reader path is the one that must scale, and it takes no lock. A finer-grained per-node writer lock is a deliberate deferred optimization (recorded in the source); it is not needed until a workload shows writer contention.

An insert links its new node bottom-up, level 0 first: the base level is the source of truth for membership, so the node is present the instant its level-0 link is published (a single release store), and the upper levels are only a search accelerator a reader tolerates seeing half-built. A remove unlinks top-down by overwriting each predecessor's forward pointer with a release store of the removed node's own (unchanged) successor, then hands the node to () -- never freed synchronously. A reader already parked on the node keeps walking its untouched forward pointers until it leaves its read-side; RCU reclaims the node only after every such reader has drained.

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

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

static int
i64_cmp(const void *a, const void *b)
{
	int64_t x = *(const int64_t *)a, y = *(const int64_t *)b;
	return x < y ? -1 : (x > y ? 1 : 0);
}

int64_t k1 = 10, k2 = 20, k3 = 30;
xtc_cskip_t *s;
xtc_cskip_create(i64_cmp, &s);
xtc_cskip_insert(s, &k3, "thirty", NULL);
xtc_cskip_insert(s, &k1, "ten", NULL);
xtc_cskip_insert(s, &k2, "twenty", NULL);

xtc_rcu_read_lock();
void *mk, *mv;
if (xtc_cskip_min(s, &mk, &mv) == XTC_OK)
	printf("min key %ld -> %s\n", (long)*(int64_t *)mk, (char *)mv);
int64_t q = 25;
void *fk, *fv;
if (xtc_cskip_floor(s, &q, &fk, &fv) == XTC_OK)
	printf("floor(25) -> %ld=%s\n", (long)*(int64_t *)fk, (char *)fv);
xtc_rcu_read_unlock();

xtc_cskip_destroy(s);

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

The xtc_cskip ordered map first appeared in libxtc 1.21.

July 14, 2026 Debian

View the mdoc source