/*
 * tbuf.c -- implement text editor buffers using trees
 *
 * Part of Publib, see man page for more information.
 * "@(#)publib-tbuf:$Id: tbuf.c,v 1.12 2003/11/15 18:24:11 liw Exp $"
 *
 * 
 * A brief description of how this works.
 * XXX probably needs to be updated
 * 
 * The text of a buffer is broken down into `chunks', which contain up to
 * CHUNK_MAX characters each. The chunks are kept in a B-tree -like tree,
 * as leaf nodes. Chunks and trees are not modified after they have been
 * created. Instead, if the buffer needs to be modified, a copy is made,
 * but those parts of the buffer that have not been modifed are shared
 * between the original and the new copy.
 * 
 * For example, assume we have the following tree, representing the buffer
 * "abcdef" (with CHUNK_MAX being 3):
 * 
 * 	  {=]
 * 	  / \
 * 	abc def
 * 
 * ("[=]" is an interior node.) Now assume that we want to delete "abc" from
 * the buffer. We then create a new buffer that has a new interior node that
 * has only one child, the chunk that contains "def":
 * 
 * 	  {=]		[=]
 * 	  / \            :
 * 	abc def <......../
 * 
 * This way, the only new memory needed is that for the (small) interior node.
 * In a larger example some of the interior nodes would be shared as well.
 * 
 * When the original buffer is no longer needed, it can be destroyed. This
 * does not destroy the "def" chunk, since it is shared.
 * 
 * Similarly, when two buffers are catenated, the new tree uses as many
 * chunks and interior nodes of the old tree as possible. When sharing
 * is impossible, some nodes are copied and the copies are altered as
 * necessary.
 * 
 * We use reference counting to implement the sharing of nodes and chunks
 * between trees. When a node or chunk is created, it's reference count
 * is set to 1. When a new tree is created and a new node is created and
 * points at a node in the old tree, the reference count for the old node is
 * incremented. However, nodes and chunks below that node are not touched,
 * since the new node does not directly reference them. When a tree is
 * destroyed, reference counts are decremented and if they fall to zero,
 * the node or chunk is freed.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include <string.h>

#include "tbuf.h"


/*
 * Internal data structures.
 *
 * This has some potential improvement for the future: At the moment, all
 * chunks and nodes are allocated with separate calls to malloc, and at least
 * in some environments this is rather expensive, both in CPU time and memory
 * use. It would probably make sense to allocate lots of memory at once with
 * malloc, and then have a simpler custom memory allocator that gives out parts
 * of the large piece of malloc'd memory. At least for the chunk and node
 * structs, which are of a constant size; not necessarily for the text parts
 * of chunks.
 */

/* The maximum number of characters in a chunk. */
#define CHUNK_MAX 10 /* XXX */
#ifndef CHUNK_MAX
#define CHUNK_MAX 128
#endif

/* The chunk itself. */
typedef struct chunk Chunk;
struct chunk {
	Chunk *next;
	size_t length;
	char *chars;
	unsigned visited:1;
};


/* The maximum number of children a node may contain. */
#define NODE_MAX 3 /* XXX */
#ifndef NODE_MAX
#define NODE_MAX    8
#endif

/* The node itself. `height' is the level of this node, counting from leafs
   (level 1) upwards, so that a node having chunks as its children has a 
   height of 2. `length' is
   the length of all chunks in the subtree for which this node is root. */
typedef struct node Node;
struct node {
	Node *next;
	size_t height, length, kids;
	union {
		Chunk *chunk[NODE_MAX];
		Node *node[NODE_MAX];
	} x;
	unsigned visited:1;
};


/* The buffer as presented to the user. (Of course, the user never sees inside
   this structure. Bondage and discipline needs to be enforced, them program
   writing lusers are dangerous.)
   
   `height' is the height of the tree containing the buffer. If it is 0,
   the buffer is empty. If 1, the tree only needs a chunk, so use x.chunk.
   Otherwise, there is at least one node, so use x.root.
   
   `offset' is the offset where `our' part of the character sequence
   described by the tree begins. `length' is the number of characters
   that belong to this buffer after the offset. This allows us to implement
   tbuf_copy very cheaply: it does not need to modify any part of the tree,
   just create a new Tbuf with modified offset and length fields.  */
