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