#include <stdio.h>
#include <inttypes.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>

#define vecmove(d, s, n) memmove(d, s, (n) * sizeof(*(d)))
#define vecset(d, v, n) memset(d, v, (n) * sizeof(*(d)))
#define error(string, args...) do { printf(string "!\n", ##args); exit(99); } while (0)
#define assert(expr) do { if (!(expr)) error("Failed assertion \"%s\"", #expr); } while (0)
#define trace_off(cmd)
#define trace_on(cmd) cmd
#define PACKED __attribute__ ((packed))

#if 1
void hexdump(void *data, unsigned size)
{
	while (size) {
		unsigned char *p;
		int w = 16, n = size < w? size: w, pad = w - n;
		printf("%p:  ", data);
		for (p = data; p < (unsigned char *)data + n;)
			printf("%02hx ", *p++);
		printf("%*.s  \"", pad*3, "");
		for (p = data; p < (unsigned char *)data + n;) {
			int c = *p++;
			printf("%c", c < ' ' || c > 127 ? '.' : c);
		}
		printf("\"\n");
		data += w;
		size -= n;
	}
}
#endif

bool get_bit(unsigned char *bitmap, unsigned i)
{
	return (bitmap[i >> 3] >> (i & 7)) & 1;
}

void set_bit(unsigned char *bitmap, unsigned i)
{
	bitmap[i >> 3] |= (1 << (i & 7));
}

void reset_bit(unsigned char *bitmap, unsigned i)
{
	bitmap[i >> 3] &= ~(1 << (i & 7));
}

#define LABEL_BITS 8
#define CHUNK_BITS 54
#define MAXVERSIONS (1 << LABEL_BITS)

typedef uint16_t version_t;
typedef uint16_t label_t;
typedef uint64_t chunk_t;
typedef unsigned tag_t;

struct exception { label_t label: LABEL_BITS; chunk_t chunk: CHUNK_BITS; } PACKED;
struct version { tag_t tag; label_t parent; bool used, ghost, present, pathmap, nearmap; };

struct version ver[MAXVERSIONS];
label_t *child_index[MAXVERSIONS];
label_t child_count[MAXVERSIONS];
label_t children[MAXVERSIONS];
label_t ordmap[MAXVERSIONS];
label_t version_count, active_count;
unsigned cycle;

label_t get_child(label_t parent, unsigned i)
{
	return child_index[parent][i];
}

label_t get_parent(label_t child)
{
	return ver[child].parent;
}

label_t get_root(void)
{
	assert(child_count[0]);
	return children[0];
}

label_t is_ghost(label_t version)
{
	return ver[version].ghost;
}

int find_tag(tag_t tag)
{
	for (int version = 1; version < version_count; version++)
		if (!is_ghost(version) && ver[version].tag == tag)
			return version;
	error("invalid snapshot '%u'", tag);
	return 0;
}

void show_table(void)
{
	for (int i = 0; i < version_count; i++) {
		printf("%i: ", i);
		if (!ver[i].used)
			printf("(free)");
		else if (!i)
			printf("(origin)");
		else {
			printf("<- ");
			if (!get_parent(i))
				printf("root");
			else
				printf("%i", get_parent(i));
			if (!is_ghost(i)) // 0 should be a ghost
				printf(" '%i'", ver[i].tag);
		}
		printf("\n");
	}
}

int count_table(void)
{
	int total = 0;
	for (int i = 0; i < version_count; i++)
		total += ver[i].used;
	return total;
}

unsigned exceptions;
struct exception excep[1000];

void show_exceptions(void)
{
	printf("%i exceptions: ", exceptions);
	for (int i = 0; i < exceptions; i++)
		printf("[%i, %Lu] ", excep[i].label, (chunk_t)excep[i].chunk);
	printf("\n");
}

void show_index(void)
{
	printf("child index: ");
	for (int i = 0; i < version_count; i++)
		printf("%i:%u ", i, children - child_index[i]);
	printf("\n");
}