struct tbuf {
	Tbuf *next, *prev;
	size_t height, offset, length;
	union {
		Chunk *chunk;
		Node *root;
	} x;
};


/* List of all Tbufs, Nodes and Chunk that exist at the moment. Needed for 
   garbage collection. */
static Tbuf *tbuf_chain = NULL;
static Node *node_chain = NULL;
static Chunk *chunk_chain = NULL;

/* List of unused Nodes. */
static Node *free_nodes = NULL;


/*
 * Routines to print out the data structures for debugging. These are not
 * normally enabled.
 */

#if 0
#define dump_chunk(f, level, chunk) ((void) 0)
#define dump_node(f, level, node) ((void) 0)
#define dump_tbuf(f, tbuf) ((void) 0)
#else

static void dump_chunk(FILE *f, int level, Chunk *chunk) {
	int c, spaces;
	size_t i;
	
	spaces = level * 2;
	fprintf(f, "%*schunk at %p\n", spaces, "", (void *) chunk);
	fprintf(f, "%*s..length=%lu\n", spaces, "", (unsigned long) chunk->length);
	fprintf(f, "%*s..chars(%p)=<", spaces, "", (void *) chunk->chars);
	fflush(f);
	for (i = 0; i < chunk->length; ++i) {
		c = chunk->chars[i];
		if (isprint(c))
			fprintf(f, "%c", c);
		else
			fprintf(f, "<%02x>", (unsigned) c);
	}
	fprintf(f, ">\n");
}

static void dump_node(FILE *f, int level, Node *node) {
	int spaces;
	size_t i;
	
	spaces = level * 2;
	fprintf(f, "%*snode at %p\n", spaces, "", (void *) node);
	fprintf(f, "%*s..height=%lu\n", spaces, "", (unsigned long) node->height);
	fprintf(f, "%*s..length=%lu\n", spaces, "", (unsigned long) node->length);
	fprintf(f, "%*s..kids=%lu\n", spaces, "", (unsigned long) node->kids);
	
	if (node->height == 2) {
		for (i = 0; i < node->kids; ++i)
			dump_chunk(f, level + 1, node->x.chunk[i]);
	} else {
		for (i = 0; i < node->kids; ++i)
			dump_node(f, level + 1, node->x.node[i]);
	}
}

#if 0
static void dump_tbuf(FILE *f, Tbuf *tbuf) {
	fprintf(f, "tbuf at %p\n", (void *) tbuf);
	fprintf(f, "..height=%lu\n", (unsigned long) tbuf->height);
	fprintf(f, "..offset=%lu\n", (unsigned long) tbuf->offset);
	fprintf(f, "..length=%lu\n", (unsigned long) tbuf->length);
	if (tbuf->height == 1)
		dump_chunk(f, 1, tbuf->x.chunk);
	else if (tbuf->height >= 2)
		dump_node(f, 1, tbuf->x.root);
	fprintf(f, "end of tbuf dump at %p\n", (void *) tbuf);
}
#endif

#endif


/*
 * tbuf_create and the routines it needs. `new_chunk' is used elsewhere as
 * well.
 */

/* Create a new chunk. Advance `*chars' and reduce `*nchars' by the length
   of the newly created chunk. */
static Chunk *new_chunk(const char **chars, size_t *nchars) {
	size_t n;
	Chunk *chunk;

	if (*nchars <= CHUNK_MAX)
		n = *nchars;
	else
		n = CHUNK_MAX;

	chunk = malloc(sizeof(Chunk));
	if (chunk == NULL)
		return NULL;

	if (n == 0)
		chunk->chars = NULL;
	else {
		chunk->chars = malloc(n);
		if (chunk->chars == NULL) {
			free(chunk);
			return NULL;
		}
		memcpy(chunk->chars, *chars, n);
	}

	chunk->length = n;
	*chars += n;
	*nchars -= n;
	chunk->visited = 0;
	chunk->next = chunk_chain;
	chunk_chain = chunk;

	return chunk;
}

static Node *new_empty_node(void) {
	Node *node;

	if (free_nodes == NULL) {
		node = malloc(sizeof(Node));
		if (node == NULL)
			return NULL;
	} else {
		node = free_nodes;
		free_nodes = free_nodes->next;
	}
	node->next = node_chain;
	node_chain = node;
	node->height = 0;
	node->length = 0;
	node->kids = 0;
	node->visited = 0;
	
	return node;
}

