TreeNode.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408
  1. /*
  2. * Copyright (c) 2021, Jan de Visser <jan@de-visser.net>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/Debug.h>
  7. #include <AK/Format.h>
  8. #include <AK/NonnullOwnPtr.h>
  9. #include <AK/StringBuilder.h>
  10. #include <LibSQL/BTree.h>
  11. #include <LibSQL/Serializer.h>
  12. namespace SQL {
  13. DownPointer::DownPointer(TreeNode* owner, u32 pointer)
  14. : m_owner(owner)
  15. , m_pointer(pointer)
  16. , m_node(nullptr)
  17. {
  18. }
  19. DownPointer::DownPointer(TreeNode* owner, TreeNode* node)
  20. : m_owner(owner)
  21. , m_pointer((node) ? node->pointer() : 0)
  22. , m_node(adopt_own_if_nonnull(node))
  23. {
  24. }
  25. DownPointer::DownPointer(TreeNode* owner, DownPointer& down)
  26. : m_owner(owner)
  27. , m_pointer(down.m_pointer)
  28. , m_node(move(down.m_node))
  29. {
  30. }
  31. DownPointer::DownPointer(DownPointer const& other)
  32. : m_owner(other.m_owner)
  33. , m_pointer(other.pointer())
  34. {
  35. if (other.m_node)
  36. // FIXME This is gross. We modify the other object which we promised
  37. // to be const. However, this particular constructor is needed
  38. // when we take DownPointers from the Vector they live in when
  39. // we split a node. The original object is going to go away, so
  40. // there is no harm done. However, it's yucky. If anybody has
  41. // a better idea...
  42. m_node = move(const_cast<DownPointer&>(other).m_node);
  43. else
  44. m_node = nullptr;
  45. }
  46. TreeNode* DownPointer::node()
  47. {
  48. if (!m_node)
  49. deserialize(m_owner->tree().serializer());
  50. return m_node;
  51. }
  52. void DownPointer::deserialize(Serializer& serializer)
  53. {
  54. if (m_node || !m_pointer)
  55. return;
  56. serializer.get_block(m_pointer);
  57. m_node = serializer.make_and_deserialize<TreeNode>(m_owner->tree(), m_owner, m_pointer);
  58. }
  59. TreeNode::TreeNode(BTree& tree, u32 pointer)
  60. : IndexNode(pointer)
  61. , m_tree(tree)
  62. , m_up(nullptr)
  63. , m_entries()
  64. , m_down()
  65. {
  66. }
  67. TreeNode::TreeNode(BTree& tree, TreeNode* up, u32 pointer)
  68. : IndexNode(pointer)
  69. , m_tree(tree)
  70. , m_up(up)
  71. , m_entries()
  72. , m_down()
  73. {
  74. m_down.append(DownPointer(this, nullptr));
  75. m_is_leaf = true;
  76. }
  77. TreeNode::TreeNode(BTree& tree, TreeNode* up, DownPointer& left, u32 pointer)
  78. : IndexNode(pointer)
  79. , m_tree(tree)
  80. , m_up(up)
  81. , m_entries()
  82. , m_down()
  83. {
  84. if (left.m_node != nullptr)
  85. left.m_node->m_up = this;
  86. m_down.append(DownPointer(this, left));
  87. m_is_leaf = left.pointer() == 0;
  88. if (!pointer)
  89. set_pointer(m_tree.new_record_pointer());
  90. }
  91. TreeNode::TreeNode(BTree& tree, TreeNode* up, TreeNode* left, u32 pointer)
  92. : IndexNode(pointer)
  93. , m_tree(tree)
  94. , m_up(up)
  95. , m_entries()
  96. , m_down()
  97. {
  98. m_down.append(DownPointer(this, left));
  99. m_is_leaf = left->pointer() == 0;
  100. }
  101. void TreeNode::deserialize(Serializer& serializer)
  102. {
  103. auto nodes = serializer.deserialize<u32>();
  104. dbgln_if(SQL_DEBUG, "Deserializing node. Size {}", nodes);
  105. if (nodes > 0) {
  106. for (u32 i = 0; i < nodes; i++) {
  107. auto left = serializer.deserialize<u32>();
  108. dbgln_if(SQL_DEBUG, "Down[{}] {}", i, left);
  109. if (!m_down.is_empty())
  110. VERIFY((left == 0) == m_is_leaf);
  111. else
  112. m_is_leaf = (left == 0);
  113. m_entries.append(serializer.deserialize<Key>(m_tree.descriptor()));
  114. m_down.empend(this, left);
  115. }
  116. auto right = serializer.deserialize<u32>();
  117. dbgln_if(SQL_DEBUG, "Right {}", right);
  118. VERIFY((right == 0) == m_is_leaf);
  119. m_down.empend(this, right);
  120. }
  121. }
  122. void TreeNode::serialize(Serializer& serializer) const
  123. {
  124. u32 sz = size();
  125. serializer.serialize<u32>(sz);
  126. if (sz > 0) {
  127. for (auto ix = 0u; ix < size(); ix++) {
  128. auto& entry = m_entries[ix];
  129. dbgln_if(SQL_DEBUG, "Serializing Left[{}] = {}", ix, m_down[ix].pointer());
  130. serializer.serialize<u32>(is_leaf() ? 0u : m_down[ix].pointer());
  131. serializer.serialize<Key>(entry);
  132. }
  133. dbgln_if(SQL_DEBUG, "Serializing Right = {}", m_down[size()].pointer());
  134. serializer.serialize<u32>(is_leaf() ? 0u : m_down[size()].pointer());
  135. }
  136. }
  137. size_t TreeNode::length() const
  138. {
  139. if (!size())
  140. return 0;
  141. size_t len = sizeof(u32);
  142. for (auto& key : m_entries) {
  143. len += sizeof(u32) + key.length();
  144. }
  145. return len;
  146. }
  147. bool TreeNode::insert(Key const& key)
  148. {
  149. dbgln_if(SQL_DEBUG, "[#{}] INSERT({})", pointer(), key.to_string());
  150. if (!is_leaf())
  151. return node_for(key)->insert_in_leaf(key);
  152. return insert_in_leaf(key);
  153. }
  154. bool TreeNode::update_key_pointer(Key const& key)
  155. {
  156. dbgln_if(SQL_DEBUG, "[#{}] UPDATE({}, {})", pointer(), key.to_string(), key.pointer());
  157. if (!is_leaf())
  158. return node_for(key)->update_key_pointer(key);
  159. for (auto ix = 0u; ix < size(); ix++) {
  160. if (key == m_entries[ix]) {
  161. dbgln_if(SQL_DEBUG, "[#{}] {} == {}",
  162. pointer(), key.to_string(), m_entries[ix].to_string());
  163. if (m_entries[ix].pointer() != key.pointer()) {
  164. m_entries[ix].set_pointer(key.pointer());
  165. dump_if(SQL_DEBUG, "To WAL");
  166. tree().serializer().serialize_and_write<TreeNode>(*this, pointer());
  167. }
  168. return true;
  169. }
  170. }
  171. return false;
  172. }
  173. bool TreeNode::insert_in_leaf(Key const& key)
  174. {
  175. VERIFY(is_leaf());
  176. if (!m_tree.duplicates_allowed()) {
  177. for (auto& entry : m_entries) {
  178. if (key == entry) {
  179. dbgln_if(SQL_DEBUG, "[#{}] duplicate key {}", pointer(), key.to_string());
  180. return false;
  181. }
  182. }
  183. }
  184. dbgln_if(SQL_DEBUG, "[#{}] insert_in_leaf({})", pointer(), key.to_string());
  185. just_insert(key, nullptr);
  186. return true;
  187. }
  188. Key const& TreeNode::operator[](size_t ix) const
  189. {
  190. VERIFY(ix < size());
  191. return m_entries[ix];
  192. }
  193. u32 TreeNode::down_pointer(size_t ix) const
  194. {
  195. VERIFY(ix < m_down.size());
  196. return m_down[ix].pointer();
  197. }
  198. TreeNode* TreeNode::down_node(size_t ix)
  199. {
  200. VERIFY(ix < m_down.size());
  201. return m_down[ix].node();
  202. }
  203. TreeNode* TreeNode::node_for(Key const& key)
  204. {
  205. dump_if(SQL_DEBUG, String::formatted("node_for(Key {})", key.to_string()));
  206. if (is_leaf())
  207. return this;
  208. for (size_t ix = 0; ix < size(); ix++) {
  209. if (key < m_entries[ix]) {
  210. dbgln_if(SQL_DEBUG, "[{}] {} < {} v{}",
  211. pointer(), (String)key, (String)m_entries[ix], m_down[ix].pointer());
  212. return down_node(ix)->node_for(key);
  213. }
  214. }
  215. dbgln_if(SQL_DEBUG, "[#{}] {} >= {} v{}",
  216. pointer(), key.to_string(), (String)m_entries[size() - 1], m_down[size()].pointer());
  217. return down_node(size())->node_for(key);
  218. }
  219. Optional<u32> TreeNode::get(Key& key)
  220. {
  221. dump_if(SQL_DEBUG, String::formatted("get({})", key.to_string()));
  222. for (auto ix = 0u; ix < size(); ix++) {
  223. if (key < m_entries[ix]) {
  224. if (is_leaf()) {
  225. dbgln_if(SQL_DEBUG, "[#{}] {} < {} -> 0",
  226. pointer(), key.to_string(), (String)m_entries[ix]);
  227. return {};
  228. } else {
  229. dbgln_if(SQL_DEBUG, "[{}] {} < {} ({} -> {})",
  230. pointer(), key.to_string(), (String)m_entries[ix],
  231. ix, m_down[ix].pointer());
  232. return down_node(ix)->get(key);
  233. }
  234. }
  235. if (key == m_entries[ix]) {
  236. dbgln_if(SQL_DEBUG, "[#{}] {} == {} -> {}",
  237. pointer(), key.to_string(), (String)m_entries[ix],
  238. m_entries[ix].pointer());
  239. key.set_pointer(m_entries[ix].pointer());
  240. return m_entries[ix].pointer();
  241. }
  242. }
  243. if (m_entries.is_empty()) {
  244. dbgln_if(SQL_DEBUG, "[#{}] {} Empty node??", pointer(), key.to_string());
  245. VERIFY_NOT_REACHED();
  246. }
  247. if (is_leaf()) {
  248. dbgln_if(SQL_DEBUG, "[#{}] {} > {} -> 0",
  249. pointer(), key.to_string(), (String)m_entries[size() - 1]);
  250. return {};
  251. }
  252. dbgln_if(SQL_DEBUG, "[#{}] {} > {} ({} -> {})",
  253. pointer(), key.to_string(), (String)m_entries[size() - 1],
  254. size(), m_down[size()].pointer());
  255. return down_node(size())->get(key);
  256. }
  257. void TreeNode::just_insert(Key const& key, TreeNode* right)
  258. {
  259. dbgln_if(SQL_DEBUG, "[#{}] just_insert({}, right = {})",
  260. pointer(), (String)key, (right) ? right->pointer() : 0);
  261. dump_if(SQL_DEBUG, "Before");
  262. for (auto ix = 0u; ix < size(); ix++) {
  263. if (key < m_entries[ix]) {
  264. m_entries.insert(ix, key);
  265. VERIFY(is_leaf() == (right == nullptr));
  266. m_down.insert(ix + 1, DownPointer(this, right));
  267. if (length() > BLOCKSIZE) {
  268. split();
  269. } else {
  270. dump_if(SQL_DEBUG, "To WAL");
  271. tree().serializer().serialize_and_write(*this, pointer());
  272. }
  273. return;
  274. }
  275. }
  276. m_entries.append(key);
  277. m_down.empend(this, right);
  278. if (length() > BLOCKSIZE) {
  279. split();
  280. } else {
  281. dump_if(SQL_DEBUG, "To WAL");
  282. tree().serializer().serialize_and_write(*this, pointer());
  283. }
  284. }
  285. void TreeNode::split()
  286. {
  287. dump_if(SQL_DEBUG, "Splitting node");
  288. if (!m_up)
  289. // Make new m_up. This is the new root node.
  290. m_up = m_tree.new_root();
  291. // Take the left pointer for the new node:
  292. auto median_index = size() / 2;
  293. if (!(size() % 2))
  294. ++median_index;
  295. DownPointer left = m_down.take(median_index);
  296. // Create the new right node:
  297. auto* new_node = new TreeNode(tree(), m_up, left);
  298. // Move the rightmost keys from this node to the new right node:
  299. while (m_entries.size() > median_index) {
  300. auto entry = m_entries.take(median_index);
  301. auto down = m_down.take(median_index);
  302. // Reparent to new right node:
  303. if (down.m_node != nullptr) {
  304. down.m_node->m_up = new_node;
  305. }
  306. new_node->m_entries.append(entry);
  307. new_node->m_down.append(down);
  308. }
  309. // Move the median key in the node one level up. Its right node will
  310. // be the new node:
  311. auto median = m_entries.take_last();
  312. dump_if(SQL_DEBUG, "Split Left To WAL");
  313. tree().serializer().serialize_and_write(*this, pointer());
  314. new_node->dump_if(SQL_DEBUG, "Split Right to WAL");
  315. tree().serializer().serialize_and_write(*new_node, pointer());
  316. m_up->just_insert(median, new_node);
  317. }
  318. void TreeNode::dump_if(int flag, String&& msg)
  319. {
  320. if (!flag)
  321. return;
  322. StringBuilder builder;
  323. builder.appendff("[#{}] ", pointer());
  324. if (!msg.is_empty())
  325. builder.appendff("{}", msg);
  326. builder.append(": ");
  327. if (m_up)
  328. builder.appendff("[^{}] -> ", m_up->pointer());
  329. else
  330. builder.append("* -> ");
  331. for (size_t ix = 0; ix < m_entries.size(); ix++) {
  332. if (!is_leaf())
  333. builder.appendff("[v{}] ", m_down[ix].pointer());
  334. else
  335. VERIFY(m_down[ix].pointer() == 0);
  336. builder.appendff("'{}' ", (String)m_entries[ix]);
  337. }
  338. if (!is_leaf()) {
  339. builder.appendff("[v{}]", m_down[size()].pointer());
  340. } else {
  341. VERIFY(m_down[size()].pointer() == 0);
  342. }
  343. builder.appendff(" (size {}", (int)size());
  344. if (is_leaf()) {
  345. builder.append(", leaf");
  346. }
  347. builder.append(")");
  348. dbgln(builder.build());
  349. }
  350. void TreeNode::list_node(int indent)
  351. {
  352. auto do_indent = [&]() {
  353. for (int i = 0; i < indent; ++i) {
  354. warn(" ");
  355. }
  356. };
  357. do_indent();
  358. warnln("--> #{}", pointer());
  359. for (auto ix = 0u; ix < size(); ix++) {
  360. if (!is_leaf()) {
  361. down_node(ix)->list_node(indent + 2);
  362. }
  363. do_indent();
  364. warnln("{}", m_entries[ix].to_string());
  365. }
  366. if (!is_leaf()) {
  367. down_node(size())->list_node(indent + 2);
  368. }
  369. }
  370. }