[sgt/tweak] / buffer.c

#include "tweak.h"

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

#include "btree.h"

#ifdef TEST_BUFFER
#define BLKMIN 4
#else
#define BLKMIN 512
#endif

#define BLKMAX (2*BLKMIN)

struct file {
    FILE *fp;
    int refcount;
};

struct buffer {
    btree *bt;
};

struct bufblk {
    fileoffset_t len;		       /* number of bytes in block, always */
    struct file *file;		       /* non-NULL indicates a file block */
    fileoffset_t filepos;	       /* only meaningful if fp!=NULL */
    unsigned char *data;	       /* only used if fp==NULL */
};

static bt_element_t bufblkcopy(void *state, void *av)
{
    struct bufblk *a = (struct bufblk *)av;
    struct bufblk *ret;

    if (a->file) {
	ret = (struct bufblk *)malloc(sizeof(struct bufblk));
	ret->data = NULL;
	a->file->refcount++;
    } else {
	ret = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX);
	ret->data = (unsigned char *)(ret+1);
	memcpy(ret->data, a->data, BLKMAX);
    }

    ret->file = a->file;
    ret->filepos = a->filepos;
    ret->len = a->len;

    return ret;
}

static void bufblkfree(void *state, void *av)
{
    struct bufblk *a = (struct bufblk *)av;

    if (a->file) {
	a->file->refcount--;

	if (a->file->refcount == 0) {
	    fclose(a->file->fp);
	    free(a->file);
	}
    }

    free(a);
}

void bufblkpropmake(void *state, bt_element_t av, void *destv)
{
    struct bufblk *a = (struct bufblk *)av;
    fileoffset_t *dest = (fileoffset_t *)destv;

    *dest = a->len;
}

/* s1 may be NULL (indicating copy s2 into dest). s2 is never NULL. */
void bufblkpropmerge(void *state, void *s1v, void *s2v, void *destv)
{
    fileoffset_t *s1 = (fileoffset_t *)s1v;
    fileoffset_t *s2 = (fileoffset_t *)s2v;
    fileoffset_t *dest = (fileoffset_t *)destv;
    if (!s1 && !s2) return;	       /* don't need to free anything */
    *dest = *s2 + (s1 ? *s1 : 0);
}

static buffer *buf_new_from_bt(btree *bt)
{
    buffer *buf = (buffer *)malloc(sizeof(buffer));

    buf->bt = bt;

    return buf;
}

static btree *buf_bt_new(void)
{
    return bt_new(NULL, bufblkcopy, bufblkfree, sizeof(fileoffset_t),
		  alignof(fileoffset_t), bufblkpropmake, bufblkpropmerge,
		  NULL, 2);
}

extern void buf_free(buffer *buf)
{
    bt_free(buf->bt);
    free(buf);
}

static int bufblksearch(void *tstate, void *sstate, int ntrees,
			void **props, int *counts,
			bt_element_t *elts, int *is_elt)
{
    fileoffset_t *disttogo = (fileoffset_t *)sstate;
    fileoffset_t distsofar = 0;
    int i;

    for (i = 0; i < ntrees; i++) {
	struct bufblk *blk;
	fileoffset_t sublen = props[i] ? *(fileoffset_t *)props[i] : 0;

	if ((props[i] && *disttogo < distsofar + sublen) ||
	    (*disttogo == distsofar + sublen && i == ntrees-1)) {
	    *disttogo -= distsofar;
	    /*
	     * Descend into this subtree.
	     */
	    *is_elt = FALSE;
	    return i;
	}

	distsofar += sublen;

	if (i < ntrees-1) {
	    blk = (struct bufblk *)elts[i];

	    if (*disttogo < distsofar + blk->len) {
		/*
		 * Select this element.
		 */
		*disttogo -= distsofar;
		*is_elt = TRUE;
		return i;
	    }

	    distsofar += blk->len;
	}
    }

    assert(!"We should never reach here");
    return 0;			       /* placate gcc */
}

static int buf_bt_find_pos(btree *bt, fileoffset_t pos, fileoffset_t *poswithin)
{
    int index;

    bt_propfind(bt, bufblksearch, &pos, &index);

    *poswithin = pos;
    return index;
}

/*
 * Convert a file-data block of size at most BUFMAX into a
 * literal-data block. Returns the replacement block (the old one
 * still needs freeing) or NULL if no conversion performed.
 */