/* Create a new node. `*chars' and `*nchars' as for new_chunk (surprisingly
   enough :). */
static Node *new_node(size_t height, const char **chars, size_t *nchars) {
	Node *node;
	size_t i;

	node = new_empty_node();
	if (node == NULL)
		return NULL;

	node->height = height;
	node->length = 0;
	node->visited = 0;

	if (height == 2) {
		for (i = 0; i < NODE_MAX && *nchars > 0; ++i) {
			node->x.chunk[i] = new_chunk(chars, nchars);
			if (node->x.chunk[i] == NULL)
				return NULL;
			node->length += node->x.chunk[i]->length;
		}
	} else {
		for (i = 0; i < NODE_MAX && *nchars > 0; ++i) {
			node->x.node[i] = new_node(height-1, chars, nchars);
			if (node->x.node[i] == NULL)
				return NULL;
			node->length += node->x.node[i]->length;
		}
	}
	node->kids = i;
	
	return node;
}

/* Build a tree of nodes and chunks. */
static void *build_tree(size_t *height, const char *chars, size_t nchars) {
	size_t max_length_for_height;

	assert(nchars > 0);
	*height = 1;
	max_length_for_height = CHUNK_MAX;
	while (max_length_for_height < nchars) {
		++*height;
		max_length_for_height *= NODE_MAX;
	}

	if (*height == 1)
		return new_chunk(&chars, &nchars);
	else
		return new_node(*height, &chars, &nchars);
}


static Tbuf *new_tbuf(void) {
	Tbuf *tbuf;
	
	tbuf = malloc(sizeof(Tbuf));
	if (tbuf == NULL)
		return NULL;
	tbuf->height = 0;
	tbuf->offset = 0;
	tbuf->length = 0;
	tbuf->next = tbuf_chain;
	tbuf->prev = NULL;
	if (tbuf_chain != NULL)
		tbuf_chain->prev = tbuf;
	tbuf_chain = tbuf;
	return tbuf;
}


Tbuf *tbuf_create(const char *chars, size_t nchars) {
	Tbuf *tbuf;
	void *p;

	tbuf = new_tbuf();

	if (nchars == 0) {
		p = NULL;
	} else {
		p = build_tree(&tbuf->height, chars, nchars);
		if (p == NULL) {
			tbuf_destroy(tbuf);
			return NULL;
		}
	}

	switch (tbuf->height) {
	case 0:
		tbuf->x.chunk = NULL;
		break;
	case 1:
		tbuf->x.chunk = p;
		break;
	default:
		tbuf->x.root = p;
		break;
	}

	tbuf->length = nchars;
	return tbuf;
}



/*
 * tbuf_destroy and the routines it needs.
 */

static void chunk_destroy(Chunk *chunk) {
	if (chunk != NULL) {
		free(chunk->chars);
		free(chunk);
	}
}

static void node_destroy(Node *node) {
	node->next = free_nodes;
	free_nodes = node;
}

static void node_zero_visited(Node *node) {
	size_t i;

	node->visited = 0;
	if (node->height == 2) {
		for (i = 0; i < node->kids; ++i)
			node->x.chunk[i]->visited = 0;
	} else {
		for (i = 0; i < node->kids; ++i)
			node_zero_visited(node->x.node[i]);
	}
}

static void garbage_collect(void) {
	Tbuf *tbuf;
	Node *node, *new_node_chain, *next_node;
	Chunk *chunk, *new_chunk_chain, *next_chunk;
	
	for (chunk = chunk_chain; chunk != NULL; chunk = chunk->next)
		chunk->visited = 1;
	for (node = node_chain; node != NULL; node = node->next)
		node->visited = 1;

	for (tbuf = tbuf_chain; tbuf != NULL; tbuf = tbuf->next) {
		switch (tbuf->height) {
		case 0:
			break;
		case 1:
			tbuf->x.chunk->visited = 0;
			break;
		default:
			node_zero_visited(tbuf->x.root);
		}
	}
	
	new_chunk_chain = NULL;
	for (chunk = chunk_chain; chunk != NULL; chunk = next_chunk) {
		next_chunk = chunk->next;
		if (chunk->visited == 1)
			chunk_destroy(chunk);
		else {
			chunk->next = new_chunk_chain;
			new_chunk_chain = chunk;
		}
	}
	chunk_chain = new_chunk_chain;
	
	new_node_chain = NULL;
	for (node = node_chain; node != NULL; node = next_node) {
		next_node = node->next;
		if (node->visited == 1)
			node_destroy(node);
		else {
			node->next = new_node_chain;
			new_node_chain = node;
		}
	}
	node_chain = new_node_chain;
}


