1BEGIN {
 2	for (i = 32; i <= 126; ++i)
 3		ord[sprintf("%c", i)] = i
 4	n = -1
 5}
 6
 7function makenode(c) {
 8	++n
 9	splits[n] = c
10	left[n] = -1
11	equal[n] = -1
12	right[n] = -1
13	values[n] = 0
14}
15
16function insert(nodes, id, c) {
17	nextid = nodes[id]
18	if (nextid != -1)
19		return nextid
20	makenode(c)
21	nodes[id] = n
22	return n
23}
24
25/^(#|$)/ {next}
26
27{
28	id = 0
29	c = ord[substr($1, 1, 1)]
30	if (n < 0)
31		makenode(c)
32	for (i = 1; i <= length($1) + 1;) {
33		if (c < splits[id]) {
34			id = insert(left, id, c)
35		} else if (c == splits[id]) {
36			if (i >= length($1))
37				values[id] = $2
38			if (c == 0)
39				break
40			++i
41			c = i <= length($1) ? ord[substr($1, i, 1)] : 0
42			id = insert(equal, id, c)
43		} else {
44			id = insert(right, id, c)
45		}
46	}
47}
48
49END {
50	print "static hubbub_entity_node dict[] = {"
51	for (i = 0; i <= n; ++i)
52		print "\t{ "splits[i]", "left[i]", "equal[i]", "right[i]", "values[i]" },"
53	print "};"
54	print "static int32_t dict_root = 0;"
55}