jfs_btree.h 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173
  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. * jfs_btree.h: B+-tree
  22. *
  23. * JFS B+-tree (dtree and xtree) common definitions
  24. */
  25. /*
  26. * basic btree page - btpage
  27. *
  28. struct btpage {
  29. s64 next; right sibling bn
  30. s64 prev; left sibling bn
  31. u8 flag;
  32. u8 rsrvd[7]; type specific
  33. s64 self; self address
  34. u8 entry[4064];
  35. }; */
  36. /* btpaget_t flag */
  37. #define BT_TYPE 0x07 /* B+-tree index */
  38. #define BT_ROOT 0x01 /* root page */
  39. #define BT_LEAF 0x02 /* leaf page */
  40. #define BT_INTERNAL 0x04 /* internal page */
  41. #define BT_RIGHTMOST 0x10 /* rightmost page */
  42. #define BT_LEFTMOST 0x20 /* leftmost page */
  43. #define BT_SWAPPED 0x80 /* used by fsck for endian swapping */
  44. /* btorder (in inode) */
  45. #define BT_RANDOM 0x0000
  46. #define BT_SEQUENTIAL 0x0001
  47. #define BT_LOOKUP 0x0010
  48. #define BT_INSERT 0x0020
  49. #define BT_DELETE 0x0040
  50. /*
  51. * btree page buffer cache access
  52. */
  53. #define BT_IS_ROOT(MP) (((MP)->xflag & COMMIT_PAGE) == 0)
  54. /* get page from buffer page */
  55. #define BT_PAGE(IP, MP, TYPE, ROOT)\
  56. (BT_IS_ROOT(MP) ? (TYPE *)&JFS_IP(IP)->ROOT : (TYPE *)(MP)->data)
  57. /* get the page buffer and the page for specified block address */
  58. #define BT_GETPAGE(IP, BN, MP, TYPE, SIZE, P, RC, ROOT)\
  59. {\
  60. if ((BN) == 0)\
  61. {\
  62. MP = (struct metapage *)&JFS_IP(IP)->bxflag;\
  63. P = (TYPE *)&JFS_IP(IP)->ROOT;\
  64. RC = 0;\
  65. }\
  66. else\
  67. {\
  68. MP = read_metapage((IP), BN, SIZE, 1);\
  69. if (MP) {\
  70. RC = 0;\
  71. P = (MP)->data;\
  72. } else {\
  73. P = NULL;\
  74. jfs_err("bread failed!");\
  75. RC = -EIO;\
  76. }\
  77. }\
  78. }
  79. #define BT_MARK_DIRTY(MP, IP)\
  80. {\
  81. if (BT_IS_ROOT(MP))\
  82. mark_inode_dirty(IP);\
  83. else\
  84. mark_metapage_dirty(MP);\
  85. }
  86. /* put the page buffer */
  87. #define BT_PUTPAGE(MP)\
  88. {\
  89. if (! BT_IS_ROOT(MP)) \
  90. release_metapage(MP); \
  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. */
  98. struct 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. struct btstack {
  105. struct btframe *top;
  106. int nsplit;
  107. struct btframe stack[MAXTREEHEIGHT];
  108. };
  109. #define BT_CLR(btstack)\
  110. (btstack)->top = (btstack)->stack
  111. #define BT_STACK_FULL(btstack)\
  112. ( (btstack)->top == &((btstack)->stack[MAXTREEHEIGHT-1]))
  113. #define BT_PUSH(BTSTACK, BN, INDEX)\
  114. {\
  115. assert(!BT_STACK_FULL(BTSTACK));\
  116. (BTSTACK)->top->bn = BN;\
  117. (BTSTACK)->top->index = INDEX;\
  118. ++(BTSTACK)->top;\
  119. }
  120. #define BT_POP(btstack)\
  121. ( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top )
  122. #define BT_STACK(btstack)\
  123. ( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top )
  124. static inline void BT_STACK_DUMP(struct btstack *btstack)
  125. {
  126. int i;
  127. printk("btstack dump:\n");
  128. for (i = 0; i < MAXTREEHEIGHT; i++)
  129. printk(KERN_ERR "bn = %Lx, index = %d\n",
  130. (long long)btstack->stack[i].bn,
  131. btstack->stack[i].index);
  132. }
  133. /* retrieve search results */
  134. #define BT_GETSEARCH(IP, LEAF, BN, MP, TYPE, P, INDEX, ROOT)\
  135. {\
  136. BN = (LEAF)->bn;\
  137. MP = (LEAF)->mp;\
  138. if (BN)\
  139. P = (TYPE *)MP->data;\
  140. else\
  141. P = (TYPE *)&JFS_IP(IP)->ROOT;\
  142. INDEX = (LEAF)->index;\
  143. }
  144. /* put the page buffer of search */
  145. #define BT_PUTSEARCH(BTSTACK)\
  146. {\
  147. if (! BT_IS_ROOT((BTSTACK)->top->mp))\
  148. release_metapage((BTSTACK)->top->mp);\
  149. }
  150. #endif /* _H_JFS_BTREE */