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