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 <stdlib.h>
  26
  27 #include "progname.h"
  28
  29 static const char *objects[15] =
  30   {
  31     "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
  32   };
  33
  34 #define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
  35 #define ASSERT(condition) if (!(condition)) abort ()
  36 #define RANDOM(n) (rand () % (n))
  37 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
  38
  39 static void
  40 check_equals (gl_list_t list1, gl_list_t list2)
  41 {
  42   size_t n, i;
  43
  44   n = gl_list_size (list1);
  45   ASSERT (n == gl_list_size (list2));
  46   for (i = 0; i < n; i++)
  47     {
  48       ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
  49     }
  50 }
  51
  52 int
  53 main (int argc, char *argv[])
  54 {
  55   gl_list_t list1, list2;
  56
  57   set_program_name (argv[0]);
  58
  59   /* Allow the user to provide a non-default random seed on the command line.  */
  60   if (argc > 1)
  61     srand (atoi (argv[1]));
  62
  63   {
  64     size_t initial_size = RANDOM (50);
  65     const void **contents =
  66       (const void **) malloc (initial_size * sizeof (const void *));
  67     size_t i;
  68     unsigned int repeat;
  69
  70     for (i = 0; i < initial_size; i++)
  71       contents[i] = RANDOM_OBJECT ();
  72
  73     /* Create list1.  */
  74     list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, true,
  75                             initial_size, contents);
  76     /* Create list2.  */
  77     list2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, true);
  78     for (i = 0; i < initial_size; i++)
  79       gl_list_add_last (list2, contents[i]);
  80
  81     check_equals (list1, list2);
  82
  83     for (repeat = 0; repeat < 10000; repeat++)
  84       {
  85         unsigned int operation = RANDOM (16);
  86         switch (operation)
  87           {
  88           case 0:
  89             if (gl_list_size (list1) > 0)
  90               {
  91                 size_t index = RANDOM (gl_list_size (list1));
  92                 const char *obj = RANDOM_OBJECT ();
  93                 gl_list_node_t node1, node2;
  94
  95                 node1 = gl_list_set_at (list1, index, obj);
  96                 ASSERT (gl_list_get_at (list1, index) == obj);
  97                 ASSERT (gl_list_node_value (list1, node1) == obj);
  98
  99                 node2 = gl_list_set_at (list2, index, obj);
 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_add_first (list1, obj);
 157               node2 = gl_list_add_first (list2, obj);
 158               ASSERT (gl_list_node_value (list1, node1) == obj);
 159               ASSERT (gl_list_node_value (list2, node2) == obj);
 160               ASSERT (gl_list_get_at (list1, 0) == obj);
 161               ASSERT (gl_list_get_at (list2, 0) == obj);
 162             }
 163             break;
 164           case 4: /* add 1 element */
 165             {
 166               const char *obj = RANDOM_OBJECT ();
 167               gl_list_node_t node1, node2;
 168               node1 = gl_list_add_last (list1, obj);
 169               node2 = gl_list_add_last (list2, obj);
 170               ASSERT (gl_list_node_value (list1, node1) == obj);
 171               ASSERT (gl_list_node_value (list2, node2) == obj);
 172               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
 173               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
 174             }
 175             break;
 176           case 5: /* add 3 elements */
 177             {
 178               const char *obj0 = RANDOM_OBJECT ();
 179               const char *obj1 = RANDOM_OBJECT ();
 180               const char *obj2 = RANDOM_OBJECT ();
 181               gl_list_node_t node1, node2;
 182               node1 = gl_list_add_first (list1, obj2);
 183               node1 = gl_list_add_before (list1, node1, obj0);
 184               node1 = gl_list_add_after (list1, node1, obj1);
 185               node2 = gl_list_add_first (list2, obj2);
 186               node2 = gl_list_add_before (list2, node2, obj0);
 187               node2 = gl_list_add_after (list2, node2, obj1);
 188               ASSERT (gl_list_node_value (list1, node1) == obj1);
 189               ASSERT (gl_list_node_value (list2, node2) == obj1);
 190               ASSERT (gl_list_get_at (list1, 0) == obj0);
 191               ASSERT (gl_list_get_at (list1, 1) == obj1);
 192               ASSERT (gl_list_get_at (list1, 2) == obj2);
 193               ASSERT (gl_list_get_at (list2, 0) == obj0);
 194               ASSERT (gl_list_get_at (list2, 1) == obj1);
 195               ASSERT (gl_list_get_at (list2, 2) == obj2);
 196             }
 197             break;
 198           case 6: /* add 1 element */
 199             {
 200               size_t index = RANDOM (gl_list_size (list1) + 1);
 201               const char *obj = RANDOM_OBJECT ();
 202               gl_list_node_t node1, node2;
 203               node1 = gl_list_add_at (list1, index, obj);
 204               node2 = gl_list_add_at (list2, index, obj);
 205               ASSERT (gl_list_get_at (list1, index) == obj);
 206               ASSERT (gl_list_node_value (list1, node1) == obj);
 207               ASSERT (gl_list_get_at (list2, index) == obj);
 208               ASSERT (gl_list_node_value (list2, node2) == obj);
 209               if (index > 0)
 210                 {
 211                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
 212                           == gl_list_get_at (list1, index - 1));
 213                 }
 214               if (index + 1 < gl_list_size (list1))
 215                 {
 216                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
 217                           == gl_list_get_at (list1, index + 1));
 218                 }
 219             }
 220             break;
 221           case 7: case 8: /* remove 1 element */
 222             if (gl_list_size (list1) > 0)
 223               {
 224                 size_t n = gl_list_size (list1);
 225                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 226                 gl_list_node_t node1, node2;
 227                 node1 = gl_list_search (list1, obj);
 228                 node2 = gl_list_search (list2, obj);
 229                 ASSERT (node1 != NULL);
 230                 ASSERT (node2 != NULL);
 231                 ASSERT (gl_list_remove_node (list1, node1));
 232                 ASSERT (gl_list_remove_node (list2, node2));
 233                 ASSERT (gl_list_size (list1) == n - 1);
 234               }
 235             break;
 236           case 9: case 10: /* remove 1 element */
 237             if (gl_list_size (list1) > 0)
 238               {
 239                 size_t n = gl_list_size (list1);
 240                 size_t index = RANDOM (n);
 241                 ASSERT (gl_list_remove_at (list1, index));
 242                 ASSERT (gl_list_remove_at (list2, index));
 243                 ASSERT (gl_list_size (list1) == n - 1);
 244               }
 245             break;
 246           case 11: case 12: /* remove 1 element */
 247             if (gl_list_size (list1) > 0)
 248               {
 249                 size_t n = gl_list_size (list1);
 250                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 251                 ASSERT (gl_list_remove (list1, obj));
 252                 ASSERT (gl_list_remove (list2, obj));
 253                 ASSERT (gl_list_size (list1) == n - 1);
 254               }
 255             break;
 256           case 13:
 257             if (gl_list_size (list1) > 0)
 258               {
 259                 size_t n = gl_list_size (list1);
 260                 const char *obj = "xyzzy";
 261                 ASSERT (!gl_list_remove (list1, obj));
 262                 ASSERT (!gl_list_remove (list2, obj));
 263                 ASSERT (gl_list_size (list1) == n);
 264               }
 265             break;
 266           case 14:
 267             {
 268               size_t n = gl_list_size (list1);
 269               gl_list_iterator_t iter1, iter2;
 270               const void *elt;
 271               iter1 = gl_list_iterator (list1);
 272               iter2 = gl_list_iterator (list2);
 273               for (i = 0; i < n; i++)
 274                 {
 275                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 276                   ASSERT (gl_list_get_at (list1, i) == elt);
 277                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 278                   ASSERT (gl_list_get_at (list2, i) == elt);
 279                 }
 280               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 281               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 282               gl_list_iterator_free (&iter1);
 283               gl_list_iterator_free (&iter2);
 284             }
 285             break;
 286           case 15:
 287             {
 288               size_t end = RANDOM (gl_list_size (list1) + 1);
 289               size_t start = RANDOM (end + 1);
 290               gl_list_iterator_t iter1, iter2;
 291               const void *elt;
 292               iter1 = gl_list_iterator_from_to (list1, start, end);
 293               iter2 = gl_list_iterator_from_to (list2, start, end);
 294               for (i = start; i < end; i++)
 295                 {
 296                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 297                   ASSERT (gl_list_get_at (list1, i) == elt);
 298                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 299                   ASSERT (gl_list_get_at (list2, i) == elt);
 300                 }
 301               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 302               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 303               gl_list_iterator_free (&iter1);
 304               gl_list_iterator_free (&iter2);
 305             }
 306             break;
 307           }
 308         check_equals (list1, list2);
 309       }
 310
 311     gl_list_free (list1);
 312     gl_list_free (list2);
 313     free (contents);
 314   }
 315
 316   return 0;
 317 }