static struct bufblk *buf_convert_to_literal(struct bufblk *blk)
{
    if (blk->file && blk->len <= BLKMAX) {
	struct bufblk *ret =
	    (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX);
	ret->data = (unsigned char *)(ret+1);
	ret->file = NULL;
	ret->filepos = 0;
	ret->len = blk->len;
	fseeko(blk->file->fp, blk->filepos, SEEK_SET);
	fread(ret->data, blk->len, 1, blk->file->fp);

	return ret;
    }

    return NULL;
}

/*
 * Look at blocks `index' and `index+1' of buf. If they're both
 * literal-data blocks and one of them is undersized, merge or
 * redistribute. Returns 0 if it has not changed the number of
 * blocks, or 1 if it has merged two.
 */
static int buf_bt_cleanup(btree *bt, int index)
{
    struct bufblk *a, *b, *cvt;
    fileoffset_t totallen;
    unsigned char tmpdata[BLKMAX*2];

    if (index < 0) return 0;

    a = (struct bufblk *)bt_index(bt, index);
    b = (struct bufblk *)bt_index(bt, index+1);

    if ( a && (cvt = buf_convert_to_literal(a)) != NULL ) {
	bt_replace(bt, cvt, index);
	bufblkfree(NULL, a);
	a = cvt;
    }

    if ( b && (cvt = buf_convert_to_literal(b)) != NULL ) {
	bt_replace(bt, cvt, index+1);
	bufblkfree(NULL, b);
	b = cvt;
    }

    if (!a || !b || a->file || b->file) return 0;

    if (a->len >= BLKMIN && b->len >= BLKMIN) return 0;

    assert(a->len <= BLKMAX && b->len <= BLKMAX);

    /* Use bt_index_w to ensure reference count of 1 on both blocks */
    a = (struct bufblk *)bt_index_w(bt, index);
    b = (struct bufblk *)bt_index_w(bt, index+1);

    /*
     * So, we have one block with size at most BLKMIN, and another
     * with size at most BLKMAX. Combined, their maximum possible
     * size is in excess of BLKMAX, so we can't guaranteeably merge
     * them into one. If they won't merge, we instead redistribute
     * data between them.
     */
    totallen = a->len + b->len;
    memcpy(tmpdata, a->data, a->len);
    memcpy(tmpdata + a->len, b->data, b->len);

    if (totallen >= BLKMAX) {
	/*
	 * Redistribute into two (nearly) equal-sized blocks.
	 */
	a->len = totallen / 2;
	b->len = totallen - a->len;

	memcpy(a->data, tmpdata, a->len);
	memcpy(b->data, tmpdata + a->len, b->len);

	bt_replace(bt, a, index);
	bt_replace(bt, b, index+1);

	return 0;
    } else {
	/*
	 * Just merge into one.
	 */
	a->len = totallen;
	memcpy(a->data, tmpdata, a->len);

	bt_replace(bt, a, index);
	free(bt_delpos(bt, index+1));

	return 1;
    }
}

static int buf_bt_splitpoint(btree *bt, fileoffset_t pos)
{
    fileoffset_t poswithin;
    int index;
    struct bufblk *blk, *newblk;

    index = buf_bt_find_pos(bt, pos, &poswithin);

    if (!poswithin)
	return index;		       /* the nice simple case */

    /*
     * Now split element `index' at position `poswithin'.
     */
    blk = (struct bufblk *)bt_index_w(bt, index);   /* ensure ref count == 1 */
    newblk = (struct bufblk *)bufblkcopy(NULL, blk);

    if (!newblk->file) {
	memcpy(newblk->data, blk->data + poswithin, blk->len - poswithin);
    } else {
	newblk->filepos += poswithin;
    }
    blk->len = poswithin;
    bt_replace(bt, blk, index);
    newblk->len -= poswithin;
    bt_addpos(bt, newblk, index+1);

    buf_bt_cleanup(bt, index+1);
    index -= buf_bt_cleanup(bt, index-1);

    return index + 1;
}

static btree *buf_bt_split(btree *bt, fileoffset_t pos, int before)
{
    int index = buf_bt_splitpoint(bt, pos);
    return bt_splitpos(bt, index, before);
}

static btree *buf_bt_join(btree *a, btree *b)
{
    int index = bt_count(a) - 1;
    btree *ret;

    ret = bt_join(a, b);

    buf_bt_cleanup(ret, index);

    return ret;
}

static void buf_insert_bt(buffer *buf, btree *bt, fileoffset_t pos)
{
    btree *right = buf_bt_split(buf->bt, pos, FALSE);
    buf->bt = buf_bt_join(buf->bt, bt);
    buf->bt = buf_bt_join(buf->bt, right);
}

