[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)
{
    int d;
    block_t c, sel;
    struct btnode indir[BT_INDSZ];
    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 * BT_INDBITS)) > 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, BT_INDBSZ, &tree->a)) < 0)
	    return(-1);
	c = sz / sizeof(struct btnode);
	sel = bl >> ((d - 1) * BT_INDBITS);
	if(sel >= c) {
	    errno = ERANGE;
	    return(-1);
	}
	tree = &indir[sel];
	bl &= (1LL << ((d - 1) * BT_INDBITS)) - 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, block_t bloff)
{
    int i, subops, d, f, hasid;
    block_t c, sel, bl, nextsz;
    struct addr na;
    struct btnode indir[BT_INDSZ];
    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 * BT_INDBITS)))) {
	    /* 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 <<= BT_INDBITS);
	    tree->d = d;
	    c = 0;
	    hasid = 1;
	} else {
	    /* Get indirect block */
	    if(!hasid) {
		if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
		    return(-1);
		c = sz / sizeof(struct btnode);
		hasid = 1;
	    }
	}

	sel = bl >> ((d - 1) * BT_INDBITS);
	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) * BT_INDBITS);
	subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
	if(btputmany2(st, &indir[sel], ops + i, subops, bloff + (sel * nextsz)))
	    return(-1);
	i += subops;
	
	if((sel == BT_INDSZ - 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)
{
    return(btputmany2(st, tree, ops, numops, 0));
}

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

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)
{
    int d, f;
    struct btnode indir[BT_INDSZ];
    block_t c, ret;
    ssize_t sz;
    
    d = tree->d & 0x7f;
    f = tree->d & 0x80;
    
    if(f)
	return(1LL << (d * BT_INDBITS));
    
    if(d == 0)
	return(0);
    
    ret = 0;
    while(1) {
	if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
	    return(-1);
	c = sz / sizeof(struct btnode);
	ret += (c - 1) * (1LL << ((d - 1) * BT_INDBITS));
	d = indir[c - 1].d & 0x7f;
	f = indir[c - 1].d & 0x80;
	if(f)
	    return(ret + (1LL << (d * BT_INDBITS)));
	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
	11	ssize_t btget(struct store st, struct btnode tree, block_t bl, void *buf, size_t len)
	12	{
	13	int d;
	14	block_t c, sel;
	15	struct btnode indir[BT_INDSZ];
	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. */
	27	if((bl >> (d * BT_INDBITS)) > 0) {
	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 */
	36	if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
	37	return(-1);
	38	c = sz / sizeof(struct btnode);
	39	sel = bl >> ((d - 1) * BT_INDBITS);
	40	if(sel >= c) {
	41	errno = ERANGE;
	42	return(-1);
	43	}
	44	tree = &indir[sel];
	45	bl &= (1LL << ((d - 1) * BT_INDBITS)) - 1;
	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	*/
	91	static int btputmany2(struct store st, struct btnode tree, struct btop *ops, int numops, block_t bloff)
	92	{
	93	int i, subops, d, f, hasid;
	94	block_t c, sel, bl, nextsz;
	95	struct addr na;
	96	struct btnode indir[BT_INDSZ];
	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
	118	if(f && (bl == (1LL << (d * BT_INDBITS)))) {
	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 */
	138	for(bl = numops - 1; bl > 0; d++, bl <<= BT_INDBITS);
	139	tree->d = d;
	140	c = 0;
	141	hasid = 1;
	142	} else {
	143	/* Get indirect block */
	144	if(!hasid) {
	145	if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
	146	return(-1);
	147	c = sz / sizeof(struct btnode);
	148	hasid = 1;
	149	}
	150	}
	151
	152	sel = bl >> ((d - 1) * BT_INDBITS);
	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	}
	167	nextsz = 1LL << ((d - 1) * BT_INDBITS);
	168	subops = countops(ops + i, numops - i, bloff + (sel * nextsz), nextsz);
	169	if(btputmany2(st, &indir[sel], ops + i, subops, bloff + (sel * nextsz)))
	170	return(-1);
	171	i += subops;
	172
173	if((sel == BT_INDSZ - 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
	193	int btputmany(struct store st, struct btnode tree, struct btop *ops, int numops)
	194	{
	195	return(btputmany2(st, tree, ops, numops, 0));
	196	}
	197
	198	int btput(struct store st, struct btnode tree, block_t bl, void *buf, size_t len)
	199	{
	200	struct btop ops[1];
	201
	202	ops[0].blk = bl;
	203	ops[0].buf = buf;
	204	ops[0].len = len;
	205	return(btputmany(st, tree, ops, 1));
	206	}
	207
	208	void btmkop(struct btop op, block_t bl, void buf, size_t len)
	209	{
	210	memset(op, 0, sizeof(*op));
	211	op->blk = bl;
	212	op->buf = buf;
	213	op->len = len;
	214	}
	215
	216	static int opcmp(const struct btop op1, const struct btop op2)
	217	{
2a9c9b15	218	if(ISDELOP(op1) && ISDELOP(op2))
	219	return((op2)->blk - (op1)->blk);
	220	else if(!ISDELOP(op1) && ISDELOP(op2))
	221	return(-1);
	222	else if(ISDELOP(op1) && !ISDELOP(op2))
	223	return(1);
	224	else
	225	return((op1)->blk - (op2)->blk);
d5cf5351	226	}
	227
	228	void btsortops(struct btop *ops, int numops)
	229	{
	230	qsort(ops, numops, sizeof(ops), (int ()(const void , const void ))opcmp);
	231	}
	232
d5cf5351	233	block_t btcount(struct store st, struct btnode tree)
	234	{
	235	int d, f;
	236	struct btnode indir[BT_INDSZ];
	237	block_t c, ret;
	238	ssize_t sz;
	239
	240	d = tree->d & 0x7f;
	241	f = tree->d & 0x80;
	242
	243	if(f)
	244	return(1LL << (d * BT_INDBITS));
	245
	246	if(d == 0)
	247	return(0);
	248
	249	ret = 0;
	250	while(1) {
	251	if((sz = storeget(st, indir, BT_INDBSZ, &tree->a)) < 0)
	252	return(-1);
	253	c = sz / sizeof(struct btnode);
	254	ret += (c - 1) * (1LL << ((d - 1) * BT_INDBITS));
	255	d = indir[c - 1].d & 0x7f;
	256	f = indir[c - 1].d & 0x80;
	257	if(f)
	258	return(ret + (1LL << (d * BT_INDBITS)));
	259	tree = &indir[c - 1];
	260	}
	261	}