void tbuf_destroy(Tbuf *tbuf) {
	assert(tbuf != NULL);
#if 1
	if (tbuf_chain == tbuf)
		tbuf_chain = tbuf->next;
	if (tbuf->prev != NULL)
		tbuf->prev->next = tbuf->next;
	if (tbuf->next != NULL)
		tbuf->next->prev = tbuf->prev;
	free(tbuf);
#endif
	garbage_collect();
}


/*
 * tbuf_chars and the routines it needs.
 */

/* Copy part of a chunk to a character array, and advance the pointer to the
   array by the amount copied. */
static void chunk_collect(char **chars, Chunk *chunk, size_t off, size_t n) {
	memcpy(*chars, chunk->chars + off, n);
	*chars += n;
}

/* Visit all relevant chunks and copy the relevant parts of them. Subtrees
   can sometimes be skipped completely, based on `*off' and their length. */
static void node_collect(char **chars, Node *node, size_t *off, size_t *n) {
	size_t i;
	Chunk *chunk;

	if (node->length <= *off)
		*off -= node->length;
	else if (node->height > 2) {
		for (i = 0; i < node->kids && *n > 0; ++i)
			node_collect(chars, node->x.node[i], off, n);
	} else {
		for (i = 0; i < node->kids && *n > 0; ++i) {
			chunk = node->x.chunk[i];
			if (chunk->length <= *off)
				*off -= chunk->length;
			else if (*n <= chunk->length) {
				chunk_collect(chars, chunk, *off, *n);
				*n = 0;
			} else {
				chunk_collect(chars, chunk, *off, chunk->length);
				*off = 0;
				*n -= chunk->length;
			}
		}
	}
}

void tbuf_chars(char *chars, Tbuf *tbuf, size_t start, size_t length) {
	assert(chars != NULL);
	assert(tbuf != NULL);

	if (start >= tbuf->length || length == 0)
		return;
	if (start + length > tbuf->length)
		length = tbuf->length - start;

	start += tbuf->offset;
	if (tbuf->height == 1)
		chunk_collect(&chars, tbuf->x.chunk, start, length);
	else
		node_collect(&chars, tbuf->x.root, &start, &length);
}



/*
 * tbuf_cat and stuff that it needs. This is the most difficult operation
 * and needs the largest amount of code. This needs pictures to be explained,
 * I think, and I don't have the time to draw them now.
 */

/* Create a new chunk out an old one. */
static Chunk *copy_chunk(Chunk *chunk, size_t offset, size_t length) {
	const char *p;
	
	assert(offset < chunk->length);
	assert(offset + length <= chunk->length);
	p = chunk->chars + offset;
	return new_chunk(&p, &length);
}

/* Create a new node out of an old one. */
/* NOTE: to is "up to", not inclusive. */
static Node *copy_node(Node *node, void *before, size_t from, size_t to,
			void *after) {
	Node *node_new;
	size_t i;
	
	node_new = new_empty_node();
	if (node_new == NULL)
		return NULL;

	node_new->height = node->height;
	node_new->length = 0;
	node_new->kids = 0;

	if (node_new->height == 2) {
		if (before != NULL)
			node_new->x.chunk[node_new->kids++] = before;
		for (i = from; i < to; ++i)
			node_new->x.chunk[node_new->kids++] = node->x.chunk[i];
		if (after != NULL)
			node_new->x.chunk[node_new->kids++] = after;
		for (i = 0; i < node_new->kids; ++i)
			node_new->length += node_new->x.chunk[i]->length;
	} else {
		if (before != NULL)
			node_new->x.node[node_new->kids++] = before;
		for (i = from; i < to; ++i)
			node_new->x.node[node_new->kids++] = node->x.node[i];
		if (after != NULL)
			node_new->x.node[node_new->kids++] = after;
		for (i = 0; i < node_new->kids; ++i)
			node_new->length += node_new->x.node[i]->length;
	}

	assert(node_new->kids > 0);
	return node_new;
}

