glib/tests/slist.c

   1 #include <glib.h>
   2
   3 #define SIZE       50
   4 #define NUMBER_MIN 0000
   5 #define NUMBER_MAX 9999
   6
   7
   8 static guint32 array[SIZE];
   9
  10
  11 static gint
  12 sort (gconstpointer p1, gconstpointer p2)
  13 {
  14   gint32 a, b;
  15
  16   a = GPOINTER_TO_INT (p1);
  17   b = GPOINTER_TO_INT (p2);
  18
  19   return (a > b ? +1 : a == b ? 0 : -1);
  20 }
  21
  22 /*
  23  * gslist sort tests
  24  */
  25 static void
  26 test_slist_sort (void)
  27 {
  28   GSList *slist = NULL;
  29   gint    i;
  30
  31   for (i = 0; i < SIZE; i++)
  32     slist = g_slist_append (slist, GINT_TO_POINTER (array[i]));
  33
  34   slist = g_slist_sort (slist, sort);
  35   for (i = 0; i < SIZE - 1; i++)
  36     {
  37       gpointer p1, p2;
  38
  39       p1 = g_slist_nth_data (slist, i);
  40       p2 = g_slist_nth_data (slist, i+1);
  41
  42       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
  43     }
  44
  45   g_slist_free (slist);
  46 }
  47
  48 static void
  49 test_slist_sort_with_data (void)
  50 {
  51   GSList *slist = NULL;
  52   gint    i;
  53
  54   for (i = 0; i < SIZE; i++)
  55     slist = g_slist_append (slist, GINT_TO_POINTER (array[i]));
  56
  57   slist = g_slist_sort_with_data (slist, (GCompareDataFunc)sort, NULL);
  58   for (i = 0; i < SIZE - 1; i++)
  59     {
  60       gpointer p1, p2;
  61
  62       p1 = g_slist_nth_data (slist, i);
  63       p2 = g_slist_nth_data (slist, i+1);
  64
  65       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
  66     }
  67
  68   g_slist_free (slist);
  69 }
  70
  71 /* Test that the sort is stable. */
  72 static void
  73 test_slist_sort_stable (void)
  74 {
  75   GSList *list = NULL;  /* (element-type utf8) */
  76   GSList *copy = NULL;  /* (element-type utf8) */
  77   gsize i;
  78
  79   /* Build a test list, already ordered. */
  80   for (i = 0; i < SIZE; i++)
  81     list = g_slist_append (list, g_strdup_printf ("%" G_GSIZE_FORMAT, i / 5));
  82
  83   /* Take a copy and sort it. */
  84   copy = g_slist_copy (list);
  85   copy = g_slist_sort (copy, (GCompareFunc) g_strcmp0);
  86
  87   /* Compare the two lists, checking pointers are equal to ensure the elements
  88    * have been kept stable. */
  89   for (i = 0; i < SIZE; i++)
  90     {
  91       gpointer p1, p2;
  92
  93       p1 = g_slist_nth_data (list, i);
  94       p2 = g_slist_nth_data (list, i);
  95
  96       g_assert (p1 == p2);
  97     }
  98
  99   g_slist_free (copy);
 100   g_slist_free_full (list, g_free);
 101 }
 102
 103 static void
 104 test_slist_insert_sorted (void)
 105 {
 106   GSList *slist = NULL;
 107   gint    i;
 108
 109   for (i = 0; i < SIZE; i++)
 110     slist = g_slist_insert_sorted (slist, GINT_TO_POINTER (array[i]), sort);
 111
 112   for (i = 0; i < SIZE - 1; i++)
 113     {
 114       gpointer p1, p2;
 115
 116       p1 = g_slist_nth_data (slist, i);
 117       p2 = g_slist_nth_data (slist, i+1);
 118
 119       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
 120     }
 121
 122   g_slist_free (slist);
 123 }
 124
 125 static void
 126 test_slist_insert_sorted_with_data (void)
 127 {
 128   GSList *slist = NULL;
 129   gint    i;
 130
 131   for (i = 0; i < SIZE; i++)
 132     slist = g_slist_insert_sorted_with_data (slist,
 133                                            GINT_TO_POINTER (array[i]),
 134                                            (GCompareDataFunc)sort,
 135                                            NULL);
 136
 137   for (i = 0; i < SIZE - 1; i++)
 138     {
 139       gpointer p1, p2;
 140
 141       p1 = g_slist_nth_data (slist, i);
 142       p2 = g_slist_nth_data (slist, i+1);
 143
 144       g_assert (GPOINTER_TO_INT (p1) <= GPOINTER_TO_INT (p2));
 145     }
 146
 147   g_slist_free (slist);
 148 }
 149
 150 static void
 151 test_slist_reverse (void)
 152 {
 153   GSList *slist = NULL;
 154   GSList *st;
 155   gint    nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 156   gint    i;
 157
 158   for (i = 0; i < 10; i++)
 159     slist = g_slist_append (slist, &nums[i]);
 160
 161   slist = g_slist_reverse (slist);
 162
 163   for (i = 0; i < 10; i++)
 164     {
 165       st = g_slist_nth (slist, i);
 166       g_assert (*((gint*) st->data) == (9 - i));
 167     }
 168
 169   g_slist_free (slist);
 170 }
 171
 172 static void
 173 test_slist_nth (void)
 174 {
 175   GSList *slist = NULL;
 176   GSList *st;
 177   gint    nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 178   gint    i;
 179
 180   for (i = 0; i < 10; i++)
 181     slist = g_slist_append (slist, &nums[i]);
 182
 183   for (i = 0; i < 10; i++)
 184     {
 185       st = g_slist_nth (slist, i);
 186       g_assert (*((gint*) st->data) == i);
 187     }
 188
 189   g_slist_free (slist);
 190 }
 191
 192 static void
 193 test_slist_remove (void)
 194 {
 195   GSList *slist = NULL;
 196   GSList *st;
 197   gint    nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 198   gint    i;
 199
 200   for (i = 0; i < 10; i++)
 201     {
 202       slist = g_slist_append (slist, &nums[i]);
 203       slist = g_slist_append (slist, &nums[i]);
 204     }
 205
 206   g_assert_cmpint (g_slist_length (slist), ==, 20);
 207
 208   for (i = 0; i < 10; i++)
 209     {
 210       slist = g_slist_remove (slist, &nums[i]);
 211     }
 212
 213   g_assert_cmpint (g_slist_length (slist), ==, 10);
 214
 215   for (i = 0; i < 10; i++)
 216     {
 217       st = g_slist_nth (slist, i);
 218       g_assert (*((gint*) st->data) == i);
 219     }
 220
 221   g_slist_free (slist);
 222 }
 223
 224 static void
 225 test_slist_remove_all (void)
 226 {
 227   GSList *slist = NULL;
 228   gint    nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 229   gint    i;
 230
 231   for (i = 0; i < 10; i++)
 232     {
 233       slist = g_slist_append (slist, &nums[i]);
 234       slist = g_slist_append (slist, &nums[i]);
 235     }
 236
 237   g_assert_cmpint (g_slist_length (slist), ==, 20);
 238
 239   for (i = 0; i < 5; i++)
 240     {
 241       slist = g_slist_remove_all (slist, &nums[2 * i + 1]);
 242       slist = g_slist_remove_all (slist, &nums[8 - 2 * i]);
 243     }
 244
 245   g_assert_cmpint (g_slist_length (slist), ==, 0);
 246   g_assert (slist == NULL);
 247 }
 248
 249 static void
 250 test_slist_insert (void)
 251 {
 252   gpointer a = "a";
 253   gpointer b = "b";
 254   gpointer c = "c";
 255   GSList *slist = NULL;
 256   GSList *st;
 257   gint   nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 258   gint   i;
 259
 260   slist = g_slist_insert_before (NULL, NULL, &nums[1]);
 261   slist = g_slist_insert (slist, &nums[3], 1);
 262   slist = g_slist_insert (slist, &nums[4], -1);
 263   slist = g_slist_insert (slist, &nums[0], 0);
 264   slist = g_slist_insert (slist, &nums[5], 100);
 265   slist = g_slist_insert_before (slist, NULL, &nums[6]);
 266   slist = g_slist_insert_before (slist, slist->next->next, &nums[2]);
 267
 268   slist = g_slist_insert (slist, &nums[9], 7);
 269   slist = g_slist_insert (slist, &nums[8], 7);
 270   slist = g_slist_insert (slist, &nums[7], 7);
 271
 272   for (i = 0; i < 10; i++)
 273     {
 274       st = g_slist_nth (slist, i);
 275       g_assert (*((gint*) st->data) == i);
 276     }
 277
 278   g_slist_free (slist);
 279
 280   slist = g_slist_insert (NULL, a, 1);
 281   g_assert (slist->data == a);
 282   g_assert (slist->next == NULL);
 283   g_slist_free (slist);
 284
 285   slist = g_slist_append (NULL, a);
 286   slist = g_slist_append (slist, b);
 287   slist = g_slist_insert (slist, c, 5);
 288
 289   g_assert (slist->next->next->data == c);
 290   g_assert (slist->next->next->next == NULL);
 291   g_slist_free (slist);
 292
 293   slist = g_slist_append (NULL, a);
 294   slist = g_slist_insert_before (slist, slist, b);
 295   g_assert (slist->data == b);
 296   g_assert (slist->next->data == a);
 297   g_assert (slist->next->next == NULL);
 298   g_slist_free (slist);
 299 }
 300
 301 static gint
 302 find_num (gconstpointer l, gconstpointer data)
 303 {
 304   return *(gint*)l - GPOINTER_TO_INT(data);
 305 }
 306
 307 static void
 308 test_slist_position (void)
 309 {
 310   GSList *slist = NULL;
 311   GSList *st;
 312   gint    nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 313   gint    i;
 314
 315   for (i = 0; i < 10; i++)
 316     {
 317       slist = g_slist_append (slist, &nums[i]);
 318     }
 319
 320   g_assert_cmpint (g_slist_index (slist, NULL), ==, -1);
 321   g_assert_cmpint (g_slist_position (slist, NULL), ==, -1);
 322
 323   for (i = 0; i < 10; i++)
 324     {
 325       g_assert_cmpint (g_slist_index (slist, &nums[i]), ==, i);
 326       st = g_slist_find_custom (slist, GINT_TO_POINTER(i), find_num);
 327       g_assert (st != NULL);
 328       g_assert_cmpint (g_slist_position (slist, st), ==, i);
 329     }
 330
 331   st = g_slist_find_custom (slist, GINT_TO_POINTER (1000), find_num);
 332   g_assert (st == NULL);
 333
 334   g_slist_free (slist);
 335 }
 336
 337 static void
 338 test_slist_concat (void)
 339 {
 340   gpointer a = "a";
 341   gpointer b = "b";
 342   GSList *s1, *s2, *s;
 343
 344   s1 = g_slist_append (NULL, a);
 345   s2 = g_slist_append (NULL, b);
 346   s = g_slist_concat (s1, s2);
 347   g_assert (s->data == a);
 348   g_assert (s->next->data == b);
 349   g_assert (s->next->next == NULL);
 350   g_slist_free (s);
 351
 352   s1 = g_slist_append (NULL, a);
 353
 354   s = g_slist_concat (NULL, s1);
 355   g_assert_cmpint (g_slist_length (s), ==, 1);
 356   s = g_slist_concat (s1, NULL);
 357   g_assert_cmpint (g_slist_length (s), ==, 1);
 358
 359   g_slist_free (s);
 360
 361   s = g_slist_concat (NULL, NULL);
 362   g_assert (s == NULL);
 363 }
 364
 365 static void
 366 test_slist_copy (void)
 367 {
 368   GSList *slist = NULL, *copy;
 369   GSList *s1, *s2;
 370   guint nums[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 371   gsize i;
 372
 373   /* Copy and test a many-element list. */
 374   for (i = 0; i < 10; i++)
 375     slist = g_slist_append (slist, &nums[i]);
 376
 377   copy = g_slist_copy (slist);
 378
 379   g_assert_cmpuint (g_slist_length (copy), ==, g_slist_length (slist));
 380
 381   for (s1 = copy, s2 = slist; s1 != NULL && s2 != NULL; s1 = s1->next, s2 = s2->next)
 382     g_assert (s1->data == s2->data);
 383
 384   g_slist_free (copy);
 385   g_slist_free (slist);
 386
 387   /* Copy a NULL list. */
 388   copy = g_slist_copy (NULL);
 389   g_assert_null (copy);
 390 }
 391
 392 static gpointer
 393 copy_and_count_string (gconstpointer src,
 394                        gpointer      data)
 395 {
 396   const gchar *str = src;
 397   gsize *count = data;
 398
 399   *count = *count + 1;
 400   return g_strdup (str);
 401 }
 402
 403 static void
 404 test_slist_copy_deep (void)
 405 {
 406   GSList *slist = NULL, *copy;
 407   GSList *s1, *s2;
 408   gsize count;
 409
 410   /* Deep-copy a simple list. */
 411   slist = g_slist_append (slist, "a");
 412   slist = g_slist_append (slist, "b");
 413   slist = g_slist_append (slist, "c");
 414
 415   count = 0;
 416   copy = g_slist_copy_deep (slist, copy_and_count_string, &count);
 417
 418   g_assert_cmpuint (count, ==, g_slist_length (slist));
 419   g_assert_cmpuint (g_slist_length (copy), ==, count);
 420   for (s1 = slist, s2 = copy; s1 != NULL && s2 != NULL; s1 = s1->next, s2 = s2->next)
 421     {
 422       g_assert_cmpstr (s1->data, ==, s2->data);
 423       g_assert (s1->data != s2->data);
 424     }
 425
 426   g_slist_free_full (copy, g_free);
 427   g_slist_free (slist);
 428
 429   /* Try with an empty list. */
 430   count = 0;
 431   copy = g_slist_copy_deep (NULL, copy_and_count_string, &count);
 432   g_assert_cmpuint (count, ==, 0);
 433   g_assert_null (copy);
 434 }
 435
 436 int
 437 main (int argc, char *argv[])
 438 {
 439   gint i;
 440
 441   g_test_init (&argc, &argv, NULL);
 442
 443   /* Create an array of random numbers. */
 444   for (i = 0; i < SIZE; i++)
 445     array[i] = g_test_rand_int_range (NUMBER_MIN, NUMBER_MAX);
 446
 447   g_test_add_func ("/slist/sort", test_slist_sort);
 448   g_test_add_func ("/slist/sort-with-data", test_slist_sort_with_data);
 449   g_test_add_func ("/slist/sort/stable", test_slist_sort_stable);
 450   g_test_add_func ("/slist/insert-sorted", test_slist_insert_sorted);
 451   g_test_add_func ("/slist/insert-sorted-with-data", test_slist_insert_sorted_with_data);
 452   g_test_add_func ("/slist/reverse", test_slist_reverse);
 453   g_test_add_func ("/slist/nth", test_slist_nth);
 454   g_test_add_func ("/slist/remove", test_slist_remove);
 455   g_test_add_func ("/slist/remove-all", test_slist_remove_all);
 456   g_test_add_func ("/slist/insert", test_slist_insert);
 457   g_test_add_func ("/slist/position", test_slist_position);
 458   g_test_add_func ("/slist/concat", test_slist_concat);
 459   g_test_add_func ("/slist/copy", test_slist_copy);
 460   g_test_add_func ("/slist/copy/deep", test_slist_copy_deep);
 461
 462   return g_test_run ();
 463 }