/bitcoin/src/leveldb/table/block.cc

Source
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.
//
// Decodes the blocks generated by block_builder.cc.

#include "table/block.h"

#include <algorithm>
#include <cstdint>
#include <vector>

#include "leveldb/comparator.h"
#include "table/format.h"
#include "util/coding.h"
#include "util/logging.h"

namespace leveldb {

inline uint32_t Block::NumRestarts() const {
  assert(size_ >= sizeof(uint32_t));
  return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
}

Block::Block(const BlockContents& contents)
    : data_(contents.data.data()),
      size_(contents.data.size()),
      owned_(contents.heap_allocated) {
  if (size_ < sizeof(uint32_t)) {
    size_ = 0;  // Error marker
  } else {
    size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
    if (NumRestarts() > max_restarts_allowed) {
      // The size is too small for NumRestarts()
      size_ = 0;
    } else {
      restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
    }
  }
}

Block::~Block() {
  if (owned_) {
    delete[] data_;
  }
}

// Helper routine: decode the next block entry starting at "p",
// storing the number of shared key bytes, non_shared key bytes,
// and the length of the value in "*shared", "*non_shared", and
// "*value_length", respectively.  Will not dereference past "limit".
//
// If any errors are detected, returns nullptr.  Otherwise, returns a
// pointer to the key delta (just past the three decoded values).
static inline const char* DecodeEntry(const char* p, const char* limit,
                                      uint32_t* shared, uint32_t* non_shared,
                                      uint32_t* value_length) {
  if (limit - p < 3) return nullptr;
  *shared = reinterpret_cast<const uint8_t*>(p)[0];
  *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
  *value_length = reinterpret_cast<const uint8_t*>(p)[2];
  if ((*shared | *non_shared | *value_length) < 128) {
    // Fast path: all three values are encoded in one byte each
    p += 3;
  } else {
    if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
    if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
    if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
  }

  if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
    return nullptr;
  }
  return p;
}

class Block::Iter : public Iterator {
 private:
  const Comparator* const comparator_;
  const char* const data_;       // underlying block contents
  uint32_t const restarts_;      // Offset of restart array (list of fixed32)
  uint32_t const num_restarts_;  // Number of uint32_t entries in restart array

  // current_ is offset in data_ of current entry.  >= restarts_ if !Valid
  uint32_t current_;
  uint32_t restart_index_;  // Index of restart block in which current_ falls
  std::string key_;
  Slice value_;
  Status status_;

  inline int Compare(const Slice& a, const Slice& b) const {
    return comparator_->Compare(a, b);
  }

  // Return the offset in data_ just past the end of the current entry.
  inline uint32_t NextEntryOffset() const {
    return (value_.data() + value_.size()) - data_;
  }

  uint32_t GetRestartPoint(uint32_t index) {
    assert(index < num_restarts_);
    return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
  }

  void SeekToRestartPoint(uint32_t index) {
    key_.clear();
    restart_index_ = index;
    // current_ will be fixed by ParseNextKey();

    // ParseNextKey() starts at the end of value_, so set value_ accordingly
    uint32_t offset = GetRestartPoint(index);
    value_ = Slice(data_ + offset, 0);
  }

 public:
  Iter(const Comparator* comparator, const char* data, uint32_t restarts,
       uint32_t num_restarts)
      : comparator_(comparator),
        data_(data),
        restarts_(restarts),
        num_restarts_(num_restarts),
        current_(restarts_),
        restart_index_(num_restarts_) {
    assert(num_restarts_ > 0);
  }

  bool Valid() const override { return current_ < restarts_; }
  Status status() const override { return status_; }
  Slice key() const override {
    assert(Valid());
    return key_;
  }
  Slice value() const override {
    assert(Valid());
    return value_;
  }

  void Next() override {
    assert(Valid());
    ParseNextKey();
  }

  void Prev() override {
    assert(Valid());

    // Scan backwards to a restart point before current_
    const uint32_t original = current_;
    while (GetRestartPoint(restart_index_) >= original) {
      if (restart_index_ == 0) {
        // No more entries
        current_ = restarts_;
        restart_index_ = num_restarts_;
        return;
      }
      restart_index_--;
    }

    SeekToRestartPoint(restart_index_);
    do {
      // Loop until end of current entry hits the start of original entry
    } while (ParseNextKey() && NextEntryOffset() < original);
  }