static int bufblklensearch(void *tstate, void *sstate, int ntrees,
			   void **props, int *counts,
			   bt_element_t *elts, int *is_elt)
{
    fileoffset_t *output = (fileoffset_t *)sstate;
    fileoffset_t size = 0;
    int i;

    for (i = 0; i < ntrees; i++) {
	struct bufblk *blk;

	if (props[i])
	    size += *(fileoffset_t *)props[i];

	if (i < ntrees-1) {
	    blk = (struct bufblk *)elts[i];

	    size += blk->len;
	}
    }

    *output = size;

    /* Actual return value doesn't matter */
    *is_elt = TRUE;
    return 1;
}

static fileoffset_t buf_bt_length(btree *bt)
{
    fileoffset_t length;

    bt_propfind(bt, bufblklensearch, &length, NULL);

    return length;
}

extern fileoffset_t buf_length(buffer *buf)
{
    return buf_bt_length(buf->bt);
}

extern buffer *buf_new_empty(void)
{
    buffer *buf = (buffer *)malloc(sizeof(buffer));

    buf->bt = buf_bt_new();

    return buf;
}

extern buffer *buf_new_from_file(FILE *fp)
{
    buffer *buf = buf_new_empty();
    struct bufblk *blk;
    struct file *file;

    file = (struct file *)malloc(sizeof(struct file));
    file->fp = fp;
    file->refcount = 1;		       /* the reference we're about to make */

    blk = (struct bufblk *)malloc(sizeof(struct bufblk));
    blk->data = NULL;
    blk->file = file;
    blk->filepos = 0;

    fseeko(fp, 0, SEEK_END);
    blk->len = ftello(fp);

    bt_addpos(buf->bt, blk, 0);

    buf_bt_cleanup(buf->bt, 0);

    return buf;
}

extern void buf_fetch_data(buffer *buf, void *vdata, int len, fileoffset_t pos)
{
    int index;
    fileoffset_t poswithin;
    fileoffset_t thislen;
    unsigned char *data = (unsigned char *)vdata;

    index = buf_bt_find_pos(buf->bt, pos, &poswithin);

    while (len > 0) {
	struct bufblk *blk = (struct bufblk *)bt_index(buf->bt, index);

	thislen = blk->len - poswithin;
	if (thislen > len)
	    thislen = len;

	if (blk->file) {
	    fseeko(blk->file->fp, blk->filepos + poswithin, SEEK_SET);
	    fread(data, thislen, 1, blk->file->fp);
	} else {
	    memcpy(data, blk->data + poswithin, thislen);
	}

	data += thislen;
	len -= thislen;

	poswithin = 0;

	index++;
    }
}

extern void buf_insert_data(buffer *buf, void *vdata, int len,
                            fileoffset_t pos)
{
    btree *bt = buf_bt_new();
    int nblocks, blklen1, extra;
    int i, origlen = len;
    unsigned char *data = (unsigned char *)vdata;

    nblocks = len / ((BLKMIN + BLKMAX)/2);
    if (nblocks * BLKMAX < len)
	nblocks++;
    blklen1 = len / nblocks;
    extra = len % nblocks;
    assert(blklen1 >= BLKMIN || nblocks == 1);
    assert(blklen1 <= BLKMAX - (extra!=0));

    for (i = 0; i < nblocks; i++) {
	struct bufblk *blk;
	int blklen = blklen1 + (i < extra);

	blk = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX);
	blk->data = (unsigned char *)(blk+1);
	memcpy(blk->data, data, blklen);
	blk->len = blklen;
	blk->file = NULL;
	blk->filepos = 0;

	data += blklen;
	len -= blklen;

	bt_addpos(bt, blk, i);
	assert(origlen == buf_bt_length(bt) + len);
    }

    assert(len == 0);
    assert(origlen == buf_bt_length(bt));

    buf_insert_bt(buf, bt, pos);
}

extern void buf_delete(buffer *buf, fileoffset_t len, fileoffset_t pos)
{
    btree *left = buf_bt_split(buf->bt, pos, TRUE);
    btree *right = buf_bt_split(buf->bt, len, FALSE);

    bt_free(buf->bt);

    buf->bt = buf_bt_join(left, right);
}

extern void buf_overwrite_data(buffer *buf, void *data, int len,
                               fileoffset_t pos)
{
    buf_delete(buf, len, pos);
    buf_insert_data(buf, data, len, pos);
}

