Lines Matching refs:node
19 bool is_bnode_offset_valid(struct hfs_bnode *node, int off) in is_bnode_offset_valid() argument
21 bool is_valid = off < node->tree->node_size; in is_bnode_offset_valid()
27 node->this, node->type, node->height, in is_bnode_offset_valid()
28 node->tree->node_size, off); in is_bnode_offset_valid()
35 int check_and_correct_requested_length(struct hfs_bnode *node, int off, int len) in check_and_correct_requested_length() argument
39 if (!is_bnode_offset_valid(node, off)) in check_and_correct_requested_length()
42 node_size = node->tree->node_size; in check_and_correct_requested_length()
51 node->this, node->type, node->height, in check_and_correct_requested_length()
52 node->tree->node_size, off, len, new_len); in check_and_correct_requested_length()
60 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len) in hfs_bnode_read() argument
67 if (!is_bnode_offset_valid(node, off)) in hfs_bnode_read()
74 node->this, node->type, node->height, in hfs_bnode_read()
75 node->tree->node_size, off, len); in hfs_bnode_read()
79 len = check_and_correct_requested_length(node, off, len); in hfs_bnode_read()
81 off += node->page_offset; in hfs_bnode_read()
86 if (pagenum >= node->tree->pages_per_bnode) in hfs_bnode_read()
88 page = node->page[pagenum]; in hfs_bnode_read()
98 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) in hfs_bnode_read_u16() argument
102 hfs_bnode_read(node, &data, off, 2); in hfs_bnode_read_u16()
106 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) in hfs_bnode_read_u8() argument
110 hfs_bnode_read(node, &data, off, 1); in hfs_bnode_read_u8()
114 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) in hfs_bnode_read_key() argument
119 tree = node->tree; in hfs_bnode_read_key()
120 if (node->type == HFS_NODE_LEAF || in hfs_bnode_read_key()
122 key_len = hfs_bnode_read_u8(node, off) + 1; in hfs_bnode_read_key()
132 hfs_bnode_read(node, key, off, key_len); in hfs_bnode_read_key()
135 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) in hfs_bnode_write() argument
139 if (!is_bnode_offset_valid(node, off)) in hfs_bnode_write()
146 node->this, node->type, node->height, in hfs_bnode_write()
147 node->tree->node_size, off, len); in hfs_bnode_write()
151 len = check_and_correct_requested_length(node, off, len); in hfs_bnode_write()
153 off += node->page_offset; in hfs_bnode_write()
154 page = node->page[0]; in hfs_bnode_write()
160 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) in hfs_bnode_write_u16() argument
164 hfs_bnode_write(node, &v, off, 2); in hfs_bnode_write_u16()
167 void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data) in hfs_bnode_write_u8() argument
170 hfs_bnode_write(node, &data, off, 1); in hfs_bnode_write_u8()
173 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) in hfs_bnode_clear() argument
177 if (!is_bnode_offset_valid(node, off)) in hfs_bnode_clear()
184 node->this, node->type, node->height, in hfs_bnode_clear()
185 node->tree->node_size, off, len); in hfs_bnode_clear()
189 len = check_and_correct_requested_length(node, off, len); in hfs_bnode_clear()
191 off += node->page_offset; in hfs_bnode_clear()
192 page = node->page[0]; in hfs_bnode_clear()
219 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) in hfs_bnode_move() argument
228 len = check_and_correct_requested_length(node, src, len); in hfs_bnode_move()
229 len = check_and_correct_requested_length(node, dst, len); in hfs_bnode_move()
231 src += node->page_offset; in hfs_bnode_move()
232 dst += node->page_offset; in hfs_bnode_move()
233 page = node->page[0]; in hfs_bnode_move()
240 void hfs_bnode_dump(struct hfs_bnode *node) in hfs_bnode_dump() argument
246 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this); in hfs_bnode_dump()
247 hfs_bnode_read(node, &desc, 0, sizeof(desc)); in hfs_bnode_dump()
252 off = node->tree->node_size - 2; in hfs_bnode_dump()
254 key_off = hfs_bnode_read_u16(node, off); in hfs_bnode_dump()
256 if (i && node->type == HFS_NODE_INDEX) { in hfs_bnode_dump()
259 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
260 tmp = (hfs_bnode_read_u8(node, key_off) | 1) + 1; in hfs_bnode_dump()
262 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
264 tmp, hfs_bnode_read_u8(node, key_off)); in hfs_bnode_dump()
265 hfs_bnode_read(node, &cnid, key_off + tmp, 4); in hfs_bnode_dump()
267 } else if (i && node->type == HFS_NODE_LEAF) { in hfs_bnode_dump()
270 tmp = hfs_bnode_read_u8(node, key_off); in hfs_bnode_dump()
277 void hfs_bnode_unlink(struct hfs_bnode *node) in hfs_bnode_unlink() argument
283 tree = node->tree; in hfs_bnode_unlink()
284 if (node->prev) { in hfs_bnode_unlink()
285 tmp = hfs_bnode_find(tree, node->prev); in hfs_bnode_unlink()
288 tmp->next = node->next; in hfs_bnode_unlink()
292 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
293 tree->leaf_head = node->next; in hfs_bnode_unlink()
295 if (node->next) { in hfs_bnode_unlink()
296 tmp = hfs_bnode_find(tree, node->next); in hfs_bnode_unlink()
299 tmp->prev = node->prev; in hfs_bnode_unlink()
303 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
304 tree->leaf_tail = node->prev; in hfs_bnode_unlink()
307 if (!node->prev && !node->next) { in hfs_bnode_unlink()
310 if (!node->parent) { in hfs_bnode_unlink()
314 set_bit(HFS_BNODE_DELETED, &node->flags); in hfs_bnode_unlink()
326 struct hfs_bnode *node; in hfs_bnode_findhash() local
333 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; in hfs_bnode_findhash()
334 node; node = node->next_hash) { in hfs_bnode_findhash()
335 if (node->this == cnid) { in hfs_bnode_findhash()
336 return node; in hfs_bnode_findhash()
344 struct hfs_bnode *node, *node2; in __hfs_bnode_create() local
357 node = kzalloc(size, GFP_KERNEL); in __hfs_bnode_create()
358 if (!node) in __hfs_bnode_create()
360 node->tree = tree; in __hfs_bnode_create()
361 node->this = cnid; in __hfs_bnode_create()
362 set_bit(HFS_BNODE_NEW, &node->flags); in __hfs_bnode_create()
363 atomic_set(&node->refcnt, 1); in __hfs_bnode_create()
365 node->tree->cnid, node->this); in __hfs_bnode_create()
366 init_waitqueue_head(&node->lock_wq); in __hfs_bnode_create()
371 node->next_hash = tree->node_hash[hash]; in __hfs_bnode_create()
372 tree->node_hash[hash] = node; in __hfs_bnode_create()
377 kfree(node); in __hfs_bnode_create()
386 node->page_offset = off & ~PAGE_MASK; in __hfs_bnode_create()
391 node->page[i] = page; in __hfs_bnode_create()
394 return node; in __hfs_bnode_create()
396 set_bit(HFS_BNODE_ERROR, &node->flags); in __hfs_bnode_create()
397 return node; in __hfs_bnode_create()
400 void hfs_bnode_unhash(struct hfs_bnode *node) in hfs_bnode_unhash() argument
405 node->tree->cnid, node->this, atomic_read(&node->refcnt)); in hfs_bnode_unhash()
406 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; in hfs_bnode_unhash()
407 *p && *p != node; p = &(*p)->next_hash) in hfs_bnode_unhash()
410 *p = node->next_hash; in hfs_bnode_unhash()
411 node->tree->node_hash_cnt--; in hfs_bnode_unhash()
417 struct hfs_bnode *node; in hfs_bnode_find() local
423 node = hfs_bnode_findhash(tree, num); in hfs_bnode_find()
424 if (node) { in hfs_bnode_find()
425 hfs_bnode_get(node); in hfs_bnode_find()
427 wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags)); in hfs_bnode_find()
428 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
430 return node; in hfs_bnode_find()
433 node = __hfs_bnode_create(tree, num); in hfs_bnode_find()
434 if (!node) in hfs_bnode_find()
436 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
438 if (!test_bit(HFS_BNODE_NEW, &node->flags)) in hfs_bnode_find()
439 return node; in hfs_bnode_find()
441 desc = (struct hfs_bnode_desc *)(kmap_local_page(node->page[0]) + in hfs_bnode_find()
442 node->page_offset); in hfs_bnode_find()
443 node->prev = be32_to_cpu(desc->prev); in hfs_bnode_find()
444 node->next = be32_to_cpu(desc->next); in hfs_bnode_find()
445 node->num_recs = be16_to_cpu(desc->num_recs); in hfs_bnode_find()
446 node->type = desc->type; in hfs_bnode_find()
447 node->height = desc->height; in hfs_bnode_find()
450 switch (node->type) { in hfs_bnode_find()
453 if (node->height != 0) in hfs_bnode_find()
457 if (node->height != 1) in hfs_bnode_find()
461 if (node->height <= 1 || node->height > tree->depth) in hfs_bnode_find()
469 off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
472 for (i = 1; i <= node->num_recs; off = next_off, i++) { in hfs_bnode_find()
474 next_off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
480 if (node->type != HFS_NODE_INDEX && in hfs_bnode_find()
481 node->type != HFS_NODE_LEAF) in hfs_bnode_find()
483 key_size = hfs_bnode_read_u8(node, off) + 1; in hfs_bnode_find()
487 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
488 wake_up(&node->lock_wq); in hfs_bnode_find()
489 return node; in hfs_bnode_find()
492 set_bit(HFS_BNODE_ERROR, &node->flags); in hfs_bnode_find()
493 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
494 wake_up(&node->lock_wq); in hfs_bnode_find()
495 hfs_bnode_put(node); in hfs_bnode_find()
499 void hfs_bnode_free(struct hfs_bnode *node) in hfs_bnode_free() argument
503 for (i = 0; i < node->tree->pages_per_bnode; i++) in hfs_bnode_free()
504 if (node->page[i]) in hfs_bnode_free()
505 put_page(node->page[i]); in hfs_bnode_free()
506 kfree(node); in hfs_bnode_free()
511 struct hfs_bnode *node; in hfs_bnode_create() local
516 node = hfs_bnode_findhash(tree, num); in hfs_bnode_create()
518 if (node) { in hfs_bnode_create()
521 return node; in hfs_bnode_create()
523 node = __hfs_bnode_create(tree, num); in hfs_bnode_create()
524 if (!node) in hfs_bnode_create()
526 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { in hfs_bnode_create()
527 hfs_bnode_put(node); in hfs_bnode_create()
531 pagep = node->page; in hfs_bnode_create()
532 memzero_page(*pagep, node->page_offset, in hfs_bnode_create()
539 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_create()
540 wake_up(&node->lock_wq); in hfs_bnode_create()
542 return node; in hfs_bnode_create()
545 void hfs_bnode_get(struct hfs_bnode *node) in hfs_bnode_get() argument
547 if (node) { in hfs_bnode_get()
548 atomic_inc(&node->refcnt); in hfs_bnode_get()
550 node->tree->cnid, node->this, in hfs_bnode_get()
551 atomic_read(&node->refcnt)); in hfs_bnode_get()
556 void hfs_bnode_put(struct hfs_bnode *node) in hfs_bnode_put() argument
558 if (node) { in hfs_bnode_put()
559 struct hfs_btree *tree = node->tree; in hfs_bnode_put()
563 node->tree->cnid, node->this, in hfs_bnode_put()
564 atomic_read(&node->refcnt)); in hfs_bnode_put()
565 BUG_ON(!atomic_read(&node->refcnt)); in hfs_bnode_put()
566 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) in hfs_bnode_put()
569 if (!node->page[i]) in hfs_bnode_put()
571 mark_page_accessed(node->page[i]); in hfs_bnode_put()
574 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { in hfs_bnode_put()
575 hfs_bnode_unhash(node); in hfs_bnode_put()
577 hfs_bnode_clear(node, 0, tree->node_size); in hfs_bnode_put()
578 hfs_bmap_free(node); in hfs_bnode_put()
579 hfs_bnode_free(node); in hfs_bnode_put()