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#include "table/merger.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 7fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/comparator.h" 8fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/iterator.h" 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/iterator_wrapper.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace { 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass MergingIterator : public Iterator { 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MergingIterator(const Comparator* comparator, Iterator** children, int n) 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : comparator_(comparator), 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org children_(new IteratorWrapper[n]), 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org n_(n), 2084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org current_(NULL), 2184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org direction_(kForward) { 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < n; i++) { 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org children_[i].Set(children[i]); 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual ~MergingIterator() { 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete[] children_; 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual bool Valid() const { 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return (current_ != NULL); 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void SeekToFirst() { 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < n_; i++) { 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org children_[i].SeekToFirst(); 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FindSmallest(); 4084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org direction_ = kForward; 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void SeekToLast() { 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < n_; i++) { 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org children_[i].SeekToLast(); 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FindLargest(); 4884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org direction_ = kReverse; 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Seek(const Slice& target) { 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < n_; i++) { 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org children_[i].Seek(target); 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FindSmallest(); 5684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org direction_ = kForward; 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Next() { 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 6184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 6284744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // Ensure that all children are positioned after key(). 6384744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // If we are moving in the forward direction, it is already 6484744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // true for all of the non-current_ children since current_ is 6584744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // the smallest child and key() == current_->key(). Otherwise, 6684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // we explicitly position the non-current_ children. 6784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org if (direction_ != kForward) { 6884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org for (int i = 0; i < n_; i++) { 6984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org IteratorWrapper* child = &children_[i]; 7084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org if (child != current_) { 7184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org child->Seek(key()); 7284744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org if (child->Valid() && 7384744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org comparator_->Compare(key(), child->key()) == 0) { 7484744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org child->Next(); 7584744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 7684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 7784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 7884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org direction_ = kForward; 7984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 8084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_->Next(); 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FindSmallest(); 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Prev() { 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 8784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 8884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // Ensure that all children are positioned before key(). 8984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // If we are moving in the reverse direction, it is already 9084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // true for all of the non-current_ children since current_ is 9184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // the largest child and key() == current_->key(). Otherwise, 9284744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // we explicitly position the non-current_ children. 9384744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org if (direction_ != kReverse) { 9484744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org for (int i = 0; i < n_; i++) { 9584744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org IteratorWrapper* child = &children_[i]; 9684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org if (child != current_) { 9784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org child->Seek(key()); 9884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org if (child->Valid()) { 9984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // Child is at first entry >= key(). Step back one to be < key() 10084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org child->Prev(); 10184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } else { 10284744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // Child has no entries >= key(). Position at last entry. 10384744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org child->SeekToLast(); 10484744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 10584744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 10684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 10784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org direction_ = kReverse; 10884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 10984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 110179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_->Prev(); 111179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FindLargest(); 112179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 113179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 114179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Slice key() const { 115179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 116179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return current_->key(); 117179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 118179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 119179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Slice value() const { 120179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 121179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return current_->value(); 122179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 123179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 124179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status status() const { 125179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status status; 126179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < n_; i++) { 127179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org status = children_[i].status(); 128179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!status.ok()) { 129179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 130179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 131179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 132179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return status; 133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 134179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 135179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void FindSmallest(); 137179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void FindLargest(); 138179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 139179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // We might want to use a heap in case there are lots of children. 140179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // For now we use a simple array since we expect a very small number 141179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // of children in leveldb. 142179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Comparator* comparator_; 143179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IteratorWrapper* children_; 144179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int n_; 145179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IteratorWrapper* current_; 14684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 14784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // Which direction is the iterator moving? 14884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org enum Direction { 14984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org kForward, 15084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org kReverse 15184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org }; 15284744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org Direction direction_; 153179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 154179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 155179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid MergingIterator::FindSmallest() { 156179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IteratorWrapper* smallest = NULL; 157179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < n_; i++) { 158179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IteratorWrapper* child = &children_[i]; 159179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (child->Valid()) { 160179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (smallest == NULL) { 161179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org smallest = child; 162179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else if (comparator_->Compare(child->key(), smallest->key()) < 0) { 163179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org smallest = child; 164179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 165179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 166179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 167179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_ = smallest; 168179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 169179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 170179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid MergingIterator::FindLargest() { 171179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IteratorWrapper* largest = NULL; 172179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = n_-1; i >= 0; i--) { 173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IteratorWrapper* child = &children_[i]; 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (child->Valid()) { 175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (largest == NULL) { 176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org largest = child; 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else if (comparator_->Compare(child->key(), largest->key()) > 0) { 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org largest = child; 179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 182179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current_ = largest; 183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 18445b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace 185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgIterator* NewMergingIterator(const Comparator* cmp, Iterator** list, int n) { 187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(n >= 0); 188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (n == 0) { 189179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return NewEmptyIterator(); 190179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else if (n == 1) { 191179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return list[0]; 192179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return new MergingIterator(cmp, list, n); 194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 19745b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 198