extern buffer *buf_cut(buffer *buf, fileoffset_t len, fileoffset_t pos)
{
    btree *left = buf_bt_split(buf->bt, pos, TRUE);
    btree *right = buf_bt_split(buf->bt, len, FALSE);
    btree *ret = buf->bt;

    buf->bt = buf_bt_join(left, right);

    return buf_new_from_bt(ret);
}

extern buffer *buf_copy(buffer *buf, fileoffset_t len, fileoffset_t pos)
{
    btree *left = buf_bt_split(buf->bt, pos, TRUE);
    btree *right = buf_bt_split(buf->bt, len, FALSE);
    btree *ret = bt_clone(buf->bt);

    buf->bt = buf_bt_join(left, buf->bt);
    buf->bt = buf_bt_join(buf->bt, right);

    return buf_new_from_bt(ret);
}

extern void buf_paste(buffer *buf, buffer *cutbuffer, fileoffset_t pos)
{
    btree *bt = bt_clone(cutbuffer->bt);
    buf_insert_bt(buf, bt, pos);
}

#ifdef TEST_BUFFER
static FILE *debugfp = NULL;
extern void buffer_diagnostic(buffer *buf, char *title)
{
    int i;
    fileoffset_t offset;
    struct bufblk *blk;

    if (!debugfp) {
	debugfp = fdopen(3, "w");
	if (!debugfp)
	    debugfp = fopen("debug.log", "w");
    }

    if (!buf) {
	fprintf(debugfp, "Buffer [%s] is null\n", title);
	return;
    }

    fprintf(debugfp, "Listing of buffer [%s]:\n", title);
    offset = 0;
    for (i = 0; (blk = (struct bufblk *)bt_index(buf->bt, i)) != NULL; i++) {
	fprintf(debugfp, "%016"OFF"x: %p, len =%8"OFF"d,", offset, blk, blk->len);
	if (blk->file) {
	    fprintf(debugfp, " file %p pos %8"OFF"d\n", blk->file, blk->filepos);
	} else {
	    int j;

	    for (j = 0; j < blk->len; j++)
		fprintf(debugfp, " %02x", blk->data[j]);

	    fprintf(debugfp, "\n");
	}
	offset += blk->len;
    }
    fprintf(debugfp, "Listing concluded\n\n");

    fflush(debugfp);
}
#endif
Commit	Line	Data
11825bd4	1	#include "tweak.h"
11825bd4	2
6e182d98	3	#include <stdio.h>
	4	#include <stdlib.h>
	5	#include <string.h>
	6	#include <ctype.h>
	7	#include <assert.h>
	8
6e182d98	9	#include "btree.h"
	10
	11	#ifdef TEST_BUFFER
	12	#define BLKMIN 4
	13	#else
	14	#define BLKMIN 512
	15	#endif
	16
	17	#define BLKMAX (2*BLKMIN)
	18
	19	struct file {
	20	FILE *fp;
	21	int refcount;
	22	};
	23
	24	struct buffer {
	25	btree *bt;
	26	};
	27
	28	struct bufblk {
11825bd4	29	fileoffset_t len; /* number of bytes in block, always */
6e182d98	30	struct file file; / non-NULL indicates a file block */
11825bd4	31	fileoffset_t filepos; /* only meaningful if fp!=NULL */
6e182d98	32	unsigned char data; / only used if fp==NULL */
	33	};
	34
