LXR linux/fs/jfs/jfs

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