tests/test-avltreehash_list.c

   1 /* Test of sequential list data type implementation.
   2    Copyright (C) 2006-2020 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 <https://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 https://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 (18);
 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: /* remove first element */
 359             {
 360               size_t n = gl_list_size (list1);
 361               bool removed1 = gl_list_remove_first (list1);
 362               ASSERT (gl_list_remove_first (list2) == removed1);
 363               ASSERT (gl_list_remove_first (list3) == removed1);
 364               ASSERT (gl_list_size (list1) == n - (int) removed1);
 365             }
 366             break;
 367           case 12: /* remove last element */
 368             {
 369               size_t n = gl_list_size (list1);
 370               bool removed1 = gl_list_remove_last (list1);
 371               ASSERT (gl_list_remove_last (list2) == removed1);
 372               ASSERT (gl_list_remove_last (list3) == removed1);
 373               ASSERT (gl_list_size (list1) == n - (int) removed1);
 374             }
 375             break;
 376           case 13: case 14: /* remove 1 element */
 377             if (gl_list_size (list1) > 0)
 378               {
 379                 size_t n = gl_list_size (list1);
 380                 const char *obj = gl_list_get_at (list1, RANDOM (n));
 381                 ASSERT (gl_list_remove (list1, obj));
 382                 ASSERT (gl_list_remove (list2, obj));
 383                 ASSERT (gl_list_remove (list3, obj));
 384                 ASSERT (gl_list_size (list1) == n - 1);
 385               }
 386             break;
 387           case 15:
 388             if (gl_list_size (list1) > 0)
 389               {
 390                 size_t n = gl_list_size (list1);
 391                 const char *obj = "xyzzy";
 392                 ASSERT (!gl_list_remove (list1, obj));
 393                 ASSERT (!gl_list_remove (list2, obj));
 394                 ASSERT (!gl_list_remove (list3, obj));
 395                 ASSERT (gl_list_size (list1) == n);
 396               }
 397             break;
 398           case 16:
 399             {
 400               size_t n = gl_list_size (list1);
 401               gl_list_iterator_t iter1, iter2, iter3;
 402               const void *elt;
 403               iter1 = gl_list_iterator (list1);
 404               iter2 = gl_list_iterator (list2);
 405               iter3 = gl_list_iterator (list3);
 406               for (i = 0; i < n; i++)
 407                 {
 408                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 409                   ASSERT (gl_list_get_at (list1, i) == elt);
 410                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 411                   ASSERT (gl_list_get_at (list2, i) == elt);
 412                   ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
 413                   ASSERT (gl_list_get_at (list3, i) == elt);
 414                 }
 415               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 416               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 417               ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
 418               gl_list_iterator_free (&iter1);
 419               gl_list_iterator_free (&iter2);
 420               gl_list_iterator_free (&iter3);
 421             }
 422             break;
 423           case 17:
 424             {
 425               size_t end = RANDOM (gl_list_size (list1) + 1);
 426               size_t start = RANDOM (end + 1);
 427               gl_list_iterator_t iter1, iter2, iter3;
 428               const void *elt;
 429               iter1 = gl_list_iterator_from_to (list1, start, end);
 430               iter2 = gl_list_iterator_from_to (list2, start, end);
 431               iter3 = gl_list_iterator_from_to (list3, start, end);
 432               for (i = start; i < end; i++)
 433                 {
 434                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
 435                   ASSERT (gl_list_get_at (list1, i) == elt);
 436                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
 437                   ASSERT (gl_list_get_at (list2, i) == elt);
 438                   ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
 439                   ASSERT (gl_list_get_at (list3, i) == elt);
 440                 }
 441               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
 442               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
 443               ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
 444               gl_list_iterator_free (&iter1);
 445               gl_list_iterator_free (&iter2);
 446               gl_list_iterator_free (&iter3);
 447             }
 448             break;
 449           }
 450         check_all (list1, list2, list3);
 451       }
 452
 453     gl_list_free (list1);
 454     gl_list_free (list2);
 455     gl_list_free (list3);
 456     free (contents);
 457   }
 458
 459   return 0;
 460 }