BTree.h 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203
  1. /*
  2. * Copyright (c) 2021, Jan de Visser <jan@de-visser.net>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include <AK/DeprecatedString.h>
  8. #include <AK/Function.h>
  9. #include <AK/NonnullRefPtr.h>
  10. #include <AK/Optional.h>
  11. #include <AK/RefPtr.h>
  12. #include <AK/Vector.h>
  13. #include <LibCore/Object.h>
  14. #include <LibSQL/Forward.h>
  15. #include <LibSQL/Heap.h>
  16. #include <LibSQL/Index.h>
  17. #include <LibSQL/Key.h>
  18. namespace SQL {
  19. /**
  20. * The BTree class models a B-Tree index. It contains a collection of
  21. * Key objects organized in TreeNode objects. Keys can be inserted,
  22. * located, deleted, and the set can be traversed in sort order. All keys in
  23. * a tree have the same underlying structure. A BTree's TreeNodes and
  24. * the keys it includes are lazily loaded from the Heap when needed.
  25. *
  26. * The classes implementing the B-Tree functionality are BTree, TreeNode,
  27. * BTreeIterator, and DownPointer (a smart pointer-like helper class).
  28. */
  29. class DownPointer {
  30. public:
  31. explicit DownPointer(TreeNode*, u32 = 0);
  32. DownPointer(TreeNode*, TreeNode*);
  33. DownPointer(DownPointer&&);
  34. DownPointer(TreeNode*, DownPointer&);
  35. ~DownPointer() = default;
  36. [[nodiscard]] u32 pointer() const { return m_pointer; }
  37. TreeNode* node();
  38. private:
  39. void deserialize(Serializer&);
  40. TreeNode* m_owner;
  41. u32 m_pointer { 0 };
  42. OwnPtr<TreeNode> m_node { nullptr };
  43. friend TreeNode;
  44. };
  45. class TreeNode : public IndexNode {
  46. public:
  47. TreeNode(BTree&, u32 = 0);
  48. TreeNode(BTree&, TreeNode*, u32 = 0);
  49. TreeNode(BTree&, TreeNode*, TreeNode*, u32 = 0);
  50. ~TreeNode() override = default;
  51. [[nodiscard]] BTree& tree() const { return m_tree; }
  52. [[nodiscard]] TreeNode* up() const { return m_up; }
  53. [[nodiscard]] size_t size() const { return m_entries.size(); }
  54. [[nodiscard]] size_t length() const;
  55. [[nodiscard]] Vector<Key> entries() const { return m_entries; }
  56. [[nodiscard]] u32 down_pointer(size_t) const;
  57. [[nodiscard]] TreeNode* down_node(size_t);
  58. [[nodiscard]] bool is_leaf() const { return m_is_leaf; }
  59. Key const& operator[](size_t index) const { return m_entries[index]; }
  60. bool insert(Key const&);
  61. bool update_key_pointer(Key const&);
  62. TreeNode* node_for(Key const&);
  63. Optional<u32> get(Key&);
  64. void deserialize(Serializer&);
  65. void serialize(Serializer&) const;
  66. private:
  67. TreeNode(BTree&, TreeNode*, DownPointer&, u32 = 0);
  68. void dump_if(int, DeprecatedString&& = "");
  69. bool insert_in_leaf(Key const&);
  70. void just_insert(Key const&, TreeNode* = nullptr);
  71. void split();
  72. void list_node(int);
  73. BTree& m_tree;
  74. TreeNode* m_up;
  75. Vector<Key> m_entries;
  76. bool m_is_leaf { true };
  77. Vector<DownPointer> m_down;
  78. friend BTree;
  79. friend BTreeIterator;
  80. };
  81. class BTree : public Index {
  82. C_OBJECT(BTree);
  83. public:
  84. ~BTree() override = default;
  85. u32 root() const { return (m_root) ? m_root->pointer() : 0; }
  86. bool insert(Key const&);
  87. bool update_key_pointer(Key const&);
  88. Optional<u32> get(Key&);
  89. BTreeIterator find(Key const& key);
  90. BTreeIterator begin();
  91. static BTreeIterator end();
  92. void list_tree();
  93. Function<void(void)> on_new_root;
  94. private:
  95. BTree(Serializer&, NonnullRefPtr<TupleDescriptor> const&, bool unique, u32 pointer);
  96. BTree(Serializer&, NonnullRefPtr<TupleDescriptor> const&, u32 pointer);
  97. void initialize_root();
  98. TreeNode* new_root();
  99. OwnPtr<TreeNode> m_root { nullptr };
  100. friend BTreeIterator;
  101. friend DownPointer;
  102. friend TreeNode;
  103. };
  104. class BTreeIterator {
  105. public:
  106. [[nodiscard]] bool is_end() const { return m_where == Where::End; }
  107. [[nodiscard]] size_t index() const { return m_index; }
  108. bool update(Key const&);
  109. bool operator==(BTreeIterator const& other) const { return cmp(other) == 0; }
  110. bool operator!=(BTreeIterator const& other) const { return cmp(other) != 0; }
  111. bool operator<(BTreeIterator const& other) const { return cmp(other) < 0; }
  112. bool operator>(BTreeIterator const& other) const { return cmp(other) > 0; }
  113. bool operator<=(BTreeIterator const& other) const { return cmp(other) <= 0; }
  114. bool operator>=(BTreeIterator const& other) const { return cmp(other) >= 0; }
  115. bool operator==(Key const& other) const { return cmp(other) == 0; }
  116. bool operator!=(Key const& other) const { return cmp(other) != 0; }
  117. bool operator<(Key const& other) const { return cmp(other) < 0; }
  118. bool operator>(Key const& other) const { return cmp(other) > 0; }
  119. bool operator<=(Key const& other) const { return cmp(other) <= 0; }
  120. bool operator>=(Key const& other) const { return cmp(other) >= 0; }
  121. BTreeIterator operator++()
  122. {
  123. *this = next();
  124. return *this;
  125. }
  126. BTreeIterator operator++(int)
  127. {
  128. *this = next();
  129. return *this;
  130. }
  131. BTreeIterator operator--()
  132. {
  133. *this = previous();
  134. return *this;
  135. }
  136. BTreeIterator const operator--(int)
  137. {
  138. *this = previous();
  139. return *this;
  140. }
  141. Key const& operator*() const
  142. {
  143. VERIFY(!is_end());
  144. return (*m_current)[m_index];
  145. }
  146. Key const& operator->() const
  147. {
  148. VERIFY(!is_end());
  149. return (*m_current)[m_index];
  150. }
  151. BTreeIterator& operator=(BTreeIterator const&);
  152. BTreeIterator(BTreeIterator const&) = default;
  153. private:
  154. BTreeIterator(TreeNode*, int index);
  155. static BTreeIterator end() { return BTreeIterator(nullptr, -1); }
  156. [[nodiscard]] int cmp(BTreeIterator const&) const;
  157. [[nodiscard]] int cmp(Key const&) const;
  158. [[nodiscard]] BTreeIterator next() const;
  159. [[nodiscard]] BTreeIterator previous() const;
  160. [[nodiscard]] Key key() const;
  161. enum class Where {
  162. Valid,
  163. End
  164. };
  165. Where m_where { Where::Valid };
  166. TreeNode* m_current { nullptr };
  167. int m_index { -1 };
  168. friend BTree;
  169. };
  170. }