NAME

critbit — dense zero-allocation radix tree with scalably parallelizable lookup

SYNOPSIS

#include <critbit.h>

struct critbit;
struct critbit_node;
struct critbit_ops;

#define CRITBIT_MAX_KEYLEN 65535

void
critbit_init(struct critbit *C, const struct critbit_ops *ops);

void
critbit_destroy(struct critbit *C);

void
critbit_node_init(struct critbit_node *N, const void *key, size_t keylen);

void
critbit_node_destroy(struct critbit_node *N);

struct critbit_node *
critbit_min(const struct critbit *C);

struct critbit_node *
critbit_max(const struct critbit *C);

struct critbit_node *
critbit_lookup(const struct critbit *C, const void *key, size_t keylen);

struct critbit_node *
critbit_lookup_prefix(const struct critbit *C, const void *key, size_t keylen);

struct critbit_node *
critbit_insert(struct critbit *C, struct critbit_node *N);

void
critbit_delete(struct critbit *C, struct critbit_node *N);

struct critbit_node *
critbit_delete_key(struct critbit *C, const void *key, size_t keylen);

struct critbit_txn_delete;
struct critbit_txn_delete_1;

void
critbit_txn_delete_begin(struct critbit *C, struct critbit_txn_delete *T, struct critbit_txn_delete_1 *T1, size_t n);

struct critbit_node *
critbit_txn_delete_key(struct critbit *C, const void *key, size_t keylen, struct critbit_txn_delete *T);

void
critbit_txn_delete(struct critbit *C, struct critbit_node *N, struct critbit_txn_delete *T);

void
critbit_txn_delete_commit(struct critbit *C, struct critbit_txn_delete *T);

struct critbit_iter;

void
critbit_iter_init(struct critbit *C, struct critbit_iter *I, void *stack, size_t stacklen);

void
critbit_iter_destroy(struct critbit *C, struct critbit_iter *I);

struct critbit_node *
critbit_iter_min(struct critbit *C, struct critbit_iter *I);

struct critbit_node *
critbit_iter_max(struct critbit *C, struct critbit_iter *I);

struct critbit_node *
critbit_iter_prev(struct critbit *C, struct critbit_iter *I);

struct critbit_node *
critbit_iter_next(struct critbit *C, struct critbit_iter *I);

DESCRIPTION

The critbit library implements dense zero-allocation binary radix trees with scalably parallelizable lookup.

radix tree

Tree-structured set of elements with string keys in lexicographic order, compressed to elide single-child branches. Time to lookup/insert/delete is O(min(k, n)), for maximum key length k in digits and n elements stored.

binary

The radix of critbit trees is 2. Keys, however, are limited to be integral numbers of bytes long; there are no partial-byte keys.

dense

Every branch has the maximum number of children, 2. No branches have empty slots in memory where children could go. Thus, the number of branches is exactly one less than the number of elements.

zero-allocation

All memory used by critbit is allocated by the caller. critbit performs no dynamic memory allocation.

scalably parallelizable lookup

With pserialize(9) or similar, multiple calls to critbit_lookup() and other lookup operations can safely run in parallel with each other and with insertion and deletion with no interprocessor synchronization in the lookup operations.

However, insertion and deletion must be serialized.

Critbit trees are so called because they are compressed to have each branch occur only at a bit position where two keys differ after a common prefix, called the ‘critical bit'.

The caller must allocate storage for a struct critbit object and one struct critbit_node object for every element in the critbit tree. These objects should otherwise be treated as opaque, and not inspected, modified, or copied. Each element has a corresponding key, which is a string of up to 65535, CRITBIT_MAX_KEYLEN, bytes.

The caller must define operations collected in a struct critbit_ops object to retrieve the key of an element and to issue synchronization barriers. For uniprocessor or otherwise serialized applications, the synchronization functions can be noops.

struct critbit_ops { 
	const void	*(*cbo_key)(const struct critbit *C, 
			    const struct critbit_node *N, size_t *keylenp); 
	void		(*cbo_membar_producer)(void); 
	void		(*cbo_membar_datadep_consumer)(void); 
	void		(*cbo_sync)(struct critbit *C); 
};

The operations are:

cbo_key(C, N, keylenp)

Given a critbit tree C and a node N, store the length in bytes of the node's key in *keylenp and return a pointer to the node's key.

cbo_membar_producer()

Guarantee all prior writes are visible to all users of lookup operations subsequent writes.

cbo_membar_datadep_consumer()

Guarantee all prior reads have completed before all subsequent dereferences of pointers read by prior reads.

cbo_sync(C)

Guarantee that all readers in critbit_lookup() and critbit_lookup_prefix() that began before the call to cbo_sync() have completed, for example by calling pserialize_perform() from pserialize(9).

INITIALIZATION AND FINALIZATION

critbit_init(C, ops)

Initialize a critbit tree with the specified operations. Must be done before any other operations on C.

critbit_destroy(C)

Destroy a critbit tree. The tree must be empty.

This operation is not necessary, but it provides a debugging aid by asserting that the tree is in a consistent state and preventing subsequent use.

critbit_node_init(N, key, keylen)

