--- /dev/null
+/*
+ * fs/lafs/dir-avl.c
+ * Copyright (C) 2005-2009
+ * Neil Brown <neilb@suse.de>
+ * Released under the GPL, version 2
+ *
+ * A directory block is stored as an AVL tree.
+ * Entries are added to the end, and merged into
+ * the AVL tree.
+ * Deleted entries are left in place, but marked
+ * as deleted (pointer is 0)
+ * When a block becomes full, we re-pack it,
+ * or split it.
+ *
+ */
+#include <memory.h>
+#include <lafs/lafs.h>
+#include "internal.h"
+
+/* TEA_transform borrowed from ext3 */
+#define DELTA 0x9E3779B9
+
+static void TEA_transform(u32 buf[2], u32 const in[4])
+{
+ u32 sum = 0;
+ u32 b0 = buf[0], b1 = buf[1];
+ u32 a = in[0], b = in[1], c = in[2], d = in[3];
+ int n = 16;
+
+ do {
+ sum += DELTA;
+ b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
+ b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
+ } while (--n);
+
+ buf[0] += b0;
+ buf[1] += b1;
+}
+
+static void str2msg(u32 *msg, int len, const char *name)
+{
+ int i;
+ u32 part = 0;
+ int pad = len;
+
+ if (len > 16)
+ len = 16;
+ for (i = 0; i < len ; i++) {
+ part = (part << 8) + name[i];
+ if ((i%4) == 3)
+ *msg++ = part;
+ }
+ for ( ; i < 16 ; i++) {
+ part = (part<<8) + pad;
+ if ((i%4) == 3)
+ *msg++ = part;
+ }
+}
+
+int lafs_hash_name(u32 seed, int len, const char *name)
+{
+ u32 buf[2];
+ u32 msg[4];
+ buf[0] = seed;
+ buf[1] = ~seed;
+
+ switch (seed & 0x7) {
+ default:
+ return 0;
+ case 0:
+ return 1;
+ case 1:
+ while (len > 0) {
+ str2msg(msg, len, name);
+ TEA_transform(buf, msg);
+ len -= 16;
+ name += 16;
+ }
+ return buf[0] & 0x7fffffff;
+ }
+}
+
+static u32 hash_piece(u32 seed, struct dirpiece *dp, u32 *offsetp)
+{
+ u32 hash = lafs_hash_name(seed, dp->length, dp->name);
+ u32 offset = 0;
+ switch (dp->chain_info) {
+ case 0:
+ break;
+ case 1:
+ offset = 1;
+ break;
+ case 2:
+ offset = (unsigned char) dp->name[dp->length];
+ break;
+ case 3:
+ memcpy(&offset, dp->name + dp->length, 4);
+ offset = le32_to_cpu(offset);
+ break;
+ }
+ if (offsetp)
+ *offsetp = offset;
+ return hash + offset;
+}
+
+/* dpaddr assumes that 'psz' (piece size) is valid when called */
+#define dpaddr(_block, _piece) ((struct dirpiece *)((_block) + ((_piece)<<psz)))
+#define dlpaddr(_block, _piece) ((struct dirleafpiece *)((_block) \
+ + ((_piece)<<psz)))
+
+static int dir_set_name(struct dirpiece *dp, const char *name, int len,
+ int chain_offset)
+{
+ memcpy(dp->name, name, len);
+
+ if (chain_offset <= 1)
+ dp->chain_info = chain_offset;
+ else if (chain_offset < 256) {
+ dp->chain_info = 2;
+ dp->name[len++] = chain_offset;
+ } else {
+ u32 co = cpu_to_le32(chain_offset);
+ memcpy(dp->name+len, &co, 4);
+ len += 4;
+ dp->chain_info = 3;
+ }
+ return len;
+}
+
+void lafs_dir_init_block(char *block, int psz, const char *name, int len,
+ u32 target, int type, int chain_offset)
+{
+ /* create a new directory block containing just the given name.
+ */
+
+ struct dirpiece *dp;
+ struct dirheader *dh;
+ int pnum;
+ if (len == 0)
+ len = strlen(name);
+ BUG_ON(len > 255);
+
+ dh = (struct dirheader *) block;
+
+ pnum = (sizeof(struct dirheader) + (1<<psz)-1) >> psz;
+
+ dh->root = pnum;
+ dh->pad = 0;
+ dp = dpaddr(block, pnum);
+ dp->target = cpu_to_le32(target);
+ dp->next[0] = 0;
+ dp->next[1] = 0;
+ dp->longer = Neither;
+ dp->length = len;
+ dp->type = type;
+
+ memcpy(dp->name, name, len);
+
+ if (chain_offset <= 1)
+ dp->chain_info = chain_offset;
+ else if (chain_offset < 256) {
+ dp->chain_info = 2;
+ dp->name[len++] = chain_offset;
+ } else {
+ u32 co = cpu_to_le32(chain_offset);
+ memcpy(dp->name+len, &co, 4);
+ len += 4;
+ dp->chain_info = 3;
+ }
+
+ /* NOTE: we want the last piece, not the next free piece, so
+ * we don't add (1<<psz) into this sum
+ */
+ dh->lastpiece = pnum + ((offsetof(struct dirpiece, name)+len-1) >> psz);
+ dh->freepieces = 255 - dh->lastpiece;
+}
+
+static inline int dir_rotate_2(char *block, int psz, u8 *treep, int dir)
+{
+ unsigned int B, C, D, E;
+ struct dirpiece *b, *d;
+
+ B = *treep; b = dpaddr(block, B);
+ D = b->next[dir]; d = dpaddr(block, D);
+ C = d->next[1-dir];
+ E = d->next[dir];
+
+ *treep = D;
+ d->next[1-dir] = B;
+ b->next[dir] = C;
+ b->longer = Neither;
+ d->longer = Neither;
+ return E;
+}
+
+static inline int dir_rotate_3(char *block, int psz, u8 *treep,
+ int dir, int third)
+{
+ unsigned int B, F, D, C, E;
+ struct dirpiece *b, *f, *d;
+
+ B = *treep; b = dpaddr(block, B);
+ F = b->next[dir]; f = dpaddr(block, F);
+ D = f->next[1-dir]; d = dpaddr(block, D);
+
+ C = d->next[1-dir];
+ E = d->next[dir];
+ *treep = D;
+ d->next[1-dir] = B;
+ d->next[dir] = F;
+ b->next[dir] = C;
+ f->next[1-dir] = E;
+ d->longer = Neither;
+ b->longer = f->longer = Neither;
+
+ if (third == Neither)
+ return 0;
+ else if (third == dir) {
+ b->longer = 1-dir;
+ return E;
+ } else {
+ f->longer = dir;
+ return C;
+ }
+}
+
+static void dir_check_balance(char *block, int psz);
+int lafs_dir_add_ent(char *block, int psz, const char *name, int len,
+ u32 target, int type, u32 seed, u32 hash, int hashoffset)
+{
+ /* Add this entry to the directory block,
+ * Return:
+ * -2 hash value is in use, same name
+ * -1 hash value is in use, different name
+ * 0 insufficient room
+ * 1 add successful
+ *
+ */
+ struct dirheader *dh = (struct dirheader *) block;
+ struct dirpiece *dp, *dpold;
+ int piece = dh->root;
+ u8 *thisp = &dh->root;
+ u8 *topp = thisp;
+ int need, space;
+ int st;
+ int first, second, third;
+
+ int depth = 0;
+ /* path is a list of bits indicate whether each successive step
+ * down from *topp was foreward(1) or backward(0).
+ */
+ unsigned long path = 0;
+
+ int dir;
+
+ /* loop detect */
+ int last = 0, cnt = 0, reset = 1;
+
+ if (len == 0)
+ len = strlen(name);
+ if (piece == 0) {
+ /* Block is empty */
+ if (type != DT_TEST)
+ lafs_dir_init_block(block, psz, name, len, target,
+ type, hashoffset);
+ return 1;
+ }
+ need = len + (hashoffset > 255 ? 4 : hashoffset > 1 ? 1 : 0);
+ need += offsetof(struct dirpiece, name);
+ need = DIV_ROUND_UP(need, (1<<psz));
+
+ /* First, find the insertion point */
+ dp = dpaddr(block, piece);
+ while (piece) {
+ u32 hval = hash_piece(seed, dp, NULL);
+
+ if (hval == hash) {
+ if (dp->target == 0)
+ /* deleted entry, no AVL op needed */
+ goto replace_deleted;
+
+ if (len == dp->length &&
+ strncmp(name, dp->name, len) == 0)
+ return -2;
+ return -1;
+ }
+ dir = (hash > hval);
+ if (dp->longer != Neither) {
+ depth = 0;
+ topp = thisp;
+ }
+ if (dir)
+ set_bit(depth, &path);
+ else
+ clear_bit(depth, &path);
+ depth++;
+ if (depth >= sizeof(path)*8)
+ return -2;
+ thisp = &dp->next[dir];
+ piece = *thisp;
+ dp = dpaddr(block, piece);
+
+ if (cnt > 0 && piece == last) {
+ return -3;
+ }
+ if (cnt == 0) {
+ reset += reset;
+ cnt = reset;
+ last = piece;
+ }
+ cnt--;
+ }
+
+ /* Now see if there is room to store this entry, given the amount of
+ * sharing that we have managed to achieve
+ */
+ if (dh->lastpiece + need > 255)
+ return 0;
+ if (type == DT_TEST)
+ /* Special flag to say 'just test if there is room */
+ return 1;
+ piece = dh->lastpiece+1;
+
+ dp = dpaddr(block, piece);
+ dh->lastpiece += need;
+ BUG_ON(dh->lastpiece == 0);
+ dh->freepieces -= need;
+ dp->target = cpu_to_le32(target);
+ dp->next[0] = 0;
+ dp->next[1] = 0;
+
+ dp->length = len;
+ dp->type = type;
+ dp->longer = Neither;
+ dir_set_name(dp, name, len, hashoffset);
+
+ /* now merge this piece into the AVL tree, rebalancing
+ * on the way up
+ */
+ *thisp = piece;
+
+ piece = *topp;
+ dp = dpaddr(block, piece);
+
+ st = 0;
+ first = !!test_bit(0, &path);
+ second = !!test_bit(1, &path);
+ if (dp->longer == Neither)
+ ;
+ else if (dp->longer != first) {
+ /* took the shorter path */
+ dp->longer = Neither;
+ piece = dp->next[first];
+ st = 1;
+ } else if (first == second) {
+ /* just a two-point rotation */
+ piece = dir_rotate_2(block, psz, topp, first);
+ st = 2;
+ } else {
+ if (depth < 3)
+ third = Neither;
+ else
+ third = !!test_bit(2, &path);
+ piece = dir_rotate_3(block, psz, topp, first, third);
+ st = 3;
+ }
+
+ while (piece && st < depth) {
+ first = test_bit(st, &path) ? 1 : 0;
+ dp = dpaddr(block, piece);
+ dp->longer = first;
+ piece = dp->next[first];
+ st++;
+ }
+ BUG_ON(dh->root == 0);
+ dir_check_balance(block, psz);
+ return 1;
+
+replace_deleted:
+ /* If there is room at the end, add an entry,
+ * else fail.
+ */
+ if (dh->lastpiece + need > 255)
+ return 0;
+ if (type == DT_TEST)
+ return 1;
+
+ space = dp->length + (dp->chain_info < 2
+ ? 0 : (dp->chain_info == 2
+ ? 1 : 4));
+ space += offsetof(struct dirpiece, name);
+ space = DIV_ROUND_UP(space, 1<<psz);
+
+ piece = dh->lastpiece + 1;
+ dpold = dp;
+ dp = dpaddr(block, piece);
+ dh->lastpiece += need;
+ dh->freepieces -= need;
+ dh->freepieces += space;
+ *thisp = piece;
+ dp->next[0] = dpold->next[0];
+ dp->next[1] = dpold->next[1];
+ dp->target = cpu_to_le32(target);
+ dp->length = len;
+ dp->type = type;
+ dir_set_name(dp, name, len, hashoffset);
+ return 1;
+}
+
+int lafs_dir_del_ent(char *block, int psz, u32 seed, u32 hash)
+{
+ /* Delete this entry from the directory block.
+ * This involves removing it from the avl tree.
+ * If it was the last entry, we reduce 'lastpiece'
+ * so the space can be used immediately.
+ */
+
+ struct dirheader *dh = (struct dirheader *)block;
+ struct dirpiece *dp;
+ struct dirpiece *second;
+ int piece = dh->root;
+ u8 *thisp = &dh->root;
+ u8 *topp = thisp;
+ u8 *targetp = NULL;
+ u8 targetn = 0;
+ int space;
+ int dir = 0;
+ int depth = 0;
+ unsigned long path = 0;
+ int st = 0;
+
+ dp = dpaddr(block, piece);
+ while (piece) {
+ u32 hval = hash_piece(seed, dp, NULL);
+
+ if (hash == hval) {
+ targetp = thisp;
+ targetn = piece;
+ }
+ dir = (hash > hval);
+ if (dp->next[dir] == 0)
+ break;
+ if (dp->longer == Neither) {
+ topp = thisp;
+ depth = 0;
+ } else if (dp->longer == (1-dir)) {
+ struct dirpiece *dp2;
+ dp2 = dpaddr(block, dp->next[1-dir]);
+ if (dp2->longer == Neither) {
+ topp = thisp;
+ depth = 0;
+ }
+ }
+ if (dir)
+ set_bit(depth, &path);
+ else
+ clear_bit(depth, &path);
+ depth++;
+ if (depth >= sizeof(path)*8)
+ return -2;
+
+ thisp = &dp->next[dir];
+ piece = *thisp;
+ dp = dpaddr(block, piece);
+ }
+ if (!targetp)
+ return 0;
+ if (dir)
+ set_bit(depth, &path);
+ else
+ clear_bit(depth, &path);
+
+ /* now we must walk down from topp to thisp rebalancing nodes,
+ * but making sure that targetp points to the link to target...
+ */
+
+ while (1) {
+ piece = *topp;
+ dir = !!test_bit(st, &path);
+ dp = dpaddr(block, piece);
+ if (dp->next[dir] == 0)
+ break;
+
+ if (dp->longer == Neither)
+ dp->longer = 1-dir;
+ else if (dp->longer == dir)
+ dp->longer = Neither;
+ else {
+ /* need a rotation */
+ second =
+ dpaddr(block, dp->next[1-dir]);
+ if (second->longer == dir) {
+ struct dirpiece *third =
+ dpaddr(block, second->next[dir]);
+ dir_rotate_3(block, psz, topp, 1-dir,
+ third->longer);
+ } else if (second->longer == Neither) {
+ dir_rotate_2(block, psz, topp, 1-dir);
+ dp->longer = 1-dir;
+ second = dpaddr(block, *topp);
+ second->longer = dir;
+ } else
+ dir_rotate_2(block, psz, topp, 1-dir);
+ if (piece == targetn) {
+ second = dpaddr(block, *topp);
+ targetp = &second->next[dir];
+ }
+ }
+ topp = &dp->next[dir];
+ st++;
+ }
+
+ /* Ok, rebalance all done, now swap *targetp for *thisp and
+ * delete
+ */
+
+ piece = *thisp;
+ *targetp = piece;
+ dp = dpaddr(block, piece);
+ second = dpaddr(block, targetn);
+ *thisp = dp->next[1-dir];
+ dp->next[0] = second->next[0];
+ dp->next[1] = second->next[1];
+ dp->longer = second->longer;
+
+ /* now second can be destroyed */
+ second->target = 0;
+ space = second->length + (second->chain_info < 2
+ ? 0 : second->chain_info == 2 ? 1 : 4);
+ space += offsetof(struct dirpiece, name);
+ space = DIV_ROUND_UP(space, 1<<psz);
+ if (dh->root == 0) {
+ /* we deleted the only entry, clear the block */
+ dh->lastpiece = (sizeof(struct dirheader) + (1<<psz)-1) >> psz;
+ dh->freepieces = 255 - dh->lastpiece;
+ } else if (targetn + space > dh->lastpiece) {
+ /* We are deleting the last entry, so it can be reused */
+ dh->freepieces += dh->lastpiece+1-targetn;
+ dh->lastpiece = targetn-1;
+ } else
+ dh->freepieces += space;
+ return 1;
+}
+
+static void dir_linearise(char *block, int psz)
+{
+ /* destructively linearise the entries in the block.
+ * i.e. arrange that for each non-deleted entry,
+ * ->next[0] points to the previous, and
+ * ->next[1] points to the next
+ * in sort order.
+ * The first points to the last, and dh->root
+ * points to the first
+ *
+ * Rather than using a stack to walk down, we reverse
+ * each pointer was we step down it, and use
+ * the ->longer field to say which way we came
+ */
+ struct dirheader *dh = (struct dirheader *)block;
+ int piece = dh->root;
+ struct dirpiece *dp = NULL;
+ int prev = 0;
+ int parent = 0;
+ int state = 0;
+ int tail;
+
+ while (piece) {
+ dp = dpaddr(block, piece);
+ switch (state) {
+ case 0: /* stepping down to piece for the first time */
+ if (dp->next[0]) {
+ /* step further down */
+ int t = dp->next[0];
+ dp->next[0] = parent;
+ dp->longer = 0;
+ parent = piece;
+ piece = t;
+ state = 0;
+ } else
+ state = 1;
+ break;
+ case 1: /* back up from the left branch */
+ /* This must be next in sequence */
+ dp->next[0] = prev;
+ prev = piece;
+ if (dp->next[1]) {
+ /* step down the other way */
+ int t = dp->next[1];
+ dp->longer = 1;
+ dp->next[1] = parent;
+ parent = piece;
+ piece = t;
+ state = 0;
+ } else
+ state = 2;
+ break;
+ case 2: /* back up from the right branch */
+ piece = parent;
+ dp = dpaddr(block, piece);
+ state = dp->longer;
+ parent = dp->next[state];
+ state++;
+ break;
+ default:
+ BUG();
+ }
+ }
+ /* now 'prev' is the last piece. Walk back along the path setting
+ * the forward link
+ */
+ piece = 0;
+ tail = prev;
+ while (prev) {
+ dp = dpaddr(block, prev);
+ dp->next[1] = piece;
+ piece = prev;
+ prev = dp->next[0];
+ }
+ dp->next[0] = tail;
+ dh->root = piece;
+}
+
+struct dir_ent *
+lafs_dir_extract(char *block, int psz, struct dir_ent *de, int pnum,
+ u32 *hash)
+{
+ /* extract the directory entry into de. de->name points into
+ * the buffer, and is not nul terminated. */
+ struct dirpiece *dp = dpaddr(block, pnum);
+
+ BUG_ON(pnum <= 0 || pnum > 255);
+ de->target = le32_to_cpu(dp->target);
+ de->type = dp->type;
+ de->name = dp->name;
+ de->nlen = dp->length;
+ if (hash)
+ *hash = hash_piece(*hash, dp, NULL);
+ return de;
+}
+
+void lafs_dir_set_target(char *block, int psz, struct dir_ent *de, int pnum)
+{
+ /* update the target and type from de */
+ struct dirpiece *dp = dpaddr(block, pnum);
+ dp->target = cpu_to_le32(de->target);
+ dp->type = de->type;
+}
+
+void lafs_dir_split(char *orig, int psz, char *new1, char *new2,
+ const char *name, u32 target, int type, u32 *newhash,
+ u32 seed, u32 hash, int chainoffset)
+{
+ /* Split the orig block together with the new name, into new1 and new2.
+ * Linearise orig, then copy one entry into which block is least empty
+ * A hash somewhere between the two blocks is placed in *newhash.
+ * It could be the highest in 'new1' but will be less than the
+ * lowest in 'new2'
+ *
+ */
+ struct dirheader *dh = (struct dirheader *)orig;
+ struct dirheader *dh1 = (struct dirheader *)new1;
+ struct dirheader *dh2 = (struct dirheader *)new2;
+ struct dirpiece *dp;
+ int first, last;
+ int full1 = 0, full2 = 0;
+ u32 offset, maxhash, minhash, hval;
+
+ dir_linearise(orig, psz);
+
+ first = dh->root;
+ dp = dpaddr(orig, first);
+ last = dp->next[0];
+ if (first == 0 || last == 0)
+ /* orig was empty ?? */
+ BUG();
+
+ /* create new1 and new2 with first and last */
+ hval = hash_piece(seed, dp, &offset);
+ if (type && hash < hval) {
+ lafs_dir_init_block(new1, psz, name, 0, target, type,
+ chainoffset);
+ type = 0;
+ maxhash = hash;
+ } else {
+ lafs_dir_init_block(new1, psz, dp->name, dp->length,
+ le32_to_cpu(dp->target), dp->type,
+ offset);
+ maxhash = hval;
+ if (first == last)
+ first = 0;
+ else
+ first = dp->next[1];
+ }
+ dp = dpaddr(orig, last);
+ hval = hash_piece(seed, dp, &offset);
+ if (type && hash > hval) {
+ lafs_dir_init_block(new2, psz, name, 0, target, type,
+ chainoffset);
+ minhash = hash;
+ type = 0;
+ } else {
+ BUG_ON(!first);
+ lafs_dir_init_block(new2, psz, dp->name, dp->length,
+ le32_to_cpu(dp->target), dp->type,
+ offset);
+ minhash = hval;
+ if (first == last)
+ first = 0;
+ else
+ last = dp->next[0];
+ }
+
+ while (first || type) {
+ /* everything from 'first' to 'last', plus 'name' (if type)
+ * is allowed to go in either block.
+ * Choose a block, and an entry, and insert it (if possible)
+ */
+ if (full2 || (dh1->freepieces >= dh2->freepieces && !full1)) {
+ /* insert into new1 from first or name */
+ dp = dpaddr(orig, first);
+ if (first)
+ hval = hash_piece(seed, dp, &offset);
+ if (type == 0 || (first && hval < hash)) {
+ /* first is the preferred candidate */
+ if (!lafs_dir_add_ent(new1, psz, dp->name,
+ dp->length,
+ le32_to_cpu(dp->target),
+ dp->type, seed, hval,
+ offset))
+ full1 = 1;
+ else {
+ maxhash = hval;
+ if (first == last)
+ first = 0;
+ else
+ first = dp->next[1];
+ }
+ } else {
+ /* insert name */
+ if (!lafs_dir_add_ent(new1, psz, name, 0,
+ target, type, seed,
+ hash, chainoffset))
+ full1 = 1;
+ else {
+ maxhash = hash;
+ type = 0;
+ }
+ }
+ } else {
+ /* insert into new2 */
+ dp = dpaddr(orig, last);
+ if (first)
+ hval = hash_piece(seed, dp, &offset);
+ if (type == 0 || (first && hval > hash)) {
+ /* last is the preferred candidate */
+ if (!lafs_dir_add_ent(new2, psz,
+ dp->name, dp->length,
+ le32_to_cpu(dp->target),
+ dp->type, seed, hval,
+ offset))
+ full2 = 1;
+ else {
+ minhash = hval;
+ if (first == last)
+ first = 0;
+ else
+ last = dp->next[0];
+ }
+ } else {
+ if (!lafs_dir_add_ent(new2, psz, name, 0,
+ target, type, seed,
+ hval, chainoffset))
+ full2 = 1;
+ else {
+ minhash = hash;
+ type = 0;
+ }
+ }
+ }
+ }
+
+ /* newhash could be minhash, but not
+ * maxhash */
+ *newhash = (minhash + maxhash) / 2;
+}
+
+void lafs_dir_repack(char *block, int psz, char *new, u32 seed, int merge)
+{
+ struct dirheader *dh = (struct dirheader *)block;
+ int pnum = (sizeof(struct dirheader) + (1<<psz)-1)>>psz;
+ int first = !merge;
+
+ while (pnum <= dh->lastpiece) {
+ int space;
+ struct dirpiece *dp = dpaddr(block, pnum);
+
+ if (dp->target) {
+ u32 offset;
+ u32 hash = hash_piece(seed, dp, &offset);
+ if (first)
+ lafs_dir_init_block(new, psz, dp->name,
+ dp->length,
+ le32_to_cpu(dp->target),
+ dp->type, offset);
+ else
+ lafs_dir_add_ent(new, psz, dp->name, dp->length,
+ le32_to_cpu(dp->target),
+ dp->type, seed, hash, offset);
+ first = 0;
+ }
+ space = dp->length + (dp->chain_info < 2
+ ? 0 : (dp->chain_info == 2
+ ? 1 : 4));
+ space += offsetof(struct dirpiece, name);
+ space = DIV_ROUND_UP(space, 1<<psz);
+
+ pnum += space;
+ }
+}
+
+int lafs_dir_find(char *block, int psz, u32 seed, u32 hash, u8 *pp)
+{
+ /* Find the entry for 'hash', if it exists.
+ * Return 1 if found, 0 if not.
+ * set 'pp' to the piece number if found, or the
+ * next larger piece if not (zero if nothing is larger).
+ */
+ struct dirheader *dh = (struct dirheader *)block;
+ int pnum = dh->root;
+ int cnt = 256;
+
+ *pp = 0;
+
+ while (pnum && cnt) {
+ struct dirpiece *dp = dpaddr(block, pnum);
+ u32 hval = hash_piece(seed, dp, NULL);
+
+ if (hval == hash) {
+ *pp = pnum;
+ return 1;
+ }
+
+ if (hash > hval)
+ pnum = dp->next[1];
+ else {
+ *pp = pnum;
+ pnum = dp->next[0];
+ }
+ cnt--;
+ }
+ return 0;
+}
+
+#if 0
+static int dir_check_loop(char *block, int psz, int pnum, int depth)
+{
+ /* walk around the tree, and BUG if we ever get a depth > 255 */
+ struct dirheader *dh = (struct dirheader *)block;
+
+ if (pnum == -1)
+ pnum = dh->root;
+ if (depth <= 0)
+ return 1;
+ if (pnum < 0 || pnum >= 256)
+ BUG();
+
+ if (pnum) {
+ struct dirpiece *dp = dpaddr(block, pnum);
+ if (dir_check_loop(block, psz, dp->next[0], depth-1) ||
+ dir_check_loop(block, psz, dp->next[1], depth-1)) {
+ printk(" ..%d(%d)\n", pnum, depth);
+ return 1;
+ }
+ }
+ return 0;
+}
+#endif
+
+int lafs_dir_empty(char *block)
+{
+ struct dirheader *dh = (struct dirheader *)block;
+ return dh->root == 0;
+}
+
+int lafs_dir_blk_size(char *block, int psz)
+{
+ /* how much of this block do we actually need to store */
+ struct dirheader *dh = (struct dirheader *)block;
+ if (lafs_dir_empty(block))
+ return 0;
+ return (dh->lastpiece+1) << psz;
+}
+
+/* Testing code here - no new important functionality */
+#ifndef MAIN
+
+static void xprintk(char *block, int psz, char *s, int a, int b, int c, int d)
+{
+ printk(s, a, b, c, d);
+ lafs_dir_print(block, psz);
+ BUG();
+}
+
+static int dir_check_depth(char *block, int psz, int p, int depth)
+{
+ struct dirpiece *dp = dpaddr(block, p);
+ int b, f;
+
+ if (depth > 10) {
+ int i;
+ for (i = 0; i < 32; i++)
+ printk("%02x ", block[i]);
+ printk("\n");
+ }
+ BUG_ON(depth > 10);
+ if (p == 0)
+ return 0;
+ b = dir_check_depth(block, psz, dp->next[0], depth+1);
+ f = dir_check_depth(block, psz, dp->next[1], depth+1);
+ if (b == f) {
+ if (dp->longer != Neither)
+ xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n",
+ p, b, f, dp->longer);
+ return b+1;
+ }
+ if (b == f-1) {
+ if (dp->longer != 1)
+ xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n",
+ p, b, f, dp->longer);
+ return f+1;
+ }
+ if (b-1 == f) {
+ if (dp->longer != 0)
+ xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n",
+ p, b, f, dp->longer);
+ return b+1;
+ }
+ xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n", p, b, f, dp->longer);
+ return (b > f ? b : f) + 1;
+}
+
+static void dir_check_balance(char *block, int psz)
+{
+ struct dirheader *dh = (struct dirheader *) block;
+ dir_check_depth(block, psz, dh->root, 0);
+}
+
+static void dir_print_piece(char *block, int psz, int piece, int depth, int dir)
+{
+ struct dirpiece *dp = dpaddr(block, piece);
+
+ if (piece == 0)
+ return;
+
+ dir_print_piece(block, psz, dp->next[0], depth+1, 0);
+ printk("%3d - %08lu:%02d %*s%c", piece,
+ (unsigned long) le32_to_cpu(dp->target),
+ depth, depth*2, "",
+ dir ? '\\' : '/');
+
+ printk("%.*s\n", dp->length, dp->name);
+ dir_print_piece(block, psz, dp->next[1], depth+1, 1);
+}
+
+static void dir_print_block(char *block, int psz, int sort)
+{
+ struct dirheader *dh;
+ struct dirpiece *dp;
+
+ dh = (struct dirheader *)block;
+ printk("===Directory Block===\n");
+
+ printk(" Root: %d\n", dh->root);
+ printk(" Last Piece : %d (%d left)\n", dh->lastpiece,
+ 255 - dh->lastpiece);
+ printk(" Free Pieces: %d (%d deleted)\n", dh->freepieces,
+ dh->freepieces - (255 - dh->lastpiece));
+ if (sort == 1)
+ dir_print_piece(block, psz, dh->root, 0, 1);
+ else if (sort == 2) {
+ /* linearised */
+ int pnum = dh->root;
+ while (pnum) {
+ dp = dpaddr(block, pnum);
+ printk("%3d - %08lu: (b:%-3d, f:%-3d, l:%d, type:%d ",
+ pnum, (unsigned long) le32_to_cpu(dp->target),
+ dp->next[0], dp->next[1], dp->longer,
+ dp->type);
+ printk(": (%d)%.*s\n", dp->length, dp->length,
+ dp->name);
+ pnum = dp->next[1];
+ }
+ } else {
+ /* don't interpret the pieces too much */
+ int pnum = (sizeof(struct dirheader) + (1<<psz)-1)>>psz;
+ while (pnum <= dh->lastpiece) {
+ dp = dpaddr(block, pnum);
+ printk("%3d - %08lu: (b:%-3d, f:%-3d, l:%d, type:%d ",
+ pnum, (unsigned long)le32_to_cpu(dp->target),
+ dp->next[0], dp->next[1], dp->longer,
+ dp->type);
+ printk(": (%d)%.*s\n", dp->length,
+ dp->length, dp->name);
+ pnum += (offsetof(struct dirpiece, name)
+ + dp->length + (1<<psz)-1)>>psz;
+ }
+ }
+}
+
+void lafs_dir_print(char *buf, int psz)
+{
+ dir_print_block(buf, psz, 1);
+}
+#endif
+
+#ifdef MAIN
+
+int noise;
+int main(int argc, char **argv)
+{
+ char block[4096];
+ int blenshift = 10;
+ int psz = blenshift - 8;
+ int arg = 2;
+ char nm[256];
+
+ lafs_dir_init_block(block, psz, argv[1], 0, 42, 3, 0);
+ while (arg < argc-1) {
+ if (argv[arg][0] != '-')
+ switch (lafs_dir_add_ent(block, psz, argv[arg], 0,
+ 42+arg, 4, 0)) {
+ case 0:
+ printf("%s didn't fit!\n", argv[arg]);
+ break;
+ case -1:
+ printf("%s already exists\n", argv[arg]);
+ break;
+ case 1:
+ printf("%s inserted\n", argv[arg]);
+ }
+ else
+ switch (lafs_dir_del_ent(block, psz, argv[arg]+1, 0)) {
+ case 0:
+ printf("%s not found!\n", argv[arg]);
+ break;
+ case -2:
+ printf("%s not deleted - bad dir\n", argv[arg]);
+ break;
+ case 1:
+ printf("%s deleted\n", argv[arg]);
+ break;
+ }
+
+ dir_check_balance(block, psz);
+ arg++;
+ }
+ dir_print_block(block, psz, 0);
+ dir_print_block(block, psz, 1);
+
+ lafs_dir_split(block, psz, block+1024, block+2048, argv[arg],
+ 40, 2, nm);
+ dir_print_block(block+1024, psz, 1);
+ dir_print_block(block+2048, psz, 1);
+ dir_get_prefix(block+1024, block+2048, psz, block+3096);
+ printf("Prefix is <%s>\n", block+3096);
+ lafs_dir_repack(block+1024, psz, block, 0);
+ lafs_dir_repack(block+2048, psz, block, 1);
+ printf("============= repacked ===================\n");
+ dir_print_block(block, psz, 1);
+ exit(0);
+}
+#endif
git / lafs-utils.git / commitdiff