From 29eec4ed65faec40e628474ba759899d7aaf9762 Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@gnu.org>
Date: Mon, 4 May 2009 19:31:16 -0700
Subject: [PATCH] range-set: New functions range_set_last and range_set_prev.

These are useful for iterating through a range set in reverse order.
---
 src/libpspp/range-set.h        | 50 ++++++++++++++++++++++++++++++++++
 tests/libpspp/range-set-test.c | 41 ++++++++++++++++++++++++++++
 2 files changed, 91 insertions(+)

diff --git a/src/libpspp/range-set.h b/src/libpspp/range-set.h
index 3b7d04f4..941692b4 100644
--- a/src/libpspp/range-set.h
+++ b/src/libpspp/range-set.h
@@ -70,6 +70,10 @@ static inline const struct range_set_node *range_set_first (
   const struct range_set *);
 static inline const struct range_set_node *range_set_next (
   const struct range_set *, const struct range_set_node *);
+static inline const struct range_set_node *range_set_last (
+  const struct range_set *);
+static inline const struct range_set_node *range_set_prev (
+  const struct range_set *, const struct range_set_node *);
 static inline unsigned long int range_set_node_get_start (
   const struct range_set_node *);
 static inline unsigned long int range_set_node_get_end (
@@ -85,6 +89,10 @@ static inline struct range_set_node *range_set_next__ (
   const struct range_set *, const struct range_set_node *);
 static inline struct range_set_node *range_set_first__ (
   const struct range_set *);
+static inline struct range_set_node *range_set_prev__ (
+  const struct range_set *, const struct range_set_node *);
+static inline struct range_set_node *range_set_last__ (
+  const struct range_set *);
 
 /* Returns true if RS contains no 1-bits, false otherwise. */
 static inline bool
@@ -118,6 +126,31 @@ range_set_next (const struct range_set *rs, const struct range_set_node *node)
           : range_set_first__ (rs));
 }
 
+/* Returns the node representing the last contiguous region of
+   1-bits in RS, or a null pointer if RS is empty.
+   Any call to range_set_insert, range_set_delete, or
+   range_set_allocate invalidates the returned node. */
+static inline const struct range_set_node *
+range_set_last (const struct range_set *rs)
+{
+  return range_set_last__ (rs);
+}
+
+/* If NODE is nonnull, returns the node representing the previous
+   contiguous region of 1-bits in RS following NODE, or a null
+   pointer if NODE is the first region in RS.
+   If NODE is null, returns the last region in RS, as for
+   range_set_last.
+   Any call to range_set_insert, range_set_delete, or
+   range_set_allocate invalidates the returned node. */
+static inline const struct range_set_node *
+range_set_prev (const struct range_set *rs, const struct range_set_node *node)
+{
+  return (node != NULL
+          ? range_set_prev__ (rs, (struct range_set_node *) node)
+          : range_set_last__ (rs));
+}
+
 /* Returns the position of the first 1-bit in NODE. */
 static inline unsigned long int
 range_set_node_get_start (const struct range_set_node *node)
@@ -166,4 +199,21 @@ range_set_first__ (const struct range_set *rs)
   return range_set_node_from_bt__ (bt_first (&rs->bt));
 }
 
+/* Returns the previous range_set_node in RS after NODE,
+   or a null pointer if NODE is the first node in RS. */
+static inline struct range_set_node *
+range_set_prev__ (const struct range_set *rs,
+                  const struct range_set_node *node)
+{
+  return range_set_node_from_bt__ (bt_prev (&rs->bt, &node->bt_node));
+}
+
+/* Returns the last range_set_node in RS,
+   or a null pointer if RS is empty. */
+static inline struct range_set_node *
+range_set_last__ (const struct range_set *rs)
+{
+  return range_set_node_from_bt__ (bt_last (&rs->bt));
+}
+
 #endif /* libpspp/range-set.h */
diff --git a/tests/libpspp/range-set-test.c b/tests/libpspp/range-set-test.c
index 2706b70d..e8cbffa5 100644
--- a/tests/libpspp/range-set-test.c
+++ b/tests/libpspp/range-set-test.c
@@ -119,6 +119,35 @@ next_region (unsigned int pattern, unsigned int offset,
   return false;
 }
 
+/* Searches the bits in PATTERN from left to right starting from
+   just beyond bit OFFSET for one or more 1-bits.  If any are
+   found, sets *START to the bit index of the first and *WIDTH to
+   the number of contiguous 1-bits and returns true.  Otherwise,
+   returns false.
+   This implementation is designed to be obviously correct, not
+   to be efficient. */
+static bool
+prev_region (unsigned int pattern, unsigned int offset,
+             unsigned long int *start, unsigned long int *width)
+{
+  unsigned int i;
+
+  assert (offset <= UINT_BIT);
+  for (i = offset; i-- > 0; )
+    if (pattern & (1u << i))
+      {
+        *start = i;
+        *width = 1;
+        while (i-- > 0 && pattern & (1u << i))
+          {
+            ++*width;
+            --*start;
+          }
+        return true;
+      }
+  return false;
+}
+
 /* Searches the bits in PATTERN from right to left starting from
    bit OFFSET.  Returns the bit index of the first 1-bit found,
    or ULONG_MAX if none is found. */
@@ -166,6 +195,18 @@ check_pattern (const struct range_set *rs, unsigned int pattern)
     }
   check (node == NULL);
 
+  for (node = rand () % 2 ? range_set_last (rs) : range_set_prev (rs, NULL),
+         start = UINT_BIT;
+       prev_region (pattern, start, &start, &width);
+       node = range_set_prev (rs, node))
+    {
+      check (node != NULL);
+      check (range_set_node_get_start (node) == start);
+      check (range_set_node_get_end (node) == start + width);
+      check (range_set_node_get_width (node) == width);
+    }
+  check (node == NULL);
+
   /* Scan from all possible positions, resetting the cache each
      time, to ensure that we get the correct answers without
      caching. */
-- 
2.30.2