6e182d98	35	static bt_element_t bufblkcopy(void state, void av)
	36	{
	37	struct bufblk a = (struct bufblk )av;
	38	struct bufblk *ret;
	39
	40	if (a->file) {
	41	ret = (struct bufblk *)malloc(sizeof(struct bufblk));
	42	ret->data = NULL;
	43	a->file->refcount++;
	44	} else {
	45	ret = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX);
	46	ret->data = (unsigned char *)(ret+1);
	47	memcpy(ret->data, a->data, BLKMAX);
	48	}
	49
	50	ret->file = a->file;
	51	ret->filepos = a->filepos;
	52	ret->len = a->len;
	53
	54	return ret;
	55	}
	56
	57	static void bufblkfree(void state, void av)
	58	{
	59	struct bufblk a = (struct bufblk )av;
	60
	61	if (a->file) {
	62	a->file->refcount--;
	63
	64	if (a->file->refcount == 0) {
	65	fclose(a->file->fp);
	66	free(a->file);
	67	}
	68	}
	69
	70	free(a);
	71	}
	72
	73	void bufblkpropmake(void state, bt_element_t av, void destv)
	74	{
	75	struct bufblk a = (struct bufblk )av;
11825bd4	76	fileoffset_t dest = (fileoffset_t )destv;
6e182d98	77
	78	*dest = a->len;
	79	}
	80
	81	/* s1 may be NULL (indicating copy s2 into dest). s2 is never NULL. */
	82	void bufblkpropmerge(void state, void s1v, void s2v, void destv)
	83	{
11825bd4	84	fileoffset_t s1 = (fileoffset_t )s1v;
	85	fileoffset_t s2 = (fileoffset_t )s2v;
	86	fileoffset_t dest = (fileoffset_t )destv;
6e182d98	87	if (!s1 && !s2) return; /* don't need to free anything */
	88	dest = s2 + (s1 ? *s1 : 0);
	89	}
	90
	91	static buffer buf_new_from_bt(btree bt)
	92	{
	93	buffer buf = (buffer )malloc(sizeof(buffer));
	94
	95	buf->bt = bt;
	96
	97	return buf;
	98	}
	99
	100	static btree *buf_bt_new(void)
	101	{
11825bd4	102	return bt_new(NULL, bufblkcopy, bufblkfree, sizeof(fileoffset_t),
11825bd4	103	alignof(fileoffset_t), bufblkpropmake, bufblkpropmerge,
6e182d98	104	NULL, 2);
	105	}
	106
	107	extern void buf_free(buffer *buf)
	108	{
	109	bt_free(buf->bt);
	110	free(buf);
	111	}
	112
	113	static int bufblksearch(void tstate, void sstate, int ntrees,
	114	void *props, int counts,
	115	bt_element_t elts, int is_elt)
	116	{
11825bd4	117	fileoffset_t disttogo = (fileoffset_t )sstate;
11825bd4	118	fileoffset_t distsofar = 0;
6e182d98	119	int i;
	120
	121	for (i = 0; i < ntrees; i++) {
	122	struct bufblk *blk;
11825bd4	123	fileoffset_t sublen = props[i] ? (fileoffset_t )props[i] : 0;
6e182d98	124
	125	if ((props[i] && *disttogo < distsofar + sublen) \|\|
	126	(*disttogo == distsofar + sublen && i == ntrees-1)) {
	127	*disttogo -= distsofar;
	128	/*
	129	* Descend into this subtree.
	130	*/
	131	*is_elt = FALSE;
	132	return i;
	133	}
	134
	135	distsofar += sublen;
	136
	137	if (i < ntrees-1) {
	138	blk = (struct bufblk *)elts[i];
	139
	140	if (*disttogo < distsofar + blk->len) {
	141	/*
	142	* Select this element.
	143	*/
	144	*disttogo -= distsofar;
	145	*is_elt = TRUE;
	146	return i;
	147	}
	148
	149	distsofar += blk->len;
	150	}
	151	}
	152
	153	assert(!"We should never reach here");
	154	return 0; /* placate gcc */
	155	}
	156