Initialize a critbit node.

critbit_node_destroy(N)

Destroy a critbit node. The node must not currently be in a tree.

This operation is not necessary, but it provides a debugging aid by asserting that the node has been deleted and preventing subsequent use.

LOOKUP OPERATIONS

The following lookup operations may be done in parallel with any other operations. The lookup operations all invoke the cbo_membar_datadep_consumer() operation to ensure correct ordering of memory reads to coordinate with any parallel modification operations.

critbit_min(C)

Return a pointer to the struct critbit_node object for the lexicographically first element of C.

critbit_max(C)

Return a pointer to the struct critbit_node object for the lexicographically last element of C.

critbit_lookup(C, key, keylen)

Return a pointer to the struct critbit_node object of the element whose key is keylen bytes at the pointer key, or NULL if there is no such element.

critbit_lookup_prefix(C, key, keylen)

Return a pointer to the struct critbit_node object of the lexicographically first element whose key begins with the keylen bytes at the pointer key, or NULL if there is no such element.

This is not the lexicographically first element before or after keylen bytes at key: if an element is returned, then its key has the keylen bytes of key as a prefix.

MODIFICATION OPERATIONS

The following modification operations, and batch deletion below, must be done only serially on a single critbit tree. They may be done in parallel with lookup operations, provided the caller fills in the necessary struct critbit_ops operations to order memory operations. They must not be done in parallel with iteration.

critbit_insert(C, N)

Insert the element whose struct critbit_node object is N into the critbit tree C. If there was already such an element in C, return a pointer to its struct critbit_node object and leave the critbit tree alone. Otherwise, return N.

Thus, critbit_insert() always returns the element that is actually in C.

The critbit_insert() function calls the cbo_membar_producer() operation to ensure correct ordering of memory writes to coordinate with any parallel lookup operations.

critbit_delete(C, N)

Delete the element whose struct critbit_node object is N from the critbit tree C. Caller must guarantee that N is currently in C.

The critbit_delete() function calls the cbo_membar_producer() operation to ensure correct ordering of memory writes to coordinate with any parallel lookup operations, and calls the cbo_sync() operation to wait for all parallel lookup operations to have completed before it returns.

critbit_delete_key(C, key, keylen)

Delete the element whose key is equal to the keylen bytes at key from the critbit tree C and return a pointer to its struct critbit_node object, if there is one. If there is no such element, return NULL instead.

The critbit_delete_key() function calls the cbo_membar_producer() operation to ensure correct ordering of memory writes to coordinate with any parallel lookup operations, and calls the cbo_sync() operation to wait for all parallel lookup operations to have completed before it returns.

BATCH DELETION

Since deletion requires waiting (twice) for all extant readers on all CPUs to complete, it is a very expensive operation. To mitigate this cost for multiple deletions, you can combine them in a batch that will do the interprocessor synchronization only once for the entire batch.

The cost of n sequential deletions is O(n*c), assuming each cbo_sync() operation costs O(c), whereas the cost of a single batch of n deletions is O(n^2 + c). Since n is usually small, and the constant factors of interprocessor synchronization are large compared to CPU-local computation, this is often a net benefit.

The caller must allocate a struct critbit_txn_delete object and an array of struct critbit_txn_delete_1 objects as temporary storage for a delete transaction, not to be reused until the transaction is committed. These objects should otherwise be treated as opaque, and not inspected, modified, or copied.

Delete transactions may be done only in serial with other modification operations and other delete transactions. They may be done in parallel with lookup operations, provided the caller fills in the necessary struct critbit_ops operations to order memory operations. They must not be done in parallel with iteration.

critbit_txn_delete_begin(C, T, T1, n)

Begin a delete transaction T for up to n deletions from the critbit tree C, recorded in the n-element array T1.

critbit_txn_delete(C, N, T)

Delete the element whose struct critbit_node object is N from the critbit tree C as if with critbit_delete. The node cannot be reused until after committing the transaction T.

critbit_txn_delete_key(C, key, keylenp, T)

Delete the element whose key is equal to the keylen bytes at key from the critbit tree C as if with critbit_delete_key(). The node returned, if any, cannot be reused until after committing the transaction T.

critbit_txn_delete_commit(C, T)

Commit the transaction T. The caller may now reuse nodes passed to critbit_txn_delete() and returned from critbit_txn_delete_key().

The critbit_txn_delete_commit() function calls the cbo_membar_producer() operation to ensure correct ordering of memory writes to coordinate with any parallel lookup operations, and calls the cbo_sync() operation to wait for all parallel lookup operations to have completed before it returns.

ITERATION

To iterate over a critbit tree, the caller must allocate temporary storage for as many bytes as the largest key in the tree, and a struct critbit_iter object. These objects should otherwise be treated as opaque, and not inspected, modified, or copied.

Iteration may be done in parallel with other iteration and lookup operations, but must not be done in parallel with any modification operations.

critbit_iter_init(C, I, stack, stacklen)

Initialize the iterator I to iterate over the critbit tree C, using the stacklen bytes at stack as temporary storage. The length stacklen must be at least the number of bytes of the longest key in C.

critbit_iter_destroy(C, I)