/* Create a new node tree out of an old one that begins after `offset' in the
   old one. */
static Node *chop_before(Node *root, size_t offset) {
	Node *node, *node_new, *root_new;
	Chunk *chunk, *chunk_new;
	size_t i, orig_offset;

	if (offset == 0)
		return root;

	orig_offset = offset;
	if (root->height == 2) {
		for (i = 0; ; ++i) {
			assert(i < root->kids);
			chunk = root->x.chunk[i];
			if (chunk->length >= offset)
				break;
			offset -= chunk->length;
		}
		if (offset == chunk->length)
			chunk_new = NULL;
		else {
			chunk_new = copy_chunk(chunk, offset, chunk->length - offset);
			if (chunk_new == NULL)
				return NULL;
		}
		root_new = copy_node(root, chunk_new, i+1, root->kids, NULL);
		if (root_new == NULL)
			return NULL;
		assert(root_new->length == root->length - orig_offset);
	} else {
		for (i = 0; ; ++i) {
			assert(i < root->kids);
			node = root->x.node[i];
			if (node->length >= offset)
				break;
			offset -= node->length;
		}
		if (offset == node->length)
			node_new = NULL;
		else {
			node_new = chop_before(node, offset);
			if (node_new == NULL)
				return NULL;
		}
		root_new = copy_node(root, node_new, i+1, root->kids, NULL);
		if (root_new == NULL)
			return NULL;
		assert(root_new->length == root->length - orig_offset);
	}
	return root_new;
}

/* Create a new node tree out of an old one that ends before `offset' in the
   old one. */
static Node *chop_after(Node *root, size_t offset) {
	Node *node, *node_new, *root_new;
	Chunk *chunk, *chunk_new;
	size_t i, orig_offset;
	
	if (offset >= root->length)
		return root;

	orig_offset = offset;
	if (root->height == 2) {
		for (i = 0; ; ++i) {
			assert(i < root->kids);
			chunk = root->x.chunk[i];
			if (chunk->length > offset)
				break;
			offset -= chunk->length;
		}
		chunk_new = copy_chunk(chunk, 0, offset);
		if (chunk_new == NULL)
			return NULL;
		assert(chunk_new->length == offset);
		root_new = copy_node(root, NULL, 0, i, chunk_new);
		if (root_new == NULL)
			return NULL;
		assert(root_new->length == orig_offset);
	} else {
		for (i = 0; ; ++i) {
			assert(i < root->kids);
			node = root->x.node[i];
			if (node->length > offset)
				break;
			offset -= node->length;
		}
		node_new = chop_after(node, offset);
		if (node_new == NULL)
			return NULL;
		root_new = copy_node(root, NULL, 0, i, node_new);
		if (root_new == NULL)
			return NULL;
		assert(root_new->length == orig_offset);
	}

	assert(root_new->height == root->height);
	return root_new;
}

/* Make sure a node tree is at least of a particular height. */
static void *make_of_height(size_t wanted, void *ptr, size_t current) {
	Node *ptr_new;

	while (current < wanted) {
		ptr_new = new_empty_node();
		if (ptr_new == NULL)
			return NULL;
		ptr_new->height = current + 1;
		ptr_new->kids = 1;
		switch (current) {
		case 0:
			assert(ptr == NULL);
			ptr_new->x.chunk[0] = NULL;
			ptr_new->length = 0;
			break;
		case 1:
			ptr_new->x.chunk[0] = ptr;
			ptr_new->length = ((Chunk *) ptr)->length;
			break;
		default:
			ptr_new->x.node[0] = ptr;
			ptr_new->length = ((Node *) ptr)->length;
			break;
		}
		ptr = ptr_new;
		++current;
	}
	return ptr;
}


#if 0

static Node *make_root(Tbuf *tbuf) {
	Node *root;
	
	assert(tbuf->height > 0);
	if (tbuf->height >= 2)
		return tbuf->x.root;

	root = new_empty_node();
	if (root == NULL)
		return NULL;
	root->height = 2;
	root->length = tbuf->length;
	root->kids = 1;
	root->x.chunk[0] = tbuf->x.chunk;

	return root;
}

