jfs_btree.h 3.3 KB

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