5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle individual btree records
13 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
);
14 static int hfs_brec_update_parent(struct hfs_find_data
*fd
);
15 static int hfs_btree_inc_height(struct hfs_btree
*tree
);
17 /* Get the length and offset of the given record in the given node */
18 u16
hfs_brec_lenoff(struct hfs_bnode
*node
, u16 rec
, u16
*off
)
23 dataoff
= node
->tree
->node_size
- (rec
+ 2) * 2;
24 hfs_bnode_read(node
, retval
, dataoff
, 4);
25 *off
= be16_to_cpu(retval
[1]);
26 return be16_to_cpu(retval
[0]) - *off
;
29 /* Get the length of the key from a keyed record */
30 u16
hfs_brec_keylen(struct hfs_bnode
*node
, u16 rec
)
34 if (node
->type
!= HFS_NODE_INDEX
&& node
->type
!= HFS_NODE_LEAF
)
37 if ((node
->type
== HFS_NODE_INDEX
) &&
38 !(node
->tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
39 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
)
40 retval
= node
->tree
->max_key_len
+ 2;
42 retval
= node
->tree
->max_key_len
+ 1;
44 recoff
= hfs_bnode_read_u16(node
, node
->tree
->node_size
- (rec
+ 1) * 2);
47 if (node
->tree
->attributes
& HFS_TREE_BIGKEYS
) {
48 retval
= hfs_bnode_read_u16(node
, recoff
) + 2;
49 if (retval
> node
->tree
->max_key_len
+ 2) {
50 printk(KERN_ERR
"hfs: keylen %d too large\n",
55 retval
= (hfs_bnode_read_u8(node
, recoff
) | 1) + 1;
56 if (retval
> node
->tree
->max_key_len
+ 1) {
57 printk(KERN_ERR
"hfs: keylen %d too large\n",
66 int hfs_brec_insert(struct hfs_find_data
*fd
, void *entry
, int entry_len
)
68 struct hfs_btree
*tree
;
69 struct hfs_bnode
*node
, *new_node
;
70 int size
, key_len
, rec
;
71 int data_off
, end_off
;
72 int idx_rec_off
, data_rec_off
, end_rec_off
;
78 hfs_btree_inc_height(tree
);
79 fd
->bnode
= hfs_bnode_find(tree
, tree
->leaf_head
);
80 if (IS_ERR(fd
->bnode
))
81 return PTR_ERR(fd
->bnode
);
85 key_len
= (fd
->search_key
->key_len
| 1) + 1;
87 /* new record idx and complete record size */
89 size
= key_len
+ entry_len
;
94 end_rec_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
95 end_off
= hfs_bnode_read_u16(node
, end_rec_off
);
97 dprint(DBG_BNODE_MOD
, "insert_rec: %d, %d, %d, %d\n", rec
, size
, end_off
, end_rec_off
);
98 if (size
> end_rec_off
- end_off
) {
100 panic("not enough room!\n");
101 new_node
= hfs_bnode_split(fd
);
102 if (IS_ERR(new_node
))
103 return PTR_ERR(new_node
);
106 if (node
->type
== HFS_NODE_LEAF
) {
108 mark_inode_dirty(tree
->inode
);
111 /* write new last offset */
112 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
113 hfs_bnode_write_u16(node
, end_rec_off
, end_off
+ size
);
115 data_rec_off
= end_rec_off
+ 2;
116 idx_rec_off
= tree
->node_size
- (rec
+ 1) * 2;
117 if (idx_rec_off
== data_rec_off
)
119 /* move all following entries */
121 data_off
= hfs_bnode_read_u16(node
, data_rec_off
+ 2);
122 hfs_bnode_write_u16(node
, data_rec_off
, data_off
+ size
);
124 } while (data_rec_off
< idx_rec_off
);
127 hfs_bnode_move(node
, data_off
+ size
, data_off
,
131 hfs_bnode_write(node
, fd
->search_key
, data_off
, key_len
);
132 hfs_bnode_write(node
, entry
, data_off
+ key_len
, entry_len
);
133 hfs_bnode_dump(node
);
136 /* update parent key if we inserted a key
137 * at the start of the first node
139 if (!rec
&& new_node
!= node
)
140 hfs_brec_update_parent(fd
);
142 hfs_bnode_put(fd
->bnode
);
143 if (!new_node
->parent
) {
144 hfs_btree_inc_height(tree
);
145 new_node
->parent
= tree
->root
;
147 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
149 /* create index data entry */
150 cnid
= cpu_to_be32(new_node
->this);
152 entry_len
= sizeof(cnid
);
155 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
156 __hfs_brec_find(fd
->bnode
, fd
);
158 hfs_bnode_put(new_node
);
161 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
162 key_len
= fd
->search_key
->key_len
+ 1;
164 fd
->search_key
->key_len
= tree
->max_key_len
;
165 key_len
= tree
->max_key_len
+ 1;
171 hfs_brec_update_parent(fd
);
176 int hfs_brec_remove(struct hfs_find_data
*fd
)
178 struct hfs_btree
*tree
;
179 struct hfs_bnode
*node
, *parent
;
180 int end_off
, rec_off
, data_off
, size
;
185 rec_off
= tree
->node_size
- (fd
->record
+ 2) * 2;
186 end_off
= tree
->node_size
- (node
->num_recs
+ 1) * 2;
188 if (node
->type
== HFS_NODE_LEAF
) {
190 mark_inode_dirty(tree
->inode
);
192 hfs_bnode_dump(node
);
193 dprint(DBG_BNODE_MOD
, "remove_rec: %d, %d\n", fd
->record
, fd
->keylength
+ fd
->entrylength
);
194 if (!--node
->num_recs
) {
195 hfs_bnode_unlink(node
);
198 parent
= hfs_bnode_find(tree
, node
->parent
);
200 return PTR_ERR(parent
);
202 node
= fd
->bnode
= parent
;
204 __hfs_brec_find(node
, fd
);
207 hfs_bnode_write_u16(node
, offsetof(struct hfs_bnode_desc
, num_recs
), node
->num_recs
);
209 if (rec_off
== end_off
)
211 size
= fd
->keylength
+ fd
->entrylength
;
214 data_off
= hfs_bnode_read_u16(node
, rec_off
);
215 hfs_bnode_write_u16(node
, rec_off
+ 2, data_off
- size
);
217 } while (rec_off
>= end_off
);
220 hfs_bnode_move(node
, fd
->keyoffset
, fd
->keyoffset
+ size
,
221 data_off
- fd
->keyoffset
- size
);
223 hfs_bnode_dump(node
);
225 hfs_brec_update_parent(fd
);
229 static struct hfs_bnode
*hfs_bnode_split(struct hfs_find_data
*fd
)
231 struct hfs_btree
*tree
;
232 struct hfs_bnode
*node
, *new_node
, *next_node
;
233 struct hfs_bnode_desc node_desc
;
234 int num_recs
, new_rec_off
, new_off
, old_rec_off
;
235 int data_start
, data_end
, size
;
239 new_node
= hfs_bmap_alloc(tree
);
240 if (IS_ERR(new_node
))
243 dprint(DBG_BNODE_MOD
, "split_nodes: %d - %d - %d\n",
244 node
->this, new_node
->this, node
->next
);
245 new_node
->next
= node
->next
;
246 new_node
->prev
= node
->this;
247 new_node
->parent
= node
->parent
;
248 new_node
->type
= node
->type
;
249 new_node
->height
= node
->height
;
252 next_node
= hfs_bnode_find(tree
, node
->next
);
256 if (IS_ERR(next_node
)) {
258 hfs_bnode_put(new_node
);
262 size
= tree
->node_size
/ 2 - node
->num_recs
* 2 - 14;
263 old_rec_off
= tree
->node_size
- 4;
266 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
267 if (data_start
> size
)
270 if (++num_recs
< node
->num_recs
)
274 hfs_bnode_put(new_node
);
276 hfs_bnode_put(next_node
);
277 return ERR_PTR(-ENOSPC
);
280 if (fd
->record
+ 1 < num_recs
) {
281 /* new record is in the lower half,
282 * so leave some more space there
286 data_start
= hfs_bnode_read_u16(node
, old_rec_off
);
289 hfs_bnode_get(new_node
);
290 fd
->bnode
= new_node
;
291 fd
->record
-= num_recs
;
292 fd
->keyoffset
-= data_start
- 14;
293 fd
->entryoffset
-= data_start
- 14;
295 new_node
->num_recs
= node
->num_recs
- num_recs
;
296 node
->num_recs
= num_recs
;
298 new_rec_off
= tree
->node_size
- 2;
300 size
= data_start
- new_off
;
301 num_recs
= new_node
->num_recs
;
302 data_end
= data_start
;
304 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
307 data_end
= hfs_bnode_read_u16(node
, old_rec_off
);
308 new_off
= data_end
- size
;
311 hfs_bnode_write_u16(new_node
, new_rec_off
, new_off
);
312 hfs_bnode_copy(new_node
, 14, node
, data_start
, data_end
- data_start
);
314 /* update new bnode header */
315 node_desc
.next
= cpu_to_be32(new_node
->next
);
316 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
317 node_desc
.type
= new_node
->type
;
318 node_desc
.height
= new_node
->height
;
319 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
320 node_desc
.reserved
= 0;
321 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
323 /* update previous bnode header */
324 node
->next
= new_node
->this;
325 hfs_bnode_read(node
, &node_desc
, 0, sizeof(node_desc
));
326 node_desc
.next
= cpu_to_be32(node
->next
);
327 node_desc
.num_recs
= cpu_to_be16(node
->num_recs
);
328 hfs_bnode_write(node
, &node_desc
, 0, sizeof(node_desc
));
330 /* update next bnode header */
332 next_node
->prev
= new_node
->this;
333 hfs_bnode_read(next_node
, &node_desc
, 0, sizeof(node_desc
));
334 node_desc
.prev
= cpu_to_be32(next_node
->prev
);
335 hfs_bnode_write(next_node
, &node_desc
, 0, sizeof(node_desc
));
336 hfs_bnode_put(next_node
);
337 } else if (node
->this == tree
->leaf_tail
) {
338 /* if there is no next node, this might be the new tail */
339 tree
->leaf_tail
= new_node
->this;
340 mark_inode_dirty(tree
->inode
);
343 hfs_bnode_dump(node
);
344 hfs_bnode_dump(new_node
);
350 static int hfs_brec_update_parent(struct hfs_find_data
*fd
)
352 struct hfs_btree
*tree
;
353 struct hfs_bnode
*node
, *new_node
, *parent
;
355 int rec
, rec_off
, end_rec_off
;
356 int start_off
, end_off
;
365 parent
= hfs_bnode_find(tree
, node
->parent
);
367 return PTR_ERR(parent
);
368 __hfs_brec_find(parent
, fd
);
369 hfs_bnode_dump(parent
);
372 /* size difference between old and new key */
373 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
)
374 newkeylen
= (hfs_bnode_read_u8(node
, 14) | 1) + 1;
376 fd
->keylength
= newkeylen
= tree
->max_key_len
+ 1;
377 dprint(DBG_BNODE_MOD
, "update_rec: %d, %d, %d\n", rec
, fd
->keylength
, newkeylen
);
379 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
380 end_rec_off
= tree
->node_size
- (parent
->num_recs
+ 1) * 2;
381 diff
= newkeylen
- fd
->keylength
;
385 end_off
= hfs_bnode_read_u16(parent
, end_rec_off
);
386 if (end_rec_off
- end_off
< diff
) {
388 printk(KERN_DEBUG
"hfs: splitting index node...\n");
390 new_node
= hfs_bnode_split(fd
);
391 if (IS_ERR(new_node
))
392 return PTR_ERR(new_node
);
395 rec_off
= tree
->node_size
- (rec
+ 2) * 2;
396 end_rec_off
= tree
->node_size
- (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 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
))
414 hfs_bnode_write_u8(parent
, fd
->keyoffset
, newkeylen
- 1);
415 hfs_bnode_dump(parent
);
423 fd
->bnode
= hfs_bnode_find(tree
, new_node
->parent
);
424 /* create index key and entry */
425 hfs_bnode_read_key(new_node
, fd
->search_key
, 14);
426 cnid
= cpu_to_be32(new_node
->this);
428 __hfs_brec_find(fd
->bnode
, fd
);
429 hfs_brec_insert(fd
, &cnid
, sizeof(cnid
));
430 hfs_bnode_put(fd
->bnode
);
431 hfs_bnode_put(new_node
);
434 if (new_node
== node
)
436 /* restore search_key */
437 hfs_bnode_read_key(node
, fd
->search_key
, 14);
441 if (!rec
&& node
->parent
)
448 static int hfs_btree_inc_height(struct hfs_btree
*tree
)
450 struct hfs_bnode
*node
, *new_node
;
451 struct hfs_bnode_desc node_desc
;
457 node
= hfs_bnode_find(tree
, tree
->root
);
459 return PTR_ERR(node
);
461 new_node
= hfs_bmap_alloc(tree
);
462 if (IS_ERR(new_node
)) {
464 return PTR_ERR(new_node
);
467 tree
->root
= new_node
->this;
469 tree
->leaf_head
= tree
->leaf_tail
= new_node
->this;
470 new_node
->type
= HFS_NODE_LEAF
;
471 new_node
->num_recs
= 0;
473 new_node
->type
= HFS_NODE_INDEX
;
474 new_node
->num_recs
= 1;
476 new_node
->parent
= 0;
479 new_node
->height
= ++tree
->depth
;
481 node_desc
.next
= cpu_to_be32(new_node
->next
);
482 node_desc
.prev
= cpu_to_be32(new_node
->prev
);
483 node_desc
.type
= new_node
->type
;
484 node_desc
.height
= new_node
->height
;
485 node_desc
.num_recs
= cpu_to_be16(new_node
->num_recs
);
486 node_desc
.reserved
= 0;
487 hfs_bnode_write(new_node
, &node_desc
, 0, sizeof(node_desc
));
489 rec
= tree
->node_size
- 2;
490 hfs_bnode_write_u16(new_node
, rec
, 14);
493 /* insert old root idx into new root */
494 node
->parent
= tree
->root
;
495 if (node
->type
== HFS_NODE_LEAF
||
496 tree
->attributes
& HFS_TREE_VARIDXKEYS
)
497 key_size
= hfs_bnode_read_u8(node
, 14) + 1;
499 key_size
= tree
->max_key_len
+ 1;
500 hfs_bnode_copy(new_node
, 14, node
, 14, key_size
);
502 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
503 key_size
= tree
->max_key_len
+ 1;
504 hfs_bnode_write_u8(new_node
, 14, tree
->max_key_len
);
506 key_size
= (key_size
+ 1) & -2;
507 cnid
= cpu_to_be32(node
->this);
508 hfs_bnode_write(new_node
, &cnid
, 14 + key_size
, 4);
511 hfs_bnode_write_u16(new_node
, rec
, 14 + key_size
+ 4);
515 hfs_bnode_put(new_node
);
516 mark_inode_dirty(tree
->inode
);
This page took 0.047127 seconds and 5 git commands to generate.