FPTreeTest.cpp 37.2 KB
Newer Older
1
/*
2
 * Copyright (C) 2017-2019 DBIS Group - TU Ilmenau, All Rights Reserved.
3
 *
4
 * This file is part of our NVM-based Data Structures repository.
5
 *
6
7
8
 * This program is free software: you can redistribute it and/or modify it under the terms of the
 * GNU General Public License as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
9
 *
10
11
12
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
13
 *
14
15
 * You should have received a copy of the GNU General Public License along with this program.
 * If not, see <http://www.gnu.org/licenses/>.
16
17
18
19
20
21
22
23
24
25
 */

#include <algorithm>
#include <unistd.h>
#include <libpmemobj++/make_persistent_atomic.hpp>
#include "catch.hpp"
#include "config.h"
#define UNIT_TESTS 1
#include "FPTree.hpp"

26
using namespace dbis::pbptrees;
27
28
29
30
31

using pmem::obj::delete_persistent_atomic;
using pmem::obj::pool;

TEST_CASE("Finding the leaf node containing a key", "[FPTree]") {
32
33
34
35
36
  using FPTreeType4 = FPTree<int, int, 4, 4>;
  using FPTreeType6 = FPTree<int, int, 6, 6>;
  using FPTreeType10  = FPTree<int, int, 10, 10> ;
  using FPTreeType12 = FPTree<int, int, 12, 12>;
  using FPTreeType20 = FPTree<int, int, 20, 20>;
37
38

  struct root {
39
40
41
42
43
    pptr<FPTreeType4> btree4;
    pptr<FPTreeType6> btree6;
    pptr<FPTreeType10> btree10;
    pptr<FPTreeType12> btree12;
    pptr<FPTreeType20> btree20;
44
45
46
47
48
49
50
51
52
53
54
55
56
  };

  pool<root> pop;
  const std::string path = dbis::gPmemPath + "FPTreeTest";

  //std::remove(path.c_str());
  if (access(path.c_str(), F_OK) != 0) {
    pop = pool<root>::create(path, "FPTree", ((std::size_t)(1024*1024*16)));
  } else {
    pop = pool<root>::open(path, "FPTree");
  }

  auto q = pop.root();
57
  auto &rootRef = *q;
58
59
  const auto alloc_class = pop.ctl_set<struct pobj_alloc_class_desc>("heap.alloc_class.128.desc",
                                                                     FPTreeType4::AllocClass);
60

61
  if (!rootRef.btree4)
62
    transaction::run(pop, [&] { rootRef.btree4 = make_persistent<FPTreeType4>(alloc_class); });
63

64
  if (!rootRef.btree6)
65
    transaction::run(pop, [&] { rootRef.btree6 = make_persistent<FPTreeType6>(alloc_class); });
66

67
  if (!rootRef.btree10)
68
    transaction::run(pop, [&] { rootRef.btree10 = make_persistent<FPTreeType10>(alloc_class); });
69

70
  if (!rootRef.btree12)
71
    transaction::run(pop, [&] { rootRef.btree12 = make_persistent<FPTreeType12>(alloc_class); });
72

73
  if (!rootRef.btree20)
74
    transaction::run(pop, [&] { rootRef.btree20 = make_persistent<FPTreeType20>(alloc_class); });
75

76
  /* -------------------------------------------------------------------------------------------- */
77
  SECTION("Looking up a key in an inner node") {
78
79
    auto &btree = *rootRef.btree10;
    auto node = btree.newBranchNode();
80
    auto &nodeRef = *node;
81
82
83
84
85
86
87
88
89
90
    for (auto i = 0; i < 10; i++) nodeRef.keys[i] = i + 1;
    nodeRef.numKeys = 10;

    REQUIRE(btree.lookupPositionInBranchNode(node, 0) == 0);
    REQUIRE(btree.lookupPositionInBranchNode(node, 1) == 1);
    REQUIRE(btree.lookupPositionInBranchNode(node, 10) == 10);
    REQUIRE(btree.lookupPositionInBranchNode(node, 5) == 5);
    REQUIRE(btree.lookupPositionInBranchNode(node, 20) == 10);

    btree.deleteBranchNode(node);
91
92
  }

93
  /* -------------------------------------------------------------------------------------------- */
94
  SECTION("Looking up a key in a leaf node") {
95
96
    auto &btree = *rootRef.btree10;
    auto node = btree.newLeafNode();
97
    auto &nodeRef = *node;
Philipp Götze's avatar
Philipp Götze committed
98
    for (auto i = 0; i < 10; i++) {
99
      nodeRef.keys.get_rw()[i] = i + 1;
100
101
      nodeRef.bits.get_rw().set(i);
      nodeRef.fp.get_rw()[i] = btree.fpHash(i + 1);
102
    }
103

104
105
106
107
    REQUIRE(btree.lookupPositionInLeafNode(node, 1) == 0);
    REQUIRE(btree.lookupPositionInLeafNode(node, 10) == 9);
    REQUIRE(btree.lookupPositionInLeafNode(node, 5) == 4);
    REQUIRE(btree.lookupPositionInLeafNode(node, 20) == 10);
108

109
    btree.deleteLeafNode(node);
110
111
  }

112
  /* -------------------------------------------------------------------------------------------- */
113
  SECTION("Balancing two inner nodes from left to right") {
114
115
116
117
118
119
120
    auto &btree = *rootRef.btree4;
    std::array<pptr<FPTreeType4::LeafNode>, 7> leafNodes = {
      { btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(),
        btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode() }
    };

    auto node1 = btree.newBranchNode();
121
    auto &node1Ref = *node1;
122
    auto node2 = btree.newBranchNode();
123
    auto &node2Ref = *node2;
124
    auto node3 = btree.newBranchNode();
125
    auto &node3Ref = *node3;
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

    node1Ref.keys[0] = 8;
    node1Ref.keys[1] = 20;
    node1Ref.children[0] = node2;
    node1Ref.children[1] = node3;
    node1Ref.numKeys = 2;

    node2Ref.keys[0] = 3;
    node2Ref.keys[1] = 4;
    node2Ref.keys[2] = 5;
    node2Ref.keys[3] = 6;
    node2Ref.children[0] = leafNodes[0];
    node2Ref.children[1] = leafNodes[1];
    node2Ref.children[2] = leafNodes[2];
    node2Ref.children[3] = leafNodes[3];
    node2Ref.children[4] = leafNodes[4];
    node2Ref.numKeys = 4;

    node3Ref.keys[0] = 10;
    node3Ref.children[0] = leafNodes[5];
    node3Ref.children[1] = leafNodes[6];
    node3Ref.numKeys = 1;

    btree.rootNode = node1;
    btree.depth = 2;

    btree.balanceBranchNodes(node2, node3, node1, 0);

154
155
156
    REQUIRE(node1->numKeys == 2);
    REQUIRE(node2->numKeys == 2);
    REQUIRE(node3->numKeys == 3);
157
158
159
160
161

    std::array<int, 2> expectedKeys1{{5, 20}};
    std::array<int, 2> expectedKeys2{{3, 4}};
    std::array<int, 3> expectedKeys3{{6, 8, 10}};

162
163
164
165
166
167
    std::array<pptr<FPTreeType4::LeafNode>, 3> expectedChildren2 = {
      { leafNodes[0], leafNodes[1], leafNodes[2] }
    };
    std::array<pptr<FPTreeType4::LeafNode>, 4> expectedChildren3 = {
      { leafNodes[3], leafNodes[4], leafNodes[5], leafNodes[6] }
    };
168
169

    REQUIRE(std::equal(std::begin(expectedKeys1), std::end(expectedKeys1),
170
                       std::begin(node1Ref.keys)));
171
    REQUIRE(std::equal(std::begin(expectedKeys2), std::end(expectedKeys2),
172
                       std::begin(node2Ref.keys)));
173
    REQUIRE(std::equal(std::begin(expectedKeys3), std::end(expectedKeys3),
174
                       std::begin(node3Ref.keys)));
175

176
177
178
    std::array<pptr<FPTreeType4::LeafNode>, 3> node2Children;
    std::transform(std::begin(node2Ref.children), std::end(node2Ref.children),
                   std::begin(node2Children), [](FPTreeType4::Node n) { return n.leaf; });
179
180
181
    REQUIRE(std::equal(std::begin(expectedChildren2), std::end(expectedChildren2),
                       std::begin(node2Children)));

182
183
184
    std::array<pptr<FPTreeType4::LeafNode>, 4> node3Children;
    std::transform(std::begin(node3Ref.children), std::end(node3Ref.children),
                   std::begin(node3Children), [](FPTreeType4::Node n) { return n.leaf; });
185
186
187
188
    REQUIRE(std::equal(std::begin(expectedChildren3), std::end(expectedChildren3),
                       std::begin(node3Children)));
  }

189
  /* -------------------------------------------------------------------------------------------- */
190
  SECTION("Balancing two inner nodes from right to left") {
191
192
193
194
195
196
197
    auto &btree = *rootRef.btree4;
    std::array<pptr<FPTreeType4::LeafNode>, 7> leafNodes = {
      { btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(),
        btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode() }
    };

    auto node1 = btree.newBranchNode();
198
    auto &node1Ref = *node1;
199
    auto node2 = btree.newBranchNode();
200
    auto &node2Ref = *node2;
201
    auto node3 = btree.newBranchNode();
202
    auto &node3Ref = *node3;
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

    node1Ref.keys[0] = 4;
    node1Ref.keys[1] = 20;
    node1Ref.children[0] = node2;
    node1Ref.children[1] = node3;
    node1Ref.numKeys = 2;

    node2Ref.keys[0] = 3;
    node2Ref.children[0] = leafNodes[0];
    node2Ref.children[1] = leafNodes[1];

    node2Ref.numKeys = 1;

    node3Ref.keys[0] = 5;
    node3Ref.keys[1] = 6;
    node3Ref.keys[2] = 7;
    node3Ref.keys[3] = 8;
    node3Ref.children[0] = leafNodes[2];
    node3Ref.children[1] = leafNodes[3];
    node3Ref.children[2] = leafNodes[4];
    node3Ref.children[3] = leafNodes[5];
    node3Ref.children[4] = leafNodes[6];

    node3Ref.numKeys = 4;

    btree.rootNode = node1;
    btree.depth = 2;

    btree.balanceBranchNodes(node3, node2, node1, 0);

233
234
235
    REQUIRE(node1->numKeys == 2);
    REQUIRE(node2->numKeys == 3);
    REQUIRE(node3->numKeys == 2);
236
237
238
239
240

    std::array<int, 2> expectedKeys1{{6, 20}};
    std::array<int, 3> expectedKeys2{{3, 4, 5}};
    std::array<int, 2> expectedKeys3{{7, 8}};

241
242
243
244
245
246
    std::array<pptr<FPTreeType4::LeafNode>, 4> expectedChildren2 = {
      { leafNodes[0], leafNodes[1], leafNodes[2], leafNodes[3] }
    };
    std::array<pptr<FPTreeType4::LeafNode>, 3> expectedChildren3 = {
      { leafNodes[4], leafNodes[5], leafNodes[6] }
    };
247
248

    REQUIRE(std::equal(std::begin(expectedKeys1), std::end(expectedKeys1),
249
                       std::begin(node1Ref.keys)));
250
    REQUIRE(std::equal(std::begin(expectedKeys2), std::end(expectedKeys2),
251
                       std::begin(node2Ref.keys)));
252
    REQUIRE(std::equal(std::begin(expectedKeys3), std::end(expectedKeys3),
253
254
255
256
                       std::begin(node3Ref.keys)));
    std::array<pptr<FPTreeType4::LeafNode>, 4> node2Children;
    std::transform(std::begin(node2Ref.children), std::end(node2Ref.children),
                   std::begin(node2Children), [](FPTreeType4::Node n) { return n.leaf; });
257
258
    REQUIRE(std::equal(std::begin(expectedChildren2), std::end(expectedChildren2),
                       std::begin(node2Children)));
259
260
261
    std::array<pptr<FPTreeType4::LeafNode>, 3> node3Children;
    std::transform(std::begin(node3Ref.children), std::end(node3Ref.children),
                   std::begin(node3Children), [](FPTreeType4::Node n) { return n.leaf; });
262
263
264
265
    REQUIRE(std::equal(std::begin(expectedChildren3), std::end(expectedChildren3),
                       std::begin(node3Children)));
  }

266
  /* -------------------------------------------------------------------------------------------- */
267
  SECTION("Handling of underflow at a inner node by rebalance") {
268
269
270
271
272
    auto &btree = *rootRef.btree4;
    std::array<pptr<FPTreeType4::LeafNode>, 6> leafNodes = {
      { btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(),
        btree.newLeafNode(), btree.newLeafNode() }
    };
273

274
275
276
    std::array<FPTreeType4::BranchNode*, 3> innerNodes = {
      { btree.newBranchNode(), btree.newBranchNode(), btree.newBranchNode() }
    };
277

278
279
280
281
    FPTreeType4::SplitInfo splitInfo;
    btree.insertInLeafNode(leafNodes[0], 1, 10, &splitInfo);
    btree.insertInLeafNode(leafNodes[0], 2, 20, &splitInfo);
    btree.insertInLeafNode(leafNodes[0], 3, 30, &splitInfo);
282

283
284
    btree.insertInLeafNode(leafNodes[1], 5, 50, &splitInfo);
    btree.insertInLeafNode(leafNodes[1], 6, 60, &splitInfo);
285

286
287
    btree.insertInLeafNode(leafNodes[2], 7, 70, &splitInfo);
    btree.insertInLeafNode(leafNodes[2], 8, 80, &splitInfo);
288

289
290
    btree.insertInLeafNode(leafNodes[3], 9, 90, &splitInfo);
    btree.insertInLeafNode(leafNodes[3], 10, 100, &splitInfo);
291

292
293
    btree.insertInLeafNode(leafNodes[4], 11, 110, &splitInfo);
    btree.insertInLeafNode(leafNodes[4], 12, 120, &splitInfo);
294

295
296
    btree.insertInLeafNode(leafNodes[5], 13, 130, &splitInfo);
    btree.insertInLeafNode(leafNodes[5], 14, 140, &splitInfo);
297

298
299
    btree.rootNode = innerNodes[0];
    btree.depth = 2;
300

301
302
303
304
305
306
307
308
309
310
311
312
    auto &inner1Ref = *innerNodes[0];
    inner1Ref.keys[0] = 7;
    inner1Ref.children[0] = innerNodes[1];
    inner1Ref.children[1] = innerNodes[2];
    inner1Ref.numKeys = 1;

    auto &inner2Ref = *innerNodes[1];
    inner2Ref.keys[0] = 7;
    inner2Ref.keys[0] = 5;
    inner2Ref.children[0] = leafNodes[0];
    inner2Ref.children[1] = leafNodes[1];
    inner2Ref.numKeys = 1;
313

314
315
316
317
318
319
320
321
322
    auto &inner3Ref = *innerNodes[2];
    inner3Ref.keys[0] = 9;
    inner3Ref.keys[1] = 11;
    inner3Ref.keys[2] = 13;
    inner3Ref.children[0] = leafNodes[2];
    inner3Ref.children[1] = leafNodes[3];
    inner3Ref.children[2] = leafNodes[4];
    inner3Ref.children[3] = leafNodes[5];
    inner3Ref.numKeys = 3;
323

324
    btree.underflowAtBranchLevel(innerNodes[0], 0, innerNodes[1]);
325

326
327
    REQUIRE(innerNodes[0]->numKeys == 1);
    REQUIRE(innerNodes[0]->keys[0] == 9);
328

329
330
    REQUIRE(innerNodes[1]->numKeys == 2);
    REQUIRE(innerNodes[2]->numKeys == 2);
331
332
333
334
335

    std::array<int, 2> expectedKeys1{{5, 7}};
    std::array<int, 2> expectedKeys2{{11, 13}};

    REQUIRE(std::equal(std::begin(expectedKeys1), std::end(expectedKeys1),
336
                       std::begin(inner2Ref.keys)));
337
    REQUIRE(std::equal(std::begin(expectedKeys2), std::end(expectedKeys2),
338
                       std::begin(inner3Ref.keys)));
339
340
  }

341
  /* -------------------------------------------------------------------------------------------- */
342
  SECTION("Merging two inner nodes") {
343
344
345
346
347
348
349
    auto &btree = *rootRef.btree4;
    std::array<pptr<FPTreeType4::LeafNode>, 5> leafNodes = {
      { btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(), btree.newLeafNode(),
        btree.newLeafNode() }
    };

    auto node1 = btree.newBranchNode();
350
    auto &node1Ref = *node1;
351
    auto node2 = btree.newBranchNode();
352
    auto &node2Ref = *node2;
353
354
355
356
357
358
359
360
361
362
363
364
365

    node1Ref.keys[0] = 5;
    node1Ref.children[0] = leafNodes[0];
    node1Ref.children[1] = leafNodes[1];
    node1Ref.numKeys = 1;

    node2Ref.keys[0] = 20;
    node2Ref.keys[1] = 30;
    node2Ref.children[0] = leafNodes[2];
    node2Ref.children[1] = leafNodes[3];
    node2Ref.children[2] = leafNodes[4];
    node2Ref.numKeys = 2;

366
367
368
369
370
371
    auto root0 = btree.newBranchNode();
    auto &root0Ref = *root0;
    root0Ref.keys[0] = 15;
    root0Ref.children[0] = node1;
    root0Ref.children[1] = node2;
    root0Ref.numKeys = 1;
372

373
    btree.rootNode = root0;
374
375
    btree.depth = 2;

376
    btree.mergeBranchNodes(node1, root0Ref.keys[0], node2);
377

378
    REQUIRE(node1->numKeys == 4);
379
380
381

    std::array<int, 4> expectedKeys{{5, 15, 20, 30}};
    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys),
382
383
384
385
386
                       std::begin(node1Ref.keys)));
    std::array<pptr<FPTreeType4::LeafNode>, 5> node1Children;
    std::transform(std::begin(node1Ref.children), std::end(node1Ref.children),
                   std::begin(node1Children), [](FPTreeType4::Node n) { return n.leaf; });
    REQUIRE(std::equal(std::begin(leafNodes), std::end(leafNodes), std::begin(node1Children)));
