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