Lines Matching full:node
18 /* Get the length and offset of the given record in the given node */
19 u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) in hfs_brec_lenoff() argument
24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
25 hfs_bnode_read(node, retval, dataoff, 4); in hfs_brec_lenoff()
31 u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) in hfs_brec_keylen() argument
35 if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF) in hfs_brec_keylen()
38 if ((node->type == HFS_NODE_INDEX) && in hfs_brec_keylen()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
45 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
49 retval = hfs_bnode_read_u16(node, recoff) + 2; in hfs_brec_keylen()
50 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
55 retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1; in hfs_brec_keylen()
56 if (retval > node->tree->max_key_len + 1) { in hfs_brec_keylen()
68 struct hfs_bnode *node, *new_node; in hfs_brec_insert() local
78 node = hfs_bnode_find(tree, tree->leaf_head); in hfs_brec_insert()
79 if (IS_ERR(node)) in hfs_brec_insert()
80 return PTR_ERR(node); in hfs_brec_insert()
81 fd->bnode = node; in hfs_brec_insert()
91 node = fd->bnode; in hfs_brec_insert()
92 hfs_bnode_dump(node); in hfs_brec_insert()
94 end_rec_off = tree->node_size - (node->num_recs + 1) * 2; in hfs_brec_insert()
95 end_off = hfs_bnode_read_u16(node, end_rec_off); in hfs_brec_insert()
107 if (node->type == HFS_NODE_LEAF) { in hfs_brec_insert()
111 node->num_recs++; in hfs_brec_insert()
113 hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs); in hfs_brec_insert()
114 hfs_bnode_write_u16(node, end_rec_off, end_off + size); in hfs_brec_insert()
122 data_off = hfs_bnode_read_u16(node, data_rec_off + 2); in hfs_brec_insert()
123 hfs_bnode_write_u16(node, data_rec_off, data_off + size); in hfs_brec_insert()
128 hfs_bnode_move(node, data_off + size, data_off, in hfs_brec_insert()
132 hfs_bnode_write(node, fd->search_key, data_off, key_len); in hfs_brec_insert()
133 hfs_bnode_write(node, entry, data_off + key_len, entry_len); in hfs_brec_insert()
134 hfs_bnode_dump(node); in hfs_brec_insert()
138 * at the start of the node and it is not the new node in hfs_brec_insert()
140 if (!rec && new_node != node) { in hfs_brec_insert()
141 hfs_bnode_read_key(node, fd->search_key, data_off + size); in hfs_brec_insert()
180 struct hfs_bnode *node, *parent; in hfs_brec_remove() local
185 node = fd->bnode; in hfs_brec_remove()
188 end_off = tree->node_size - (node->num_recs + 1) * 2; in hfs_brec_remove()
190 if (node->type == HFS_NODE_LEAF) { in hfs_brec_remove()
194 hfs_bnode_dump(node); in hfs_brec_remove()
197 if (!--node->num_recs) { in hfs_brec_remove()
198 hfs_bnode_unlink(node); in hfs_brec_remove()
199 if (!node->parent) in hfs_brec_remove()
201 parent = hfs_bnode_find(tree, node->parent); in hfs_brec_remove()
204 hfs_bnode_put(node); in hfs_brec_remove()
205 node = fd->bnode = parent; in hfs_brec_remove()
207 __hfs_brec_find(node, fd); in hfs_brec_remove()
210 hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs); in hfs_brec_remove()
216 hfs_bnode_clear(node, src, size); in hfs_brec_remove()
221 data_off = hfs_bnode_read_u16(node, rec_off); in hfs_brec_remove()
222 hfs_bnode_write_u16(node, rec_off + 2, data_off - size); in hfs_brec_remove()
231 hfs_bnode_move(node, dst, src, len); in hfs_brec_remove()
236 hfs_bnode_clear(node, src, len); in hfs_brec_remove()
242 hfs_bnode_write_u16(node, end_off, 0); in hfs_brec_remove()
244 hfs_bnode_dump(node); in hfs_brec_remove()
253 struct hfs_bnode *node, *new_node, *next_node; in hfs_bnode_split() local
259 node = fd->bnode; in hfs_bnode_split()
263 hfs_bnode_get(node); in hfs_bnode_split()
265 node->this, new_node->this, node->next); in hfs_bnode_split()
266 new_node->next = node->next; in hfs_bnode_split()
267 new_node->prev = node->this; in hfs_bnode_split()
268 new_node->parent = node->parent; in hfs_bnode_split()
269 new_node->type = node->type; in hfs_bnode_split()
270 new_node->height = node->height; in hfs_bnode_split()
272 if (node->next) in hfs_bnode_split()
273 next_node = hfs_bnode_find(tree, node->next); in hfs_bnode_split()
278 hfs_bnode_put(node); in hfs_bnode_split()
283 size = tree->node_size / 2 - node->num_recs * 2 - 14; in hfs_bnode_split()
287 data_start = hfs_bnode_read_u16(node, old_rec_off); in hfs_bnode_split()
291 if (++num_recs < node->num_recs) in hfs_bnode_split()
294 hfs_bnode_put(node); in hfs_bnode_split()
307 data_start = hfs_bnode_read_u16(node, old_rec_off); in hfs_bnode_split()
309 hfs_bnode_put(node); in hfs_bnode_split()
316 new_node->num_recs = node->num_recs - num_recs; in hfs_bnode_split()
317 node->num_recs = num_recs; in hfs_bnode_split()
328 data_end = hfs_bnode_read_u16(node, old_rec_off); in hfs_bnode_split()
333 hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start); in hfs_bnode_split()
345 node->next = new_node->this; in hfs_bnode_split()
346 hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc)); in hfs_bnode_split()
347 node_desc.next = cpu_to_be32(node->next); in hfs_bnode_split()
348 node_desc.num_recs = cpu_to_be16(node->num_recs); in hfs_bnode_split()
349 hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc)); in hfs_bnode_split()
358 } else if (node->this == tree->leaf_tail) { in hfs_bnode_split()
359 /* if there is no next node, this might be the new tail */ in hfs_bnode_split()
364 hfs_bnode_dump(node); in hfs_bnode_split()
366 hfs_bnode_put(node); in hfs_bnode_split()
374 struct hfs_bnode *node, *new_node, *parent; in hfs_brec_update_parent() local
380 node = fd->bnode; in hfs_brec_update_parent()
382 if (!node->parent) in hfs_brec_update_parent()
386 parent = hfs_bnode_find(tree, node->parent); in hfs_brec_update_parent()
397 newkeylen = (hfs_bnode_read_u8(node, 14) | 1) + 1; in hfs_brec_update_parent()
412 printk(KERN_DEBUG "splitting index node...\n"); in hfs_brec_update_parent()
436 hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen); in hfs_brec_update_parent()
441 hfs_bnode_put(node); in hfs_brec_update_parent()
442 node = parent; in hfs_brec_update_parent()
462 if (new_node == node) in hfs_brec_update_parent()
465 hfs_bnode_read_key(node, fd->search_key, 14); in hfs_brec_update_parent()
470 if (!rec && node->parent) in hfs_brec_update_parent()
473 fd->bnode = node; in hfs_brec_update_parent()
479 struct hfs_bnode *node, *new_node; in hfs_btree_inc_height() local
484 node = NULL; in hfs_btree_inc_height()
486 node = hfs_bnode_find(tree, tree->root); in hfs_btree_inc_height()
487 if (IS_ERR(node)) in hfs_btree_inc_height()
488 return PTR_ERR(node); in hfs_btree_inc_height()
492 hfs_bnode_put(node); in hfs_btree_inc_height()
521 if (node) { in hfs_btree_inc_height()
523 node->parent = tree->root; in hfs_btree_inc_height()
524 if (node->type == HFS_NODE_LEAF || in hfs_btree_inc_height()
526 key_size = hfs_bnode_read_u8(node, 14) + 1; in hfs_btree_inc_height()
529 hfs_bnode_copy(new_node, 14, node, 14, key_size); in hfs_btree_inc_height()
536 cnid = cpu_to_be32(node->this); in hfs_btree_inc_height()
542 hfs_bnode_put(node); in hfs_btree_inc_height()