387
388
  }

389
  /* -------------------------------------------------------------------------------------------- */
390
  SECTION("Merging two leaf nodes") {
391
    auto &btree = *rootRef.btree10;
392

393
    auto node1 = btree.newLeafNode();
394
    auto &node1Ref = *node1;
395
    auto node2 = btree.newLeafNode();
396
    auto &node2Ref = *node2;
397
398

    for (auto i = 0; i < 4; i++) {
399
400
      node1Ref.keys.get_rw()[i] = i;
      node1Ref.values.get_rw()[i] = i + 100;
401
402
      node1Ref.bits.get_rw().set(i);
      node1Ref.fp.get_rw()[i] = btree.fpHash(i);
403
404
405
    }

    for (auto i = 0; i < 4; i++) {
406
407
      node2Ref.keys.get_rw()[i] = i + 10;
      node2Ref.values.get_rw()[i] = i + 200;
408
409
      node2Ref.bits.get_rw().set(i);
      node2Ref.fp.get_rw()[i] = btree.fpHash(i + 10);
410
    }
411
    node1Ref.nextLeaf = node2;
412

413
    btree.mergeLeafNodes(node1, node2);
414

415
    REQUIRE(node1Ref.nextLeaf == nullptr);
416
    REQUIRE(node1Ref.bits.get_ro().count() == 8);
417
418
419
420

    std::array<int, 8> expectedKeys{{0, 1, 2, 3, 10, 11, 12, 13}};
    std::array<int, 8> expectedValues{{100, 101, 102, 103, 200, 201, 202, 203}};
    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys),
