malloc/tst-dynarray.c

   1 /* Test for dynamic arrays.
   2    Copyright (C) 2017 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library 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 GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #include "tst-dynarray-shared.h"
  20
  21 #define DYNARRAY_STRUCT dynarray_long
  22 #define DYNARRAY_ELEMENT long
  23 #define DYNARRAY_PREFIX dynarray_long_
  24 #define DYNARRAY_ELEMENT_INIT(e) (*(e) = 17)
  25 #include <malloc/dynarray-skeleton.c>
  26
  27 struct long_array
  28 {
  29   long *array;
  30   size_t length;
  31 };
  32
  33 #define DYNARRAY_STRUCT dynarray_long_noscratch
  34 #define DYNARRAY_ELEMENT long
  35 #define DYNARRAY_PREFIX dynarray_long_noscratch_
  36 #define DYNARRAY_ELEMENT_INIT(e) (*(e) = 23)
  37 #define DYNARRAY_FINAL_TYPE struct long_array
  38 #define DYNARRAY_INITIAL_SIZE 0
  39 #include <malloc/dynarray-skeleton.c>
  40
  41 #define DYNARRAY_STRUCT zstr
  42 #define DYNARRAY_ELEMENT char
  43 #define DYNARRAY_PREFIX zstr_
  44 #define DYNARRAY_INITIAL_SIZE 128
  45 #include <malloc/dynarray-skeleton.c>
  46
  47 #include <malloc.h>
  48 #include <mcheck.h>
  49 #include <stdint.h>
  50 #include <support/check.h>
  51 #include <support/support.h>
  52
  53 enum { max_count = 20 };
  54
  55 /* Test dynamic arrays with int elements (no automatic deallocation
  56    for elements).  */
  57 static void
  58 test_int (void)
  59 {
  60   /* Empty array.  */
  61   {
  62     struct dynarray_int dyn;
  63     dynarray_int_init (&dyn);
  64     CHECK_EMPTY (int, &dyn);
  65   }
  66
  67   /* Empty array with finalization.  */
  68   {
  69     struct dynarray_int dyn;
  70     dynarray_int_init (&dyn);
  71     CHECK_INIT_STATE (int, &dyn);
  72     struct int_array result = { (int *) (uintptr_t) -1, -1 };
  73     TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
  74     CHECK_INIT_STATE (int, &dyn);
  75     TEST_VERIFY_EXIT (result.array == NULL);
  76     TEST_VERIFY_EXIT (result.length == 0);
  77   }
  78
  79   /* Non-empty array tests.
  80
  81      do_add: Switch between emplace (false) and add (true).
  82      do_finalize: Perform finalize call at the end.
  83      do_clear: Perform clear call at the end.
  84      do_remove_last: Perform remove_last call after adding elements.
  85      count: Number of elements added to the array.  */
  86   for (int do_add = 0; do_add < 2; ++do_add)
  87     for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
  88       for (int do_clear = 0; do_clear < 2; ++do_clear)
  89         for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
  90           for (unsigned int count = 0; count < max_count; ++count)
  91             {
  92               if (do_remove_last && count == 0)
  93                 continue;
  94               unsigned int base = count * count;
  95               struct dynarray_int dyn;
  96               dynarray_int_init (&dyn);
  97               for (unsigned int i = 0; i < count; ++i)
  98                 {
  99                   if (do_add)
 100                     dynarray_int_add (&dyn, base + i);
 101                   else
 102                     {
 103                       int *place = dynarray_int_emplace (&dyn);
 104                       TEST_VERIFY_EXIT (place != NULL);
 105                       *place = base + i;
 106                     }
 107                   TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
 108                   TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == i + 1);
 109                   TEST_VERIFY_EXIT (dynarray_int_size (&dyn)
 110                                     <= dyn.dynarray_header.allocated);
 111                 }
 112               TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == count);
 113               TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
 114               unsigned final_count;
 115               bool heap_array = dyn.dynarray_header.array != dyn.scratch;
 116               if (do_remove_last)
 117                 {
 118                   dynarray_int_remove_last (&dyn);
 119                   if (count == 0)
 120                     final_count = 0;
 121                   else
 122                     final_count = count - 1;
 123                 }
 124               else
 125                 final_count = count;
 126               if (do_clear)
 127                 {
 128                   dynarray_int_clear (&dyn);
 129                   final_count = 0;
 130                 }
 131               TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
 132               TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
 133                                 == heap_array);
 134               TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == final_count);
 135               TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
 136               if (!do_clear)
 137                 for (unsigned int i = 0; i < final_count; ++i)
 138                   TEST_VERIFY_EXIT (*dynarray_int_at (&dyn, i) == base + i);
 139               if (do_finalize)
 140                 {
 141                   struct int_array result = { (int *) (uintptr_t) -1, -1 };
 142                   TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
 143                   CHECK_INIT_STATE (int, &dyn);
 144                   TEST_VERIFY_EXIT (result.length == final_count);
 145                   if (final_count == 0)
 146                     TEST_VERIFY_EXIT (result.array == NULL);
 147                   else
 148                     {
 149                       TEST_VERIFY_EXIT (result.array != NULL);
 150                       TEST_VERIFY_EXIT (result.array != (int *) (uintptr_t) -1);
 151                       TEST_VERIFY_EXIT
 152                         (malloc_usable_size (result.array)
 153                          >= final_count * sizeof (result.array[0]));
 154                       for (unsigned int i = 0; i < final_count; ++i)
 155                         TEST_VERIFY_EXIT (result.array[i] == base + i);
 156                       free (result.array);
 157                     }
 158                 }
 159               else /* !do_finalize */
 160                 {
 161                   dynarray_int_free (&dyn);
 162                   CHECK_INIT_STATE (int, &dyn);
 163                 }
 164             }
 165 }
 166
 167 /* Test dynamic arrays with char * elements (with automatic
 168    deallocation of the pointed-to strings).  */
 169 static void
 170 test_str (void)
 171 {
 172   /* Empty array.  */
 173   {
 174     struct dynarray_str dyn;
 175     dynarray_str_init (&dyn);
 176     CHECK_EMPTY (str, &dyn);
 177   }
 178
 179   /* Empty array with finalization.  */
 180   {
 181     struct dynarray_str dyn;
 182     dynarray_str_init (&dyn);
 183     TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
 184     struct str_array result = { (char **) (uintptr_t) -1, -1 };
 185     TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
 186     CHECK_INIT_STATE (str, &dyn);
 187     TEST_VERIFY_EXIT (result.array == NULL);
 188     TEST_VERIFY_EXIT (result.length == 0);
 189   }
 190
 191   /* Non-empty array tests.
 192
 193      do_add: Switch between emplace (false) and add (true).
 194      do_finalize: Perform finalize call at the end.
 195      do_clear: Perform clear call at the end.
 196      do_remove_last: Perform remove_last call after adding elements.
 197      count: Number of elements added to the array.  */
 198   for (int do_add = 0; do_add < 2; ++do_add)
 199     for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
 200       for (int do_clear = 0; do_clear < 2; ++do_clear)
 201         for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
 202           for (unsigned int count = 0; count < max_count; ++count)
 203             {
 204               if (do_remove_last && count == 0)
 205                 continue;
 206               unsigned int base = count * count;
 207               struct dynarray_str dyn;
 208               dynarray_str_init (&dyn);
 209               for (unsigned int i = 0; i < count; ++i)
 210                 {
 211                   char *item = xasprintf ("%d", base + i);
 212                   if (do_add)
 213                     dynarray_str_add (&dyn, item);
 214                   else
 215                     {
 216                       char **place = dynarray_str_emplace (&dyn);
 217                       TEST_VERIFY_EXIT (place != NULL);
 218                       TEST_VERIFY_EXIT (*place == NULL);
 219                       *place = item;
 220                     }
 221                   TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
 222                   TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == i + 1);
 223                   TEST_VERIFY_EXIT (dynarray_str_size (&dyn)
 224                                     <= dyn.dynarray_header.allocated);
 225                 }
 226               TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == count);
 227               TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
 228               unsigned final_count;
 229               bool heap_array = dyn.dynarray_header.array != dyn.scratch;
 230               if (do_remove_last)
 231                 {
 232                   dynarray_str_remove_last (&dyn);
 233                   if (count == 0)
 234                     final_count = 0;
 235                   else
 236                     final_count = count - 1;
 237                 }
 238               else
 239                 final_count = count;
 240               if (do_clear)
 241                 {
 242                   dynarray_str_clear (&dyn);
 243                   final_count = 0;
 244                 }
 245               TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
 246               TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
 247                                 == heap_array);
 248               TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == final_count);
 249               TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
 250               if (!do_clear)
 251                 for (unsigned int i = 0; i < count - do_remove_last; ++i)
 252                   {
 253                     char *expected = xasprintf ("%d", base + i);
 254                     const char *actual = *dynarray_str_at (&dyn, i);
 255                     TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
 256                     free (expected);
 257                   }
 258               if (do_finalize)
 259                 {
 260                   struct str_array result = { (char **) (uintptr_t) -1, -1 };
 261                   TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
 262                   CHECK_INIT_STATE (str, &dyn);
 263                   TEST_VERIFY_EXIT (result.length == final_count);
 264                   if (final_count == 0)
 265                     TEST_VERIFY_EXIT (result.array == NULL);
 266                   else
 267                     {
 268                       TEST_VERIFY_EXIT (result.array != NULL);
 269                       TEST_VERIFY_EXIT (result.array
 270                                         != (char **) (uintptr_t) -1);
 271                       TEST_VERIFY_EXIT (result.length
 272                                         == count - do_remove_last);
 273                       TEST_VERIFY_EXIT
 274                         (malloc_usable_size (result.array)
 275                          >= final_count * sizeof (result.array[0]));
 276                       for (unsigned int i = 0; i < count - do_remove_last; ++i)
 277                         {
 278                           char *expected = xasprintf ("%d", base + i);
 279                           char *actual = result.array[i];
 280                           TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
 281                           free (expected);
 282                           free (actual);
 283                         }
 284                       free (result.array);
 285                     }
 286                 }
 287               else /* !do_finalize */
 288                 {
 289                   dynarray_str_free (&dyn);
 290                   CHECK_INIT_STATE (str, &dyn);
 291                 }
 292             }
 293
 294   /* Test resizing.  */
 295   {
 296     enum { count = 2131 };
 297     struct dynarray_str dyn;
 298     dynarray_str_init (&dyn);
 299
 300     /* From length 0 to length 1.  */
 301     TEST_VERIFY (dynarray_str_resize (&dyn, 1));
 302     TEST_VERIFY (dynarray_str_size (&dyn) == 1);
 303     TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
 304     *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");
 305     dynarray_str_free (&dyn);
 306
 307     /* From length 0 to length 1 and 2.  */
 308     TEST_VERIFY (dynarray_str_resize (&dyn, 1));
 309     TEST_VERIFY (dynarray_str_size (&dyn) == 1);
 310     TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
 311     *dynarray_str_at (&dyn, 0) = xstrdup ("allocated0");
 312     TEST_VERIFY (dynarray_str_resize (&dyn, 2));
 313     TEST_VERIFY (dynarray_str_size (&dyn) == 2);
 314     TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
 315     TEST_VERIFY (*dynarray_str_at (&dyn, 1) == NULL);
 316     *dynarray_str_at (&dyn, 1) = xstrdup ("allocated1");
 317     TEST_VERIFY (dynarray_str_resize (&dyn, count));
 318     TEST_VERIFY (dynarray_str_size (&dyn) == count);
 319     TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
 320     TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
 321     for (int i = 2; i < count; ++i)
 322       TEST_VERIFY (*dynarray_str_at (&dyn, i) == NULL);
 323     *dynarray_str_at (&dyn, count - 1) = xstrdup ("allocated2");
 324     TEST_VERIFY (dynarray_str_resize (&dyn, 3));
 325     TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
 326     TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
 327     TEST_VERIFY (*dynarray_str_at (&dyn, 2) == NULL);
 328     dynarray_str_free (&dyn);
 329   }
 330 }
 331
 332 /* Verify that DYNARRAY_ELEMENT_INIT has an effect.  */
 333 static void
 334 test_long_init (void)
 335 {
 336   enum { count = 2131 };
 337   {
 338     struct dynarray_long dyn;
 339     dynarray_long_init (&dyn);
 340     for (int i = 0; i < count; ++i)
 341       {
 342         long *place = dynarray_long_emplace (&dyn);
 343         TEST_VERIFY_EXIT (place != NULL);
 344         TEST_VERIFY (*place == 17);
 345       }
 346     TEST_VERIFY (dynarray_long_size (&dyn) == count);
 347     for (int i = 0; i < count; ++i)
 348       TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
 349     dynarray_long_free (&dyn);
 350
 351     TEST_VERIFY (dynarray_long_resize (&dyn, 1));
 352     TEST_VERIFY (dynarray_long_size (&dyn) == 1);
 353     TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
 354     *dynarray_long_at (&dyn, 0) = 18;
 355     dynarray_long_free (&dyn);
 356     TEST_VERIFY (dynarray_long_resize (&dyn, 1));
 357     TEST_VERIFY (dynarray_long_size (&dyn) == 1);
 358     TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
 359     TEST_VERIFY (dynarray_long_resize (&dyn, 2));
 360     TEST_VERIFY (dynarray_long_size (&dyn) == 2);
 361     TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
 362     TEST_VERIFY (*dynarray_long_at (&dyn, 1) == 17);
 363     *dynarray_long_at (&dyn, 0) = 18;
 364     TEST_VERIFY (dynarray_long_resize (&dyn, count));
 365     TEST_VERIFY (dynarray_long_size (&dyn) == count);
 366     TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 18);
 367     for (int i = 1; i < count; ++i)
 368       TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
 369     dynarray_long_free (&dyn);
 370   }
 371
 372   /* Similar, but without an on-stack scratch region
 373      (DYNARRAY_INITIAL_SIZE is 0).  */
 374   {
 375     struct dynarray_long_noscratch dyn;
 376     dynarray_long_noscratch_init (&dyn);
 377     struct long_array result;
 378     TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
 379     TEST_VERIFY (result.array == NULL);
 380     TEST_VERIFY (result.length == 0);
 381
 382     /* Test with one element.  */
 383     {
 384       long *place = dynarray_long_noscratch_emplace (&dyn);
 385       TEST_VERIFY_EXIT (place != NULL);
 386       TEST_VERIFY (*place == 23);
 387     }
 388     TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
 389     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
 390     TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
 391     TEST_VERIFY_EXIT (result.array != NULL);
 392     TEST_VERIFY (result.length == 1);
 393     TEST_VERIFY (result.array[0] == 23);
 394     free (result.array);
 395
 396     for (int i = 0; i < count; ++i)
 397       {
 398         long *place = dynarray_long_noscratch_emplace (&dyn);
 399         TEST_VERIFY_EXIT (place != NULL);
 400         TEST_VERIFY (*place == 23);
 401         if (i == 0)
 402           *place = 29;
 403       }
 404     TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
 405     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 29);
 406     for (int i = 1; i < count; ++i)
 407       TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
 408     TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
 409     TEST_VERIFY_EXIT (result.array != NULL);
 410     TEST_VERIFY (result.length == count);
 411     TEST_VERIFY (result.array[0] == 29);
 412     for (int i = 1; i < count; ++i)
 413       TEST_VERIFY (result.array[i] == 23);
 414     free (result.array);
 415
 416     TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
 417     TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
 418     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
 419     *dynarray_long_noscratch_at (&dyn, 0) = 24;
 420     dynarray_long_noscratch_free (&dyn);
 421     TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
 422     TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
 423     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
 424     TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 2));
 425     TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 2);
 426     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
 427     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 1) == 23);
 428     *dynarray_long_noscratch_at (&dyn, 0) = 24;
 429     TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, count));
 430     TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
 431     TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 24);
 432     for (int i = 1; i < count; ++i)
 433       TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
 434     dynarray_long_noscratch_free (&dyn);
 435   }
 436 }
 437
 438 /* Test NUL-terminated string construction with the add function and
 439    the simple finalize function.  */
 440 static void
 441 test_zstr (void)
 442 {
 443   /* Totally empty string (no NUL termination).  */
 444   {
 445     struct zstr s;
 446     zstr_init (&s);
 447     char *result = zstr_finalize (&s, NULL);
 448     TEST_VERIFY (result == NULL);
 449     TEST_VERIFY (zstr_size (&s) == 0);
 450     size_t length = 1;
 451     result = zstr_finalize (&s, &length);
 452     TEST_VERIFY (result == NULL);
 453     TEST_VERIFY (length == 0);
 454     TEST_VERIFY (zstr_size (&s) == 0);
 455   }
 456
 457   /* Empty string.  */
 458   {
 459     struct zstr s;
 460     zstr_init (&s);
 461     zstr_add (&s, '\0');
 462     char *result = zstr_finalize (&s, NULL);
 463     TEST_VERIFY_EXIT (result != NULL);
 464     TEST_VERIFY (*result == '\0');
 465     TEST_VERIFY (zstr_size (&s) == 0);
 466     free (result);
 467
 468     zstr_add (&s, '\0');
 469     size_t length = 1;
 470     result = zstr_finalize (&s, &length);
 471     TEST_VERIFY_EXIT (result != NULL);
 472     TEST_VERIFY (*result == '\0');
 473     TEST_VERIFY (length == 1);
 474     TEST_VERIFY (zstr_size (&s) == 0);
 475     free (result);
 476   }
 477
 478   /* A few characters.  */
 479   {
 480     struct zstr s;
 481     zstr_init (&s);
 482     zstr_add (&s, 'A');
 483     zstr_add (&s, 'b');
 484     zstr_add (&s, 'c');
 485     zstr_add (&s, '\0');
 486     char *result = zstr_finalize (&s, NULL);
 487     TEST_VERIFY_EXIT (result != NULL);
 488     TEST_VERIFY (strcmp (result, "Abc") == 0);
 489     TEST_VERIFY (zstr_size (&s) == 0);
 490     free (result);
 491
 492     zstr_add (&s, 'X');
 493     zstr_add (&s, 'y');
 494     zstr_add (&s, 'z');
 495     zstr_add (&s, '\0');
 496     size_t length = 1;
 497     result = zstr_finalize (&s, &length);
 498     TEST_VERIFY_EXIT (result != NULL);
 499     TEST_VERIFY (strcmp (result, "Xyz") == 0);
 500     TEST_VERIFY (length == 4);
 501     TEST_VERIFY (zstr_size (&s) == 0);
 502     free (result);
 503   }
 504 }
 505
 506 static int
 507 do_test (void)
 508 {
 509   mtrace ();
 510   test_int ();
 511   test_str ();
 512   test_long_init ();
 513   test_zstr ();
 514   return 0;
 515 }
 516
 517 #include <support/test-driver.c>