[vcfs.git] / blocktree.c

#include <stdlib.h>
#include <errno.h>
#include <string.h>

#include "store.h"
#include "blocktree.h"

#define min(a, b) (((b) < (a))?(b):(a))
#define ISDELOP(op) (((op).buf == NULL) && ((op).fillfn == NULL))

ssize_t btget(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len, size_t blsize)
{
    int d;
    block_t c, sel;
    struct btnode indir[1 << blsize];
    ssize_t sz;
    
    if(tree->d == 0) {
	errno = ERANGE;
	return(-1);
    }
    while(1) {
	d = tree->d & 0x7f;
	/* This check should really only be necessary on the first
	 * iteration, but I felt it was easier to put it in the
	 * loop. */
	if((bl >> (d * blsize)) > 0) {
	    errno = ERANGE;
	    return(-1);
	}
	
	if(d == 0)
	    return(storeget(st, buf, len, &tree->a));
	
	/* Luckily, this is tail recursive */
	if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
	    return(-1);
	c = sz / sizeof(struct btnode);
	sel = bl >> ((d - 1) * blsize);
	if(sel >= c) {
	    errno = ERANGE;
	    return(-1);
	}
	tree = &indir[sel];
	bl &= (1LL << ((d - 1) * blsize)) - 1;
    }
    return(0);
}

static int btputleaf(struct store *st, struct btnode *leaf, struct btop *op, block_t bloff)
{
    void *buf;
    struct addr na;
    int ret;
    
    if(ISDELOP(*op)) {
	leaf->d = 0;
	return(0);
    }
    buf = NULL;
    if(op->buf == NULL) {
	buf = op->buf = malloc(op->len);
	if(op->fillfn(buf, op->len, op->pdata))
	    return(-1);
    }
    ret = storeput(st, op->buf, op->len, &na);
    if(buf != NULL)
	free(buf);
    if(ret)
	return(-1);
    leaf->d = 0x80;
    leaf->a = na;
    return(0);
}

static int countops(struct btop *ops, int numops, block_t bloff, block_t maxbl)
{
    int i;
    
    for(i = 0; i < numops; i++) {
	if(ops[i].blk - bloff >= maxbl)
	    break;
    }
    return(i);
}

/*
 * blputmany() in many ways makes the code uglier, but it saves a
 * *lot* of space, since it doesn't need to store intermediary blocks.
 */
static int btputmany2(struct store *st, struct btnode *tree, struct btop *ops, int numops, size_t blsize, block_t bloff)
{
    int i, subops, d, f, hasid;
    block_t c, sel, bl, nextsz;
    struct addr na;
    struct btnode indir[1 << blsize];
    ssize_t sz;
    
    d = tree->d & 0x7f;
    f = tree->d & 0x80;

    hasid = 0;
    
    for(i = 0; i < numops; ) {
	if(ops[i].blk < bloff) {
	    errno = ERANGE;
	    return(-1);
	}
	bl = ops[i].blk - bloff;
    
	if((d == 0) && (bl == 0)) {
	    if(btputleaf(st, tree, ops, bloff))
		return(-1);
	    i++;
	    continue;
	}
    
	if(f && (bl == (1LL << (d * blsize)))) {
	    /* New level of indirection */
	    if(hasid) {
		if(storeput(st, indir, c * sizeof(struct btnode), &na))
		    return(-1);
		tree->a = na;
	    }
	    indir[0] = *tree;
	    tree->d = ++d;
	    f = 0;
	    c = 1;
	    hasid = 1;
	} else if(d == 0) {
	    /* New tree */
	    if(bl != 0) {
		errno = ERANGE;
		return(-1);
	    }
	    /* Assume that numops == largest block number + 1 -- gaps
	     * will be detected as errors later */
	    for(bl = numops - 1; bl > 0; d++, bl <<= blsize);
	    tree->d = d;
	    c = 0;
	    hasid = 1;
	} else {
	    /* Get indirect block */
	    if(!hasid) {
		if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
		    return(-1);
		c = sz / sizeof(struct btnode);
		hasid = 1;
	    }
	}

	sel = bl >> ((d - 1) * blsize);
	if(sel > c) {
	    errno = ERANGE;
	    return(-1);
	}
    
	if(sel == c) {
	    /* Append new */
	    if((c > 0) && (!(indir[c - 1].d & 0x80) || ((indir[c - 1].d & 0x7f) < (d - 1)))) {
		errno = ERANGE;
		return(-1);
	    }
	    indir[c].d = 0;
	    c++;
	}
	nextsz = 1LL << ((d - 1) * blsize);
	subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
	if(btputmany2(st, &indir[sel], ops + i, subops, blsize, bloff + (sel * nextsz)))
	    return(-1);
	i += subops;
	
	if((sel == (1 << blsize) - 1) && (indir[sel].d == ((d - 1) | 0x80))) {
	    /* Filled up */
	    tree->d |= 0x80;
	    f = 1;
	} else if(indir[sel].d == 0) {
	    /* Erased */
	    if(--c == 1) {
		tree->d = indir[0].d;
		tree->a = indir[0].a;
	    }
	}
    }
    if(hasid) {
	if(storeput(st, indir, c * sizeof(struct btnode), &na))
	    return(-1);
	tree->a = na;
    }
    return(0);
}