421
                       std::begin(node1Ref.keys.get_ro())));
422
    REQUIRE(std::equal(std::begin(expectedValues), std::end(expectedValues),
423
                       std::begin(node1Ref.values.get_ro())));
424
425
  }

426
  /* -------------------------------------------------------------------------------------------- */
427
  SECTION("Balancing two leaf nodes") {
428
    auto &btree = *rootRef.btree10;
429

430
    auto node1 = btree.newLeafNode();
431
    auto &node1Ref = *node1;
432
    auto node2 = btree.newLeafNode();
433
    auto &node2Ref = *node2;
434
435

    for (auto i = 0; i < 8; i++) {
436
437
      node1Ref.keys.get_rw()[i] = i + 1;
      node1Ref.values.get_rw()[i] = i * 100;
438
439
      node1Ref.bits.get_rw().set(i);
      node1Ref.fp.get_rw()[i] = btree.fpHash(i+1);
440
441
442
    }

    for (auto i = 0; i < 4; i++) {
443
444
      node2Ref.keys.get_rw()[i] = i + 11;
      node2Ref.values.get_rw()[i] = i * 200;
445
446
      node2Ref.bits.get_rw().set(i);
      node2Ref.fp.get_rw()[i] = btree.fpHash(i+11);
447
448
    }

449
    btree.balanceLeafNodes(node1, node2);
450
451
    REQUIRE(node2Ref.bits.get_ro().count() == 6);
    REQUIRE(node1Ref.bits.get_ro().count() == 6);
452
453
454

    std::array<int, 6> expectedKeys1{{1, 2, 3, 4, 5, 6}};
    std::array<int, 6> expectedValues1{{0, 100, 200, 300, 400, 500}};
455
456
    REQUIRE(std::equal(std::begin(expectedKeys1), std::begin(expectedKeys1) + 6,
                       std::begin(node1Ref.keys.get_ro())));
457
    REQUIRE(std::equal(std::begin(expectedValues1), std::end(expectedValues1),
458
                       std::begin(node1Ref.values.get_ro())));
459
460
461

    std::array<int, 6> expectedKeys2{{7, 8, 11, 12, 13, 14}};
    std::array<int, 6> expectedValues2{{0, 200, 400, 600, 600, 700}};
462
463
464
465
    std::vector<int> node2vecK {std::begin(node2Ref.keys.get_ro()),
                                std::begin(node2Ref.keys.get_ro()) + 6};
    std::vector<int> node2vecV {std::begin(node2Ref.values.get_ro()),
                                std::begin(node2Ref.values.get_ro()) + 6};
466
467
    std::sort(std::begin(node2vecK), std::end(node2vecK));
    std::sort(std::begin(node2vecV), std::end(node2vecV));
468
    REQUIRE(std::equal(std::begin(expectedKeys2), std::begin(expectedKeys2) + 6,
469
                       std::begin(node2vecK)));
470
    REQUIRE(std::equal(std::begin(expectedValues2), std::begin(expectedValues2) + 6,
471
472
473
                       std::begin(node2vecV)));
  }

