/* 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 
  {
    struct list_elem elem;      /* List element. */
    int value;                  /* Item value. */
  };

static void shuffle (struct value[], size_t);
static bool value_less (const struct list_elem *, const struct 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 (" %d", size);
      for (repeat = 0; repeat < 10; repeat++) 
        {
          static struct value values[MAX_SIZE * 4];
          struct list list;
          struct 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);

          /* Verify correct minimum and maximum elements. */
          e = list_min (&list, value_less, NULL);
          ASSERT (size ? list_entry (e, struct value, elem)->value == 0
                  : e == list_begin (&list));
          e = list_max (&list, value_less, NULL);
          ASSERT (size ? list_entry (e, struct value, elem)->value == size - 1
                  : e == list_begin (&list));

          /* 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");
  printf ("list: PASS\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 struct list_elem *a_, const struct 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) 
{
  struct 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) 
{
  struct 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));
}