/* IBM_PROLOG_BEGIN_TAG */ /* This is an automatically generated prolog. */ /* */ /* bos720 src/bos/kernel/j2/include/j2_btree.h 1.6.1.1 */ /* */ /* Licensed Materials - Property of IBM */ /* */ /* Restricted Materials of IBM */ /* */ /* COPYRIGHT International Business Machines Corp. 1999,2015 */ /* All Rights Reserved */ /* */ /* US Government Users Restricted Rights - Use, duplication or */ /* disclosure restricted by GSA ADP Schedule Contract with IBM Corp. */ /* */ /* IBM_PROLOG_END_TAG */ /* @(#)79 1.6.1.1 src/bos/kernel/j2/include/j2_btree.h, sysj2, bos720, 1514A_720 3/26/15 04:04:36 */ /* * COMPONENT_NAME: (SYSJ2) JFS2 Physical File System * * FUNCTIONS: * * ORIGINS: 27 * * (C) COPYRIGHT International Business Machines Corp. 1996, 1999 * All Rights Reserved * Licensed Materials - Property of IBM * * US Government Users Restricted Rights - Use, duplication or * disclosure restricted by GSA ADP Schedule Contract with IBM Corp. */ #ifndef _H_J2_BTREE #define _H_J2_BTREE /* * j2_btree.h: B+-tree * * J2 B+-tree (dtree and xtree) common definitions */ /* * basic btree page - btpage_t */ typedef struct { int64 next; /* 8: right sibling bn */ int64 prev; /* 8: left sibling bn */ uint8 flag; /* 1: */ uint8 rsrvd[7]; /* 7: type specific */ int64 self; /* 8: self address */ uint8 entry[4064]; /* 4064: */ } btpage_t; /* (4096) */ /* btpaget_t flag */ #define BT_TYPE 0x07 /* B+-tree index */ #define BT_ROOT 0x01 /* root page */ #define BT_LEAF 0x02 /* leaf page */ #define BT_INTERNAL 0x04 /* internal page */ #define BT_RIGHTMOST 0x10 /* rightmost page */ #define BT_LEFTMOST 0x20 /* leftmost page */ #define MAXTREEHEIGHT 8 #ifdef _KERNEL #include <j2/j2_bufmgr.h> /* * btree page buffer cache access */ /* get page from buffer page */ #define BT_PAGE(IP, BP, TYPE)\ (BP->pb_xflag & PB_BUFFER) ? (TYPE *)BP->pb_data : (TYPE *)&IP->i_btroot /* get the page buffer and the page for specified block address */ #define BT_GETPAGE_CORE(IP, BN, BP, TYPE, SIZE, P, RC,FLAG)\ {\ if ((BN) == 0)\ {\ BP = (jbuf_t *)&IP->i_bxflag;\ P = (TYPE *)&IP->i_btroot;\ RC = 0;\ }\ else\ {\ RC = bmRead(IP, (BN), (SIZE), FLAG, \ PBDT(TYPE), &(BP)); \ if (RC == 0)\ P = (TYPE *)BP->pb_data;\ }\ } /* get the page buffer and the page for specified block address */ #define BT_GETPAGE(IP, BN, BP, TYPE, SIZE, P, RC)\ BT_GETPAGE_CORE(IP, BN, BP, TYPE, SIZE, P, RC,bmREAD_BLOCK) #define BT_GETPAGE_RAW(IP, BN, BP, TYPE, SIZE, P, RC, FLAG)\ BT_GETPAGE_CORE(IP, BN, BP, TYPE, SIZE, P, RC,bmREAD_RAW|FLAG) /* put the page buffer */ #define BT_PUTPAGE(BP)\ {\ if ((BP)->pb_xflag & PB_BUFFER)\ bmRelease(BP);\ } /* * btree traversal/recovery stack * * record the path traversed during the search; * top frame record the leaf page/entry selected. * * record recovery information during update * traversing up the path of the target leaf; */ typedef struct btframe { /* stack frame */ int64 bn; /* */ int16 index; /* */ int16 lastindex; /* */ jbuf_t *bp; /* */ } btframe_t; /* */ typedef struct btstack { btframe_t *top; /* traversal tree grows from low to high */ int32 nsplit; /* */ btframe_t stack[MAXTREEHEIGHT+1]; btframe_t *bottom; /* recovery tree grows from high to low */ } btstack_t; #define BT_CLR(btstack)\ {\ (btstack)->top = (btstack)->stack;\ (btstack)->bottom = &(btstack)->stack[MAXTREEHEIGHT];\ } #define BT_PUSH(BTSTACK, BN, INDEX)\ {\ (BTSTACK)->top->bn = BN;\ (BTSTACK)->top->index = INDEX;\ ++(BTSTACK)->top;\ } #define RT_PUSH(BTSTACK, BP, INDEX, LV)\ {\ (BTSTACK)->bottom->bp = BP;\ (BTSTACK)->bottom->index = INDEX;\ (BTSTACK)->bottom->lastindex = LV;\ --(BTSTACK)->bottom;\ } #define BT_POP(btstack)\ ( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top ) #define RT_POP(btstack)\ ( (btstack)->bottom == &(btstack)->stack[MAXTREEHEIGHT] ? NULL : ++(btstack)->bottom ) #define BT_STACK(btstack)\ ( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top ) /* retrieve search results */ #define BT_GETSEARCH(IP, LEAF, BN, BP, TYPE, P, INDEX)\ {\ BN = (LEAF)->bn;\ BP = (LEAF)->bp;\ if (BN)\ P = (TYPE *)BP->pb_data;\ else\ P = (TYPE *)&IP->i_btroot;\ INDEX = (LEAF)->index;\ } /* put the page buffer of search */ #define BT_PUTSEARCH(BTSTACK)\ {\ if ((BTSTACK)->top->bp->pb_xflag & PB_BUFFER)\ bmRelease((BTSTACK)->top->bp);\ } #endif /* _KERNEL */ #endif /* _H_J2_BTREE */