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
,
43 node
->tree
->node_size
- (rec
+ 1) * 2);
47 retval
= hfs_bnode_read_u16(node
, recoff
) + 2;
48 if (retval
> node
->tree
->max_key_len
+ 2) {
49 printk(KERN_ERR
"hfs: keylen %d too large\n",
57 int hfs_brec_insert(struct hfs_find_data
*fd
, void *entry
, int entry_len
)
59 struct hfs_btree
*tree
;
60 struct hfs_bnode
*node
, *new_node
;
61 int size
, key_len
, rec
;
62 int data_off
, end_off
;
63 int idx_rec_off
, data_rec_off
, end_rec_off
;
69 hfs_btree_inc_height(tree
);
70 fd
->bnode
= hfs_bnode_find(tree
, tree
->leaf_head
);
71 if (IS_ERR(fd
->bnode
))
72 return PTR_ERR(fd
->bnode
);
76 key_len
= be16_to_cpu(fd
->search_key
->key_len
) + 2;
78 /* new record idx and complete record size */
80 size
= key_len
+ entry_len
;
85 end_rec_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
86 end_off
= hfs_bnode_read_u16(node
, end_rec_off
);
88 dprint(DBG_BNODE_MOD
, "insert_rec: %d, %d, %d, %d\n",
89 rec
, size
, end_off
, end_rec_off
);
90 if (size
> end_rec_off
- end_off
) {
92 panic("not enough room!\n");
93 new_node
= hfs_bnode_split(fd
);
95 return PTR_ERR(new_node
);
98 if (node
->type
== HFS_NODE_LEAF
) {
100 mark_inode_dirty(tree
->inode
);
103 /* write new last offset */
104 hfs_bnode_write_u16(node
,
105 offsetof(struct hfs_bnode_desc
, num_recs
),
107 hfs_bnode_write_u16(node
, end_rec_off
, end_off
+ size
);
109 data_rec_off
= end_rec_off
+ 2;
110 idx_rec_off
= tree
->node_size
- (rec
+ 1) * 2;
111 if (idx_rec_off
== data_rec_off
)
113 /* move all following entries */
115 data_off
= hfs_bnode_read_u16(node
, data_rec_off
+ 2);
116 hfs_bnode_write_u16(node
, data_rec_off
, data_off
+ size
);
118 } while (data_rec_off
< idx_rec_off
);
121 hfs_bnode_move(node
, data_off
+ size
, data_off
,
125 hfs_bnode_write(node
, fd
->search_key
, data_off
, key_len
);
126 hfs_bnode_write(node
, entry
, data_off
+ key_len
, entry_len
);
127 hfs_bnode_dump(node
);
130 /* update parent key if we inserted a key
131 * at the start of the first node
133 if (!rec
&& new_node
!= node
)
134 hfs_brec_update_parent(fd
);
136 hfs_bnode_put(fd
->bnode
);
137 if (!new_node
->parent
) {
138 hfs_btree_inc_height(tree
);
139 new_node
->parent
= tree
->root
;
141 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
143 /* create index data entry */
144 cnid
= cpu_to_be32(new_node
->this);
146 entry_len
= sizeof(cnid
);
149 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
150 __hfs_brec_find(fd
->bnode
, fd
);
152 hfs_bnode_put(new_node
);
155 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
156 key_len
= be16_to_cpu(fd
->search_key
->key_len
) + 2;
158 fd
->search_key
->key_len
=
159 cpu_to_be16(tree
->max_key_len
);
160 key_len
= tree
->max_key_len
+ 2;
166 hfs_brec_update_parent(fd
);
171 int hfs_brec_remove(struct hfs_find_data
*fd
)
173 struct hfs_btree
*tree
;
174 struct hfs_bnode
*node
, *parent
;
175 int end_off
, rec_off
, data_off
, size
;
180 rec_off
= tree
->node_size
- (fd
->record
+ 2) * 2;
181 end_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
183 if (node
->type
== HFS_NODE_LEAF
) {
185 mark_inode_dirty(tree
->inode
);
187 hfs_bnode_dump(node
);
188 dprint(DBG_BNODE_MOD
, "remove_rec: %d, %d\n",
189 fd
->record
, fd
->keylength
+ fd
->entrylength
);
190 if (!--node
->num_recs
) {
191 hfs_bnode_unlink(node
);
194 parent
= hfs_bnode_find(tree
, node
->parent
);
196 return PTR_ERR(parent
);
198 node
= fd
->bnode
= parent
;
200 __hfs_brec_find(node
, fd
);
203 hfs_bnode_write_u16(node
,
204 offsetof(struct hfs_bnode_desc
, num_recs
),
207 if (rec_off
== end_off
)
209 size
= fd
->keylength
+ fd
->entrylength
;
212 data_off
= hfs_bnode_read_u16(node
, rec_off
);
213 hfs_bnode_write_u16(node
, rec_off
+ 2, data_off
- size
);
215 } while (rec_off
>= end_off
);
218 hfs_bnode_move(node
, fd
->keyoffset
, fd
->keyoffset
+ size
,
219 data_off
- fd
->keyoffset
- size
);
221 hfs_bnode_dump(node
);
223 hfs_brec_update_parent(fd
);
227 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
)
229 struct hfs_btree
*tree
;
230 struct hfs_bnode
*node
, *new_node
, *next_node
;
231 struct hfs_bnode_desc node_desc
;
232 int num_recs
, new_rec_off
, new_off
, old_rec_off
;
233 int data_start
, data_end
, size
;
237 new_node
= hfs_bmap_alloc(tree
);
238 if (IS_ERR(new_node
))
241 dprint(DBG_BNODE_MOD
, "split_nodes: %d - %d - %d\n",
242 node
->this, new_node
->this, node
->next
);
243 new_node
->next
= node
->next
;
244 new_node
->prev
= node
->this;
245 new_node
->parent
= node
->parent
;
246 new_node
->type
= node
->type
;
247 new_node
->height
= node
->height
;
250 next_node
= hfs_bnode_find(tree
, node
->next
);
254 if (IS_ERR(next_node
)) {
256 hfs_bnode_put(new_node
);
260 size
= tree
->node_size
/ 2 - node
->num_recs
* 2 - 14;
261 old_rec_off
= tree
->node_size
- 4;
264 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
265 if (data_start
> size
)
268 if (++num_recs
< node
->num_recs
)
272 hfs_bnode_put(new_node
);
274 hfs_bnode_put(next_node
);
275 return ERR_PTR(-ENOSPC
);
278 if (fd
->record
+ 1 < num_recs
) {
279 /* new record is in the lower half,
280 * so leave some more space there
284 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
287 hfs_bnode_get(new_node
);
288 fd
->bnode
= new_node
;
289 fd
->record
-= num_recs
;
290 fd
->keyoffset
-= data_start
- 14;
291 fd
->entryoffset
-= data_start
- 14;
293 new_node
->num_recs
= node
->num_recs
- num_recs
;
294 node
->num_recs
= num_recs
;
296 new_rec_off
= tree
->node_size
- 2;
298 size
= data_start
- new_off
;
299 num_recs
= new_node
->num_recs
;
300 data_end
= data_start
;
302 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
305 data_end
= hfs_bnode_read_u16(node
, old_rec_off
);
306 new_off
= data_end
- size
;
309 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
310 hfs_bnode_copy(new_node
, 14, node
, data_start
, data_end
- data_start
);
312 /* update new bnode header */
313 node_desc
.next
= cpu_to_be32(new_node
->next
);
314 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
315 node_desc
.type
= new_node
->type
;
316 node_desc
.height
= new_node
->height
;
317 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
318 node_desc
.reserved
= 0;
319 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
321 /* update previous bnode header */
322 node
->next
= new_node
->this;
323 hfs_bnode_read(node
, &node_desc
, 0, sizeof(node_desc
));
324 node_desc
.next
= cpu_to_be32(node
->next
);
325 node_desc
.num_recs
= cpu_to_be16(node
->num_recs
);
326 hfs_bnode_write(node
, &node_desc
, 0, sizeof(node_desc
));
328 /* update next bnode header */
330 next_node
->prev
= new_node
->this;
331 hfs_bnode_read(next_node
, &node_desc
, 0, sizeof(node_desc
));
332 node_desc
.prev
= cpu_to_be32(next_node
->prev
);
333 hfs_bnode_write(next_node
, &node_desc
, 0, sizeof(node_desc
));
334 hfs_bnode_put(next_node
);
335 } else if (node
->this == tree
->leaf_tail
) {
336 /* if there is no next node, this might be the new tail */
337 tree
->leaf_tail
= new_node
->this;
338 mark_inode_dirty(tree
->inode
);
341 hfs_bnode_dump(node
);
342 hfs_bnode_dump(new_node
);
348 static int hfs_brec_update_parent(struct hfs_find_data
*fd
)
350 struct hfs_btree
*tree
;
351 struct hfs_bnode
*node
, *new_node
, *parent
;
353 int rec
, rec_off
, end_rec_off
;
354 int start_off
, end_off
;
363 parent
= hfs_bnode_find(tree
, node
->parent
);
365 return PTR_ERR(parent
);
366 __hfs_brec_find(parent
, fd
);
367 hfs_bnode_dump(parent
);
370 /* size difference between old and new key */
371 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
372 newkeylen
= hfs_bnode_read_u16(node
, 14) + 2;
374 fd
->keylength
= newkeylen
= tree
->max_key_len
+ 2;
375 dprint(DBG_BNODE_MOD
, "update_rec: %d, %d, %d\n",
376 rec
, fd
->keylength
, newkeylen
);
378 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
379 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
380 diff
= newkeylen
- fd
->keylength
;
384 end_off
= hfs_bnode_read_u16(parent
, end_rec_off
);
385 if (end_rec_off
- end_off
< diff
) {
387 dprint(DBG_BNODE_MOD
, "hfs: splitting index node.\n");
389 new_node
= hfs_bnode_split(fd
);
390 if (IS_ERR(new_node
))
391 return PTR_ERR(new_node
);
394 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
395 end_rec_off
= tree
->node_size
-
396 (parent
->num_recs
+ 1) * 2;
400 end_off
= start_off
= hfs_bnode_read_u16(parent
, rec_off
);
401 hfs_bnode_write_u16(parent
, rec_off
, start_off
+ diff
);
402 start_off
-= 4; /* move previous cnid too */
404 while (rec_off
> end_rec_off
) {
406 end_off
= hfs_bnode_read_u16(parent
, rec_off
);
407 hfs_bnode_write_u16(parent
, rec_off
, end_off
+ diff
);
409 hfs_bnode_move(parent
, start_off
+ diff
, start_off
,
410 end_off
- start_off
);
412 hfs_bnode_copy(parent
, fd
->keyoffset
, node
, 14, newkeylen
);
413 hfs_bnode_dump(parent
);
421 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
422 /* create index key and entry */
423 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
424 cnid
= cpu_to_be32(new_node
->this);
426 __hfs_brec_find(fd
->bnode
, fd
);
427 hfs_brec_insert(fd
, &cnid
, sizeof(cnid
));
428 hfs_bnode_put(fd
->bnode
);
429 hfs_bnode_put(new_node
);
432 if (new_node
== node
)
434 /* restore search_key */
435 hfs_bnode_read_key(node
, fd
->search_key
, 14);
439 if (!rec
&& node
->parent
)
446 static int hfs_btree_inc_height(struct hfs_btree
*tree
)
448 struct hfs_bnode
*node
, *new_node
;
449 struct hfs_bnode_desc node_desc
;
455 node
= hfs_bnode_find(tree
, tree
->root
);
457 return PTR_ERR(node
);
459 new_node
= hfs_bmap_alloc(tree
);
460 if (IS_ERR(new_node
)) {
462 return PTR_ERR(new_node
);
465 tree
->root
= new_node
->this;
467 tree
->leaf_head
= tree
->leaf_tail
= new_node
->this;
468 new_node
->type
= HFS_NODE_LEAF
;
469 new_node
->num_recs
= 0;
471 new_node
->type
= HFS_NODE_INDEX
;
472 new_node
->num_recs
= 1;
474 new_node
->parent
= 0;
477 new_node
->height
= ++tree
->depth
;
479 node_desc
.next
= cpu_to_be32(new_node
->next
);
480 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
481 node_desc
.type
= new_node
->type
;
482 node_desc
.height
= new_node
->height
;
483 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
484 node_desc
.reserved
= 0;
485 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
487 rec
= tree
->node_size
- 2;
488 hfs_bnode_write_u16(new_node
, rec
, 14);
491 /* insert old root idx into new root */
492 node
->parent
= tree
->root
;
493 if (node
->type
== HFS_NODE_LEAF
||
494 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
495 key_size
= hfs_bnode_read_u16(node
, 14) + 2;
497 key_size
= tree
->max_key_len
+ 2;
498 hfs_bnode_copy(new_node
, 14, node
, 14, key_size
);
500 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
501 key_size
= tree
->max_key_len
+ 2;
502 hfs_bnode_write_u16(new_node
, 14, tree
->max_key_len
);
504 cnid
= cpu_to_be32(node
->this);
505 hfs_bnode_write(new_node
, &cnid
, 14 + key_size
, 4);
508 hfs_bnode_write_u16(new_node
, rec
, 14 + key_size
+ 4);
512 hfs_bnode_put(new_node
);
513 mark_inode_dirty(tree
->inode
);