tests/test-linkedhash_list.c

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