5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle individual btree records
13 /* Get the length and offset of the given record in the given node */
14 u16
hfs_brec_lenoff(struct hfs_bnode
*node
, u16 rec
, u16
*off
)
19 dataoff
= node
->tree
->node_size
- (rec
+ 2) * 2;
20 hfs_bnode_read(node
, retval
, dataoff
, 4);
21 *off
= be16_to_cpu(retval
[1]);
22 return be16_to_cpu(retval
[0]) - *off
;
25 /* Get the length of the key from a keyed record */
26 u16
hfs_brec_keylen(struct hfs_bnode
*node
, u16 rec
)
30 if (node
->type
!= HFS_NODE_INDEX
&& node
->type
!= HFS_NODE_LEAF
)
33 if ((node
->type
== HFS_NODE_INDEX
) &&
34 !(node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
35 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
)
36 retval
= node
->tree
->max_key_len
+ 2;
38 retval
= node
->tree
->max_key_len
+ 1;
40 recoff
= hfs_bnode_read_u16(node
, node
->tree
->node_size
- (rec
+ 1) * 2);
43 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
)
44 retval
= hfs_bnode_read_u16(node
, recoff
) + 2;
46 retval
= (hfs_bnode_read_u8(node
, recoff
) | 1) + 1;
51 int hfs_brec_insert(struct hfs_find_data
*fd
, void *entry
, int entry_len
)
53 struct hfs_btree
*tree
;
54 struct hfs_bnode
*node
, *new_node
;
55 int size
, key_len
, rec
;
56 int data_off
, end_off
;
57 int idx_rec_off
, data_rec_off
, end_rec_off
;
63 hfs_btree_inc_height(tree
);
64 fd
->bnode
= hfs_bnode_find(tree
, tree
->leaf_head
);
65 if (IS_ERR(fd
->bnode
))
66 return PTR_ERR(fd
->bnode
);
70 key_len
= (fd
->search_key
->key_len
| 1) + 1;
72 /* new record idx and complete record size */
74 size
= key_len
+ entry_len
;
79 end_rec_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
80 end_off
= hfs_bnode_read_u16(node
, end_rec_off
);
82 dprint(DBG_BNODE_MOD
, "insert_rec: %d, %d, %d, %d\n", rec
, size
, end_off
, end_rec_off
);
83 if (size
> end_rec_off
- end_off
) {
85 panic("not enough room!\n");
86 new_node
= hfs_bnode_split(fd
);
88 return PTR_ERR(new_node
);
91 if (node
->type
== HFS_NODE_LEAF
) {
93 mark_inode_dirty(tree
->inode
);
96 /* write new last offset */
97 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
98 hfs_bnode_write_u16(node
, end_rec_off
, end_off
+ size
);
100 data_rec_off
= end_rec_off
+ 2;
101 idx_rec_off
= tree
->node_size
- (rec
+ 1) * 2;
102 if (idx_rec_off
== data_rec_off
)
104 /* move all following entries */
106 data_off
= hfs_bnode_read_u16(node
, data_rec_off
+ 2);
107 hfs_bnode_write_u16(node
, data_rec_off
, data_off
+ size
);
109 } while (data_rec_off
< idx_rec_off
);
112 hfs_bnode_move(node
, data_off
+ size
, data_off
,
116 hfs_bnode_write(node
, fd
->search_key
, data_off
, key_len
);
117 hfs_bnode_write(node
, entry
, data_off
+ key_len
, entry_len
);
118 hfs_bnode_dump(node
);
121 /* update parent key if we inserted a key
122 * at the start of the first node
124 if (!rec
&& new_node
!= node
)
125 hfs_brec_update_parent(fd
);
127 hfs_bnode_put(fd
->bnode
);
128 if (!new_node
->parent
) {
129 hfs_btree_inc_height(tree
);
130 new_node
->parent
= tree
->root
;
132 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
134 /* create index data entry */
135 cnid
= cpu_to_be32(new_node
->this);
137 entry_len
= sizeof(cnid
);
140 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
141 __hfs_brec_find(fd
->bnode
, fd
);
143 hfs_bnode_put(new_node
);
146 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
147 key_len
= fd
->search_key
->key_len
+ 1;
149 fd
->search_key
->key_len
= tree
->max_key_len
;
150 key_len
= tree
->max_key_len
+ 1;
156 hfs_brec_update_parent(fd
);
161 int hfs_brec_remove(struct hfs_find_data
*fd
)
163 struct hfs_btree
*tree
;
164 struct hfs_bnode
*node
, *parent
;
165 int end_off
, rec_off
, data_off
, size
;
170 rec_off
= tree
->node_size
- (fd
->record
+ 2) * 2;
171 end_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
173 if (node
->type
== HFS_NODE_LEAF
) {
175 mark_inode_dirty(tree
->inode
);
177 hfs_bnode_dump(node
);
178 dprint(DBG_BNODE_MOD
, "remove_rec: %d, %d\n", fd
->record
, fd
->keylength
+ fd
->entrylength
);
179 if (!--node
->num_recs
) {
180 hfs_bnode_unlink(node
);
183 parent
= hfs_bnode_find(tree
, node
->parent
);
185 return PTR_ERR(parent
);
187 node
= fd
->bnode
= parent
;
189 __hfs_brec_find(node
, fd
);
192 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
194 if (rec_off
== end_off
)
196 size
= fd
->keylength
+ fd
->entrylength
;
199 data_off
= hfs_bnode_read_u16(node
, rec_off
);
200 hfs_bnode_write_u16(node
, rec_off
+ 2, data_off
- size
);
202 } while (rec_off
>= end_off
);
205 hfs_bnode_move(node
, fd
->keyoffset
, fd
->keyoffset
+ size
,
206 data_off
- fd
->keyoffset
- size
);
208 hfs_bnode_dump(node
);
210 hfs_brec_update_parent(fd
);
214 struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
)
216 struct hfs_btree
*tree
;
217 struct hfs_bnode
*node
, *new_node
;
218 struct hfs_bnode_desc node_desc
;
219 int num_recs
, new_rec_off
, new_off
, old_rec_off
;
220 int data_start
, data_end
, size
;
224 new_node
= hfs_bmap_alloc(tree
);
225 if (IS_ERR(new_node
))
228 dprint(DBG_BNODE_MOD
, "split_nodes: %d - %d - %d\n",
229 node
->this, new_node
->this, node
->next
);
230 new_node
->next
= node
->next
;
231 new_node
->prev
= node
->this;
232 new_node
->parent
= node
->parent
;
233 new_node
->type
= node
->type
;
234 new_node
->height
= node
->height
;
236 size
= tree
->node_size
/ 2 - node
->num_recs
* 2 - 14;
237 old_rec_off
= tree
->node_size
- 4;
240 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
241 if (data_start
> size
)
244 if (++num_recs
< node
->num_recs
)
248 hfs_bnode_put(new_node
);
249 return ERR_PTR(-ENOSPC
);
252 if (fd
->record
+ 1 < num_recs
) {
253 /* new record is in the lower half,
254 * so leave some more space there
258 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
261 hfs_bnode_get(new_node
);
262 fd
->bnode
= new_node
;
263 fd
->record
-= num_recs
;
264 fd
->keyoffset
-= data_start
- 14;
265 fd
->entryoffset
-= data_start
- 14;
267 new_node
->num_recs
= node
->num_recs
- num_recs
;
268 node
->num_recs
= num_recs
;
270 new_rec_off
= tree
->node_size
- 2;
272 size
= data_start
- new_off
;
273 num_recs
= new_node
->num_recs
;
274 data_end
= data_start
;
276 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
279 data_end
= hfs_bnode_read_u16(node
, old_rec_off
);
280 new_off
= data_end
- size
;
283 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
284 hfs_bnode_copy(new_node
, 14, node
, data_start
, data_end
- data_start
);
286 /* update new bnode header */
287 node_desc
.next
= cpu_to_be32(new_node
->next
);
288 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
289 node_desc
.type
= new_node
->type
;
290 node_desc
.height
= new_node
->height
;
291 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
292 node_desc
.reserved
= 0;
293 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
295 /* update previous bnode header */
296 node
->next
= new_node
->this;
297 hfs_bnode_read(node
, &node_desc
, 0, sizeof(node_desc
));
298 node_desc
.next
= cpu_to_be32(node
->next
);
299 node_desc
.num_recs
= cpu_to_be16(node
->num_recs
);
300 hfs_bnode_write(node
, &node_desc
, 0, sizeof(node_desc
));
302 /* update next bnode header */
303 if (new_node
->next
) {
304 struct hfs_bnode
*next_node
= hfs_bnode_find(tree
, new_node
->next
);
305 next_node
->prev
= new_node
->this;
306 hfs_bnode_read(next_node
, &node_desc
, 0, sizeof(node_desc
));
307 node_desc
.prev
= cpu_to_be32(next_node
->prev
);
308 hfs_bnode_write(next_node
, &node_desc
, 0, sizeof(node_desc
));
309 hfs_bnode_put(next_node
);
310 } else if (node
->this == tree
->leaf_tail
) {
311 /* if there is no next node, this might be the new tail */
312 tree
->leaf_tail
= new_node
->this;
313 mark_inode_dirty(tree
->inode
);
316 hfs_bnode_dump(node
);
317 hfs_bnode_dump(new_node
);
323 int hfs_brec_update_parent(struct hfs_find_data
*fd
)
325 struct hfs_btree
*tree
;
326 struct hfs_bnode
*node
, *new_node
, *parent
;
328 int rec
, rec_off
, end_rec_off
;
329 int start_off
, end_off
;
338 parent
= hfs_bnode_find(tree
, node
->parent
);
340 return PTR_ERR(parent
);
341 __hfs_brec_find(parent
, fd
);
342 hfs_bnode_dump(parent
);
345 /* size difference between old and new key */
346 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
347 newkeylen
= (hfs_bnode_read_u8(node
, 14) | 1) + 1;
349 fd
->keylength
= newkeylen
= tree
->max_key_len
+ 1;
350 dprint(DBG_BNODE_MOD
, "update_rec: %d, %d, %d\n", rec
, fd
->keylength
, newkeylen
);
352 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
353 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
354 diff
= newkeylen
- fd
->keylength
;
358 end_off
= hfs_bnode_read_u16(parent
, end_rec_off
);
359 if (end_rec_off
- end_off
< diff
) {
361 printk("splitting index node...\n");
363 new_node
= hfs_bnode_split(fd
);
364 if (IS_ERR(new_node
))
365 return PTR_ERR(new_node
);
368 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
369 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
373 end_off
= start_off
= hfs_bnode_read_u16(parent
, rec_off
);
374 hfs_bnode_write_u16(parent
, rec_off
, start_off
+ diff
);
375 start_off
-= 4; /* move previous cnid too */
377 while (rec_off
> end_rec_off
) {
379 end_off
= hfs_bnode_read_u16(parent
, rec_off
);
380 hfs_bnode_write_u16(parent
, rec_off
, end_off
+ diff
);
382 hfs_bnode_move(parent
, start_off
+ diff
, start_off
,
383 end_off
- start_off
);
385 hfs_bnode_copy(parent
, fd
->keyoffset
, node
, 14, newkeylen
);
386 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
))
387 hfs_bnode_write_u8(parent
, fd
->keyoffset
, newkeylen
- 1);
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 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_u8(node
, 14) + 1;
472 key_size
= tree
->max_key_len
+ 1;
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
+ 1;
477 hfs_bnode_write_u8(new_node
, 14, tree
->max_key_len
);
479 key_size
= (key_size
+ 1) & -2;
480 cnid
= cpu_to_be32(node
->this);
481 hfs_bnode_write(new_node
, &cnid
, 14 + key_size
, 4);
484 hfs_bnode_write_u16(new_node
, rec
, 14 + key_size
+ 4);
488 hfs_bnode_put(new_node
);
489 mark_inode_dirty(tree
->inode
);