SERVER-13084: move iterator into record layer

26 files changed, 315 insertions, 224 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 873ea8e2d6a..cf064668f16 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -611,7 +611,6 @@ serverOnlyFiles = [ "db/curop.cpp",
                     "db/structure/collection_compact.cpp",
                     "db/catalog/collection_cursor_cache.cpp",
                     "db/catalog/collection_info_cache.cpp",
-                    "db/structure/collection_iterator.cpp",
                     "db/catalog/database_holder.cpp",
                     "db/background.cpp",
                     "db/pdfile.cpp",
@@ -623,7 +622,9 @@ serverOnlyFiles = [ "db/curop.cpp",
                     "db/structure/record_store.cpp",
                     "db/structure/record_store_v1_base.cpp",
                     "db/structure/record_store_v1_capped.cpp",
+                    "db/structure/record_store_v1_capped_iterator.cpp",
                     "db/structure/record_store_v1_simple.cpp",
+                    "db/structure/record_store_v1_simple_iterator.cpp",
                     "db/extsort.cpp",
                     "db/index_builder.cpp",
                     "db/index_rebuilder.cpp",
diff --git a/src/mongo/db/catalog/collection.cpp b/src/mongo/db/catalog/collection.cpp
index bbcb0827a80..3cc34a1c2e2 100644
--- a/src/mongo/db/catalog/collection.cpp
+++ b/src/mongo/db/catalog/collection.cpp
@@ -44,7 +44,6 @@
 #include "mongo/db/repl/rs.h"
 #include "mongo/db/storage/extent.h"
 #include "mongo/db/storage/extent_manager.h"
-#include "mongo/db/structure/collection_iterator.h"
 
 #include "mongo/db/auth/user_document_parser.h" // XXX-ANDY
 
@@ -130,16 +129,14 @@ namespace mongo {
         return true;
     }
 
-    CollectionIterator* Collection::getIterator( const DiskLoc& start, bool tailable,
+    RecordIterator* Collection::getIterator( const DiskLoc& start, bool tailable,
                                                      const CollectionScanParams::Direction& dir) const {
-        verify( ok() );
-        if ( _details->isCapped() )
-            return new CappedIterator( this, start, tailable, dir );
-        return new FlatIterator( this, start, dir );
+        invariant( ok() );
+        return _recordStore->getIterator( start, tailable, dir );
     }
 
     int64_t Collection::countTableScan( const MatchExpression* expression ) {
-        scoped_ptr<CollectionIterator> iterator( getIterator( DiskLoc(),
+        scoped_ptr<RecordIterator> iterator( getIterator( DiskLoc(),
                                                               false,
                                                               CollectionScanParams::FORWARD ) );
         int64_t count = 0;
diff --git a/src/mongo/db/catalog/collection.h b/src/mongo/db/catalog/collection.h
index ac7ff418455..be92af2cdb3 100644
--- a/src/mongo/db/catalog/collection.h
+++ b/src/mongo/db/catalog/collection.h
@@ -50,7 +50,7 @@ namespace mongo {
     class IndexCatalog;
     class MultiIndexBlock;
 
-    class CollectionIterator;
+    class RecordIterator;
     class FlatIterator;
     class CappedIterator;
 
@@ -139,8 +139,8 @@ namespace mongo {
          * canonical to get all would be
          * getIterator( DiskLoc(), false, CollectionScanParams::FORWARD )
          */
-        CollectionIterator* getIterator( const DiskLoc& start, bool tailable,
-                                         const CollectionScanParams::Direction& dir) const;
+        RecordIterator* getIterator( const DiskLoc& start, bool tailable,
+                                     const CollectionScanParams::Direction& dir) const;
 
 
         /**
diff --git a/src/mongo/db/commands/rename_collection.cpp b/src/mongo/db/commands/rename_collection.cpp
index bac52e7e579..30b0e59d58a 100644
--- a/src/mongo/db/commands/rename_collection.cpp
+++ b/src/mongo/db/commands/rename_collection.cpp
@@ -39,7 +39,6 @@
 #include "mongo/db/instance.h"
 #include "mongo/db/namespace_string.h"
 #include "mongo/db/ops/insert.h"
-#include "mongo/db/structure/collection_iterator.h"
 
 namespace mongo {
 
@@ -231,7 +230,7 @@ namespace mongo {
 
             // Copy over all the data from source collection to target collection.
             bool insertSuccessful = true;
-            boost::scoped_ptr<CollectionIterator> sourceIt;
+            boost::scoped_ptr<RecordIterator> sourceIt;
 
             {
                 Client::Context srcCtx( source );
diff --git a/src/mongo/db/exec/collection_scan.cpp b/src/mongo/db/exec/collection_scan.cpp
index 1a29d8b76fb..2e73d9b49f1 100644
--- a/src/mongo/db/exec/collection_scan.cpp
+++ b/src/mongo/db/exec/collection_scan.cpp
@@ -33,11 +33,9 @@
 #include "mongo/db/exec/filter.h"
 #include "mongo/db/exec/working_set.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/util/fail_point_service.h"
 
 #include "mongo/db/client.h" // XXX-ERH
-#include "mongo/db/pdfile.h" // XXX-ERH/ACM
 
 namespace mongo {
 
@@ -168,7 +166,7 @@ namespace mongo {
 
         // If we're here, 'dl' is being deleted.
 
-        // Deletions can harm the underlying CollectionIterator so we must pass them down.
+        // Deletions can harm the underlying RecordIterator so we must pass them down.
         if (NULL != _iter) {
             _iter->invalidate(dl);
         }
diff --git a/src/mongo/db/exec/collection_scan.h b/src/mongo/db/exec/collection_scan.h
index fbe1d935c0b..969c23a5b9f 100644
--- a/src/mongo/db/exec/collection_scan.h
+++ b/src/mongo/db/exec/collection_scan.h
@@ -32,10 +32,10 @@
 #include "mongo/db/exec/collection_scan_common.h"
 #include "mongo/db/exec/plan_stage.h"
 #include "mongo/db/matcher/expression.h"
-#include "mongo/db/structure/collection_iterator.h"
 
 namespace mongo {
 
+    class RecordIterator;
     class WorkingSet;
 
     /**
@@ -71,7 +71,7 @@ namespace mongo {
         // The filter is not owned by us.
         const MatchExpression* _filter;
 
-        scoped_ptr<CollectionIterator> _iter;
+        scoped_ptr<RecordIterator> _iter;
 
         CollectionScanParams _params;
 
diff --git a/src/mongo/db/repair_database.cpp b/src/mongo/db/repair_database.cpp
index 098184c3c83..b28859b5237 100644
--- a/src/mongo/db/repair_database.cpp
+++ b/src/mongo/db/repair_database.cpp
@@ -41,7 +41,6 @@
 #include "mongo/db/cloner.h"
 #include "mongo/db/index/index_descriptor.h"
 #include "mongo/db/kill_current_op.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/util/file.h"
 #include "mongo/util/file_allocator.h"
 
@@ -328,7 +327,7 @@ namespace mongo {
                 Client::Context ctx( ns );
                 Collection* coll = originalDatabase->getCollection( ns );
                 if ( coll ) {
-                    scoped_ptr<CollectionIterator> it( coll->getIterator( DiskLoc(),
+                    scoped_ptr<RecordIterator> it( coll->getIterator( DiskLoc(),
                                                                           false,
                                                                           CollectionScanParams::FORWARD ) );
                     while ( !it->isEOF() ) {
@@ -394,7 +393,7 @@ namespace mongo {
 
                 }
 
-                scoped_ptr<CollectionIterator> iterator( originalCollection->getIterator( DiskLoc(),
+                scoped_ptr<RecordIterator> iterator( originalCollection->getIterator( DiskLoc(),
                                                                                           false,
                                                                                           CollectionScanParams::FORWARD ) );
                 while ( !iterator->isEOF() ) {
diff --git a/src/mongo/db/structure/collection_compact.cpp b/src/mongo/db/structure/collection_compact.cpp
index 22d00a199e4..a59e232cfb4 100644
--- a/src/mongo/db/structure/collection_compact.cpp
+++ b/src/mongo/db/structure/collection_compact.cpp
@@ -43,7 +43,6 @@
 #include "mongo/db/structure/catalog/namespace_details.h"
 #include "mongo/db/storage/extent.h"
 #include "mongo/db/storage/extent_manager.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/util/touch_pages.h"
 
 namespace mongo {
diff --git a/src/mongo/db/structure/record_store.h b/src/mongo/db/structure/record_store.h
index 921b61f082a..934eddf8551 100644
--- a/src/mongo/db/structure/record_store.h
+++ b/src/mongo/db/structure/record_store.h
@@ -32,6 +32,7 @@
 
 #include "mongo/base/owned_pointer_vector.h"
 #include "mongo/db/diskloc.h"
+#include "mongo/db/exec/collection_scan_common.h"
 
 namespace mongo {
 
@@ -42,6 +43,36 @@ namespace mongo {
     class NamespaceDetails;
     class Record;
 
+    /**
+     * A RecordIterator provides an interface for walking over a RecordStore.
+     * The details of navigating the collection's structure are below this interface.
+     */
+    class RecordIterator {
+    public:
+        virtual ~RecordIterator() { }
+
+        // True if getNext will produce no more data, false otherwise.
+        virtual bool isEOF() = 0;
+
+        // Return the DiskLoc that the iterator points at.  Returns DiskLoc() if isEOF.
+        virtual DiskLoc curr() = 0;
+
+        // Return the DiskLoc that the iterator points at and move the iterator to the next item
+        // from the collection.  Returns DiskLoc() if isEOF.
+        virtual DiskLoc getNext() = 0;
+
+        // Can only be called after prepareToYield and before recoverFromYield.
+        virtual void invalidate(const DiskLoc& dl) = 0;
+
+        // Save any state required to resume operation (without crashing) after DiskLoc deletion or
+        // a collection drop.
+        virtual void prepareToYield() = 0;
+
+        // Returns true if collection still exists, false otherwise.
+        virtual bool recoverFromYield() = 0;
+    };
+
+
     class RecordStore {
         MONGO_DISALLOW_COPYING(RecordStore);
     public:
@@ -58,8 +89,17 @@ namespace mongo {
 
         virtual StatusWith<DiskLoc> insertRecord( const DocWriter* doc, int quotaMax ) = 0;
 
+        /**
+         * returned iterator owned by caller
+         * canonical to get all would be
+         * getIterator( DiskLoc(), false, CollectionScanParams::FORWARD )
+         */
+        virtual RecordIterator* getIterator( const DiskLoc& start, bool tailable,
+                                             const CollectionScanParams::Direction& dir) const = 0;
+
         // higher level
 
+
         /**
          * removes all Records
          */
diff --git a/src/mongo/db/structure/record_store_v1_base.h b/src/mongo/db/structure/record_store_v1_base.h
index d1d7d02f1a3..94ddcda2919 100644
--- a/src/mongo/db/structure/record_store_v1_base.h
+++ b/src/mongo/db/structure/record_store_v1_base.h
@@ -35,6 +35,7 @@
 
 namespace mongo {
 
+    class CappedRecordStoreV1Iterator;
     class DocWriter;
     class ExtentManager;
     class NamespaceDetails;
@@ -61,6 +62,8 @@ namespace mongo {
 
         // TODO: another sad one
         virtual const DeletedRecord* deletedRecordFor( const DiskLoc& loc ) const;
+
+        const NamespaceDetails* details() const { return _details; }
     protected:
         virtual StatusWith<DiskLoc> allocRecord( int lengthWithHeaders, int quotaMax ) = 0;
 
@@ -78,6 +81,8 @@ namespace mongo {
         NamespaceDetails* _details;
         ExtentManager* _extentManager;
         bool _isSystemIndexes;
+
+        friend class CappedRecordStoreV1Iterator;
     };
 
 }
diff --git a/src/mongo/db/structure/record_store_v1_capped.cpp b/src/mongo/db/structure/record_store_v1_capped.cpp
index 19f74802ca6..df4cd476560 100644
--- a/src/mongo/db/structure/record_store_v1_capped.cpp
+++ b/src/mongo/db/structure/record_store_v1_capped.cpp
@@ -36,6 +36,7 @@
 #include "mongo/db/storage/extent_manager.h"
 #include "mongo/db/storage/record.h"
 #include "mongo/db/structure/catalog/namespace_details.h"
+#include "mongo/db/structure/record_store_v1_capped_iterator.h"
 
 /*
  capped collection layout
@@ -572,4 +573,9 @@ namespace mongo {
         }
     }
 
+    RecordIterator* CappedRecordStoreV1::getIterator( const DiskLoc& start, bool tailable,
+                                                      const CollectionScanParams::Direction& dir) const {
+        return new CappedRecordStoreV1Iterator( this, start, tailable, dir );
+    }
+
 }
diff --git a/src/mongo/db/structure/record_store_v1_capped.h b/src/mongo/db/structure/record_store_v1_capped.h
index 22750c522e3..961ed2aa584 100644
--- a/src/mongo/db/structure/record_store_v1_capped.h
+++ b/src/mongo/db/structure/record_store_v1_capped.h
@@ -60,6 +60,9 @@ namespace mongo {
          */
         void temp_cappedTruncateAfter( DiskLoc end, bool inclusive );
 
+        virtual RecordIterator* getIterator( const DiskLoc& start, bool tailable,
+                                             const CollectionScanParams::Direction& dir) const;
+
     protected:
         virtual StatusWith<DiskLoc> allocRecord( int lengthWithHeaders, int quotaMax );
 
diff --git a/src/mongo/db/structure/collection_iterator.cpp b/src/mongo/db/structure/record_store_v1_capped_iterator.cpp
index 18373bfade4..a18356c6b6d 100644
--- a/src/mongo/db/structure/collection_iterator.cpp
+++ b/src/mongo/db/structure/record_store_v1_capped_iterator.cpp
@@ -26,124 +26,30 @@
  *    it in the license file.
  */
 
-#include "mongo/db/structure/collection_iterator.h"
+#include "mongo/db/structure/record_store_v1_capped_iterator.h"
 
-#include "mongo/db/structure/catalog/namespace_details.h"
+#include "mongo/db/catalog/collection.h"
 #include "mongo/db/storage/extent.h"
 #include "mongo/db/storage/extent_manager.h"
-#include "mongo/db/catalog/collection.h"
+#include "mongo/db/structure/catalog/namespace_details.h"
+#include "mongo/db/structure/record_store_v1_capped.h"
 
 namespace mongo {
 
-    //
-    // Regular / non-capped collection traversal
-    //
-
-    FlatIterator::FlatIterator(const Collection* collection,
-                               const DiskLoc& start,
-                               const CollectionScanParams::Direction& dir)
-        : _curr(start), _collection(collection), _direction(dir) {
-
-        if (_curr.isNull()) {
-
-            const ExtentManager* em = _collection->getExtentManager();
-
-            if ( _collection->_details->firstExtent().isNull() ) {
-                // nothing in the collection
-                verify( _collection->_details->lastExtent().isNull() );
-            }
-            else if (CollectionScanParams::FORWARD == _direction) {
-
-                // Find a non-empty extent and start with the first record in it.
-                Extent* e = em->getExtent( _collection->_details->firstExtent() );
-
-                while (e->firstRecord.isNull() && !e->xnext.isNull()) {
-                    e = em->getNextExtent( e );
-                }
-
-                // _curr may be set to DiskLoc() here if e->lastRecord isNull but there is no
-                // valid e->xnext
-                _curr = e->firstRecord;
-            }
-            else {
-                // Walk backwards, skipping empty extents, and use the last record in the first
-                // non-empty extent we see.
-                Extent* e = em->getExtent( _collection->_details->lastExtent() );
-
-                // TODO ELABORATE
-                // Does one of e->lastRecord.isNull(), e.firstRecord.isNull() imply the other?
-                while (e->lastRecord.isNull() && !e->xprev.isNull()) {
-                    e = em->getPrevExtent( e );
-                }
-
-                // _curr may be set to DiskLoc() here if e->lastRecord isNull but there is no
-                // valid e->xprev
-                _curr = e->lastRecord;
-            }
-        }
-    }
-
-    bool FlatIterator::isEOF() {
-        return _curr.isNull();
-    }
-
-    DiskLoc FlatIterator::curr() { return _curr; }
-
-    DiskLoc FlatIterator::getNext() {
-        DiskLoc ret = _curr;
-
-        // Move to the next thing.
-        if (!isEOF()) {
-            if (CollectionScanParams::FORWARD == _direction) {
-                _curr = _collection->getExtentManager()->getNextRecord( _curr );
-            }
-            else {
-                _curr = _collection->getExtentManager()->getPrevRecord( _curr );
-            }
-        }
-
-        return ret;
-    }
-
-    void FlatIterator::invalidate(const DiskLoc& dl) {
-        verify( _collection->ok() );
-
-        // Just move past the thing being deleted.
-        if (dl == _curr) {
-            // We don't care about the return of getNext so much as the side effect of moving _curr
-            // to the 'next' thing.
-            getNext();
-        }
-    }
-
-    void FlatIterator::prepareToYield() {
-    }
-
-    bool FlatIterator::recoverFromYield() {
-        // if the collection is dropped, then the cursor should be destroyed
-        // this check is just a sanity check that the Collection instance we're about to use
-        // has need been destroyed
-        verify( _collection->ok() );
-
-        return true;
-    }
 
     //
     // Capped collection traversal
     //
-
-    CappedIterator::CappedIterator(const Collection* collection,
-                                   const DiskLoc& start, bool tailable,
-                                   const CollectionScanParams::Direction& dir)
+    CappedRecordStoreV1Iterator::CappedRecordStoreV1Iterator( const CappedRecordStoreV1* collection,
+                                                              const DiskLoc& start, bool tailable,
+                                                              const CollectionScanParams::Direction& dir)
         : _collection(collection), _curr(start), _tailable(tailable),
           _direction(dir), _killedByInvalidate(false) {
 
-        verify( collection->ok() );
-
         if (_curr.isNull()) {
 
-            const NamespaceDetails* nsd = _collection->_details;
-            const ExtentManager* em = _collection->getExtentManager();
+            const NamespaceDetails* nsd = _collection->details();
+            const ExtentManager* em = _collection->_extentManager;
 
             // If a start position isn't specified, we fill one out from the start of the
             // collection.
@@ -177,15 +83,15 @@ namespace mongo {
         }
     }
 
-    bool CappedIterator::isEOF() { return _curr.isNull(); }
+    bool CappedRecordStoreV1Iterator::isEOF() { return _curr.isNull(); }
 
-    DiskLoc CappedIterator::curr() { return _curr; }
+    DiskLoc CappedRecordStoreV1Iterator::curr() { return _curr; }
 
-    DiskLoc CappedIterator::getNext() {
+    DiskLoc CappedRecordStoreV1Iterator::getNext() {
         DiskLoc ret = _curr;
 
-        const NamespaceDetails* nsd = _collection->_details;
-        const ExtentManager* em = _collection->getExtentManager();
+        const NamespaceDetails* nsd = _collection->details();
+        const ExtentManager* em = _collection->_extentManager;
 
         // Move to the next thing.
         if (!isEOF()) {
@@ -208,7 +114,7 @@ namespace mongo {
         return ret;
     }
 
-    void CappedIterator::invalidate(const DiskLoc& dl) {
+    void CappedRecordStoreV1Iterator::invalidate(const DiskLoc& dl) {
         if ((_tailable && _curr.isNull() && dl == _prev) || (dl == _curr)) {
             // In the _tailable case, we're about to kill the DiskLoc that we're tailing.  Nothing
             // that we can possibly do to survive that.
@@ -223,22 +129,20 @@ namespace mongo {
         }
     }
 
-    void CappedIterator::prepareToYield() {
+    void CappedRecordStoreV1Iterator::prepareToYield() {
     }
 
-    bool CappedIterator::recoverFromYield() {
+    bool CappedRecordStoreV1Iterator::recoverFromYield() {
         // If invalidate invalidated the DiskLoc we relied on, give up now.
         if (_killedByInvalidate) {
             _collection = NULL;
             return false;
         }
 
-        verify( _collection->ok() );
-
         return true;
     }
 
-    DiskLoc CappedIterator::getNextCapped(const NamespaceDetails* nsd, const ExtentManager* em,
+    DiskLoc CappedRecordStoreV1Iterator::getNextCapped(const NamespaceDetails* nsd, const ExtentManager* em,
                                           const DiskLoc& dl,
                                           CollectionScanParams::Direction direction ) {
         verify(!dl.isNull());
@@ -297,7 +201,7 @@ namespace mongo {
         }
     }
 
-    DiskLoc CappedIterator::nextLoop(const NamespaceDetails* nsd, const ExtentManager* em,
+    DiskLoc CappedRecordStoreV1Iterator::nextLoop(const NamespaceDetails* nsd, const ExtentManager* em,
                                      const DiskLoc& prev) {
         // TODO ELABORATE
         verify(nsd->capLooped());
@@ -306,7 +210,7 @@ namespace mongo {
         return nsd->firstRecord();
     }
 
-    DiskLoc CappedIterator::prevLoop(const NamespaceDetails* nsd, const ExtentManager* em,
+    DiskLoc CappedRecordStoreV1Iterator::prevLoop(const NamespaceDetails* nsd, const ExtentManager* em,
                                      const DiskLoc& curr) {
         // TODO ELABORATE
         verify(nsd->capLooped());
diff --git a/src/mongo/db/structure/collection_iterator.h b/src/mongo/db/structure/record_store_v1_capped_iterator.h
index fdd40a6cc18..7a2b9153b17 100644
--- a/src/mongo/db/structure/collection_iterator.h
+++ b/src/mongo/db/structure/record_store_v1_capped_iterator.h
@@ -28,72 +28,11 @@
 
 #pragma once
 
-#include "mongo/db/exec/collection_scan_common.h"
+#include "mongo/db/structure/record_store.h"
 
 namespace mongo {
 
-    class Collection;
-    class DiskLoc;
-    class ExtentManager;
-    class NamespaceDetails;
-
-    /**
-     * A CollectionIterator provides an interface for walking over a collection.
-     * The details of navigating the collection's structure are below this interface.
-     */
-    class CollectionIterator {
-    public:
-        virtual ~CollectionIterator() { }
-
-        // True if getNext will produce no more data, false otherwise.
-        virtual bool isEOF() = 0;
-
-        // Return the DiskLoc that the iterator points at.  Returns DiskLoc() if isEOF.
-        virtual DiskLoc curr() = 0;
-
-        // Return the DiskLoc that the iterator points at and move the iterator to the next item
-        // from the collection.  Returns DiskLoc() if isEOF.
-        virtual DiskLoc getNext() = 0;
-
-        // Can only be called after prepareToYield and before recoverFromYield.
-        virtual void invalidate(const DiskLoc& dl) = 0;
-
-        // Save any state required to resume operation (without crashing) after DiskLoc deletion or
-        // a collection drop.
-        virtual void prepareToYield() = 0;
-
-        // Returns true if collection still exists, false otherwise.
-        virtual bool recoverFromYield() = 0;
-    };
-
-    /**
-     * This class iterates over a non-capped collection identified by 'ns'.
-     * The collection must exist when the constructor is called.
-     *
-     * If start is not DiskLoc(), the iteration begins at that DiskLoc.
-     */
-    class FlatIterator : public CollectionIterator {
-    public:
-        FlatIterator(const Collection* collection, const DiskLoc& start,
-                     const CollectionScanParams::Direction& dir);
-        virtual ~FlatIterator() { }
-
-        virtual bool isEOF();
-        virtual DiskLoc getNext();
-        virtual DiskLoc curr();
-
-        virtual void invalidate(const DiskLoc& dl);
-        virtual void prepareToYield();
-        virtual bool recoverFromYield();
-
-    private:
-        // The result returned on the next call to getNext().
-        DiskLoc _curr;
-
-        const Collection* _collection;
-
-        CollectionScanParams::Direction _direction;
-    };
+    class CappedRecordStoreV1;
 
     /**
      * This class iterates over a capped collection identified by 'ns'.
@@ -104,11 +43,13 @@ namespace mongo {
      * If tailable is true, getNext() can be called after isEOF.  It will use the last valid
      * returned DiskLoc and try to find the next record from that.
      */
-    class CappedIterator : public CollectionIterator {
+    class CappedRecordStoreV1Iterator : public RecordIterator {
     public:
-        CappedIterator(const Collection* collection, const DiskLoc& start, bool tailable,
-                       const CollectionScanParams::Direction& dir);
-        virtual ~CappedIterator() { }
+        CappedRecordStoreV1Iterator( const CappedRecordStoreV1* collection,
+                                     const DiskLoc& start,
+                                     bool tailable,
+                                     const CollectionScanParams::Direction& dir );
+        virtual ~CappedRecordStoreV1Iterator() { }
 
         // If this is a tailable cursor, isEOF could change its mind after a call to getNext().
         virtual bool isEOF();
@@ -131,7 +72,7 @@ namespace mongo {
                                 const DiskLoc& prev);
 
         // The collection we're iterating over.
-        const Collection* _collection;
+        const CappedRecordStoreV1* _collection;
 
         // The result returned on the next call to getNext().
         DiskLoc _curr;
diff --git a/src/mongo/db/structure/record_store_v1_simple.cpp b/src/mongo/db/structure/record_store_v1_simple.cpp
index 1a7f1a95854..c094ef46b60 100644
--- a/src/mongo/db/structure/record_store_v1_simple.cpp
+++ b/src/mongo/db/structure/record_store_v1_simple.cpp
@@ -38,6 +38,7 @@
 #include "mongo/db/storage/extent_manager.h"
 #include "mongo/db/storage/record.h"
 #include "mongo/db/structure/catalog/namespace_details.h"
+#include "mongo/db/structure/record_store_v1_simple_iterator.h"
 #include "mongo/util/mmap.h"
 
 namespace mongo {
@@ -260,4 +261,10 @@ namespace mongo {
         getDur().writingDiskLoc(list) = dloc;
         d->nextDeleted() = oldHead;
     }
+
+    RecordIterator* SimpleRecordStoreV1::getIterator( const DiskLoc& start, bool tailable,
+                                                      const CollectionScanParams::Direction& dir) const {
+        return new SimpleRecordStoreV1Iterator( this, start, dir );
+    }
+
 }
diff --git a/src/mongo/db/structure/record_store_v1_simple.h b/src/mongo/db/structure/record_store_v1_simple.h
index b9be4f9ee44..1af6f002767 100644
--- a/src/mongo/db/structure/record_store_v1_simple.h
+++ b/src/mongo/db/structure/record_store_v1_simple.h
@@ -35,6 +35,8 @@
 
 namespace mongo {
 
+    class SimpleRecordStoreV1Iterator;
+
     // used by index and original collections
     class SimpleRecordStoreV1 : public RecordStoreV1Base {
     public:
@@ -45,6 +47,9 @@ namespace mongo {
 
         virtual ~SimpleRecordStoreV1();
 
+        virtual RecordIterator* getIterator( const DiskLoc& start, bool tailable,
+                                             const CollectionScanParams::Direction& dir) const;
+
         virtual Status truncate();
     protected:
         virtual StatusWith<DiskLoc> allocRecord( int lengthWithHeaders, int quotaMax );
@@ -54,6 +59,8 @@ namespace mongo {
         DiskLoc _allocFromExistingExtents( int lengthWithHeaders );
 
         bool _normalCollection;
+
+        friend class SimpleRecordStoreV1Iterator;
     };
 
 }
diff --git a/src/mongo/db/structure/record_store_v1_simple_iterator.cpp b/src/mongo/db/structure/record_store_v1_simple_iterator.cpp
new file mode 100644
index 00000000000..c764c10e609
--- /dev/null
+++ b/src/mongo/db/structure/record_store_v1_simple_iterator.cpp
@@ -0,0 +1,126 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/structure/record_store_v1_simple_iterator.h"
+
+#include "mongo/db/catalog/collection.h"
+#include "mongo/db/storage/extent.h"
+#include "mongo/db/storage/extent_manager.h"
+#include "mongo/db/structure/catalog/namespace_details.h"
+#include "mongo/db/structure/record_store_v1_simple.h"
+
+namespace mongo {
+
+    //
+    // Regular / non-capped collection traversal
+    //
+
+    SimpleRecordStoreV1Iterator::SimpleRecordStoreV1Iterator(const SimpleRecordStoreV1* collection,
+                                                             const DiskLoc& start,
+                                                             const CollectionScanParams::Direction& dir)
+        : _curr(start), _collection(collection), _direction(dir) {
+
+        if (_curr.isNull()) {
+
+            const ExtentManager* em = _collection->_extentManager;
+
+            if ( _collection->details()->firstExtent().isNull() ) {
+                // nothing in the collection
+                verify( _collection->details()->lastExtent().isNull() );
+            }
+            else if (CollectionScanParams::FORWARD == _direction) {
+
+                // Find a non-empty extent and start with the first record in it.
+                Extent* e = em->getExtent( _collection->details()->firstExtent() );
+
+                while (e->firstRecord.isNull() && !e->xnext.isNull()) {
+                    e = em->getNextExtent( e );
+                }
+
+                // _curr may be set to DiskLoc() here if e->lastRecord isNull but there is no
+                // valid e->xnext
+                _curr = e->firstRecord;
+            }
+            else {
+                // Walk backwards, skipping empty extents, and use the last record in the first
+                // non-empty extent we see.
+                Extent* e = em->getExtent( _collection->details()->lastExtent() );
+
+                // TODO ELABORATE
+                // Does one of e->lastRecord.isNull(), e.firstRecord.isNull() imply the other?
+                while (e->lastRecord.isNull() && !e->xprev.isNull()) {
+                    e = em->getPrevExtent( e );
+                }
+
+                // _curr may be set to DiskLoc() here if e->lastRecord isNull but there is no
+                // valid e->xprev
+                _curr = e->lastRecord;
+            }
+        }
+    }
+
+    bool SimpleRecordStoreV1Iterator::isEOF() {
+        return _curr.isNull();
+    }
+
+    DiskLoc SimpleRecordStoreV1Iterator::curr() { return _curr; }
+
+    DiskLoc SimpleRecordStoreV1Iterator::getNext() {
+        DiskLoc ret = _curr;
+
+        // Move to the next thing.
+        if (!isEOF()) {
+            if (CollectionScanParams::FORWARD == _direction) {
+                _curr = _collection->_extentManager->getNextRecord( _curr );
+            }
+            else {
+                _curr = _collection->_extentManager->getPrevRecord( _curr );
+            }
+        }
+
+        return ret;
+    }
+
+    void SimpleRecordStoreV1Iterator::invalidate(const DiskLoc& dl) {
+        // Just move past the thing being deleted.
+        if (dl == _curr) {
+            // We don't care about the return of getNext so much as the side effect of moving _curr
+            // to the 'next' thing.
+            getNext();
+        }
+    }
+
+    void SimpleRecordStoreV1Iterator::prepareToYield() {
+    }
+
+    bool SimpleRecordStoreV1Iterator::recoverFromYield() {
+        // if the collection is dropped, then the cursor should be destroyed
+        return true;
+    }
+
+}
diff --git a/src/mongo/db/structure/record_store_v1_simple_iterator.h b/src/mongo/db/structure/record_store_v1_simple_iterator.h
new file mode 100644
index 00000000000..0ef10667a23
--- /dev/null
+++ b/src/mongo/db/structure/record_store_v1_simple_iterator.h
@@ -0,0 +1,67 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/db/structure/record_store.h"
+
+namespace mongo {
+
+    class SimpleRecordStoreV1;
+
+    /**
+     * This class iterates over a non-capped collection identified by 'ns'.
+     * The collection must exist when the constructor is called.
+     *
+     * If start is not DiskLoc(), the iteration begins at that DiskLoc.
+     */
+    class SimpleRecordStoreV1Iterator : public RecordIterator {
+    public:
+        SimpleRecordStoreV1Iterator( const SimpleRecordStoreV1* records,
+                                     const DiskLoc& start,
+                                     const CollectionScanParams::Direction& dir );
+        virtual ~SimpleRecordStoreV1Iterator() { }
+
+        virtual bool isEOF();
+        virtual DiskLoc getNext();
+        virtual DiskLoc curr();
+
+        virtual void invalidate(const DiskLoc& dl);
+        virtual void prepareToYield();
+        virtual bool recoverFromYield();
+
+    private:
+        // The result returned on the next call to getNext().
+        DiskLoc _curr;
+
+        const SimpleRecordStoreV1* _collection;
+
+        CollectionScanParams::Direction _direction;
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/dbtests/indexupdatetests.cpp b/src/mongo/dbtests/indexupdatetests.cpp
index c46ae9218cf..2160975eb70 100644
--- a/src/mongo/dbtests/indexupdatetests.cpp
+++ b/src/mongo/dbtests/indexupdatetests.cpp
@@ -36,7 +36,6 @@
 #include "mongo/db/kill_current_op.h"
 #include "mongo/db/sort_phase_one.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/platform/cstdint.h"
 
 #include "mongo/dbtests/dbtests.h"
diff --git a/src/mongo/dbtests/query_stage_and.cpp b/src/mongo/dbtests/query_stage_and.cpp
index b6f7cd8b986..ec805f81972 100644
--- a/src/mongo/dbtests/query_stage_and.cpp
+++ b/src/mongo/dbtests/query_stage_and.cpp
@@ -44,7 +44,6 @@
 #include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/dbtests/dbtests.h"
 #include "mongo/util/mongoutils/str.h"
 
@@ -71,7 +70,7 @@ namespace QueryStageAnd {
         }
 
         void getLocs(set<DiskLoc>* out, Collection* coll) {
-            CollectionIterator* it = coll->getIterator(DiskLoc(), false,
+            RecordIterator* it = coll->getIterator(DiskLoc(), false,
                                                        CollectionScanParams::FORWARD);
             while (!it->isEOF()) {
                 DiskLoc nextLoc = it->getNext();
diff --git a/src/mongo/dbtests/query_stage_count.cpp b/src/mongo/dbtests/query_stage_count.cpp
index ef21a4d9d61..090bf068f63 100644
--- a/src/mongo/dbtests/query_stage_count.cpp
+++ b/src/mongo/dbtests/query_stage_count.cpp
@@ -39,7 +39,6 @@
 #include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/dbtests/dbtests.h"
 #include "mongo/util/fail_point.h"
 #include "mongo/util/fail_point_registry.h"
diff --git a/src/mongo/dbtests/query_stage_fetch.cpp b/src/mongo/dbtests/query_stage_fetch.cpp
index 445e6341209..8ca27ed9ad0 100644
--- a/src/mongo/dbtests/query_stage_fetch.cpp
+++ b/src/mongo/dbtests/query_stage_fetch.cpp
@@ -42,7 +42,6 @@
 #include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/dbtests/dbtests.h"
 #include "mongo/util/fail_point.h"
 #include "mongo/util/fail_point_registry.h"
@@ -59,7 +58,7 @@ namespace QueryStageFetch {
         }
 
         void getLocs(set<DiskLoc>* out, Collection* coll) {
-            CollectionIterator* it = coll->getIterator(DiskLoc(), false,
+            RecordIterator* it = coll->getIterator(DiskLoc(), false,
                                                        CollectionScanParams::FORWARD);
             while (!it->isEOF()) {
                 DiskLoc nextLoc = it->getNext();
diff --git a/src/mongo/dbtests/query_stage_keep.cpp b/src/mongo/dbtests/query_stage_keep.cpp
index 3c37af51e95..8e4699950e8 100644
--- a/src/mongo/dbtests/query_stage_keep.cpp
+++ b/src/mongo/dbtests/query_stage_keep.cpp
@@ -43,7 +43,6 @@
 #include "mongo/db/matcher/expression_parser.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/dbtests/dbtests.h"
 #include "mongo/util/fail_point.h"
 #include "mongo/util/fail_point_registry.h"
@@ -60,7 +59,7 @@ namespace QueryStageKeep {
         }
 
         void getLocs(set<DiskLoc>* out, Collection* coll) {
-            CollectionIterator* it = coll->getIterator(DiskLoc(), false,
+            RecordIterator* it = coll->getIterator(DiskLoc(), false,
                                                        CollectionScanParams::FORWARD);
             while (!it->isEOF()) {
                 DiskLoc nextLoc = it->getNext();
diff --git a/src/mongo/dbtests/query_stage_merge_sort.cpp b/src/mongo/dbtests/query_stage_merge_sort.cpp
index 7449e3e07e2..0063181b14a 100644
--- a/src/mongo/dbtests/query_stage_merge_sort.cpp
+++ b/src/mongo/dbtests/query_stage_merge_sort.cpp
@@ -36,7 +36,6 @@
 #include "mongo/db/json.h"
 #include "mongo/db/query/plan_executor.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/dbtests/dbtests.h"
 
 /**
@@ -71,7 +70,7 @@ namespace QueryStageMergeSortTests {
         }
 
         void getLocs(set<DiskLoc>* out, Collection* coll) {
-            CollectionIterator* it = coll->getIterator(DiskLoc(), false,
+            RecordIterator* it = coll->getIterator(DiskLoc(), false,
                                                        CollectionScanParams::FORWARD);
             while (!it->isEOF()) {
                 DiskLoc nextLoc = it->getNext();
diff --git a/src/mongo/dbtests/query_stage_sort.cpp b/src/mongo/dbtests/query_stage_sort.cpp
index 7033ae4a489..462a82ef248 100644
--- a/src/mongo/dbtests/query_stage_sort.cpp
+++ b/src/mongo/dbtests/query_stage_sort.cpp
@@ -36,7 +36,6 @@
 #include "mongo/db/json.h"
 #include "mongo/db/query/plan_executor.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 #include "mongo/dbtests/dbtests.h"
 
 /**
@@ -64,7 +63,7 @@ namespace QueryStageSortTests {
         }
 
         void getLocs(set<DiskLoc>* out, Collection* coll) {
-            CollectionIterator* it = coll->getIterator(DiskLoc(), false,
+            RecordIterator* it = coll->getIterator(DiskLoc(), false,
                                                        CollectionScanParams::FORWARD);
             while (!it->isEOF()) {
                 DiskLoc nextLoc = it->getNext();
diff --git a/src/mongo/dbtests/repltests.cpp b/src/mongo/dbtests/repltests.cpp
index 9f720c1d0ca..10c08845122 100644
--- a/src/mongo/dbtests/repltests.cpp
+++ b/src/mongo/dbtests/repltests.cpp
@@ -43,7 +43,6 @@
 #include "mongo/db/repl/rs.h"
 #include "mongo/db/ops/update.h"
 #include "mongo/db/catalog/collection.h"
-#include "mongo/db/structure/collection_iterator.h"
 
 #include "mongo/dbtests/dbtests.h"
 
@@ -121,7 +120,7 @@ namespace ReplTests {
             }
 
             int count = 0;
-            CollectionIterator* it = coll->getIterator( DiskLoc(), false,
+            RecordIterator* it = coll->getIterator( DiskLoc(), false,
                                                         CollectionScanParams::FORWARD );
             for ( ; !it->isEOF(); it->getNext() ) {
                 ++count;
@@ -139,7 +138,7 @@ namespace ReplTests {
             }
 
             int count = 0;
-            CollectionIterator* it = coll->getIterator( DiskLoc(), false,
+            RecordIterator* it = coll->getIterator( DiskLoc(), false,
                                                         CollectionScanParams::FORWARD );
             for ( ; !it->isEOF(); it->getNext() ) {
                 ++count;
@@ -155,7 +154,7 @@ namespace ReplTests {
                 Database* db = ctx.db();
                 Collection* coll = db->getCollection( cllNS() );
 
-                CollectionIterator* it = coll->getIterator( DiskLoc(), false,
+                RecordIterator* it = coll->getIterator( DiskLoc(), false,
                                                             CollectionScanParams::FORWARD );
                 while ( !it->isEOF() ) {
                     DiskLoc currLoc = it->getNext();
@@ -186,7 +185,7 @@ namespace ReplTests {
                 coll = db->createCollection( ns );
             }
 
-            CollectionIterator* it = coll->getIterator( DiskLoc(), false,
+            RecordIterator* it = coll->getIterator( DiskLoc(), false,
                                                         CollectionScanParams::FORWARD );
             out() << "all for " << ns << endl;
             while ( !it->isEOF() ) {
@@ -206,7 +205,7 @@ namespace ReplTests {
             }
 
             vector< DiskLoc > toDelete;
-            CollectionIterator* it = coll->getIterator( DiskLoc(), false,
+            RecordIterator* it = coll->getIterator( DiskLoc(), false,
                                                         CollectionScanParams::FORWARD );
             while ( !it->isEOF() ) {
                 toDelete.push_back( it->getNext() );