btree.c (e473c1f265f429427e09531435ceaf0fdbb86d15) btree.c (3033342a0b76048e32ce1faebfa85cf8f1aa93b5)
1/*
2 * btree.c - NILFS B-tree.
3 *
4 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or

--- 1513 unchanged lines hidden (view full) ---

1522
1523 nchildren = nilfs_btree_node_get_nchildren(btree, node);
1524 maxkey = nilfs_btree_node_get_key(btree, node, nchildren - 1);
1525 nextmaxkey = (nchildren > 1) ?
1526 nilfs_btree_node_get_key(btree, node, nchildren - 2) : 0;
1527 if (bh != NULL)
1528 brelse(bh);
1529
1/*
2 * btree.c - NILFS B-tree.
3 *
4 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or

--- 1513 unchanged lines hidden (view full) ---

1522
1523 nchildren = nilfs_btree_node_get_nchildren(btree, node);
1524 maxkey = nilfs_btree_node_get_key(btree, node, nchildren - 1);
1525 nextmaxkey = (nchildren > 1) ?
1526 nilfs_btree_node_get_key(btree, node, nchildren - 2) : 0;
1527 if (bh != NULL)
1528 brelse(bh);
1529
1530 return (maxkey == key) && (nextmaxkey < bmap->b_low);
1530 return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
1531}
1532
1533static int nilfs_btree_gather_data(struct nilfs_bmap *bmap,
1534 __u64 *keys, __u64 *ptrs, int nitems)
1535{
1536 struct buffer_head *bh;
1537 struct nilfs_btree *btree;
1538 struct nilfs_btree_node *node, *root;

--- 90 unchanged lines hidden (view full) ---

1629 return ret;
1630
1631}
1632
1633static void
1634nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *bmap,
1635 __u64 key, __u64 ptr,
1636 const __u64 *keys, const __u64 *ptrs,
1531}
1532
1533static int nilfs_btree_gather_data(struct nilfs_bmap *bmap,
1534 __u64 *keys, __u64 *ptrs, int nitems)
1535{
1536 struct buffer_head *bh;
1537 struct nilfs_btree *btree;
1538 struct nilfs_btree_node *node, *root;

--- 90 unchanged lines hidden (view full) ---

1629 return ret;
1630
1631}
1632
1633static void
1634nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *bmap,
1635 __u64 key, __u64 ptr,
1636 const __u64 *keys, const __u64 *ptrs,
1637 int n, __u64 low, __u64 high,
1637 int n,
1638 union nilfs_bmap_ptr_req *dreq,
1639 union nilfs_bmap_ptr_req *nreq,
1640 struct buffer_head *bh)
1641{
1642 struct nilfs_btree *btree;
1643 struct nilfs_btree_node *node;
1644 __u64 tmpptr;
1645
1646 /* free resources */
1647 if (bmap->b_ops->bop_clear != NULL)
1648 bmap->b_ops->bop_clear(bmap);
1649
1650 /* ptr must be a pointer to a buffer head. */
1651 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1652
1653 /* convert and insert */
1654 btree = (struct nilfs_btree *)bmap;
1638 union nilfs_bmap_ptr_req *dreq,
1639 union nilfs_bmap_ptr_req *nreq,
1640 struct buffer_head *bh)
1641{
1642 struct nilfs_btree *btree;
1643 struct nilfs_btree_node *node;
1644 __u64 tmpptr;
1645
1646 /* free resources */
1647 if (bmap->b_ops->bop_clear != NULL)
1648 bmap->b_ops->bop_clear(bmap);
1649
1650 /* ptr must be a pointer to a buffer head. */
1651 set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1652
1653 /* convert and insert */
1654 btree = (struct nilfs_btree *)bmap;
1655 nilfs_btree_init(bmap, low, high);
1655 nilfs_btree_init(bmap);
1656 if (nreq != NULL) {
1657 bmap->b_pops->bpop_commit_alloc_ptr(bmap, dreq);
1658 bmap->b_pops->bpop_commit_alloc_ptr(bmap, nreq);
1659
1660 /* create child node at level 1 */
1661 lock_buffer(bh);
1662 node = (struct nilfs_btree_node *)bh->b_data;
1663 nilfs_btree_node_init(btree, node, 0, 1, n, keys, ptrs);

--- 32 unchanged lines hidden (view full) ---

1696/**
1697 * nilfs_btree_convert_and_insert -
1698 * @bmap:
1699 * @key:
1700 * @ptr:
1701 * @keys:
1702 * @ptrs:
1703 * @n:
1656 if (nreq != NULL) {
1657 bmap->b_pops->bpop_commit_alloc_ptr(bmap, dreq);
1658 bmap->b_pops->bpop_commit_alloc_ptr(bmap, nreq);
1659
1660 /* create child node at level 1 */
1661 lock_buffer(bh);
1662 node = (struct nilfs_btree_node *)bh->b_data;
1663 nilfs_btree_node_init(btree, node, 0, 1, n, keys, ptrs);

--- 32 unchanged lines hidden (view full) ---

1696/**
1697 * nilfs_btree_convert_and_insert -
1698 * @bmap:
1699 * @key:
1700 * @ptr:
1701 * @keys:
1702 * @ptrs:
1703 * @n:
1704 * @low:
1705 * @high:
1706 */
1707int nilfs_btree_convert_and_insert(struct nilfs_bmap *bmap,
1708 __u64 key, __u64 ptr,
1704 */
1705int nilfs_btree_convert_and_insert(struct nilfs_bmap *bmap,
1706 __u64 key, __u64 ptr,
1709 const __u64 *keys, const __u64 *ptrs,
1710 int n, __u64 low, __u64 high)
1707 const __u64 *keys, const __u64 *ptrs, int n)
1711{
1712 struct buffer_head *bh;
1713 union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
1714 struct nilfs_bmap_stats stats;
1715 int ret;
1716
1717 if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1718 di = &dreq;

--- 8 unchanged lines hidden (view full) ---

1727 BUG();
1728 }
1729
1730 ret = nilfs_btree_prepare_convert_and_insert(bmap, key, di, ni, &bh,
1731 &stats);
1732 if (ret < 0)
1733 return ret;
1734 nilfs_btree_commit_convert_and_insert(bmap, key, ptr, keys, ptrs, n,
1708{
1709 struct buffer_head *bh;
1710 union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
1711 struct nilfs_bmap_stats stats;
1712 int ret;
1713
1714 if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1715 di = &dreq;

--- 8 unchanged lines hidden (view full) ---

1724 BUG();
1725 }
1726
1727 ret = nilfs_btree_prepare_convert_and_insert(bmap, key, di, ni, &bh,
1728 &stats);
1729 if (ret < 0)
1730 return ret;
1731 nilfs_btree_commit_convert_and_insert(bmap, key, ptr, keys, ptrs, n,
1735 low, high, di, ni, bh);
1732 di, ni, bh);
1736 nilfs_bmap_add_blocks(bmap, stats.bs_nblocks);
1737 return 0;
1738}
1739
1740static int nilfs_btree_propagate_p(struct nilfs_btree *btree,
1741 struct nilfs_btree_path *path,
1742 int level,
1743 struct buffer_head *bh)

--- 496 unchanged lines hidden (view full) ---

2240
2241static const struct nilfs_btree_operations nilfs_btree_ops_p = {
2242 .btop_find_target = NULL,
2243 .btop_set_target = NULL,
2244 .btop_propagate = nilfs_btree_propagate_p,
2245 .btop_assign = nilfs_btree_assign_p,
2246};
2247
1733 nilfs_bmap_add_blocks(bmap, stats.bs_nblocks);
1734 return 0;
1735}
1736
1737static int nilfs_btree_propagate_p(struct nilfs_btree *btree,
1738 struct nilfs_btree_path *path,
1739 int level,
1740 struct buffer_head *bh)

