glib/tests/array-test.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 /*
  19  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  20  * file for a list of people on the GLib Team.  See the ChangeLog
  21  * files for a list of changes.  These files are distributed with
  22  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  23  */
  24
  25 #undef G_DISABLE_ASSERT
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include "glib.h"
  31
  32 /* Test data to be passed to any function which calls g_array_new(), providing
  33  * the parameters for that call. Most #GArray tests should be repeated for all
  34  * possible values of #ArrayTestData. */
  35 typedef struct
  36 {
  37   gboolean zero_terminated;
  38   gboolean clear_;
  39 } ArrayTestData;
  40
  41 /* Assert that @garray contains @n_expected_elements as given in @expected_data.
  42  * @garray must contain #gint elements. */
  43 static void
  44 assert_int_array_equal (GArray     *garray,
  45                         const gint *expected_data,
  46                         gsize       n_expected_elements)
  47 {
  48   gsize i;
  49
  50   g_assert_cmpuint (garray->len, ==, n_expected_elements);
  51   for (i = 0; i < garray->len; i++)
  52     g_assert_cmpint (g_array_index (garray, gint, i), ==, expected_data[i]);
  53 }
  54
  55 /* Iff config->zero_terminated is %TRUE, assert that the final element of
  56  * @garray is zero. @garray must contain #gint elements. */
  57 static void
  58 assert_int_array_zero_terminated (const ArrayTestData *config,
  59                                   GArray              *garray)
  60 {
  61   if (config->zero_terminated)
  62     {
  63       gint *data = (gint *) garray->data;
  64       g_assert_cmpint (data[garray->len], ==, 0);
  65     }
  66 }
  67
  68 static void
  69 sum_up (gpointer data,
  70         gpointer user_data)
  71 {
  72   gint *sum = (gint *)user_data;
  73
  74   *sum += GPOINTER_TO_INT (data);
  75 }
  76
  77 /* Check that expanding an array with g_array_set_size() clears the new elements
  78  * if @clear_ was specified during construction. */
  79 static void
  80 array_set_size (gconstpointer test_data)
  81 {
  82   const ArrayTestData *config = test_data;
  83   GArray *garray;
  84   gsize i;
  85
  86   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
  87   g_assert_cmpuint (garray->len, ==, 0);
  88   assert_int_array_zero_terminated (config, garray);
  89
  90   g_array_set_size (garray, 5);
  91   g_assert_cmpuint (garray->len, ==, 5);
  92   assert_int_array_zero_terminated (config, garray);
  93
  94   if (config->clear_)
  95     for (i = 0; i < 5; i++)
  96       g_assert_cmpint (g_array_index (garray, gint, i), ==, 0);
  97
  98   g_array_unref (garray);
  99 }
 100
 101 /* As with array_set_size(), but with a sized array. */
 102 static void
 103 array_set_size_sized (gconstpointer test_data)
 104 {
 105   const ArrayTestData *config = test_data;
 106   GArray *garray;
 107   gsize i;
 108
 109   garray = g_array_sized_new (config->zero_terminated, config->clear_, sizeof (gint), 10);
 110   g_assert_cmpuint (garray->len, ==, 0);
 111   assert_int_array_zero_terminated (config, garray);
 112
 113   g_array_set_size (garray, 5);
 114   g_assert_cmpuint (garray->len, ==, 5);
 115   assert_int_array_zero_terminated (config, garray);
 116
 117   if (config->clear_)
 118     for (i = 0; i < 5; i++)
 119       g_assert_cmpint (g_array_index (garray, gint, i), ==, 0);
 120
 121   g_array_unref (garray);
 122 }
 123
 124 /* Check that a zero-terminated array does actually have a zero terminator. */
 125 static void
 126 array_new_zero_terminated (void)
 127 {
 128   GArray *garray;
 129   gchar *out_str = NULL;
 130
 131   garray = g_array_new (TRUE, FALSE, sizeof (gchar));
 132   g_assert_cmpuint (garray->len, ==, 0);
 133
 134   g_array_append_vals (garray, "hello", strlen ("hello"));
 135   g_assert_cmpuint (garray->len, ==, 5);
 136   g_assert_cmpstr (garray->data, ==, "hello");
 137
 138   out_str = g_array_free (garray, FALSE);
 139   g_assert_cmpstr (out_str, ==, "hello");
 140   g_free (out_str);
 141 }
 142
 143 /* Check that g_array_append_val() works correctly for various #GArray
 144  * configurations. */
 145 static void
 146 array_append_val (gconstpointer test_data)
 147 {
 148   const ArrayTestData *config = test_data;
 149   GArray *garray;
 150   gint i;
 151   gint *segment;
 152
 153   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 154   for (i = 0; i < 10000; i++)
 155     g_array_append_val (garray, i);
 156   assert_int_array_zero_terminated (config, garray);
 157
 158   for (i = 0; i < 10000; i++)
 159     g_assert_cmpint (g_array_index (garray, gint, i), ==, i);
 160
 161   segment = (gint*)g_array_free (garray, FALSE);
 162   for (i = 0; i < 10000; i++)
 163     g_assert_cmpint (segment[i], ==, i);
 164   if (config->zero_terminated)
 165     g_assert_cmpint (segment[10000], ==, 0);
 166
 167   g_free (segment);
 168 }
 169
 170 /* Check that g_array_prepend_val() works correctly for various #GArray
 171  * configurations. */
 172 static void
 173 array_prepend_val (gconstpointer test_data)
 174 {
 175   const ArrayTestData *config = test_data;
 176   GArray *garray;
 177   gint i;
 178
 179   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 180   for (i = 0; i < 100; i++)
 181     g_array_prepend_val (garray, i);
 182   assert_int_array_zero_terminated (config, garray);
 183
 184   for (i = 0; i < 100; i++)
 185     g_assert_cmpint (g_array_index (garray, gint, i), ==, (100 - i - 1));
 186
 187   g_array_free (garray, TRUE);
 188 }
 189
 190 /* Test that g_array_prepend_vals() works correctly with various array
 191  * configurations. */
 192 static void
 193 array_prepend_vals (gconstpointer test_data)
 194 {
 195   const ArrayTestData *config = test_data;
 196   GArray *garray, *garray_out;
 197   const gint vals[] = { 0, 1, 2, 3, 4 };
 198   const gint expected_vals1[] = { 0, 1 };
 199   const gint expected_vals2[] = { 2, 0, 1 };
 200   const gint expected_vals3[] = { 3, 4, 2, 0, 1 };
 201
 202   /* Set up an array. */
 203   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 204   assert_int_array_zero_terminated (config, garray);
 205
 206   /* Prepend several values to an empty array. */
 207   garray_out = g_array_prepend_vals (garray, vals, 2);
 208   g_assert_true (garray == garray_out);
 209   assert_int_array_equal (garray, expected_vals1, G_N_ELEMENTS (expected_vals1));
 210   assert_int_array_zero_terminated (config, garray);
 211
 212   /* Prepend a single value. */
 213   garray_out = g_array_prepend_vals (garray, vals + 2, 1);
 214   g_assert_true (garray == garray_out);
 215   assert_int_array_equal (garray, expected_vals2, G_N_ELEMENTS (expected_vals2));
 216   assert_int_array_zero_terminated (config, garray);
 217
 218   /* Prepend several values to a non-empty array. */
 219   garray_out = g_array_prepend_vals (garray, vals + 3, 2);
 220   g_assert_true (garray == garray_out);
 221   assert_int_array_equal (garray, expected_vals3, G_N_ELEMENTS (expected_vals3));
 222   assert_int_array_zero_terminated (config, garray);
 223
 224   /* Prepend no values. */
 225   garray_out = g_array_prepend_vals (garray, vals, 0);
 226   g_assert_true (garray == garray_out);
 227   assert_int_array_equal (garray, expected_vals3, G_N_ELEMENTS (expected_vals3));
 228   assert_int_array_zero_terminated (config, garray);
 229
 230   /* Prepend no values with %NULL data. */
 231   garray_out = g_array_prepend_vals (garray, NULL, 0);
 232   g_assert_true (garray == garray_out);
 233   assert_int_array_equal (garray, expected_vals3, G_N_ELEMENTS (expected_vals3));
 234   assert_int_array_zero_terminated (config, garray);
 235
 236   g_array_free (garray, TRUE);
 237 }
 238
 239 /* Test that g_array_insert_vals() works correctly with various array
 240  * configurations. */
 241 static void
 242 array_insert_vals (gconstpointer test_data)
 243 {
 244   const ArrayTestData *config = test_data;
 245   GArray *garray, *garray_out;
 246   gsize i;
 247   const gint vals[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
 248   const gint expected_vals1[] = { 0, 1 };
 249   const gint expected_vals2[] = { 0, 2, 3, 1 };
 250   const gint expected_vals3[] = { 0, 2, 3, 1, 4 };
 251   const gint expected_vals4[] = { 5, 0, 2, 3, 1, 4 };
 252   const gint expected_vals5[] = { 5, 0, 2, 3, 1, 4, 0, 0, 0, 0, 6, 7 };
 253
 254   /* Set up an array. */
 255   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 256   assert_int_array_zero_terminated (config, garray);
 257
 258   /* Insert several values at the beginning. */
 259   garray_out = g_array_insert_vals (garray, 0, vals, 2);
 260   g_assert_true (garray == garray_out);
 261   assert_int_array_equal (garray, expected_vals1, G_N_ELEMENTS (expected_vals1));
 262   assert_int_array_zero_terminated (config, garray);
 263
 264   /* Insert some more part-way through. */
 265   garray_out = g_array_insert_vals (garray, 1, vals + 2, 2);
 266   g_assert_true (garray == garray_out);
 267   assert_int_array_equal (garray, expected_vals2, G_N_ELEMENTS (expected_vals2));
 268   assert_int_array_zero_terminated (config, garray);
 269
 270   /* And at the end. */
 271   garray_out = g_array_insert_vals (garray, garray->len, vals + 4, 1);
 272   g_assert_true (garray == garray_out);
 273   assert_int_array_equal (garray, expected_vals3, G_N_ELEMENTS (expected_vals3));
 274   assert_int_array_zero_terminated (config, garray);
 275
 276   /* Then back at the beginning again. */
 277   garray_out = g_array_insert_vals (garray, 0, vals + 5, 1);
 278   g_assert_true (garray == garray_out);
 279   assert_int_array_equal (garray, expected_vals4, G_N_ELEMENTS (expected_vals4));
 280   assert_int_array_zero_terminated (config, garray);
 281
 282   /* Insert zero elements. */
 283   garray_out = g_array_insert_vals (garray, 0, vals, 0);
 284   g_assert_true (garray == garray_out);
 285   assert_int_array_equal (garray, expected_vals4, G_N_ELEMENTS (expected_vals4));
 286   assert_int_array_zero_terminated (config, garray);
 287
 288   /* Insert zero elements with a %NULL pointer. */
 289   garray_out = g_array_insert_vals (garray, 0, NULL, 0);
 290   g_assert_true (garray == garray_out);
 291   assert_int_array_equal (garray, expected_vals4, G_N_ELEMENTS (expected_vals4));
 292   assert_int_array_zero_terminated (config, garray);
 293
 294   /* Insert some elements off the end of the array. The behaviour here depends
 295    * on whether the array clears entries. */
 296   garray_out = g_array_insert_vals (garray, garray->len + 4, vals + 6, 2);
 297   g_assert_true (garray == garray_out);
 298
 299   g_assert_cmpuint (garray->len, ==, G_N_ELEMENTS (expected_vals5));
 300   for (i = 0; i < G_N_ELEMENTS (expected_vals5); i++)
 301     {
 302       if (config->clear_ || i < 6 || i > 9)
 303         g_assert_cmpint (g_array_index (garray, gint, i), ==, expected_vals5[i]);
 304     }
 305
 306   assert_int_array_zero_terminated (config, garray);
 307
 308   g_array_free (garray, TRUE);
 309 }
 310
 311 /* Check that g_array_remove_index() works correctly for various #GArray
 312  * configurations. */
 313 static void
 314 array_remove_index (gconstpointer test_data)
 315 {
 316   const ArrayTestData *config = test_data;
 317   GArray *garray;
 318   gint i;
 319   gint prev, cur;
 320
 321   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 322   for (i = 0; i < 100; i++)
 323     g_array_append_val (garray, i);
 324   assert_int_array_zero_terminated (config, garray);
 325
 326   g_assert_cmpint (garray->len, ==, 100);
 327
 328   g_array_remove_index (garray, 1);
 329   g_array_remove_index (garray, 3);
 330   g_array_remove_index (garray, 21);
 331   g_array_remove_index (garray, 57);
 332
 333   g_assert_cmpint (garray->len, ==, 96);
 334   assert_int_array_zero_terminated (config, garray);
 335
 336   prev = -1;
 337   for (i = 0; i < garray->len; i++)
 338     {
 339       cur = g_array_index (garray, gint, i);
 340       g_assert (cur != 1 &&  cur != 4 && cur != 23 && cur != 60);
 341       g_assert_cmpint (prev, <, cur);
 342       prev = cur;
 343     }
 344
 345   g_array_free (garray, TRUE);
 346 }
 347
 348 /* Check that g_array_remove_index_fast() works correctly for various #GArray
 349  * configurations. */
 350 static void
 351 array_remove_index_fast (gconstpointer test_data)
 352 {
 353   const ArrayTestData *config = test_data;
 354   GArray *garray;
 355   gint i;
 356   gint prev, cur;
 357
 358   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 359   for (i = 0; i < 100; i++)
 360     g_array_append_val (garray, i);
 361
 362   g_assert_cmpint (garray->len, ==, 100);
 363   assert_int_array_zero_terminated (config, garray);
 364
 365   g_array_remove_index_fast (garray, 1);
 366   g_array_remove_index_fast (garray, 3);
 367   g_array_remove_index_fast (garray, 21);
 368   g_array_remove_index_fast (garray, 57);
 369
 370   g_assert_cmpint (garray->len, ==, 96);
 371   assert_int_array_zero_terminated (config, garray);
 372
 373   prev = -1;
 374   for (i = 0; i < garray->len; i++)
 375     {
 376       cur = g_array_index (garray, gint, i);
 377       g_assert (cur != 1 &&  cur != 3 && cur != 21 && cur != 57);
 378       if (cur < 96)
 379         {
 380           g_assert_cmpint (prev, <, cur);
 381           prev = cur;
 382         }
 383     }
 384
 385   g_array_free (garray, TRUE);
 386 }
 387
 388 /* Check that g_array_remove_range() works correctly for various #GArray
 389  * configurations. */
 390 static void
 391 array_remove_range (gconstpointer test_data)
 392 {
 393   const ArrayTestData *config = test_data;
 394   GArray *garray;
 395   gint i;
 396   gint prev, cur;
 397
 398   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 399   for (i = 0; i < 100; i++)
 400     g_array_append_val (garray, i);
 401
 402   g_assert_cmpint (garray->len, ==, 100);
 403   assert_int_array_zero_terminated (config, garray);
 404
 405   g_array_remove_range (garray, 31, 4);
 406
 407   g_assert_cmpint (garray->len, ==, 96);
 408   assert_int_array_zero_terminated (config, garray);
 409
 410   prev = -1;
 411   for (i = 0; i < garray->len; i++)
 412     {
 413       cur = g_array_index (garray, gint, i);
 414       g_assert (cur < 31 || cur > 34);
 415       g_assert_cmpint (prev, <, cur);
 416       prev = cur;
 417     }
 418
 419   /* Ensure the entire array can be cleared, even when empty. */
 420   g_array_remove_range (garray, 0, garray->len);
 421
 422   g_assert_cmpint (garray->len, ==, 0);
 423   assert_int_array_zero_terminated (config, garray);
 424
 425   g_array_remove_range (garray, 0, garray->len);
 426
 427   g_assert_cmpint (garray->len, ==, 0);
 428   assert_int_array_zero_terminated (config, garray);
 429
 430   g_array_free (garray, TRUE);
 431 }
 432
 433 static void
 434 array_ref_count (void)
 435 {
 436   GArray *garray;
 437   GArray *garray2;
 438   gint i;
 439
 440   garray = g_array_new (FALSE, FALSE, sizeof (gint));
 441   g_assert_cmpint (g_array_get_element_size (garray), ==, sizeof (gint));
 442   for (i = 0; i < 100; i++)
 443     g_array_prepend_val (garray, i);
 444
 445   /* check we can ref, unref and still access the array */
 446   garray2 = g_array_ref (garray);
 447   g_assert (garray == garray2);
 448   g_array_unref (garray2);
 449   for (i = 0; i < 100; i++)
 450     g_assert_cmpint (g_array_index (garray, gint, i), ==, (100 - i - 1));
 451
 452   /* garray2 should be an empty valid GArray wrapper */
 453   garray2 = g_array_ref (garray);
 454   g_array_free (garray, TRUE);
 455
 456   g_assert_cmpint (garray2->len, ==, 0);
 457   g_array_unref (garray2);
 458 }
 459
 460 static int
 461 int_compare (gconstpointer p1, gconstpointer p2)
 462 {
 463   const gint *i1 = p1;
 464   const gint *i2 = p2;
 465
 466   return *i1 - *i2;
 467 }
 468
 469 static void
 470 array_copy (gconstpointer test_data)
 471 {
 472   GArray *array, *array_copy;
 473   gsize i;
 474   const ArrayTestData *config = test_data;
 475   const gsize array_size = 100;
 476
 477   /* Testing degenerated cases */
 478   if (g_test_undefined ())
 479     {
 480       g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
 481                              "*assertion*!= NULL*");
 482       array = g_array_copy (NULL);
 483       g_test_assert_expected_messages ();
 484
 485       g_assert_null (array);
 486     }
 487
 488   /* Testing simple copy */
 489   array = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 490
 491   for (i = 0; i < array_size; i++)
 492     g_array_append_val (array, i);
 493
 494   array_copy = g_array_copy (array);
 495
 496   /* Check internal data */
 497   for (i = 0; i < array_size; i++)
 498     g_assert_cmpuint (g_array_index (array, gint, i), ==,
 499                       g_array_index (array_copy, gint, i));
 500
 501   /* Check internal parameters ('zero_terminated' flag) */
 502   if (config->zero_terminated)
 503     {
 504       const gint *data = (const gint *) array_copy->data;
 505       g_assert_cmpint (data[array_copy->len], ==, 0);
 506     }
 507
 508   /* Check internal parameters ('clear' flag) */
 509   if (config->clear_)
 510     {
 511       guint old_length = array_copy->len;
 512       g_array_set_size (array_copy, old_length + 5);
 513       for (i = old_length; i < old_length + 5; i++)
 514         g_assert_cmpint (g_array_index (array_copy, gint, i), ==, 0);
 515     }
 516
 517   /* Clean-up */
 518   g_array_unref (array);
 519   g_array_unref (array_copy);
 520 }
 521
 522 static int
 523 int_compare_data (gconstpointer p1, gconstpointer p2, gpointer data)
 524 {
 525   const gint *i1 = p1;
 526   const gint *i2 = p2;
 527
 528   return *i1 - *i2;
 529 }
 530
 531 /* Check that g_array_sort() works correctly for various #GArray
 532  * configurations. */
 533 static void
 534 array_sort (gconstpointer test_data)
 535 {
 536   const ArrayTestData *config = test_data;
 537   GArray *garray;
 538   gint i;
 539   gint prev, cur;
 540
 541   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 542   for (i = 0; i < 10000; i++)
 543     {
 544       cur = g_random_int_range (0, 10000);
 545       g_array_append_val (garray, cur);
 546     }
 547   assert_int_array_zero_terminated (config, garray);
 548
 549   g_array_sort (garray, int_compare);
 550   assert_int_array_zero_terminated (config, garray);
 551
 552   prev = -1;
 553   for (i = 0; i < garray->len; i++)
 554     {
 555       cur = g_array_index (garray, gint, i);
 556       g_assert_cmpint (prev, <=, cur);
 557       prev = cur;
 558     }
 559
 560   g_array_free (garray, TRUE);
 561 }
 562
 563 /* Check that g_array_sort_with_data() works correctly for various #GArray
 564  * configurations. */
 565 static void
 566 array_sort_with_data (gconstpointer test_data)
 567 {
 568   const ArrayTestData *config = test_data;
 569   GArray *garray;
 570   gint i;
 571   gint prev, cur;
 572
 573   garray = g_array_new (config->zero_terminated, config->clear_, sizeof (gint));
 574   for (i = 0; i < 10000; i++)
 575     {
 576       cur = g_random_int_range (0, 10000);
 577       g_array_append_val (garray, cur);
 578     }
 579   assert_int_array_zero_terminated (config, garray);
 580
 581   g_array_sort_with_data (garray, int_compare_data, NULL);
 582   assert_int_array_zero_terminated (config, garray);
 583
 584   prev = -1;
 585   for (i = 0; i < garray->len; i++)
 586     {
 587       cur = g_array_index (garray, gint, i);
 588       g_assert_cmpint (prev, <=, cur);
 589       prev = cur;
 590     }
 591
 592   g_array_free (garray, TRUE);
 593 }
 594
 595 static gint num_clear_func_invocations = 0;
 596
 597 static void
 598 my_clear_func (gpointer data)
 599 {
 600   num_clear_func_invocations += 1;
 601 }
 602
 603 static void
 604 array_clear_func (void)
 605 {
 606   GArray *garray;
 607   gint i;
 608   gint cur;
 609
 610   garray = g_array_new (FALSE, FALSE, sizeof (gint));
 611   g_array_set_clear_func (garray, my_clear_func);
 612
 613   for (i = 0; i < 10; i++)
 614     {
 615       cur = g_random_int_range (0, 100);
 616       g_array_append_val (garray, cur);
 617     }
 618
 619   g_array_remove_index (garray, 9);
 620   g_assert_cmpint (num_clear_func_invocations, ==, 1);
 621
 622   g_array_remove_range (garray, 5, 3);
 623   g_assert_cmpint (num_clear_func_invocations, ==, 4);
 624
 625   g_array_remove_index_fast (garray, 4);
 626   g_assert_cmpint (num_clear_func_invocations, ==, 5);
 627
 628   g_array_free (garray, TRUE);
 629   g_assert_cmpint (num_clear_func_invocations, ==, 10);
 630 }
 631
 632 /* Defining a comparison function for testing g_array_binary_search() */
 633 static gint
 634 cmpint (gconstpointer a, gconstpointer b)
 635 {
 636   const gint *_a = a;
 637   const gint *_b = b;
 638
 639   return *_a - *_b;
 640 }
 641
 642 /* Testing g_array_binary_search() function */
 643 static void
 644 test_array_binary_search (void)
 645 {
 646   GArray *garray;
 647   guint i, matched_index;
 648
 649   if (g_test_undefined ())
 650     {
 651       /* Testing degenerated cases */
 652       garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 0);
 653       g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
 654                              "*assertion*!= NULL*");
 655       g_assert_false (g_array_binary_search (NULL, &i, cmpint, NULL));
 656       g_test_assert_expected_messages ();
 657
 658       g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
 659                              "*assertion*!= NULL*");
 660       g_assert_false (g_array_binary_search (garray, &i, NULL, NULL));
 661       g_test_assert_expected_messages ();
 662       g_array_free (garray, TRUE);
 663     }
 664
 665   /* Testing array of size 0 */
 666   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 0);
 667
 668   i = 1;
 669   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 670
 671   g_array_free (garray, TRUE);
 672
 673   /* Testing array of size 1 */
 674   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 1);
 675   i = 1;
 676   g_array_append_val (garray, i);
 677
 678   g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 679
 680   i = 0;
 681   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 682
 683   i = 2;
 684   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 685
 686   g_array_free (garray, TRUE);
 687
 688   /* Testing array of size 2 */
 689   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 2);
 690   for (i = 1; i < 3; i++)
 691     g_array_append_val (garray, i);
 692
 693   for (i = 1; i < 3; i++)
 694     g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 695
 696   i = 0;
 697   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 698
 699   i = 4;
 700   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 701
 702   g_array_free (garray, TRUE);
 703
 704   /* Testing array of size 3 */
 705   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 3);
 706   for (i = 1; i < 4; i++)
 707     g_array_append_val (garray, i);
 708
 709   for (i = 1; i < 4; i++)
 710     g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 711
 712   i = 0;
 713   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 714
 715   i = 5;
 716   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 717
 718   g_array_free (garray, TRUE);
 719
 720   /* Testing array of size 10000 */
 721   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 10000);
 722
 723   for (i = 1; i < 10001; i++)
 724     g_array_append_val (garray, i);
 725
 726   for (i = 1; i < 10001; i++)
 727     g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 728
 729   for (i = 1; i < 10001; i++)
 730     {
 731       g_assert_true (g_array_binary_search (garray, &i, cmpint, &matched_index));
 732       g_assert_cmpint (i, ==, matched_index + 1);
 733     }
 734
 735   /* Testing negative result */
 736   i = 0;
 737   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 738   g_assert_false (g_array_binary_search (garray, &i, cmpint, &matched_index));
 739
 740   i = 10002;
 741   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 742   g_assert_false (g_array_binary_search (garray, &i, cmpint, &matched_index));
 743
 744   g_array_free (garray, TRUE);
 745
 746   /* Test for a not-found element in the middle of the array. */
 747   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 3);
 748   for (i = 1; i < 10; i += 2)
 749     g_array_append_val (garray, i);
 750
 751   i = 0;
 752   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 753
 754   i = 2;
 755   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 756
 757   i = 10;
 758   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 759
 760   g_array_free (garray, TRUE);
 761 }
 762
 763 static void
 764 pointer_array_add (void)
 765 {
 766   GPtrArray *gparray;
 767   gint i;
 768   gint sum = 0;
 769   gpointer *segment;
 770
 771   gparray = g_ptr_array_sized_new (1000);
 772
 773   for (i = 0; i < 10000; i++)
 774     g_ptr_array_add (gparray, GINT_TO_POINTER (i));
 775
 776   for (i = 0; i < 10000; i++)
 777     g_assert (g_ptr_array_index (gparray, i) == GINT_TO_POINTER (i));
 778
 779   g_ptr_array_foreach (gparray, sum_up, &sum);
 780   g_assert (sum == 49995000);
 781
 782   segment = g_ptr_array_free (gparray, FALSE);
 783   for (i = 0; i < 10000; i++)
 784     g_assert (segment[i] == GINT_TO_POINTER (i));
 785   g_free (segment);
 786 }
 787
 788 static void
 789 pointer_array_insert (void)
 790 {
 791   GPtrArray *gparray;
 792   gint i;
 793   gint sum = 0;
 794   gint index;
 795
 796   gparray = g_ptr_array_sized_new (1000);
 797
 798   for (i = 0; i < 10000; i++)
 799     {
 800       index = g_random_int_range (-1, i + 1);
 801       g_ptr_array_insert (gparray, index, GINT_TO_POINTER (i));
 802     }
 803
 804   g_ptr_array_foreach (gparray, sum_up, &sum);
 805   g_assert (sum == 49995000);
 806
 807   g_ptr_array_free (gparray, TRUE);
 808 }
 809
 810 static void
 811 pointer_array_ref_count (void)
 812 {
 813   GPtrArray *gparray;
 814   GPtrArray *gparray2;
 815   gint i;
 816   gint sum = 0;
 817
 818   gparray = g_ptr_array_new ();
 819   for (i = 0; i < 10000; i++)
 820     g_ptr_array_add (gparray, GINT_TO_POINTER (i));
 821
 822   /* check we can ref, unref and still access the array */
 823   gparray2 = g_ptr_array_ref (gparray);
 824   g_assert (gparray == gparray2);
 825   g_ptr_array_unref (gparray2);
 826   for (i = 0; i < 10000; i++)
 827     g_assert (g_ptr_array_index (gparray, i) == GINT_TO_POINTER (i));
 828
 829   g_ptr_array_foreach (gparray, sum_up, &sum);
 830   g_assert (sum == 49995000);
 831
 832   /* gparray2 should be an empty valid GPtrArray wrapper */
 833   gparray2 = g_ptr_array_ref (gparray);
 834   g_ptr_array_free (gparray, TRUE);
 835
 836   g_assert_cmpint (gparray2->len, ==, 0);
 837   g_ptr_array_unref (gparray2);
 838 }
 839
 840 static gint num_free_func_invocations = 0;
 841
 842 static void
 843 my_free_func (gpointer data)
 844 {
 845   num_free_func_invocations++;
 846   g_free (data);
 847 }
 848
 849 static void
 850 pointer_array_free_func (void)
 851 {
 852   GPtrArray *gparray;
 853   GPtrArray *gparray2;
 854   gchar **strv;
 855   gchar *s;
 856
 857   num_free_func_invocations = 0;
 858   gparray = g_ptr_array_new_with_free_func (my_free_func);
 859   g_ptr_array_unref (gparray);
 860   g_assert_cmpint (num_free_func_invocations, ==, 0);
 861
 862   gparray = g_ptr_array_new_with_free_func (my_free_func);
 863   g_ptr_array_free (gparray, TRUE);
 864   g_assert_cmpint (num_free_func_invocations, ==, 0);
 865
 866   num_free_func_invocations = 0;
 867   gparray = g_ptr_array_new_with_free_func (my_free_func);
 868   g_ptr_array_add (gparray, g_strdup ("foo"));
 869   g_ptr_array_add (gparray, g_strdup ("bar"));
 870   g_ptr_array_add (gparray, g_strdup ("baz"));
 871   g_ptr_array_remove_index (gparray, 0);
 872   g_assert_cmpint (num_free_func_invocations, ==, 1);
 873   g_ptr_array_remove_index_fast (gparray, 1);
 874   g_assert_cmpint (num_free_func_invocations, ==, 2);
 875   s = g_strdup ("frob");
 876   g_ptr_array_add (gparray, s);
 877   g_assert (g_ptr_array_remove (gparray, s));
 878   g_assert (!g_ptr_array_remove (gparray, "nuun"));
 879   g_assert (!g_ptr_array_remove_fast (gparray, "mlo"));
 880   g_assert_cmpint (num_free_func_invocations, ==, 3);
 881   s = g_strdup ("frob");
 882   g_ptr_array_add (gparray, s);
 883   g_ptr_array_set_size (gparray, 1);
 884   g_assert_cmpint (num_free_func_invocations, ==, 4);
 885   g_ptr_array_ref (gparray);
 886   g_ptr_array_unref (gparray);
 887   g_assert_cmpint (num_free_func_invocations, ==, 4);
 888   g_ptr_array_unref (gparray);
 889   g_assert_cmpint (num_free_func_invocations, ==, 5);
 890
 891   num_free_func_invocations = 0;
 892   gparray = g_ptr_array_new_full (10, my_free_func);
 893   g_ptr_array_add (gparray, g_strdup ("foo"));
 894   g_ptr_array_add (gparray, g_strdup ("bar"));
 895   g_ptr_array_add (gparray, g_strdup ("baz"));
 896   g_ptr_array_set_size (gparray, 20);
 897   g_ptr_array_add (gparray, NULL);
 898   gparray2 = g_ptr_array_ref (gparray);
 899   strv = (gchar **) g_ptr_array_free (gparray, FALSE);
 900   g_assert_cmpint (num_free_func_invocations, ==, 0);
 901   g_strfreev (strv);
 902   g_ptr_array_unref (gparray2);
 903   g_assert_cmpint (num_free_func_invocations, ==, 0);
 904
 905   num_free_func_invocations = 0;
 906   gparray = g_ptr_array_new_with_free_func (my_free_func);
 907   g_ptr_array_add (gparray, g_strdup ("foo"));
 908   g_ptr_array_add (gparray, g_strdup ("bar"));
 909   g_ptr_array_add (gparray, g_strdup ("baz"));
 910   g_ptr_array_remove_range (gparray, 1, 1);
 911   g_ptr_array_unref (gparray);
 912   g_assert_cmpint (num_free_func_invocations, ==, 3);
 913
 914   num_free_func_invocations = 0;
 915   gparray = g_ptr_array_new_with_free_func (my_free_func);
 916   g_ptr_array_add (gparray, g_strdup ("foo"));
 917   g_ptr_array_add (gparray, g_strdup ("bar"));
 918   g_ptr_array_add (gparray, g_strdup ("baz"));
 919   g_ptr_array_free (gparray, TRUE);
 920   g_assert_cmpint (num_free_func_invocations, ==, 3);
 921
 922   num_free_func_invocations = 0;
 923   gparray = g_ptr_array_new_with_free_func (my_free_func);
 924   g_ptr_array_add (gparray, "foo");
 925   g_ptr_array_add (gparray, "bar");
 926   g_ptr_array_add (gparray, "baz");
 927   g_ptr_array_set_free_func (gparray, NULL);
 928   g_ptr_array_free (gparray, TRUE);
 929   g_assert_cmpint (num_free_func_invocations, ==, 0);
 930 }
 931
 932 static gpointer
 933 ptr_array_copy_func (gconstpointer src, gpointer userdata)
 934 {
 935   gsize *dst = g_malloc (sizeof (gsize));
 936   *dst = *((gsize *) src);
 937   return dst;
 938 }
 939
 940 /* Test the g_ptr_array_copy() function */
 941 static void
 942 pointer_array_copy (void)
 943 {
 944   GPtrArray *ptr_array, *ptr_array2;
 945   gsize i;
 946   const gsize array_size = 100;
 947   gsize *array_test = g_malloc (array_size * sizeof (gsize));
 948
 949   g_test_summary ("Check all normal behaviour of stealing elements from one "
 950                   "array to append to another, covering different array sizes "
 951                   "and element copy functions");
 952
 953   if (g_test_undefined ())
 954     {
 955       /* Testing degenerated cases */
 956       g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
 957                              "*assertion*!= NULL*");
 958       ptr_array = g_ptr_array_copy (NULL, NULL, NULL);
 959       g_test_assert_expected_messages ();
 960       g_assert_cmpuint ((gsize) ptr_array, ==, (gsize) NULL);
 961     }
 962
 963   /* Initializing array_test */
 964   for (i = 0; i < array_size; i++)
 965     array_test[i] = i;
 966
 967   /* Test copy an empty array */
 968   ptr_array = g_ptr_array_sized_new (0);
 969   ptr_array2 = g_ptr_array_copy (ptr_array, NULL, NULL);
 970
 971   g_assert_cmpuint (ptr_array2->len, ==, ptr_array->len);
 972
 973   g_ptr_array_unref (ptr_array);
 974   g_ptr_array_unref (ptr_array2);
 975
 976   /* Test simple copy */
 977   ptr_array = g_ptr_array_sized_new (array_size);
 978
 979   for (i = 0; i < array_size; i++)
 980     g_ptr_array_add (ptr_array, &array_test[i]);
 981
 982   ptr_array2 = g_ptr_array_copy (ptr_array, NULL, NULL);
 983
 984   g_assert_cmpuint (ptr_array2->len, ==, ptr_array->len);
 985   for (i = 0; i < array_size; i++)
 986     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array2, i)), ==, i);
 987
 988   for (i = 0; i < array_size; i++)
 989     g_assert_cmpuint ((gsize) g_ptr_array_index (ptr_array, i), ==,
 990                       (gsize) g_ptr_array_index (ptr_array2, i));
 991
 992   g_ptr_array_free (ptr_array2, TRUE);
 993
 994   /* Test copy through GCopyFunc */
 995   ptr_array2 = g_ptr_array_copy (ptr_array, ptr_array_copy_func, NULL);
 996   g_ptr_array_set_free_func (ptr_array2, g_free);
 997
 998   g_assert_cmpuint (ptr_array2->len, ==, ptr_array->len);
 999   for (i = 0; i < array_size; i++)
