Lines Matching refs:node
9 * Handle basic btree node operations
18 void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len)
26 off += node->page_offset;
31 if (pagenum >= node->tree->pages_per_bnode)
33 page = node->page[pagenum];
45 u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off)
49 hfs_bnode_read(node, &data, off, 2);
53 u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off)
57 hfs_bnode_read(node, &data, off, 1);
61 void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off)
66 tree = node->tree;
67 if (node->type == HFS_NODE_LEAF ||
69 key_len = hfs_bnode_read_u8(node, off) + 1;
73 hfs_bnode_read(node, key, off, key_len);
76 void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len)
80 off += node->page_offset;
81 page = node->page[0];
88 void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data)
92 hfs_bnode_write(node, &v, off, 2);
95 void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data)
98 hfs_bnode_write(node, &data, off, 1);
101 void hfs_bnode_clear(struct hfs_bnode *node, int off, int len)
105 off += node->page_offset;
106 page = node->page[0];
132 void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len)
140 src += node->page_offset;
141 dst += node->page_offset;
142 page = node->page[0];
149 void hfs_bnode_dump(struct hfs_bnode *node)
155 hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this);
156 hfs_bnode_read(node, &desc, 0, sizeof(desc));
161 off = node->tree->node_size - 2;
163 key_off = hfs_bnode_read_u16(node, off);
165 if (i && node->type == HFS_NODE_INDEX) {
168 if (node->tree->attributes & HFS_TREE_VARIDXKEYS)
169 tmp = (hfs_bnode_read_u8(node, key_off) | 1) + 1;
171 tmp = node->tree->max_key_len + 1;
173 tmp, hfs_bnode_read_u8(node, key_off));
174 hfs_bnode_read(node, &cnid, key_off + tmp, 4);
176 } else if (i && node->type == HFS_NODE_LEAF) {
179 tmp = hfs_bnode_read_u8(node, key_off);
186 void hfs_bnode_unlink(struct hfs_bnode *node)
192 tree = node->tree;
193 if (node->prev) {
194 tmp = hfs_bnode_find(tree, node->prev);
197 tmp->next = node->next;
201 } else if (node->type == HFS_NODE_LEAF)
202 tree->leaf_head = node->next;
204 if (node->next) {
205 tmp = hfs_bnode_find(tree, node->next);
208 tmp->prev = node->prev;
212 } else if (node->type == HFS_NODE_LEAF)
213 tree->leaf_tail = node->prev;
216 if (!node->prev && !node->next) {
219 if (!node->parent) {
223 set_bit(HFS_BNODE_DELETED, &node->flags);
235 struct hfs_bnode *node;
238 pr_err("request for non-existent node %d in B*Tree\n", cnid);
242 for (node = tree->node_hash[hfs_bnode_hash(cnid)];
243 node; node = node->next_hash) {
244 if (node->this == cnid) {
245 return node;
253 struct hfs_bnode *node, *node2;
260 pr_err("request for non-existent node %d in B*Tree\n", cnid);
266 node = kzalloc(size, GFP_KERNEL);
267 if (!node)
269 node->tree = tree;
270 node->this = cnid;
271 set_bit(HFS_BNODE_NEW, &node->flags);
272 atomic_set(&node->refcnt, 1);
274 node->tree->cnid, node->this);
275 init_waitqueue_head(&node->lock_wq);
280 node->next_hash = tree->node_hash[hash];
281 tree->node_hash[hash] = node;
286 kfree(node);
295 node->page_offset = off & ~PAGE_MASK;
304 node->page[i] = page;
307 return node;
309 set_bit(HFS_BNODE_ERROR, &node->flags);
310 return node;
313 void hfs_bnode_unhash(struct hfs_bnode *node)
318 node->tree->cnid, node->this, atomic_read(&node->refcnt));
319 for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)];
320 *p && *p != node; p = &(*p)->next_hash)
323 *p = node->next_hash;
324 node->tree->node_hash_cnt--;
327 /* Load a particular node out of a tree */
330 struct hfs_bnode *node;
336 node = hfs_bnode_findhash(tree, num);
337 if (node) {
338 hfs_bnode_get(node);
340 wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags));
341 if (test_bit(HFS_BNODE_ERROR, &node->flags))
343 return node;
346 node = __hfs_bnode_create(tree, num);
347 if (!node)
349 if (test_bit(HFS_BNODE_ERROR, &node->flags))
351 if (!test_bit(HFS_BNODE_NEW, &node->flags))
352 return node;
354 desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset);
355 node->prev = be32_to_cpu(desc->prev);
356 node->next = be32_to_cpu(desc->next);
357 node->num_recs = be16_to_cpu(desc->num_recs);
358 node->type = desc->type;
359 node->height = desc->height;
360 kunmap(node->page[0]);
362 switch (node->type) {
365 if (node->height != 0)
369 if (node->height != 1)
373 if (node->height <= 1 || node->height > tree->depth)
381 off = hfs_bnode_read_u16(node, rec_off);
384 for (i = 1; i <= node->num_recs; off = next_off, i++) {
386 next_off = hfs_bnode_read_u16(node, rec_off);
392 if (node->type != HFS_NODE_INDEX &&
393 node->type != HFS_NODE_LEAF)
395 key_size = hfs_bnode_read_u8(node, off) + 1;
399 clear_bit(HFS_BNODE_NEW, &node->flags);
400 wake_up(&node->lock_wq);
401 return node;
404 set_bit(HFS_BNODE_ERROR, &node->flags);
405 clear_bit(HFS_BNODE_NEW, &node->flags);
406 wake_up(&node->lock_wq);
407 hfs_bnode_put(node);
411 void hfs_bnode_free(struct hfs_bnode *node)
415 for (i = 0; i < node->tree->pages_per_bnode; i++)
416 if (node->page[i])
417 put_page(node->page[i]);
418 kfree(node);
423 struct hfs_bnode *node;
428 node = hfs_bnode_findhash(tree, num);
430 if (node) {
431 pr_crit("new node %u already hashed?\n", num);
433 return node;
435 node = __hfs_bnode_create(tree, num);
436 if (!node)
438 if (test_bit(HFS_BNODE_ERROR, &node->flags)) {
439 hfs_bnode_put(node);
443 pagep = node->page;
444 memset(kmap(*pagep) + node->page_offset, 0,
453 clear_bit(HFS_BNODE_NEW, &node->flags);
454 wake_up(&node->lock_wq);
456 return node;
459 void hfs_bnode_get(struct hfs_bnode *node)
461 if (node) {
462 atomic_inc(&node->refcnt);
464 node->tree->cnid, node->this,
465 atomic_read(&node->refcnt));
469 /* Dispose of resources used by a node */
470 void hfs_bnode_put(struct hfs_bnode *node)
472 if (node) {
473 struct hfs_btree *tree = node->tree;
477 node->tree->cnid, node->this,
478 atomic_read(&node->refcnt));
479 BUG_ON(!atomic_read(&node->refcnt));
480 if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock))
483 if (!node->page[i])
485 mark_page_accessed(node->page[i]);
488 if (test_bit(HFS_BNODE_DELETED, &node->flags)) {
489 hfs_bnode_unhash(node);
491 hfs_bmap_free(node);
492 hfs_bnode_free(node);