glib/tests/list.c

   1 #include <glib.h>
   2 #include <stdlib.h>
   3
   4 #define SIZE       50
   5 #define NUMBER_MIN 0000
   6 #define NUMBER_MAX 9999
   7
   8
   9 static guint32 array[SIZE];
  10
  11
  12 static gint
  13 sort (gconstpointer p1, gconstpointer p2)
  14 {
  15   gint32 a, b;
  16
  17   a = GPOINTER_TO_INT (p1);
  18   b = GPOINTER_TO_INT (p2);
  19
  20   return (a > b ? +1 : a == b ? 0 : -1);
  21 }
  22
  23 /*
  24  * glist sort tests
  25  */
  26 static void
  27 test_list_sort (void)
  28 {
  29   GList *list = NULL;
  30   gint   i;
  31
  32   for (i = 0; i < SIZE; i++)
  33     list = g_list_append (list, GINT_TO_POINTER (array[i]));
  34
  35   list = g_list_sort (list, sort);
  36   for (i = 0; i < SIZE - 1; i++)
  37     {
  38       gpointer p1, p2;
  39
  40       p1 = g_list_nth_data (list, i);
  41       p2 = g_list_nth_data (list, i+1);
  42
  43       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
  44     }
  45
  46   g_list_free (list);
  47 }
  48
  49 static void
  50 test_list_sort_with_data (void)
  51 {
  52   GList *list = NULL;
  53   gint   i;
  54
  55   for (i = 0; i < SIZE; i++)
  56     list = g_list_append (list, GINT_TO_POINTER (array[i]));
  57
  58   list = g_list_sort_with_data (list, (GCompareDataFunc)sort, NULL);
  59   for (i = 0; i < SIZE - 1; i++)
  60     {
  61       gpointer p1, p2;
  62
  63       p1 = g_list_nth_data (list, i);
  64       p2 = g_list_nth_data (list, i+1);
  65
  66       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
  67     }
  68
  69   g_list_free (list);
  70 }
  71
  72 /* Test that the sort is stable. */
  73 static void
  74 test_list_sort_stable (void)
  75 {
  76   GList *list = NULL;  /* (element-type utf8) */
  77   GList *copy = NULL;  /* (element-type utf8) */
  78   gsize i;
  79
  80   /* Build a test list, already ordered. */
  81   for (i = 0; i < SIZE; i++)
  82     list = g_list_append (list, g_strdup_printf ("%" G_GSIZE_FORMAT, i / 5));
  83
  84   /* Take a copy and sort it. */
  85   copy = g_list_copy (list);
  86   copy = g_list_sort (copy, (GCompareFunc) g_strcmp0);
  87
  88   /* Compare the two lists, checking pointers are equal to ensure the elements
  89    * have been kept stable. */
  90   for (i = 0; i < SIZE; i++)
  91     {
  92       gpointer p1, p2;
  93
  94       p1 = g_list_nth_data (list, i);
  95       p2 = g_list_nth_data (list, i);
  96
  97       g_assert (p1 == p2);
  98     }
  99
 100   g_list_free (copy);
 101   g_list_free_full (list, g_free);
 102 }
 103
 104 static void
 105 test_list_insert_sorted (void)
 106 {
 107   GList *list = NULL;
 108   gint   i;
 109
 110   for (i = 0; i < SIZE; i++)
 111     list = g_list_insert_sorted (list, GINT_TO_POINTER (array[i]), sort);
 112
 113   for (i = 0; i < SIZE - 1; i++)
 114     {
 115       gpointer p1, p2;
 116
 117       p1 = g_list_nth_data (list, i);
 118       p2 = g_list_nth_data (list, i+1);
 119
 120       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
 121     }
 122
 123   g_list_free (list);
 124 }
 125
 126 static void
 127 test_list_insert_sorted_with_data (void)
 128 {
 129   GList *list = NULL;
 130   gint   i;
 131
 132   for (i = 0; i < SIZE; i++)
 133     list = g_list_insert_sorted_with_data (list,
 134                                            GINT_TO_POINTER (array[i]),
 135                                            (GCompareDataFunc)sort,
 136                                            NULL);
 137
 138   for (i = 0; i < SIZE - 1; i++)
 139     {
 140       gpointer p1, p2;
 141
 142       p1 = g_list_nth_data (list, i);
 143       p2 = g_list_nth_data (list, i+1);
 144
 145       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
 146     }
 147
 148   g_list_free (list);
 149 }
 150
 151 static void
 152 test_list_reverse (void)
 153 {
 154   GList *list = NULL;
 155   GList *st;
 156   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 157   gint   i;
 158
 159   for (i = 0; i < 10; i++)
 160     list = g_list_append (list, &nums[i]);
 161
 162   list = g_list_reverse (list);
 163
 164   for (i = 0; i < 10; i++)
 165     {
 166       st = g_list_nth (list, i);
 167       g_assert (*((gint*) st->data) == (9 - i));
 168     }
 169
 170   g_list_free (list);
 171 }
 172
 173 static void
 174 test_list_nth (void)
 175 {
 176   GList *list = NULL;
 177   GList *st;
 178   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 179   gint   i;
 180
 181   for (i = 0; i < 10; i++)
 182     list = g_list_append (list, &nums[i]);
 183
 184   for (i = 0; i < 10; i++)
 185     {
 186       st = g_list_nth (list, i);
 187       g_assert (*((gint*) st->data) == i);
 188     }
 189
 190   g_list_free (list);
 191 }
 192
 193 static void
 194 test_list_concat (void)
 195 {
 196   GList *list1 = NULL;
 197   GList *list2 = NULL;
 198   GList *st;
 199   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 200   gint i;
 201
 202   for (i = 0; i < 5; i++)
 203     {
 204       list1 = g_list_append (list1, &nums[i]);
 205       list2 = g_list_append (list2, &nums[i+5]);
 206     }
 207
 208   g_assert_cmpint (g_list_length (list1), ==, 5);
 209   g_assert_cmpint (g_list_length (list2), ==, 5);
 210
 211   list1 = g_list_concat (list1, list2);
 212
 213   g_assert_cmpint (g_list_length (list1), ==, 10);
 214
 215   for (i = 0; i < 10; i++)
 216     {
 217       st = g_list_nth (list1, i);
 218       g_assert (*((gint*) st->data) == i);
 219     }
 220
 221   list2 = g_list_concat (NULL, list1);
 222   g_assert_cmpint (g_list_length (list2), ==, 10);
 223
 224   list2 = g_list_concat (list1, NULL);
 225   g_assert_cmpint (g_list_length (list2), ==, 10);
 226
 227   list2 = g_list_concat (NULL, NULL);
 228   g_assert (list2 == NULL);
 229
 230   g_list_free (list1);
 231 }
 232
 233 static void
 234 test_list_remove (void)
 235 {
 236   GList *list = NULL;
 237   GList *st;
 238   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 239   gint   i;
 240
 241   for (i = 0; i < 10; i++)
 242     {
 243       list = g_list_append (list, &nums[i]);
 244       list = g_list_append (list, &nums[i]);
 245     }
 246
 247   g_assert_cmpint (g_list_length (list), ==, 20);
 248
 249   for (i = 0; i < 10; i++)
 250     {
 251       list = g_list_remove (list, &nums[i]);
 252     }
 253
 254   g_assert_cmpint (g_list_length (list), ==, 10);
 255
 256   for (i = 0; i < 10; i++)
 257     {
 258       st = g_list_nth (list, i);
 259       g_assert (*((gint*) st->data) == i);
 260     }
 261
 262   g_list_free (list);
 263 }
 264
 265 static void
 266 test_list_remove_all (void)
 267 {
 268   GList *list = NULL;
 269   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 270   gint   i;
 271
 272   for (i = 0; i < 10; i++)
 273     {
 274       list = g_list_append (list, &nums[i]);
 275       list = g_list_append (list, &nums[i]);
 276     }
 277
 278   g_assert_cmpint (g_list_length (list), ==, 20);
 279
 280   for (i = 0; i < 5; i++)
 281     {
 282       list = g_list_remove_all (list, &nums[2 * i + 1]);
 283       list = g_list_remove_all (list, &nums[8 - 2 * i]);
 284     }
 285
 286   g_assert_cmpint (g_list_length (list), ==, 0);
 287   g_assert (list == NULL);
 288 }
 289
 290 static void
 291 test_list_first_last (void)
 292 {
 293   GList *list = NULL;
 294   GList *st;
 295   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 296   gint   i;
 297
 298   for (i = 0; i < 10; i++)
 299     list = g_list_append (list, &nums[i]);
 300
 301   st = g_list_last (list);
 302   g_assert (*((gint*) st->data) == 9);
 303   st = g_list_nth_prev (st, 3);
 304   g_assert (*((gint*) st->data) == 6);
 305   st = g_list_first (st);
 306   g_assert (*((gint*) st->data) == 0);
 307
 308   g_list_free (list);
 309 }
 310
 311 static void
 312 test_list_insert (void)
 313 {
 314   GList *list = NULL;
 315   GList *st;
 316   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 317   gint   i;
 318
 319   list = g_list_insert_before (NULL, NULL, &nums[1]);
 320   list = g_list_insert (list, &nums[3], 1);
 321   list = g_list_insert (list, &nums[4], -1);
 322   list = g_list_insert (list, &nums[0], 0);
 323   list = g_list_insert (list, &nums[5], 100);
 324   list = g_list_insert_before (list, NULL, &nums[6]);
 325   list = g_list_insert_before (list, list->next->next, &nums[2]);
 326
 327   list = g_list_insert (list, &nums[9], 7);
 328   list = g_list_insert (list, &nums[8], 7);
 329   list = g_list_insert (list, &nums[7], 7);
 330
 331   for (i = 0; i < 10; i++)
 332     {
 333       st = g_list_nth (list, i);
 334       g_assert (*((gint*) st->data) == i);
 335     }
 336
 337   g_list_free (list);
 338 }
 339
 340 typedef struct
 341 {
 342   gboolean freed;
 343   int x;
 344 } ListItem;
 345
 346 static void
 347 free_func (gpointer data)
 348 {
 349   ListItem *item = data;
 350
 351   item->freed = TRUE;
 352 }
 353
 354 static ListItem *
 355 new_item (int x)
 356 {
 357   ListItem *item;
 358
 359   item = g_slice_new (ListItem);
 360   item->freed = FALSE;
 361   item->x = x;
 362
 363   return item;
 364 }
 365
 366 static void
 367 test_free_full (void)
 368 {
 369   ListItem *one, *two, *three;
 370   GSList *slist = NULL;
 371   GList *list = NULL;
 372
 373   slist = g_slist_prepend (slist, one = new_item (1));
 374   slist = g_slist_prepend (slist, two = new_item (2));
 375   slist = g_slist_prepend (slist, three = new_item (3));
 376   g_assert (!one->freed);
 377   g_assert (!two->freed);
 378   g_assert (!three->freed);
 379   g_slist_free_full (slist, free_func);
 380   g_assert (one->freed);
 381   g_assert (two->freed);
 382   g_assert (three->freed);
 383   g_slice_free (ListItem, one);
 384   g_slice_free (ListItem, two);
 385   g_slice_free (ListItem, three);
 386
 387   list = g_list_prepend (list, one = new_item (1));
 388   list = g_list_prepend (list, two = new_item (2));
 389   list = g_list_prepend (list, three = new_item (3));
 390   g_assert (!one->freed);
 391   g_assert (!two->freed);
 392   g_assert (!three->freed);
 393   g_list_free_full (list, free_func);
 394   g_assert (one->freed);
 395   g_assert (two->freed);
 396   g_assert (three->freed);
 397   g_slice_free (ListItem, one);
 398   g_slice_free (ListItem, two);
 399   g_slice_free (ListItem, three);
 400 }
 401
 402 static void
 403 test_list_copy (void)
 404 {
 405   GList *l, *l2;
 406   GList *u, *v;
 407
 408   l = NULL;
 409   l = g_list_append (l, GINT_TO_POINTER (1));
 410   l = g_list_append (l, GINT_TO_POINTER (2));
 411   l = g_list_append (l, GINT_TO_POINTER (3));
 412
 413   l2 = g_list_copy (l);
 414
 415   for (u = l, v = l2; u && v; u = u->next, v = v->next)
 416     {
 417       g_assert (u->data == v->data);
 418     }
 419
 420   g_list_free (l);
 421   g_list_free (l2);
 422 }
 423
 424 static gpointer
 425 multiply_value (gconstpointer value, gpointer data)
 426 {
 427   return GINT_TO_POINTER (GPOINTER_TO_INT (value) * GPOINTER_TO_INT (data));
 428 }
 429
 430 static void
 431 test_list_copy_deep (void)
 432 {
 433   GList *l, *l2;
 434   GList *u, *v;
 435
 436   l = NULL;
 437   l = g_list_append (l, GINT_TO_POINTER (1));
 438   l = g_list_append (l, GINT_TO_POINTER (2));
 439   l = g_list_append (l, GINT_TO_POINTER (3));
 440
 441   l2 = g_list_copy_deep (l, multiply_value, GINT_TO_POINTER (2));
 442
 443   for (u = l, v = l2; u && v; u = u->next, v = v->next)
 444     {
 445       g_assert_cmpint (GPOINTER_TO_INT (u->data) * 2, ==, GPOINTER_TO_INT (v->data));
 446     }
 447
 448   g_list_free (l);
 449   g_list_free (l2);
 450 }
 451
 452 static void
 453 test_delete_link (void)
 454 {
 455   GList *l, *l2;
 456
 457   l = NULL;
 458   l = g_list_append (l, GINT_TO_POINTER (1));
 459   l = g_list_append (l, GINT_TO_POINTER (2));
 460   l = g_list_append (l, GINT_TO_POINTER (3));
 461
 462   l2 = l->next;
 463
 464   l = g_list_delete_link (l, l2);
 465   g_assert (l->data == GINT_TO_POINTER (1));
 466   g_assert (l->next->data == GINT_TO_POINTER (3));
 467
 468   g_list_free (l);
 469 }
 470
 471 static void
 472 test_prepend (void)
 473 {
 474   GList *l, *l2;
 475
 476   l = NULL;
 477   l = g_list_prepend (l, "c");
 478   l = g_list_prepend (l, "a");
 479
 480   g_assert (l->data == (gpointer)"a");
 481   g_assert (l->next->data == (gpointer)"c");
 482   g_assert (l->next->next == NULL);
 483
 484   l2 = l->next;
 485   l2 = g_list_prepend (l2, "b");
 486   g_assert (l2->prev == l);
 487
 488   g_assert (l->data == (gpointer)"a");
 489   g_assert (l->next->data == (gpointer)"b");
 490   g_assert (l->next->next->data == (gpointer)"c");
 491   g_assert (l->next->next->next == NULL);
 492
 493   g_list_free (l);
 494 }
 495
 496 static void
 497 test_position (void)
 498 {
 499   GList *l, *ll;
 500
 501   l = NULL;
 502   l = g_list_append (l, "a");
 503   l = g_list_append (l, "b");
 504   l = g_list_append (l, "c");
 505
 506   ll = g_list_find (l, "a");
 507   g_assert_cmpint (g_list_position (l, ll), ==, 0);
 508   g_assert_cmpint (g_list_index (l, "a"), ==, 0);
 509   ll = g_list_find (l, "b");
 510   g_assert_cmpint (g_list_position (l, ll), ==, 1);
 511   g_assert_cmpint (g_list_index (l, "b"), ==, 1);
 512   ll = g_list_find (l, "c");
 513   g_assert_cmpint (g_list_position (l, ll), ==, 2);
 514   g_assert_cmpint (g_list_index (l, "c"), ==, 2);
 515
 516   ll = g_list_append (NULL, "d");
 517   g_assert_cmpint (g_list_position (l, ll), ==, -1);
 518   g_assert_cmpint (g_list_index (l, "d"), ==, -1);
 519
 520   g_list_free (l);
 521   g_list_free (ll);
 522 }
 523
 524 static void
 525 test_double_free (void)
 526 {
 527   GList *list, *link;
 528   GList  intruder = { NULL, (gpointer)0xDEADBEEF, (gpointer)0xDEADBEEF };
 529
 530   if (g_test_subprocess ())
 531     {
 532       list = NULL;
 533       list = g_list_append (list, "a");
 534       link = list = g_list_append (list, "b");
 535       list = g_list_append (list, "c");
 536
 537       list = g_list_remove_link (list, link);
 538       link->prev = list;
 539       link->next = &intruder;
 540       list = g_list_remove_link (list, link);
 541
 542       g_list_free (list);
 543       return;
 544     }
 545
 546   g_test_trap_subprocess (NULL, 0, 0);
 547   g_test_trap_assert_failed ();
 548   g_test_trap_assert_stderr ("*corrupted double-linked list detected*");
 549 }
 550
 551 int
 552 main (int argc, char *argv[])
 553 {
 554   gint i;
 555
 556   g_test_init (&argc, &argv, NULL);
 557
 558   /* Create an array of random numbers. */
 559   for (i = 0; i < SIZE; i++)
 560     array[i] = g_test_rand_int_range (NUMBER_MIN, NUMBER_MAX);
 561
 562   g_test_add_func ("/list/sort", test_list_sort);
 563   g_test_add_func ("/list/sort-with-data", test_list_sort_with_data);
 564   g_test_add_func ("/list/sort/stable", test_list_sort_stable);
 565   g_test_add_func ("/list/insert-sorted", test_list_insert_sorted);
 566   g_test_add_func ("/list/insert-sorted-with-data", test_list_insert_sorted_with_data);
 567   g_test_add_func ("/list/reverse", test_list_reverse);
 568   g_test_add_func ("/list/nth", test_list_nth);
 569   g_test_add_func ("/list/concat", test_list_concat);
 570   g_test_add_func ("/list/remove", test_list_remove);
 571   g_test_add_func ("/list/remove-all", test_list_remove_all);
 572   g_test_add_func ("/list/first-last", test_list_first_last);
 573   g_test_add_func ("/list/insert", test_list_insert);
 574   g_test_add_func ("/list/free-full", test_free_full);
 575   g_test_add_func ("/list/copy", test_list_copy);
 576   g_test_add_func ("/list/copy-deep", test_list_copy_deep);
 577   g_test_add_func ("/list/delete-link", test_delete_link);
 578   g_test_add_func ("/list/prepend", test_prepend);
 579   g_test_add_func ("/list/position", test_position);
 580   g_test_add_func ("/list/double-free", test_double_free);
 581
 582   return g_test_run ();
 583 }