tests/test-array_list.c

   1 /* Test of sequential list data type implementation.
   2    Copyright (C) 2006-2009 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2007.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include "gl_array_list.h"
  21
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24
  25 #include "progname.h"
  26
  27 static const char *objects[15] =
  28   {
  29     "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
  30   };
  31
  32 #define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
  33 #define ASSERT(expr) \
  34   do                                                                         \
  35     {                                                                        \
  36       if (!(expr))                                                           \
  37         {                                                                    \
  38           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  39           fflush (stderr);                                                   \
  40           abort ();                                                          \
  41         }                                                                    \
  42     }                                                                        \
  43   while (0)
  44 #define RANDOM(n) (rand () % (n))
  45 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
  46
  47 static void
  48 check_equals (gl_list_t list1, gl_list_t list2)
  49 {
  50   size_t n, i;
  51
  52   n = gl_list_size (list1);
  53   ASSERT (n == gl_list_size (list2));
  54   for (i = 0; i < n; i++)
  55     {
  56       ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
  57     }
  58 }
  59
  60 int
  61 main (int argc, char *argv[])
  62 {
  63   gl_list_t list1, list2;
  64
  65   set_program_name (argv[0]);
  66
  67   /* Allow the user to provide a non-default random seed on the command line.  */
  68   if (argc > 1)
  69     srand (atoi (argv[1]));
  70
  71   {
  72     size_t initial_size = RANDOM (50);
  73     const void **contents =
  74       (const void **) malloc (initial_size * sizeof (const void *));
  75     size_t i;
  76     unsigned int repeat;
  77
  78     for (i = 0; i < initial_size; i++)
  79       contents[i] = RANDOM_OBJECT ();
  80
  81     /* Create list1.  */
  82     list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
  83                                initial_size, contents);
  84     ASSERT (list1 != NULL);
  85     /* Create list2.  */
  86     list2 = gl_list_nx_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
  87     ASSERT (list2 != NULL);
  88     for (i = 0; i < initial_size; i++)
  89       ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
  90
  91     check_equals (list1, list2);
  92
  93     for (repeat = 0; repeat < 10000; repeat++)
  94       {
  95         unsigned int operation = RANDOM (16);
  96         switch (operation)
  97           {
  98           case 0:
  99             if (gl_list_size (list1) > 0)
 100               {
 101                 size_t index = RANDOM (gl_list_size (list1));
 102                 const char *obj = RANDOM_OBJECT ();
 103                 gl_list_node_t node1, node2;
 104
 105                 node1 = gl_list_nx_set_at (list1, index, obj);
 106                 ASSERT (node1 != NULL);
 107                 ASSERT (gl_list_get_at (list1, index) == obj);
 108                 ASSERT (gl_list_node_value (list1, node1) == obj);
 109
 110                 node2 = gl_list_nx_set_at (list2, index, obj);
 111                 ASSERT (node2 != NULL);
 112                 ASSERT (gl_list_get_at (list2, index) == obj);
 113                 ASSERT (gl_list_node_value (list2, node2) == obj);
 114
 115                 if (index > 0)
 116                   {
 117                     ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 118                             == gl_list_get_at (list1, index - 1));
 119                   }
 120                 if (index + 1 < gl_list_size (list1))
 121                   {
 122                     ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 123                             == gl_list_get_at (list1, index + 1));
 124                   }
 125               }
 126             break;
 127           case 1:
 128             {
 129               const char *obj = RANDOM_OBJECT ();
 130               gl_list_node_t node1, node2;
 131               node1 = gl_list_search (list1, obj);
 132               node2 = gl_list_search (list2, obj);
 133               if (node1 == NULL)
 134                 {
 135                   ASSERT (node2 == NULL);
 136                 }
 137               else
 138                 {
 139                   ASSERT (node2 != NULL);
 140                   ASSERT (gl_list_node_value (list1, node1) == obj);
 141                   ASSERT (gl_list_node_value (list2, node2) == obj);
 142                 }
 143             }
 144             break;
 145           case 2:
 146             {
 147               const char *obj = RANDOM_OBJECT ();
 148               size_t index1, index2;
 149               index1 = gl_list_indexof (list1, obj);
 150               index2 = gl_list_indexof (list2, obj);
 151               if (index1 == (size_t)(-1))
 152                 {
 153                   ASSERT (index2 == (size_t)(-1));
 154                 }
 155               else
 156                 {
 157                   ASSERT (index2 != (size_t)(-1));
 158                   ASSERT (gl_list_get_at (list1, index1) == obj);
 159                   ASSERT (gl_list_get_at (list2, index2) == obj);
 160                   ASSERT (index2 == index1);
 161                 }
 162             }
 163             break;
 164           case 3: /* add 1 element */
 165             {
 166               const char *obj = RANDOM_OBJECT ();
 167               gl_list_node_t node1, node2;
 168               node1 = gl_list_nx_add_first (list1, obj);
 169               ASSERT (node1 != NULL);
 170               node2 = gl_list_nx_add_first (list2, obj);
 171               ASSERT (node2 != NULL);
 172               ASSERT (gl_list_node_value (list1, node1) == obj);
 173               ASSERT (gl_list_node_value (list2, node2) == obj);
 174               ASSERT (gl_list_get_at (list1, 0) == obj);
 175               ASSERT (gl_list_get_at (list2, 0) == obj);
 176             }
 177             break;
 178           case 4: /* add 1 element */
 179             {
 180               const char *obj = RANDOM_OBJECT ();
 181               gl_list_node_t node1, node2;
 182               node1 = gl_list_nx_add_last (list1, obj);
 183               ASSERT (node1 != NULL);
 184               node2 = gl_list_nx_add_last (list2, obj);
 185               ASSERT (node2 != NULL);
 186               ASSERT (gl_list_node_value (list1, node1) == obj);
 187               ASSERT (gl_list_node_value (list2, node2) == obj);
 188               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
 189               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
 190             }
 191             break;
 192           case 5: /* add 3 elements */
 193             {
 194               const char *obj0 = RANDOM_OBJECT ();
 195               const char *obj1 = RANDOM_OBJECT ();
 196               const char *obj2 = RANDOM_OBJECT ();
 197               gl_list_node_t node1, node2;
 198               node1 = gl_list_nx_add_first (list1, obj2);
 199               ASSERT (node1 != NULL);
 200               node1 = gl_list_nx_add_before (list1, node1, obj0);
 201               ASSERT (node1 != NULL);
 202               node1 = gl_list_nx_add_after (list1, node1, obj1);
 203               ASSERT (node1 != NULL);
 204               node2 = gl_list_nx_add_first (list2, obj2);
 205               ASSERT (node2 != NULL);
 206               node2 = gl_list_nx_add_before (list2, node2, obj0);
 207               ASSERT (node2 != NULL);
 208               node2 = gl_list_nx_add_after (list2, node2, obj1);
 209               ASSERT (node2 != NULL);
 210               ASSERT (gl_list_node_value (list1, node1) == obj1);
 211               ASSERT (gl_list_node_value (list2, node2) == obj1);
 212               ASSERT (gl_list_get_at (list1, 0) == obj0);
 213               ASSERT (gl_list_get_at (list1, 1) == obj1);
 214               ASSERT (gl_list_get_at (list1, 2) == obj2);
 215               ASSERT (gl_list_get_at (list2, 0) == obj0);
 216               ASSERT (gl_list_get_at (list2, 1) == obj1);
 217               ASSERT (gl_list_get_at (list2, 2) == obj2);
 218             }
 219             break;
 220           case 6: /* add 1 element */
 221             {
 222               size_t index = RANDOM (gl_list_size (list1) + 1);
 223               const char *obj = RANDOM_OBJECT ();
 224               gl_list_node_t node1, node2;
 225               node1 = gl_list_nx_add_at (list1, index, obj);
 226               ASSERT (node1 != NULL);
 227               node2 = gl_list_nx_add_at (list2, index, obj);
 228               ASSERT (node2 != NULL);
 229               ASSERT (gl_list_get_at (list1, index) == obj);
 230               ASSERT (gl_list_node_value (list1, node1) == obj);
 231               ASSERT (gl_list_get_at (list2, index) == obj);
 232               ASSERT (gl_list_node_value (list2, node2) == obj);
 233               if (index > 0)
 234                 {
 235                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 236                           == gl_list_get_at (list1, index - 1));
 237                 }
 238               if (index + 1 < gl_list_size (list1))
 239                 {
 240                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 241                           == gl_list_get_at (list1, index + 1));
 242                 }
 243             }
 244             break;
 245           case 7: case 8: /* remove 1 element */
 246             if (gl_list_size (list1) > 0)
 247               {
 248                 size_t n = gl_list_size (list1);
 249                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 250                 gl_list_node_t node1, node2;
 251                 node1 = gl_list_search (list1, obj);
 252                 node2 = gl_list_search (list2, obj);
 253                 ASSERT (node1 != NULL);
 254                 ASSERT (node2 != NULL);
 255                 ASSERT (gl_list_remove_node (list1, node1));
 256                 ASSERT (gl_list_remove_node (list2, node2));
 257                 ASSERT (gl_list_size (list1) == n - 1);
 258               }
 259             break;
 260           case 9: case 10: /* remove 1 element */
 261             if (gl_list_size (list1) > 0)
 262               {
 263                 size_t n = gl_list_size (list1);
 264                 size_t index = RANDOM (n);
 265                 ASSERT (gl_list_remove_at (list1, index));
 266                 ASSERT (gl_list_remove_at (list2, index));
 267                 ASSERT (gl_list_size (list1) == n - 1);
 268               }
 269             break;
 270           case 11: case 12: /* remove 1 element */
 271             if (gl_list_size (list1) > 0)
 272               {
 273                 size_t n = gl_list_size (list1);
 274                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 275                 ASSERT (gl_list_remove (list1, obj));
 276                 ASSERT (gl_list_remove (list2, obj));
 277                 ASSERT (gl_list_size (list1) == n - 1);
 278               }
 279             break;
 280           case 13:
 281             if (gl_list_size (list1) > 0)
 282               {
 283                 size_t n = gl_list_size (list1);
 284                 const char *obj = "xyzzy";
 285                 ASSERT (!gl_list_remove (list1, obj));
 286                 ASSERT (!gl_list_remove (list2, obj));
 287                 ASSERT (gl_list_size (list1) == n);
 288               }
 289             break;
 290           case 14:
 291             {
 292               size_t n = gl_list_size (list1);
 293               gl_list_iterator_t iter1, iter2;
 294               const void *elt;
 295               iter1 = gl_list_iterator (list1);
 296               iter2 = gl_list_iterator (list2);
 297               for (i = 0; i < n; i++)
 298                 {
 299                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 300                   ASSERT (gl_list_get_at (list1, i) == elt);
 301                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 302                   ASSERT (gl_list_get_at (list2, i) == elt);
 303                 }
 304               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 305               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 306               gl_list_iterator_free (&iter1);
 307               gl_list_iterator_free (&iter2);
 308             }
 309             break;
 310           case 15:
 311             {
 312               size_t end = RANDOM (gl_list_size (list1) + 1);
 313               size_t start = RANDOM (end + 1);
 314               gl_list_iterator_t iter1, iter2;
 315               const void *elt;
 316               iter1 = gl_list_iterator_from_to (list1, start, end);
 317               iter2 = gl_list_iterator_from_to (list2, start, end);
 318               for (i = start; i < end; i++)
 319                 {
 320                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 321                   ASSERT (gl_list_get_at (list1, i) == elt);
 322                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 323                   ASSERT (gl_list_get_at (list2, i) == elt);
 324                 }
 325               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 326               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 327               gl_list_iterator_free (&iter1);
 328               gl_list_iterator_free (&iter2);
 329             }
 330             break;
 331           }
 332         check_equals (list1, list2);
 333       }
 334
 335     gl_list_free (list1);
 336     gl_list_free (list2);
 337     free (contents);
 338   }
 339
 340   return 0;
 341 }