int btputmany(struct store *st, struct btnode *tree, struct btop *ops, int numops, size_t blsize)
{
    return(btputmany2(st, tree, ops, numops, blsize, 0));
}

int btput(struct store *st, struct btnode *tree, block_t bl, void *buf, size_t len, size_t blsize)
{
    struct btop ops;
    
    memset(&ops, 0, sizeof(ops));
    ops.blk = bl;
    ops.buf = buf;
    ops.len = len;
    return(btputmany(st, tree, &ops, 1, blsize));
}

void btmkop(struct btop *op, block_t bl, void *buf, size_t len)
{
    memset(op, 0, sizeof(*op));
    op->blk = bl;
    op->buf = buf;
    op->len = len;
}

static int opcmp(const struct btop **op1, const struct btop **op2)
{
    if(ISDELOP(**op1) && ISDELOP(**op2))
	return((*op2)->blk - (*op1)->blk);
    else if(!ISDELOP(**op1) && ISDELOP(**op2))
	return(-1);
    else if(ISDELOP(**op1) && !ISDELOP(**op2))
	return(1);
    else
	return((*op1)->blk - (*op2)->blk);
}

void btsortops(struct btop *ops, int numops)
{
    qsort(ops, numops, sizeof(*ops), (int (*)(const void *, const void *))opcmp);
}

block_t btcount(struct store *st, struct btnode *tree, size_t blsize)
{
    int d, f;
    struct btnode indir[1 << blsize];
    block_t c, ret;
    ssize_t sz;
    
    d = tree->d & 0x7f;
    f = tree->d & 0x80;
    
    if(f)
	return(1LL << (d * blsize));
    
    if(d == 0)
	return(0);
    
    ret = 0;
    while(1) {
	if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
	    return(-1);
	c = sz / sizeof(struct btnode);
	ret += (c - 1) * (1LL << ((d - 1) * blsize));
	d = indir[c - 1].d & 0x7f;
	f = indir[c - 1].d & 0x80;
	if(f)
	    return(ret + (1LL << (d * blsize)));
	tree = &indir[c - 1];
    }
}
Commit	Line	Data
d5cf5351	1	#include <stdlib.h>
	2	#include <errno.h>
	3	#include <string.h>
	4
	5	#include "store.h"
	6	#include "blocktree.h"
	7
	8	#define min(a, b) (((b) < (a))?(b):(a))