--- 496 unchanged lines hidden (view full) ---

2237
2238static const struct nilfs_btree_operations nilfs_btree_ops_p = {
2239 .btop_find_target = NULL,
2240 .btop_set_target = NULL,
2241 .btop_propagate = nilfs_btree_propagate_p,
2242 .btop_assign = nilfs_btree_assign_p,
2243};
2244
2248int nilfs_btree_init(struct nilfs_bmap *bmap, __u64 low, __u64 high)
2245int nilfs_btree_init(struct nilfs_bmap *bmap)
2249{
2246{
2250 struct nilfs_btree *btree;
2247 struct nilfs_btree *btree = (struct nilfs_btree *)bmap;
2251
2248
2252 btree = (struct nilfs_btree *)bmap;
2253 bmap->b_ops = &nilfs_btree_ops;
2249 bmap->b_ops = &nilfs_btree_ops;
2254 bmap->b_low = low;
2255 bmap->b_high = high;
2256 switch (bmap->b_inode->i_ino) {
2257 case NILFS_DAT_INO:
2258 btree->bt_ops = &nilfs_btree_ops_p;
2259 break;
2260 default:
2261 btree->bt_ops = &nilfs_btree_ops_v;
2262 break;
2263 }
2264
2265 return 0;
2266}
2267
2268void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
2269{
2250 switch (bmap->b_inode->i_ino) {
2251 case NILFS_DAT_INO:
2252 btree->bt_ops = &nilfs_btree_ops_p;
2253 break;
2254 default:
2255 btree->bt_ops = &nilfs_btree_ops_v;
2256 break;
2257 }
2258
2259 return 0;
2260}
2261
2262void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
2263{
2270 bmap->b_low = NILFS_BMAP_LARGE_LOW;
2271 bmap->b_high = NILFS_BMAP_LARGE_HIGH;
2272 bmap->b_ops = &nilfs_btree_ops_gc;
2273}
2264 bmap->b_ops = &nilfs_btree_ops_gc;
2265}