Lines Matching full:node
9 * Handle basic btree node operations
18 void hfs_bnode_read(struct hfs_bnode *node, void *buf, in hfs_bnode_read() argument
23 off += node->page_offset; in hfs_bnode_read()
24 page = node->page[0]; in hfs_bnode_read()
30 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) in hfs_bnode_read_u16() argument
34 hfs_bnode_read(node, &data, off, 2); in hfs_bnode_read_u16()
38 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) in hfs_bnode_read_u8() argument
42 hfs_bnode_read(node, &data, off, 1); in hfs_bnode_read_u8()
46 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) in hfs_bnode_read_key() argument
51 tree = node->tree; in hfs_bnode_read_key()
52 if (node->type == HFS_NODE_LEAF || in hfs_bnode_read_key()
54 key_len = hfs_bnode_read_u8(node, off) + 1; in hfs_bnode_read_key()
58 hfs_bnode_read(node, key, off, key_len); in hfs_bnode_read_key()
61 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) in hfs_bnode_write() argument
65 off += node->page_offset; in hfs_bnode_write()
66 page = node->page[0]; in hfs_bnode_write()
73 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) in hfs_bnode_write_u16() argument
77 hfs_bnode_write(node, &v, off, 2); in hfs_bnode_write_u16()
80 void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data) in hfs_bnode_write_u8() argument
83 hfs_bnode_write(node, &data, off, 1); in hfs_bnode_write_u8()
86 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) in hfs_bnode_clear() argument
90 off += node->page_offset; in hfs_bnode_clear()
91 page = node->page[0]; in hfs_bnode_clear()
117 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) in hfs_bnode_move() argument
125 src += node->page_offset; in hfs_bnode_move()
126 dst += node->page_offset; in hfs_bnode_move()
127 page = node->page[0]; in hfs_bnode_move()
134 void hfs_bnode_dump(struct hfs_bnode *node) in hfs_bnode_dump() argument
140 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this); in hfs_bnode_dump()
141 hfs_bnode_read(node, &desc, 0, sizeof(desc)); in hfs_bnode_dump()
146 off = node->tree->node_size - 2; in hfs_bnode_dump()
148 key_off = hfs_bnode_read_u16(node, off); in hfs_bnode_dump()
150 if (i && node->type == HFS_NODE_INDEX) { in hfs_bnode_dump()
153 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
154 tmp = (hfs_bnode_read_u8(node, key_off) | 1) + 1; in hfs_bnode_dump()
156 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
158 tmp, hfs_bnode_read_u8(node, key_off)); in hfs_bnode_dump()
159 hfs_bnode_read(node, &cnid, key_off + tmp, 4); in hfs_bnode_dump()
161 } else if (i && node->type == HFS_NODE_LEAF) { in hfs_bnode_dump()
164 tmp = hfs_bnode_read_u8(node, key_off); in hfs_bnode_dump()
171 void hfs_bnode_unlink(struct hfs_bnode *node) in hfs_bnode_unlink() argument
177 tree = node->tree; in hfs_bnode_unlink()
178 if (node->prev) { in hfs_bnode_unlink()
179 tmp = hfs_bnode_find(tree, node->prev); in hfs_bnode_unlink()
182 tmp->next = node->next; in hfs_bnode_unlink()
186 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
187 tree->leaf_head = node->next; in hfs_bnode_unlink()
189 if (node->next) { in hfs_bnode_unlink()
190 tmp = hfs_bnode_find(tree, node->next); in hfs_bnode_unlink()
193 tmp->prev = node->prev; in hfs_bnode_unlink()
197 } else if (node->type == HFS_NODE_LEAF) in hfs_bnode_unlink()
198 tree->leaf_tail = node->prev; in hfs_bnode_unlink()
201 if (!node->prev && !node->next) { in hfs_bnode_unlink()
204 if (!node->parent) { in hfs_bnode_unlink()
208 set_bit(HFS_BNODE_DELETED, &node->flags); in hfs_bnode_unlink()
220 struct hfs_bnode *node; in hfs_bnode_findhash() local
223 pr_err("request for non-existent node %d in B*Tree\n", cnid); in hfs_bnode_findhash()
227 for (node = tree->node_hash[hfs_bnode_hash(cnid)]; in hfs_bnode_findhash()
228 node; node = node->next_hash) { in hfs_bnode_findhash()
229 if (node->this == cnid) { in hfs_bnode_findhash()
230 return node; in hfs_bnode_findhash()
238 struct hfs_bnode *node, *node2; in __hfs_bnode_create() local
245 pr_err("request for non-existent node %d in B*Tree\n", cnid); in __hfs_bnode_create()
251 node = kzalloc(size, GFP_KERNEL); in __hfs_bnode_create()
252 if (!node) in __hfs_bnode_create()
254 node->tree = tree; in __hfs_bnode_create()
255 node->this = cnid; in __hfs_bnode_create()
256 set_bit(HFS_BNODE_NEW, &node->flags); in __hfs_bnode_create()
257 atomic_set(&node->refcnt, 1); in __hfs_bnode_create()
259 node->tree->cnid, node->this); in __hfs_bnode_create()
260 init_waitqueue_head(&node->lock_wq); in __hfs_bnode_create()
265 node->next_hash = tree->node_hash[hash]; in __hfs_bnode_create()
266 tree->node_hash[hash] = node; in __hfs_bnode_create()
270 kfree(node); in __hfs_bnode_create()
279 node->page_offset = off & ~PAGE_MASK; in __hfs_bnode_create()
288 node->page[i] = page; in __hfs_bnode_create()
291 return node; in __hfs_bnode_create()
293 set_bit(HFS_BNODE_ERROR, &node->flags); in __hfs_bnode_create()
294 return node; in __hfs_bnode_create()
297 void hfs_bnode_unhash(struct hfs_bnode *node) in hfs_bnode_unhash() argument
302 node->tree->cnid, node->this, atomic_read(&node->refcnt)); in hfs_bnode_unhash()
303 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; in hfs_bnode_unhash()
304 *p && *p != node; p = &(*p)->next_hash) in hfs_bnode_unhash()
307 *p = node->next_hash; in hfs_bnode_unhash()
308 node->tree->node_hash_cnt--; in hfs_bnode_unhash()
311 /* Load a particular node out of a tree */
314 struct hfs_bnode *node; in hfs_bnode_find() local
320 node = hfs_bnode_findhash(tree, num); in hfs_bnode_find()
321 if (node) { in hfs_bnode_find()
322 hfs_bnode_get(node); in hfs_bnode_find()
324 wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags)); in hfs_bnode_find()
325 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
327 return node; in hfs_bnode_find()
330 node = __hfs_bnode_create(tree, num); in hfs_bnode_find()
331 if (!node) in hfs_bnode_find()
333 if (test_bit(HFS_BNODE_ERROR, &node->flags)) in hfs_bnode_find()
335 if (!test_bit(HFS_BNODE_NEW, &node->flags)) in hfs_bnode_find()
336 return node; in hfs_bnode_find()
338 desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset); in hfs_bnode_find()
339 node->prev = be32_to_cpu(desc->prev); in hfs_bnode_find()
340 node->next = be32_to_cpu(desc->next); in hfs_bnode_find()
341 node->num_recs = be16_to_cpu(desc->num_recs); in hfs_bnode_find()
342 node->type = desc->type; in hfs_bnode_find()
343 node->height = desc->height; in hfs_bnode_find()
344 kunmap(node->page[0]); in hfs_bnode_find()
346 switch (node->type) { in hfs_bnode_find()
349 if (node->height != 0) in hfs_bnode_find()
353 if (node->height != 1) in hfs_bnode_find()
357 if (node->height <= 1 || node->height > tree->depth) in hfs_bnode_find()
365 off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
368 for (i = 1; i <= node->num_recs; off = next_off, i++) { in hfs_bnode_find()
370 next_off = hfs_bnode_read_u16(node, rec_off); in hfs_bnode_find()
376 if (node->type != HFS_NODE_INDEX && in hfs_bnode_find()
377 node->type != HFS_NODE_LEAF) in hfs_bnode_find()
379 key_size = hfs_bnode_read_u8(node, off) + 1; in hfs_bnode_find()
383 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
384 wake_up(&node->lock_wq); in hfs_bnode_find()
385 return node; in hfs_bnode_find()
388 set_bit(HFS_BNODE_ERROR, &node->flags); in hfs_bnode_find()
389 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_find()
390 wake_up(&node->lock_wq); in hfs_bnode_find()
391 hfs_bnode_put(node); in hfs_bnode_find()
395 void hfs_bnode_free(struct hfs_bnode *node) in hfs_bnode_free() argument
399 for (i = 0; i < node->tree->pages_per_bnode; i++) in hfs_bnode_free()
400 if (node->page[i]) in hfs_bnode_free()
401 put_page(node->page[i]); in hfs_bnode_free()
402 kfree(node); in hfs_bnode_free()
407 struct hfs_bnode *node; in hfs_bnode_create() local
412 node = hfs_bnode_findhash(tree, num); in hfs_bnode_create()
414 if (node) { in hfs_bnode_create()
415 pr_crit("new node %u already hashed?\n", num); in hfs_bnode_create()
417 return node; in hfs_bnode_create()
419 node = __hfs_bnode_create(tree, num); in hfs_bnode_create()
420 if (!node) in hfs_bnode_create()
422 if (test_bit(HFS_BNODE_ERROR, &node->flags)) { in hfs_bnode_create()
423 hfs_bnode_put(node); in hfs_bnode_create()
427 pagep = node->page; in hfs_bnode_create()
428 memset(kmap(*pagep) + node->page_offset, 0, in hfs_bnode_create()
437 clear_bit(HFS_BNODE_NEW, &node->flags); in hfs_bnode_create()
438 wake_up(&node->lock_wq); in hfs_bnode_create()
440 return node; in hfs_bnode_create()
443 void hfs_bnode_get(struct hfs_bnode *node) in hfs_bnode_get() argument
445 if (node) { in hfs_bnode_get()
446 atomic_inc(&node->refcnt); in hfs_bnode_get()
448 node->tree->cnid, node->this, in hfs_bnode_get()
449 atomic_read(&node->refcnt)); in hfs_bnode_get()
453 /* Dispose of resources used by a node */
454 void hfs_bnode_put(struct hfs_bnode *node) in hfs_bnode_put() argument
456 if (node) { in hfs_bnode_put()
457 struct hfs_btree *tree = node->tree; in hfs_bnode_put()
461 node->tree->cnid, node->this, in hfs_bnode_put()
462 atomic_read(&node->refcnt)); in hfs_bnode_put()
463 BUG_ON(!atomic_read(&node->refcnt)); in hfs_bnode_put()
464 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) in hfs_bnode_put()
467 if (!node->page[i]) in hfs_bnode_put()
469 mark_page_accessed(node->page[i]); in hfs_bnode_put()
472 if (test_bit(HFS_BNODE_DELETED, &node->flags)) { in hfs_bnode_put()
473 hfs_bnode_unhash(node); in hfs_bnode_put()
475 hfs_bmap_free(node); in hfs_bnode_put()
476 hfs_bnode_free(node); in hfs_bnode_put()