int show_subtree(version_t version, int depth, version_t target)
{
	assert(depth < MAXVERSIONS);
	printf("%*s%i: ", 3 * depth, "", version);
	if (!is_ghost(version))
		printf("'%i'", ver[version].tag);
	else printf("~%i", child_count[version]);
	for (int i = 0; i < exceptions; i++)
		if (excep[i].label == version)
			printf(" [%Lu]", (chunk_t)excep[i].chunk);
	printf("%s\n", target == version ? " <==" : "");
	int total = 0;
	for (int i = 0; i < child_count[version]; i++)
		total += show_subtree(get_child(version, i), depth + 1, target);
	return total + 1;
}

void show_tree_with_target(tag_t tag)
{
	version_t target = tag == -1 ? 0 : find_tag(tag);
	int total = child_count[0] ? show_subtree(get_root(), 0, target) : 0;
	printf("%u versions\n", total);
}

void show_tree(void)
{
	show_tree_with_target(-1);
}

int count_subtree(label_t version, int depth)
{
	if (depth > MAXVERSIONS)
		return MAXVERSIONS;
	assert(ver[version].used);
	int total = 0;
	for (int i = 0; i < child_count[version]; i++)
		total += count_subtree(get_child(version, i), depth + 1);
	return total + 1;
}

int count_tree(void)
{
	return count_subtree(0, 0);
}

void order_tree(label_t version, int order)
{
	ordmap[version] = order;
	for (int i = 0; i < child_count[version]; i++)
		order_tree(get_child(version, i), order + 1);
}

/* Chunk allocation */

#define MAXCHUNKS MAXVERSIONS

typedef unsigned data_t;

chunk_t nextchunk;
data_t snapdata[MAXCHUNKS], orgdata = 0x1234;
data_t checkdata[MAXVERSIONS];
bool allocmap[MAXCHUNKS];

chunk_t new_chunk(data_t data)
{
	for (int i = 0; i < MAXCHUNKS; i++, nextchunk++) {
		if (nextchunk == MAXCHUNKS)
			nextchunk = 0;
		if (!allocmap[nextchunk])
			goto found;
	}
	error("out of chunks");
found:
	assert(!allocmap[nextchunk]);
	allocmap[nextchunk] = 1;
	snapdata[nextchunk] = data;
	return nextchunk++;

}

void free_chunk(chunk_t chunk)
{
	assert(allocmap[chunk]);
	allocmap[chunk] = 0;
}

/* Version allocation */

label_t new_version(label_t parent, uint32_t tag)
{
	int version;
	for (version = 1; version < version_count; version++)
		if (!ver[version].used)
			goto recycle;
	int last = version_count - 1;
	child_index[version_count] = version_count ? child_index[last] + child_count[last] : children;
	version = version_count++;
recycle:
	ver[version] = (struct version){ .parent = parent, .tag = tag, .used = 1 };
	assert(!child_count[version]);
	active_count++;
	return version;
}

void free_version(label_t version)
{
	assert(ver[version].used);
	ver[version].parent = 0;
	ver[version].used = 0;
	active_count--;
}

/* Version tree editing */

void add_exception(label_t label, chunk_t chunk)
{
	printf("new exception [%u, %Lu]\n", label, chunk);
	assert(exceptions < MAXVERSIONS);
	excep[exceptions++] = (struct exception){ .label = label, .chunk = chunk };
}

unsigned char pathmap[MAXVERSIONS][MAXVERSIONS >> 3];
unsigned char nearmap[MAXVERSIONS][MAXVERSIONS >> 3];

/*
 * Store the ord numbers in the version table.  Per-version bitmap specifies
 * whether any given version is on the path to root.  Walk the exception list
 * looking for the label on the path with the highest ord.
 */
