tests/test-rbtreehash_list.c

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