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           /* Sort and verify list. */
  63           list_sort (&list, value_less, NULL);
  64           verify_list_fwd (&list, size);
  65
  66           /* Reverse and verify list. */
  67           list_reverse (&list);
  68           verify_list_bkwd (&list, size);
  69
  70           /* Shuffle, insert using list_insert_ordered(),
  71              and verify ordering. */
  72           shuffle (values, size);
  73           list_init (&list);
  74           for (i = 0; i < size; i++)
  75             list_insert_ordered (&list, &values[i].elem,
  76                                  value_less, NULL);
  77           verify_list_fwd (&list, size);
  78
  79           /* Duplicate some items, uniquify, and verify. */
  80           ofs = size;
  81           for (e = list_begin (&list); e != list_end (&list);
  82                e = list_next (e))
  83             {
  84               struct value *v = list_entry (e, struct value, elem);
  85               int copies = random_ulong () % 4;
  86               while (copies-- > 0)
  87                 {
  88                   values[ofs].value = v->value;
  89                   list_insert (e, &values[ofs++].elem);
  90                 }
  91             }
  92           ASSERT ((size_t) ofs < sizeof values / sizeof *values);
  93           list_unique (&list, NULL, value_less, NULL);
  94           verify_list_fwd (&list, size);
  95         }
  96     }
  97
  98   printf (" done\n");
  99 }
 100
 101 /* Shuffles the CNT elements in ARRAY into random order. */
 102 static void
 103 shuffle (struct value *array, size_t cnt)
 104 {
 105   size_t i;
 106
 107   for (i = 0; i < cnt; i++)
 108     {
 109       size_t j = i + random_ulong () % (cnt - i);
 110       struct value t = array[j];
 111       array[j] = array[i];
 112       array[i] = t;
 113     }
 114 }
 115
 116 /* Returns true if value A is less than value B, false
 117    otherwise. */
 118 static bool
 119 value_less (const list_elem *a_, const list_elem *b_, void *aux UNUSED)
 120 {
 121   const struct value *a = list_entry (a_, struct value, elem);
 122   const struct value *b = list_entry (b_, struct value, elem);
 123
 124   return a->value < b->value;
 125 }
 126
 127 /* Verifies that LIST contains the values 0...SIZE when traversed
 128    in forward order. */
 129 static void
 130 verify_list_fwd (struct list *list, int size)
 131 {
 132   list_elem *e;
 133   int i;
 134
 135   for (i = 0, e = list_begin (list);
 136        i < size && e != list_end (list);
 137        i++, e = list_next (e))
 138     {
 139       struct value *v = list_entry (e, struct value, elem);
 140       ASSERT (i == v->value);
 141     }
 142   ASSERT (i == size);
 143   ASSERT (e == list_end (list));
 144 }
 145
 146 /* Verifies that LIST contains the values 0...SIZE when traversed
 147    in reverse order. */
 148 static void
 149 verify_list_bkwd (struct list *list, int size)
 150 {
 151   list_elem *e;
 152   int i;
 153
 154   for (i = 0, e = list_rbegin (list);
 155        i < size && e != list_rend (list);
 156        i++, e = list_prev (e))
 157     {
 158       struct value *v = list_entry (e, struct value, elem);
 159       ASSERT (i == v->value);
 160     }
 161   ASSERT (i == size);
 162   ASSERT (e == list_rend (list));
 163 }