474
  /* -------------------------------------------------------------------------------------------- */
475
  SECTION("Handling of underflow at a leaf node by merge and replace the root node") {
476
477
478
    auto &btree = *rootRef.btree6;

    auto leaf1 = btree.newLeafNode();
479
    auto &leaf1Ref = *leaf1;
480
    auto leaf2 = btree.newLeafNode();
481
    auto &leaf2Ref = *leaf2;
482
483
484
    leaf1Ref.nextLeaf = leaf2;
    leaf2Ref.prevLeaf = leaf1;
    const auto parent = btree.newBranchNode();
485
    auto &parentRef = *parent;
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501

    FPTreeType6::SplitInfo splitInfo;
    btree.insertInLeafNode(leaf1, 1, 10, &splitInfo);
    btree.insertInLeafNode(leaf1, 2, 20, &splitInfo);
    btree.insertInLeafNode(leaf1, 3, 30, &splitInfo);
    btree.insertInLeafNode(leaf2, 4, 40, &splitInfo);
    btree.insertInLeafNode(leaf2, 5, 50, &splitInfo);

    parentRef.keys[0] = 4;
    parentRef.numKeys = 1;
    parentRef.children[0] = leaf1;
    parentRef.children[1] = leaf2;
    btree.rootNode = parent;
    btree.depth = 1;

    btree.underflowAtLeafLevel(parent, 1, leaf2);
502
    REQUIRE(leaf1Ref.bits.get_ro().count() == 5);
503
    REQUIRE(btree.rootNode.leaf == leaf1);
504
505
506
507
508

    std::array<int, 5> expectedKeys{{1, 2, 3, 4, 5}};
    std::array<int, 5> expectedValues{{10, 20, 30, 40, 50}};

    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys),