  void Seek(const Slice& target) override {
    // Binary search in restart array to find the last restart point
    // with a key < target
    uint32_t left = 0;
    uint32_t right = num_restarts_ - 1;
    while (left < right) {
      uint32_t mid = (left + right + 1) / 2;
      uint32_t region_offset = GetRestartPoint(mid);
      uint32_t shared, non_shared, value_length;
      const char* key_ptr =
          DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
                      &non_shared, &value_length);
      if (key_ptr == nullptr || (shared != 0)) {
        CorruptionError();
        return;
      }
      Slice mid_key(key_ptr, non_shared);
      if (Compare(mid_key, target) < 0) {
        // Key at "mid" is smaller than "target".  Therefore all
        // blocks before "mid" are uninteresting.
        left = mid;
      } else {
        // Key at "mid" is >= "target".  Therefore all blocks at or
        // after "mid" are uninteresting.
        right = mid - 1;
      }
    }

    // Linear search (within restart block) for first key >= target
    SeekToRestartPoint(left);
    while (true) {
      if (!ParseNextKey()) {
        return;
      }
      if (Compare(key_, target) >= 0) {
        return;
      }
    }
  }

  void SeekToFirst() override {
    SeekToRestartPoint(0);
    ParseNextKey();
  }

  void SeekToLast() override {
    SeekToRestartPoint(num_restarts_ - 1);
    while (ParseNextKey() && NextEntryOffset() < restarts_) {
      // Keep skipping
    }
  }

 private:
  void CorruptionError() {
    current_ = restarts_;
    restart_index_ = num_restarts_;
    status_ = Status::Corruption("bad entry in block");
    key_.clear();
    value_.clear();
  }

  bool ParseNextKey() {
    current_ = NextEntryOffset();
    const char* p = data_ + current_;
    const char* limit = data_ + restarts_;  // Restarts come right after data
    if (p >= limit) {
      // No more entries to return.  Mark as invalid.
      current_ = restarts_;
      restart_index_ = num_restarts_;
      return false;
    }

    // Decode next entry
    uint32_t shared, non_shared, value_length;
    p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
    if (p == nullptr || key_.size() < shared) {
      CorruptionError();
      return false;
    } else {
      key_.resize(shared);
      key_.append(p, non_shared);
      value_ = Slice(p + non_shared, value_length);
      while (restart_index_ + 1 < num_restarts_ &&
             GetRestartPoint(restart_index_ + 1) < current_) {
        ++restart_index_;
      }
      return true;
    }
  }
};

Iterator* Block::NewIterator(const Comparator* comparator) {
  if (size_ < sizeof(uint32_t)) {
    return NewErrorIterator(Status::Corruption("bad block contents"));
  }
  const uint32_t num_restarts = NumRestarts();
  if (num_restarts == 0) {
    return NewEmptyIterator();
  } else {
    return new Iter(comparator, data_, restart_offset_, num_restarts);
  }
}

}  // namespace leveldb

Coverage Report

Created: 2025-06-10 13:21

