range-set: Add new function range_set_scan().

[pspp-builds.git] / src / libpspp / range-set.c

diff --git a/src/libpspp/range-set.c b/src/libpspp/range-set.c
index d238ea98c5f72e03bbc49a16adcf584ef33894ad..efa3b4d670e7e06c3c560ebc64ade1bf4d45ae21 100644 (file)
--- a/src/libpspp/range-set.c
+++ b/src/libpspp/range-set.c
@@ -321,6 +321,40 @@ range_set_contains (const struct range_set *rs_, unsigned long int position)
         }
     }
 }
+
+/* Returns the smallest position of a 1-bit greater than or
+   equal to START.  Returns ULONG_MAX if there is no 1-bit with
+   position greater than or equal to START. */
+unsigned long int
+range_set_scan (const struct range_set *rs_, unsigned long int start)
+{
+  struct range_set *rs = (struct range_set *) rs_;
+  unsigned long int retval = ULONG_MAX;
+  struct bt_node *bt_node;
+
+  if (start < rs->cache_end && start >= rs->cache_start && rs->cache_value)
+    return start;
+  bt_node = rs->bt.root;
+  while (bt_node != NULL)
+    {
+      struct range_set_node *node = range_set_node_from_bt__ (bt_node);
+      if (start < node->start)
+        {
+          retval = node->start;
+          bt_node = node->bt_node.down[0];
+        }
+      else if (start >= node->end)
+        bt_node = node->bt_node.down[1];
+      else
+        {
+          rs->cache_start = node->start;
+          rs->cache_end = node->end;
+          rs->cache_value = true;
+          return start;
+        }
+    }
+  return retval;
+}
 \f
 /* Compares `range_set_node's A and B and returns a strcmp-like
    return value. */