509
                       std::begin(leaf1Ref.keys.get_ro())));
510
    REQUIRE(std::equal(std::begin(expectedValues), std::end(expectedValues),
511
                       std::begin(leaf1Ref.values.get_ro())));
512
513
  }

514
  /* -------------------------------------------------------------------------------------------- */
515
  SECTION("Handling of underflow at a leaf node by merge") {
516
517
518
    auto &btree = *rootRef.btree6;

    auto leaf1 = btree.newLeafNode();
519
    auto &leaf1Ref = *leaf1;
520
    auto leaf2 = btree.newLeafNode();
521
    auto &leaf2Ref = *leaf2;
522
    auto leaf3 = btree.newLeafNode();
523
    auto &leaf3Ref = *leaf3;
524
525
526
527
528
    leaf1Ref.nextLeaf = leaf2;
    leaf2Ref.prevLeaf = leaf1;
    leaf2Ref.nextLeaf = leaf3;
    leaf3Ref.prevLeaf = leaf2;
    const auto parent = btree.newBranchNode();
529
    auto &parentRef = *parent;
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549

    FPTreeType6::SplitInfo splitInfo;
    btree.insertInLeafNode(leaf1, 1, 10, &splitInfo);
    btree.insertInLeafNode(leaf1, 2, 20, &splitInfo);
    btree.insertInLeafNode(leaf1, 3, 30, &splitInfo);
    btree.insertInLeafNode(leaf2, 4, 40, &splitInfo);
    btree.insertInLeafNode(leaf2, 5, 50, &splitInfo);
    btree.insertInLeafNode(leaf3, 7, 70, &splitInfo);
    btree.insertInLeafNode(leaf3, 8, 80, &splitInfo);
    btree.insertInLeafNode(leaf3, 9, 90, &splitInfo);

    parentRef.keys[0] = 4;
    parentRef.keys[1] = 7;
    parentRef.numKeys = 2;
    parentRef.children[0] = leaf1;
    parentRef.children[1] = leaf2;
    parentRef.children[1] = leaf3;
    btree.rootNode = parent;

    btree.underflowAtLeafLevel(parent, 1, leaf2);
550
    REQUIRE(leaf1Ref.bits.get_ro().count() == 5);
551
    REQUIRE(btree.rootNode.branch == parent);
552
    REQUIRE(parent->numKeys == 1);
553
554
  }

555
  /* -------------------------------------------------------------------------------------------- */
556
  SECTION("Handling of underflow at a leaf node by rebalance") {
557
558
559
    auto &btree = *rootRef.btree6;

    auto leaf1 = btree.newLeafNode();
560
    auto &leaf1Ref = *leaf1;
561
    auto leaf2 = btree.newLeafNode();
562
    auto &leaf2Ref = *leaf2;
563
564
565
    leaf1Ref.nextLeaf = leaf2;
    leaf2Ref.prevLeaf = leaf1;
    const auto parent = btree.newBranchNode();
566
    auto &parentRef = *parent;
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581

    FPTreeType6::SplitInfo splitInfo;
    btree.insertInLeafNode(leaf1, 1, 10, &splitInfo);
    btree.insertInLeafNode(leaf1, 2, 20, &splitInfo);
    btree.insertInLeafNode(leaf1, 3, 30, &splitInfo);
    btree.insertInLeafNode(leaf1, 4, 40, &splitInfo);
    btree.insertInLeafNode(leaf2, 5, 50, &splitInfo);
    btree.insertInLeafNode(leaf2, 6, 60, &splitInfo);

    parentRef.keys[0] = 5;
    parentRef.numKeys = 1;
    parentRef.children[0] = leaf1;
    parentRef.children[1] = leaf2;

    btree.underflowAtLeafLevel(parent, 1, leaf2);
582
583
    REQUIRE(leaf1Ref.bits.get_ro().count() == 3);
    REQUIRE(leaf2Ref.bits.get_ro().count() == 3);
584
585
586
587
588

    std::array<int, 3> expectedKeys1{{1, 2, 3}};
    std::array<int, 3> expectedValues1{{10, 20, 30}};

    REQUIRE(std::equal(std::begin(expectedKeys1), std::end(expectedKeys1),
589
                       std::begin(leaf1Ref.keys.get_ro())));
590
    REQUIRE(std::equal(std::begin(expectedValues1), std::end(expectedValues1),
591
                       std::begin(leaf1Ref.values.get_ro())));
592
593
594
595

    std::array<int, 3> expectedKeys2{{4, 5, 6}};
    std::array<int, 3> expectedValues2{{40, 50, 60}};

596
597
598
599
    std::vector<int> leaf2vecK {std::begin(leaf2Ref.keys.get_ro()),
                                std::begin(leaf2Ref.keys.get_ro()) + 3};
    std::vector<int> leaf2vecV {std::begin(leaf2Ref.values.get_ro()),
                                std::begin(leaf2Ref.values.get_ro()) + 3};
600
601
    std::sort(std::begin(leaf2vecK), std::end(leaf2vecK));
    std::sort(std::begin(leaf2vecV), std::end(leaf2vecV));
602
    REQUIRE(std::equal(std::begin(expectedKeys2), std::end(expectedKeys2), std::begin(leaf2vecK)));
603
604
605
606
    REQUIRE(std::equal(std::begin(expectedValues2), std::end(expectedValues2),
                       std::begin(leaf2vecV)));
  }