static Chunk *rightmost_chunk(Node *root) {
	assert(root->height >= 2);
	while (root->height > 2)
		root = root->x.node[root->kids - 1];
	return root->x.chunk[root->kids - 1];
}

static Chunk *leftmost_chunk(Node *root) {
	assert(root->height >= 2);
	while (root->height > 2)
		root = root->x.node[0];
	return root->x.chunk[0];
}

#endif

static Node *replace_rightmost_chunk(Node *root, Chunk *chunk) {
	Node *new, *new_kid;
	int i;

	new = new_empty_node();
	if (new == NULL)
		return NULL;

	new->height = root->height;
	new->kids = root->kids;

	if (root->height == 2) {
		new->length = root->length
				- root->x.chunk[root->kids-1]->length
				+ chunk->length;
		for (i = 0; i < root->kids-1; ++i)
			new->x.chunk[i] = root->x.chunk[i];
		new->x.chunk[root->kids-1] = chunk;
	} else {
		new_kid = replace_rightmost_chunk(root->x.node[root->kids-1], 
							chunk);
		new->length = root->length
				- root->x.node[root->kids-1]->length
				+ new_kid->length;
		for (i = 0; i < root->kids-1; ++i)
			new->x.node[i] = root->x.node[i];
		new->x.node[root->kids-1] = new_kid;
	}

	assert(new->kids > 0);
	return new;
}

static Tbuf *copy_tbuf(Tbuf *tbuf) {
	Tbuf *new;
	
	new = new_tbuf();
	if (new == NULL)
		return NULL;
	new->height = tbuf->height;
	new->offset = tbuf->offset;
	new->length = tbuf->length;
	new->x = tbuf->x;
	return new;
}

static Node *trim_chunk_tree(Tbuf *tbuf) {
	Node *root;
	Chunk *chunk;
	
	switch (tbuf->height) {
	case 0:
		assert(0);
		return NULL;
	
	case 1:
		root = new_empty_node();
		if (root == NULL)
			return NULL;
		chunk = tbuf->x.chunk;
		root->length = chunk->length;
		root->height = 2;
		root->kids = 1;
		root->x.chunk[0] = chunk;
		return root;
		
	default:
		root = tbuf->x.root;
		root = chop_after(root, tbuf->offset + tbuf->length);
		if (root == NULL)
			return NULL;
		return chop_before(root, tbuf->offset);
	}
	/*NOTREACHED*/
}

static void copy_kids(void **kids, int *total, void **tab, int from, int to) {
	int i;
	
	for (i = from; i <= to; ++i)
		kids[(*total)++] = tab[i];
}

static void copy_kids_to_node(Node *node, void **kids, int from, int to) {
	int i;
	Chunk *ckid;
	Node *nkid;
	
	switch (node->height) {
	case 1:
		assert(0);
		break;
	case 2:
		for (i = from; i <= to; ++i) {
			ckid = kids[i];
			node->x.chunk[node->kids++] = ckid;
			node->length += ckid->length;
		}
		break;
	default:
		for (i = from; i <= to; ++i) {
			nkid = kids[i];
			node->x.node[node->kids++] = nkid;
			node->length += nkid->length;
		}
		break;
	}
}

static void collect_right_side(void **tab, Node *root) {
	int i;
	
	for (i = root->height; i > 2; --i) {
		tab[i] = root;
		root = root->x.node[root->kids-1];
	}
	assert(root->height == 2);
	tab[1] = root->x.chunk[root->kids-1];
}

static void collect_left_side(void **tab, Node *root) {
	int i;
	
	for (i = root->height; i > 2; --i) {
		tab[i] = root;
		root = root->x.node[0];
	}
	assert(root->height == 2);
	tab[1] = root->x.chunk[0];
}

