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