tests/test-array_list.c

   1 /* Test of sequential list data type implementation.
   2    Copyright (C) 2006-2007 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 2, or (at your option)
   8    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, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 #include <config.h>
  20
  21 #include "gl_array_list.h"
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25
  26 #include "progname.h"
  27
  28 static const char *objects[15] =
  29   {
  30     "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
  31   };
  32
  33 #define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
  34 #define ASSERT(expr) \
  35   do                                                                         \
  36     {                                                                        \
  37       if (!(expr))                                                           \
  38         {                                                                    \
  39           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  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_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
  83                             initial_size, contents);
  84     /* Create list2.  */
  85     list2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
  86     for (i = 0; i < initial_size; i++)
  87       gl_list_add_last (list2, contents[i]);
  88
  89     check_equals (list1, list2);
  90
  91     for (repeat = 0; repeat < 10000; repeat++)
  92       {
  93         unsigned int operation = RANDOM (16);
  94         switch (operation)
  95           {
  96           case 0:
  97             if (gl_list_size (list1) > 0)
  98               {
  99                 size_t index = RANDOM (gl_list_size (list1));
 100                 const char *obj = RANDOM_OBJECT ();
 101                 gl_list_node_t node1, node2;
 102
 103                 node1 = gl_list_set_at (list1, index, obj);
 104                 ASSERT (gl_list_get_at (list1, index) == obj);
 105                 ASSERT (gl_list_node_value (list1, node1) == obj);
 106
 107                 node2 = gl_list_set_at (list2, index, obj);
 108                 ASSERT (gl_list_get_at (list2, index) == obj);
 109                 ASSERT (gl_list_node_value (list2, node2) == obj);
 110
 111                 if (index > 0)
 112                   {
 113                     ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 114                             == gl_list_get_at (list1, index - 1));
 115                   }
 116                 if (index + 1 < gl_list_size (list1))
 117                   {
 118                     ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 119                             == gl_list_get_at (list1, index + 1));
 120                   }
 121               }
 122             break;
 123           case 1:
 124             {
 125               const char *obj = RANDOM_OBJECT ();
 126               gl_list_node_t node1, node2;
 127               node1 = gl_list_search (list1, obj);
 128               node2 = gl_list_search (list2, obj);
 129               if (node1 == NULL)
 130                 {
 131                   ASSERT (node2 == NULL);
 132                 }
 133               else
 134                 {
 135                   ASSERT (node2 != NULL);
 136                   ASSERT (gl_list_node_value (list1, node1) == obj);
 137                   ASSERT (gl_list_node_value (list2, node2) == obj);
 138                 }
 139             }
 140             break;
 141           case 2:
 142             {
 143               const char *obj = RANDOM_OBJECT ();
 144               size_t index1, index2;
 145               index1 = gl_list_indexof (list1, obj);
 146               index2 = gl_list_indexof (list2, obj);
 147               if (index1 == (size_t)(-1))
 148                 {
 149                   ASSERT (index2 == (size_t)(-1));
 150                 }
 151               else
 152                 {
 153                   ASSERT (index2 != (size_t)(-1));
 154                   ASSERT (gl_list_get_at (list1, index1) == obj);
 155                   ASSERT (gl_list_get_at (list2, index2) == obj);
 156                   ASSERT (index2 == index1);
 157                 }
 158             }
 159             break;
 160           case 3: /* add 1 element */
 161             {
 162               const char *obj = RANDOM_OBJECT ();
 163               gl_list_node_t node1, node2;
 164               node1 = gl_list_add_first (list1, obj);
 165               node2 = gl_list_add_first (list2, obj);
 166               ASSERT (gl_list_node_value (list1, node1) == obj);
 167               ASSERT (gl_list_node_value (list2, node2) == obj);
 168               ASSERT (gl_list_get_at (list1, 0) == obj);
 169               ASSERT (gl_list_get_at (list2, 0) == obj);
 170             }
 171             break;
 172           case 4: /* add 1 element */
 173             {
 174               const char *obj = RANDOM_OBJECT ();
 175               gl_list_node_t node1, node2;
 176               node1 = gl_list_add_last (list1, obj);
 177               node2 = gl_list_add_last (list2, obj);
 178               ASSERT (gl_list_node_value (list1, node1) == obj);
 179               ASSERT (gl_list_node_value (list2, node2) == obj);
 180               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
 181               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
 182             }
 183             break;
 184           case 5: /* add 3 elements */
 185             {
 186               const char *obj0 = RANDOM_OBJECT ();
 187               const char *obj1 = RANDOM_OBJECT ();
 188               const char *obj2 = RANDOM_OBJECT ();
 189               gl_list_node_t node1, node2;
 190               node1 = gl_list_add_first (list1, obj2);
 191               node1 = gl_list_add_before (list1, node1, obj0);
 192               node1 = gl_list_add_after (list1, node1, obj1);
 193               node2 = gl_list_add_first (list2, obj2);
 194               node2 = gl_list_add_before (list2, node2, obj0);
 195               node2 = gl_list_add_after (list2, node2, obj1);
 196               ASSERT (gl_list_node_value (list1, node1) == obj1);
 197               ASSERT (gl_list_node_value (list2, node2) == obj1);
 198               ASSERT (gl_list_get_at (list1, 0) == obj0);
 199               ASSERT (gl_list_get_at (list1, 1) == obj1);
 200               ASSERT (gl_list_get_at (list1, 2) == obj2);
 201               ASSERT (gl_list_get_at (list2, 0) == obj0);
 202               ASSERT (gl_list_get_at (list2, 1) == obj1);
 203               ASSERT (gl_list_get_at (list2, 2) == obj2);
 204             }
 205             break;
 206           case 6: /* add 1 element */
 207             {
 208               size_t index = RANDOM (gl_list_size (list1) + 1);
 209               const char *obj = RANDOM_OBJECT ();
 210               gl_list_node_t node1, node2;
 211               node1 = gl_list_add_at (list1, index, obj);
 212               node2 = gl_list_add_at (list2, index, obj);
 213               ASSERT (gl_list_get_at (list1, index) == obj);
 214               ASSERT (gl_list_node_value (list1, node1) == obj);
 215               ASSERT (gl_list_get_at (list2, index) == obj);
 216               ASSERT (gl_list_node_value (list2, node2) == obj);
 217               if (index > 0)
 218                 {
 219                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 220                           == gl_list_get_at (list1, index - 1));
 221                 }
 222               if (index + 1 < gl_list_size (list1))
 223                 {
 224                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 225                           == gl_list_get_at (list1, index + 1));
 226                 }
 227             }
 228             break;
 229           case 7: case 8: /* remove 1 element */
 230             if (gl_list_size (list1) > 0)
 231               {
 232                 size_t n = gl_list_size (list1);
 233                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 234                 gl_list_node_t node1, node2;
 235                 node1 = gl_list_search (list1, obj);
 236                 node2 = gl_list_search (list2, obj);
 237                 ASSERT (node1 != NULL);
 238                 ASSERT (node2 != NULL);
 239                 ASSERT (gl_list_remove_node (list1, node1));
 240                 ASSERT (gl_list_remove_node (list2, node2));
 241                 ASSERT (gl_list_size (list1) == n - 1);
 242               }
 243             break;
 244           case 9: case 10: /* remove 1 element */
 245             if (gl_list_size (list1) > 0)
 246               {
 247                 size_t n = gl_list_size (list1);
 248                 size_t index = RANDOM (n);
 249                 ASSERT (gl_list_remove_at (list1, index));
 250                 ASSERT (gl_list_remove_at (list2, index));
 251                 ASSERT (gl_list_size (list1) == n - 1);
 252               }
 253             break;
 254           case 11: case 12: /* remove 1 element */
 255             if (gl_list_size (list1) > 0)
 256               {
 257                 size_t n = gl_list_size (list1);
 258                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 259                 ASSERT (gl_list_remove (list1, obj));
 260                 ASSERT (gl_list_remove (list2, obj));
 261                 ASSERT (gl_list_size (list1) == n - 1);
 262               }
 263             break;
 264           case 13:
 265             if (gl_list_size (list1) > 0)
 266               {
 267                 size_t n = gl_list_size (list1);
 268                 const char *obj = "xyzzy";
 269                 ASSERT (!gl_list_remove (list1, obj));
 270                 ASSERT (!gl_list_remove (list2, obj));
 271                 ASSERT (gl_list_size (list1) == n);
 272               }
 273             break;
 274           case 14:
 275             {
 276               size_t n = gl_list_size (list1);
 277               gl_list_iterator_t iter1, iter2;
 278               const void *elt;
 279               iter1 = gl_list_iterator (list1);
 280               iter2 = gl_list_iterator (list2);
 281               for (i = 0; i < n; i++)
 282                 {
 283                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 284                   ASSERT (gl_list_get_at (list1, i) == elt);
 285                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 286                   ASSERT (gl_list_get_at (list2, i) == elt);
 287                 }
 288               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 289               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 290               gl_list_iterator_free (&iter1);
 291               gl_list_iterator_free (&iter2);
 292             }
 293             break;
 294           case 15:
 295             {
 296               size_t end = RANDOM (gl_list_size (list1) + 1);
 297               size_t start = RANDOM (end + 1);
 298               gl_list_iterator_t iter1, iter2;
 299               const void *elt;
 300               iter1 = gl_list_iterator_from_to (list1, start, end);
 301               iter2 = gl_list_iterator_from_to (list2, start, end);
 302               for (i = start; i < end; i++)
 303                 {
 304                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 305                   ASSERT (gl_list_get_at (list1, i) == elt);
 306                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 307                   ASSERT (gl_list_get_at (list2, i) == elt);
 308                 }
 309               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 310               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 311               gl_list_iterator_free (&iter1);
 312               gl_list_iterator_free (&iter2);
 313             }
 314             break;
 315           }
 316         check_equals (list1, list2);
 317       }
 318
 319     gl_list_free (list1);
 320     gl_list_free (list2);
 321     free (contents);
 322   }
 323
 324   return 0;
 325 }