struct exception *lookup_chunk(label_t target)
{
	if (!ver[target].pathmap) {
		trace_off(printf("load pathmap for %u \n", target);)
		memset(pathmap[target], 0, sizeof(pathmap[target]));
		for (label_t v = target; v; v = get_parent(v))
			set_bit(pathmap[target], v);
		ver[target].pathmap = 1;
	}
	int high = 0;
	unsigned char *path = pathmap[target];
	struct exception *found = NULL;
	for (struct exception *e = excep; e < excep + exceptions; e++)
		if (get_bit(path, e->label) && ordmap[e->label] > high)
			high = ordmap[(found = e)->label];
	return found;
}


unsigned count_near(label_t target)
{
	if (!ver[target].nearmap) {
		trace_off(printf("load nearmap for %u \n", target);)
		memset(nearmap[target], 0, sizeof(nearmap[target]));
		for (int i = 0; i < child_count[target]; i++)
			set_bit(nearmap[target], get_child(target, i));
		set_bit(nearmap[target], target);
		ver[target].nearmap = 1;
	}
	unsigned char *map = nearmap[target];
	int present = 0;
	for (struct exception *e = excep; e < excep + exceptions; e++)
		present += get_bit(map, e->label);
	assert(present <= child_count[target] + 1);
	return present;
}

struct exception *find_exception(label_t target)
{
	for (int i = 0; i < exceptions; i++)
		if (excep[i].label == target)
			return &excep[i];
	return NULL;
}

void set_present(bool flag)
{
	for (struct exception *e = excep; e < excep + exceptions; e++)
		ver[e->label].present = flag;
}

bool is_present(version_t version)
{
	return ver[version].present;
}

int count_heirs(label_t version)
{
	int heirs = 0;
	for (int i = 0; i < child_count[version]; i++) {
		version_t child = get_child(version, i);
		if (!is_present(child))
			heirs += count_heirs(child) + !is_ghost(child);
	}
	return heirs;
}

/*
 * O(exceptions) orphan test
 *
 * The orphan test is used in snapshot write and exception delete to identify
 * any new orphans created as a result of a write that creates an exclusive
 * exception for the only heir of the ghost exception, or a delete that removes
 * the only heir and does not promote a new heir.
 *
 * The current method of determining whether a ghost exception is an orphan is
 * to recurse through the subtree below the ghost until a visible version is
 * found that inherits the exception.  This test runs in O(versions) time.
 *
 * To perform this test in O(exceptions) time, we proceed as follows.
 *
 * Identify a subtree of the version tree consisting only of subtrees consisting
 * only of ghost versions in interior nodes and visible versions at the terminal
 * nodes, descending from the ghost ancestor of the victim version nearest the
 * root and not having any visible versions or present exceptions between itself
 * and the victim.  Call each node of that subtree a "nexus".  The interesting
 * question is whether any path from the ghost exception reaches a visible version
 * with no exception.  If not, then the ghost exception is an orphan that must be
 * deleted.
 *
 * This can be computed efficiently using a bottom up approach with a single pass
 * through the exception list.  At each nexus keep a count of the children of the
 * nexus that are known not to inherit from that nexus.  Call that the blocked
 * count.  Now:
 *
 * For each exception in the exception list
 *    If the version labeled by the exception is a nexus then increment the
 *    blocked count of the nexus
 *
 *    If the blocked count is now equal to the number of children of the nexus
 *    then repeat from the preceding step
 *
 * At completion, if the blocked count of the ghost ancestor is equal to its child
 * count, the ghost exception is an orphan.
 *
 * Not yet implemented.
 */

int inherited(version_t version)
{
	set_present(1);
	int heirs = count_heirs(version);
	set_present(0);
	//printf("version %i exception has %i heirs\n", version, heirs);
	return heirs;
}

label_t *find_child_pos(label_t parent, label_t child, unsigned count)
{
	/* insert sorted for cosmetic reasons */
	label_t *p = child_index[parent];
	for (int i = 0; i < count; i++, p++)
		if (child < *p)
			break;
	return p;
}

