tests/test-avltreehash_list.c

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