Skip to content

Commit c86265d

Browse files
andrewbytecoderandrewbytecoder
committed
添加双向链表实现
1 parent 3aa45c6 commit c86265d

File tree

6 files changed

+143
-14
lines changed

6 files changed

+143
-14
lines changed

‎db/db_impl.cc

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1161,6 +1161,7 @@ namespace leveldb {
11611161
}
11621162

11631163
Iterator *DBImpl::NewIterator(const ReadOptions &options) {
1164+
// 序列号
11641165
SequenceNumber latest_snapshot;
11651166
uint32_t seed;
11661167
Iterator *iter = NewInternalIterator(options, &latest_snapshot, &seed);

‎demo/CMakeLists.txt

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,8 @@ target_link_libraries(test
2222
target_include_directories(test
2323
PUBLIC ${PROJECT_SOURCE_DIR}/include)
2424

25+
add_executable(list
26+
list/tail_list.cpp)
2527

2628
# 添加各个算法测试代码
2729
add_subdirectory(batch_test)

‎demo/leveldb_exec.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,34 @@ int main(int argc, char *argv[]) {
6464
}
6565
}
6666

67+
// 使用迭代器去除数据库中所有的数据
68+
leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
69+
for (it->SeekToFirst(); it->Valid(); it->Next()) {
70+
cout << it->key().ToString() << ": " << it->value().ToString() << endl;
71+
}
72+
assert(it->status().ok()); // Check for any errors found during the scan
73+
74+
std::cout << "==================================" << std::endl;
75+
// 定位都 4开头的，然后指向该值
76+
for (it->Seek("4");
77+
it->Valid()/* && it->key().ToString() < "5"*/;
78+
it->Next()) {
79+
cout << it->key().ToString() << ": " << it->value().ToString() << endl;
80+
}
81+
// 反向迭代
82+
for (it->SeekToLast(); it->Valid(); it->Prev()) {
83+
cout << it->key().ToString() << ": " << it->value().ToString() << endl;
84+
}
85+
86+
delete it;
87+
88+
// 为数据库创建快照
89+
leveldb::ReadOptions readOptions;
90+
readOptions.snapshot = db->GetSnapshot();
91+
leveldb::Iterator* iter = db->NewIterator(readOptions);
92+
delete iter;
93+
db->ReleaseSnapshot(readOptions.snapshot);
94+
6795
// 数据库不使用的时候记得及时清除
6896
delete db;
6997

‎demo/list/tail_list.cpp

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
//
2+
// Created by wangyz38535 on 2024/4/24.
3+
//
4+
5+
#include <iostream>
6+
7+
// 尾插式循环链表
8+
class TailList;
9+
10+
class Snapshot {
11+
public:
12+
~Snapshot() = default;
13+
};
14+
15+
// Snapshots are kept in a doubly-linked list in the DB.
16+
// Each SnapshotImpl corresponds to a particular sequence number.
17+
class NodeImpl : public Snapshot {
18+
public:
19+
explicit NodeImpl(uint64_t sequence_number)
20+
: sequence_number_(sequence_number) {}
21+
22+
uint64_t sequence_number() const { return sequence_number_; }
23+
24+
private:
25+
friend class TailList;
26+
27+
// NodeImpl is kept in a doubly-linked circular list. The TailList
28+
// implementation operates on the next/previous fields direcly.
29+
NodeImpl* prev_{};
30+
NodeImpl* next_{};
31+
32+
const uint64_t sequence_number_;
33+
};
34+
35+
class TailList {
36+
public:
37+
TailList() : head_(0) {
38+
head_.prev_ = &head_;
39+
head_.next_ = &head_;
40+
}
41+
42+
bool empty() const { return head_.next_ == &head_; }
43+
NodeImpl* oldest() const {
44+
return head_.next_;
45+
}
46+
NodeImpl* newest() const {
47+
return head_.prev_;
48+
}
49+
50+
// new 出一个node节点，并把对应的node放到链表结尾
51+
NodeImpl* New(uint64_t sequence_number) {
52+
53+
auto* snapshot = new NodeImpl(sequence_number);
54+
55+
snapshot->next_ = &head_;
56+
snapshot->prev_ = head_.prev_;
57+
snapshot->prev_->next_ = snapshot;
58+
snapshot->next_->prev_ = snapshot;
59+
return snapshot;
60+
}
61+
62+
// Removes a NodeImpl from this list.
63+
//
64+
// The snapshot must have been created by calling New() on this list.
65+
//
66+
// The snapshot pointer should not be const, because its memory is
67+
// deallocated. However, that would force us to change DB::ReleaseSnapshot(),
68+
// which is in the API, and currently takes a const Snapshot.
69+
static void Delete(const NodeImpl* snapshot) {
70+
snapshot->prev_->next_ = snapshot->next_;
71+
snapshot->next_->prev_ = snapshot->prev_;
72+
delete snapshot;
73+
}
74+
75+
private:
76+
// Dummy head of doubly-linked list of snapshots
77+
NodeImpl head_;
78+
};
79+
80+
81+
int main(int argc, char* argv[]) {
82+
83+
TailList list;
84+
85+
list.New(1);
86+
list.New(2);
87+
list.New(3);
88+
list.New(3);
89+
list.New(3);
90+
list.New(3);
91+
92+
do {
93+
94+
auto lpNode = list.newest();
95+
std::cout << lpNode->sequence_number() << std::endl;
96+
TailList::Delete(lpNode);
97+
98+
} while (!list.empty());
99+
100+
101+
return 0;
102+
}
103+

‎doc/instruction/readme.adoc

Lines changed: 5 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -245,8 +245,7 @@ assert(it->status().ok()); // Check for any errors found during the scan
245245
delete it;
246246
```
247247

248-
The following variation shows how to process just the keys in the range
249-
[start,limit):
248+
Seek可以查询某个值，并将迭代器指向该值，通过限定范围可以查询一定范围内的数据[start,limit):
250249

251250
```c++
252251
for (it->Seek(start);
@@ -266,14 +265,12 @@ for (it->SeekToLast(); it->Valid(); it->Prev()) {
266265
```
267266

268267
=== Snapshots
268+
通过方法 `DB::GetSnapshot()` 可以创建 `leveldb` 数据库的快照
269269

270-
Snapshots provide consistent read-only views over the entire state of the
271-
key-value store. `ReadOptions::snapshot` may be non-NULL to indicate that a
272-
read should operate on a particular version of the DB state. If
273-
`ReadOptions::snapshot` is NULL, the read will operate on an implicit snapshot
274-
of the current state.
270+
快照为键值存储提供了一个只读的视图，当 `ReadOptions::snapshot` 非空时代表一个指定版本数据库状态视图。如果 `ReadOptions::snapshot` 为空，读取的数据将从隐式快照中获取。
271+
272+
“implicit snapshot”是指在用户未明确指定快照的情况下，数据库系统自动为读操作创建并使用的一个代表当前数据库状态的临时快照，以提供数据一致性保障。这种机制免去了用户手动管理快照的复杂性，适用于大多数常规查询场景。
275273

276-
Snapshots are created by the `DB::GetSnapshot()` method:
277274

278275
```c++
279276
leveldb::ReadOptions options;

‎include/leveldb/db.h

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -90,12 +90,10 @@ namespace leveldb {
9090
virtual Status Get(const ReadOptions &options, const Slice &key,
9191
std::string *value) = 0;
9292

93-
// Return a heap-allocated iterator over the contents of the database.
94-
// The result of NewIterator() is initially invalid (caller must
95-
// call one of the Seek methods on the iterator before using it).
96-
//
97-
// Caller should delete the iterator when it is no longer needed.
98-
// The returned iterator should be deleted before this db is deleted.
93+
// 返回一个在堆上申请，迭代器中包含数据库所有的内容
94+
// 需要注意的是NewIterator返回的迭代器指向是非法的，因此在正常使用在使用迭代器时，
95+
// 必须先调用一下Seek方法
96+
// 当迭代器不在使用时，需要进行及时删除，并且删除需要保证在数据库删除之前
9997
virtual Iterator *NewIterator(const ReadOptions &options) = 0;
10098

10199
// Return a handle to the current DB state. Iterators created with

0 commit comments

Comments
 (0)