11825bd4	157	static int buf_bt_find_pos(btree bt, fileoffset_t pos, fileoffset_t poswithin)
6e182d98	158	{
	159	int index;
	160
	161	bt_propfind(bt, bufblksearch, &pos, &index);
	162
	163	*poswithin = pos;
	164	return index;
	165	}
	166
	167	/*
	168	* Convert a file-data block of size at most BUFMAX into a
	169	* literal-data block. Returns the replacement block (the old one
	170	* still needs freeing) or NULL if no conversion performed.
	171	*/
	172	static struct bufblk buf_convert_to_literal(struct bufblk blk)
	173	{
	174	if (blk->file && blk->len <= BLKMAX) {
	175	struct bufblk *ret =
	176	(struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX);
	177	ret->data = (unsigned char *)(ret+1);
	178	ret->file = NULL;
	179	ret->filepos = 0;
	180	ret->len = blk->len;
11825bd4	181	fseeko(blk->file->fp, blk->filepos, SEEK_SET);
6e182d98	182	fread(ret->data, blk->len, 1, blk->file->fp);
	183
	184	return ret;
	185	}
	186
	187	return NULL;
	188	}
	189
	190	/*
	191	* Look at blocks `index' and `index+1' of buf. If they're both
	192	* literal-data blocks and one of them is undersized, merge or
	193	* redistribute. Returns 0 if it has not changed the number of
	194	* blocks, or 1 if it has merged two.
	195	*/
	196	static int buf_bt_cleanup(btree *bt, int index)
	197	{
	198	struct bufblk a, b, *cvt;
11825bd4	199	fileoffset_t totallen;
6e182d98	200	unsigned char tmpdata[BLKMAX*2];
	201
	202	if (index < 0) return 0;
	203
	204	a = (struct bufblk *)bt_index(bt, index);
	205	b = (struct bufblk *)bt_index(bt, index+1);
	206
	207	if ( a && (cvt = buf_convert_to_literal(a)) != NULL ) {
	208	bt_replace(bt, cvt, index);
	209	bufblkfree(NULL, a);
	210	a = cvt;
	211	}
	212
	213	if ( b && (cvt = buf_convert_to_literal(b)) != NULL ) {
	214	bt_replace(bt, cvt, index+1);
	215	bufblkfree(NULL, b);
	216	b = cvt;
	217	}
	218
	219	if (!a \|\| !b \|\| a->file \|\| b->file) return 0;
	220
	221	if (a->len >= BLKMIN && b->len >= BLKMIN) return 0;
	222
	223	assert(a->len <= BLKMAX && b->len <= BLKMAX);
	224
	225	/* Use bt_index_w to ensure reference count of 1 on both blocks */
	226	a = (struct bufblk *)bt_index_w(bt, index);
	227	b = (struct bufblk *)bt_index_w(bt, index+1);
	228
	229	/*
	230	* So, we have one block with size at most BLKMIN, and another
	231	* with size at most BLKMAX. Combined, their maximum possible
	232	* size is in excess of BLKMAX, so we can't guaranteeably merge
	233	* them into one. If they won't merge, we instead redistribute
	234	* data between them.
	235	*/
	236	totallen = a->len + b->len;
	237	memcpy(tmpdata, a->data, a->len);
	238	memcpy(tmpdata + a->len, b->data, b->len);
	239
	240	if (totallen >= BLKMAX) {
	241	/*
	242	* Redistribute into two (nearly) equal-sized blocks.
	243	*/
	244	a->len = totallen / 2;
	245	b->len = totallen - a->len;
	246
	247	memcpy(a->data, tmpdata, a->len);
	248	memcpy(b->data, tmpdata + a->len, b->len);
	249
	250	bt_replace(bt, a, index);
	251	bt_replace(bt, b, index+1);
	252
	253	return 0;
	254	} else {
	255	/*
	256	* Just merge into one.
	257	*/
	258	a->len = totallen;
	259	memcpy(a->data, tmpdata, a->len);
	260
	261	bt_replace(bt, a, index);
	262	free(bt_delpos(bt, index+1));
	263
264	return 1;
265	}
266	}
267
11825bd4	268	static int buf_bt_splitpoint(btree *bt, fileoffset_t pos)
6e182d98	269	{
11825bd4	270	fileoffset_t poswithin;
11825bd4	271	int index;
6e182d98	272	struct bufblk blk, newblk;
	273
	274	index = buf_bt_find_pos(bt, pos, &poswithin);
	275
	276	if (!poswithin)
	277	return index; /* the nice simple case */
	278
	279	/*
	280	* Now split element `index' at position `poswithin'.
	281	*/
	282	blk = (struct bufblk )bt_index_w(bt, index); / ensure ref count == 1 */
	283	newblk = (struct bufblk *)bufblkcopy(NULL, blk);
	284
	285	if (!newblk->file) {
	286	memcpy(newblk->data, blk->data + poswithin, blk->len - poswithin);
	287	} else {
	288	newblk->filepos += poswithin;
	289	}
	290	blk->len = poswithin;
	291	bt_replace(bt, blk, index);
	292	newblk->len -= poswithin;
	293	bt_addpos(bt, newblk, index+1);
	294
	295	buf_bt_cleanup(bt, index+1);
	296	index -= buf_bt_cleanup(bt, index-1);
	297
	298	return index + 1;
	299	}
	300
11825bd4	301	static btree buf_bt_split(btree bt, fileoffset_t pos, int before)
6e182d98	302	{
	303	int index = buf_bt_splitpoint(bt, pos);
	304	return bt_splitpos(bt, index, before);
	305	}
	306
	307	static btree buf_bt_join(btree a, btree *b)
	308	{
	309	int index = bt_count(a) - 1;
	310	btree *ret;
	311
	312	ret = bt_join(a, b);
	313
	314	buf_bt_cleanup(ret, index);
	315
	316	return ret;
	317	}
	318
