Lab 3.2 迭代器

1 BlockIterator的设计

现在实现我们的Block的迭代器。通过Block的编码格式可知, 只需要知道当前的索引, 就可以在Block中查询该索引的kv对, 因此迭代器只需要记录当前索引和原始Block的引用就可以了。

这也就是之前提到的std::enable_shared_from_this的作用，让我们的BlockIterator可以使用Block的智能指针, 为什么这样设计呢? 因为BlockIterator的生命周期是依赖于于Block的, 如果Block的生命周期结束, BlockIterator依然存在, 那么就会产生悬空指针, 因此我们需要使用智能指针来管理Block的生命周期。

这么说可能有点迷糊, 我们直接看头文件定义:

class BlockIterator {
  // ...
private:
  std::shared_ptr<Block> block;                   // 指向所属的 Block
  size_t current_index;                           // 当前位置的索引
  uint64_t tranc_id_;                             // 当前事务 id
  mutable std::optional<value_type> cached_value; // 缓存当前值
};

cached_value其实算是个小优化, 尽管有索引就在block中进行二分查找, 但这里还是用一个值进行缓存, 因为迭代器可能被反复读取值, 而每次读取值需要按照数据编码的格式进行解码, 在多次读取迭代器值的情况下, 缓存起来从理论上速度回更快

这里的BlockIterator不同于我们之前的HeapIterator, 它并不持有我们实际的键值对数据, 而进行对Block中的键值对位置进行定位, 因此就需要保证其指针block是有效的, 在现代C++中, 我们应该避免使用裸指针, 因此这里使用了std::shared_ptr来保证其指针block有效的。但 std::shared_ptr<Block> block肯定是某个Blcok的this指针, 而this是裸指针, 因此我们需要使Block继承std::enable_shared_from_this, 这样就可以通过shared_from_this()获取代表this指针的shared_ptr<Block>了。

需要注意的是, 使用shared_from_this()时, 需要保证类的实例被shared_ptr管理, 否则会抛出异常, 具体可以查询相关资料, 这里不过多介绍。

其余成员变量应该很好理解, current_index记录当前索引, tranc_id_记录当前事务 id, cached_value缓存当前值。

2 实现 `BlockIterator`

本部分你需要修改的代码文件为：

src/block/block_iterator.cpp
include/block/block_iterator.h (Optional)

2.1 构造函数实现

实现构造函数，传入一个 block 和 key，以及事务 tranc_id, 这里在构造迭代器时就将迭代器移动到指定key的位置(还需要满足tranc_id的可见性, 不过现在你可以先忽略这个可见性的判断逻辑)。

你需要借助之前实现的Block的成员函数来实现这的移动逻辑:

BlockIterator::BlockIterator(std::shared_ptr<Block> b, const std::string &key,
                             uint64_t tranc_id)
    : block(b), tranc_id_(tranc_id), cached_value(std::nullopt) {
  // TODO: Lab3.2 创建迭代器时直接移动到指定的key位置
  // ? 你需要借助之前实现的 Block 类的成员函数
}

2.2 运算符重载

迭代器的运算符重载是你需要实现的基础成员函数:

BlockIterator::pointer BlockIterator::operator->() const {
  // TODO: Lab3.2 -> 重载
  return nullptr;
}

BlockIterator &BlockIterator::operator++() {
  // TODO: Lab3.2 ++ 重载
  // ? 在后续的Lab实现事务后，你可能需要对这个函数进行返修
  return *this;
}

bool BlockIterator::operator==(const BlockIterator &other) const {
  // TODO: Lab3.2 == 重载
  return true;
}

bool BlockIterator::operator!=(const BlockIterator &other) const {
  // TODO: Lab3.2 != 重载
  return true;
}

BlockIterator::value_type BlockIterator::operator*() const {
  // TODO: Lab3.2 * 重载
  return {};
}

这些运算符重载函数中, 你也不需要考虑tranc_id的相关逻辑, 只是你需要记得, 后续实现了事务功能后, 本Lab的部分逻辑需要进行调整

2.3 辅助函数

这里有一些作者提供的可能用用的辅助函数, 你可以按选择实现他们, 也可以忽略他们, 自己按照自己的理解创建自定义的成员函数:

void BlockIterator::update_current() const {
  // TODO: Lab3.2 更新当前指针
  // ? 该函数是可选的实现, 你可以采用自己的其他方案实现->, 而不是使用
  // ? cached_value 来缓存当前指针
}

void BlockIterator::skip_by_tranc_id() {
  // TODO: Lab3.2 * 跳过事务ID
  // ? 只是进行标记以供你在后续Lab实现事务功能后修改
  // ? 现在你不需要考虑这个函数
}

这里的skip_by_tranc_id只是标记后续Lab实现事务带来的的一些逻辑上的变化, 你现在不需要实现。而update_current则是一个可选的实现, 其用来更新缓存的键值对变量, 你可以采用自己的其他方案实现->, 而不是使用成员变量cached_value和这个函数。

4 获取迭代器的接口函数实现

现在我们已经实现了BlockIterator的, 我们需要实现Block的begin和end函数将BlockIterator进行返回给外部组件使用:

BlockIterator Block::begin(uint64_t tranc_id) {
  // TODO Lab 3.2 获取begin迭代器
  return BlockIterator(nullptr, 0, 0);
}

BlockIterator Block::end() {
  // TODO Lab 3.2 获取end迭代器
  return BlockIterator(nullptr, 0, 0);
}

这里的tranc_id同样可以暂时忽略, 但对应类实例的值还是要在构造函数中初始化的。

5 测试

测试代码在test/test_block.cpp中, 你在完成上述组件实现后的测试结果预期为:

✗ xmake
✗ xmake run test_block
[==========] Running 10 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 10 tests from BlockTest
[ RUN      ] BlockTest.DecodeTest
[       OK ] BlockTest.DecodeTest (0 ms)
[ RUN      ] BlockTest.EncodeTest
[       OK ] BlockTest.EncodeTest (0 ms)
[ RUN      ] BlockTest.BinarySearchTest
[       OK ] BlockTest.BinarySearchTest (0 ms)
[ RUN      ] BlockTest.EdgeCasesTest
[       OK ] BlockTest.EdgeCasesTest (0 ms)
[ RUN      ] BlockTest.LargeDataTest
[       OK ] BlockTest.LargeDataTest (0 ms)
[ RUN      ] BlockTest.ErrorHandlingTest
[       OK ] BlockTest.ErrorHandlingTest (1 ms)
[ RUN      ] BlockTest.IteratorTest
[       OK ] BlockTest.IteratorTest (0 ms)
[ RUN      ] BlockTest.PredicateTest
test/test_block.cpp:277: Failure
Value of: result.has_value()
  Actual: false
Expected: true

unknown file: Failure
C++ exception with description "bad optional access" thrown in the test body.

PredicateTest需要你在完成下一小节的任务后, 才能通过。

现在你可以开启下一节的范围查询

Keyboard shortcuts

Tiny-LSM-Lab