Line	Count	Source
1		// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2		// Use of this source code is governed by a BSD-style license that can be
3		// found in the LICENSE file. See the AUTHORS file for names of contributors.
4		//
5		// Decodes the blocks generated by block_builder.cc.
6
7		#include "table/block.h"
8
9		#include <algorithm>
10		#include <cstdint>
11		#include <vector>
12
13		#include "leveldb/comparator.h"
14		#include "table/format.h"
15		#include "util/coding.h"
16		#include "util/logging.h"
17
18		namespace leveldb {
19
20	192	inline uint32_t Block::NumRestarts() const {
21	192	assert(size_ >= sizeof(uint32_t)); Branch (21:3): [True: 192, False: 0]
22	192	return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
23	192	}
24
25		Block::Block(const BlockContents& contents)
26	60	: data_(contents.data.data()),
27	60	size_(contents.data.size()),
28	60	owned_(contents.heap_allocated) {
29	60	if (size_ < sizeof(uint32_t)) { Branch (29:7): [True: 0, False: 60]
30	0	size_ = 0; // Error marker
31	60	} else {
32	60	size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
33	60	if (NumRestarts() > max_restarts_allowed) { Branch (33:9): [True: 0, False: 60]
34		// The size is too small for NumRestarts()
35	0	size_ = 0;
36	60	} else {
37	60	restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
38	60	}
39	60	}
40	60	}
41
42	60	Block::~Block() {
43	60	if (owned_) { Branch (43:7): [True: 0, False: 60]
44	0	delete[] data_;
45	0	}
46	60	}
47
48		// Helper routine: decode the next block entry starting at "p",
49		// storing the number of shared key bytes, non_shared key bytes,
50		// and the length of the value in "shared", "non_shared", and
51		// "*value_length", respectively. Will not dereference past "limit".
52		//
53		// If any errors are detected, returns nullptr. Otherwise, returns a
54		// pointer to the key delta (just past the three decoded values).
55		static inline const char* DecodeEntry(const char* p, const char* limit,
56		uint32_t* shared, uint32_t* non_shared,
57	295	uint32_t* value_length) {
58	295	if (limit - p < 3) return nullptr; Branch (58:7): [True: 0, False: 295]
59	295	shared = reinterpret_cast<const uint8_t>(p)[0];
60	295	non_shared = reinterpret_cast<const uint8_t>(p)[1];
61	295	value_length = reinterpret_cast<const uint8_t>(p)[2];
62	295	if ((shared \| non_shared \| *value_length) < 128) { Branch (62:7): [True: 295, False: 0]
63		// Fast path: all three values are encoded in one byte each
64	295	p += 3;
65	295	} else {
66	0	if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr; Branch (66:9): [True: 0, False: 0]
67	0	if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr; Branch (67:9): [True: 0, False: 0]
68	0	if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr; Branch (68:9): [True: 0, False: 0]
69	0	}
70
71	295	if (static_cast<uint32_t>(limit - p) < (non_shared + value_length)) { Branch (71:7): [True: 0, False: 295]
72	0	return nullptr;
73	0	}
74	295	return p;
75	295	}
76
77		class Block::Iter : public Iterator {
78		private:
79		const Comparator* const comparator_;
80		const char* const data_; // underlying block contents
81		uint32_t const restarts_; // Offset of restart array (list of fixed32)
82		uint32_t const num_restarts_; // Number of uint32_t entries in restart array
83
84		// current_ is offset in data_ of current entry. >= restarts_ if !Valid
85		uint32_t current_;
86		uint32_t restart_index_; // Index of restart block in which current_ falls
87		std::string key_;
88		Slice value_;
89		Status status_;
90
91	263	inline int Compare(const Slice& a, const Slice& b) const {
92	263	return comparator_->Compare(a, b);
93	263	}
94
95		// Return the offset in data_ just past the end of the current entry.
96	230	inline uint32_t NextEntryOffset() const {
97	230	return (value_.data() + value_.size()) - data_;
98	230	}
99
100	244	uint32_t GetRestartPoint(uint32_t index) {
101	244	assert(index < num_restarts_); Branch (101:5): [True: 244, False: 0]
102	244	return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
103	244	}
104
105	48	void SeekToRestartPoint(uint32_t index) {
106	48	key_.clear();
107	48	restart_index_ = index;
108		// current_ will be fixed by ParseNextKey();
109
110		// ParseNextKey() starts at the end of value_, so set value_ accordingly
111	48	uint32_t offset = GetRestartPoint(index);
112	48	value_ = Slice(data_ + offset, 0);
113	48	}
114
115		public:
116		Iter(const Comparator* comparator, const char* data, uint32_t restarts,
117		uint32_t num_restarts)
118	72	: comparator_(comparator),
119	72	data_(data),
120	72	restarts_(restarts),
121	72	num_restarts_(num_restarts),
122	72	current_(restarts_),
123	72	restart_index_(num_restarts_) {
124	72	assert(num_restarts_ > 0); Branch (124:5): [True: 72, False: 0]
125	72	}
126
127	356	bool Valid() const override { return current_ < restarts_; }
128	48	Status status() const override { return status_; }
129	75	Slice key() const override {
130	75	assert(Valid()); Branch (130:5): [True: 75, False: 0]
131	75	return key_;
132	75	}
133	103	Slice value() const override {
134	103	assert(Valid()); Branch (134:5): [True: 103, False: 0]
135	103	return value_;
136	103	}
137
138	46	void Next() override {
139	46	assert(Valid()); Branch (139:5): [True: 46, False: 0]
140	46	ParseNextKey();
141	46	}
142
143	0	void Prev() override {
144	0	assert(Valid()); Branch (144:5): [True: 0, False: 0]
145
146		// Scan backwards to a restart point before current_
147	0	const uint32_t original = current_;
148	0	while (GetRestartPoint(restart_index_) >= original) { Branch (148:12): [True: 0, False: 0]
149	0	if (restart_index_ == 0) { Branch (149:11): [True: 0, False: 0]
150		// No more entries
151	0	current_ = restarts_;
152	0	restart_index_ = num_restarts_;
153	0	return;
154	0	}
155	0	restart_index_--;
156	0	}
157
158	0	SeekToRestartPoint(restart_index_);
159	0	do {
160		// Loop until end of current entry hits the start of original entry
161	0	} while (ParseNextKey() && NextEntryOffset() < original); Branch (161:14): [True: 0, False: 0] Branch (161:32): [True: 0, False: 0]
162	0	}
163
164	48	void Seek(const Slice& target) override {
165		// Binary search in restart array to find the last restart point
166		// with a key < target
167	48	uint32_t left = 0;
168	48	uint32_t right = num_restarts_ - 1;
169	127	while (left < right) { Branch (169:12): [True: 79, False: 48]
170	79	uint32_t mid = (left + right + 1) / 2;
171	79	uint32_t region_offset = GetRestartPoint(mid);
172	79	uint32_t shared, non_shared, value_length;
173	79	const char* key_ptr =
174	79	DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
175	79	&non_shared, &value_length);
176	79	if (key_ptr == nullptr \|\| (shared != 0)) { Branch (176:11): [True: 0, False: 79] Branch (176:33): [True: 0, False: 79]
177	0	CorruptionError();
178	0	return;
179	0	}
180	79	Slice mid_key(key_ptr, non_shared);
181	79	if (Compare(mid_key, target) < 0) { Branch (181:11): [True: 61, False: 18]
182		// Key at "mid" is smaller than "target". Therefore all
183		// blocks before "mid" are uninteresting.
184	61	left = mid;
185	61	} else {
186		// Key at "mid" is >= "target". Therefore all blocks at or
187		// after "mid" are uninteresting.
188	18	right = mid - 1;
189	18	}
190	79	}
191
192		// Linear search (within restart block) for first key >= target
193	48	SeekToRestartPoint(left);
194	184	while (true) { Branch (194:12): [Folded - Ignored]
195	184	if (!ParseNextKey()) { Branch (195:11): [True: 0, False: 184]
196	0	return;
197	0	}
198	184	if (Compare(key_, target) >= 0) { Branch (198:11): [True: 48, False: 136]
199	48	return;
200	48	}
201	184	}
202	48	}
203
204	0	void SeekToFirst() override {
205	0	SeekToRestartPoint(0);
206	0	ParseNextKey();
207	0	}
208
209	0	void SeekToLast() override {
210	0	SeekToRestartPoint(num_restarts_ - 1);
211	0	while (ParseNextKey() && NextEntryOffset() < restarts_) { Branch (211:12): [True: 0, False: 0] Branch (211:30): [True: 0, False: 0]
212		// Keep skipping
213	0	}
214	0	}
215
216		private:
217	0	void CorruptionError() {
218	0	current_ = restarts_;
219	0	restart_index_ = num_restarts_;
220	0	status_ = Status::Corruption("bad entry in block");
221	0	key_.clear();
222	0	value_.clear();
223	0	}
224
225	230	bool ParseNextKey() {
226	230	current_ = NextEntryOffset();
227	230	const char* p = data_ + current_;
228	230	const char* limit = data_ + restarts_; // Restarts come right after data
229	230	if (p >= limit) { Branch (229:9): [True: 14, False: 216]
230		// No more entries to return. Mark as invalid.
231	14	current_ = restarts_;
232	14	restart_index_ = num_restarts_;
233	14	return false;
234	14	}
235
236		// Decode next entry
237	216	uint32_t shared, non_shared, value_length;
238	216	p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
239	216	if (p == nullptr \|\| key_.size() < shared) { Branch (239:9): [True: 0, False: 216] Branch (239:25): [True: 0, False: 216]
240	0	CorruptionError();
241	0	return false;
242	216	} else {
243	216	key_.resize(shared);
244	216	key_.append(p, non_shared);
245	216	value_ = Slice(p + non_shared, value_length);
246	219	while (restart_index_ + 1 < num_restarts_ && Branch (246:14): [True: 117, False: 102]
247	219	GetRestartPoint(restart_index_ + 1) < current_) { Branch (247:14): [True: 3, False: 114]
248	3	++restart_index_;
249	3	}
250	216	return true;
251	216	}
252	216	}
253		};
254
255	72	Iterator* Block::NewIterator(const Comparator* comparator) {
256	72	if (size_ < sizeof(uint32_t)) { Branch (256:7): [True: 0, False: 72]
257	0	return NewErrorIterator(Status::Corruption("bad block contents"));
258	0	}
259	72	const uint32_t num_restarts = NumRestarts();
260	72	if (num_restarts == 0) { Branch (260:7): [True: 0, False: 72]
261	0	return NewEmptyIterator();
262	72	} else {
263	72	return new Iter(comparator, data_, restart_offset_, num_restarts);
264	72	}
265	72	}
266
267		} // namespace leveldb