label_t *find_child(label_t parent, label_t child)
{
	for (int i = 0; i < child_count[parent]; i++)
		if (get_child(parent, i) == child)
			return child_index[parent] + i;
	error("child not found");
}

void insert_child(label_t parent, label_t child)
{
	label_t *p = find_child_pos(parent, child, child_count[parent]);
	vecmove(p + 1, p, children + version_count - p - 1);
	*p = child;
	for (int i = parent + 1; i < version_count; i++)
		child_index[i]++;
	child_count[parent]++;
	ver[child].parent = parent;
	ver[parent].nearmap = 0;
	order_tree(get_root(), 1); // overkill
}

void remove_child(label_t child)
{
	label_t parent = get_parent(child);
	label_t *p = find_child(parent, child);
	vecmove(p, p + 1, children + version_count - p - 1);
	for (int i = parent + 1; i < version_count; i++)
		child_index[i]--;
	child_count[parent]--;
	ver[parent].nearmap = 0;
}

void replace_child(label_t child, label_t newchild)
{
	version_t parent = get_parent(child);
	version_t *p1 = child_index[parent], *p2 = find_child(parent, child);
	vecmove(p2, p2 + 1, p1 + child_count[parent] - p2 - 1);
	p2 = find_child_pos(parent, newchild, child_count[parent] - 1);
	vecmove(p2 + 1, p2, p1 + child_count[parent] - p2 - 1);
	*p2 = newchild;
	ver[newchild].parent = parent;
	free_version(child);
	ver[parent].nearmap = 0;
}

void invalidate_path(version_t version)
{
	assert(version < MAXVERSIONS);
	assert(ver[version].used);
	ver[version].pathmap = 0;
	for (int i = 0; i < child_count[version]; i++)
		invalidate_path(get_child(version, i));
}

void promote_child(label_t child)
{
	version_t parent = get_parent(child);
	printf("promote version %u to child of %u \n", child, parent);
	assert(child_count[parent] == 1);
	remove_child(child);
	replace_child(parent, child);
	invalidate_path(child);
	order_tree(get_root(), 1); // overkill
}

void extract_children(void) // O(n^2)
{
	unsigned total = 0;
	memset(child_count, 0, sizeof child_count);
	for (int parent = 0; parent < version_count; parent++) {
		child_index[parent] = children + total;
		for (int child = 0; child < version_count; child++)
			if (get_parent(child) == parent) {
				children[total++] = child;
				child_count[parent]++;
			}
	}
}

/*
 * Three pass O(versions) tree extract
 *
 * 1: walk the table incrementing child counts of nonfree parents
 * 2: accumlate the counts to create the index, clear the counts
 * 3: walk the table filling in the children using the index
 */
void extract_children_fast_untested(void) // O(n^2)
{
	unsigned total = 0;
	vecset(child_count, 0, version_count);
	for (int i = 0; i < version_count; i++)
		if (ver[i].used)
			child_count[get_parent(i)]++;
	for (int i = 0; i < version_count; i++) {
		child_index[i] = children + total;
		total += child_count[i];
	}
	vecset(child_count, 0, version_count);
	for (int i = 0; i < version_count; i++)
		if (ver[i].used) {
			version_t parent = get_parent(i);
			child_index[parent][child_count[parent]++] = i;
		}
}

/*
 * O(exceptions) exception delete
 *
 * 1: walk the exception list incrementing per parent present child counts
 * 2: walk the list deleting target exceptions where present equals child count
 * 3: walk the list clearing present entries for the next time round
 */
label_t brood[MAXVERSIONS]; /* children present in exception list per parent */

