Aggressively compressed radix tree (patricia trie)

experimental-aggressively-compressed-patricia-trie.c

struct Edge;			/* forward declaration */

#define VERTEX_MAX_EDGES 3	/* instead of real memory allocation */

struct Vertex {
	unsigned long int width;
	struct Edge *edges[VERTEX_MAX_EDGES];
	void *datum;
};

struct Edge {
	struct Vertex *from;
	struct Vertex *to;
	int datum;		/* instead of real split-char data */
};

struct Graph {
	struct Vertex *root;
};

#define NULL ((void *)0)	/* instead of real NULL from stdlib.h */

/**
 *              (0)                    v1
 *              / \                   /  \
 *             c   f              v1e1    v1e2
 *            /     \              /        \
 *          (2)     ( )          v2          v3
 *          / \      |          /  \
 *         r   t    fat      v2e1  v2e2
 *        /     \              |    |
 *      ( )     ( )           v4    v5
 *       |       |
 *      car     cat
 */

struct Edge v1e1;
struct Edge v1e2;

struct Vertex v1 = {
	.width = 2,
	.edges = {&v1e1, &v1e2},
	.datum = NULL
};

struct Vertex v2;

struct Edge v1e1 = {
	.from = &v1,
	.to = &v2,
	.datum = 'c',
};

struct Vertex v3;

struct Edge v1e2 = {
	.from = &v1,
	.to = &v3,
	.datum = 'f',
};

struct Edge v2e1;
struct Edge v2e2;

struct Vertex v2 = {
	.width = 2,
	.edges = {&v2e1, &v2e2},
	.datum = NULL
};

struct Vertex v4;

struct Edge v2e1 = {
	.from = &v2,
	.to = &v4,
	.datum = 'r'
};

struct Vertex v5;

struct Edge v2e2 = {
	.from = &v2,
	.to = &v5,
	.datum = 't'
};

/* bottom-most vertices */

struct Vertex v3 = {
	.width = 0,
	.edges = 0,
	.datum = "fat"
};

struct Vertex v4 = {
	.width = 0,
	.edges = 0,
	.datum = "car"
};

struct Vertex v5 = {
	.width = 0,
	.edges = 0,
	.datum = "cat"
};

/* test graph */

struct Graph g = {
	.root = &v1
};

/* test code */

int
main(void)
{
	/* TODO: traverse the trie here */

	return 0;
}