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 #ifdef HAVE_CONFIG_H
  20 # include <config.h>
  21 #endif
  22
  23 #include "gl_array_list.h"
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27
  28 #include "progname.h"
  29
  30 static const char *objects[15] =
  31   {
  32     "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
  33   };
  34
  35 #define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
  36 #define ASSERT(expr) \
  37   do                                                                         \
  38     {                                                                        \
  39       if (!(expr))                                                           \
  40         {                                                                    \
  41           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  42           abort ();                                                          \
  43         }                                                                    \
  44     }                                                                        \
  45   while (0)
  46 #define RANDOM(n) (rand () % (n))
  47 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
  48
  49 static void
  50 check_equals (gl_list_t list1, gl_list_t list2)
  51 {
  52   size_t n, i;
  53
  54   n = gl_list_size (list1);
  55   ASSERT (n == gl_list_size (list2));
  56   for (i = 0; i < n; i++)
  57     {
  58       ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
  59     }
  60 }
  61
  62 int
  63 main (int argc, char *argv[])
  64 {
  65   gl_list_t list1, list2;
  66
  67   set_program_name (argv[0]);
  68
  69   /* Allow the user to provide a non-default random seed on the command line.  */
  70   if (argc > 1)
  71     srand (atoi (argv[1]));
  72
  73   {
  74     size_t initial_size = RANDOM (50);
  75     const void **contents =
  76       (const void **) malloc (initial_size * sizeof (const void *));
  77     size_t i;
  78     unsigned int repeat;
  79
  80     for (i = 0; i < initial_size; i++)
  81       contents[i] = RANDOM_OBJECT ();
  82
  83     /* Create list1.  */
  84     list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
  85                             initial_size, contents);
  86     /* Create list2.  */
  87     list2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
  88     for (i = 0; i < initial_size; i++)
  89       gl_list_add_last (list2, contents[i]);
  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_set_at (list1, index, obj);
 106                 ASSERT (gl_list_get_at (list1, index) == obj);
 107                 ASSERT (gl_list_node_value (list1, node1) == obj);
 108
 109                 node2 = gl_list_set_at (list2, index, obj);
 110                 ASSERT (gl_list_get_at (list2, index) == obj);
 111                 ASSERT (gl_list_node_value (list2, node2) == obj);
 112
 113                 if (index > 0)
 114                   {
 115                     ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 116                             == gl_list_get_at (list1, index - 1));
 117                   }
 118                 if (index + 1 < gl_list_size (list1))
 119                   {
 120                     ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 121                             == gl_list_get_at (list1, index + 1));
 122                   }
 123               }
 124             break;
 125           case 1:
 126             {
 127               const char *obj = RANDOM_OBJECT ();
 128               gl_list_node_t node1, node2;
 129               node1 = gl_list_search (list1, obj);
 130               node2 = gl_list_search (list2, obj);
 131               if (node1 == NULL)
 132                 {
 133                   ASSERT (node2 == NULL);
 134                 }
 135               else
 136                 {
 137                   ASSERT (node2 != NULL);
 138                   ASSERT (gl_list_node_value (list1, node1) == obj);
 139                   ASSERT (gl_list_node_value (list2, node2) == obj);
 140                 }
 141             }
 142             break;
 143           case 2:
 144             {
 145               const char *obj = RANDOM_OBJECT ();
 146               size_t index1, index2;
 147               index1 = gl_list_indexof (list1, obj);
 148               index2 = gl_list_indexof (list2, obj);
 149               if (index1 == (size_t)(-1))
 150                 {
 151                   ASSERT (index2 == (size_t)(-1));
 152                 }
 153               else
 154                 {
 155                   ASSERT (index2 != (size_t)(-1));
 156                   ASSERT (gl_list_get_at (list1, index1) == obj);
 157                   ASSERT (gl_list_get_at (list2, index2) == obj);
 158                   ASSERT (index2 == index1);
 159                 }
 160             }
 161             break;
 162           case 3: /* add 1 element */
 163             {
 164               const char *obj = RANDOM_OBJECT ();
 165               gl_list_node_t node1, node2;
 166               node1 = gl_list_add_first (list1, obj);
 167               node2 = gl_list_add_first (list2, obj);
 168               ASSERT (gl_list_node_value (list1, node1) == obj);
 169               ASSERT (gl_list_node_value (list2, node2) == obj);
 170               ASSERT (gl_list_get_at (list1, 0) == obj);
 171               ASSERT (gl_list_get_at (list2, 0) == obj);
 172             }
 173             break;
 174           case 4: /* add 1 element */
 175             {
 176               const char *obj = RANDOM_OBJECT ();
 177               gl_list_node_t node1, node2;
 178               node1 = gl_list_add_last (list1, obj);
 179               node2 = gl_list_add_last (list2, obj);
 180               ASSERT (gl_list_node_value (list1, node1) == obj);
 181               ASSERT (gl_list_node_value (list2, node2) == obj);
 182               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
 183               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
 184             }
 185             break;
 186           case 5: /* add 3 elements */
 187             {
 188               const char *obj0 = RANDOM_OBJECT ();
 189               const char *obj1 = RANDOM_OBJECT ();
 190               const char *obj2 = RANDOM_OBJECT ();
 191               gl_list_node_t node1, node2;
 192               node1 = gl_list_add_first (list1, obj2);
 193               node1 = gl_list_add_before (list1, node1, obj0);
 194               node1 = gl_list_add_after (list1, node1, obj1);
 195               node2 = gl_list_add_first (list2, obj2);
 196               node2 = gl_list_add_before (list2, node2, obj0);
 197               node2 = gl_list_add_after (list2, node2, obj1);
 198               ASSERT (gl_list_node_value (list1, node1) == obj1);
 199               ASSERT (gl_list_node_value (list2, node2) == obj1);
 200               ASSERT (gl_list_get_at (list1, 0) == obj0);
 201               ASSERT (gl_list_get_at (list1, 1) == obj1);
 202               ASSERT (gl_list_get_at (list1, 2) == obj2);
 203               ASSERT (gl_list_get_at (list2, 0) == obj0);
 204               ASSERT (gl_list_get_at (list2, 1) == obj1);
 205               ASSERT (gl_list_get_at (list2, 2) == obj2);
 206             }
 207             break;
 208           case 6: /* add 1 element */
 209             {
 210               size_t index = RANDOM (gl_list_size (list1) + 1);
 211               const char *obj = RANDOM_OBJECT ();
 212               gl_list_node_t node1, node2;
 213               node1 = gl_list_add_at (list1, index, obj);
 214               node2 = gl_list_add_at (list2, index, obj);
 215               ASSERT (gl_list_get_at (list1, index) == obj);
 216               ASSERT (gl_list_node_value (list1, node1) == obj);
 217               ASSERT (gl_list_get_at (list2, index) == obj);
 218               ASSERT (gl_list_node_value (list2, node2) == obj);
 219               if (index > 0)
 220                 {
 221                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 222                           == gl_list_get_at (list1, index - 1));
 223                 }
 224               if (index + 1 < gl_list_size (list1))
 225                 {
 226                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 227                           == gl_list_get_at (list1, index + 1));
 228                 }
 229             }
 230             break;
 231           case 7: case 8: /* remove 1 element */
 232             if (gl_list_size (list1) > 0)
 233               {
 234                 size_t n = gl_list_size (list1);
 235                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 236                 gl_list_node_t node1, node2;
 237                 node1 = gl_list_search (list1, obj);
 238                 node2 = gl_list_search (list2, obj);
 239                 ASSERT (node1 != NULL);
 240                 ASSERT (node2 != NULL);
 241                 ASSERT (gl_list_remove_node (list1, node1));
 242                 ASSERT (gl_list_remove_node (list2, node2));
 243                 ASSERT (gl_list_size (list1) == n - 1);
 244               }
 245             break;
 246           case 9: case 10: /* remove 1 element */
 247             if (gl_list_size (list1) > 0)
 248               {
 249                 size_t n = gl_list_size (list1);
 250                 size_t index = RANDOM (n);
 251                 ASSERT (gl_list_remove_at (list1, index));
 252                 ASSERT (gl_list_remove_at (list2, index));
 253                 ASSERT (gl_list_size (list1) == n - 1);
 254               }
 255             break;
 256           case 11: case 12: /* remove 1 element */
 257             if (gl_list_size (list1) > 0)
 258               {
 259                 size_t n = gl_list_size (list1);
 260                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 261                 ASSERT (gl_list_remove (list1, obj));
 262                 ASSERT (gl_list_remove (list2, obj));
 263                 ASSERT (gl_list_size (list1) == n - 1);
 264               }
 265             break;
 266           case 13:
 267             if (gl_list_size (list1) > 0)
 268               {
 269                 size_t n = gl_list_size (list1);
 270                 const char *obj = "xyzzy";
 271                 ASSERT (!gl_list_remove (list1, obj));
 272                 ASSERT (!gl_list_remove (list2, obj));
 273                 ASSERT (gl_list_size (list1) == n);
 274               }
 275             break;
 276           case 14:
 277             {
 278               size_t n = gl_list_size (list1);
 279               gl_list_iterator_t iter1, iter2;
 280               const void *elt;
 281               iter1 = gl_list_iterator (list1);
 282               iter2 = gl_list_iterator (list2);
 283               for (i = 0; i < n; i++)
 284                 {
 285                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 286                   ASSERT (gl_list_get_at (list1, i) == elt);
 287                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 288                   ASSERT (gl_list_get_at (list2, i) == elt);
 289                 }
 290               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 291               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 292               gl_list_iterator_free (&iter1);
 293               gl_list_iterator_free (&iter2);
 294             }
 295             break;
 296           case 15:
 297             {
 298               size_t end = RANDOM (gl_list_size (list1) + 1);
 299               size_t start = RANDOM (end + 1);
 300               gl_list_iterator_t iter1, iter2;
 301               const void *elt;
 302               iter1 = gl_list_iterator_from_to (list1, start, end);
 303               iter2 = gl_list_iterator_from_to (list2, start, end);
 304               for (i = start; i < end; i++)
 305                 {
 306                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 307                   ASSERT (gl_list_get_at (list1, i) == elt);
 308                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 309                   ASSERT (gl_list_get_at (list2, i) == elt);
 310                 }
 311               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 312               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 313               gl_list_iterator_free (&iter1);
 314               gl_list_iterator_free (&iter2);
 315             }
 316             break;
 317           }
 318         check_equals (list1, list2);
 319       }
 320
 321     gl_list_free (list1);
 322     gl_list_free (list2);
 323     free (contents);
 324   }
 325
 326   return 0;
 327 }