bool delete_exceptions(version_t target, version_t parent)
{
	printf("delete target %u, parent %i, %i children\n", target, parent, child_count[target]);
	struct exception *limit = excep + exceptions, *save = excep, *kill = NULL;
	for (struct exception *from = excep; from < limit; from++)
		brood[get_parent(from->label)]++;
	set_present(1);
	if (!is_present(target)) {
		/* kill orphans */
		version_t ancestor = parent;
		while (!is_present(ancestor) && ancestor)
			ancestor = get_parent(ancestor);
		if (ancestor && is_ghost(ancestor) && is_present(ancestor) && !count_heirs(ancestor))
			kill = find_exception(ancestor);
	}
	if (kill)
		printf("kill orphan %u\n", kill->label);
	if (!is_ghost(parent))
		parent = 0;
	for (struct exception *from = excep; from < limit; from++) {
		if (from == kill)
			goto free;
		version_t label = from->label;
		if (label == target || label == parent) {
			if (child_count[label] == brood[label])
				goto free;
			if (child_count[label] == 1) {
				if (!count_heirs(label))
					goto free;
				printf("relabel %i as %i\n", label, get_child(label, 0));
				ver[label].present = 0;
				label = from->label = get_child(label, 0);
				ver[label].present = 1;
				goto keep;
			}
			if (child_count[label] > 1 && !count_heirs(label))
				goto free;
			goto keep;
		}
keep:
		*save++ = *from;
		continue;
free:
		ver[label].present = 0;
		printf("free [%i, %Li]\n", from->label, (chunk_t)from->chunk);
		free_chunk(from->chunk);
		exceptions--;
	}
	set_present(0);
	for (save = excep; save < excep + exceptions; save++)
		brood[get_parent(save->label)] = 0;
	return parent && child_count[parent] == 1;
}

/* External operations */

void snapshot_delete(tag_t tag)
{
	//if (cycle == 75109) show_tree_with_target(tag);
	version_t target = find_tag(tag);
	memset(brood, 0, sizeof(brood));
	ver[target].tag = 0;
	ver[target].ghost = 1; /* does not inherit ghost exception */
	version_t parent = get_parent(target);
	switch (child_count[target]) {
	case 0:
		remove_child(target); /* no relabel to deleted child */
		free_version(target);
		if (delete_exceptions(target, parent))
			promote_child(get_child(parent, 0));
		break;
	case 1:
		delete_exceptions(target, parent);
		promote_child(get_child(target, 0));
		break;
	default:
		delete_exceptions(target, parent);
	}
}
/*
 * Ghost exception inheritance
 *
 * Any ghost exception inherited only by ghosts may be deleted.
 *
 * If a target with more than one child, an exception and no heirs is deleted
 * then the exception may be deleted.
 *
 * Replacing a target with one child and no exception by its child with no
 * heirs reduces heirs of the parent.
 *
 * If a target has no children and no exception then removing it or replacing
 * its ghost parent with no exception by a sibling of the target with no
 * heirs reduces heirs of the parent.
 *
 * If heirs are reduced, a search for a ghost ancestor with an uninherited
 * exception must be performed.
 */

void snapshot_of_snapshot(tag_t tag, tag_t parent_tag)
{
	label_t parent = find_tag(parent_tag);
	label_t child = new_version(parent, tag);
	assert(!child_count[child]);
	insert_child(parent, child);
	order_tree(get_root(), 1); // overkill
}

void snapshot_of_origin(tag_t tag)
{
	label_t root = new_version(0, tag);
	if (!child_count[0]) {
		insert_child(0, root);
		return;
	}
	insert_child(root, get_child(0, 0));
	children[0] = root;
	invalidate_path(root);
	order_tree(get_root(), 1); // overkill
}

data_t snapshot_read(tag_t tag)
{
	struct exception *found = lookup_chunk(find_tag(tag));
	//printf("read version %u, chunk %Li \n", find_tag(tag), found->chunk);
	return found ? snapdata[found->chunk] : orgdata;
}

