API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 12th, 2018
76
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 24.68 KB | None | 0 0
raw download clone embed print report
  1. ////////////////////////////////////////////////////////////////////////////////
  2. /// \file
  3. /// \brief Unit-тесты для B-деревьев
  4. /// \author Sergey Shershakov
  5. /// \version 0.1.0
  6. /// \date 01.05.2017
  7. /// This is a part of the course "Algorithms and Data Structures"
  8. /// provided by the School of Software Engineering of the Faculty
  9. /// of Computer Science at the Higher School of Economics.
  10. ///
  11. /// Gtest-based unit test.
  12. /// The naming conventions imply the name of a unit-test module is the same as
  13. /// the name of the corresponding tested module with _test suffix
  14. ///
  15. ///
  16. ////////////////////////////////////////////////////////////////////////////////
  17.  
  18.  
  19.  
  20.  
  21. #include <gtest/gtest.h>
  22.  
  23.  
  24. #include "btree.h"
  25.  
  26. /** \brief Путь к каталогу с рабочими тестовыми файлами. */
  27. static const char* TEST_FILES_PATH = "../../out/";
  28.  
  29.  
  30.  
  31. using namespace xi;
  32.  
  33.  
  34. /** \brief Тестовый класс для тестирования открытых интерфейсов B-tree. */
  35. class BTreeTest : public ::testing::Test {
  36. public:
  37. //BTreeTest()
  38. // : _dumper(DUMP_EVENTLOG_PUB_FN, DUMP_IMGS_PUB_PATH)
  39. //{
  40. //}
  41.  
  42. public:
  43. //static const int STRUCT2_SEQ[];
  44. //static const int STRUCT2_SEQ_NUM;
  45. std::string& getFn(const char* fn)
  46. {
  47. _fn = TEST_FILES_PATH;
  48. _fn.append(fn);
  49. return _fn;
  50. }
  51.  
  52. protected:
  53. std::string _fn; ///< Имя файла
  54. //RBTreeDefDumper<int, std::less<int>> _dumper;
  55.  
  56. ///** \brief Выводить в формате GraphViz. */
  57. //RBTreeGvDumper<int, std::less<int>> _gvDumper;
  58. }; // class RBTreePubTest
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65. TEST_F(BTreeTest, Simplest)
  66. {
  67. //EXPECT_TRUE(tree.isEmpty());
  68. }
  69.  
  70.  
  71. TEST_F(BTreeTest, Order1)
  72. {
  73. std::string fn(TEST_FILES_PATH); // имя файла
  74. fn.append("order1.xibt");
  75.  
  76.  
  77. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  78.  
  79. EXPECT_EQ(10, bt.getRecSize());
  80.  
  81. EXPECT_EQ(2, bt.getOrder());
  82. EXPECT_EQ(3, bt.getMaxKeys());
  83. EXPECT_EQ(1, bt.getMinKeys());
  84. EXPECT_EQ(30, bt.getKeysSize());
  85. EXPECT_EQ(32, bt.getCursorsOfs()); // 30 + 2
  86. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  87.  
  88. EXPECT_EQ(1, bt.getLastPageNum());
  89. EXPECT_EQ(1, bt.getRootPageNum());
  90.  
  91.  
  92. //EXPECT_TRUE(tree.isEmpty());
  93. }
  94.  
  95.  
  96. TEST_F(BTreeTest, AllocPage1)
  97. {
  98. std::string fn(TEST_FILES_PATH);
  99. fn.append("AllocPage1.xibt");
  100.  
  101.  
  102. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  103. FileBaseBTree::PageWrapper wp(&bt);
  104.  
  105.  
  106. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  107. EXPECT_EQ(1, bt.getLastPageNum());
  108.  
  109. // добавим пару страничек
  110. bt.allocPage(wp, 1, true); //true);
  111. EXPECT_EQ(2, bt.getLastPageNum());
  112.  
  113. bt.allocPage(wp, 2, false); //false);
  114. EXPECT_EQ(3, bt.getLastPageNum());
  115.  
  116. bt.allocPage(wp, 3, true); //true);
  117. EXPECT_EQ(4, bt.getLastPageNum());
  118.  
  119.  
  120.  
  121. }
  122.  
  123.  
  124.  
  125. TEST_F(BTreeTest, ReadPage1)
  126. {
  127. std::string fn(TEST_FILES_PATH);
  128. fn.append("ReadPage1.xibt");
  129.  
  130.  
  131. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  132. FileBaseBTree::PageWrapper wp(&bt);
  133.  
  134.  
  135. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  136. EXPECT_EQ(1, bt.getLastPageNum());
  137.  
  138. // добавим пару страничек
  139. bt.allocPage(wp, 1, true); //true);
  140. EXPECT_EQ(2, bt.getLastPageNum());
  141.  
  142. bt.allocPage(wp, 2, false); //false);
  143. EXPECT_EQ(3, bt.getLastPageNum());
  144.  
  145. bt.allocPage(wp, 3, true); //true);
  146. EXPECT_EQ(4, bt.getLastPageNum());
  147.  
  148. // читаем странички (1-я теперь под корень!)
  149. //bt.readWorkPage(2);
  150. wp.readPage(2);
  151. EXPECT_TRUE(wp.isLeaf());
  152. EXPECT_EQ(1, wp.getKeysNum());
  153.  
  154. //bt.readWorkPage(4);
  155. wp.readPage(4);
  156. EXPECT_TRUE(wp.isLeaf());
  157. EXPECT_EQ(3, wp.getKeysNum());
  158.  
  159. //bt.readWorkPage(3);
  160. wp.readPage(3);
  161. EXPECT_FALSE(wp.isLeaf());
  162. EXPECT_EQ(2, wp.getKeysNum());
  163. }
  164.  
  165.  
  166. // тестируем запись модифицированных страничек
  167. TEST_F(BTreeTest, WritePage1)
  168. {
  169. std::string& fn = getFn("WritePage1.xibt");
  170.  
  171.  
  172. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  173. FileBaseBTree::PageWrapper wp(&bt);
  174.  
  175. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  176. EXPECT_EQ(1, bt.getLastPageNum());
  177.  
  178. // добавим пару страничек
  179. bt.allocPage(wp, 1, true); //true);
  180. EXPECT_EQ(2, bt.getLastPageNum());
  181.  
  182. bt.allocPage(wp, 2, false); //false);
  183. EXPECT_EQ(3, bt.getLastPageNum());
  184.  
  185.  
  186. // читаем странички
  187. //bt.readWorkPage(2);
  188. wp.readPage(2);
  189. EXPECT_TRUE(wp.isLeaf());
  190. EXPECT_EQ(1, wp.getKeysNum());
  191.  
  192.  
  193.  
  194. // модифицируем страничку 2
  195. wp.setLeaf(false); // была истина
  196. *(wp.getKey(0)) = 'A'; // нумерация ключей — с нуля!!!
  197. //bt.writeWorkPage(2);
  198. wp.writePage();
  199.  
  200. //bt.readWorkPage(3);
  201. wp.readPage(3);
  202. EXPECT_FALSE(wp.isLeaf());
  203. EXPECT_EQ(2, wp.getKeysNum());
  204.  
  205. // модифицируем страничку 3
  206. wp.setKeyNum(3); // сделали три ключа на пробу!
  207. *(wp.getKey(1)) = 'B';
  208. //bt.writeWorkPage(3);
  209. wp.writePage();
  210.  
  211.  
  212. // еще раз читаем страницы
  213. //bt.readWorkPage(2);
  214. wp.readPage(2);
  215. EXPECT_FALSE(wp.isLeaf()); // теперь это должен быть не лист
  216. EXPECT_EQ(1, wp.getKeysNum());
  217. EXPECT_EQ('A', *(wp.getKey(0)));
  218.  
  219. // еще раз читаем страницы
  220. //bt.readWorkPage(3);
  221. wp.readPage(3);
  222. EXPECT_FALSE(wp.isLeaf());
  223. EXPECT_EQ(3, wp.getKeysNum()); // теперь тут три ключа должно быть!
  224. EXPECT_EQ('B', *(wp.getKey(1)));
  225.  
  226. }
  227.  
  228.  
  229. // тестируем запись модифицированных страничек через рабочие страницы
  230. TEST_F(BTreeTest, WritePage2)
  231. {
  232. std::string& fn = getFn("WritePage2.xibt");
  233.  
  234.  
  235. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  236. FileBaseBTree::PageWrapper wp(&bt);
  237.  
  238. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  239. EXPECT_EQ(1, bt.getLastPageNum());
  240.  
  241. // добавим пару страничек
  242. bt.allocPage(wp, 1, true); //true);
  243. EXPECT_EQ(2, bt.getLastPageNum());
  244.  
  245. bt.allocPage(wp, 2, false); //false);
  246. EXPECT_EQ(3, bt.getLastPageNum());
  247.  
  248.  
  249. FileBaseBTree::PageWrapper wp1(&bt);
  250.  
  251. // читаем и модифицируем страничку 2
  252. wp1.readPage(2);
  253. EXPECT_TRUE(wp1.isLeaf());
  254. EXPECT_EQ(1, wp1.getKeysNum());
  255.  
  256. wp1.setLeaf(false); // была истина
  257. *(wp1.getKey(0)) = 'A'; // нумерация ключей — с нуля!!!
  258. wp1.writePage();
  259.  
  260.  
  261. // читаем и модифицируем страничку 3
  262. wp1.readPage(3);
  263. EXPECT_FALSE(wp1.isLeaf());
  264. EXPECT_EQ(2, wp1.getKeysNum());
  265.  
  266. wp1.setKeyNum(3); // сделали три ключа на пробу!
  267. *(wp1.getKey(1)) = 'B'; // нумерация ключей — с нуля!!!
  268. wp1.writePage();
  269.  
  270. FileBaseBTree::PageWrapper wp2(&bt);
  271.  
  272. // еще раз читаем страницы
  273. wp2.readPage(2);
  274. EXPECT_FALSE(wp2.isLeaf());
  275. EXPECT_EQ(1, wp2.getKeysNum());
  276. EXPECT_EQ('A', *(wp2.getKey(0)));
  277.  
  278. wp2.readPage(3);
  279. EXPECT_FALSE(wp2.isLeaf());
  280. EXPECT_EQ(3, wp2.getKeysNum());
  281. EXPECT_EQ('B', *(wp2.getKey(1)));
  282. }
  283.  
  284. // тестирует создание файла с последующим переотркрытием на том же объекте!
  285. TEST_F(BTreeTest, ReopenFile1)
  286. {
  287. std::string& fn = getFn("ReopenFile1.xibt");
  288.  
  289. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  290. FileBaseBTree::PageWrapper wp(&bt);
  291.  
  292. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  293. EXPECT_EQ(1, bt.getLastPageNum());
  294.  
  295. // добавим пару страничек
  296. bt.allocPage(wp, 1, true); //true);
  297. EXPECT_EQ(2, bt.getLastPageNum());
  298.  
  299. bt.allocPage(wp, 2, false); //false);
  300. EXPECT_EQ(3, bt.getLastPageNum());
  301.  
  302.  
  303. // читаем странички
  304. //bt.readWorkPage(2);
  305. wp.readPage(2);
  306. EXPECT_TRUE(wp.isLeaf());
  307. EXPECT_EQ(1, wp.getKeysNum());
  308.  
  309. //bt.readWorkPage(3);
  310. wp.readPage(3);
  311. EXPECT_FALSE(wp.isLeaf());
  312. EXPECT_EQ(2, wp.getKeysNum());
  313.  
  314. bt.close();
  315.  
  316.  
  317. // открываем заново
  318. bt.open(fn); // , nullptr);
  319. EXPECT_EQ(10, bt.getRecSize());
  320.  
  321. EXPECT_EQ(2, bt.getOrder());
  322. EXPECT_EQ(3, bt.getMaxKeys());
  323. EXPECT_EQ(1, bt.getMinKeys());
  324. EXPECT_EQ(30, bt.getKeysSize());
  325. EXPECT_EQ(32, bt.getCursorsOfs()); // 30 + 2
  326. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  327.  
  328. EXPECT_EQ(3, bt.getLastPageNum());
  329. EXPECT_EQ(1, bt.getRootPageNum());
  330.  
  331. }
  332.  
  333. // тестирует создание файла с последующим переотркрытием в другом объекте!
  334. TEST_F(BTreeTest, ReopenFile2)
  335. {
  336. std::string& fn = getFn("ReopenFile2.xibt");
  337.  
  338. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  339. FileBaseBTree::PageWrapper wp(&bt);
  340.  
  341. EXPECT_EQ(48, bt.getNodePageSize()); // 32 + 4 * 4 = 48
  342. EXPECT_EQ(1, bt.getLastPageNum());
  343.  
  344. // добавим пару страничек
  345. bt.allocPage(wp, 1, true); //true);
  346. EXPECT_EQ(2, bt.getLastPageNum());
  347.  
  348. bt.allocPage(wp, 2, false); //false);
  349. EXPECT_EQ(3, bt.getLastPageNum());
  350.  
  351.  
  352. // читаем странички
  353. //bt.readWorkPage(2);
  354. wp.readPage(2);
  355. EXPECT_TRUE(wp.isLeaf());
  356. EXPECT_EQ(1, wp.getKeysNum());
  357.  
  358. //bt.readWorkPage(3);
  359. wp.readPage(3);
  360. EXPECT_FALSE(wp.isLeaf());
  361. EXPECT_EQ(2, wp.getKeysNum());
  362.  
  363. bt.close();
  364.  
  365.  
  366. // создаем новое дерево и открываем
  367. FileBaseBTree bt2(fn, nullptr); // без компаратора!
  368. EXPECT_EQ(10, bt2.getRecSize());
  369.  
  370. EXPECT_EQ(2, bt2.getOrder());
  371. EXPECT_EQ(3, bt2.getMaxKeys());
  372. EXPECT_EQ(1, bt2.getMinKeys());
  373. EXPECT_EQ(30, bt2.getKeysSize());
  374. EXPECT_EQ(32, bt2.getCursorsOfs()); // 30 + 2
  375. EXPECT_EQ(48, bt2.getNodePageSize()); // 32 + 4 * 4 = 48
  376.  
  377. EXPECT_EQ(3, bt2.getLastPageNum());
  378. EXPECT_EQ(1, bt2.getRootPageNum());
  379.  
  380. }
  381.  
  382. TEST_F(BTreeTest, WorkPages1)
  383. {
  384. std::string& fn = getFn("WorkPages1.xibt");
  385.  
  386. FileBaseBTree bt(2, 10, nullptr, fn); // без компаратора!
  387. FileBaseBTree::PageWrapper wp1(&bt);
  388. EXPECT_EQ(1, bt.getLastPageNum());
  389.  
  390. // добавим пару страничек
  391. wp1.allocPage(1, true);
  392. EXPECT_EQ(2, bt.getLastPageNum());
  393. EXPECT_FALSE(wp1.isFull());
  394.  
  395.  
  396. wp1.allocPage(3, false);
  397. EXPECT_EQ(3, bt.getLastPageNum());
  398. EXPECT_TRUE(wp1.isFull());
  399. }
  400.  
  401.  
  402. TEST_F(BTreeTest, KeysNCursors1)
  403. {
  404. std::string& fn = getFn("KeysNCursors1.xibt");
  405.  
  406. FileBaseBTree bt(2, 10, nullptr, fn);
  407. FileBaseBTree::PageWrapper wp1(&bt);
  408. //FileBaseBTree::PageWrapper wp2(&bt);
  409.  
  410. wp1.allocPage(1, false);
  411. *(wp1.getKey(0)) = 'A';
  412. EXPECT_EQ(nullptr, wp1.getKey(1));
  413. //ASSERT_THROW(*(wp1.getKey(1)) = 'B', DerivedClassException);
  414.  
  415. wp1.setCursor(0, 1);
  416. wp1.setCursor(1, 2);
  417. ASSERT_THROW(wp1.setCursor(2, 42), std::invalid_argument);
  418. wp1.writePage();
  419.  
  420. //EXPECT_E
  421. }
  422.  
  423. TEST_F(BTreeTest, KeysNCursors2)
  424. {
  425. std::string& fn = getFn("KeysNCursors2.xibt");
  426.  
  427.  
  428. FileBaseBTree bt(3, 2, nullptr, fn);
  429. FileBaseBTree::PageWrapper wp1(&bt);
  430.  
  431. wp1.allocPage(3, false);
  432. *((UShort*)wp1.getKey(0)) = 0x0201;
  433. *((UShort*)wp1.getKey(1)) = 0x0207;
  434. *((UShort*)wp1.getKey(2)) = 0x0208;
  435.  
  436. wp1.setCursor(0, 0xF0F0F0F0); // отладочные бетолковые значения
  437. wp1.setCursor(1, 0xF1F1F1F1);
  438. wp1.setCursor(2, 0xF2F2F2F2);
  439. wp1.setCursor(3, 0xF3F3F3F3);
  440.  
  441. wp1.writePage();
  442.  
  443. FileBaseBTree::PageWrapper wp2(&bt);
  444. wp2.allocPage(5, false); // nLeaf);
  445. *((UShort*)wp2.getKey(0)) = 0x0302;
  446. *((UShort*)wp2.getKey(1)) = 0x0303;
  447. *((UShort*)wp2.getKey(2)) = 0x0304;
  448. *((UShort*)wp2.getKey(3)) = 0x0305;
  449. *((UShort*)wp2.getKey(4)) = 0x0306;
  450.  
  451. wp2.setCursor(0, 0xB0B0B0B0); // отладочные бетолковые значения
  452. wp2.setCursor(1, 0xB1B1B1B1);
  453. wp2.setCursor(2, 0xB2B2B2B2);
  454. wp2.setCursor(3, 0xB3B3B3B3);
  455. wp2.setCursor(4, 0xB4B4B4B4);
  456. wp2.setCursor(5, 0xB5B5B5B5);
  457.  
  458.  
  459. wp2.writePage();
  460.  
  461. // уст. курсор
  462. wp1.setCursor(1, wp2.getPageNum()); // ссылаемся на 3 страницу
  463. wp1.writePage();
  464. }
  465.  
  466.  
  467.  
  468. TEST_F(BTreeTest, Split1)
  469. {
  470. std::string& fn = getFn("Split1.xibt");
  471.  
  472.  
  473. FileBaseBTree bt(3, 2, nullptr, fn);
  474. FileBaseBTree::PageWrapper wp1(&bt);
  475.  
  476. wp1.allocPage(3, false);
  477. *((UShort*)wp1.getKey(0)) = 0x0201;
  478. *((UShort*)wp1.getKey(1)) = 0x0207;
  479. *((UShort*)wp1.getKey(2)) = 0x0208;
  480.  
  481.  
  482.  
  483. wp1.setCursor(0, 0xF0F0F0F0); // отладочные бестолковые значения
  484. wp1.setCursor(1, 0xF1F1F1F1);
  485. wp1.setCursor(2, 0xF2F2F2F2);
  486. wp1.setCursor(3, 0xF3F3F3F3);
  487.  
  488. wp1.writePage();
  489.  
  490. FileBaseBTree::PageWrapper wp2(&bt);
  491. wp2.allocPage(5, false); // nLeaf);
  492. *((UShort*)wp2.getKey(0)) = 0x0302;
  493. *((UShort*)wp2.getKey(1)) = 0x0303;
  494. *((UShort*)wp2.getKey(2)) = 0x0304;
  495. *((UShort*)wp2.getKey(3)) = 0x0305;
  496. *((UShort*)wp2.getKey(4)) = 0x0306;
  497.  
  498. wp2.setCursor(0, 0xB0B0B0B0); // отладочные бестолковые значения
  499. wp2.setCursor(1, 0xB1B1B1B1);
  500. wp2.setCursor(2, 0xB2B2B2B2);
  501. wp2.setCursor(3, 0xB3B3B3B3);
  502. wp2.setCursor(4, 0xB4B4B4B4);
  503. wp2.setCursor(5, 0xB5B5B5B5);
  504.  
  505.  
  506. wp2.writePage();
  507.  
  508. // уст. курсор
  509. wp1.setCursor(1, wp2.getPageNum()); // ссылаемся на 3 страницу
  510. wp1.writePage();
  511.  
  512. // выполняем собственно сплит
  513. wp1.splitChild(1); // курсор на 3 страницу
  514.  
  515.  
  516. ASSERT_EQ(wp1.getKeysNum(), 4);
  517.  
  518. ASSERT_EQ(*((UShort*)wp1.getKey(0)),0x0201);
  519. ASSERT_EQ(*((UShort*)wp1.getKey(1)),0x0304);
  520. ASSERT_EQ(*((UShort*)wp1.getKey(2)),0x0207);
  521. ASSERT_EQ(*((UShort*)wp1.getKey(3)),0x0208);
  522.  
  523. ASSERT_EQ(wp1.getCursor(0), 0xF0F0F0F0);
  524. ASSERT_EQ(wp1.getCursor(1), 0x00000003);
  525. ASSERT_EQ(wp1.getCursor(2), 0x00000004);
  526. ASSERT_EQ(wp1.getCursor(3), 0xF2F2F2F2);
  527. ASSERT_EQ(wp1.getCursor(4), 0xF3F3F3F3);
  528.  
  529. wp2.readPage(wp2.getPageNum()); // It was changed
  530.  
  531. ASSERT_EQ(wp2.getKeysNum(), 2);
  532. ASSERT_EQ(*((UShort*)wp2.getKey(0)),0x0302);
  533. ASSERT_EQ(*((UShort*)wp2.getKey(1)),0x0303);
  534. ASSERT_EQ(wp2.getCursor(0), 0xB0B0B0B0);
  535. ASSERT_EQ(wp2.getCursor(1), 0xB1B1B1B1);
  536. ASSERT_EQ(wp2.getCursor(2), 0xB2B2B2B2);
  537.  
  538. wp2.readPageFromChild(wp1, 2);
  539.  
  540. ASSERT_EQ(wp2.getKeysNum(), 2);
  541. ASSERT_EQ(*((UShort*)wp2.getKey(0)),0x0305);
  542. ASSERT_EQ(*((UShort*)wp2.getKey(1)),0x0306);
  543. ASSERT_EQ(wp2.getCursor(0), 0xB3B3B3B3);
  544. ASSERT_EQ(wp2.getCursor(1), 0xB4B4B4B4);
  545. ASSERT_EQ(wp2.getCursor(2), 0xB5B5B5B5);
  546. }
  547.  
  548. TEST_F(BTreeTest, Split2)
  549. {
  550. std::string& fn = getFn("Split2.xibt");
  551.  
  552.  
  553. FileBaseBTree bt(2, 1, nullptr, fn);
  554. FileBaseBTree::PageWrapper wp1(&bt);
  555.  
  556. wp1.allocPage(2, false);
  557. *(wp1.getKey(0)) = 0x01;
  558. *(wp1.getKey(1)) = 0x07;
  559.  
  560.  
  561. wp1.setCursor(0, 0xF0F0F0F0); // отладочные бестолковые значения
  562. wp1.setCursor(1, 0xF1F1F1F1);
  563. wp1.setCursor(2, 0xF2F2F2F2);
  564.  
  565.  
  566. wp1.writePage();
  567.  
  568. FileBaseBTree::PageWrapper wp2(&bt);
  569. wp2.allocPage(3, false); // nLeaf);
  570. *(wp2.getKey(0)) = 0x08;
  571. *(wp2.getKey(1)) = 0x09;
  572. *(wp2.getKey(2)) = 0x0A;
  573.  
  574.  
  575. wp2.setCursor(0, 0xB0B0B0B0); // отладочные бестолковые значения
  576. wp2.setCursor(1, 0xB1B1B1B1);
  577. wp2.setCursor(2, 0xB2B2B2B2);
  578. wp2.setCursor(3, 0xB3B3B3B3);
  579.  
  580.  
  581. wp2.writePage();
  582.  
  583. // уст. курсор
  584. wp1.setCursor(2, wp2.getPageNum()); // ссылаемся на 3 страницу крайним правым курсором
  585. wp1.writePage();
  586.  
  587. // выполняем собственно сплит////
  588. wp1.splitChild(2); // 2-й курсор на 3 страницу
  589. }
  590.  
  591.  
  592.  
  593. // простой сравниватель байт
  594. struct ByteComparator : public BaseBTree::IComparator {
  595. virtual bool compare(const Byte* lhv, const Byte* rhv, UInt sz) override
  596. {
  597. if (*lhv < *rhv)
  598. return true;
  599. return false;
  600. }
  601.  
  602. // простейшая реализация — побайтное сравнение
  603. virtual bool isEqual(const Byte* lhv, const Byte* rhv, UInt sz) override
  604. {
  605. for (UInt i = 0; i < sz; ++i)
  606. if (*lhv != *rhv)
  607. return false;
  608.  
  609. return true;
  610. }
  611.  
  612.  
  613.  
  614. };
  615.  
  616.  
  617. TEST_F(BTreeTest, InsertNonFull1)
  618. {
  619. std::string& fn = getFn("InsertNonFull1.xibt");
  620.  
  621. ByteComparator comparator;
  622.  
  623. FileBaseBTree bt(2, 1, &comparator, fn);
  624. FileBaseBTree::PageWrapper wp1(&bt);
  625.  
  626. wp1.allocPage(2, false);
  627. *(wp1.getKey(0)) = 0x05;
  628. *(wp1.getKey(1)) = 0x11;
  629.  
  630.  
  631. wp1.setCursor(0, 0xF0F0F0F0); // отладочные бестолковые значения
  632. wp1.setCursor(1, 0xF1F1F1F1);
  633. wp1.setCursor(2, 0xF2F2F2F2);
  634.  
  635.  
  636. wp1.writePage();
  637.  
  638. FileBaseBTree::PageWrapper wp2(&bt);
  639. wp2.allocPage(2, true); // nLeaf);
  640. *(wp2.getKey(0)) = 0x01;
  641. *(wp2.getKey(1)) = 0x03;
  642. wp2.writePage();
  643.  
  644. FileBaseBTree::PageWrapper wp3(&bt);
  645. wp3.allocPage(2, true); // nLeaf);
  646. *(wp3.getKey(0)) = 0x07;
  647. *(wp3.getKey(1)) = 0x09;
  648. wp3.writePage();
  649.  
  650. FileBaseBTree::PageWrapper wp4(&bt);
  651. wp4.allocPage(2, true); // nLeaf);
  652. *(wp4.getKey(0)) = 0x13;
  653. *(wp4.getKey(1)) = 0x15;
  654. wp4.writePage();
  655.  
  656.  
  657. wp2.setCursor(0, 0xB0B0B0B0); // отладочные бестолковые значения
  658. wp2.setCursor(1, 0xB1B1B1B1);
  659. wp2.setCursor(2, 0xB2B2B2B2);
  660. wp2.writePage();
  661.  
  662. // уст. курсор
  663. wp1.setCursor(0, wp2.getPageNum());
  664. wp1.setCursor(1, wp3.getPageNum());
  665. wp1.setCursor(2, wp4.getPageNum());
  666. wp1.writePage();
  667.  
  668.  
  669. // вставляем 1 в "верхний" узел
  670. Byte k = 0x02;
  671. wp1.insertNonFull(&k);
  672. wp2.readPage(wp2.getPageNum());
  673.  
  674. ASSERT_EQ(wp1.getKeysNum(), 2);
  675. ASSERT_EQ(*(wp1.getKey(0)), 0x05);
  676. ASSERT_EQ(*(wp1.getKey(1)), 0x11);
  677. ASSERT_EQ(wp1.getCursor(0), 3);
  678. ASSERT_EQ(wp1.getCursor(1), 4);
  679.  
  680. ASSERT_EQ(wp2.getKeysNum(), 3);
  681. ASSERT_EQ(*(wp2.getKey(0)), 0x01);
  682. ASSERT_EQ(*(wp2.getKey(1)), 0x02);
  683. ASSERT_EQ(*(wp2.getKey(2)), 0x03);
  684.  
  685. // теперь в заполненный добавим
  686. //k = 0x04; // это норм
  687. k = 0x02;
  688. wp1.insertNonFull(&k);
  689. wp2.readPage(wp2.getPageNum());
  690.  
  691. ASSERT_EQ(wp1.getKeysNum(), 3);
  692. ASSERT_EQ(*(wp1.getKey(0)), 0x02);
  693. ASSERT_EQ(*(wp1.getKey(1)), 0x05);
  694. ASSERT_EQ(*(wp1.getKey(2)), 0x11);
  695. ASSERT_EQ(wp1.getCursor(0), 3);
  696. ASSERT_EQ(wp1.getCursor(1), 6);
  697. ASSERT_EQ(wp1.getCursor(2), 4);
  698.  
  699. ASSERT_EQ(wp2.getKeysNum(), 1);
  700. ASSERT_EQ(*(wp2.getKey(0)), 0x01);
  701.  
  702.  
  703. wp2.readPage(6);
  704. ASSERT_EQ(wp2.getKeysNum(), 2);
  705. ASSERT_EQ(*(wp2.getKey(0)), 0x02);
  706. ASSERT_EQ(*(wp2.getKey(1)), 0x03);
  707. }
  708.  
  709.  
  710. TEST_F(BTreeTest, Insert1)
  711. {
  712. std::string& fn = getFn("Insert1.xibt");
  713.  
  714. ByteComparator comparator;
  715. FileBaseBTree bt(2, 1, &comparator, fn);
  716.  
  717.  
  718. Byte k = 0x03;
  719. bt.insert(&k);
  720.  
  721. k = 0x02;
  722. bt.insert(&k);
  723.  
  724. k = 0x01;
  725. bt.insert(&k);
  726. }
  727.  
  728. TEST_F(BTreeTest, Insert2)
  729. {
  730. std::string& fn = getFn("Insert2.xibt");
  731.  
  732. ByteComparator comparator;
  733. FileBaseBTree bt(2, 1, &comparator, fn);
  734.  
  735.  
  736. Byte k = 0x03;
  737. bt.insert(&k);
  738.  
  739. k = 0x02;
  740. bt.insert(&k);
  741.  
  742. k = 0x01;
  743. bt.insert(&k);
  744.  
  745. k = 0x04;
  746. bt.insert(&k);
  747.  
  748. FileBaseBTree::PageWrapper wp1(&bt);
  749. wp1.readPage(1);
  750.  
  751. ASSERT_EQ(wp1.getKeysNum(), 1);
  752. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  753. ASSERT_TRUE(wp1.isLeaf());
  754.  
  755. wp1.readPage(2);
  756.  
  757. ASSERT_EQ(wp1.getKeysNum(), 1);
  758. ASSERT_EQ(*(wp1.getKey(0)),0x02);
  759.  
  760. ASSERT_EQ(wp1.getCursor(0), 1);
  761. ASSERT_EQ(wp1.getCursor(1), 3);
  762. ASSERT_TRUE(wp1.isRoot());
  763.  
  764. wp1.readPage(3);
  765.  
  766. ASSERT_EQ(wp1.getKeysNum(), 2);
  767. ASSERT_EQ(*(wp1.getKey(0)),0x03);
  768. ASSERT_EQ(*(wp1.getKey(1)),0x04);
  769. ASSERT_TRUE(wp1.isLeaf());
  770. }
  771.  
  772.  
  773. TEST_F(BTreeTest, Insert3)
  774. {
  775. std::string& fn = getFn("Insert3.xibt");
  776.  
  777. ByteComparator comparator;
  778. FileBaseBTree bt(2, 1, &comparator, fn);
  779.  
  780. FileBaseBTree::PageWrapper wp1(&bt);
  781. wp1.readPage(1);
  782.  
  783. Byte els[] = { 0x01, 0x11, 0x09, 0x05, 0x07, 0x03, 0x03 };
  784. // for (int i = 0; i < sizeof(els) / sizeof(els[0]); ++i)
  785. // {
  786. // Byte& el = els[i];
  787. // bt.insert(&el);
  788. // }
  789.  
  790.  
  791. Byte k = 0x01;
  792. bt.insert(&k);
  793.  
  794. wp1.readPage(1);
  795.  
  796. ASSERT_EQ(wp1.getKeysNum(), 1);
  797. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  798. ASSERT_TRUE(wp1.isRoot());
  799.  
  800. k = 0x11;
  801. bt.insert(&k);
  802.  
  803. wp1.readPage(1);
  804.  
  805. ASSERT_EQ(wp1.getKeysNum(), 2);
  806. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  807. ASSERT_EQ(*(wp1.getKey(1)),0x11);
  808. ASSERT_TRUE(wp1.isRoot());
  809.  
  810. k = 0x09;
  811. bt.insert(&k);
  812.  
  813. wp1.readPage(1);
  814.  
  815. ASSERT_EQ(wp1.getKeysNum(), 3);
  816. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  817. ASSERT_EQ(*(wp1.getKey(1)),0x09);
  818. ASSERT_EQ(*(wp1.getKey(2)),0x11);
  819. ASSERT_TRUE(wp1.isRoot());
  820.  
  821. k = 0x05;
  822. bt.insert(&k);
  823.  
  824. wp1.readPage(1);
  825.  
  826. ASSERT_EQ(wp1.getKeysNum(), 2);
  827. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  828. ASSERT_EQ(*(wp1.getKey(1)),0x05);
  829. ASSERT_TRUE(wp1.isLeaf());
  830.  
  831. wp1.readPage(2);
  832. ASSERT_EQ(wp1.getKeysNum(), 1);
  833. ASSERT_EQ(*(wp1.getKey(0)),0x09);
  834. ASSERT_EQ(wp1.getCursor(0), 1);
  835. ASSERT_EQ(wp1.getCursor(1), 3);
  836. ASSERT_TRUE(wp1.isRoot());
  837.  
  838. wp1.readPage(3);
  839. ASSERT_EQ(wp1.getKeysNum(), 1);
  840. ASSERT_EQ(*(wp1.getKey(0)),0x11);
  841. ASSERT_TRUE(wp1.isLeaf());
  842.  
  843. k = 0x07;
  844. bt.insert(&k);
  845.  
  846. wp1.readPage(1);
  847.  
  848. ASSERT_EQ(wp1.getKeysNum(), 3);
  849. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  850. ASSERT_EQ(*(wp1.getKey(1)),0x05);
  851. ASSERT_EQ(*(wp1.getKey(2)),0x07);
  852. ASSERT_TRUE(wp1.isLeaf());
  853.  
  854. wp1.readPage(2);
  855. ASSERT_EQ(wp1.getKeysNum(), 1);
  856. ASSERT_EQ(*(wp1.getKey(0)),0x09);
  857. ASSERT_EQ(wp1.getCursor(0), 1);
  858. ASSERT_EQ(wp1.getCursor(1), 3);
  859. ASSERT_TRUE(wp1.isRoot());
  860.  
  861. wp1.readPage(3);
  862. ASSERT_EQ(wp1.getKeysNum(), 1);
  863. ASSERT_EQ(*(wp1.getKey(0)),0x11);
  864. ASSERT_TRUE(wp1.isLeaf());
  865.  
  866. k = 0x03;
  867. bt.insert(&k);
  868.  
  869. wp1.readPage(1);
  870.  
  871. ASSERT_EQ(wp1.getKeysNum(), 2);
  872. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  873. ASSERT_EQ(*(wp1.getKey(1)),0x03);
  874.  
  875. ASSERT_TRUE(wp1.isLeaf());
  876.  
  877. wp1.readPage(2);
  878. ASSERT_EQ(wp1.getKeysNum(), 2);
  879. ASSERT_EQ(*(wp1.getKey(0)),0x05);
  880. ASSERT_EQ(*(wp1.getKey(1)),0x09);
  881. ASSERT_EQ(wp1.getCursor(0), 1);
  882. ASSERT_EQ(wp1.getCursor(1), 4);
  883. ASSERT_EQ(wp1.getCursor(2), 3);
  884. ASSERT_TRUE(wp1.isRoot());
  885.  
  886. wp1.readPage(4);
  887. ASSERT_EQ(wp1.getKeysNum(), 1);
  888. ASSERT_EQ(*(wp1.getKey(0)),0x07);
  889. ASSERT_TRUE(wp1.isLeaf());
  890.  
  891. wp1.readPage(3);
  892. ASSERT_EQ(wp1.getKeysNum(), 1);
  893. ASSERT_EQ(*(wp1.getKey(0)),0x11);
  894. ASSERT_TRUE(wp1.isLeaf());
  895.  
  896. k = 0x03;
  897. bt.insert(&k);
  898.  
  899. wp1.readPage(1);
  900.  
  901. ASSERT_EQ(wp1.getKeysNum(), 3);
  902. ASSERT_EQ(*(wp1.getKey(0)),0x01);
  903. ASSERT_EQ(*(wp1.getKey(1)),0x03);
  904. ASSERT_EQ(*(wp1.getKey(2)),0x03);
  905.  
  906. ASSERT_TRUE(wp1.isLeaf());
  907.  
  908. wp1.readPage(2);
  909. ASSERT_EQ(wp1.getKeysNum(), 2);
  910. ASSERT_EQ(*(wp1.getKey(0)),0x05);
  911. ASSERT_EQ(*(wp1.getKey(1)),0x09);
  912. ASSERT_EQ(wp1.getCursor(0), 1);
  913. ASSERT_EQ(wp1.getCursor(1), 4);
  914. ASSERT_EQ(wp1.getCursor(2), 3);
  915. ASSERT_TRUE(wp1.isRoot());
  916.  
  917. wp1.readPage(4);
  918. ASSERT_EQ(wp1.getKeysNum(), 1);
  919. ASSERT_EQ(*(wp1.getKey(0)),0x07);
  920. ASSERT_TRUE(wp1.isLeaf());
  921.  
  922. wp1.readPage(3);
  923. ASSERT_EQ(wp1.getKeysNum(), 1);
  924. ASSERT_EQ(*(wp1.getKey(0)),0x11);
  925. ASSERT_TRUE(wp1.isLeaf());
  926. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!