git

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

10
static struct cb_node *cb_node_of(const void *p)
11
{
12
	return (struct cb_node *)((uintptr_t)p - 1);
13
}
14

15
/* locate the best match, does not do a final comparision */
16
static struct cb_node *cb_internal_best_match(struct cb_node *p,
17
					const uint8_t *k, size_t klen)
18
{
19
	while (1 & (uintptr_t)p) {
20
		struct cb_node *q = cb_node_of(p);
21
		uint8_t c = q->byte < klen ? k[q->byte] : 0;
22
		size_t direction = (1 + (q->otherbits | c)) >> 8;
23

24
		p = q->child[direction];
25
	}
26
	return p;
27
}
28

29
/* returns NULL if successful, existing cb_node if duplicate */
30
struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen)
31
{
32
	size_t newbyte, newotherbits;
33
	uint8_t c;
34
	int newdirection;
35
	struct cb_node **wherep, *p;
36

37
	assert(!((uintptr_t)node & 1)); /* allocations must be aligned */
38

39
	if (!t->root) {		/* insert into empty tree */
40
		t->root = node;
41
		return NULL;	/* success */
42
	}
43

44
	/* see if a node already exists */
45
	p = cb_internal_best_match(t->root, node->k, klen);
46

47
	/* find first differing byte */
48
	for (newbyte = 0; newbyte < klen; newbyte++) {
49
		if (p->k[newbyte] != node->k[newbyte])
50
			goto different_byte_found;
51
	}
52
	return p;	/* element exists, let user deal with it */
53

54
different_byte_found:
55
	newotherbits = p->k[newbyte] ^ node->k[newbyte];
56
	newotherbits |= newotherbits >> 1;
57
	newotherbits |= newotherbits >> 2;
58
	newotherbits |= newotherbits >> 4;
59
	newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;
60
	c = p->k[newbyte];
61
	newdirection = (1 + (newotherbits | c)) >> 8;
62

63
	node->byte = newbyte;
64
	node->otherbits = newotherbits;
65
	node->child[1 - newdirection] = node;
66

67
	/* find a place to insert it */
68
	wherep = &t->root;
69
	for (;;) {
70
		struct cb_node *q;
71
		size_t direction;
72

73
		p = *wherep;
74
		if (!(1 & (uintptr_t)p))
75
			break;
76
		q = cb_node_of(p);
77
		if (q->byte > newbyte)
78
			break;
79
		if (q->byte == newbyte && q->otherbits > newotherbits)
80
			break;
81
		c = q->byte < klen ? node->k[q->byte] : 0;
82
		direction = (1 + (q->otherbits | c)) >> 8;
83
		wherep = q->child + direction;
84
	}
85

86
	node->child[newdirection] = *wherep;
87
	*wherep = (struct cb_node *)(1 + (uintptr_t)node);
88

89
	return NULL; /* success */
90
}
91

92
struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen)
93
{
94
	struct cb_node *p = cb_internal_best_match(t->root, k, klen);
95

96
	return p && !memcmp(p->k, k, klen) ? p : NULL;
97
}
98

99
static enum cb_next cb_descend(struct cb_node *p, cb_iter fn, void *arg)
100
{
101
	if (1 & (uintptr_t)p) {
102
		struct cb_node *q = cb_node_of(p);
103
		enum cb_next n = cb_descend(q->child[0], fn, arg);
104

105
		return n == CB_BREAK ? n : cb_descend(q->child[1], fn, arg);
106
	} else {
107
		return fn(p, arg);
108
	}
109
}
110

111
void cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
112
			cb_iter fn, void *arg)
113
{
114
	struct cb_node *p = t->root;
115
	struct cb_node *top = p;
116
	size_t i = 0;
117

118
	if (!p) return; /* empty tree */
119

120
	/* Walk tree, maintaining top pointer */
121
	while (1 & (uintptr_t)p) {
122
		struct cb_node *q = cb_node_of(p);
123
		uint8_t c = q->byte < klen ? kpfx[q->byte] : 0;
124
		size_t direction = (1 + (q->otherbits | c)) >> 8;
125

126
		p = q->child[direction];
127
		if (q->byte < klen)
128
			top = p;
129
	}
130

131
	for (i = 0; i < klen; i++) {
132
		if (p->k[i] != kpfx[i])
133
			return; /* "best" match failed */
134
	}
135
	cb_descend(top, fn, arg);
136
}
137