607
  /* -------------------------------------------------------------------------------------------- */
608
  SECTION("Handling of underflow at a inner node") {
609
610
611
612
    auto &btree = *rootRef.btree4;
    FPTreeType4::SplitInfo splitInfo;

    auto leaf1 = btree.newLeafNode();
613
    auto &leaf1Ref = *leaf1;
614
615
616
617
618
    btree.insertInLeafNode(leaf1, 1, 1, &splitInfo);
    btree.insertInLeafNode(leaf1, 2, 2, &splitInfo);
    btree.insertInLeafNode(leaf1, 3, 3, &splitInfo);

    auto leaf2 = btree.newLeafNode();
619
    auto &leaf2Ref = *leaf2;
620
621
622
623
624
625
    btree.insertInLeafNode(leaf2, 5, 5, &splitInfo);
    btree.insertInLeafNode(leaf2, 6, 6, &splitInfo);
    leaf1Ref.nextLeaf = leaf2;
    leaf2Ref.prevLeaf = leaf1;

    auto leaf3 = btree.newLeafNode();
626
    auto &leaf3Ref = *leaf3;
627
628
629
630
631
632
    btree.insertInLeafNode(leaf3, 10, 10, &splitInfo);
    btree.insertInLeafNode(leaf3, 11, 11, &splitInfo);
    leaf2Ref.nextLeaf = leaf3;
    leaf3Ref.prevLeaf = leaf2;

    auto leaf4 = btree.newLeafNode();
633
    auto &leaf4Ref = *leaf4;
634
635
636
637
638
639
    btree.insertInLeafNode(leaf4, 15, 15, &splitInfo);
    btree.insertInLeafNode(leaf4, 16, 16, &splitInfo);
    leaf3Ref.nextLeaf = leaf4;
    leaf4Ref.prevLeaf = leaf3;

    auto leaf5 = btree.newLeafNode();
640
    auto &leaf5Ref = *leaf5;
641
642
643
644
645
646
647
    btree.insertInLeafNode(leaf5, 20, 20, &splitInfo);
    btree.insertInLeafNode(leaf5, 21, 21, &splitInfo);
    btree.insertInLeafNode(leaf5, 22, 22, &splitInfo);
    leaf4Ref.nextLeaf = leaf5;
    leaf5Ref.prevLeaf = leaf4;

    auto leaf6 = btree.newLeafNode();
648
    auto &leaf6Ref = *leaf6;
649
650
651
652
653
654
655
    btree.insertInLeafNode(leaf6, 31, 31, &splitInfo);
    btree.insertInLeafNode(leaf6, 32, 32, &splitInfo);
    btree.insertInLeafNode(leaf6, 33, 33, &splitInfo);
    leaf5Ref.nextLeaf = leaf6;
    leaf6Ref.prevLeaf = leaf5;

    const auto inner1 = btree.newBranchNode();
656
    auto &inner1Ref = *inner1;
657
658
659
660
661
662
663
664
    inner1Ref.keys[0] = 5;
    inner1Ref.keys[1] = 10;
    inner1Ref.children[0] = leaf1;
    inner1Ref.children[1] = leaf2;
    inner1Ref.children[2] = leaf3;
    inner1Ref.numKeys = 2;

    const auto inner2 = btree.newBranchNode();
665
    auto &inner2Ref = *inner2;
666
667
668
669
670
671
672
    inner2Ref.keys[0] = 20;
    inner2Ref.keys[1] = 30;
    inner2Ref.children[0] = leaf4;
    inner2Ref.children[1] = leaf5;
    inner2Ref.children[2] = leaf6;
    inner2Ref.numKeys = 2;

673
674
675
676
677
678
    auto root0 = btree.newBranchNode();
    auto &root0Ref = *root0;
    root0Ref.keys[0] = 15;
    root0Ref.children[0] = inner1;
    root0Ref.children[1] = inner2;
    root0Ref.numKeys = 1;
679

680
    btree.rootNode = root0;
681
    btree.depth = 2;
682
683
    btree.eraseFromBranchNode(root0, btree.depth, 10);
    REQUIRE(btree.rootNode.branch != root0);
684
685
    REQUIRE(btree.depth < 2);

686
    REQUIRE(inner1->numKeys == 4);
687
    std::array<int, 4> expectedKeys{{5, 15, 20, 30}};
688
689
690
    std::array<pptr<FPTreeType4::LeafNode>, 5> expectedChildren {
      {leaf1, leaf2, leaf4, leaf5, leaf6}
    };
691
692

    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys),