Destroy the iterator I.

This operation is not necessary, but it provides a debugging aid by preventing subsequent use of I.

critbit_iter_min(C, I)

Move I to the lexicographically least element of C and return a pointer to its struct critbit_node object, or NULL if C is empty.

critbit_iter_max(C, I)

Move I to the lexicographically greatest of C and return a pointer to its struct critbit_node object, or NULL if C is empty.

critbit_iter_next(C, I)

Move I to the lexicographically next element and return a pointer to its struct critbit_node object, or NULL if there are no more elements in C.

critbit_iter_prev(C, I)

Move I to the lexicographically previous element and return a pointer to its struct critbit_node object, or NULL if there are no more elements in C.

EXAMPLES

Example application in the NetBSD kernel. Definitions:

struct widget { 
	uint64_t		key; 
	struct critbit_node	node; 
	... 
}; 
 
struct { 
	krwlock_t		lock; 
	struct critbit_tree	tree; 
	struct pserialize	*psz; 
} widgets __cacheline_aligned; 
 
static const void * 
widget_key(const struct critbit *C, const struct critbit_node *N, 
    size_t *keylenp) 
{ 
	const struct widget *W = container_of(N, struct widget, node); 
 
	KASSERT(C == &widgets.tree); 
 
	*keylenp = sizeof W->key; 
	return &W->key; 
} 
 
static void 
widgets_sync(struct critbit_tree *C) 
{ 
 
	KASSERT(C == &widgets.tree); 
	KASSERT(rw_write_held(&widgets.lock)); 
 
	/* Wait for all pserialize read sections to complete. */ 
	pserialize_perform(widgets.psz); 
} 
 
static const struct critbit_ops widget_critbit_ops = { 
	.cbo_key = &widget_key, 
	.cbo_membar_producer = &membar_producer, 
	.cbo_membar_datadep_consumer = &membar_datadep_consumer, 
	.cbo_sync = &widgets_sync, 
};

Lookup:

	uint64_t key = ...; 
	struct widget *W; 
	int result = -1; 
	int s; 
 
	s = pserialize_read_enter(); 
	W = critbit_lookup(&widgets.tree, &key, sizeof key); 
	if (W == NULL) 
		goto out; 
	result = bromble(W); 
out:	pserialize_read_exit(s);

Insert:

	uint64_t key = ...; 
	struct widget *W, *W0; 
 
	W = alloc_widget(); 
	W->key = key; 
	W->... = ...; 
 
	rw_enter(&widgets.lock, RW_WRITER); 
	W0 = critbit_insert(&widgets.tree, W); 
	rw_exit(&widgets.lock); 
 
	if (W0 != W) { 
		/* Failed to insert -- key already used. */ 
		free_widget(W); 
		return EEXIST; 
	}

Delete:

	uint64_t key = ...; 
	struct widget *W; 
 
	rw_enter(&widgets.lock, RW_WRITER); 
	W = critbit_delete_key(&widgets.tree, &key, sizeof key); 
	rw_exit(&widgets.lock); 
 
	if (W != NULL) 
		free_widget(W);

Batch delete:

	uint64_t key, keys[10] = ...; 
	struct widget *W, *deleted[__arraycount(keys)]; 
	struct critbit *C = &widgets.tree; 
	struct critbit_txn_delete_1 T1[__arraycount(keys)]; 
	struct critbit_txn_delete txn, T = &txn; 
	unsigned i, ndeleted = 0; 
 
	rw_enter(&widgets.lock, RW_WRITER); 
	critbit_txn_delete_begin(C, T, T1, __arraycount(T1)); 
	for (i = 0; i < arraycount(keys); i++) { 
		key = keys[i]; 
		W = critbit_txn_delete_key(C, key, sizeof key, T); 
		if (W != NULL) 
			deleted[ndeleted++] = W; 
	} 
	critbit_txn_delete_commit(C, T); 
	rw_exit(&widgets.lock); 
 
	/* Can now safely reuse the widgets we deleted. */ 
	for (i = 0; i < ndeleted; i++) { 
		W = deleted[i]; 
		free_widget(W); 
	}

Iterate:

	struct critbit *C = &widgets.tree; 
	struct widget *W; 
	uint64_t pseudokey; 
	struct critbit_iter iter, *I = &iter; 
	int result = -1; 
 
	rw_enter(&widgets.lock, RW_READER); 
	critbit_iter_init(C, I, &pseudokey, sizeof pseudokey); 
	for (W = critbit_iter_min(C, I); 
	     W != NULL; 
	     W = critbit_iter_next(C, I)) { 
		if (mimsiness(W) == QUARK) { 
			result = outgrobe(W); 
			break; 
		} 
	} 
	critbit_iter_destroy(C, I); 
	rw_exit(&widgets.lock);

SEE ALSO

membar_ops(3), rbtree(3), pserialize(9)

Daniel J. Bernstein, Crit-bit trees, https://cr.yp.to/critbit.html.

AUTHORS

Taylor R Campbell <campbell+critbit@mumble.net>

BUGS

Variable-length keys may be broken.

Insertion and deletion must be serialized.

critbit is not cache-aware.