src/libstrongswan/tests/suites/test_linked_list.c

   1 /*
   2  * Copyright (C) 2013 Tobias Brunner
   3  *
   4  * Copyright (C) secunet Security Networks AG
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2 of the License, or (at your
   9  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * for more details.
  15  */
  16
  17 #include "test_suite.h"
  18
  19 #include <collections/linked_list.h>
  20
  21 /*******************************************************************************
  22  * test fixture
  23  */
  24
  25 static linked_list_t *list;
  26
  27 START_SETUP(setup_list)
  28 {
  29         void *x = NULL;
  30
  31         list = linked_list_create();
  32         ck_assert_int_eq(list->get_count(list), 0);
  33         ck_assert(list->get_first(list, &x) == NOT_FOUND);
  34         ck_assert(list->get_last(list, &x) == NOT_FOUND);
  35 }
  36 END_SETUP
  37
  38 START_TEARDOWN(teardown_list)
  39 {
  40         list->destroy(list);
  41 }
  42 END_TEARDOWN
  43
  44 /*******************************************************************************
  45  * insert first/last
  46  */
  47
  48 START_TEST(test_insert_first)
  49 {
  50         void *a = (void*)1, *b = (void*)2, *x = NULL;
  51
  52         list->insert_first(list, a);
  53         ck_assert_int_eq(list->get_count(list), 1);
  54         ck_assert(list->get_first(list, &x) == SUCCESS);
  55         ck_assert(x == a);
  56         ck_assert(list->get_last(list, &x) == SUCCESS);
  57         ck_assert(x == a);
  58
  59         list->insert_first(list, b);
  60         ck_assert_int_eq(list->get_count(list), 2);
  61         ck_assert(list->get_first(list, &x) == SUCCESS);
  62         ck_assert(x == b);
  63         ck_assert(list->get_last(list, &x) == SUCCESS);
  64         ck_assert(x == a);
  65 }
  66 END_TEST
  67
  68 START_TEST(test_insert_last)
  69 {
  70         void *a = (void*)1, *b = (void*)2, *x = NULL;
  71
  72         list->insert_last(list, a);
  73         ck_assert_int_eq(list->get_count(list), 1);
  74         ck_assert(list->get_first(list, &x) == SUCCESS);
  75         ck_assert(x == a);
  76         ck_assert(list->get_last(list, &x) == SUCCESS);
  77         ck_assert(x == a);
  78
  79         list->insert_last(list, b);
  80         ck_assert_int_eq(list->get_count(list), 2);
  81         ck_assert(list->get_first(list, &x) == SUCCESS);
  82         ck_assert(x == a);
  83         ck_assert(list->get_last(list, &x) == SUCCESS);
  84         ck_assert(x == b);
  85 }
  86 END_TEST
  87
  88 /*******************************************************************************
  89  * remove first/last
  90  */
  91
  92 START_TEST(test_remove_first)
  93 {
  94         void *a = (void*)1, *b = (void*)2, *x = NULL;
  95
  96         list->insert_first(list, a);
  97         list->insert_first(list, b);
  98         ck_assert(list->remove_first(list, &x) == SUCCESS);
  99         ck_assert_int_eq(list->get_count(list), 1);
 100         ck_assert(x == b);
 101         ck_assert(list->remove_first(list, &x) == SUCCESS);
 102         ck_assert_int_eq(list->get_count(list), 0);
 103         ck_assert(x == a);
 104         ck_assert(list->remove_first(list, &x) == NOT_FOUND);
 105         ck_assert(list->remove_last(list, &x) == NOT_FOUND);
 106 }
 107 END_TEST
 108
 109 START_TEST(test_remove_last)
 110 {
 111         void *a = (void*)1, *b = (void*)2, *x = NULL;
 112
 113         list->insert_first(list, a);
 114         list->insert_first(list, b);
 115         ck_assert(list->remove_last(list, &x) == SUCCESS);
 116         ck_assert_int_eq(list->get_count(list), 1);
 117         ck_assert(x == a);
 118         ck_assert(list->remove_last(list, &x) == SUCCESS);
 119         ck_assert_int_eq(list->get_count(list), 0);
 120         ck_assert(x == b);
 121         ck_assert(list->remove_first(list, &x) == NOT_FOUND);
 122         ck_assert(list->remove_last(list, &x) == NOT_FOUND);
 123 }
 124 END_TEST
 125
 126 /*******************************************************************************
 127  * helper function for remove and find tests
 128  */
 129
 130 static bool match_a(void *item, void *a)
 131 {
 132         ck_assert(a == (void*)1);
 133         return item == a;
 134 }
 135
 136 static bool match_b(void *item, void *b)
 137 {
 138         ck_assert(b == (void*)2);
 139         return item == b;
 140 }
 141
 142 /*******************************************************************************
 143  * remove
 144  */
 145
 146 START_TEST(test_remove)
 147 {
 148         void *a = (void*)1, *b = (void*)2;
 149
 150         list->insert_first(list, a);
 151         ck_assert(list->remove(list, a, NULL) == 1);
 152         ck_assert_int_eq(list->get_count(list), 0);
 153
 154         list->insert_last(list, a);
 155         list->insert_last(list, a);
 156         list->insert_last(list, a);
 157         list->insert_last(list, b);
 158         ck_assert(list->remove(list, a, NULL) == 3);
 159         ck_assert(list->remove(list, a, NULL) == 0);
 160         ck_assert_int_eq(list->get_count(list), 1);
 161         ck_assert(list->remove(list, b, NULL) == 1);
 162         ck_assert(list->remove(list, b, NULL) == 0);
 163 }
 164 END_TEST
 165
 166 START_TEST(test_remove_callback)
 167 {
 168         void *a = (void*)1, *b = (void*)2;
 169
 170         list->insert_last(list, a);
 171         list->insert_last(list, b);
 172         list->insert_last(list, a);
 173         list->insert_last(list, b);
 174         ck_assert(list->remove(list, a, match_a) == 2);
 175         ck_assert(list->remove(list, a, match_a) == 0);
 176         ck_assert_int_eq(list->get_count(list), 2);
 177         ck_assert(list->remove(list, b, match_b) == 2);
 178         ck_assert(list->remove(list, b, match_b) == 0);
 179         ck_assert_int_eq(list->get_count(list), 0);
 180 }
 181 END_TEST
 182
 183 /*******************************************************************************
 184  * find
 185  */
 186
 187 CALLBACK(find_a_b, bool,
 188         void *item, va_list args)
 189 {
 190         void *a, *b;
 191
 192         VA_ARGS_VGET(args, a, b);
 193         ck_assert(a == (void*)1);
 194         ck_assert(b == (void*)2);
 195         return item == a || item == b;
 196 }
 197
 198 CALLBACK(find_a, bool,
 199         void *item, va_list args)
 200 {
 201         void *a;
 202
 203         VA_ARGS_VGET(args, a);
 204         return match_a(item, a);
 205 }
 206
 207 CALLBACK(find_b, bool,
 208         void *item, va_list args)
 209 {
 210         void *b;
 211
 212         VA_ARGS_VGET(args, b);
 213         return match_b(item, b);
 214 }
 215
 216 START_TEST(test_find)
 217 {
 218         void *a = (void*)1, *b = (void*)2;
 219
 220         ck_assert(!list->find_first(list, NULL, &a));
 221         list->insert_last(list, a);
 222         ck_assert(list->find_first(list, NULL, &a));
 223         ck_assert(!list->find_first(list, NULL, &b));
 224         list->insert_last(list, b);
 225         ck_assert(list->find_first(list, NULL, &a));
 226         ck_assert(list->find_first(list, NULL, &b));
 227
 228         ck_assert(!list->find_first(list, NULL, NULL));
 229 }
 230 END_TEST
 231
 232 START_TEST(test_find_callback)
 233 {
 234         void *a = (void*)1, *b = (void*)2, *x = NULL;
 235
 236         ck_assert(!list->find_first(list, find_a_b, &x, a, b));
 237         list->insert_last(list, a);
 238         ck_assert(list->find_first(list, find_a, NULL, a));
 239         x = NULL;
 240         ck_assert(list->find_first(list, find_a, &x, a));
 241         ck_assert(a == x);
 242         ck_assert(!list->find_first(list, find_b, &x, b));
 243         ck_assert(a == x);
 244         x = NULL;
 245         ck_assert(list->find_first(list, find_a_b, &x, a, b));
 246         ck_assert(a == x);
 247
 248         list->insert_last(list, b);
 249         ck_assert(list->find_first(list, find_a, &x, a));
 250         ck_assert(a == x);
 251         ck_assert(list->find_first(list, find_b, &x, b));
 252         ck_assert(b == x);
 253         x = NULL;
 254         ck_assert(list->find_first(list, find_a_b, &x, a, b));
 255         ck_assert(a == x);
 256 }
 257 END_TEST
 258
 259 CALLBACK(find_args, bool,
 260         void *item, va_list args)
 261 {
 262         uint64_t d, e;
 263         level_t c;
 264         int *a, b;
 265
 266         VA_ARGS_VGET(args, a, b, c, d, e);
 267         ck_assert_int_eq(*a, 1);
 268         ck_assert_int_eq(b, 2);
 269         ck_assert_int_eq(c, LEVEL_PRIVATE);
 270         ck_assert_int_eq(d, UINT64_MAX);
 271         ck_assert_int_eq(e, UINT64_MAX-1);
 272         return item == a;
 273 }
 274
 275 START_TEST(test_find_callback_args)
 276 {
 277         int a = 1, b = 2, *x;
 278         uint64_t d = UINT64_MAX;
 279
 280         list->insert_last(list, &a);
 281         ck_assert(list->find_first(list, find_args, (void**)&x, &a, b,
 282                                                            LEVEL_PRIVATE, d, UINT64_MAX-1));
 283         ck_assert_int_eq(a, *x);
 284 }
 285 END_TEST
 286
 287 /*******************************************************************************
 288  * invoke
 289  */
 290
 291 typedef struct invoke_t invoke_t;
 292
 293 struct invoke_t {
 294         int val;
 295         void (*invoke)(invoke_t *item);
 296 };
 297
 298 CALLBACK(invoke, void,
 299         intptr_t item, va_list args)
 300 {
 301         void *a, *b, *c, *d;
 302         int *sum;
 303
 304         VA_ARGS_VGET(args, a, b, c, d, sum);
 305         ck_assert_int_eq((uintptr_t)a, 1);
 306         ck_assert_int_eq((uintptr_t)b, 2);
 307         ck_assert_int_eq((uintptr_t)c, 3);
 308         ck_assert_int_eq((uintptr_t)d, 4);
 309         *sum += item;
 310 }
 311
 312 static void invoke_offset(invoke_t *item)
 313 {
 314         item->val++;
 315 }
 316
 317 START_TEST(test_invoke_function)
 318 {
 319         int sum = 0;
 320
 321         list->insert_last(list, (void*)1);
 322         list->insert_last(list, (void*)2);
 323         list->insert_last(list, (void*)3);
 324         list->insert_last(list, (void*)4);
 325         list->insert_last(list, (void*)5);
 326         list->invoke_function(list, invoke, (uintptr_t)1, (uintptr_t)2,
 327                                                   (uintptr_t)3, (uintptr_t)4, &sum);
 328         ck_assert_int_eq(sum, 15);
 329 }
 330 END_TEST
 331
 332 START_TEST(test_invoke_offset)
 333 {
 334         invoke_t items[] = {
 335                 { .val = 1, .invoke = invoke_offset, },
 336                 { .val = 2, .invoke = invoke_offset, },
 337                 { .val = 3, .invoke = invoke_offset, },
 338                 { .val = 4, .invoke = invoke_offset, },
 339                 { .val = 5, .invoke = invoke_offset, },
 340         }, *item;
 341         int i;
 342
 343         for (i = 0; i < countof(items); i++)
 344         {
 345                 list->insert_last(list, &items[i]);
 346         }
 347         list->invoke_offset(list, offsetof(invoke_t, invoke));
 348         i = 2;
 349         while (list->remove_first(list, (void**)&item) == SUCCESS)
 350         {
 351                 ck_assert_int_eq(item->val, i++);
 352         }
 353 }
 354 END_TEST
 355
 356 /*******************************************************************************
 357  * clone
 358  */
 359
 360 typedef struct clone_t clone_t;
 361
 362 struct clone_t {
 363         void *val;
 364         void *(*clone)(clone_t *item);
 365 };
 366
 367 static void *clonefn(clone_t *item)
 368 {
 369         return item->val;
 370 }
 371
 372 static void test_clone(linked_list_t *list)
 373 {
 374         intptr_t x;
 375         int round = 1;
 376
 377         ck_assert_int_eq(list->get_count(list), 5);
 378         while (list->remove_first(list, (void*)&x) == SUCCESS)
 379         {
 380                 ck_assert_int_eq(round, x);
 381                 round++;
 382         }
 383         ck_assert_int_eq(round, 6);
 384 }
 385
 386 START_TEST(test_clone_offset)
 387 {
 388         linked_list_t *other;
 389         clone_t items[] = {
 390                 { .val = (void*)1, .clone = clonefn, },
 391                 { .val = (void*)2, .clone = clonefn, },
 392                 { .val = (void*)3, .clone = clonefn, },
 393                 { .val = (void*)4, .clone = clonefn, },
 394                 { .val = (void*)5, .clone = clonefn, },
 395         };
 396         int i;
 397
 398         for (i = 0; i < countof(items); i++)
 399         {
 400                 list->insert_last(list, &items[i]);
 401         }
 402         other = list->clone_offset(list, offsetof(clone_t, clone));
 403         test_clone(other);
 404         other->destroy(other);
 405 }
 406 END_TEST
 407
 408
 409 /*******************************************************************************
 410  * equals
 411  */
 412
 413 typedef struct equals_t equals_t;
 414
 415 struct equals_t {
 416         int val;
 417         bool (*equals)(equals_t *a, equals_t *b);
 418 };
 419
 420 static bool equalsfn(equals_t *a, equals_t *b)
 421 {
 422         return a->val == b->val;
 423 }
 424
 425 START_TEST(test_equals_offset)
 426 {
 427         linked_list_t *other;
 428         equals_t *x, items[] = {
 429                 { .val = 1, .equals = equalsfn, },
 430                 { .val = 2, .equals = equalsfn, },
 431                 { .val = 3, .equals = equalsfn, },
 432                 { .val = 4, .equals = equalsfn, },
 433                 { .val = 5, .equals = equalsfn, },
 434         };
 435         int i;
 436
 437         for (i = 0; i < countof(items); i++)
 438         {
 439                 list->insert_last(list, &items[i]);
 440         }
 441         ck_assert(list->equals_offset(list, list, offsetof(equals_t, equals)));
 442         other = linked_list_create_from_enumerator(list->create_enumerator(list));
 443         ck_assert(list->equals_offset(list, other, offsetof(equals_t, equals)));
 444         other->remove_last(other, (void**)&x);
 445         ck_assert(!list->equals_offset(list, other, offsetof(equals_t, equals)));
 446         list->remove_last(list, (void**)&x);
 447         ck_assert(list->equals_offset(list, other, offsetof(equals_t, equals)));
 448         other->remove_first(other, (void**)&x);
 449         ck_assert(!list->equals_offset(list, other, offsetof(equals_t, equals)));
 450         list->remove_first(list, (void**)&x);
 451         ck_assert(list->equals_offset(list, other, offsetof(equals_t, equals)));
 452         while (list->remove_first(list, (void**)&x) == SUCCESS);
 453         while (other->remove_first(other, (void**)&x) == SUCCESS);
 454         ck_assert(list->equals_offset(list, other, offsetof(equals_t, equals)));
 455         other->destroy(other);
 456 }
 457 END_TEST
 458
 459 START_TEST(test_equals_function)
 460 {
 461         linked_list_t *other;
 462         equals_t *x, items[] = {
 463                 { .val = 1, },
 464                 { .val = 2, },
 465                 { .val = 3, },
 466                 { .val = 4, },
 467                 { .val = 5, },
 468         };
 469         int i;
 470
 471         for (i = 0; i < countof(items); i++)
 472         {
 473                 list->insert_last(list, &items[i]);
 474         }
 475         ck_assert(list->equals_function(list, list, (void*)equalsfn));
 476         other = linked_list_create_from_enumerator(list->create_enumerator(list));
 477         ck_assert(list->equals_function(list, other, (void*)equalsfn));
 478         other->remove_last(other, (void**)&x);
 479         ck_assert(!list->equals_function(list, other, (void*)equalsfn));
 480         list->remove_last(list, (void**)&x);
 481         ck_assert(list->equals_function(list, other, (void*)equalsfn));
 482         other->remove_first(other, (void**)&x);
 483         ck_assert(!list->equals_function(list, other, (void*)equalsfn));
 484         list->remove_first(list, (void**)&x);
 485         ck_assert(list->equals_function(list, other, (void*)equalsfn));
 486         while (list->remove_first(list, (void**)&x) == SUCCESS);
 487         while (other->remove_first(other, (void**)&x) == SUCCESS);
 488         ck_assert(list->equals_function(list, other, (void*)equalsfn));
 489         other->destroy(other);
 490 }
 491 END_TEST
 492
 493 Suite *linked_list_suite_create()
 494 {
 495         Suite *s;
 496         TCase *tc;
 497
 498         s = suite_create("linked list");
 499
 500         tc = tcase_create("insert/get");
 501         tcase_add_checked_fixture(tc, setup_list, teardown_list);
 502         tcase_add_test(tc, test_insert_first);
 503         tcase_add_test(tc, test_insert_last);
 504         suite_add_tcase(s, tc);
 505
 506         tc = tcase_create("remove");
 507         tcase_add_checked_fixture(tc, setup_list, teardown_list);
 508         tcase_add_test(tc, test_remove_first);
 509         tcase_add_test(tc, test_remove_last);
 510         tcase_add_test(tc, test_remove);
 511         tcase_add_test(tc, test_remove_callback);
 512         suite_add_tcase(s, tc);
 513
 514         tc = tcase_create("find");
 515         tcase_add_checked_fixture(tc, setup_list, teardown_list);
 516         tcase_add_test(tc, test_find);
 517         tcase_add_test(tc, test_find_callback);
 518         tcase_add_test(tc, test_find_callback_args);
 519         suite_add_tcase(s, tc);
 520
 521         tc = tcase_create("invoke");
 522         tcase_add_checked_fixture(tc, setup_list, teardown_list);
 523         tcase_add_test(tc, test_invoke_function);
 524         tcase_add_test(tc, test_invoke_offset);
 525         suite_add_tcase(s, tc);
 526
 527         tc = tcase_create("clone");
 528         tcase_add_checked_fixture(tc, setup_list, teardown_list);
 529         tcase_add_test(tc, test_clone_offset);
 530         suite_add_tcase(s, tc);
 531
 532         tc = tcase_create("equals");
 533         tcase_add_checked_fixture(tc, setup_list, teardown_list);
 534         tcase_add_test(tc, test_equals_offset);
 535         tcase_add_test(tc, test_equals_function);
 536         suite_add_tcase(s, tc);
 537
 538         return s;
 539 }