2a9c9b15	9	#define ISDELOP(op) (((op).buf == NULL) && ((op).fillfn == NULL))
d5cf5351	10
34b0b353	11	ssize_t btget(struct store st, struct btnode tree, block_t bl, void *buf, size_t len, size_t blsize)
d5cf5351	12	{
	13	int d;
	14	block_t c, sel;
34b0b353	15	struct btnode indir[1 << blsize];
d5cf5351	16	ssize_t sz;
	17
	18	if(tree->d == 0) {
	19	errno = ERANGE;
	20	return(-1);
	21	}
	22	while(1) {
	23	d = tree->d & 0x7f;
	24	/* This check should really only be necessary on the first
	25	* iteration, but I felt it was easier to put it in the
	26	* loop. */
34b0b353	27	if((bl >> (d * blsize)) > 0) {
d5cf5351	28	errno = ERANGE;
	29	return(-1);
	30	}
	31
	32	if(d == 0)
	33	return(storeget(st, buf, len, &tree->a));
	34
	35	/* Luckily, this is tail recursive */
34b0b353	36	if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
d5cf5351	37	return(-1);
d5cf5351	38	c = sz / sizeof(struct btnode);
34b0b353	39	sel = bl >> ((d - 1) * blsize);
d5cf5351	40	if(sel >= c) {
	41	errno = ERANGE;
	42	return(-1);
	43	}
	44	tree = &indir[sel];
34b0b353	45	bl &= (1LL << ((d - 1) * blsize)) - 1;
d5cf5351	46	}
	47	return(0);
	48	}
	49
	50	static int btputleaf(struct store st, struct btnode leaf, struct btop *op, block_t bloff)
	51	{
	52	void *buf;
	53	struct addr na;
	54	int ret;
	55
2a9c9b15	56	if(ISDELOP(*op)) {
	57	leaf->d = 0;
	58	return(0);
	59	}
d5cf5351	60	buf = NULL;
	61	if(op->buf == NULL) {
	62	buf = op->buf = malloc(op->len);
	63	if(op->fillfn(buf, op->len, op->pdata))
	64	return(-1);
	65	}
	66	ret = storeput(st, op->buf, op->len, &na);
	67	if(buf != NULL)
	68	free(buf);
	69	if(ret)
	70	return(-1);
	71	leaf->d = 0x80;
	72	leaf->a = na;
	73	return(0);
	74	}
	75
	76	static int countops(struct btop *ops, int numops, block_t bloff, block_t maxbl)
	77	{
	78	int i;
	79
	80	for(i = 0; i < numops; i++) {
	81	if(ops[i].blk - bloff >= maxbl)
	82	break;
	83	}
	84	return(i);
	85	}
	86
	87	/*
	88	* blputmany() in many ways makes the code uglier, but it saves a
	89	* lot of space, since it doesn't need to store intermediary blocks.
	90	*/
34b0b353	91	static int btputmany2(struct store st, struct btnode tree, struct btop *ops, int numops, size_t blsize, block_t bloff)
d5cf5351	92	{
	93	int i, subops, d, f, hasid;
	94	block_t c, sel, bl, nextsz;
	95	struct addr na;
34b0b353	96	struct btnode indir[1 << blsize];
d5cf5351	97	ssize_t sz;
	98
	99	d = tree->d & 0x7f;
	100	f = tree->d & 0x80;
	101
	102	hasid = 0;
	103
	104	for(i = 0; i < numops; ) {
2a9c9b15	105	if(ops[i].blk < bloff) {
	106	errno = ERANGE;
	107	return(-1);
	108	}
d5cf5351	109	bl = ops[i].blk - bloff;
	110
	111	if((d == 0) && (bl == 0)) {
	112	if(btputleaf(st, tree, ops, bloff))
	113	return(-1);
	114	i++;
	115	continue;
	116	}
	117
34b0b353	118	if(f && (bl == (1LL << (d * blsize)))) {
d5cf5351	119	/* New level of indirection */
	120	if(hasid) {
	121	if(storeput(st, indir, c * sizeof(struct btnode), &na))
	122	return(-1);
	123	tree->a = na;
	124	}
	125	indir[0] = *tree;
	126	tree->d = ++d;
	127	f = 0;
	128	c = 1;
	129	hasid = 1;
	130	} else if(d == 0) {
	131	/* New tree */
	132	if(bl != 0) {
	133	errno = ERANGE;
	134	return(-1);
	135	}
	136	/* Assume that numops == largest block number + 1 -- gaps
	137	* will be detected as errors later */
34b0b353	138	for(bl = numops - 1; bl > 0; d++, bl <<= blsize);
d5cf5351	139	tree->d = d;
	140	c = 0;
	141	hasid = 1;
	142	} else {
	143	/* Get indirect block */
	144	if(!hasid) {
34b0b353	145	if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
d5cf5351	146	return(-1);
	147	c = sz / sizeof(struct btnode);
	148	hasid = 1;
	149	}
	150	}
	151
34b0b353	152	sel = bl >> ((d - 1) * blsize);
d5cf5351	153	if(sel > c) {
	154	errno = ERANGE;
	155	return(-1);
	156	}
	157
	158	if(sel == c) {
	159	/* Append new */
	160	if((c > 0) && (!(indir[c - 1].d & 0x80) \|\| ((indir[c - 1].d & 0x7f) < (d - 1)))) {
	161	errno = ERANGE;
	162	return(-1);
	163	}
	164	indir[c].d = 0;
	165	c++;
	166	}
34b0b353	167	nextsz = 1LL << ((d - 1) * blsize);
d5cf5351	168	subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
34b0b353	169	if(btputmany2(st, &indir[sel], ops + i, subops, blsize, bloff + (sel * nextsz)))
d5cf5351	170	return(-1);
	171	i += subops;
	172
34b0b353	173	if((sel == (1 << blsize) - 1) && (indir[sel].d == ((d - 1) \| 0x80))) {
2a9c9b15	174	/* Filled up */
d5cf5351	175	tree->d \|= 0x80;
d5cf5351	176	f = 1;
2a9c9b15	177	} else if(indir[sel].d == 0) {
	178	/* Erased */
	179	if(--c == 1) {
	180	tree->d = indir[0].d;
	181	tree->a = indir[0].a;
	182	}
d5cf5351	183	}
	184	}
	185	if(hasid) {
	186	if(storeput(st, indir, c * sizeof(struct btnode), &na))
	187	return(-1);
	188	tree->a = na;
	189	}
	190	return(0);
	191	}
	192
