http://blog.csdn.net/sparkliang/article/details/8635821

BlockBuilder的接口

1. void Reset(); // 重设内容，通常在Finish之后调用已构建新的block
2. //添加k/v，要求：Reset()之后没有调用过Finish()；Key > 任何已加入的key
3. void Add(const Slice& key,const Slice& value);
4. // 结束构建block，并返回指向block内容的指针
5. Slice Finish();// 返回Slice的生存周期：Builder的生存周期，or直到Reset()被调用
6. size_t CurrentSizeEstimate()const; // 返回正在构建block的未压缩大小—估计值
7. bool empty() const { returnbuffer_.empty();} // 没有entry则返回true

1. std::string            buffer_; // block的内容
2. std::vector<uint32_t>  restarts_;  // 重启点-后面会分析到
3. int                  counter_;  // 重启后生成的entry数
4. std::string            last_key_; // 记录最后添加的key

6.3.2 BlockBuilder::Add()

1. assert(!finished_);
2. assert(counter_ <= options_->block_restart_interval);
3. assert(buffer_.empty() || options_->comparator->Compare(key,last_key_piece) > 0);

1. Slice last_key_piece(last_key_);
2. if (counter_ < options_->block_restart_interval) { //前缀压缩
3. // 计算key与last_key_的公共前缀
4. const size_t min_length= std::min(last_key_piece.size(), key.size());
5. while ((shared < min_length)&& (last_key_piece[shared] == key[shared])) {
6. shared++;
7. }else{ // 新的重启点
8. restarts_.push_back(buffer_.size());
9. counter_ = 0;
10. }

1. const size_t non_shared = key.size() - shared; // key前缀之后的字符串长度
2. // append"<shared><non_shared><value_size>" 到buffer_
3. PutVarint32(&buffer_, shared);
4. PutVarint32(&buffer_, non_shared);
5. PutVarint32(&buffer_, value.size());
6. // 其后是前缀之后的字符串 + value
7. buffer_.append(key.data() + shared, non_shared);
8. buffer_.append(value.data(), value.size());
9. // 更新状态 ，last_key_ = key及计数器counter_
10. last_key_.resize(shared);   // 连一个string的赋值都要照顾到，使内存copy最小化
11. last_key_.append(key.data() + shared, non_shared);
12. assert(Slice(last_key_) == key);
13. counter_++;

6.3.3 BlockBuilder::Finish()

1. for (size_t i = 0; i < restarts_.size(); i++) {  // 重启点
2. PutFixed32(&buffer_, restarts_[i]);
3. }
4. PutFixed32(&buffer_, restarts_.size());    // 重启点数量
5. finished_ = true;
6. return Slice(buffer_);

6.3.4 BlockBuilder::Reset() & 大小

1. void BlockBuilder::Reset() {
2. buffer_.clear();  restarts_.clear();  last_key_.clear();
3. restarts_.push_back(0);       // 第一个重启点位置总是 0
4. counter_ = 0;
5. finished_ = false;
6. }
7. size_t BlockBuilder::CurrentSizeEstimate () const {
8. // buffer大小 +重启点数组长度 + 重启点长度(uint32)
9. return (buffer_.size() +  restarts_.size() * sizeof(uint32_t) + sizeof(uint32_t));
10. }

6.3.5 Block类接口

1. size_t size() const { returnsize_; }
2. Iterator* NewIterator(constComparator* comparator);
3. const char* data_; // block数据指针
4. size_t size_;      // block数据大小
5. uint32_t restart_offset_;     // 重启点数组在data_中的偏移
6. bool owned_;              //data_[]是否是Block拥有的

6.3.6 Block初始化

1. >data = Slice();
2. >cachable = false; // 无cache
3. >heap_allocated = false; // 非heap分配
4. 根据contents为成员赋值
5. data_ = contents.data.data(), size_ =contents.data.size(),owned_ = contents.heap_allocated;

1. if (size_ < sizeof(uint32_t)){
2. size_ = 0;  // 出错了
3. } else {
4. restart_offset_ = size_ - (1 +NumRestarts()) * sizeof(uint32_t);
5. if (restart_offset_ > size_- sizeof(uint32_t)) size_ = 0;
6. }

6.3.7 Block::Iter

1. const Comparator* constcomparator_; // key比较器
2. const char* const data_;      // block内容
3. uint32_t const restarts_;     // 重启点(uint32数组)在data中的偏移
4. uint32_t const num_restarts_; // 重启点个数
5. uint32_t current_; // 当前entry在data中的偏移.  >= restarts_表明非法
6. uint32_t restart_index_;  // current_所在的重启点的index

1. current_ = NextEntryOffset(); // (value_.data() + value_.size()) - data_
2. const char* p = data_ +current_;
3. const char* limit = data_ +restarts_; // Restarts come right after data
4. if (p >= limit) { // entry到头了，标记为invalid.
5. current_ = restarts_;
6. restart_index_ =num_restarts_;
7. return false;
8. }

1. uint32_t shared, non_shared,value_length;
2. p = DecodeEntry(p, limit,&shared, &non_shared, &value_length);
3. if (p == NULL || key_.size()< shared) {
4. CorruptionError();
5. return false;
6. } else { // 成功
7. key_.resize(shared);
8. key_.append(p, non_shared);
9. value_ = Slice(p +non_shared, value_length);
10. while (restart_index_ + 1< num_restarts_ && GetRestartPoint(restart_index_ + 1) < current_) {
11. ++restart_index_; //更新重启点index
12. }
13. return true;
14. }

1. const uint32_t original =current_;
2. while (GetRestartPoint(restart_index_)>= original) {
3. if (restart_index_ == 0) { // 到第一个entry了，标记invalid状态
4. current_ = restarts_;
5. restart_index_ =num_restarts_;
6. return;
7. }
8. restart_index_--;
9. }
10. SeekToRestartPoint(restart_index_);//根据restart index定位到重启点的k/v对

1. void SeekToRestartPoint(uint32_tindex) {
2. key_.clear();
3. restart_index_ = index;
4. // ParseNextKey()会设置current_;
5. //ParseNextKey()从value_结尾开始, 因此需要相应的设置value_
6. uint32_t offset =GetRestartPoint(index);
7. value_ = Slice(data_ + offset,0); // value长度设置为0，字符串指针是data_+offset
8. }

1. virtual void SeekToFirst() {
2. SeekToRestartPoint(0);
3. ParseNextKey();
4. }
5. virtual void SeekToLast() {
6. SeekToRestartPoint(num_restarts_ - 1);
7. while (ParseNextKey()&& NextEntryOffset() < restarts_) {} //Keep skipping
8. }

1. while (true) {
2. if (!ParseNextKey()) return;
3. if (Compare(key_, target)>= 0) return;
4. }