From 2e2a6414933167456860f7dac8c52d14b25d4821 Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
Date: Mon, 27 Sep 2004 04:37:41 +0000
Subject: [PATCH] Test for linked list implementation.

---
 src/tests/threads/list.c | 163 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 163 insertions(+)
 create mode 100644 src/tests/threads/list.c

diff --git a/src/tests/threads/list.c b/src/tests/threads/list.c
new file mode 100644
index 0000000..aac583f
--- /dev/null
+++ b/src/tests/threads/list.c
@@ -0,0 +1,163 @@
+/* Test program for lib/kernel/list.c.
+
+   Attempts to test the list functionality that is not
+   sufficiently tested elsewhere in Pintos.
+
+   This is not a test we will run on your submitted projects.
+   It is here for completeness.
+*/
+
+#undef NDEBUG
+#include <debug.h>
+#include <list.h>
+#include <random.h>
+#include <stdio.h>
+#include "threads/test.h"
+
+/* Maximum number of elements in a linked list that we will
+   test. */
+#define MAX_SIZE 64
+
+/* A linked list element. */
+struct value 
+  {
+    list_elem elem;             /* List element. */
+    int value;                  /* Item value. */
+  };
+
+static void shuffle (struct value[], size_t);
+static bool value_less (const list_elem *, const list_elem *, void *);
+static void verify_list_fwd (struct list *, int size);
+static void verify_list_bkwd (struct list *, int size);
+
+/* Test the linked list implementation. */
+void
+test (void) 
+{
+  int size;
+
+  printf ("testing various size lists:");
+  for (size = 0; size < MAX_SIZE; size++) 
+    {
+      int repeat;
+
+      printf (" %zu", size);
+      for (repeat = 0; repeat < 10; repeat++) 
+        {
+          static struct value values[MAX_SIZE * 4];
+          struct list list;
+          list_elem *e;
+          int i, ofs;
+
+          /* Put values 0...SIZE in random order in VALUES. */
+          for (i = 0; i < size; i++)
+            values[i].value = i;
+          shuffle (values, size);
+  
+          /* Assemble list. */
+          list_init (&list);
+          for (i = 0; i < size; i++)
+            list_push_back (&list, &values[i].elem);
+
+          /* Sort and verify list. */
+          list_sort (&list, value_less, NULL);
+          verify_list_fwd (&list, size);
+
+          /* Reverse and verify list. */
+          list_reverse (&list);
+          verify_list_bkwd (&list, size);
+
+          /* Shuffle, insert using list_insert_ordered(),
+             and verify ordering. */
+          shuffle (values, size);
+          list_init (&list);
+          for (i = 0; i < size; i++)
+            list_insert_ordered (&list, &values[i].elem,
+                                 value_less, NULL);
+          verify_list_fwd (&list, size);
+
+          /* Duplicate some items, uniquify, and verify. */
+          ofs = size;
+          for (e = list_begin (&list); e != list_end (&list);
+               e = list_next (e))
+            {
+              struct value *v = list_entry (e, struct value, elem);
+              int copies = random_ulong () % 4;
+              while (copies-- > 0) 
+                {
+                  values[ofs].value = v->value;
+                  list_insert (e, &values[ofs++].elem);
+                }
+            }
+          ASSERT ((size_t) ofs < sizeof values / sizeof *values);
+          list_unique (&list, NULL, value_less, NULL);
+          verify_list_fwd (&list, size);
+        }
+    }
+  
+  printf (" done\n");
+}
+
+/* Shuffles the CNT elements in ARRAY into random order. */
+static void
+shuffle (struct value *array, size_t cnt) 
+{
+  size_t i;
+
+  for (i = 0; i < cnt; i++)
+    {
+      size_t j = i + random_ulong () % (cnt - i);
+      struct value t = array[j];
+      array[j] = array[i];
+      array[i] = t;
+    }
+}
+
+/* Returns true if value A is less than value B, false
+   otherwise. */
+static bool
+value_less (const list_elem *a_, const list_elem *b_, void *aux UNUSED) 
+{
+  const struct value *a = list_entry (a_, struct value, elem);
+  const struct value *b = list_entry (b_, struct value, elem);
+  
+  return a->value < b->value;
+}
+
+/* Verifies that LIST contains the values 0...SIZE when traversed
+   in forward order. */
+static void
+verify_list_fwd (struct list *list, int size) 
+{
+  list_elem *e;
+  int i;
+  
+  for (i = 0, e = list_begin (list);
+       i < size && e != list_end (list);
+       i++, e = list_next (e)) 
+    {
+      struct value *v = list_entry (e, struct value, elem);
+      ASSERT (i == v->value);
+    }
+  ASSERT (i == size);
+  ASSERT (e == list_end (list));
+}
+
+/* Verifies that LIST contains the values 0...SIZE when traversed
+   in reverse order. */
+static void
+verify_list_bkwd (struct list *list, int size) 
+{
+  list_elem *e;
+  int i;
+
+  for (i = 0, e = list_rbegin (list);
+       i < size && e != list_rend (list);
+       i++, e = list_prev (e)) 
+    {
+      struct value *v = list_entry (e, struct value, elem);
+      ASSERT (i == v->value);
+    }
+  ASSERT (i == size);
+  ASSERT (e == list_rend (list));
+}
-- 
2.30.2