[施工中] levelDB 代码阅读笔记 06 iterator

Mar 26, 2022 · 3 min read · leveldb

Overview

接口

一个ABC，后面会继承这个类做各种实现

clean up function

代码比较好懂，唯一让我感到疑惑的是 clean up function 这部分

 1
 2 // FIXME: 不太理解为什么需要很多个clean up function
 3  // Cleanup functions are stored in a single-linked list.
 4  // The list's head node is inlined in the iterator.
 5  struct CleanupNode {
 6    // True if the node is not used. Only head nodes might be unused.
 7    bool IsEmpty() const { return function == nullptr; }
 8    // Invokes the cleanup function.
 9    void Run() {
10      assert(function != nullptr);
11      (*function)(arg1, arg2);
12    }
13
14    // The head node is used if the function pointer is not null.
15    CleanupFunction function;
16    void* arg1;
17    void* arg2;
18    CleanupNode* next;
19  };
20  CleanupNode cleanup_head_;
21};
22

从 table/iterator.cc 的析构函数中，可以看到在iterator析构的时候会依次调用多个clean up function

 1
 2Iterator::~Iterator() {
 3  if (!cleanup_head_.IsEmpty()) {
 4    cleanup_head_.Run();
 5    for (CleanupNode* node = cleanup_head_.next; node != nullptr;) {
 6      node->Run();
 7      CleanupNode* next_node = node->next;
 8      delete node;
 9      node = next_node;
10    }
11  }
12}
13

clean up funtion可以通过调用注册函数添加到列表里

 1
 2void Iterator::RegisterCleanup(CleanupFunction func, void* arg1, void* arg2) {
 3  assert(func != nullptr);
 4  CleanupNode* node;
 5  if (cleanup_head_.IsEmpty()) {
 6    node = &cleanup_head_;
 7  } else {
 8    // 头插法。 新的node插在了clean_head后面
 9    node = new CleanupNode();
10    node->next = cleanup_head_.next;
11    cleanup_head_.next = node;
12  }
13  node->function = func;
14  node->arg1 = arg1;
15  node->arg2 = arg2;
16}
17
18

这里有两部分让人不懂

Info
  1. 为什么需要多个clean up function?
  2. clean up funtion的参数是在注册时就唯一确定了，而不是在调用时。 clean up function究竟是在清理什么？

带着这些疑问，继续往下读

iteratorWrapper

这里包了一层，目的是把key()和valid()的结果cache住，节省了依次取地址的开销

带来的代价就是，对于会影响key()和valid()结果的operation,需要额外的update操作，变得更重了。

猜测是有某些频繁读key()和valid()的场景，因此做了这样一个trade-off

 1
 2
 3// A internal wrapper class with an interface similar to Iterator that
 4// caches the valid() and key() results for an underlying iterator.
 5// This can help avoid virtual function calls and also gives better
 6// cache locality.
 7class IteratorWrapper {
 8 public:
 9  IteratorWrapper() : iter_(nullptr), valid_(false) {}
10  explicit IteratorWrapper(Iterator* iter) : iter_(nullptr) { Set(iter); }
11  ~IteratorWrapper() { delete iter_; }
12  Iterator* iter() const { return iter_; }
13
14  // Takes ownership of "iter" and will delete it when destroyed, or
15  // when Set() is invoked again.
16  void Set(Iterator* iter) {
17    delete iter_;
18    iter_ = iter;
19    if (iter_ == nullptr) {
20      valid_ = false;
21    } else {
22      Update();
23    }
24  }
25
26  // Iterator interface methods
27  bool Valid() const { return valid_; }
28  Slice key() const {
29    assert(Valid());
30    return key_;
31  }
32  Slice value() const {
33    assert(Valid());
34    return iter_->value();
35  }
36  // Methods below require iter() != nullptr
37  Status status() const {
38    assert(iter_);
39    return iter_->status();
40  }
41  void Next() {
42    assert(iter_);
43    iter_->Next();
44    Update();
45  }
46  void Prev() {
47    assert(iter_);
48    iter_->Prev();
49    Update();
50  }
51  void Seek(const Slice& k) {
52    assert(iter_);
53    iter_->Seek(k);
54    Update();
55  }
56  void SeekToFirst() {
57    assert(iter_);
58    iter_->SeekToFirst();
59    Update();
60  }
61  void SeekToLast() {
62    assert(iter_);
63    iter_->SeekToLast();
64    Update();
65  }
66
67 private:
68  void Update() {
69    valid_ = iter_->Valid();
70    if (valid_) {
71      key_ = iter_->key();
72    }
73  }
74
75  Iterator* iter_;
76  bool valid_;
77  Slice key_;
78};
79

two level iterator

一个二级迭代器 第一层为index iterator, index iterator对应的value是一个data block, 对应date iterator

比较重要的是这个函数,每到一个新的index位置，会用来生成下一级的第一个data iterator

data_block_handle_ 可以理解成对data block的一个标识，避免重复初始化这个data block的data iterator

 1
 2// note: 每次InitDataBlock是可能改变成员变量data_iter_的值的
 3void TwoLevelIterator::InitDataBlock() {
 4  if (!index_iter_.Valid()) {
 5    SetDataIterator(nullptr);
 6  } else {
 7    Slice handle = index_iter_.value();
 8    if (data_iter_.iter() != nullptr &&
 9        handle.compare(data_block_handle_) == 0) {
10      // data_iter_ is already constructed with this iterator, so
11      // no need to change anything
12    } else {
13      Iterator* iter = (*block_function_)(arg_, options_, handle);
14      data_block_handle_.assign(handle.data(), handle.size());
15      // note: data iterator是由block function创建出来的
16      SetDataIterator(iter);
17    }
18  }
19}

Posts in this Series