693
694
695
696
                       std::begin(inner1Ref.keys)));
    std::array<pptr<FPTreeType4::LeafNode>, 5> inner1Children;
    std::transform(std::begin(inner1Ref.children), std::end(inner1Ref.children),
                   std::begin(inner1Children), [](FPTreeType4::Node n) { return n.leaf; });
697
698
699
700
    REQUIRE(std::equal(std::begin(expectedChildren), std::end(expectedChildren),
                       std::begin(inner1Children)));
  }

701
  /* -------------------------------------------------------------------------------------------- */
702
  SECTION("Inserting an entry into a leaf node") {
703
704
    auto &btree = *rootRef.btree12;
    FPTreeType12::SplitInfo splitInfo;
705
    auto res = false;
706
    auto node = btree.newLeafNode();
707
    auto &nodeRef = *node;
708
709

    for (auto i = 0; i < 9; i++) {
710
711
      nodeRef.keys.get_rw()[i] = (i + 1) * 2;
      nodeRef.values.get_rw()[i] = (i * 2) + 100;
712
713
      nodeRef.bits.get_rw().set(i);
      nodeRef.fp.get_rw()[i] = btree.fpHash((i + 1) * 2);
714
715
    }

716
    res = btree.insertInLeafNode(node, 5, 5000, &splitInfo);
717
    REQUIRE(res == false);
718
    REQUIRE(nodeRef.bits.get_ro().count() == 10);
719

720
    res = btree.insertInLeafNode(node, 1, 1, &splitInfo);
721
    REQUIRE(res == false);
722
    REQUIRE(nodeRef.bits.get_ro().count() == 11);
723

724
    res = btree.insertInLeafNode(node, 2, 1000, &splitInfo);
725
    REQUIRE(res == false);
726
    REQUIRE(nodeRef.bits.get_ro().count() == 11);
727
728

    std::array<int, 11> expectedKeys{{1, 2, 4, 5, 6, 8, 10, 12, 14, 16, 18}};
729
    std::array<int, 11> expectedValues{{1, 102, 104, 106, 108, 110, 112, 114, 116, 1000, 5000}};
730

731
732
733
734
    std::vector<int> nodevecK {std::begin(nodeRef.keys.get_ro()),
                               std::begin(nodeRef.keys.get_ro()) + 11};
    std::vector<int> nodevecV {std::begin(nodeRef.values.get_ro()),
                               std::begin(nodeRef.values.get_ro()) + 11};
735
736
    std::sort(std::begin(nodevecK), std::end(nodevecK));
    std::sort(std::begin(nodevecV), std::end(nodevecV));
Philipp Götze's avatar
Philipp Götze committed
737

738
739
740
741
742
    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys),
                       std::begin(nodevecK)));
    REQUIRE(std::equal(std::begin(expectedValues), std::end(expectedValues),
                       std::begin(nodevecV)));

743
    res = btree.insertInLeafNode(node, 20, 21, &splitInfo);
744
745
    REQUIRE(res == false);

746
    res = btree.insertInLeafNode(node, 25, 25, &splitInfo);
747
748
749
    REQUIRE(res == true);
  }

750
  /* -------------------------------------------------------------------------------------------- */
751
  SECTION("Inserting an entry into a leaf node at a given position") {
752
753
    auto &btree = *rootRef.btree20;
    auto node = btree.newLeafNode();
754
    auto &nodeRef = *node;
755
756

    for (auto i = 0; i < 9; i++) {
757
758
      nodeRef.keys.get_rw()[i] = (i + 1) * 2;
      nodeRef.values.get_rw()[i] = (i * 2) + 100;
759
760
      nodeRef.bits.get_rw().set(i);
      nodeRef.fp.get_rw()[i] = btree.fpHash((i + 1) * 2);
761
762
    }

763
    btree.insertInLeafNodeAtPosition(node, 9, 5, 5000);
764
    REQUIRE(nodeRef.bits.get_ro().count() == 10);
765
    btree.insertInLeafNodeAtPosition(node, 10, 1, 1);
766
    REQUIRE(nodeRef.bits.get_ro().count() == 11);
767
768

    std::array<int, 11> expectedKeys{{1, 2, 4, 5, 6, 8, 10, 12, 14, 16, 18}};
769
    std::array<int, 11> expectedValues{{1, 100, 102,104, 106, 108, 110, 112, 114, 116, 5000}};
770

771
772
773
774
    std::vector<int> nodevecK {std::begin(nodeRef.keys.get_ro()),
                               std::begin(nodeRef.keys.get_ro()) + 11};
    std::vector<int> nodevecV {std::begin(nodeRef.values.get_ro()),
                               std::begin(nodeRef.values.get_ro()) + 11};
775
776
    std::sort(std::begin(nodevecK), std::end(nodevecK));
    std::sort(std::begin(nodevecV), std::end(nodevecV));
Philipp Götze's avatar
Philipp Götze committed
777

778
    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys), std::begin(nodevecK)));
779
780
781
782
    REQUIRE(std::equal(std::begin(expectedValues), std::end(expectedValues),
                       std::begin(nodevecV)));
  }

783
  /* -------------------------------------------------------------------------------------------- */
784
  SECTION("Inserting an entry into an inner node without a split") {
785
786
    auto &btree = *rootRef.btree4;
    FPTreeType4::SplitInfo splitInfo;
787

788
789
790
791
792
793
794
795
796
797
    auto leaf1 = btree.newLeafNode();
    btree.insertInLeafNode(leaf1, 1, 10, &splitInfo);
    btree.insertInLeafNode(leaf1, 2, 20, &splitInfo);
    btree.insertInLeafNode(leaf1, 3, 30, &splitInfo);

    auto leaf2 = btree.newLeafNode();
    btree.insertInLeafNode(leaf2, 10, 100, &splitInfo);
    btree.insertInLeafNode(leaf2, 12, 120, &splitInfo);

    auto node = btree.newBranchNode();
798
    auto &nodeRef = *node;
799
800
801
802
803
804
805
806
807
    nodeRef.keys[0] = 10;
    nodeRef.children[0] = leaf1;
    nodeRef.children[1] = leaf2;
    nodeRef.numKeys = 1;

    btree.rootNode = node;
    btree.depth = 2;

    btree.insertInBranchNode(node, 1, 11, 112, &splitInfo);
808
    REQUIRE(leaf2->bits.get_ro().count() == 3);
809
810
  }

