From 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 16 Apr 2005 15:20:36 -0700 Subject: Linux-2.6.12-rc2 Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip! --- fs/hfsplus/brec.c | 491 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 491 insertions(+) create mode 100644 fs/hfsplus/brec.c (limited to 'fs/hfsplus/brec.c') diff --git a/fs/hfsplus/brec.c b/fs/hfsplus/brec.c new file mode 100644 index 00000000000..0ccef2ab790 --- /dev/null +++ b/fs/hfsplus/brec.c @@ -0,0 +1,491 @@ +/* + * linux/fs/hfsplus/brec.c + * + * Copyright (C) 2001 + * Brad Boyer (flar@allandria.com) + * (C) 2003 Ardis Technologies + * + * Handle individual btree records + */ + +#include "hfsplus_fs.h" +#include "hfsplus_raw.h" + +static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd); +static int hfs_brec_update_parent(struct hfs_find_data *fd); +static int hfs_btree_inc_height(struct hfs_btree *); + +/* Get the length and offset of the given record in the given node */ +u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) +{ + __be16 retval[2]; + u16 dataoff; + + dataoff = node->tree->node_size - (rec + 2) * 2; + hfs_bnode_read(node, retval, dataoff, 4); + *off = be16_to_cpu(retval[1]); + return be16_to_cpu(retval[0]) - *off; +} + +/* Get the length of the key from a keyed record */ +u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) +{ + u16 retval, recoff; + + if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF) + return 0; + + if ((node->type == HFS_NODE_INDEX) && + !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { + retval = node->tree->max_key_len + 2; + } else { + recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); + if (!recoff) + return 0; + if (node->tree->attributes & HFS_TREE_BIGKEYS) + retval = hfs_bnode_read_u16(node, recoff) + 2; + else + retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1; + } + return retval; +} + +int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int entry_len) +{ + struct hfs_btree *tree; + struct hfs_bnode *node, *new_node; + int size, key_len, rec; + int data_off, end_off; + int idx_rec_off, data_rec_off, end_rec_off; + __be32 cnid; + + tree = fd->tree; + if (!fd->bnode) { + if (!tree->root) + hfs_btree_inc_height(tree); + fd->bnode = hfs_bnode_find(tree, tree->leaf_head); + if (IS_ERR(fd->bnode)) + return PTR_ERR(fd->bnode); + fd->record = -1; + } + new_node = NULL; + key_len = be16_to_cpu(fd->search_key->key_len) + 2; +again: + /* new record idx and complete record size */ + rec = fd->record + 1; + size = key_len + entry_len; + + node = fd->bnode; + hfs_bnode_dump(node); + /* get last offset */ + end_rec_off = tree->node_size - (node->num_recs + 1) * 2; + end_off = hfs_bnode_read_u16(node, end_rec_off); + end_rec_off -= 2; + dprint(DBG_BNODE_MOD, "insert_rec: %d, %d, %d, %d\n", rec, size, end_off, end_rec_off); + if (size > end_rec_off - end_off) { + if (new_node) + panic("not enough room!\n"); + new_node = hfs_bnode_split(fd); + if (IS_ERR(new_node)) + return PTR_ERR(new_node); + goto again; + } + if (node->type == HFS_NODE_LEAF) { + tree->leaf_count++; + mark_inode_dirty(tree->inode); + } + node->num_recs++; + /* write new last offset */ + hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs); + hfs_bnode_write_u16(node, end_rec_off, end_off + size); + data_off = end_off; + data_rec_off = end_rec_off + 2; + idx_rec_off = tree->node_size - (rec + 1) * 2; + if (idx_rec_off == data_rec_off) + goto skip; + /* move all following entries */ + do { + data_off = hfs_bnode_read_u16(node, data_rec_off + 2); + hfs_bnode_write_u16(node, data_rec_off, data_off + size); + data_rec_off += 2; + } while (data_rec_off < idx_rec_off); + + /* move data away */ + hfs_bnode_move(node, data_off + size, data_off, + end_off - data_off); + +skip: + hfs_bnode_write(node, fd->search_key, data_off, key_len); + hfs_bnode_write(node, entry, data_off + key_len, entry_len); + hfs_bnode_dump(node); + + if (new_node) { + /* update parent key if we inserted a key + * at the start of the first node + */ + if (!rec && new_node != node) + hfs_brec_update_parent(fd); + + hfs_bnode_put(fd->bnode); + if (!new_node->parent) { + hfs_btree_inc_height(tree); + new_node->parent = tree->root; + } + fd->bnode = hfs_bnode_find(tree, new_node->parent); + + /* create index data entry */ + cnid = cpu_to_be32(new_node->this); + entry = &cnid; + entry_len = sizeof(cnid); + + /* get index key */ + hfs_bnode_read_key(new_node, fd->search_key, 14); + __hfs_brec_find(fd->bnode, fd); + + hfs_bnode_put(new_node); + new_node = NULL; + + if (tree->attributes & HFS_TREE_VARIDXKEYS) + key_len = be16_to_cpu(fd->search_key->key_len) + 2; + else { + fd->search_key->key_len = cpu_to_be16(tree->max_key_len); + key_len = tree->max_key_len + 2; + } + goto again; + } + + if (!rec) + hfs_brec_update_parent(fd); + + return 0; +} + +int hfs_brec_remove(struct hfs_find_data *fd) +{ + struct hfs_btree *tree; + struct hfs_bnode *node, *parent; + int end_off, rec_off, data_off, size; + + tree = fd->tree; + node = fd->bnode; +again: + rec_off = tree->node_size - (fd->record + 2) * 2; + end_off = tree->node_size - (node->num_recs + 1) * 2; + + if (node->type == HFS_NODE_LEAF) { + tree->leaf_count--; + mark_inode_dirty(tree->inode); + } + hfs_bnode_dump(node); + dprint(DBG_BNODE_MOD, "remove_rec: %d, %d\n", fd->record, fd->keylength + fd->entrylength); + if (!--node->num_recs) { + hfs_bnode_unlink(node); + if (!node->parent) + return 0; + parent = hfs_bnode_find(tree, node->parent); + if (IS_ERR(parent)) + return PTR_ERR(parent); + hfs_bnode_put(node); + node = fd->bnode = parent; + + __hfs_brec_find(node, fd); + goto again; + } + hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs); + + if (rec_off == end_off) + goto skip; + size = fd->keylength + fd->entrylength; + + do { + data_off = hfs_bnode_read_u16(node, rec_off); + hfs_bnode_write_u16(node, rec_off + 2, data_off - size); + rec_off -= 2; + } while (rec_off >= end_off); + + /* fill hole */ + hfs_bnode_move(node, fd->keyoffset, fd->keyoffset + size, + data_off - fd->keyoffset - size); +skip: + hfs_bnode_dump(node); + if (!fd->record) + hfs_brec_update_parent(fd); + return 0; +} + +static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) +{ + struct hfs_btree *tree; + struct hfs_bnode *node, *new_node; + struct hfs_bnode_desc node_desc; + int num_recs, new_rec_off, new_off, old_rec_off; + int data_start, data_end, size; + + tree = fd->tree; + node = fd->bnode; + new_node = hfs_bmap_alloc(tree); + if (IS_ERR(new_node)) + return new_node; + hfs_bnode_get(node); + dprint(DBG_BNODE_MOD, "split_nodes: %d - %d - %d\n", + node->this, new_node->this, node->next); + new_node->next = node->next; + new_node->prev = node->this; + new_node->parent = node->parent; + new_node->type = node->type; + new_node->height = node->height; + + size = tree->node_size / 2 - node->num_recs * 2 - 14; + old_rec_off = tree->node_size - 4; + num_recs = 1; + for (;;) { + data_start = hfs_bnode_read_u16(node, old_rec_off); + if (data_start > size) + break; + old_rec_off -= 2; + if (++num_recs < node->num_recs) + continue; + /* panic? */ + hfs_bnode_put(node); + hfs_bnode_put(new_node); + return ERR_PTR(-ENOSPC); + } + + if (fd->record + 1 < num_recs) { + /* new record is in the lower half, + * so leave some more space there + */ + old_rec_off += 2; + num_recs--; + data_start = hfs_bnode_read_u16(node, old_rec_off); + } else { + hfs_bnode_put(node); + hfs_bnode_get(new_node); + fd->bnode = new_node; + fd->record -= num_recs; + fd->keyoffset -= data_start - 14; + fd->entryoffset -= data_start - 14; + } + new_node->num_recs = node->num_recs - num_recs; + node->num_recs = num_recs; + + new_rec_off = tree->node_size - 2; + new_off = 14; + size = data_start - new_off; + num_recs = new_node->num_recs; + data_end = data_start; + while (num_recs) { + hfs_bnode_write_u16(new_node, new_rec_off, new_off); + old_rec_off -= 2; + new_rec_off -= 2; + data_end = hfs_bnode_read_u16(node, old_rec_off); + new_off = data_end - size; + num_recs--; + } + hfs_bnode_write_u16(new_node, new_rec_off, new_off); + hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start); + + /* update new bnode header */ + node_desc.next = cpu_to_be32(new_node->next); + node_desc.prev = cpu_to_be32(new_node->prev); + node_desc.type = new_node->type; + node_desc.height = new_node->height; + node_desc.num_recs = cpu_to_be16(new_node->num_recs); + node_desc.reserved = 0; + hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc)); + + /* update previous bnode header */ + node->next = new_node->this; + hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc)); + node_desc.next = cpu_to_be32(node->next); + node_desc.num_recs = cpu_to_be16(node->num_recs); + hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc)); + + /* update next bnode header */ + if (new_node->next) { + struct hfs_bnode *next_node = hfs_bnode_find(tree, new_node->next); + next_node->prev = new_node->this; + hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc)); + node_desc.prev = cpu_to_be32(next_node->prev); + hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc)); + hfs_bnode_put(next_node); + } else if (node->this == tree->leaf_tail) { + /* if there is no next node, this might be the new tail */ + tree->leaf_tail = new_node->this; + mark_inode_dirty(tree->inode); + } + + hfs_bnode_dump(node); + hfs_bnode_dump(new_node); + hfs_bnode_put(node); + + return new_node; +} + +static int hfs_brec_update_parent(struct hfs_find_data *fd) +{ + struct hfs_btree *tree; + struct hfs_bnode *node, *new_node, *parent; + int newkeylen, diff; + int rec, rec_off, end_rec_off; + int start_off, end_off; + + tree = fd->tree; + node = fd->bnode; + new_node = NULL; + if (!node->parent) + return 0; + +again: + parent = hfs_bnode_find(tree, node->parent); + if (IS_ERR(parent)) + return PTR_ERR(parent); + __hfs_brec_find(parent, fd); + hfs_bnode_dump(parent); + rec = fd->record; + + /* size difference between old and new key */ + if (tree->attributes & HFS_TREE_VARIDXKEYS) + newkeylen = hfs_bnode_read_u16(node, 14) + 2; + else + fd->keylength = newkeylen = tree->max_key_len + 2; + dprint(DBG_BNODE_MOD, "update_rec: %d, %d, %d\n", rec, fd->keylength, newkeylen); + + rec_off = tree->node_size - (rec + 2) * 2; + end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; + diff = newkeylen - fd->keylength; + if (!diff) + goto skip; + if (diff > 0) { + end_off = hfs_bnode_read_u16(parent, end_rec_off); + if (end_rec_off - end_off < diff) { + + printk("splitting index node...\n"); + fd->bnode = parent; + new_node = hfs_bnode_split(fd); + if (IS_ERR(new_node)) + return PTR_ERR(new_node); + parent = fd->bnode; + rec = fd->record; + rec_off = tree->node_size - (rec + 2) * 2; + end_rec_off = tree->node_size - (parent->num_recs + 1) * 2; + } + } + + end_off = start_off = hfs_bnode_read_u16(parent, rec_off); + hfs_bnode_write_u16(parent, rec_off, start_off + diff); + start_off -= 4; /* move previous cnid too */ + + while (rec_off > end_rec_off) { + rec_off -= 2; + end_off = hfs_bnode_read_u16(parent, rec_off); + hfs_bnode_write_u16(parent, rec_off, end_off + diff); + } + hfs_bnode_move(parent, start_off + diff, start_off, + end_off - start_off); +skip: + hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen); + hfs_bnode_dump(parent); + + hfs_bnode_put(node); + node = parent; + + if (new_node) { + __be32 cnid; + + fd->bnode = hfs_bnode_find(tree, new_node->parent); + /* create index key and entry */ + hfs_bnode_read_key(new_node, fd->search_key, 14); + cnid = cpu_to_be32(new_node->this); + + __hfs_brec_find(fd->bnode, fd); + hfs_brec_insert(fd, &cnid, sizeof(cnid)); + hfs_bnode_put(fd->bnode); + hfs_bnode_put(new_node); + + if (!rec) { + if (new_node == node) + goto out; + /* restore search_key */ + hfs_bnode_read_key(node, fd->search_key, 14); + } + } + + if (!rec && node->parent) + goto again; +out: + fd->bnode = node; + return 0; +} + +static int hfs_btree_inc_height(struct hfs_btree *tree) +{ + struct hfs_bnode *node, *new_node; + struct hfs_bnode_desc node_desc; + int key_size, rec; + __be32 cnid; + + node = NULL; + if (tree->root) { + node = hfs_bnode_find(tree, tree->root); + if (IS_ERR(node)) + return PTR_ERR(node); + } + new_node = hfs_bmap_alloc(tree); + if (IS_ERR(new_node)) { + hfs_bnode_put(node); + return PTR_ERR(new_node); + } + + tree->root = new_node->this; + if (!tree->depth) { + tree->leaf_head = tree->leaf_tail = new_node->this; + new_node->type = HFS_NODE_LEAF; + new_node->num_recs = 0; + } else { + new_node->type = HFS_NODE_INDEX; + new_node->num_recs = 1; + } + new_node->parent = 0; + new_node->next = 0; + new_node->prev = 0; + new_node->height = ++tree->depth; + + node_desc.next = cpu_to_be32(new_node->next); + node_desc.prev = cpu_to_be32(new_node->prev); + node_desc.type = new_node->type; + node_desc.height = new_node->height; + node_desc.num_recs = cpu_to_be16(new_node->num_recs); + node_desc.reserved = 0; + hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc)); + + rec = tree->node_size - 2; + hfs_bnode_write_u16(new_node, rec, 14); + + if (node) { + /* insert old root idx into new root */ + node->parent = tree->root; + if (node->type == HFS_NODE_LEAF || + tree->attributes & HFS_TREE_VARIDXKEYS) + key_size = hfs_bnode_read_u16(node, 14) + 2; + else + key_size = tree->max_key_len + 2; + hfs_bnode_copy(new_node, 14, node, 14, key_size); + + if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { + key_size = tree->max_key_len + 2; + hfs_bnode_write_u16(new_node, 14, tree->max_key_len); + } + cnid = cpu_to_be32(node->this); + hfs_bnode_write(new_node, &cnid, 14 + key_size, 4); + + rec -= 2; + hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4); + + hfs_bnode_put(node); + } + hfs_bnode_put(new_node); + mark_inode_dirty(tree->inode); + + return 0; +} -- cgit v1.2.3