X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Frange-set-test.c;h=e8cbffa5e6334408bbd69dc4c7c2a7e9dbb72829;hb=e9599a2f8e86d986fff1518682ba8942bd67d1c0;hp=b0eb7abbf81f5249fb2b29131a4a1351e9c2b726;hpb=186db0c54bcb0caf4a6df1fcc60b8158bc11ab92;p=pspp-builds.git

diff --git a/tests/libpspp/range-set-test.c b/tests/libpspp/range-set-test.c
index b0eb7abb..e8cbffa5 100644
--- a/tests/libpspp/range-set-test.c
+++ b/tests/libpspp/range-set-test.c
@@ -119,6 +119,47 @@ 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. */
+static unsigned long int
+next_1bit (unsigned int pattern, unsigned int offset)
+{
+  for (; offset < UINT_BIT; offset++)
+    if (pattern & (1u << offset))
+      return offset;
+  return ULONG_MAX;
+}
+
 /* Prints the regions in RS to stdout. */
 static void UNUSED
 print_regions (const struct range_set *rs)
@@ -139,6 +180,7 @@ check_pattern (const struct range_set *rs, unsigned int pattern)
 {
   const struct range_set_node *node;
   unsigned long int start, width;
+  unsigned long int s1, s2;
   int i;
 
   for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
@@ -153,6 +195,52 @@ 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;
+      nonconst_rs->cache_end = 0;
+      s1 = range_set_scan (rs, start);
+      s2 = next_1bit (pattern, start);
+      check (s1 == s2);
+    }
+
+  /* Scan in forward order to exercise expected cache behavior. */
+  for (s1 = range_set_scan (rs, 0), s2 = next_1bit (pattern, 0); ;
+       s1 = range_set_scan (rs, s1 + 1), s2 = next_1bit (pattern, s2 + 1))
+    {
+      check (s1 == s2);
+      if (s1 == ULONG_MAX)
+        break;
+    }
+
+  /* Scan in random order to frustrate cache. */
+  for (i = 0; i < 32; i++)
+    {
+      start = rand () % 32;
+      s1 = range_set_scan (rs, start);
+      s2 = next_1bit (pattern, start);
+      check (s1 == s2);
+    }
+
+  /* Test range_set_scan() with negative cache. */
+  check (!range_set_contains (rs, 999));
+  check (range_set_scan (rs, 1111) == ULONG_MAX);
+
   for (i = 0; i < UINT_BIT; i++)
     check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
   check (!range_set_contains (rs,
@@ -364,6 +452,13 @@ test_pool (void)
   range_set_insert (rs, 1, 10);
   pool_destroy (pool);
 }
+
+/* Tests range_set_destroy(NULL). */
+static void
+test_destroy_null (void)
+{
+  range_set_destroy (NULL);
+}
 
 /* Main program. */
 
@@ -385,6 +480,7 @@ main (void)
   run_test (test_allocate, "allocate");
   run_test (test_allocate_fully, "allocate_fully");
   run_test (test_pool, "pool");
+  run_test (test_destroy_null, "destroy null");
   putchar ('\n');
 
   return 0;