X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Frange-set-test.c;h=8d6e68316834d707254b5888f92d1b41b1064bb6;hb=cb062bfc8fa1b1477de31fd8a0f072f4bcf3d6b1;hp=2706b70d23ecf00a8dc30ea639580f8edcef01f1;hpb=f726e96e846a133b6493fb017668d4cf4795f737;p=pspp

diff --git a/tests/libpspp/range-set-test.c b/tests/libpspp/range-set-test.c
index 2706b70d23..8d6e683168 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,12 +195,24 @@ 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. */
   for (start = 0; start <= 32; start++)
     {
-      struct range_set *nonconst_rs = (struct range_set *) rs;
+      struct range_set *nonconst_rs = CONST_CAST (struct range_set *, rs);
       nonconst_rs->cache_end = 0;
       s1 = range_set_scan (rs, start);
       s2 = next_1bit (pattern, start);