btree.h 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. // Copyright 2019 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef SQL_RECOVER_MODULE_BTREE_H_
  5. #define SQL_RECOVER_MODULE_BTREE_H_
  6. #include <cstdint>
  7. #include <ostream>
  8. #include "base/check.h"
  9. #include "base/sequence_checker.h"
  10. namespace sql {
  11. namespace recover {
  12. class DatabasePageReader;
  13. // Streaming decoder for inner pages in SQLite table B-trees.
  14. //
  15. // The decoder outputs the page IDs of the inner page's children pages.
  16. //
  17. // An instance can only be used to decode a single page. Instances are not
  18. // thread-safe.
  19. class InnerPageDecoder {
  20. public:
  21. // Creates a decoder for a DatabasePageReader's last read page.
  22. //
  23. // |db_reader| must have been used to read an inner page of a table B-tree.
  24. // |db_reader| must outlive this instance.
  25. explicit InnerPageDecoder(DatabasePageReader* db_reader) noexcept;
  26. ~InnerPageDecoder() noexcept = default;
  27. InnerPageDecoder(const InnerPageDecoder&) = delete;
  28. InnerPageDecoder& operator=(const InnerPageDecoder&) = delete;
  29. // The ID of the database page decoded by this instance.
  30. int page_id() const {
  31. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  32. return page_id_;
  33. }
  34. // Returns true iff TryAdvance() may be called.
  35. bool CanAdvance() const {
  36. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  37. // The <= below is not a typo. Inner nodes store the right-most child
  38. // pointer in their headers, so their child count is (cell_count + 1).
  39. return next_read_index_ <= cell_count_;
  40. }
  41. // Advances the reader and returns the last read value.
  42. //
  43. // May return an invalid page ID if database was corrupted or the read failed.
  44. // The caller must use DatabasePageReader::IsValidPageId() to verify the
  45. // returned page ID. The caller should continue attempting to read as long as
  46. // CanAdvance() returns true.
  47. int TryAdvance();
  48. // True if the given reader may point to an inner page in a table B-tree.
  49. //
  50. // The last ReadPage() call on |db_reader| must have succeeded.
  51. static bool IsOnValidPage(DatabasePageReader* db_reader);
  52. private:
  53. // Returns the number of cells in the B-tree page.
  54. //
  55. // Checks for database corruption. The caller can assume that the cell pointer
  56. // array with the returned size will not extend past the page buffer.
  57. static int ComputeCellCount(DatabasePageReader* db_reader);
  58. // The number of the B-tree page this reader is reading.
  59. const int page_id_;
  60. // Used to read the tree page.
  61. //
  62. // Raw pointer usage is acceptable because this instance's owner is expected
  63. // to ensure that the DatabasePageReader outlives this.
  64. DatabasePageReader* const db_reader_;
  65. // Caches the ComputeCellCount() value for this reader's page.
  66. const int cell_count_ = ComputeCellCount(db_reader_);
  67. // The reader's cursor state.
  68. //
  69. // Each B-tree page has a header and many cells. In an inner B-tree page, each
  70. // cell points to a child page, and the header points to the last child page.
  71. // So, an inner page with N cells has N+1 children, and |next_read_index_|
  72. // takes values between 0 and |cell_count_| + 1.
  73. int next_read_index_ = 0;
  74. SEQUENCE_CHECKER(sequence_checker_);
  75. };
  76. // Streaming decoder for leaf pages in SQLite table B-trees.
  77. //
  78. // Conceptually, the decoder outputs (rowid, record size, record offset) tuples
  79. // for all the values stored in the leaf page. The tuple members can be accessed
  80. // via last_record_{rowid, size, offset}() methods.
  81. //
  82. // An instance can only be used to decode a single page. Instances are not
  83. // thread-safe.
  84. class LeafPageDecoder {
  85. public:
  86. // Creates a decoder for a DatabasePageReader's last read page.
  87. //
  88. LeafPageDecoder() noexcept;
  89. ~LeafPageDecoder() noexcept = default;
  90. LeafPageDecoder(const LeafPageDecoder&) = delete;
  91. LeafPageDecoder& operator=(const LeafPageDecoder&) = delete;
  92. // The rowid of the most recent record read by TryAdvance().
  93. //
  94. // Must only be called after a successful call to TryAdvance().
  95. int64_t last_record_rowid() const {
  96. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  97. DCHECK(last_record_size_ != 0)
  98. << "TryAdvance() not called / did not succeed";
  99. return last_record_rowid_;
  100. }
  101. // The size of the most recent record read by TryAdvance().
  102. //
  103. // Must only be called after a successful call to TryAdvance().
  104. int64_t last_record_size() const {
  105. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  106. DCHECK(last_record_size_ != 0)
  107. << "TryAdvance() not called / did not succeed";
  108. return last_record_size_;
  109. }
  110. // The page offset of the most recent record read by TryAdvance().
  111. //
  112. // Must only be called after a successful call to TryAdvance().
  113. int64_t last_record_offset() const {
  114. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  115. DCHECK(last_record_size_ != 0)
  116. << "TryAdvance() not called / did not succeed";
  117. return last_record_offset_;
  118. }
  119. // Returns true iff TryAdvance() may be called.
  120. bool CanAdvance() const {
  121. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  122. return next_read_index_ < cell_count_;
  123. }
  124. // Advances the reader and returns the last read value.
  125. //
  126. // Returns false if the read fails. The caller should continue attempting to
  127. // read as long as CanAdvance() returns true.
  128. bool TryAdvance();
  129. // Initialize with DatabasePageReader
  130. // |db_reader| must have been used to read an inner page of a table B-tree.
  131. // |db_reader| must outlive this instance.
  132. void Initialize(DatabasePageReader* db_reader);
  133. // Reset internal DatabasePageReader
  134. void Reset();
  135. // True if DatabasePageReader is valid
  136. bool IsValid() { return (db_reader_ != nullptr); }
  137. // True if the given reader may point to an inner page in a table B-tree.
  138. //
  139. // The last ReadPage() call on |db_reader| must have succeeded.
  140. static bool IsOnValidPage(DatabasePageReader* db_reader);
  141. private:
  142. // Returns the number of cells in the B-tree page.
  143. //
  144. // Checks for database corruption. The caller can assume that the cell pointer
  145. // array with the returned size will not extend past the page buffer.
  146. static int ComputeCellCount(DatabasePageReader* db_reader);
  147. // The number of the B-tree page this reader is reading.
  148. int64_t page_id_;
  149. // Used to read the tree page.
  150. //
  151. // Raw pointer usage is acceptable because this instance's owner is expected
  152. // to ensure that the DatabasePageReader outlives this.
  153. DatabasePageReader* db_reader_;
  154. // Caches the ComputeCellCount() value for this reader's page.
  155. int cell_count_;
  156. // The reader's cursor state.
  157. //
  158. // Each B-tree cell contains a value. So, this member takes values in
  159. // [0, cell_count_).
  160. int next_read_index_ = 0;
  161. int64_t last_record_size_ = 0;
  162. int64_t last_record_rowid_ = 0;
  163. int last_record_offset_ = 0;
  164. SEQUENCE_CHECKER(sequence_checker_);
  165. };
  166. } // namespace recover
  167. } // namespace sql
  168. #endif // SQL_RECOVER_MODULE_BTREE_H_