tests/test-array_list.c

   1 /* Test of sequential list data type implementation.
   2    Copyright (C) 2006-2021 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 <https://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include "gl_array_list.h"
  21
  22 #include <stdlib.h>
  23
  24 #include "macros.h"
  25
  26 static const char *objects[15] =
  27   {
  28     "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
  29   };
  30
  31 #define RANDOM(n) (rand () % (n))
  32 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
  33
  34 static void
  35 check_equals (gl_list_t list1, gl_list_t list2)
  36 {
  37   size_t n, i;
  38
  39   n = gl_list_size (list1);
  40   ASSERT (n == gl_list_size (list2));
  41   for (i = 0; i < n; i++)
  42     {
  43       ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
  44     }
  45 }
  46
  47 static void
  48 check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
  49 {
  50   size_t n = gl_list_size (list1);
  51   size_t i;
  52   gl_list_node_t node2;
  53
  54   i = 0;
  55   node2 = gl_list_first_node (list2);
  56   while (i < n && node2 != NULL)
  57     {
  58       ASSERT (gl_list_get_at (list1, i) == gl_list_node_value (list2, node2));
  59       i++;
  60       node2 = gl_list_next_node (list2, node2);
  61     }
  62   ASSERT ((i == n) == (node2 == NULL));
  63 }
  64
  65 static void
  66 check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
  67 {
  68   size_t n = gl_list_size (list1);
  69   size_t i;
  70   gl_list_node_t node2;
  71
  72   i = n - 1;
  73   node2 = gl_list_last_node (list2);
  74   while (i != (size_t)(-1) && node2 != NULL)
  75     {
  76       ASSERT (gl_list_get_at (list1, i) == gl_list_node_value (list2, node2));
  77       i--;
  78       node2 = gl_list_previous_node (list2, node2);
  79     }
  80   ASSERT ((i == (size_t)(-1)) == (node2 == NULL));
  81 }
  82
  83 int
  84 main (int argc, char *argv[])
  85 {
  86   gl_list_t list1, list2;
  87
  88   /* Allow the user to provide a non-default random seed on the command line.  */
  89   if (argc > 1)
  90     srand (atoi (argv[1]));
  91
  92   {
  93     size_t initial_size = RANDOM (50);
  94     const void **contents =
  95       (const void **) malloc (initial_size * sizeof (const void *));
  96     size_t i;
  97     unsigned int repeat;
  98
  99     for (i = 0; i < initial_size; i++)
 100       contents[i] = RANDOM_OBJECT ();
 101
 102     /* Create list1.  */
 103     list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
 104                                initial_size, contents);
 105     ASSERT (list1 != NULL);
 106     /* Create list2.  */
 107     list2 = gl_list_nx_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
 108     ASSERT (list2 != NULL);
 109     for (i = 0; i < initial_size; i++)
 110       ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
 111
 112     check_equals (list1, list2);
 113
 114     check_equals_by_forward_iteration (list1, list2);
 115     check_equals_by_backward_iteration (list1, list2);
 116
 117     for (repeat = 0; repeat < 10000; repeat++)
 118       {
 119         unsigned int operation = RANDOM (18);
 120         switch (operation)
 121           {
 122           case 0:
 123             if (gl_list_size (list1) > 0)
 124               {
 125                 size_t index = RANDOM (gl_list_size (list1));
 126                 const char *obj = RANDOM_OBJECT ();
 127                 gl_list_node_t node1, node2;
 128
 129                 node1 = gl_list_nx_set_at (list1, index, obj);
 130                 ASSERT (node1 != NULL);
 131                 ASSERT (gl_list_get_at (list1, index) == obj);
 132                 ASSERT (gl_list_node_value (list1, node1) == obj);
 133
 134                 node2 = gl_list_nx_set_at (list2, index, obj);
 135                 ASSERT (node2 != NULL);
 136                 ASSERT (gl_list_get_at (list2, index) == obj);
 137                 ASSERT (gl_list_node_value (list2, node2) == obj);
 138
 139                 if (index > 0)
 140                   {
 141                     ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 142                             == gl_list_get_at (list1, index - 1));
 143                   }
 144                 if (index + 1 < gl_list_size (list1))
 145                   {
 146                     ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 147                             == gl_list_get_at (list1, index + 1));
 148                   }
 149               }
 150             break;
 151           case 1:
 152             {
 153               const char *obj = RANDOM_OBJECT ();
 154               gl_list_node_t node1, node2;
 155               node1 = gl_list_search (list1, obj);
 156               node2 = gl_list_search (list2, obj);
 157               if (node1 == NULL)
 158                 {
 159                   ASSERT (node2 == NULL);
 160                 }
 161               else
 162                 {
 163                   ASSERT (node2 != NULL);
 164                   ASSERT (gl_list_node_value (list1, node1) == obj);
 165                   ASSERT (gl_list_node_value (list2, node2) == obj);
 166                 }
 167             }
 168             break;
 169           case 2:
 170             {
 171               const char *obj = RANDOM_OBJECT ();
 172               size_t index1, index2;
 173               index1 = gl_list_indexof (list1, obj);
 174               index2 = gl_list_indexof (list2, obj);
 175               if (index1 == (size_t)(-1))
 176                 {
 177                   ASSERT (index2 == (size_t)(-1));
 178                 }
 179               else
 180                 {
 181                   ASSERT (index2 != (size_t)(-1));
 182                   ASSERT (gl_list_get_at (list1, index1) == obj);
 183                   ASSERT (gl_list_get_at (list2, index2) == obj);
 184                   ASSERT (index2 == index1);
 185                 }
 186             }
 187             break;
 188           case 3: /* add 1 element */
 189             {
 190               const char *obj = RANDOM_OBJECT ();
 191               gl_list_node_t node1, node2;
 192               node1 = gl_list_nx_add_first (list1, obj);
 193               ASSERT (node1 != NULL);
 194               node2 = gl_list_nx_add_first (list2, obj);
 195               ASSERT (node2 != NULL);
 196               ASSERT (gl_list_node_value (list1, node1) == obj);
 197               ASSERT (gl_list_node_value (list2, node2) == obj);
 198               ASSERT (gl_list_get_at (list1, 0) == obj);
 199               ASSERT (gl_list_get_at (list2, 0) == obj);
 200             }
 201             break;
 202           case 4: /* add 1 element */
 203             {
 204               const char *obj = RANDOM_OBJECT ();
 205               gl_list_node_t node1, node2;
 206               node1 = gl_list_nx_add_last (list1, obj);
 207               ASSERT (node1 != NULL);
 208               node2 = gl_list_nx_add_last (list2, obj);
 209               ASSERT (node2 != NULL);
 210               ASSERT (gl_list_node_value (list1, node1) == obj);
 211               ASSERT (gl_list_node_value (list2, node2) == obj);
 212               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
 213               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
 214             }
 215             break;
 216           case 5: /* add 3 elements */
 217             {
 218               const char *obj0 = RANDOM_OBJECT ();
 219               const char *obj1 = RANDOM_OBJECT ();
 220               const char *obj2 = RANDOM_OBJECT ();
 221               gl_list_node_t node1, node2;
 222               node1 = gl_list_nx_add_first (list1, obj2);
 223               ASSERT (node1 != NULL);
 224               node1 = gl_list_nx_add_before (list1, node1, obj0);
 225               ASSERT (node1 != NULL);
 226               node1 = gl_list_nx_add_after (list1, node1, obj1);
 227               ASSERT (node1 != NULL);
 228               node2 = gl_list_nx_add_first (list2, obj2);
 229               ASSERT (node2 != NULL);
 230               node2 = gl_list_nx_add_before (list2, node2, obj0);
 231               ASSERT (node2 != NULL);
 232               node2 = gl_list_nx_add_after (list2, node2, obj1);
 233               ASSERT (node2 != NULL);
 234               ASSERT (gl_list_node_value (list1, node1) == obj1);
 235               ASSERT (gl_list_node_value (list2, node2) == obj1);
 236               ASSERT (gl_list_get_at (list1, 0) == obj0);
 237               ASSERT (gl_list_get_at (list1, 1) == obj1);
 238               ASSERT (gl_list_get_at (list1, 2) == obj2);
 239               ASSERT (gl_list_get_at (list2, 0) == obj0);
 240               ASSERT (gl_list_get_at (list2, 1) == obj1);
 241               ASSERT (gl_list_get_at (list2, 2) == obj2);
 242             }
 243             break;
 244           case 6: /* add 1 element */
 245             {
 246               size_t index = RANDOM (gl_list_size (list1) + 1);
 247               const char *obj = RANDOM_OBJECT ();
 248               gl_list_node_t node1, node2;
 249               node1 = gl_list_nx_add_at (list1, index, obj);
 250               ASSERT (node1 != NULL);
 251               node2 = gl_list_nx_add_at (list2, index, obj);
 252               ASSERT (node2 != NULL);
 253               ASSERT (gl_list_get_at (list1, index) == obj);
 254               ASSERT (gl_list_node_value (list1, node1) == obj);
 255               ASSERT (gl_list_get_at (list2, index) == obj);
 256               ASSERT (gl_list_node_value (list2, node2) == obj);
 257               if (index > 0)
 258                 {
 259                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 260                           == gl_list_get_at (list1, index - 1));
 261                 }
 262               if (index + 1 < gl_list_size (list1))
 263                 {
 264                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 265                           == gl_list_get_at (list1, index + 1));
 266                 }
 267             }
 268             break;
 269           case 7: case 8: /* remove 1 element */
 270             if (gl_list_size (list1) > 0)
 271               {
 272                 size_t n = gl_list_size (list1);
 273                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 274                 gl_list_node_t node1, node2;
 275                 node1 = gl_list_search (list1, obj);
 276                 node2 = gl_list_search (list2, obj);
 277                 ASSERT (node1 != NULL);
 278                 ASSERT (node2 != NULL);
 279                 ASSERT (gl_list_remove_node (list1, node1));
 280                 ASSERT (gl_list_remove_node (list2, node2));
 281                 ASSERT (gl_list_size (list1) == n - 1);
 282               }
 283             break;
 284           case 9: case 10: /* remove 1 element */
 285             if (gl_list_size (list1) > 0)
 286               {
 287                 size_t n = gl_list_size (list1);
 288                 size_t index = RANDOM (n);
 289                 ASSERT (gl_list_remove_at (list1, index));
 290                 ASSERT (gl_list_remove_at (list2, index));
 291                 ASSERT (gl_list_size (list1) == n - 1);
 292               }
 293             break;
 294           case 11: /* remove first element */
 295             {
 296               size_t n = gl_list_size (list1);
 297               bool removed1 = gl_list_remove_first (list1);
 298               ASSERT (gl_list_remove_first (list2) == removed1);
 299               ASSERT (gl_list_size (list1) == n - (int) removed1);
 300             }
 301             break;
 302           case 12: /* remove last element */
 303             {
 304               size_t n = gl_list_size (list1);
 305               bool removed1 = gl_list_remove_last (list1);
 306               ASSERT (gl_list_remove_last (list2) == removed1);
 307               ASSERT (gl_list_size (list1) == n - (int) removed1);
 308             }
 309             break;
 310           case 13: case 14: /* remove 1 element */
 311             if (gl_list_size (list1) > 0)
 312               {
 313                 size_t n = gl_list_size (list1);
 314                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 315                 ASSERT (gl_list_remove (list1, obj));
 316                 ASSERT (gl_list_remove (list2, obj));
 317                 ASSERT (gl_list_size (list1) == n - 1);
 318               }
 319             break;
 320           case 15:
 321             if (gl_list_size (list1) > 0)
 322               {
 323                 size_t n = gl_list_size (list1);
 324                 const char *obj = "xyzzy";
 325                 ASSERT (!gl_list_remove (list1, obj));
 326                 ASSERT (!gl_list_remove (list2, obj));
 327                 ASSERT (gl_list_size (list1) == n);
 328               }
 329             break;
 330           case 16:
 331             {
 332               size_t n = gl_list_size (list1);
 333               gl_list_iterator_t iter1, iter2;
 334               const void *elt;
 335               iter1 = gl_list_iterator (list1);
 336               iter2 = gl_list_iterator (list2);
 337               for (i = 0; i < n; i++)
 338                 {
 339                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 340                   ASSERT (gl_list_get_at (list1, i) == elt);
 341                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 342                   ASSERT (gl_list_get_at (list2, i) == elt);
 343                 }
 344               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 345               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 346               gl_list_iterator_free (&iter1);
 347               gl_list_iterator_free (&iter2);
 348             }
 349             break;
 350           case 17:
 351             {
 352               size_t end = RANDOM (gl_list_size (list1) + 1);
 353               size_t start = RANDOM (end + 1);
 354               gl_list_iterator_t iter1, iter2;
 355               const void *elt;
 356               iter1 = gl_list_iterator_from_to (list1, start, end);
 357               iter2 = gl_list_iterator_from_to (list2, start, end);
 358               for (i = start; i < end; i++)
 359                 {
 360                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 361                   ASSERT (gl_list_get_at (list1, i) == elt);
 362                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 363                   ASSERT (gl_list_get_at (list2, i) == elt);
 364                 }
 365               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 366               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 367               gl_list_iterator_free (&iter1);
 368               gl_list_iterator_free (&iter2);
 369             }
 370             break;
 371           }
 372         check_equals (list1, list2);
 373       }
 374
 375     gl_list_free (list1);
 376     gl_list_free (list2);
 377     free (contents);
 378   }
 379
 380   return 0;
 381 }