2 * linux/fs/hfsplus/brec.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle individual btree records
11 #include "hfsplus_fs.h"
12 #include "hfsplus_raw.h"
14 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
);
15 static int hfs_brec_update_parent(struct hfs_find_data
*fd
);
16 static int hfs_btree_inc_height(struct hfs_btree
*);
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
)
24 dataoff
= node
->tree
->node_size
- (rec
+ 2) * 2;
25 hfs_bnode_read(node
, retval
, dataoff
, 4);
26 *off
= be16_to_cpu(retval
[1]);
27 return be16_to_cpu(retval
[0]) - *off
;
30 /* Get the length of the key from a keyed record */
31 u16
hfs_brec_keylen(struct hfs_bnode
*node
, u16 rec
)
35 if (node
->type
!= HFS_NODE_INDEX
&& node
->type
!= HFS_NODE_LEAF
)
38 if ((node
->type
== HFS_NODE_INDEX
) &&
39 !(node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
40 retval
= node
->tree
->max_key_len
+ 2;
42 recoff
= hfs_bnode_read_u16(node
, node
->tree
->node_size
- (rec
+ 1) * 2);
45 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
)
46 retval
= hfs_bnode_read_u16(node
, recoff
) + 2;
48 retval
= (hfs_bnode_read_u8(node
, recoff
) | 1) + 1;
53 int hfs_brec_insert(struct hfs_find_data
*fd
, void *entry
, int entry_len
)
55 struct hfs_btree
*tree
;
56 struct hfs_bnode
*node
, *new_node
;
57 int size
, key_len
, rec
;
58 int data_off
, end_off
;
59 int idx_rec_off
, data_rec_off
, end_rec_off
;
65 hfs_btree_inc_height(tree
);
66 fd
->bnode
= hfs_bnode_find(tree
, tree
->leaf_head
);
67 if (IS_ERR(fd
->bnode
))
68 return PTR_ERR(fd
->bnode
);
72 key_len
= be16_to_cpu(fd
->search_key
->key_len
) + 2;
74 /* new record idx and complete record size */
76 size
= key_len
+ entry_len
;
81 end_rec_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
82 end_off
= hfs_bnode_read_u16(node
, end_rec_off
);
84 dprint(DBG_BNODE_MOD
, "insert_rec: %d, %d, %d, %d\n", rec
, size
, end_off
, end_rec_off
);
85 if (size
> end_rec_off
- end_off
) {
87 panic("not enough room!\n");
88 new_node
= hfs_bnode_split(fd
);
90 return PTR_ERR(new_node
);
93 if (node
->type
== HFS_NODE_LEAF
) {
95 mark_inode_dirty(tree
->inode
);
98 /* write new last offset */
99 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
100 hfs_bnode_write_u16(node
, end_rec_off
, end_off
+ size
);
102 data_rec_off
= end_rec_off
+ 2;
103 idx_rec_off
= tree
->node_size
- (rec
+ 1) * 2;
104 if (idx_rec_off
== data_rec_off
)
106 /* move all following entries */
108 data_off
= hfs_bnode_read_u16(node
, data_rec_off
+ 2);
109 hfs_bnode_write_u16(node
, data_rec_off
, data_off
+ size
);
111 } while (data_rec_off
< idx_rec_off
);
114 hfs_bnode_move(node
, data_off
+ size
, data_off
,
118 hfs_bnode_write(node
, fd
->search_key
, data_off
, key_len
);
119 hfs_bnode_write(node
, entry
, data_off
+ key_len
, entry_len
);
120 hfs_bnode_dump(node
);
123 /* update parent key if we inserted a key
124 * at the start of the first node
126 if (!rec
&& new_node
!= node
)
127 hfs_brec_update_parent(fd
);
129 hfs_bnode_put(fd
->bnode
);
130 if (!new_node
->parent
) {
131 hfs_btree_inc_height(tree
);
132 new_node
->parent
= tree
->root
;
134 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
136 /* create index data entry */
137 cnid
= cpu_to_be32(new_node
->this);
139 entry_len
= sizeof(cnid
);
142 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
143 __hfs_brec_find(fd
->bnode
, fd
);
145 hfs_bnode_put(new_node
);
148 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
149 key_len
= be16_to_cpu(fd
->search_key
->key_len
) + 2;
151 fd
->search_key
->key_len
= cpu_to_be16(tree
->max_key_len
);
152 key_len
= tree
->max_key_len
+ 2;
158 hfs_brec_update_parent(fd
);
163 int hfs_brec_remove(struct hfs_find_data
*fd
)
165 struct hfs_btree
*tree
;
166 struct hfs_bnode
*node
, *parent
;
167 int end_off
, rec_off
, data_off
, size
;
172 rec_off
= tree
->node_size
- (fd
->record
+ 2) * 2;
173 end_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
175 if (node
->type
== HFS_NODE_LEAF
) {
177 mark_inode_dirty(tree
->inode
);
179 hfs_bnode_dump(node
);
180 dprint(DBG_BNODE_MOD
, "remove_rec: %d, %d\n", fd
->record
, fd
->keylength
+ fd
->entrylength
);
181 if (!--node
->num_recs
) {
182 hfs_bnode_unlink(node
);
185 parent
= hfs_bnode_find(tree
, node
->parent
);
187 return PTR_ERR(parent
);
189 node
= fd
->bnode
= parent
;
191 __hfs_brec_find(node
, fd
);
194 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
196 if (rec_off
== end_off
)
198 size
= fd
->keylength
+ fd
->entrylength
;
201 data_off
= hfs_bnode_read_u16(node
, rec_off
);
202 hfs_bnode_write_u16(node
, rec_off
+ 2, data_off
- size
);
204 } while (rec_off
>= end_off
);
207 hfs_bnode_move(node
, fd
->keyoffset
, fd
->keyoffset
+ size
,
208 data_off
- fd
->keyoffset
- size
);
210 hfs_bnode_dump(node
);
212 hfs_brec_update_parent(fd
);
216 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
)
218 struct hfs_btree
*tree
;
219 struct hfs_bnode
*node
, *new_node
;
220 struct hfs_bnode_desc node_desc
;
221 int num_recs
, new_rec_off
, new_off
, old_rec_off
;
222 int data_start
, data_end
, size
;
226 new_node
= hfs_bmap_alloc(tree
);
227 if (IS_ERR(new_node
))
230 dprint(DBG_BNODE_MOD
, "split_nodes: %d - %d - %d\n",
231 node
->this, new_node
->this, node
->next
);
232 new_node
->next
= node
->next
;
233 new_node
->prev
= node
->this;
234 new_node
->parent
= node
->parent
;
235 new_node
->type
= node
->type
;
236 new_node
->height
= node
->height
;
238 size
= tree
->node_size
/ 2 - node
->num_recs
* 2 - 14;
239 old_rec_off
= tree
->node_size
- 4;
242 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
243 if (data_start
> size
)
246 if (++num_recs
< node
->num_recs
)
250 hfs_bnode_put(new_node
);
251 return ERR_PTR(-ENOSPC
);
254 if (fd
->record
+ 1 < num_recs
) {
255 /* new record is in the lower half,
256 * so leave some more space there
260 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
263 hfs_bnode_get(new_node
);
264 fd
->bnode
= new_node
;
265 fd
->record
-= num_recs
;
266 fd
->keyoffset
-= data_start
- 14;
267 fd
->entryoffset
-= data_start
- 14;
269 new_node
->num_recs
= node
->num_recs
- num_recs
;
270 node
->num_recs
= num_recs
;
272 new_rec_off
= tree
->node_size
- 2;
274 size
= data_start
- new_off
;
275 num_recs
= new_node
->num_recs
;
276 data_end
= data_start
;
278 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
281 data_end
= hfs_bnode_read_u16(node
, old_rec_off
);
282 new_off
= data_end
- size
;
285 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
286 hfs_bnode_copy(new_node
, 14, node
, data_start
, data_end
- data_start
);
288 /* update new bnode header */
289 node_desc
.next
= cpu_to_be32(new_node
->next
);
290 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
291 node_desc
.type
= new_node
->type
;
292 node_desc
.height
= new_node
->height
;
293 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
294 node_desc
.reserved
= 0;
295 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
297 /* update previous bnode header */
298 node
->next
= new_node
->this;
299 hfs_bnode_read(node
, &node_desc
, 0, sizeof(node_desc
));
300 node_desc
.next
= cpu_to_be32(node
->next
);
301 node_desc
.num_recs
= cpu_to_be16(node
->num_recs
);
302 hfs_bnode_write(node
, &node_desc
, 0, sizeof(node_desc
));
304 /* update next bnode header */
305 if (new_node
->next
) {
306 struct hfs_bnode
*next_node
= hfs_bnode_find(tree
, new_node
->next
);
307 next_node
->prev
= new_node
->this;
308 hfs_bnode_read(next_node
, &node_desc
, 0, sizeof(node_desc
));
309 node_desc
.prev
= cpu_to_be32(next_node
->prev
);
310 hfs_bnode_write(next_node
, &node_desc
, 0, sizeof(node_desc
));
311 hfs_bnode_put(next_node
);
312 } else if (node
->this == tree
->leaf_tail
) {
313 /* if there is no next node, this might be the new tail */
314 tree
->leaf_tail
= new_node
->this;
315 mark_inode_dirty(tree
->inode
);
318 hfs_bnode_dump(node
);
319 hfs_bnode_dump(new_node
);
325 static int hfs_brec_update_parent(struct hfs_find_data
*fd
)
327 struct hfs_btree
*tree
;
328 struct hfs_bnode
*node
, *new_node
, *parent
;
330 int rec
, rec_off
, end_rec_off
;
331 int start_off
, end_off
;
340 parent
= hfs_bnode_find(tree
, node
->parent
);
342 return PTR_ERR(parent
);
343 __hfs_brec_find(parent
, fd
);
344 hfs_bnode_dump(parent
);
347 /* size difference between old and new key */
348 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
349 newkeylen
= hfs_bnode_read_u16(node
, 14) + 2;
351 fd
->keylength
= newkeylen
= tree
->max_key_len
+ 2;
352 dprint(DBG_BNODE_MOD
, "update_rec: %d, %d, %d\n", rec
, fd
->keylength
, newkeylen
);
354 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
355 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
356 diff
= newkeylen
- fd
->keylength
;
360 end_off
= hfs_bnode_read_u16(parent
, end_rec_off
);
361 if (end_rec_off
- end_off
< diff
) {
363 printk(KERN_DEBUG
"hfs: splitting index node...\n");
365 new_node
= hfs_bnode_split(fd
);
366 if (IS_ERR(new_node
))
367 return PTR_ERR(new_node
);
370 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
371 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
375 end_off
= start_off
= hfs_bnode_read_u16(parent
, rec_off
);
376 hfs_bnode_write_u16(parent
, rec_off
, start_off
+ diff
);
377 start_off
-= 4; /* move previous cnid too */
379 while (rec_off
> end_rec_off
) {
381 end_off
= hfs_bnode_read_u16(parent
, rec_off
);
382 hfs_bnode_write_u16(parent
, rec_off
, end_off
+ diff
);
384 hfs_bnode_move(parent
, start_off
+ diff
, start_off
,
385 end_off
- start_off
);
387 hfs_bnode_copy(parent
, fd
->keyoffset
, node
, 14, newkeylen
);
388 hfs_bnode_dump(parent
);
396 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
397 /* create index key and entry */
398 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
399 cnid
= cpu_to_be32(new_node
->this);
401 __hfs_brec_find(fd
->bnode
, fd
);
402 hfs_brec_insert(fd
, &cnid
, sizeof(cnid
));
403 hfs_bnode_put(fd
->bnode
);
404 hfs_bnode_put(new_node
);
407 if (new_node
== node
)
409 /* restore search_key */
410 hfs_bnode_read_key(node
, fd
->search_key
, 14);
414 if (!rec
&& node
->parent
)
421 static int hfs_btree_inc_height(struct hfs_btree
*tree
)
423 struct hfs_bnode
*node
, *new_node
;
424 struct hfs_bnode_desc node_desc
;
430 node
= hfs_bnode_find(tree
, tree
->root
);
432 return PTR_ERR(node
);
434 new_node
= hfs_bmap_alloc(tree
);
435 if (IS_ERR(new_node
)) {
437 return PTR_ERR(new_node
);
440 tree
->root
= new_node
->this;
442 tree
->leaf_head
= tree
->leaf_tail
= new_node
->this;
443 new_node
->type
= HFS_NODE_LEAF
;
444 new_node
->num_recs
= 0;
446 new_node
->type
= HFS_NODE_INDEX
;
447 new_node
->num_recs
= 1;
449 new_node
->parent
= 0;
452 new_node
->height
= ++tree
->depth
;
454 node_desc
.next
= cpu_to_be32(new_node
->next
);
455 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
456 node_desc
.type
= new_node
->type
;
457 node_desc
.height
= new_node
->height
;
458 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
459 node_desc
.reserved
= 0;
460 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
462 rec
= tree
->node_size
- 2;
463 hfs_bnode_write_u16(new_node
, rec
, 14);
466 /* insert old root idx into new root */
467 node
->parent
= tree
->root
;
468 if (node
->type
== HFS_NODE_LEAF
||
469 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
470 key_size
= hfs_bnode_read_u16(node
, 14) + 2;
472 key_size
= tree
->max_key_len
+ 2;
473 hfs_bnode_copy(new_node
, 14, node
, 14, key_size
);
475 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
476 key_size
= tree
->max_key_len
+ 2;
477 hfs_bnode_write_u16(new_node
, 14, tree
->max_key_len
);
479 cnid
= cpu_to_be32(node
->this);
480 hfs_bnode_write(new_node
, &cnid
, 14 + key_size
, 4);
483 hfs_bnode_write_u16(new_node
, rec
, 14 + key_size
+ 4);
487 hfs_bnode_put(new_node
);
488 mark_inode_dirty(tree
->inode
);
This page took 0.04058 seconds and 5 git commands to generate.