pintos-os.org Git - pintos-anon/blob - src/tests/threads/list.c

   1 /* Test program for lib/kernel/list.c.
   2
   3    Attempts to test the list functionality that is not
   4    sufficiently tested elsewhere in Pintos.
   5
   6    This is not a test we will run on your submitted projects.
   7    It is here for completeness.
   8 */
   9
  10 #undef NDEBUG
  11 #include <debug.h>
  12 #include <list.h>
  13 #include <random.h>
  14 #include <stdio.h>
  15 #include "threads/test.h"
  16
  17 /* Maximum number of elements in a linked list that we will
  18    test. */
  19 #define MAX_SIZE 64
  20
  21 /* A linked list element. */
  22 struct value
  23   {
  24     struct list_elem elem;      /* List element. */
  25     int value;                  /* Item value. */
  26   };
  27
  28 static void shuffle (struct value[], size_t);
  29 static bool value_less (const struct list_elem *, const struct list_elem *,
  30                         void *);
  31 static void verify_list_fwd (struct list *, int size);
  32 static void verify_list_bkwd (struct list *, int size);
  33
  34 /* Test the linked list implementation. */
  35 void
  36 test (void)
  37 {
  38   int size;
  39
  40   printf ("testing various size lists:");
  41   for (size = 0; size < MAX_SIZE; size++)
  42     {
  43       int repeat;
  44
  45       printf (" %d", size);
  46       for (repeat = 0; repeat < 10; repeat++)
  47         {
  48           static struct value values[MAX_SIZE * 4];
  49           struct list list;
  50           struct list_elem *e;
  51           int i, ofs;
  52
  53           /* Put values 0...SIZE in random order in VALUES. */
  54           for (i = 0; i < size; i++)
  55             values[i].value = i;
  56           shuffle (values, size);
  57
  58           /* Assemble list. */
  59           list_init (&list);
  60           for (i = 0; i < size; i++)
  61             list_push_back (&list, &values[i].elem);
  62
  63           /* Verify correct minimum and maximum elements. */
  64           e = list_min (&list, value_less, NULL);
  65           ASSERT (size ? list_entry (e, struct value, elem)->value == 0
  66                   : e == list_begin (&list));
  67           e = list_max (&list, value_less, NULL);
  68           ASSERT (size ? list_entry (e, struct value, elem)->value == size - 1
  69                   : e == list_begin (&list));
  70
  71           /* Sort and verify list. */
  72           list_sort (&list, value_less, NULL);
  73           verify_list_fwd (&list, size);
  74
  75           /* Reverse and verify list. */
  76           list_reverse (&list);
  77           verify_list_bkwd (&list, size);
  78
  79           /* Shuffle, insert using list_insert_ordered(),
  80              and verify ordering. */
  81           shuffle (values, size);
  82           list_init (&list);
  83           for (i = 0; i < size; i++)
  84             list_insert_ordered (&list, &values[i].elem,
  85                                  value_less, NULL);
  86           verify_list_fwd (&list, size);
  87
  88           /* Duplicate some items, uniquify, and verify. */
  89           ofs = size;
  90           for (e = list_begin (&list); e != list_end (&list);
  91                e = list_next (e))
  92             {
  93               struct value *v = list_entry (e, struct value, elem);
  94               int copies = random_ulong () % 4;
  95               while (copies-- > 0)
  96                 {
  97                   values[ofs].value = v->value;
  98                   list_insert (e, &values[ofs++].elem);
  99                 }
 100             }
 101           ASSERT ((size_t) ofs < sizeof values / sizeof *values);
 102           list_unique (&list, NULL, value_less, NULL);
 103           verify_list_fwd (&list, size);
 104         }
 105     }
 106
 107   printf (" done\n");
 108   printf ("list: PASS\n");
 109 }
 110
 111 /* Shuffles the CNT elements in ARRAY into random order. */
 112 static void
 113 shuffle (struct value *array, size_t cnt)
 114 {
 115   size_t i;
 116
 117   for (i = 0; i < cnt; i++)
 118     {
 119       size_t j = i + random_ulong () % (cnt - i);
 120       struct value t = array[j];
 121       array[j] = array[i];
 122       array[i] = t;
 123     }
 124 }
 125
 126 /* Returns true if value A is less than value B, false
 127    otherwise. */
 128 static bool
 129 value_less (const struct list_elem *a_, const struct list_elem *b_,
 130             void *aux UNUSED)
 131 {
 132   const struct value *a = list_entry (a_, struct value, elem);
 133   const struct value *b = list_entry (b_, struct value, elem);
 134
 135   return a->value < b->value;
 136 }
 137
 138 /* Verifies that LIST contains the values 0...SIZE when traversed
 139    in forward order. */
 140 static void
 141 verify_list_fwd (struct list *list, int size)
 142 {
 143   struct list_elem *e;
 144   int i;
 145
 146   for (i = 0, e = list_begin (list);
 147        i < size && e != list_end (list);
 148        i++, e = list_next (e))
 149     {
 150       struct value *v = list_entry (e, struct value, elem);
 151       ASSERT (i == v->value);
 152     }
 153   ASSERT (i == size);
 154   ASSERT (e == list_end (list));
 155 }
 156
 157 /* Verifies that LIST contains the values 0...SIZE when traversed
 158    in reverse order. */
 159 static void
 160 verify_list_bkwd (struct list *list, int size)
 161 {
 162   struct list_elem *e;
 163   int i;
 164
 165   for (i = 0, e = list_rbegin (list);
 166        i < size && e != list_rend (list);
 167        i++, e = list_prev (e))
 168     {
 169       struct value *v = list_entry (e, struct value, elem);
 170       ASSERT (i == v->value);
 171     }
 172   ASSERT (i == size);
 173   ASSERT (e == list_rend (list));
 174 }