34b0b353	193	int btputmany(struct store st, struct btnode tree, struct btop *ops, int numops, size_t blsize)
d5cf5351	194	{
34b0b353	195	return(btputmany2(st, tree, ops, numops, blsize, 0));
d5cf5351	196	}
d5cf5351	197
34b0b353	198	int btput(struct store st, struct btnode tree, block_t bl, void *buf, size_t len, size_t blsize)
d5cf5351	199	{
34b0b353	200	struct btop ops;
d5cf5351	201
34b0b353	202	memset(&ops, 0, sizeof(ops));
	203	ops.blk = bl;
	204	ops.buf = buf;
	205	ops.len = len;
	206	return(btputmany(st, tree, &ops, 1, blsize));
d5cf5351	207	}
	208
	209	void btmkop(struct btop op, block_t bl, void buf, size_t len)
	210	{
	211	memset(op, 0, sizeof(*op));
	212	op->blk = bl;
	213	op->buf = buf;
	214	op->len = len;
	215	}
	216
	217	static int opcmp(const struct btop op1, const struct btop op2)
	218	{
2a9c9b15	219	if(ISDELOP(op1) && ISDELOP(op2))
	220	return((op2)->blk - (op1)->blk);
	221	else if(!ISDELOP(op1) && ISDELOP(op2))
	222	return(-1);
	223	else if(ISDELOP(op1) && !ISDELOP(op2))
	224	return(1);
	225	else
	226	return((op1)->blk - (op2)->blk);
d5cf5351	227	}
	228
	229	void btsortops(struct btop *ops, int numops)
	230	{
	231	qsort(ops, numops, sizeof(ops), (int ()(const void , const void ))opcmp);
	232	}
	233
34b0b353	234	block_t btcount(struct store st, struct btnode tree, size_t blsize)
d5cf5351	235	{
d5cf5351	236	int d, f;
34b0b353	237	struct btnode indir[1 << blsize];
d5cf5351	238	block_t c, ret;
	239	ssize_t sz;
	240
	241	d = tree->d & 0x7f;
	242	f = tree->d & 0x80;
	243
	244	if(f)
34b0b353	245	return(1LL << (d * blsize));
d5cf5351	246
	247	if(d == 0)
	248	return(0);
	249
	250	ret = 0;
	251	while(1) {
34b0b353	252	if((sz = storeget(st, indir, sizeof(indir), &tree->a)) < 0)
d5cf5351	253	return(-1);
d5cf5351	254	c = sz / sizeof(struct btnode);
34b0b353	255	ret += (c - 1) * (1LL << ((d - 1) * blsize));
d5cf5351	256	d = indir[c - 1].d & 0x7f;
	257	f = indir[c - 1].d & 0x80;
	258	if(f)
34b0b353	259	return(ret + (1LL << (d * blsize)));
d5cf5351	260	tree = &indir[c - 1];
	261	}
	262	}