11825bd4	319	static void buf_insert_bt(buffer buf, btree bt, fileoffset_t pos)
6e182d98	320	{
	321	btree *right = buf_bt_split(buf->bt, pos, FALSE);
	322	buf->bt = buf_bt_join(buf->bt, bt);
	323	buf->bt = buf_bt_join(buf->bt, right);
	324	}
	325
	326	static int bufblklensearch(void tstate, void sstate, int ntrees,
	327	void *props, int counts,
	328	bt_element_t elts, int is_elt)
	329	{
11825bd4	330	fileoffset_t output = (fileoffset_t )sstate;
	331	fileoffset_t size = 0;
	332	int i;
6e182d98	333
	334	for (i = 0; i < ntrees; i++) {
	335	struct bufblk *blk;
	336
	337	if (props[i])
11825bd4	338	size += (fileoffset_t )props[i];
6e182d98	339
	340	if (i < ntrees-1) {
	341	blk = (struct bufblk *)elts[i];
	342
	343	size += blk->len;
	344	}
	345	}
	346
	347	*output = size;
	348
	349	/* Actual return value doesn't matter */
	350	*is_elt = TRUE;
	351	return 1;
	352	}
	353
11825bd4	354	static fileoffset_t buf_bt_length(btree *bt)
6e182d98	355	{
11825bd4	356	fileoffset_t length;
6e182d98	357
	358	bt_propfind(bt, bufblklensearch, &length, NULL);
	359
	360	return length;
	361	}
	362
11825bd4	363	extern fileoffset_t buf_length(buffer *buf)
6e182d98	364	{
	365	return buf_bt_length(buf->bt);
	366	}
	367
	368	extern buffer *buf_new_empty(void)
	369	{
	370	buffer buf = (buffer )malloc(sizeof(buffer));
	371
	372	buf->bt = buf_bt_new();
	373
	374	return buf;
	375	}
	376
	377	extern buffer buf_new_from_file(FILE fp)
	378	{
	379	buffer *buf = buf_new_empty();
	380	struct bufblk *blk;
	381	struct file *file;
	382
	383	file = (struct file *)malloc(sizeof(struct file));
	384	file->fp = fp;
	385	file->refcount = 1; /* the reference we're about to make */
	386
	387	blk = (struct bufblk *)malloc(sizeof(struct bufblk));
	388	blk->data = NULL;
	389	blk->file = file;
	390	blk->filepos = 0;
	391
11825bd4	392	fseeko(fp, 0, SEEK_END);
11825bd4	393	blk->len = ftello(fp);
6e182d98	394
	395	bt_addpos(buf->bt, blk, 0);
	396
	397	buf_bt_cleanup(buf->bt, 0);
	398
	399	return buf;
	400	}
	401
11825bd4	402	extern void buf_fetch_data(buffer buf, void vdata, int len, fileoffset_t pos)
6e182d98	403	{
11825bd4	404	int index;
	405	fileoffset_t poswithin;
	406	fileoffset_t thislen;
6e182d98	407	unsigned char data = (unsigned char )vdata;
	408
	409	index = buf_bt_find_pos(buf->bt, pos, &poswithin);
	410
	411	while (len > 0) {
	412	struct bufblk blk = (struct bufblk )bt_index(buf->bt, index);
	413
	414	thislen = blk->len - poswithin;
	415	if (thislen > len)
	416	thislen = len;
	417
	418	if (blk->file) {
11825bd4	419	fseeko(blk->file->fp, blk->filepos + poswithin, SEEK_SET);
6e182d98	420	fread(data, thislen, 1, blk->file->fp);
	421	} else {
	422	memcpy(data, blk->data + poswithin, thislen);
	423	}
	424
	425	data += thislen;
	426	len -= thislen;
	427
	428	poswithin = 0;
	429
	430	index++;
	431	}
	432	}
	433
