1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#ifndef STORAGE_LEVELDB_DB_MEMTABLE_H_ 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#define STORAGE_LEVELDB_DB_MEMTABLE_H_ 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <string> 9fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/db.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/dbformat.h" 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/skiplist.h" 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/arena.h" 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass InternalKeyComparator; 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Mutex; 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass MemTableIterator; 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass MemTable { 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 22a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // MemTables are reference counted. The initial reference count 23a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // is zero and the caller must call Ref() at least once. 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit MemTable(const InternalKeyComparator& comparator); 25a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 26a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Increase reference count. 27a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org void Ref() { ++refs_; } 28a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 29a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Drop reference count. Delete if no more references exist. 30a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org void Unref() { 31a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org --refs_; 32a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(refs_ >= 0); 33a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (refs_ <= 0) { 34a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org delete this; 35a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 36a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Returns an estimate of the number of bytes of data in use by this 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // data structure. 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: external synchronization to prevent simultaneous 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // operations on the same MemTable. 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t ApproximateMemoryUsage(); 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return an iterator that yields the contents of the memtable. 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // The caller must ensure that the underlying MemTable remains live 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // while the returned iterator is live. The keys returned by this 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // iterator are internal keys encoded by AppendInternalKey in the 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // db/format.{h,cc} module. 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* NewIterator(); 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Add an entry into memtable that maps key to value at the 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // specified sequence number and with the specified type. 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Typically value will be empty if type==kTypeDeletion. 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Add(SequenceNumber seq, ValueType type, 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& key, 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& value); 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 608cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // If memtable contains a value for key, store it in *value and return true. 618cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // If memtable contains a deletion for key, store a NotFound() error 628cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // in *status and return true. 638cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Else, return false. 648cd4ab8303620197cf24282ae8639060efbb326egabor@google.com bool Get(const LookupKey& key, std::string* value, Status* s); 658cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 67a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org ~MemTable(); // Private since only Unref() should be used to delete it 68a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org struct KeyComparator { 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const InternalKeyComparator comparator; 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { } 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int operator()(const char* a, const char* b) const; 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org }; 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org friend class MemTableIterator; 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org friend class MemTableBackwardIterator; 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org typedef SkipList<const char*, KeyComparator> Table; 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KeyComparator comparator_; 80a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int refs_; 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Arena arena_; 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Table table_; 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // No copying allowed 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MemTable(const MemTable&); 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void operator=(const MemTable&); 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 8945b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#endif // STORAGE_LEVELDB_DB_MEMTABLE_H_ 92