static void combine_chunks(void **p1, void **p2, Chunk *chunk1, Chunk *chunk2)
{
	size_t len1, len2, len;
	char buf[CHUNK_MAX];
	const char *cstr;
	
	assert(p1 != NULL);
	assert(p2 != NULL);
	assert(chunk1 != NULL);
	assert(chunk2 != NULL);

	len1 = chunk1->length;
	len2 = chunk2->length;
	
	if (len1 + len2 > CHUNK_MAX) {
		*p1 = chunk1;
		*p2 = chunk2;
	} else {
		memcpy(buf, chunk1->chars, len1);
		memcpy(buf + len1, chunk2->chars, len2);
		cstr = buf;
		len = len1 + len2;
		*p1 = new_chunk(&cstr, &len);
		*p2 = NULL;
		assert(((Chunk *) *p1)->length == len1 + len2);
	}
}

#define SMART_CAT_HEIGHT 100

static Node *smart_cat(Tbuf *tbuf1, Tbuf *tbuf2, Node *root1, Node *root2) {
	void *tab1[SMART_CAT_HEIGHT] = { NULL, };
	void *tab2[SMART_CAT_HEIGHT] = { NULL, };
	void *allkids[NODE_MAX * 2];
	void *p1, *p2, *q1, *q2;
	size_t i, h1, h2, h_max;
	int kids1, kids2, total_kids;

	h1 = root1->height;
	h2 = root2->height;
	
	assert(h1 > 0);
	assert(h2 > 0);
	
	if (h1 >= SMART_CAT_HEIGHT || h2 >= SMART_CAT_HEIGHT)
		return NULL;	/* stupid_cat will handle this */
	if (h1 < h2)
		h_max = h2;
	else
		h_max = h1;

	collect_right_side(tab1, root1);
	collect_left_side(tab2, root2);
	
	combine_chunks(&p1, &p2, tab1[1], tab2[1]);
	if (p1 == NULL)
		return NULL;
	
	for (i = 2; i <= h_max; ++i) {
		kids1 = (tab1[i] == NULL) ? 0 : ((Node *) tab1[i])->kids;
		kids2 = (tab2[i] == NULL) ? 0 : ((Node *) tab2[i])->kids;
		
		if (kids1 + kids2 > NODE_MAX)
			return NULL;
		
		total_kids = 0;
		copy_kids(allkids, &total_kids, tab1, 0, kids1-2);
		if (p1 != NULL)
			allkids[total_kids++] = p1;
		if (p2 != NULL)
			allkids[total_kids++] = p2;
		copy_kids(allkids, &total_kids, tab1, 1, kids2-1);
			
		if (total_kids > NODE_MAX) {
			q1 = new_empty_node();
			if (q1 == NULL)
				return NULL;
			((Node *)q1)->height = i;
			copy_kids_to_node(q1, allkids, 0, NODE_MAX-1);

			q2 = new_empty_node();
			if (q2 == NULL)
				return NULL;
			((Node *)q2)->height = i;
			copy_kids_to_node(q2, allkids, NODE_MAX, total_kids-1);
		} else {
			q1 = new_empty_node();
			if (q1 == NULL)
				return NULL;
			((Node *)q1)->height = i;
			copy_kids_to_node(q1, allkids, 0, total_kids-1);
			q2 = NULL;
		}
		
		p1 = q1;
		p2 = q2;
	}

	if (p2 != NULL)
		return NULL;
	
	assert(p1 != NULL);
	return p1;
}

static Node *stupid_cat(Tbuf *tbuf1, Tbuf *tbuf2, Node *p1, Node *p2) {
	Node *new_root;
	size_t h1, h2;
	
printf("stupid_cat: ------------------------------------------------\n");
	h1 = p1->height;
	h2 = p2->height;
	if (h1 < h2) {
		p1 = make_of_height(h2, p1, h1);
		h1 = h2;
	} else if (h2 < h2) {
		p2 = make_of_height(h1, p2, h2);
		h2 = h1;
	}
	assert(h1 > 1);
	if (p1 == NULL || p2 == NULL)
		return NULL;
	
	new_root = new_empty_node();
	new_root->height = h1 + 1;
	new_root->length = p1->length + p2->length;
	new_root->kids = 2;
	new_root->x.node[0] = p1;
	new_root->x.node[1] = p2;
	
	return new_root;
}

