提供基本的ttl测试用例
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

380 lines
11 KiB

Release 1.18 Changes are: * Update version number to 1.18 * Replace the basic fprintf call with a call to fwrite in order to work around the apparent compiler optimization/rewrite failure that we are seeing with the new toolchain/iOS SDKs provided with Xcode6 and iOS8. * Fix ALL the header guards. * Createed a README.md with the LevelDB project description. * A new CONTRIBUTING file. * Don't implicitly convert uint64_t to size_t or int. Either preserve it as uint64_t, or explicitly cast. This fixes MSVC warnings about possible value truncation when compiling this code in Chromium. * Added a DumpFile() library function that encapsulates the guts of the "leveldbutil dump" command. This will allow clients to dump data to their log files instead of stdout. It will also allow clients to supply their own environment. * leveldb: Remove unused function 'ConsumeChar'. * leveldbutil: Remove unused member variables from WriteBatchItemPrinter. * OpenBSD, NetBSD and DragonflyBSD have _LITTLE_ENDIAN, so define PLATFORM_IS_LITTLE_ENDIAN like on FreeBSD. This fixes: * issue #143 * issue #198 * issue #249 * Switch from <cstdatomic> to <atomic>. The former never made it into the standard and doesn't exist in modern gcc versions at all. The later contains everything that leveldb was using from the former. This problem was noticed when porting to Portable Native Client where no memory barrier is defined. The fact that <cstdatomic> is missing normally goes unnoticed since memory barriers are defined for most architectures. * Make Hash() treat its input as unsigned. Before this change LevelDB files from platforms with different signedness of char were not compatible. This change fixes: issue #243 * Verify checksums of index/meta/filter blocks when paranoid_checks set. * Invoke all tools for iOS with xcrun. (This was causing problems with the new XCode 5.1.1 image on pulse.) * include <sys/stat.h> only once, and fix the following linter warning: "Found C system header after C++ system header" * When encountering a corrupted table file, return Status::Corruption instead of Status::InvalidArgument. * Support cygwin as build platform, patch is from https://code.google.com/p/leveldb/issues/detail?id=188 * Fix typo, merge patch from https://code.google.com/p/leveldb/issues/detail?id=159 * Fix typos and comments, and address the following two issues: * issue #166 * issue #241 * Add missing db synchronize after "fillseq" in the benchmark. * Removed unused variable in SeekRandom: value (issue #201)
10 years ago
  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. #ifndef STORAGE_LEVELDB_DB_SKIPLIST_H_
  5. #define STORAGE_LEVELDB_DB_SKIPLIST_H_
  6. // Thread safety
  7. // -------------
  8. //
  9. // Writes require external synchronization, most likely a mutex.
  10. // Reads require a guarantee that the SkipList will not be destroyed
  11. // while the read is in progress. Apart from that, reads progress
  12. // without any internal locking or synchronization.
  13. //
  14. // Invariants:
  15. //
  16. // (1) Allocated nodes are never deleted until the SkipList is
  17. // destroyed. This is trivially guaranteed by the code since we
  18. // never delete any skip list nodes.
  19. //
  20. // (2) The contents of a Node except for the next/prev pointers are
  21. // immutable after the Node has been linked into the SkipList.
  22. // Only Insert() modifies the list, and it is careful to initialize
  23. // a node and use release-stores to publish the nodes in one or
  24. // more lists.
  25. //
  26. // ... prev vs. next pointer ordering ...
  27. #include <atomic>
  28. #include <cassert>
  29. #include <cstdlib>
  30. #include "util/arena.h"
  31. #include "util/random.h"
  32. namespace leveldb {
  33. template <typename Key, class Comparator>
  34. class SkipList {
  35. private:
  36. struct Node;
  37. public:
  38. // Create a new SkipList object that will use "cmp" for comparing keys,
  39. // and will allocate memory using "*arena". Objects allocated in the arena
  40. // must remain allocated for the lifetime of the skiplist object.
  41. explicit SkipList(Comparator cmp, Arena* arena);
  42. SkipList(const SkipList&) = delete;
  43. SkipList& operator=(const SkipList&) = delete;
  44. // Insert key into the list.
  45. // REQUIRES: nothing that compares equal to key is currently in the list.
  46. void Insert(const Key& key);
  47. // Returns true iff an entry that compares equal to key is in the list.
  48. bool Contains(const Key& key) const;
  49. // Iteration over the contents of a skip list
  50. class Iterator {
  51. public:
  52. // Initialize an iterator over the specified list.
  53. // The returned iterator is not valid.
  54. explicit Iterator(const SkipList* list);
  55. // Returns true iff the iterator is positioned at a valid node.
  56. bool Valid() const;
  57. // Returns the key at the current position.
  58. // REQUIRES: Valid()
  59. const Key& key() const;
  60. // Advances to the next position.
  61. // REQUIRES: Valid()
  62. void Next();
  63. // Advances to the previous position.
  64. // REQUIRES: Valid()
  65. void Prev();
  66. // Advance to the first entry with a key >= target
  67. void Seek(const Key& target);
  68. // Position at the first entry in list.
  69. // Final state of iterator is Valid() iff list is not empty.
  70. void SeekToFirst();
  71. // Position at the last entry in list.
  72. // Final state of iterator is Valid() iff list is not empty.
  73. void SeekToLast();
  74. private:
  75. const SkipList* list_;
  76. Node* node_;
  77. // Intentionally copyable
  78. };
  79. private:
  80. enum { kMaxHeight = 12 };
  81. inline int GetMaxHeight() const {
  82. return max_height_.load(std::memory_order_relaxed);
  83. }
  84. Node* NewNode(const Key& key, int height);
  85. int RandomHeight();
  86. bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }
  87. // Return true if key is greater than the data stored in "n"
  88. bool KeyIsAfterNode(const Key& key, Node* n) const;
  89. // Return the earliest node that comes at or after key.
  90. // Return nullptr if there is no such node.
  91. //
  92. // If prev is non-null, fills prev[level] with pointer to previous
  93. // node at "level" for every level in [0..max_height_-1].
  94. Node* FindGreaterOrEqual(const Key& key, Node** prev) const;
  95. // Return the latest node with a key < key.
  96. // Return head_ if there is no such node.
  97. Node* FindLessThan(const Key& key) const;
  98. // Return the last node in the list.
  99. // Return head_ if list is empty.
  100. Node* FindLast() const;
  101. // Immutable after construction
  102. Comparator const compare_;
  103. Arena* const arena_; // Arena used for allocations of nodes
  104. Node* const head_;
  105. // Modified only by Insert(). Read racily by readers, but stale
  106. // values are ok.
  107. std::atomic<int> max_height_; // Height of the entire list
  108. // Read/written only by Insert().
  109. Random rnd_;
  110. };
  111. // Implementation details follow
  112. template <typename Key, class Comparator>
  113. struct SkipList<Key, Comparator>::Node {
  114. explicit Node(const Key& k) : key(k) {}
  115. Key const key;
  116. // Accessors/mutators for links. Wrapped in methods so we can
  117. // add the appropriate barriers as necessary.
  118. Node* Next(int n) {
  119. assert(n >= 0);
  120. // Use an 'acquire load' so that we observe a fully initialized
  121. // version of the returned Node.
  122. return next_[n].load(std::memory_order_acquire);
  123. }
  124. void SetNext(int n, Node* x) {
  125. assert(n >= 0);
  126. // Use a 'release store' so that anybody who reads through this
  127. // pointer observes a fully initialized version of the inserted node.
  128. next_[n].store(x, std::memory_order_release);
  129. }
  130. // No-barrier variants that can be safely used in a few locations.
  131. Node* NoBarrier_Next(int n) {
  132. assert(n >= 0);
  133. return next_[n].load(std::memory_order_relaxed);
  134. }
  135. void NoBarrier_SetNext(int n, Node* x) {
  136. assert(n >= 0);
  137. next_[n].store(x, std::memory_order_relaxed);
  138. }
  139. private:
  140. // Array of length equal to the node height. next_[0] is lowest level link.
  141. std::atomic<Node*> next_[1];
  142. };
  143. template <typename Key, class Comparator>
  144. typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
  145. const Key& key, int height) {
  146. char* const node_memory = arena_->AllocateAligned(
  147. sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
  148. return new (node_memory) Node(key);
  149. }
  150. template <typename Key, class Comparator>
  151. inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) {
  152. list_ = list;
  153. node_ = nullptr;
  154. }
  155. template <typename Key, class Comparator>
  156. inline bool SkipList<Key, Comparator>::Iterator::Valid() const {
  157. return node_ != nullptr;
  158. }
  159. template <typename Key, class Comparator>
  160. inline const Key& SkipList<Key, Comparator>::Iterator::key() const {
  161. assert(Valid());
  162. return node_->key;
  163. }
  164. template <typename Key, class Comparator>
  165. inline void SkipList<Key, Comparator>::Iterator::Next() {
  166. assert(Valid());
  167. node_ = node_->Next(0);
  168. }
  169. template <typename Key, class Comparator>
  170. inline void SkipList<Key, Comparator>::Iterator::Prev() {
  171. // Instead of using explicit "prev" links, we just search for the
  172. // last node that falls before key.
  173. assert(Valid());
  174. node_ = list_->FindLessThan(node_->key);
  175. if (node_ == list_->head_) {
  176. node_ = nullptr;
  177. }
  178. }
  179. template <typename Key, class Comparator>
  180. inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
  181. node_ = list_->FindGreaterOrEqual(target, nullptr);
  182. }
  183. template <typename Key, class Comparator>
  184. inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() {
  185. node_ = list_->head_->Next(0);
  186. }
  187. template <typename Key, class Comparator>
  188. inline void SkipList<Key, Comparator>::Iterator::SeekToLast() {
  189. node_ = list_->FindLast();
  190. if (node_ == list_->head_) {
  191. node_ = nullptr;
  192. }
  193. }
  194. template <typename Key, class Comparator>
  195. int SkipList<Key, Comparator>::RandomHeight() {
  196. // Increase height with probability 1 in kBranching
  197. static const unsigned int kBranching = 4;
  198. int height = 1;
  199. while (height < kMaxHeight && rnd_.OneIn(kBranching)) {
  200. height++;
  201. }
  202. assert(height > 0);
  203. assert(height <= kMaxHeight);
  204. return height;
  205. }
  206. template <typename Key, class Comparator>
  207. bool SkipList<Key, Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {
  208. // null n is considered infinite
  209. return (n != nullptr) && (compare_(n->key, key) < 0);
  210. }
  211. template <typename Key, class Comparator>
  212. typename SkipList<Key, Comparator>::Node*
  213. SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
  214. Node** prev) const {
  215. Node* x = head_;
  216. int level = GetMaxHeight() - 1;
  217. while (true) {
  218. Node* next = x->Next(level);
  219. if (KeyIsAfterNode(key, next)) {
  220. // Keep searching in this list
  221. x = next;
  222. } else {
  223. if (prev != nullptr) prev[level] = x;
  224. if (level == 0) {
  225. return next;
  226. } else {
  227. // Switch to next list
  228. level--;
  229. }
  230. }
  231. }
  232. }
  233. template <typename Key, class Comparator>
  234. typename SkipList<Key, Comparator>::Node*
  235. SkipList<Key, Comparator>::FindLessThan(const Key& key) const {
  236. Node* x = head_;
  237. int level = GetMaxHeight() - 1;
  238. while (true) {
  239. assert(x == head_ || compare_(x->key, key) < 0);
  240. Node* next = x->Next(level);
  241. if (next == nullptr || compare_(next->key, key) >= 0) {
  242. if (level == 0) {
  243. return x;
  244. } else {
  245. // Switch to next list
  246. level--;
  247. }
  248. } else {
  249. x = next;
  250. }
  251. }
  252. }
  253. template <typename Key, class Comparator>
  254. typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::FindLast()
  255. const {
  256. Node* x = head_;
  257. int level = GetMaxHeight() - 1;
  258. while (true) {
  259. Node* next = x->Next(level);
  260. if (next == nullptr) {
  261. if (level == 0) {
  262. return x;
  263. } else {
  264. // Switch to next list
  265. level--;
  266. }
  267. } else {
  268. x = next;
  269. }
  270. }
  271. }
  272. template <typename Key, class Comparator>
  273. SkipList<Key, Comparator>::SkipList(Comparator cmp, Arena* arena)
  274. : compare_(cmp),
  275. arena_(arena),
  276. head_(NewNode(0 /* any key will do */, kMaxHeight)),
  277. max_height_(1),
  278. rnd_(0xdeadbeef) {
  279. for (int i = 0; i < kMaxHeight; i++) {
  280. head_->SetNext(i, nullptr);
  281. }
  282. }
  283. template <typename Key, class Comparator>
  284. void SkipList<Key, Comparator>::Insert(const Key& key) {
  285. // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  286. // here since Insert() is externally synchronized.
  287. Node* prev[kMaxHeight];
  288. Node* x = FindGreaterOrEqual(key, prev);
  289. // Our data structure does not allow duplicate insertion
  290. assert(x == nullptr || !Equal(key, x->key));
  291. int height = RandomHeight();
  292. if (height > GetMaxHeight()) {
  293. for (int i = GetMaxHeight(); i < height; i++) {
  294. prev[i] = head_;
  295. }
  296. // It is ok to mutate max_height_ without any synchronization
  297. // with concurrent readers. A concurrent reader that observes
  298. // the new value of max_height_ will see either the old value of
  299. // new level pointers from head_ (nullptr), or a new value set in
  300. // the loop below. In the former case the reader will
  301. // immediately drop to the next level since nullptr sorts after all
  302. // keys. In the latter case the reader will use the new node.
  303. max_height_.store(height, std::memory_order_relaxed);
  304. }
  305. x = NewNode(key, height);
  306. for (int i = 0; i < height; i++) {
  307. // NoBarrier_SetNext() suffices since we will add a barrier when
  308. // we publish a pointer to "x" in prev[i].
  309. x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
  310. prev[i]->SetNext(i, x);
  311. }
  312. }
  313. template <typename Key, class Comparator>
  314. bool SkipList<Key, Comparator>::Contains(const Key& key) const {
  315. Node* x = FindGreaterOrEqual(key, nullptr);
  316. if (x != nullptr && Equal(key, x->key)) {
  317. return true;
  318. } else {
  319. return false;
  320. }
  321. }
  322. } // namespace leveldb
  323. #endif // STORAGE_LEVELDB_DB_SKIPLIST_H_