tests/test-array_list.c

   1 /* Test of sequential list data type implementation.
   2    Copyright (C) 2006-2014 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 <stdlib.h>
  23
  24 #include "progname.h"
  25 #include "macros.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 RANDOM(n) (rand () % (n))
  33 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
  34
  35 static void
  36 check_equals (gl_list_t list1, gl_list_t list2)
  37 {
  38   size_t n, i;
  39
  40   n = gl_list_size (list1);
  41   ASSERT (n == gl_list_size (list2));
  42   for (i = 0; i < n; i++)
  43     {
  44       ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
  45     }
  46 }
  47
  48 int
  49 main (int argc, char *argv[])
  50 {
  51   gl_list_t list1, list2;
  52
  53   set_program_name (argv[0]);
  54
  55   /* Allow the user to provide a non-default random seed on the command line.  */
  56   if (argc > 1)
  57     srand (atoi (argv[1]));
  58
  59   {
  60     size_t initial_size = RANDOM (50);
  61     const void **contents =
  62       (const void **) malloc (initial_size * sizeof (const void *));
  63     size_t i;
  64     unsigned int repeat;
  65
  66     for (i = 0; i < initial_size; i++)
  67       contents[i] = RANDOM_OBJECT ();
  68
  69     /* Create list1.  */
  70     list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
  71                                initial_size, contents);
  72     ASSERT (list1 != NULL);
  73     /* Create list2.  */
  74     list2 = gl_list_nx_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
  75     ASSERT (list2 != NULL);
  76     for (i = 0; i < initial_size; i++)
  77       ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
  78
  79     check_equals (list1, list2);
  80
  81     for (repeat = 0; repeat < 10000; repeat++)
  82       {
  83         unsigned int operation = RANDOM (16);
  84         switch (operation)
  85           {
  86           case 0:
  87             if (gl_list_size (list1) > 0)
  88               {
  89                 size_t index = RANDOM (gl_list_size (list1));
  90                 const char *obj = RANDOM_OBJECT ();
  91                 gl_list_node_t node1, node2;
  92
  93                 node1 = gl_list_nx_set_at (list1, index, obj);
  94                 ASSERT (node1 != NULL);
  95                 ASSERT (gl_list_get_at (list1, index) == obj);
  96                 ASSERT (gl_list_node_value (list1, node1) == obj);
  97
  98                 node2 = gl_list_nx_set_at (list2, index, obj);
  99                 ASSERT (node2 != NULL);
 100                 ASSERT (gl_list_get_at (list2, index) == obj);
 101                 ASSERT (gl_list_node_value (list2, node2) == obj);
 102
 103                 if (index > 0)
 104                   {
 105                     ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 106                             == gl_list_get_at (list1, index - 1));
 107                   }
 108                 if (index + 1 < gl_list_size (list1))
 109                   {
 110                     ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 111                             == gl_list_get_at (list1, index + 1));
 112                   }
 113               }
 114             break;
 115           case 1:
 116             {
 117               const char *obj = RANDOM_OBJECT ();
 118               gl_list_node_t node1, node2;
 119               node1 = gl_list_search (list1, obj);
 120               node2 = gl_list_search (list2, obj);
 121               if (node1 == NULL)
 122                 {
 123                   ASSERT (node2 == NULL);
 124                 }
 125               else
 126                 {
 127                   ASSERT (node2 != NULL);
 128                   ASSERT (gl_list_node_value (list1, node1) == obj);
 129                   ASSERT (gl_list_node_value (list2, node2) == obj);
 130                 }
 131             }
 132             break;
 133           case 2:
 134             {
 135               const char *obj = RANDOM_OBJECT ();
 136               size_t index1, index2;
 137               index1 = gl_list_indexof (list1, obj);
 138               index2 = gl_list_indexof (list2, obj);
 139               if (index1 == (size_t)(-1))
 140                 {
 141                   ASSERT (index2 == (size_t)(-1));
 142                 }
 143               else
 144                 {
 145                   ASSERT (index2 != (size_t)(-1));
 146                   ASSERT (gl_list_get_at (list1, index1) == obj);
 147                   ASSERT (gl_list_get_at (list2, index2) == obj);
 148                   ASSERT (index2 == index1);
 149                 }
 150             }
 151             break;
 152           case 3: /* add 1 element */
 153             {
 154               const char *obj = RANDOM_OBJECT ();
 155               gl_list_node_t node1, node2;
 156               node1 = gl_list_nx_add_first (list1, obj);
 157               ASSERT (node1 != NULL);
 158               node2 = gl_list_nx_add_first (list2, obj);
 159               ASSERT (node2 != NULL);
 160               ASSERT (gl_list_node_value (list1, node1) == obj);
 161               ASSERT (gl_list_node_value (list2, node2) == obj);
 162               ASSERT (gl_list_get_at (list1, 0) == obj);
 163               ASSERT (gl_list_get_at (list2, 0) == obj);
 164             }
 165             break;
 166           case 4: /* add 1 element */
 167             {
 168               const char *obj = RANDOM_OBJECT ();
 169               gl_list_node_t node1, node2;
 170               node1 = gl_list_nx_add_last (list1, obj);
 171               ASSERT (node1 != NULL);
 172               node2 = gl_list_nx_add_last (list2, obj);
 173               ASSERT (node2 != NULL);
 174               ASSERT (gl_list_node_value (list1, node1) == obj);
 175               ASSERT (gl_list_node_value (list2, node2) == obj);
 176               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
 177               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
 178             }
 179             break;
 180           case 5: /* add 3 elements */
 181             {
 182               const char *obj0 = RANDOM_OBJECT ();
 183               const char *obj1 = RANDOM_OBJECT ();
 184               const char *obj2 = RANDOM_OBJECT ();
 185               gl_list_node_t node1, node2;
 186               node1 = gl_list_nx_add_first (list1, obj2);
 187               ASSERT (node1 != NULL);
 188               node1 = gl_list_nx_add_before (list1, node1, obj0);
 189               ASSERT (node1 != NULL);
 190               node1 = gl_list_nx_add_after (list1, node1, obj1);
 191               ASSERT (node1 != NULL);
 192               node2 = gl_list_nx_add_first (list2, obj2);
 193               ASSERT (node2 != NULL);
 194               node2 = gl_list_nx_add_before (list2, node2, obj0);
 195               ASSERT (node2 != NULL);
 196               node2 = gl_list_nx_add_after (list2, node2, obj1);
 197               ASSERT (node2 != NULL);
 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_nx_add_at (list1, index, obj);
 214               ASSERT (node1 != NULL);
 215               node2 = gl_list_nx_add_at (list2, index, obj);
 216               ASSERT (node2 != NULL);
 217               ASSERT (gl_list_get_at (list1, index) == obj);
 218               ASSERT (gl_list_node_value (list1, node1) == obj);
 219               ASSERT (gl_list_get_at (list2, index) == obj);
 220               ASSERT (gl_list_node_value (list2, node2) == obj);
 221               if (index > 0)
 222                 {
 223                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 224                           == gl_list_get_at (list1, index - 1));
 225                 }
 226               if (index + 1 < gl_list_size (list1))
 227                 {
 228                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 229                           == gl_list_get_at (list1, index + 1));
 230                 }
 231             }
 232             break;
 233           case 7: case 8: /* remove 1 element */
 234             if (gl_list_size (list1) > 0)
 235               {
 236                 size_t n = gl_list_size (list1);
 237                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 238                 gl_list_node_t node1, node2;
 239                 node1 = gl_list_search (list1, obj);
 240                 node2 = gl_list_search (list2, obj);
 241                 ASSERT (node1 != NULL);
 242                 ASSERT (node2 != NULL);
 243                 ASSERT (gl_list_remove_node (list1, node1));
 244                 ASSERT (gl_list_remove_node (list2, node2));
 245                 ASSERT (gl_list_size (list1) == n - 1);
 246               }
 247             break;
 248           case 9: case 10: /* remove 1 element */
 249             if (gl_list_size (list1) > 0)
 250               {
 251                 size_t n = gl_list_size (list1);
 252                 size_t index = RANDOM (n);
 253                 ASSERT (gl_list_remove_at (list1, index));
 254                 ASSERT (gl_list_remove_at (list2, index));
 255                 ASSERT (gl_list_size (list1) == n - 1);
 256               }
 257             break;
 258           case 11: case 12: /* remove 1 element */
 259             if (gl_list_size (list1) > 0)
 260               {
 261                 size_t n = gl_list_size (list1);
 262                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 263                 ASSERT (gl_list_remove (list1, obj));
 264                 ASSERT (gl_list_remove (list2, obj));
 265                 ASSERT (gl_list_size (list1) == n - 1);
 266               }
 267             break;
 268           case 13:
 269             if (gl_list_size (list1) > 0)
 270               {
 271                 size_t n = gl_list_size (list1);
 272                 const char *obj = "xyzzy";
 273                 ASSERT (!gl_list_remove (list1, obj));
 274                 ASSERT (!gl_list_remove (list2, obj));
 275                 ASSERT (gl_list_size (list1) == n);
 276               }
 277             break;
 278           case 14:
 279             {
 280               size_t n = gl_list_size (list1);
 281               gl_list_iterator_t iter1, iter2;
 282               const void *elt;
 283               iter1 = gl_list_iterator (list1);
 284               iter2 = gl_list_iterator (list2);
 285               for (i = 0; i < n; i++)
 286                 {
 287                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 288                   ASSERT (gl_list_get_at (list1, i) == elt);
 289                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 290                   ASSERT (gl_list_get_at (list2, i) == elt);
 291                 }
 292               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 293               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 294               gl_list_iterator_free (&iter1);
 295               gl_list_iterator_free (&iter2);
 296             }
 297             break;
 298           case 15:
 299             {
 300               size_t end = RANDOM (gl_list_size (list1) + 1);
 301               size_t start = RANDOM (end + 1);
 302               gl_list_iterator_t iter1, iter2;
 303               const void *elt;
 304               iter1 = gl_list_iterator_from_to (list1, start, end);
 305               iter2 = gl_list_iterator_from_to (list2, start, end);
 306               for (i = start; i < end; i++)
 307                 {
 308                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 309                   ASSERT (gl_list_get_at (list1, i) == elt);
 310                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 311                   ASSERT (gl_list_get_at (list2, i) == elt);
 312                 }
 313               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 314               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 315               gl_list_iterator_free (&iter1);
 316               gl_list_iterator_free (&iter2);
 317             }
 318             break;
 319           }
 320         check_equals (list1, list2);
 321       }
 322
 323     gl_list_free (list1);
 324     gl_list_free (list2);
 325     free (contents);
 326   }
 327
 328   return 0;
 329 }