tests/test-linkedhash_list.c

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