void snapshot_write(tag_t tag, data_t data)
{
	label_t target = find_tag(tag);
	printf("write 0x%x to snapshot %i version %u \n", data, tag, target);
	struct exception *e;

	/* has unique exception? */
	if (count_near(target) == child_count[target] + 1) {
		e = find_exception(target);
		goto rewrite;
	}

	/* create implicit version? */
	if (child_count[target]) {
		label_t child = new_version(target, tag);
		printf("implicit version %u of %u \n", child, target);
		insert_child(target, child);
		ver[target].ghost = 1;
		target = child;
	}

	/* relabel orphan? */
	set_present(1);
	label_t ancestor = get_parent(target);
	while (!is_present(ancestor) && is_ghost(ancestor))
		ancestor = get_parent(ancestor);
	bool relabel = is_ghost(ancestor) && count_heirs(ancestor) == 1;
	set_present(0);
	if (relabel) {
		printf("relabel version %u exception to %u!\n", ancestor, target);
		e = find_exception(ancestor);
		e->label = target;
		goto rewrite;
	}

	/* new exception */
	chunk_t chunk = new_chunk(data);
	add_exception(target, chunk);
	checkdata[target] = snapdata[chunk] = data;
	return;
rewrite:
	printf("rewrite chunk %Lu to 0x%x\n", (chunk_t)e->chunk, data);
	checkdata[target] = snapdata[e->chunk] = data;
	return;
}

void origin_write(data_t data)
{
	printf("write 0x%x to origin\n", data);
	if (child_count[0] && !find_exception(get_root()))
		add_exception(get_root(), new_chunk(orgdata));
	orgdata = data;
}

void fuzztest(int cycles)
{
	tag_t snap[MAXVERSIONS], tag, newtag = 1000;
	int snaps = 0;
	char *why;

	for (cycle = 1; cycle <= cycles; cycle++) {
		printf("--- cycle %i ---\n", cycle);
		if (!snaps || rand() % 5 == 0) {
			if (!snaps || (snaps < MAXVERSIONS / 2 && rand() % 2000000 < 1000000)) {
				/* Randomly create snapshot */
				tag = snap[snaps] = newtag++;
				if (!snaps || rand() % 20 == 0) {
					printf("create snapshot %u of origin\n", tag);
					snapshot_of_origin(tag);
					checkdata[find_tag(tag)] = orgdata;
				} else {
					tag_t parent = snap[rand() % snaps];
					printf("create snapshot %u of %u \n", tag, parent);
					snapshot_of_snapshot(tag, parent);
					checkdata[find_tag(tag)] = snapshot_read(parent);
				}
				snaps++;
			} else {
				/* Randomly delete snapshot */
				int which = rand() % snaps;
				printf("delete snapshot %u \n", snap[which]);
				delete_snapshot(snap[which]);
				snap[which] = snap[--snaps];
			}
		} else {
			/* Write to random snapshot */
			data_t data = rand();
			if (rand() % 20 == 0) {
				tag = -1;
				origin_write(data);
			} else {
				tag = snap[rand() % snaps];
				snapshot_write(tag, data);
			}
		}
continue;
		/* Validate version table */
		why = "version 0 corrupted";
		if (is_ghost(0) || child_count[0] > 1)
			goto eek;
		for (int version = 0; version < version_count; version++) {
			why = "present flag should be clear";
			if (ver[version].present) {
				printf("present flag should be clear for %u\n", version);
				goto eek;
			}
			why = "ghost has less than two children";
			if (is_ghost(version) && child_count[version] < 2) {
				printf("ghost %i has less than two children\n", version);
				goto eek;
			}
		}
		/* Validate version tree */
		why = "tree has a cycle";
		int counted = count_tree();
		if (counted == MAXVERSIONS)
			goto eek;
		why = "wrong number of versions in version tree";
		if (counted != active_count)
			goto eek;
		/* Validate exception list */
		bool member[MAXVERSIONS] = { };
		for (int i = 0; i < exceptions; i++) {
			label_t version = excep[i].label;
			//printf("[%i, %Lu]\n", version, (chunk_t)excep[i].chunk);
			why = "invalid exception label";
			if (version == 0 || version > MAXVERSIONS)
				goto eek;
			why = "deleted version in exception list";
			if (!ver[version].used)
				goto eek;
			why = "multiple exceptions with same label";
			if (member[version])
				goto eek;
			why = "ghost has orphan exception";
			if (is_ghost(version) && !inherited(version)) {
				printf("ghost %i has orphan exception\n", version);
				goto eek;
			}
			member[version] = 1;
		}
		/* Validate snapshot data */
		why = "snapshot has wrong data";
		for (int i = 0; i < snaps; i++) {
			data_t data = snapshot_read(snap[i]);
			if (data != checkdata[find_tag(snap[i])]) {
				printf("snapshot %u has wrong data 0x%x\n", snap[i], data);
				tag = snap[i];
				goto eek;
			}
		}
		//if (cycle == 75109) { show_tree(); exit(1); }
	}
	show_tree();
	show_exceptions();
	return;
eek:
	printf("--- Failed at cycle %u --- \n", cycle);
	show_tree_with_target(tag);
	//show_table();
	printf("tree count = %u, table count = %u, active count = %u\n", count_tree(), count_table(), active_count);
	show_exceptions();
	error("%s", why);
}

