[bug-recutils] [PATCH 11/13] src: support index t rees that point to a leaf too left of the key searched f or.

[Michał Masłowski]

This is needed for performance tests to get correct results on a 20000
record set.  This is a bug, would need better unit tests to fix
correctly.
---
 ChangeLog          |  7 +++++++
 src/rec-idx-tree.c | 25 +++++++++++++++----------
 2 files changed, 22 insertions(+), 10 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 78c97b3..7650fd2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2012-08-20  Michał Masłowski  <address@hidden>
+
+       src: support index trees that point to a leaf too left of the key
+       searched for.
+       * src/rec-idx-tree.c (rec_idx_tree_scan_common): Check for
+       next-node offset before using the comparison result.
+
 2012-08-19  Michał Masłowski  <address@hidden>
 
        src: keep indexes in rsets.
diff --git a/src/rec-idx-tree.c b/src/rec-idx-tree.c
index c641e71..751230c 100644
--- a/src/rec-idx-tree.c
+++ b/src/rec-idx-tree.c
@@ -562,12 +562,13 @@ rec_idx_tree_scan_common (rec_idx_tree_t idx_tree,
 
       node = (const uint64_t*) root;
       n_entries = (int) node[0];
-      node++;
+      root = (const uint8_t*) &node[1];
       empty = true;
 
       while (n_entries > 0)
         {
           n_entries--;
+          node = (const uint64_t*) root;
 
           if (root + sizeof (node[0]) * 2 >= idx_tree->end)
             {
@@ -656,15 +657,6 @@ rec_idx_tree_scan_common (rec_idx_tree_t idx_tree,
           return NULL;  /* truncated index */
         }
 
-      if ((comparison < 0) || (left_ind > 0)
-          || ((line & REC_IDX_TREE_NONFIRST_MASK) && first_only))
-        {
-          /* Skip the record, it has too small key or index.  */
-          left_ind--;
-          right_ind--;
-          continue;
-        }
-
       /* We could have parsed the last entry of the node.  In that
          case go to the start of the next one so the iterator always
          starts at a leaf node entry.  */
@@ -691,6 +683,19 @@ rec_idx_tree_scan_common (rec_idx_tree_t idx_tree,
             }
         }
 
+      if ((comparison < 0) || (left_ind > 0)
+          || ((line & REC_IDX_TREE_NONFIRST_MASK) && first_only))
+        {
+          /* Skip the record, it has too small key or index.  */
+          if (left_ind > 0)
+            {
+              left_ind--;
+            }
+
+          right_ind--;
+          continue;
+        }
+
       /* Prepare the iterator. */
       iter_state = malloc (sizeof (*iter_state));
       if (!iter_state)
-- 
1.7.11.4