811
  /* -------------------------------------------------------------------------------------------- */
812
  SECTION("Inserting an entry into an inner node with split") {
813
814
    auto &btree = *rootRef.btree4;
    FPTreeType4::SplitInfo splitInfo;
815

816
817
818
819
820
821
822
823
824
825
826
827
    auto leaf1 = btree.newLeafNode();
    btree.insertInLeafNode(leaf1, 1, 10, &splitInfo);
    btree.insertInLeafNode(leaf1, 2, 20, &splitInfo);
    btree.insertInLeafNode(leaf1, 3, 30, &splitInfo);

    auto leaf2 = btree.newLeafNode();
    btree.insertInLeafNode(leaf2, 10, 100, &splitInfo);
    btree.insertInLeafNode(leaf2, 11, 110, &splitInfo);
    btree.insertInLeafNode(leaf2, 13, 130, &splitInfo);
    btree.insertInLeafNode(leaf2, 14, 140, &splitInfo);

    auto node = btree.newBranchNode();
828
    auto &nodeRef = *node;
829
830
831
832
833
834
835
836
837
    nodeRef.keys[0] = 10;
    nodeRef.children[0] = leaf1;
    nodeRef.children[1] = leaf2;
    nodeRef.numKeys = 1;

    btree.rootNode = node;
    btree.depth = 2;

    btree.insertInBranchNode(node, 1, 12, 112, &splitInfo);
838
    REQUIRE(leaf2->bits.get_ro().count() == 2);
839
    REQUIRE(node->numKeys == 2);
840

841
    std::array<int, 2> expectedKeys{{10, 12}};
842
    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys), std::begin(nodeRef.keys)));
843

844
    std::array<int, 3> expectedKeys2{{12, 13, 14}};
845
    auto &leaf3Ref = *nodeRef.children[2].leaf;
846
847
    std::vector<int> actualKeys{};
    for(auto i = 0u; i < 4; i++)
848
      if(leaf3Ref.bits.get_ro().test(i))
849
        actualKeys.push_back(leaf3Ref.keys.get_ro()[i]);
850
    std::sort(std::begin(actualKeys), std::end(actualKeys));
851
    REQUIRE(std::equal(std::begin(expectedKeys2), std::end(expectedKeys2), std::begin(actualKeys)));
852
853
  }

854
  /* -------------------------------------------------------------------------------------------- */
855
  SECTION("Deleting an entry from a leaf node") {
856
857
    auto &btree = *rootRef.btree20;
    auto node = btree.newLeafNode();
858
    auto &nodeRef = *node;
859
860

    for (auto i = 0; i < 9; i++) {
861
862
      nodeRef.keys.get_rw()[i] = i + 1;
      nodeRef.values.get_rw()[i] = i + 100;
863
864
      nodeRef.bits.get_rw().set(i);
      nodeRef.fp.get_rw()[i] = btree.fpHash(i + 1);
865
866
    }

867
    REQUIRE(btree.eraseFromLeafNode(node, 5) == true);
868
    REQUIRE(nodeRef.bits.get_ro().count() == 8);
869
    REQUIRE(btree.eraseFromLeafNode(node, 15) == false);
870
    REQUIRE(nodeRef.bits.get_ro().count() == 8);
871
872
873
874

    std::array<int, 8> expectedKeys{{1, 2, 3, 4, 6, 7, 8, 9 }};
    std::array<int, 8> expectedValues{
        {100, 101, 102, 103, 105, 106, 107, 108 }};
Philipp Götze's avatar
Philipp Götze committed
875

876
877
    std::vector<int> nodevecK {std::begin(nodeRef.keys.get_ro()),
                               std::begin(nodeRef.keys.get_ro()) + 9};
878
    nodevecK.erase(nodevecK.begin() + 4);
879
880
    std::vector<int> nodevecV {std::begin(nodeRef.values.get_ro()),
                               std::begin(nodeRef.values.get_ro()) + 9};
881
    nodevecV.erase(nodevecV.begin() + 4);
882
883
884
    std::sort(std::begin(nodevecK), std::end(nodevecK));
    std::sort(std::begin(nodevecV), std::end(nodevecV));

885
    REQUIRE(std::equal(std::begin(expectedKeys), std::end(expectedKeys), std::begin(nodevecK)));
886
887
888
889
    REQUIRE(std::equal(std::begin(expectedValues), std::end(expectedValues),
                       std::begin(nodevecV)));
  }

890
  /* -------------------------------------------------------------------------------------------- */
891
  SECTION("Testing delete from a leaf node in a B+ tree") {
892
893
894
    auto &btree = *rootRef.btree20;
    for (int i = 0; i < 20; i += 2) btree.insert(i, i);
    REQUIRE (btree.erase(10) == true);
895
    int res;
896
    REQUIRE (btree.lookup(10, &res) == false);
897
898
  }

899
  /* -------------------------------------------------------------------------------------------- */
900
  SECTION("Constructing a B+ tree and iterating over it") {
901
    auto btree = rootRef.btree10;
902
    transaction::run(pop, [&] {
903
      delete_persistent<FPTreeType10>(btree);
904
      btree = make_persistent<FPTreeType10>(alloc_class);
905
      auto &btreeRef = *btree;
906
      for (int i = 0; i < 50; ++i)
907
        btreeRef.insert(i, i * 2);
908
909
910
911
912
913
914
915
916
917
918
919
920
    });

    int num = 0;
    auto