Tbuf *tbuf_cat(Tbuf *tbuf1, Tbuf *tbuf2) {
	Tbuf *tbuf_new;
	Node *p1, *p2, *new_root;

	if (tbuf1->length == 0)
		return copy_tbuf(tbuf2);
	if (tbuf2->length == 0)
		return copy_tbuf(tbuf1);
	
	p1 = trim_chunk_tree(tbuf1);
	p2 = trim_chunk_tree(tbuf2);
	if (p1 == NULL || p2 == NULL)
		return NULL;
	
	new_root = smart_cat(tbuf1, tbuf2, p1, p2);
	if (new_root == NULL)
		new_root = stupid_cat(tbuf1, tbuf2, p1, p2);
	if (new_root == NULL)
		return NULL;

	tbuf_new = new_tbuf();
	if (tbuf_new == NULL)
		return NULL;
	tbuf_new->height = new_root->height;
	tbuf_new->length = new_root->length;
	tbuf_new->x.root = new_root;

	return tbuf_new;
}


/*
 * tbuf_copy needs no auxiliary routines of its own.
 */

Tbuf *tbuf_copy(Tbuf *tbuf, size_t start, size_t length) {
	Tbuf *tbuf_new;
	Node *temp;

	if (start >= tbuf->length || length == 0)
		return tbuf_create("", 0);

	if (start + length > tbuf->length)
		length = tbuf->length - start;

	tbuf_new = new_tbuf();
	if (tbuf_new == NULL)
		return NULL;

	switch (tbuf->height) {
	case 0:
		tbuf_new->height = 0;
		tbuf_new->offset = 0;
		tbuf_new->length = 0;
		break;
	
	case 1:
		tbuf_new->height = 1;
		tbuf_new->offset = tbuf->offset + start;
		tbuf_new->length = length;
		tbuf_new->x.chunk = tbuf->x.chunk;
		break;
	
	default:
#if 1
		temp = chop_before(tbuf->x.root, tbuf->offset);
		temp = chop_after(temp, tbuf->length);
		while (temp->height > 2 && temp->kids == 1)
			temp = temp->x.node[0];
		tbuf_new->x.root = temp;
		tbuf_new->height = temp->height;
#else
		tbuf_new->x.root = tbuf->x.root;
		tbuf_new->height = tbuf->height;
#endif
		tbuf_new->offset = 0;
		tbuf_new->length = length;
		break;
	}

	return tbuf_new;
}


/*
 * tbuf_get_stats. Statistics gathering.
 */

static void gather_chunk_stats(struct tbuf_stat *stat, Chunk *chunk, 
int shared) {
	size_t chunk_memory;
	
	if (!chunk->visited) {
		++stat->tbuf_chunks;
		chunk_memory = sizeof(Chunk) + chunk->length;
		stat->tbuf_memory_total += chunk_memory;
		chunk->visited = 1;
	}
}

static void gather_node_stats(struct tbuf_stat *stat, Node *node, int shared) {
	size_t i;
	
	if (!node->visited) {
		++stat->tbuf_nodes;
		stat->tbuf_memory_total += sizeof(Node);
		if (node->kids < 3)
			++stat->tbuf_nodes_with_few_kids;
		if (node->height == 2) {
			for (i = 0; i < node->kids; ++i)
				gather_chunk_stats(stat, node->x.chunk[i], shared);
		} else {
			for (i = 0; i < node->kids; ++i)
				gather_node_stats(stat, node->x.node[i], shared);
		}
		node->visited = 1;
	}
}

void tbuf_get_stats(struct tbuf_stat *stat, Tbuf *tbuf) {
	stat->tbuf = tbuf;
	stat->tbuf_length = tbuf->length;
	stat->tbuf_height = tbuf->height;

	stat->tbuf_nodes = 0;
	stat->tbuf_chunks = 0;
	stat->tbuf_memory_total = sizeof(Tbuf);
	stat->tbuf_nodes_with_few_kids = 0;

	switch (tbuf->height) {
	case 0:
		break;
	
	case 1:
		tbuf->x.chunk->visited = 0;
		gather_chunk_stats(stat, tbuf->x.chunk, 0);
		break;
	
	default:
		node_zero_visited(tbuf->x.root);
		gather_node_stats(stat, tbuf->x.root, 0);
		break;
	}
}



/*
 * Return length of buffer.
 */
 
size_t tbuf_length(Tbuf *tbuf) {
	return tbuf->length;
}