LXR linux/fs/jfs/jfs

   1/* SPDX-License-Identifier: GPL-2.0-or-later */
   2/*
   3 *   Copyright (C) International Business Machines Corp., 2000-2004
   4 */
   5#ifndef _H_JFS_BTREE
   6#define _H_JFS_BTREE
   7
   8/*
   9 *      jfs_btree.h: B+-tree
  10 *
  11 * JFS B+-tree (dtree and xtree) common definitions
  12 */
  13
  14/*
  15 *      basic btree page - btpage
  16 *
  17struct btpage {
  18        s64 next;               right sibling bn
  19        s64 prev;               left sibling bn
  20
  21        u8 flag;
  22        u8 rsrvd[7];            type specific
  23        s64 self;               self address
  24
  25        u8 entry[4064];
  26};                                              */
  27
  28/* btpaget_t flag */
  29#define BT_TYPE         0x07    /* B+-tree index */
  30#define BT_ROOT         0x01    /* root page */
  31#define BT_LEAF         0x02    /* leaf page */
  32#define BT_INTERNAL     0x04    /* internal page */
  33#define BT_RIGHTMOST    0x10    /* rightmost page */
  34#define BT_LEFTMOST     0x20    /* leftmost page */
  35#define BT_SWAPPED      0x80    /* used by fsck for endian swapping */
  36
  37/* btorder (in inode) */
  38#define BT_RANDOM               0x0000
  39#define BT_SEQUENTIAL           0x0001
  40#define BT_LOOKUP               0x0010
  41#define BT_INSERT               0x0020
  42#define BT_DELETE               0x0040
  43
  44/*
  45 *      btree page buffer cache access
  46 */
  47#define BT_IS_ROOT(MP) (((MP)->xflag & COMMIT_PAGE) == 0)
  48
  49/* get page from buffer page */
  50#define BT_PAGE(IP, MP, TYPE, ROOT)\
  51        (BT_IS_ROOT(MP) ? (TYPE *)&JFS_IP(IP)->ROOT : (TYPE *)(MP)->data)
  52
  53/* get the page buffer and the page for specified block address */
  54#define BT_GETPAGE(IP, BN, MP, TYPE, SIZE, P, RC, ROOT)\
  55{\
  56        if ((BN) == 0)\
  57        {\
  58                MP = (struct metapage *)&JFS_IP(IP)->bxflag;\
  59                P = (TYPE *)&JFS_IP(IP)->ROOT;\
  60                RC = 0;\
  61        }\
  62        else\
  63        {\
  64                MP = read_metapage((IP), BN, SIZE, 1);\
  65                if (MP) {\
  66                        RC = 0;\
  67                        P = (MP)->data;\
  68                } else {\
  69                        P = NULL;\
  70                        jfs_err("bread failed!");\
  71                        RC = -EIO;\
  72                }\
  73        }\
  74}
  75
  76#define BT_MARK_DIRTY(MP, IP)\
  77{\
  78        if (BT_IS_ROOT(MP))\
  79                mark_inode_dirty(IP);\
  80        else\
  81                mark_metapage_dirty(MP);\
  82}
  83
  84/* put the page buffer */
  85#define BT_PUTPAGE(MP)\
  86{\
  87        if (! BT_IS_ROOT(MP)) \
  88                release_metapage(MP); \
  89}
  90
  91
  92/*
  93 *      btree traversal stack
  94 *
  95 * record the path traversed during the search;
  96 * top frame record the leaf page/entry selected.
  97 */
  98struct btframe {        /* stack frame */
  99        s64 bn;                 /* 8: */
 100        s16 index;              /* 2: */
 101        s16 lastindex;          /* 2: unused */
 102        struct metapage *mp;    /* 4/8: */
 103};                              /* (16/24) */
 104
 105struct btstack {
 106        struct btframe *top;
 107        int nsplit;
 108        struct btframe stack[MAXTREEHEIGHT];
 109};
 110
 111#define BT_CLR(btstack)\
 112        (btstack)->top = (btstack)->stack
 113
 114#define BT_STACK_FULL(btstack)\
 115        ( (btstack)->top == &((btstack)->stack[MAXTREEHEIGHT-1]))
 116
 117#define BT_PUSH(BTSTACK, BN, INDEX)\
 118{\
 119        assert(!BT_STACK_FULL(BTSTACK));\
 120        (BTSTACK)->top->bn = BN;\
 121        (BTSTACK)->top->index = INDEX;\
 122        ++(BTSTACK)->top;\
 123}
 124
 125#define BT_POP(btstack)\
 126        ( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top )
 127
 128#define BT_STACK(btstack)\
 129        ( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top )
 130
 131static inline void BT_STACK_DUMP(struct btstack *btstack)
 132{
 133        int i;
 134        printk("btstack dump:\n");
 135        for (i = 0; i < MAXTREEHEIGHT; i++)
 136                printk(KERN_ERR "bn = %Lx, index = %d\n",
 137                       (long long)btstack->stack[i].bn,
 138                       btstack->stack[i].index);
 139}
 140
 141/* retrieve search results */
 142#define BT_GETSEARCH(IP, LEAF, BN, MP, TYPE, P, INDEX, ROOT)\
 143{\
 144        BN = (LEAF)->bn;\
 145        MP = (LEAF)->mp;\
 146        if (BN)\
 147                P = (TYPE *)MP->data;\
 148        else\
 149                P = (TYPE *)&JFS_IP(IP)->ROOT;\
 150        INDEX = (LEAF)->index;\
 151}
 152
 153/* put the page buffer of search */
 154#define BT_PUTSEARCH(BTSTACK)\
 155{\
 156        if (! BT_IS_ROOT((BTSTACK)->top->mp))\
 157                release_metapage((BTSTACK)->top->mp);\
 158}
 159#endif                          /* _H_JFS_BTREE */
 160