Add comments for foreach_key_range() method and related methods.

2 files changed, 30 insertions, 0 deletions

diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.h b/vespalib/src/vespa/vespalib/btree/btreeiterator.h
index 5d590115125..6933fc1c2d0 100644
--- a/vespalib/src/vespa/vespalib/btree/btreeiterator.h
+++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.h
@@ -304,6 +304,10 @@ protected:
      */
     VESPA_DLL_LOCAL void clearPath(uint32_t pathSize);
 
+    /**
+     * Call func with leaf entry key value as argument for all leaf entries in subtree
+     * from this iterator position to end of subtree.
+     */
     template <typename FunctionType>
     void
     foreach_key_range_start(uint32_t level, FunctionType func) const
@@ -320,6 +324,11 @@ protected:
         }
     }
 
+    /**
+     * Call func with leaf entry key value as argument for all leaf entries in subtree
+     * from start of subtree until this iterator position is reached (i.e. entries in
+     * subtree before this iterator position).
+     */
     template <typename FunctionType>
     void
     foreach_key_range_end(uint32_t level, FunctionType func) const
@@ -484,6 +493,11 @@ public:
         }
     }
 
+    /**
+     * Call func with leaf entry key value as argument for all leaf entries in tree from
+     * this iterator position until end_itr position is reached (i.e. entries in
+     * range [this iterator, end_itr)).
+     */
     template <typename FunctionType>
     void
     foreach_key_range(const BTreeIteratorBase &end_itr, FunctionType func) const
@@ -499,6 +513,10 @@ public:
         assert(_allocator == end_itr._allocator);
         uint32_t level = _pathSize;
         if (level > 0u) {
+            /**
+             * Tree has intermediate nodes. Detect lowest shared tree node for this
+             * iterator and end_itr.
+             */
             uint32_t idx;
             uint32_t eidx;
             do {
@@ -515,13 +533,18 @@ public:
                 }
             } while (level != 0);
             if (level > 0u) {
+                // Lowest shared node is an intermediate node.
+                // Left subtree for child [idx], from this iterator position to end of subtree.
                 foreach_key_range_start(level - 1, func);
                 auto &store = _allocator->getNodeStore();
                 auto node = _path[level - 1].getNode();
+                // Any intermediate subtrees for children [idx + 1, eidx).
                 node->foreach_key_range(store, idx + 1, eidx, func);
+                // Right subtree for child [eidx], from start of subtree to end_itr position.
                 end_itr.foreach_key_range_end(level - 1, func);
                 return;
             } else {
+                // Lowest shared node is a leaf node.
                 assert(_leaf.getNode() == end_itr._leaf.getNode());
             }
         }
diff --git a/vespalib/src/vespa/vespalib/btree/btreenode.h b/vespalib/src/vespa/vespalib/btree/btreenode.h
index 4abf18c0037..0c70e70bc6a 100644
--- a/vespalib/src/vespa/vespalib/btree/btreenode.h
+++ b/vespalib/src/vespa/vespalib/btree/btreenode.h
@@ -370,6 +370,10 @@ public:
         }
     }
 
+    /**
+     * Call func with leaf entry key value as argument for all leaf entries in subtrees
+     * for children [start_idx, end_idx).
+     */
     template <typename NodeStoreType, typename FunctionType>
     void foreach_key_range(NodeStoreType &store, uint32_t start_idx, uint32_t end_idx, FunctionType func) const {
         const BTreeNode::Ref *it = this->_data;
@@ -475,6 +479,9 @@ public:
         }
     }
 
+    /**
+     * Call func with leaf entry key value as argument for leaf entries [start_idx, end_idx).
+     */
     template <typename FunctionType>
     void foreach_key_range(uint32_t start_idx, uint32_t end_idx, FunctionType func) const {
         const KeyT *it = _keys;