blocktree.c

   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))
   9 #define ISDELOP(op) (((op).buf == NULL) && ((op).fillfn == NULL))
  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
  56     if(ISDELOP(*op)) {
  57         leaf->d = 0;
  58         return(0);
  59     }
  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; ) {
 105         if(ops[i].blk < bloff) {
 106             errno = ERANGE;
 107             return(-1);
 108         }
 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))) {
 174             /* Filled up */
 175             tree->d |= 0x80;
 176             f = 1;
 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             }
 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 {
 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);
 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
 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 }