Lines Matching refs:node
9 * Handle basic btree node operations
21 /* Copy a specified range of bytes from the raw data of a node */
22 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len)
27 off += node->page_offset;
28 pagep = node->page + (off >> PAGE_SHIFT);
41 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off)
45 hfs_bnode_read(node, &data, off, 2);
49 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off)
53 hfs_bnode_read(node, &data, off, 1);
57 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off)
62 tree = node->tree;
63 if (node->type == HFS_NODE_LEAF ||
65 node->tree->cnid == HFSPLUS_ATTR_CNID)
66 key_len = hfs_bnode_read_u16(node, off) + 2;
70 hfs_bnode_read(node, key, off, key_len);
73 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len)
78 off += node->page_offset;
79 pagep = node->page + (off >> PAGE_SHIFT);
94 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data)
98 hfs_bnode_write(node, &v, off, 2);
101 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len)
106 off += node->page_offset;
107 pagep = node->page + (off >> PAGE_SHIFT);
175 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len)
184 src += node->page_offset;
185 dst += node->page_offset;
188 src_page = node->page + (src >> PAGE_SHIFT);
191 dst_page = node->page + (dst >> PAGE_SHIFT);
239 src_page = node->page + (src >> PAGE_SHIFT);
241 dst_page = node->page + (dst >> PAGE_SHIFT);
291 void hfs_bnode_dump(struct hfs_bnode *node)
297 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this);
298 hfs_bnode_read(node, &desc, 0, sizeof(desc));
303 off = node->tree->node_size - 2;
305 key_off = hfs_bnode_read_u16(node, off);
307 if (i && node->type == HFS_NODE_INDEX) {
310 if (node->tree->attributes & HFS_TREE_VARIDXKEYS ||
311 node->tree->cnid == HFSPLUS_ATTR_CNID)
312 tmp = hfs_bnode_read_u16(node, key_off) + 2;
314 tmp = node->tree->max_key_len + 2;
316 hfs_bnode_read(node, &cnid, key_off + tmp, 4);
318 } else if (i && node->type == HFS_NODE_LEAF) {
321 tmp = hfs_bnode_read_u16(node, key_off);
328 void hfs_bnode_unlink(struct hfs_bnode *node)
334 tree = node->tree;
335 if (node->prev) {
336 tmp = hfs_bnode_find(tree, node->prev);
339 tmp->next = node->next;
344 } else if (node->type == HFS_NODE_LEAF)
345 tree->leaf_head = node->next;
347 if (node->next) {
348 tmp = hfs_bnode_find(tree, node->next);
351 tmp->prev = node->prev;
356 } else if (node->type == HFS_NODE_LEAF)
357 tree->leaf_tail = node->prev;
360 if (!node->prev && !node->next)
362 if (!node->parent) {
366 set_bit(HFS_BNODE_DELETED, &node->flags);
378 struct hfs_bnode *node;
381 pr_err("request for non-existent node %d in B*Tree\n",
386 for (node = tree->node_hash[hfs_bnode_hash(cnid)];
387 node; node = node->next_hash)
388 if (node->this == cnid)
389 return node;
395 struct hfs_bnode *node, *node2;
402 pr_err("request for non-existent node %d in B*Tree\n",
409 node = kzalloc(size, GFP_KERNEL);
410 if (!node)
412 node->tree = tree;
413 node->this = cnid;
414 set_bit(HFS_BNODE_NEW, &node->flags);
415 atomic_set(&node->refcnt, 1);
417 node->tree->cnid, node->this);
418 init_waitqueue_head(&node->lock_wq);
423 node->next_hash = tree->node_hash[hash];
424 tree->node_hash[hash] = node;
428 kfree(node);
438 node->page_offset = off & ~PAGE_MASK;
443 node->page[i] = page;
446 return node;
448 set_bit(HFS_BNODE_ERROR, &node->flags);
449 return node;
452 void hfs_bnode_unhash(struct hfs_bnode *node)
457 node->tree->cnid, node->this, atomic_read(&node->refcnt));
458 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)];
459 *p && *p != node; p = &(*p)->next_hash)
462 *p = node->next_hash;
463 node->tree->node_hash_cnt--;
466 /* Load a particular node out of a tree */
469 struct hfs_bnode *node;
475 node = hfs_bnode_findhash(tree, num);
476 if (node) {
477 hfs_bnode_get(node);
479 wait_event(node->lock_wq,
480 !test_bit(HFS_BNODE_NEW, &node->flags));
481 if (test_bit(HFS_BNODE_ERROR, &node->flags))
483 return node;
486 node = __hfs_bnode_create(tree, num);
487 if (!node)
489 if (test_bit(HFS_BNODE_ERROR, &node->flags))
491 if (!test_bit(HFS_BNODE_NEW, &node->flags))
492 return node;
494 desc = (struct hfs_bnode_desc *)(kmap_local_page(node->page[0]) +
495 node->page_offset);
496 node->prev = be32_to_cpu(desc->prev);
497 node->next = be32_to_cpu(desc->next);
498 node->num_recs = be16_to_cpu(desc->num_recs);
499 node->type = desc->type;
500 node->height = desc->height;
503 switch (node->type) {
506 if (node->height != 0)
510 if (node->height != 1)
514 if (node->height <= 1 || node->height > tree->depth)
522 off = hfs_bnode_read_u16(node, rec_off);
525 for (i = 1; i <= node->num_recs; off = next_off, i++) {
527 next_off = hfs_bnode_read_u16(node, rec_off);
533 if (node->type != HFS_NODE_INDEX &&
534 node->type != HFS_NODE_LEAF)
536 key_size = hfs_bnode_read_u16(node, off) + 2;
540 clear_bit(HFS_BNODE_NEW, &node->flags);
541 wake_up(&node->lock_wq);
542 return node;
545 set_bit(HFS_BNODE_ERROR, &node->flags);
546 clear_bit(HFS_BNODE_NEW, &node->flags);
547 wake_up(&node->lock_wq);
548 hfs_bnode_put(node);
552 void hfs_bnode_free(struct hfs_bnode *node)
556 for (i = 0; i < node->tree->pages_per_bnode; i++)
557 if (node->page[i])
558 put_page(node->page[i]);
559 kfree(node);
564 struct hfs_bnode *node;
569 node = hfs_bnode_findhash(tree, num);
571 if (node) {
572 pr_crit("new node %u already hashed?\n", num);
574 return node;
576 node = __hfs_bnode_create(tree, num);
577 if (!node)
579 if (test_bit(HFS_BNODE_ERROR, &node->flags)) {
580 hfs_bnode_put(node);
584 pagep = node->page;
585 memzero_page(*pagep, node->page_offset,
592 clear_bit(HFS_BNODE_NEW, &node->flags);
593 wake_up(&node->lock_wq);
595 return node;
598 void hfs_bnode_get(struct hfs_bnode *node)
600 if (node) {
601 atomic_inc(&node->refcnt);
603 node->tree->cnid, node->this,
604 atomic_read(&node->refcnt));
608 /* Dispose of resources used by a node */
609 void hfs_bnode_put(struct hfs_bnode *node)
611 if (node) {
612 struct hfs_btree *tree = node->tree;
616 node->tree->cnid, node->this,
617 atomic_read(&node->refcnt));
618 BUG_ON(!atomic_read(&node->refcnt));
619 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock))
622 if (!node->page[i])
624 mark_page_accessed(node->page[i]);
627 if (test_bit(HFS_BNODE_DELETED, &node->flags)) {
628 hfs_bnode_unhash(node);
631 hfs_bnode_clear(node, 0, tree->node_size);
632 hfs_bmap_free(node);
633 hfs_bnode_free(node);