1000     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array2, i)), ==, i);
1001
1002   for (i = 0; i < array_size; i++)
1003     g_assert_cmpuint ((gsize) g_ptr_array_index (ptr_array, i), !=,
1004                       (gsize) g_ptr_array_index (ptr_array2, i));
1005
1006   g_ptr_array_free (ptr_array2, TRUE);
1007
1008   /* Final cleanup */
1009   g_ptr_array_free (ptr_array, TRUE);
1010   g_free (array_test);
1011 }
1012
1013 /* Test the g_ptr_array_extend() function */
1014 static void
1015 pointer_array_extend (void)
1016 {
1017   GPtrArray *ptr_array, *ptr_array2;
1018   gsize i;
1019   const gsize array_size = 100;
1020   gsize *array_test = g_malloc (array_size * sizeof (gsize));
1021
1022   if (g_test_undefined ())
1023     {
1024       /* Testing degenerated cases */
1025       ptr_array = g_ptr_array_sized_new (0);
1026       g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
1027                              "*assertion*!= NULL*");
1028       g_ptr_array_extend (NULL, ptr_array, NULL, NULL);
1029       g_test_assert_expected_messages ();
1030
1031       g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
1032                              "*assertion*!= NULL*");
1033       g_ptr_array_extend (ptr_array, NULL, NULL, NULL);
1034       g_test_assert_expected_messages ();
1035
1036       g_ptr_array_unref (ptr_array);
1037     }
1038
1039   /* Initializing array_test */
1040   for (i = 0; i < array_size; i++)
1041     array_test[i] = i;
1042
1043   /* Testing extend with array of size zero */
1044   ptr_array = g_ptr_array_sized_new (0);
1045   ptr_array2 = g_ptr_array_sized_new (0);
1046
1047   g_ptr_array_extend (ptr_array, ptr_array2, NULL, NULL);
1048
1049   g_assert_cmpuint (ptr_array->len, ==, 0);
1050   g_assert_cmpuint (ptr_array2->len, ==, 0);
1051
1052   g_ptr_array_unref (ptr_array);
1053   g_ptr_array_unref (ptr_array2);
1054
1055   /* Testing extend an array of size zero */
1056   ptr_array = g_ptr_array_sized_new (array_size);
1057   ptr_array2 = g_ptr_array_sized_new (0);
1058
1059   for (i = 0; i < array_size; i++)
1060     {
1061       g_ptr_array_add (ptr_array, &array_test[i]);
1062     }
1063
1064   g_ptr_array_extend (ptr_array, ptr_array2, NULL, NULL);
1065
1066   for (i = 0; i < array_size; i++)
1067     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array, i)), ==, i);
1068
1069   g_ptr_array_unref (ptr_array);
1070   g_ptr_array_unref (ptr_array2);
1071
1072   /* Testing extend an array of size zero */
1073   ptr_array = g_ptr_array_sized_new (0);
1074   ptr_array2 = g_ptr_array_sized_new (array_size);
1075
1076   for (i = 0; i < array_size; i++)
1077     {
1078       g_ptr_array_add (ptr_array2, &array_test[i]);
1079     }
1080
1081   g_ptr_array_extend (ptr_array, ptr_array2, NULL, NULL);
1082
1083   for (i = 0; i < array_size; i++)
1084     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array, i)), ==, i);
1085
1086   g_ptr_array_unref (ptr_array);
1087   g_ptr_array_unref (ptr_array2);
1088
1089   /* Testing simple extend */
1090   ptr_array = g_ptr_array_sized_new (array_size / 2);
1091   ptr_array2 = g_ptr_array_sized_new (array_size / 2);
1092
1093   for (i = 0; i < array_size / 2; i++)
1094     {
1095       g_ptr_array_add (ptr_array, &array_test[i]);
1096       g_ptr_array_add (ptr_array2, &array_test[i + (array_size / 2)]);
1097     }
1098
1099   g_ptr_array_extend (ptr_array, ptr_array2, NULL, NULL);
1100
1101   for (i = 0; i < array_size; i++)
1102     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array, i)), ==, i);
1103
1104   g_ptr_array_unref (ptr_array);
1105   g_ptr_array_unref (ptr_array2);
1106
1107   /* Testing extend with GCopyFunc */
1108   ptr_array = g_ptr_array_sized_new (array_size / 2);
1109   ptr_array2 = g_ptr_array_sized_new (array_size / 2);
1110
1111   for (i = 0; i < array_size / 2; i++)
1112     {
1113       g_ptr_array_add (ptr_array, &array_test[i]);
1114       g_ptr_array_add (ptr_array2, &array_test[i + (array_size / 2)]);
1115     }
1116
1117   g_ptr_array_extend (ptr_array, ptr_array2, ptr_array_copy_func, NULL);
1118
1119   for (i = 0; i < array_size; i++)
1120     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array, i)), ==, i);
1121
1122   /* Clean-up memory */
1123   for (i = array_size / 2; i < array_size; i++)
1124     g_free (g_ptr_array_index (ptr_array, i));
1125
1126   g_ptr_array_unref (ptr_array);
1127   g_ptr_array_unref (ptr_array2);
1128   g_free (array_test);
1129 }
1130
1131 /* Test the g_ptr_array_extend_and_steal() function */
1132 static void
1133 pointer_array_extend_and_steal (void)
1134 {
1135   GPtrArray *ptr_array, *ptr_array2, *ptr_array3;
1136   gsize i;
1137   const gsize array_size = 100;
1138   gsize *array_test = g_malloc (array_size * sizeof (gsize));
1139
1140   /* Initializing array_test */
1141   for (i = 0; i < array_size; i++)
1142     array_test[i] = i;
1143
1144   /* Testing simple extend_and_steal() */
1145   ptr_array = g_ptr_array_sized_new (array_size / 2);
1146   ptr_array2 = g_ptr_array_sized_new (array_size / 2);
1147
1148   for (i = 0; i < array_size / 2; i++)
1149     {
1150       g_ptr_array_add (ptr_array, &array_test[i]);
1151       g_ptr_array_add (ptr_array2, &array_test[i + (array_size / 2)]);
1152     }
1153
1154   g_ptr_array_extend_and_steal (ptr_array, ptr_array2);
1155
1156   for (i = 0; i < array_size; i++)
1157     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array, i)), ==, i);
1158
1159   g_ptr_array_free (ptr_array, TRUE);
1160
1161   /* Testing extend_and_steal() with a pending reference to stolen array */
1162   ptr_array = g_ptr_array_sized_new (array_size / 2);
1163   ptr_array2 = g_ptr_array_sized_new (array_size / 2);
1164
1165   for (i = 0; i < array_size / 2; i++)
1166     {
1167       g_ptr_array_add (ptr_array, &array_test[i]);
1168       g_ptr_array_add (ptr_array2, &array_test[i + (array_size / 2)]);
1169     }
1170
1171   ptr_array3 = g_ptr_array_ref (ptr_array2);
1172
1173   g_ptr_array_extend_and_steal (ptr_array, ptr_array2);
1174
1175   for (i = 0; i < array_size; i++)
1176     g_assert_cmpuint (*((gsize *) g_ptr_array_index (ptr_array, i)), ==, i);
1177
1178   g_assert_cmpuint (ptr_array3->len, ==, 0);
1179   g_assert_null (ptr_array3->pdata);
1180
1181   g_ptr_array_free (ptr_array, TRUE);
1182   g_ptr_array_free (ptr_array3, TRUE);
1183
1184   /* Final memory clean-up */
1185   g_free (array_test);
1186 }
1187
1188 static gint
1189 ptr_compare (gconstpointer p1, gconstpointer p2)
1190 {
1191   gpointer i1 = *(gpointer*)p1;
1192   gpointer i2 = *(gpointer*)p2;
1193
1194   return GPOINTER_TO_INT (i1) - GPOINTER_TO_INT (i2);
1195 }
1196
1197 static gint
1198 ptr_compare_data (gconstpointer p1, gconstpointer p2, gpointer data)
1199 {
1200   gpointer i1 = *(gpointer*)p1;
1201   gpointer i2 = *(gpointer*)p2;
1202
1203   return GPOINTER_TO_INT (i1) - GPOINTER_TO_INT (i2);
1204 }
1205
1206 static void
1207 pointer_array_sort (void)
1208 {
1209   GPtrArray *gparray;
1210   gint i;
1211   gint val;
1212   gint prev, cur;
1213
1214   gparray = g_ptr_array_new ();
1215   for (i = 0; i < 10000; i++)
1216     {
1217       val = g_random_int_range (0, 10000);
1218       g_ptr_array_add (gparray, GINT_TO_POINTER (val));
1219     }
1220
1221   g_ptr_array_sort (gparray, ptr_compare);
1222
1223   prev = -1;
1224   for (i = 0; i < 10000; i++)
1225     {
1226       cur = GPOINTER_TO_INT (g_ptr_array_index (gparray, i));
1227       g_assert_cmpint (prev, <=, cur);
1228       prev = cur;
1229     }
1230
1231   g_ptr_array_free (gparray, TRUE);
1232 }
1233
1234 static void
1235 pointer_array_sort_with_data (void)
1236 {
1237   GPtrArray *gparray;
1238   gint i;
1239   gint prev, cur;
1240
1241   gparray = g_ptr_array_new ();
1242   for (i = 0; i < 10000; i++)
1243     g_ptr_array_add (gparray, GINT_TO_POINTER (g_random_int_range (0, 10000)));
1244
1245   g_ptr_array_sort_with_data (gparray, ptr_compare_data, NULL);
1246
1247   prev = -1;
1248   for (i = 0; i < 10000; i++)
1249     {
1250       cur = GPOINTER_TO_INT (g_ptr_array_index (gparray, i));
1251       g_assert_cmpint (prev, <=, cur);
1252       prev = cur;
1253     }
1254
1255   g_ptr_array_free (gparray, TRUE);
1256 }
1257
1258 static void
1259 pointer_array_find_empty (void)
1260 {
1261   GPtrArray *array;
1262   guint idx;
1263
1264   array = g_ptr_array_new ();
1265
1266   g_assert_false (g_ptr_array_find (array, "some-value", NULL));  /* NULL index */
1267   g_assert_false (g_ptr_array_find (array, "some-value", &idx));  /* non-NULL index */
1268   g_assert_false (g_ptr_array_find_with_equal_func (array, "some-value", g_str_equal, NULL));  /* NULL index */
1269   g_assert_false (g_ptr_array_find_with_equal_func (array, "some-value", g_str_equal, &idx));  /* non-NULL index */
1270
1271   g_ptr_array_free (array, TRUE);
1272 }
1273
1274 static void
1275 pointer_array_find_non_empty (void)
1276 {
1277   GPtrArray *array;
1278   guint idx;
1279   const gchar *str_pointer = "static-string";
1280
1281   array = g_ptr_array_new ();
1282
1283   g_ptr_array_add (array, "some");
1284   g_ptr_array_add (array, "random");
1285   g_ptr_array_add (array, "values");
1286   g_ptr_array_add (array, "some");
1287   g_ptr_array_add (array, "duplicated");
1288   g_ptr_array_add (array, (gpointer) str_pointer);
1289
1290   g_assert_true (g_ptr_array_find_with_equal_func (array, "random", g_str_equal, NULL));  /* NULL index */
1291   g_assert_true (g_ptr_array_find_with_equal_func (array, "random", g_str_equal, &idx));  /* non-NULL index */
1292   g_assert_cmpuint (idx, ==, 1);
1293
1294   g_assert_true (g_ptr_array_find_with_equal_func (array, "some", g_str_equal, &idx));  /* duplicate element */
1295   g_assert_cmpuint (idx, ==, 0);
1296
1297   g_assert_false (g_ptr_array_find_with_equal_func (array, "nope", g_str_equal, NULL));
1298
1299   g_assert_true (g_ptr_array_find_with_equal_func (array, str_pointer, g_str_equal, &idx));
1300   g_assert_cmpuint (idx, ==, 5);
1301   idx = G_MAXUINT;
1302   g_assert_true (g_ptr_array_find_with_equal_func (array, str_pointer, NULL, &idx));  /* NULL equal func */
1303   g_assert_cmpuint (idx, ==, 5);
1304   idx = G_MAXUINT;
1305   g_assert_true (g_ptr_array_find (array, str_pointer, &idx));  /* NULL equal func */
1306   g_assert_cmpuint (idx, ==, 5);
1307
1308   g_ptr_array_free (array, TRUE);
1309 }
1310
1311 static void
1312 steal_destroy_notify (gpointer data)
1313 {
1314   guint *counter = data;
1315   *counter = *counter + 1;
1316 }
1317
1318 /* Test that g_ptr_array_steal_index() and g_ptr_array_steal_index_fast() can
1319  * remove elements from a pointer array without the #GDestroyNotify being called. */
1320 static void
1321 pointer_array_steal (void)
1322 {
1323   guint i1 = 0, i2 = 0, i3 = 0, i4 = 0;
1324   gpointer out1, out2;
1325   GPtrArray *array = g_ptr_array_new_with_free_func (steal_destroy_notify);
1326
1327   g_ptr_array_add (array, &i1);
1328   g_ptr_array_add (array, &i2);
1329   g_ptr_array_add (array, &i3);
1330   g_ptr_array_add (array, &i4);
1331
1332   g_assert_cmpuint (array->len, ==, 4);
1333
1334   /* Remove a single element. */
1335   out1 = g_ptr_array_steal_index (array, 0);
1336   g_assert_true (out1 == &i1);
1337   g_assert_cmpuint (i1, ==, 0);  /* should not have been destroyed */
1338
1339   /* Following elements should have been moved down. */
1340   g_assert_cmpuint (array->len, ==, 3);
1341   g_assert_true (g_ptr_array_index (array, 0) == &i2);
1342   g_assert_true (g_ptr_array_index (array, 1) == &i3);
1343   g_assert_true (g_ptr_array_index (array, 2) == &i4);
1344
1345   /* Remove another element, quickly. */
1346   out2 = g_ptr_array_steal_index_fast (array, 0);
1347   g_assert_true (out2 == &i2);
1348   g_assert_cmpuint (i2, ==, 0);  /* should not have been destroyed */
1349
1350   /* Last element should have been swapped in place. */
1351   g_assert_cmpuint (array->len, ==, 2);
1352   g_assert_true (g_ptr_array_index (array, 0) == &i4);
1353   g_assert_true (g_ptr_array_index (array, 1) == &i3);
1354
1355   /* Check that destroying the pointer array doesn’t affect the stolen elements. */
1356   g_ptr_array_unref (array);
1357
1358   g_assert_cmpuint (i1, ==, 0);
1359   g_assert_cmpuint (i2, ==, 0);
1360   g_assert_cmpuint (i3, ==, 1);
1361   g_assert_cmpuint (i4, ==, 1);
1362 }
1363
1364 static void
1365 byte_array_append (void)
1366 {
1367   GByteArray *gbarray;
1368   gint i;
1369   guint8 *segment;
1370
1371   gbarray = g_byte_array_sized_new (1000);
1372   for (i = 0; i < 10000; i++)
1373     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
1374
1375   for (i = 0; i < 10000; i++)
1376     {
1377       g_assert (gbarray->data[4*i] == 'a');
1378       g_assert (gbarray->data[4*i+1] == 'b');
1379       g_assert (gbarray->data[4*i+2] == 'c');
1380       g_assert (gbarray->data[4*i+3] == 'd');
1381     }
1382
1383   segment = g_byte_array_free (gbarray, FALSE);
1384
1385   for (i = 0; i < 10000; i++)
1386     {
1387       g_assert (segment[4*i] == 'a');
1388       g_assert (segment[4*i+1] == 'b');
1389       g_assert (segment[4*i+2] == 'c');
1390       g_assert (segment[4*i+3] == 'd');
1391     }
1392
1393   g_free (segment);
1394 }
1395
1396 static void
1397 byte_array_prepend (void)
1398 {
1399   GByteArray *gbarray;
1400   gint i;
1401
1402   gbarray = g_byte_array_new ();
1403   g_byte_array_set_size (gbarray, 1000);
1404
1405   for (i = 0; i < 10000; i++)
1406     g_byte_array_prepend (gbarray, (guint8*) "abcd", 4);
1407
1408   for (i = 0; i < 10000; i++)
1409     {
1410       g_assert (gbarray->data[4*i] == 'a');
1411       g_assert (gbarray->data[4*i+1] == 'b');
1412       g_assert (gbarray->data[4*i+2] == 'c');
1413       g_assert (gbarray->data[4*i+3] == 'd');
1414     }
1415
1416   g_byte_array_free (gbarray, TRUE);
1417 }
1418
1419 static void
1420 byte_array_ref_count (void)
1421 {
1422   GByteArray *gbarray;
1423   GByteArray *gbarray2;
1424   gint i;
1425
1426   gbarray = g_byte_array_new ();
1427   for (i = 0; i < 10000; i++)
1428     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
1429
1430   gbarray2 = g_byte_array_ref (gbarray);
1431   g_assert (gbarray2 == gbarray);
1432   g_byte_array_unref (gbarray2);
1433   for (i = 0; i < 10000; i++)
1434     {
1435       g_assert (gbarray->data[4*i] == 'a');
1436       g_assert (gbarray->data[4*i+1] == 'b');
1437       g_assert (gbarray->data[4*i+2] == 'c');
1438       g_assert (gbarray->data[4*i+3] == 'd');
1439     }
1440
1441   gbarray2 = g_byte_array_ref (gbarray);
1442   g_assert (gbarray2 == gbarray);
1443   g_byte_array_free (gbarray, TRUE);
1444   g_assert_cmpint (gbarray2->len, ==, 0);
1445   g_byte_array_unref (gbarray2);
1446 }
1447
1448 static void
1449 byte_array_remove (void)
1450 {
1451   GByteArray *gbarray;
1452   gint i;
1453
1454   gbarray = g_byte_array_new ();
1455   for (i = 0; i < 100; i++)
1456     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
1457
1458   g_assert_cmpint (gbarray->len, ==, 400);
1459
1460   g_byte_array_remove_index (gbarray, 4);
1461   g_byte_array_remove_index (gbarray, 4);
1462   g_byte_array_remove_index (gbarray, 4);
1463   g_byte_array_remove_index (gbarray, 4);
1464
1465   g_assert_cmpint (gbarray->len, ==, 396);
1466
1467   for (i = 0; i < 99; i++)
1468     {
1469       g_assert (gbarray->data[4*i] == 'a');
1470       g_assert (gbarray->data[4*i+1] == 'b');
1471       g_assert (gbarray->data[4*i+2] == 'c');
1472       g_assert (gbarray->data[4*i+3] == 'd');
1473     }
1474
1475   g_byte_array_free (gbarray, TRUE);
1476 }
1477
1478 static void
1479 byte_array_remove_fast (void)
1480 {
1481   GByteArray *gbarray;
1482   gint i;
1483
1484   gbarray = g_byte_array_new ();
1485   for (i = 0; i < 100; i++)
1486     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
1487
1488   g_assert_cmpint (gbarray->len, ==, 400);
1489
1490   g_byte_array_remove_index_fast (gbarray, 4);
1491   g_byte_array_remove_index_fast (gbarray, 4);
1492   g_byte_array_remove_index_fast (gbarray, 4);
1493   g_byte_array_remove_index_fast (gbarray, 4);
1494
1495   g_assert_cmpint (gbarray->len, ==, 396);
1496
1497   for (i = 0; i < 99; i++)
1498     {
1499       g_assert (gbarray->data[4*i] == 'a');
1500       g_assert (gbarray->data[4*i+1] == 'b');
1501       g_assert (gbarray->data[4*i+2] == 'c');
1502       g_assert (gbarray->data[4*i+3] == 'd');
1503     }
1504
1505   g_byte_array_free (gbarray, TRUE);
1506 }
1507
1508 static void
1509 byte_array_remove_range (void)
1510 {
1511   GByteArray *gbarray;
1512   gint i;
1513
1514   gbarray = g_byte_array_new ();
1515   for (i = 0; i < 100; i++)
1516     g_byte_array_append (gbarray, (guint8*) "abcd", 4);
1517
1518   g_assert_cmpint (gbarray->len, ==, 400);
1519
1520   g_byte_array_remove_range (gbarray, 12, 4);
1521
1522   g_assert_cmpint (gbarray->len, ==, 396);
1523
1524   for (i = 0; i < 99; i++)
1525     {
1526       g_assert (gbarray->data[4*i] == 'a');
1527       g_assert (gbarray->data[4*i+1] == 'b');
1528       g_assert (gbarray->data[4*i+2] == 'c');
1529       g_assert (gbarray->data[4*i+3] == 'd');
1530     }
1531
1532   /* Ensure the entire array can be cleared, even when empty. */
1533   g_byte_array_remove_range (gbarray, 0, gbarray->len);
1534   g_byte_array_remove_range (gbarray, 0, gbarray->len);
1535
1536   g_byte_array_free (gbarray, TRUE);
1537 }
1538
1539 static int
1540 byte_compare (gconstpointer p1, gconstpointer p2)
1541 {
1542   const guint8 *i1 = p1;
1543   const guint8 *i2 = p2;
1544
1545   return *i1 - *i2;
1546 }
1547
1548 static int
1549 byte_compare_data (gconstpointer p1, gconstpointer p2, gpointer data)
1550 {
1551   const guint8 *i1 = p1;
1552   const guint8 *i2 = p2;
1553
1554   return *i1 - *i2;
1555 }
1556
1557 static void
1558 byte_array_sort (void)
1559 {
1560   GByteArray *gbarray;
1561   gint i;
1562   guint8 val;
1563   guint8 prev, cur;
1564
1565   gbarray = g_byte_array_new ();
1566   for (i = 0; i < 100; i++)
1567     {
1568       val = 'a' + g_random_int_range (0, 26);
1569       g_byte_array_append (gbarray, (guint8*) &val, 1);
1570     }
1571
1572   g_byte_array_sort (gbarray, byte_compare);
1573
1574   prev = 'a';
1575   for (i = 0; i < gbarray->len; i++)
1576     {
1577       cur = gbarray->data[i];
1578       g_assert_cmpint (prev, <=, cur);
1579       prev = cur;
1580     }
1581
1582   g_byte_array_free (gbarray, TRUE);
1583 }
1584
1585 static void
1586 byte_array_sort_with_data (void)
1587 {
1588   GByteArray *gbarray;
1589   gint i;
1590   guint8 val;
1591   guint8 prev, cur;
1592
1593   gbarray = g_byte_array_new ();
1594   for (i = 0; i < 100; i++)
1595     {
1596       val = 'a' + g_random_int_range (0, 26);
1597       g_byte_array_append (gbarray, (guint8*) &val, 1);
1598     }
1599
1600   g_byte_array_sort_with_data (gbarray, byte_compare_data, NULL);
1601
1602   prev = 'a';
1603   for (i = 0; i < gbarray->len; i++)
1604     {
1605       cur = gbarray->data[i];
1606       g_assert_cmpint (prev, <=, cur);
1607       prev = cur;
1608     }
1609
1610   g_byte_array_free (gbarray, TRUE);
1611 }
1612
1613 static void
1614 byte_array_new_take (void)
1615 {
1616   GByteArray *gbarray;
1617   guint8 *data;
1618
1619   data = g_memdup ("woooweeewow", 11);
1620   gbarray = g_byte_array_new_take (data, 11);
1621   g_assert (gbarray->data == data);
1622   g_assert_cmpuint (gbarray->len, ==, 11);
1623   g_byte_array_free (gbarray, TRUE);
1624 }
1625
1626 static void
1627 byte_array_free_to_bytes (void)
1628 {
1629   GByteArray *gbarray;
1630   gpointer memory;
1631   GBytes *bytes;
1632   gsize size;
1633
1634   gbarray = g_byte_array_new ();
1635   g_byte_array_append (gbarray, (guint8 *)"woooweeewow", 11);
1636   memory = gbarray->data;
1637
1638   bytes = g_byte_array_free_to_bytes (gbarray);
1639   g_assert (bytes != NULL);
1640   g_assert_cmpuint (g_bytes_get_size (bytes), ==, 11);
1641   g_assert (g_bytes_get_data (bytes, &size) == memory);
1642   g_assert_cmpuint (size, ==, 11);
1643
1644   g_bytes_unref (bytes);
1645 }
1646
1647 static void
1648 add_array_test (const gchar         *test_path,
1649                 const ArrayTestData *config,
1650                 GTestDataFunc        test_func)
1651 {
1652   gchar *test_name = NULL;
1653
1654   test_name = g_strdup_printf ("%s/%s-%s",
1655                                test_path,
1656                                config->zero_terminated ? "zero-terminated" : "non-zero-terminated",
1657                                config->clear_ ? "clear" : "no-clear");
1658   g_test_add_data_func (test_name, config, test_func);
1659   g_free (test_name);
1660 }
1661
1662 int
1663 main (int argc, char *argv[])
1664 {
1665   /* Test all possible combinations of g_array_new() parameters. */
1666   const ArrayTestData array_configurations[] =
1667     {
1668       { FALSE, FALSE },
1669       { FALSE, TRUE },
1670       { TRUE, FALSE },
1671       { TRUE, TRUE },
1672     };
1673   gsize i;
1674
1675   g_test_init (&argc, &argv, NULL);
1676
1677   g_test_bug_base ("https://bugzilla.gnome.org/");
1678
1679   /* array tests */
1680   g_test_add_func ("/array/new/zero-terminated", array_new_zero_terminated);
1681   g_test_add_func ("/array/ref-count", array_ref_count);
1682   g_test_add_func ("/array/clear-func", array_clear_func);
1683   g_test_add_func ("/array/binary-search", test_array_binary_search);
1684
1685   for (i = 0; i < G_N_ELEMENTS (array_configurations); i++)
1686     {
1687       add_array_test ("/array/set-size", &array_configurations[i], array_set_size);
1688       add_array_test ("/array/set-size/sized", &array_configurations[i], array_set_size_sized);
1689       add_array_test ("/array/append-val", &array_configurations[i], array_append_val);
1690       add_array_test ("/array/prepend-val", &array_configurations[i], array_prepend_val);
1691       add_array_test ("/array/prepend-vals", &array_configurations[i], array_prepend_vals);
1692       add_array_test ("/array/insert-vals", &array_configurations[i], array_insert_vals);
1693       add_array_test ("/array/remove-index", &array_configurations[i], array_remove_index);
1694       add_array_test ("/array/remove-index-fast", &array_configurations[i], array_remove_index_fast);
1695       add_array_test ("/array/remove-range", &array_configurations[i], array_remove_range);
1696       add_array_test ("/array/copy", &array_configurations[i], array_copy);
1697       add_array_test ("/array/sort", &array_configurations[i], array_sort);
1698       add_array_test ("/array/sort-with-data", &array_configurations[i], array_sort_with_data);
1699     }
1700
1701   /* pointer arrays */
1702   g_test_add_func ("/pointerarray/add", pointer_array_add);
1703   g_test_add_func ("/pointerarray/insert", pointer_array_insert);
1704   g_test_add_func ("/pointerarray/ref-count", pointer_array_ref_count);
1705   g_test_add_func ("/pointerarray/free-func", pointer_array_free_func);
1706   g_test_add_func ("/pointerarray/array_copy", pointer_array_copy);
1707   g_test_add_func ("/pointerarray/array_extend", pointer_array_extend);
1708   g_test_add_func ("/pointerarray/array_extend_and_steal", pointer_array_extend_and_steal);
1709   g_test_add_func ("/pointerarray/sort", pointer_array_sort);
1710   g_test_add_func ("/pointerarray/sort-with-data", pointer_array_sort_with_data);
1711   g_test_add_func ("/pointerarray/find/empty", pointer_array_find_empty);
1712   g_test_add_func ("/pointerarray/find/non-empty", pointer_array_find_non_empty);
1713   g_test_add_func ("/pointerarray/steal", pointer_array_steal);
1714
1715   /* byte arrays */
1716   g_test_add_func ("/bytearray/append", byte_array_append);
1717   g_test_add_func ("/bytearray/prepend", byte_array_prepend);
1718   g_test_add_func ("/bytearray/remove", byte_array_remove);
1719   g_test_add_func ("/bytearray/remove-fast", byte_array_remove_fast);
1720   g_test_add_func ("/bytearray/remove-range", byte_array_remove_range);
1721   g_test_add_func ("/bytearray/ref-count", byte_array_ref_count);
1722   g_test_add_func ("/bytearray/sort", byte_array_sort);
1723   g_test_add_func ("/bytearray/sort-with-data", byte_array_sort_with_data);
1724   g_test_add_func ("/bytearray/new-take", byte_array_new_take);
1725   g_test_add_func ("/bytearray/free-to-bytes", byte_array_free_to_bytes);
1726
1727   return g_test_run ();
1728 }
1729