int main(void)
{
	label_t v0 = new_version(-1, 0);

#if 1
	srand(12345);
	fuzztest(20000000);
	return 0;
#endif

	tag_t nexttag = 1001;
	label_t v1 = v1 = new_version(v0, nexttag++);
	label_t v2 = v2 = new_version(v1, nexttag++);
	label_t v3 = v3 = new_version(v2, nexttag++);
#if 0
	show_table();
	extract_children();
	show_tree();
	hexdump(child_count, 16);
	hexdump(child_index, 16);
	hexdump(children, 16);
	promote_child(v3);
	//remove_version(v5);
	//delete_snapshot(2000);
	//nested_snapshot(123, 2005);
	//snapshot_of_origin(123);
	show_table();
	hexdump(child_count, 16);
	hexdump(child_index, 16);
	hexdump(children, 16);
	show_tree();
	extract_children();
	show_tree();
	return 0;
	free_version(v1);
	free_version(v4);
	show_table();
	return 0;
#endif
	extract_children();
	label_t target = v2;
	tag_t tag = ver[target].tag;
	add_exception(v2, new_chunk(0));
	show_exceptions();
	show_tree();
	printf("data = %u\n", snapshot_read(tag));
	snapshot_write(tag, 0x333);
	show_tree();
	snapshot_write(1003, 0x666);
	show_tree();
//	hexdump(snapdata, 16);
//	origin_write(666);
//	origin_write(777);
//	snapshot_write(ver[target].tag, 555);
	show_exceptions();
	hexdump(snapdata, 32);
	printf("data = 0x%x, orgdata = 0x%x\n", snapshot_read(tag), orgdata);
	printf("v3 data = 0x%x\n", snapshot_read(ver[v3].tag));
	show_tree();
	hexdump(nearmap[v2], 16);
//	delete_exceptions((label_t[]){ v7 }, 1);
	delete_snapshot(1003);
	show_tree();
	show_exceptions();
	delete_snapshot(1001);
	show_tree();
	show_exceptions();
	delete_snapshot(1002);
	show_tree();
	show_exceptions();
	snapshot_of_origin(1009);
	show_tree();
	show_exceptions();
	printf("data = 0x%x, orgdata = 0x%x\n", snapshot_read(1002), orgdata);
	hexdump(child_index, 16);
	return 0;

	label_t v4 = v4 = new_version(v1, nexttag++);
	label_t v5 = v5 = new_version(v4, nexttag++);
	label_t v6 = v6 = new_version(v4, nexttag++);
	add_exception(v5, new_chunk(0));
	add_exception(v6, new_chunk(0));
#if 0
	load_nearmap(v4);
	hexdump(nearmap[v4], 16);
	return 0;
#endif

	return 0;
}