git/cbtree.c

/*
 * crit-bit tree implementation, does no allocations internally
 * For more information on crit-bit trees: https://cr.yp.to/critbit.html
 * Based on Adam Langley's adaptation of Dan Bernstein's public domain code
 * git clone https://github.com/agl/critbit.git
 */
#include "git-compat-util.h"
#include "cbtree.h"

static struct cb_node *cb_node_of(const void *p)
{ … }

/* locate the best match, does not do a final comparison */
static struct cb_node *cb_internal_best_match(struct cb_node *p,
					const uint8_t *k, size_t klen)
{ … }

/* returns NULL if successful, existing cb_node if duplicate */
struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen)
{ … }

struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen)
{ … }

static enum cb_next cb_descend(struct cb_node *p, cb_iter fn, void *arg)
{ … }

void cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
			cb_iter fn, void *arg)
{ … }