1*4882a593Smuzhiyun /* SPDX-License-Identifier: GPL-2.0+ */ 2*4882a593Smuzhiyun /* 3*4882a593Smuzhiyun * btree.h - NILFS B-tree. 4*4882a593Smuzhiyun * 5*4882a593Smuzhiyun * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation. 6*4882a593Smuzhiyun * 7*4882a593Smuzhiyun * Written by Koji Sato. 8*4882a593Smuzhiyun */ 9*4882a593Smuzhiyun 10*4882a593Smuzhiyun #ifndef _NILFS_BTREE_H 11*4882a593Smuzhiyun #define _NILFS_BTREE_H 12*4882a593Smuzhiyun 13*4882a593Smuzhiyun #include <linux/types.h> 14*4882a593Smuzhiyun #include <linux/buffer_head.h> 15*4882a593Smuzhiyun #include <linux/list.h> 16*4882a593Smuzhiyun #include <linux/nilfs2_ondisk.h> /* nilfs_btree_node */ 17*4882a593Smuzhiyun #include "btnode.h" 18*4882a593Smuzhiyun #include "bmap.h" 19*4882a593Smuzhiyun 20*4882a593Smuzhiyun /** 21*4882a593Smuzhiyun * struct nilfs_btree_path - A path on which B-tree operations are executed 22*4882a593Smuzhiyun * @bp_bh: buffer head of node block 23*4882a593Smuzhiyun * @bp_sib_bh: buffer head of sibling node block 24*4882a593Smuzhiyun * @bp_index: index of child node 25*4882a593Smuzhiyun * @bp_oldreq: ptr end request for old ptr 26*4882a593Smuzhiyun * @bp_newreq: ptr alloc request for new ptr 27*4882a593Smuzhiyun * @bp_op: rebalance operation 28*4882a593Smuzhiyun */ 29*4882a593Smuzhiyun struct nilfs_btree_path { 30*4882a593Smuzhiyun struct buffer_head *bp_bh; 31*4882a593Smuzhiyun struct buffer_head *bp_sib_bh; 32*4882a593Smuzhiyun int bp_index; 33*4882a593Smuzhiyun union nilfs_bmap_ptr_req bp_oldreq; 34*4882a593Smuzhiyun union nilfs_bmap_ptr_req bp_newreq; 35*4882a593Smuzhiyun struct nilfs_btnode_chkey_ctxt bp_ctxt; 36*4882a593Smuzhiyun void (*bp_op)(struct nilfs_bmap *, struct nilfs_btree_path *, 37*4882a593Smuzhiyun int, __u64 *, __u64 *); 38*4882a593Smuzhiyun }; 39*4882a593Smuzhiyun 40*4882a593Smuzhiyun #define NILFS_BTREE_ROOT_SIZE NILFS_BMAP_SIZE 41*4882a593Smuzhiyun #define NILFS_BTREE_ROOT_NCHILDREN_MAX \ 42*4882a593Smuzhiyun ((NILFS_BTREE_ROOT_SIZE - sizeof(struct nilfs_btree_node)) / \ 43*4882a593Smuzhiyun (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */))) 44*4882a593Smuzhiyun #define NILFS_BTREE_ROOT_NCHILDREN_MIN 0 45*4882a593Smuzhiyun #define NILFS_BTREE_NODE_EXTRA_PAD_SIZE (sizeof(__le64)) 46*4882a593Smuzhiyun #define NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize) \ 47*4882a593Smuzhiyun (((nodesize) - sizeof(struct nilfs_btree_node) - \ 48*4882a593Smuzhiyun NILFS_BTREE_NODE_EXTRA_PAD_SIZE) / \ 49*4882a593Smuzhiyun (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */))) 50*4882a593Smuzhiyun #define NILFS_BTREE_NODE_NCHILDREN_MIN(nodesize) \ 51*4882a593Smuzhiyun ((NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize) - 1) / 2 + 1) 52*4882a593Smuzhiyun #define NILFS_BTREE_KEY_MIN ((__u64)0) 53*4882a593Smuzhiyun #define NILFS_BTREE_KEY_MAX (~(__u64)0) 54*4882a593Smuzhiyun 55*4882a593Smuzhiyun extern struct kmem_cache *nilfs_btree_path_cache; 56*4882a593Smuzhiyun 57*4882a593Smuzhiyun int nilfs_btree_init(struct nilfs_bmap *); 58*4882a593Smuzhiyun int nilfs_btree_convert_and_insert(struct nilfs_bmap *, __u64, __u64, 59*4882a593Smuzhiyun const __u64 *, const __u64 *, int); 60*4882a593Smuzhiyun void nilfs_btree_init_gc(struct nilfs_bmap *); 61*4882a593Smuzhiyun 62*4882a593Smuzhiyun int nilfs_btree_broken_node_block(struct buffer_head *bh); 63*4882a593Smuzhiyun 64*4882a593Smuzhiyun #endif /* _NILFS_BTREE_H */ 65