11825bd4	434	extern void buf_insert_data(buffer buf, void vdata, int len,
11825bd4	435	fileoffset_t pos)
6e182d98	436	{
	437	btree *bt = buf_bt_new();
	438	int nblocks, blklen1, extra;
	439	int i, origlen = len;
	440	unsigned char data = (unsigned char )vdata;
	441
	442	nblocks = len / ((BLKMIN + BLKMAX)/2);
	443	if (nblocks * BLKMAX < len)
	444	nblocks++;
	445	blklen1 = len / nblocks;
	446	extra = len % nblocks;
	447	assert(blklen1 >= BLKMIN \|\| nblocks == 1);
	448	assert(blklen1 <= BLKMAX - (extra!=0));
	449
	450	for (i = 0; i < nblocks; i++) {
	451	struct bufblk *blk;
	452	int blklen = blklen1 + (i < extra);
	453
	454	blk = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX);
	455	blk->data = (unsigned char *)(blk+1);
	456	memcpy(blk->data, data, blklen);
	457	blk->len = blklen;
	458	blk->file = NULL;
	459	blk->filepos = 0;
	460
	461	data += blklen;
	462	len -= blklen;
	463
	464	bt_addpos(bt, blk, i);
	465	assert(origlen == buf_bt_length(bt) + len);
	466	}
	467
	468	assert(len == 0);
	469	assert(origlen == buf_bt_length(bt));
	470
	471	buf_insert_bt(buf, bt, pos);
	472	}
	473
11825bd4	474	extern void buf_delete(buffer *buf, fileoffset_t len, fileoffset_t pos)
6e182d98	475	{
	476	btree *left = buf_bt_split(buf->bt, pos, TRUE);
	477	btree *right = buf_bt_split(buf->bt, len, FALSE);
	478
	479	bt_free(buf->bt);
	480
	481	buf->bt = buf_bt_join(left, right);
	482	}
	483
11825bd4	484	extern void buf_overwrite_data(buffer buf, void data, int len,
11825bd4	485	fileoffset_t pos)
6e182d98	486	{
	487	buf_delete(buf, len, pos);
	488	buf_insert_data(buf, data, len, pos);
	489	}
	490
11825bd4	491	extern buffer buf_cut(buffer buf, fileoffset_t len, fileoffset_t pos)
6e182d98	492	{
	493	btree *left = buf_bt_split(buf->bt, pos, TRUE);
	494	btree *right = buf_bt_split(buf->bt, len, FALSE);
	495	btree *ret = buf->bt;
	496
	497	buf->bt = buf_bt_join(left, right);
	498
	499	return buf_new_from_bt(ret);
	500	}
	501
11825bd4	502	extern buffer buf_copy(buffer buf, fileoffset_t len, fileoffset_t pos)
6e182d98	503	{
	504	btree *left = buf_bt_split(buf->bt, pos, TRUE);
	505	btree *right = buf_bt_split(buf->bt, len, FALSE);
	506	btree *ret = bt_clone(buf->bt);
	507
	508	buf->bt = buf_bt_join(left, buf->bt);
	509	buf->bt = buf_bt_join(buf->bt, right);
	510
	511	return buf_new_from_bt(ret);
	512	}
	513
11825bd4	514	extern void buf_paste(buffer buf, buffer cutbuffer, fileoffset_t pos)
6e182d98	515	{
	516	btree *bt = bt_clone(cutbuffer->bt);
	517	buf_insert_bt(buf, bt, pos);
	518	}
	519
	520	#ifdef TEST_BUFFER
	521	static FILE *debugfp = NULL;
	522	extern void buffer_diagnostic(buffer buf, char title)
	523	{
11825bd4	524	int i;
11825bd4	525	fileoffset_t offset;
6e182d98	526	struct bufblk *blk;
	527
	528	if (!debugfp) {
	529	debugfp = fdopen(3, "w");
	530	if (!debugfp)
	531	debugfp = fopen("debug.log", "w");
	532	}
	533
	534	if (!buf) {
	535	fprintf(debugfp, "Buffer [%s] is null\n", title);
	536	return;
	537	}
	538
	539	fprintf(debugfp, "Listing of buffer [%s]:\n", title);
	540	offset = 0;
	541	for (i = 0; (blk = (struct bufblk *)bt_index(buf->bt, i)) != NULL; i++) {
11825bd4	542	fprintf(debugfp, "%016"OFF"x: %p, len =%8"OFF"d,", offset, blk, blk->len);
6e182d98	543	if (blk->file) {
11825bd4	544	fprintf(debugfp, " file %p pos %8"OFF"d\n", blk->file, blk->filepos);
6e182d98	545	} else {
	546	int j;
	547
	548	for (j = 0; j < blk->len; j++)
	549	fprintf(debugfp, " %02x", blk->data[j]);
	550
	551	fprintf(debugfp, "\n");
	552	}
	553	offset += blk->len;
	554	}
	555	fprintf(debugfp, "Listing concluded\n\n");
	556
	557	fflush(debugfp);
	558	}
	559	#endif