Lines Matching full: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) in hfs_bnode_read() argument
27 off += node->page_offset; in hfs_bnode_read()
28 pagep = node->page + (off >> PAGE_SHIFT); in hfs_bnode_read()
41 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) in hfs_bnode_read_u16() argument
45 hfs_bnode_read(node, &data, off, 2); in hfs_bnode_read_u16()
49 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) in hfs_bnode_read_u8() argument
53 hfs_bnode_read(node, &data, off, 1); in hfs_bnode_read_u8()
57 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) in hfs_bnode_read_key() argument
62 tree = node->tree; in hfs_bnode_read_key()
63 if (node->type == HFS_NODE_LEAF || in hfs_bnode_read_key()
65 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
66 key_len = hfs_bnode_read_u16(node, off) + 2; in hfs_bnode_read_key()
76 hfs_bnode_read(node, key, off, key_len); in hfs_bnode_read_key()
79 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) in hfs_bnode_write() argument
84 off += node->page_offset; in hfs_bnode_write()
85 pagep = node->page + (off >> PAGE_SHIFT); in hfs_bnode_write()
100 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) in hfs_bnode_write_u16() argument
104 hfs_bnode_write(node, &v, off, 2); in hfs_bnode_write_u16()
107 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) in hfs_bnode_clear() argument
112 off += node->page_offset; in hfs_bnode_clear()
113 pagep = node->page + (off >> PAGE_SHIFT); in hfs_bnode_clear()
181 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) in hfs_bnode_move() argument
190 src += node->page_offset; in hfs_bnode_move()
191 dst += node->page_offset; in hfs_bnode_move()
194 src_page = node->page + (src >> PAGE_SHIFT); in hfs_bnode_move()
197 dst_page = node->page + (dst >> PAGE_SHIFT); in hfs_bnode_move()
245 src_page = node->page + (src >> PAGE_SHIFT); in hfs_bnode_move()
247 dst_page = node->page + (dst >> PAGE_SHIFT); in hfs_bnode_move()
297 void hfs_bnode_dump(struct hfs_bnode *node) in hfs_bnode_dump() argument
303 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this); in hfs_bnode_dump()
304 hfs_bnode_read(node, &desc, 0, sizeof(desc)); in hfs_bnode_dump()
309 off = node->tree->node_size - 2; in hfs_bnode_dump()
311 key_off = hfs_bnode_read_u16(node, off); in hfs_bnode_dump()
313 if (i && node->type == HFS_NODE_INDEX) { in hfs_bnode_dump()
316 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
317 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
318 tmp = hfs_bnode_read_u16(node, key_off) + 2; in hfs_bnode_dump()
320 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
322 hfs_bnode_read(node, &cnid, key_off + tmp, 4); in hfs_bnode_dump()
324 } else if (i && node->type == HFS_NODE_LEAF) { in hfs_bnode_dump()
327 tmp = hfs_bnode_read_u16(node, key_off); in hfs_bnode_dump()
334 void hfs_bnode_unlink(struct hfs_bnode *node) in hfs_bnode_unlink() argument
340 tree = node->tree; in hfs_bnode_unlink()
341 if (node->prev) { in hfs_bnode_unlink()
342 tmp = hfs_bnode_find(tree, node->prev); in hfs_bnode_unlink()
345 tmp->next = node->next; in hfs_bnode_unlink()
350 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
351 tree->leaf_head = node->next; in hfs_bnode_unlink()
353 if (node->next) { in hfs_bnode_unlink()
354 tmp = hfs_bnode_find(tree, node->next); in hfs_bnode_unlink()
357 tmp->prev = node->prev; in hfs_bnode_unlink()
362 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
363 tree->leaf_tail = node->prev; in hfs_bnode_unlink()
366 if (!node->prev && !node->next) in hfs_bnode_unlink()
368 if (!node->parent) { in hfs_bnode_unlink()
372 set_bit(HFS_BNODE_DELETED, &node->flags); in hfs_bnode_unlink()
384 struct hfs_bnode *node; in hfs_bnode_findhash() local
387 pr_err("request for non-existent node %d in B*Tree\n", in hfs_bnode_findhash()
392 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; in hfs_bnode_findhash()
393 node; node = node->next_hash) in hfs_bnode_findhash()
394 if (node->this == cnid) in hfs_bnode_findhash()
395 return node; in hfs_bnode_findhash()
401 struct hfs_bnode *node, *node2; in __hfs_bnode_create() local
408 pr_err("request for non-existent node %d in B*Tree\n", in __hfs_bnode_create()
415 node = kzalloc(size, GFP_KERNEL); in __hfs_bnode_create()
416 if (!node) in __hfs_bnode_create()
418 node->tree = tree; in __hfs_bnode_create()
419 node->this = cnid; in __hfs_bnode_create()
420 set_bit(HFS_BNODE_NEW, &node->flags); in __hfs_bnode_create()
421 atomic_set(&node->refcnt, 1); in __hfs_bnode_create()
423 node->tree->cnid, node->this); in __hfs_bnode_create()
424 init_waitqueue_head(&node->lock_wq); in __hfs_bnode_create()
429 node->next_hash = tree->node_hash[hash]; in __hfs_bnode_create()
430 tree->node_hash[hash] = node; in __hfs_bnode_create()
434 kfree(node); in __hfs_bnode_create()
444 node->page_offset = off & ~PAGE_MASK; in __hfs_bnode_create()
449 node->page[i] = page; in __hfs_bnode_create()
452 return node; in __hfs_bnode_create()
454 set_bit(HFS_BNODE_ERROR, &node->flags); in __hfs_bnode_create()
455 return node; in __hfs_bnode_create()
458 void hfs_bnode_unhash(struct hfs_bnode *node) in hfs_bnode_unhash() argument
463 node->tree->cnid, node->this, atomic_read(&node->refcnt)); in hfs_bnode_unhash()
464 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; in hfs_bnode_unhash()
465 *p && *p != node; p = &(*p)->next_hash) in hfs_bnode_unhash()
468 *p = node->next_hash; in hfs_bnode_unhash()
469 node->tree->node_hash_cnt--; in hfs_bnode_unhash()
472 /* Load a particular node out of a tree */
475 struct hfs_bnode *node; in hfs_bnode_find() local
481 node = hfs_bnode_findhash(tree, num); in hfs_bnode_find()
482 if (node) { in hfs_bnode_find()
483 hfs_bnode_get(node); in hfs_bnode_find()
485 wait_event(node->lock_wq, in hfs_bnode_find()
486 !test_bit(HFS_BNODE_NEW, &node->flags)); in hfs_bnode_find()
487 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
489 return node; in hfs_bnode_find()
492 node = __hfs_bnode_create(tree, num); in hfs_bnode_find()
493 if (!node) in hfs_bnode_find()
495 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
497 if (!test_bit(HFS_BNODE_NEW, &node->flags)) in hfs_bnode_find()
498 return node; in hfs_bnode_find()
500 desc = (struct hfs_bnode_desc *)(kmap_local_page(node->page[0]) + in hfs_bnode_find()
501 node->page_offset); in hfs_bnode_find()
502 node->prev = be32_to_cpu(desc->prev); in hfs_bnode_find()
503 node->next = be32_to_cpu(desc->next); in hfs_bnode_find()
504 node->num_recs = be16_to_cpu(desc->num_recs); in hfs_bnode_find()
505 node->type = desc->type; in hfs_bnode_find()
506 node->height = desc->height; in hfs_bnode_find()
509 switch (node->type) { in hfs_bnode_find()
512 if (node->height != 0) in hfs_bnode_find()
516 if (node->height != 1) in hfs_bnode_find()
520 if (node->height <= 1 || node->height > tree->depth) in hfs_bnode_find()
528 off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
531 for (i = 1; i <= node->num_recs; off = next_off, i++) { in hfs_bnode_find()
533 next_off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
539 if (node->type != HFS_NODE_INDEX && in hfs_bnode_find()
540 node->type != HFS_NODE_LEAF) in hfs_bnode_find()
542 key_size = hfs_bnode_read_u16(node, off) + 2; in hfs_bnode_find()
546 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
547 wake_up(&node->lock_wq); in hfs_bnode_find()
548 return node; in hfs_bnode_find()
551 set_bit(HFS_BNODE_ERROR, &node->flags); in hfs_bnode_find()
552 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
553 wake_up(&node->lock_wq); in hfs_bnode_find()
554 hfs_bnode_put(node); in hfs_bnode_find()
558 void hfs_bnode_free(struct hfs_bnode *node) in hfs_bnode_free() argument
562 for (i = 0; i < node->tree->pages_per_bnode; i++) in hfs_bnode_free()
563 if (node->page[i]) in hfs_bnode_free()
564 put_page(node->page[i]); in hfs_bnode_free()
565 kfree(node); in hfs_bnode_free()
570 struct hfs_bnode *node; in hfs_bnode_create() local
575 node = hfs_bnode_findhash(tree, num); in hfs_bnode_create()
577 if (node) { in hfs_bnode_create()
578 pr_crit("new node %u already hashed?\n", num); in hfs_bnode_create()
580 return node; in hfs_bnode_create()
582 node = __hfs_bnode_create(tree, num); in hfs_bnode_create()
583 if (!node) in hfs_bnode_create()
585 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { in hfs_bnode_create()
586 hfs_bnode_put(node); in hfs_bnode_create()
590 pagep = node->page; in hfs_bnode_create()
591 memzero_page(*pagep, node->page_offset, in hfs_bnode_create()
598 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_create()
599 wake_up(&node->lock_wq); in hfs_bnode_create()
601 return node; in hfs_bnode_create()
604 void hfs_bnode_get(struct hfs_bnode *node) in hfs_bnode_get() argument
606 if (node) { in hfs_bnode_get()
607 atomic_inc(&node->refcnt); in hfs_bnode_get()
609 node->tree->cnid, node->this, in hfs_bnode_get()
610 atomic_read(&node->refcnt)); in hfs_bnode_get()
614 /* Dispose of resources used by a node */
615 void hfs_bnode_put(struct hfs_bnode *node) in hfs_bnode_put() argument
617 if (node) { in hfs_bnode_put()
618 struct hfs_btree *tree = node->tree; in hfs_bnode_put()
622 node->tree->cnid, node->this, in hfs_bnode_put()
623 atomic_read(&node->refcnt)); in hfs_bnode_put()
624 BUG_ON(!atomic_read(&node->refcnt)); in hfs_bnode_put()
625 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) in hfs_bnode_put()
628 if (!node->page[i]) in hfs_bnode_put()
630 mark_page_accessed(node->page[i]); in hfs_bnode_put()
633 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { in hfs_bnode_put()
634 hfs_bnode_unhash(node); in hfs_bnode_put()
637 hfs_bnode_clear(node, 0, tree->node_size); in hfs_bnode_put()
638 hfs_bmap_free(node); in hfs_bnode_put()
639 hfs_bnode_free(node); in hfs_bnode_put()