tests/core/vector.c

   1 #include "clar_libgit2.h"
   2 #include "vector.h"
   3
   4 /* initial size of 1 would cause writing past array bounds */
   5 void test_core_vector__0(void)
   6 {
   7         git_vector x;
   8         int i;
   9         git_vector_init(&x, 1, NULL);
  10         for (i = 0; i < 10; ++i) {
  11                 git_vector_insert(&x, (void*) 0xabc);
  12         }
  13         git_vector_free(&x);
  14 }
  15
  16
  17 /* don't read past array bounds on remove() */
  18 void test_core_vector__1(void)
  19 {
  20         git_vector x;
  21         // make initial capacity exact for our insertions.
  22         git_vector_init(&x, 3, NULL);
  23         git_vector_insert(&x, (void*) 0xabc);
  24         git_vector_insert(&x, (void*) 0xdef);
  25         git_vector_insert(&x, (void*) 0x123);
  26
  27         git_vector_remove(&x, 0); // used to read past array bounds.
  28         git_vector_free(&x);
  29 }
  30
  31
  32 static int test_cmp(const void *a, const void *b)
  33 {
  34         return *(const int *)a - *(const int *)b;
  35 }
  36
  37 /* remove duplicates */
  38 void test_core_vector__2(void)
  39 {
  40         git_vector x;
  41         int *ptrs[2];
  42
  43         ptrs[0] = git__malloc(sizeof(int));
  44         ptrs[1] = git__malloc(sizeof(int));
  45
  46         *ptrs[0] = 2;
  47         *ptrs[1] = 1;
  48
  49         cl_git_pass(git_vector_init(&x, 5, test_cmp));
  50         cl_git_pass(git_vector_insert(&x, ptrs[0]));
  51         cl_git_pass(git_vector_insert(&x, ptrs[1]));
  52         cl_git_pass(git_vector_insert(&x, ptrs[1]));
  53         cl_git_pass(git_vector_insert(&x, ptrs[0]));
  54         cl_git_pass(git_vector_insert(&x, ptrs[1]));
  55         cl_assert(x.length == 5);
  56
  57         git_vector_uniq(&x, NULL);
  58         cl_assert(x.length == 2);
  59
  60         git_vector_free(&x);
  61
  62         git__free(ptrs[0]);
  63         git__free(ptrs[1]);
  64 }
  65
  66
  67 static int compare_them(const void *a, const void *b)
  68 {
  69         return (int)((long)a - (long)b);
  70 }
  71
  72 /* insert_sorted */
  73 void test_core_vector__3(void)
  74 {
  75         git_vector x;
  76         long i;
  77         git_vector_init(&x, 1, &compare_them);
  78
  79         for (i = 0; i < 10; i += 2) {
  80                 git_vector_insert_sorted(&x, (void*)(i + 1), NULL);
  81         }
  82
  83         for (i = 9; i > 0; i -= 2) {
  84                 git_vector_insert_sorted(&x, (void*)(i + 1), NULL);
  85         }
  86
  87         cl_assert(x.length == 10);
  88         for (i = 0; i < 10; ++i) {
  89                 cl_assert(git_vector_get(&x, i) == (void*)(i + 1));
  90         }
  91
  92         git_vector_free(&x);
  93 }
  94
  95 /* insert_sorted with duplicates */
  96 void test_core_vector__4(void)
  97 {
  98         git_vector x;
  99         long i;
 100         git_vector_init(&x, 1, &compare_them);
 101
 102         for (i = 0; i < 10; i += 2) {
 103                 git_vector_insert_sorted(&x, (void*)(i + 1), NULL);
 104         }
 105
 106         for (i = 9; i > 0; i -= 2) {
 107                 git_vector_insert_sorted(&x, (void*)(i + 1), NULL);
 108         }
 109
 110         for (i = 0; i < 10; i += 2) {
 111                 git_vector_insert_sorted(&x, (void*)(i + 1), NULL);
 112         }
 113
 114         for (i = 9; i > 0; i -= 2) {
 115                 git_vector_insert_sorted(&x, (void*)(i + 1), NULL);
 116         }
 117
 118         cl_assert(x.length == 20);
 119         for (i = 0; i < 20; ++i) {
 120                 cl_assert(git_vector_get(&x, i) == (void*)(i / 2 + 1));
 121         }
 122
 123         git_vector_free(&x);
 124 }
 125
 126 typedef struct {
 127         int content;
 128         int count;
 129 } my_struct;
 130
 131 static int _struct_count = 0;
 132
 133 static int compare_structs(const void *a, const void *b)
 134 {
 135         return ((const my_struct *)a)->content -
 136                 ((const my_struct *)b)->content;
 137 }
 138
 139 static int merge_structs(void **old_raw, void *new)
 140 {
 141         my_struct *old = *(my_struct **)old_raw;
 142         cl_assert(((my_struct *)old)->content == ((my_struct *)new)->content);
 143         ((my_struct *)old)->count += 1;
 144         git__free(new);
 145         _struct_count--;
 146         return GIT_EEXISTS;
 147 }
 148
 149 static my_struct *alloc_struct(int value)
 150 {
 151         my_struct *st = git__malloc(sizeof(my_struct));
 152         st->content = value;
 153         st->count = 0;
 154         _struct_count++;
 155         return st;
 156 }
 157
 158 /* insert_sorted with duplicates and special handling */
 159 void test_core_vector__5(void)
 160 {
 161         git_vector x;
 162         int i;
 163
 164         git_vector_init(&x, 1, &compare_structs);
 165
 166         for (i = 0; i < 10; i += 2)
 167                 git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);
 168
 169         for (i = 9; i > 0; i -= 2)
 170                 git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);
 171
 172         cl_assert(x.length == 10);
 173         cl_assert(_struct_count == 10);
 174
 175         for (i = 0; i < 10; i += 2)
 176                 git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);
 177
 178         for (i = 9; i > 0; i -= 2)
 179                 git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs);
 180
 181         cl_assert(x.length == 10);
 182         cl_assert(_struct_count == 10);
 183
 184         for (i = 0; i < 10; ++i) {
 185                 cl_assert(((my_struct *)git_vector_get(&x, i))->content == i);
 186                 git__free(git_vector_get(&x, i));
 187                 _struct_count--;
 188         }
 189
 190         git_vector_free(&x);
 191 }
 192
 193 static int remove_ones(const git_vector *v, size_t idx, void *p)
 194 {
 195         GIT_UNUSED(p);
 196         return (git_vector_get(v, idx) == (void *)0x001);
 197 }
 198
 199 /* Test removal based on callback */
 200 void test_core_vector__remove_matching(void)
 201 {
 202         git_vector x;
 203         size_t i;
 204         void *compare;
 205
 206         git_vector_init(&x, 1, NULL);
 207         git_vector_insert(&x, (void*) 0x001);
 208
 209         cl_assert(x.length == 1);
 210         git_vector_remove_matching(&x, remove_ones, NULL);
 211         cl_assert(x.length == 0);
 212
 213         git_vector_insert(&x, (void*) 0x001);
 214         git_vector_insert(&x, (void*) 0x001);
 215         git_vector_insert(&x, (void*) 0x001);
 216
 217         cl_assert(x.length == 3);
 218         git_vector_remove_matching(&x, remove_ones, NULL);
 219         cl_assert(x.length == 0);
 220
 221         git_vector_insert(&x, (void*) 0x002);
 222         git_vector_insert(&x, (void*) 0x001);
 223         git_vector_insert(&x, (void*) 0x002);
 224         git_vector_insert(&x, (void*) 0x001);
 225
 226         cl_assert(x.length == 4);
 227         git_vector_remove_matching(&x, remove_ones, NULL);
 228         cl_assert(x.length == 2);
 229
 230         git_vector_foreach(&x, i, compare) {
 231                 cl_assert(compare != (void *)0x001);
 232         }
 233
 234         git_vector_clear(&x);
 235
 236         git_vector_insert(&x, (void*) 0x001);
 237         git_vector_insert(&x, (void*) 0x002);
 238         git_vector_insert(&x, (void*) 0x002);
 239         git_vector_insert(&x, (void*) 0x001);
 240
 241         cl_assert(x.length == 4);
 242         git_vector_remove_matching(&x, remove_ones, NULL);
 243         cl_assert(x.length == 2);
 244
 245         git_vector_foreach(&x, i, compare) {
 246                 cl_assert(compare != (void *)0x001);
 247         }
 248
 249         git_vector_clear(&x);
 250
 251         git_vector_insert(&x, (void*) 0x002);
 252         git_vector_insert(&x, (void*) 0x001);
 253         git_vector_insert(&x, (void*) 0x002);
 254         git_vector_insert(&x, (void*) 0x001);
 255
 256         cl_assert(x.length == 4);
 257         git_vector_remove_matching(&x, remove_ones, NULL);
 258         cl_assert(x.length == 2);
 259
 260         git_vector_foreach(&x, i, compare) {
 261                 cl_assert(compare != (void *)0x001);
 262         }
 263
 264         git_vector_clear(&x);
 265
 266         git_vector_insert(&x, (void*) 0x002);
 267         git_vector_insert(&x, (void*) 0x003);
 268         git_vector_insert(&x, (void*) 0x002);
 269         git_vector_insert(&x, (void*) 0x003);
 270
 271         cl_assert(x.length == 4);
 272         git_vector_remove_matching(&x, remove_ones, NULL);
 273         cl_assert(x.length == 4);
 274
 275         git_vector_free(&x);
 276 }
 277
 278 static void assert_vector(git_vector *x, void *expected[], size_t len)
 279 {
 280         size_t i;
 281
 282         cl_assert_equal_i(len, x->length);
 283
 284         for (i = 0; i < len; i++)
 285                 cl_assert(expected[i] == x->contents[i]);
 286 }
 287
 288 void test_core_vector__grow_and_shrink(void)
 289 {
 290         git_vector x = GIT_VECTOR_INIT;
 291         void *expected1[] = {
 292                 (void *)0x02, (void *)0x03, (void *)0x04, (void *)0x05,
 293                 (void *)0x06, (void *)0x07, (void *)0x08, (void *)0x09,
 294                 (void *)0x0a
 295         };
 296         void *expected2[] = {
 297                 (void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,
 298                 (void *)0x07, (void *)0x08, (void *)0x09, (void *)0x0a
 299         };
 300         void *expected3[] = {
 301                 (void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,
 302                 (void *)0x0a
 303         };
 304         void *expected4[] = {
 305                 (void *)0x02, (void *)0x04, (void *)0x05
 306         };
 307         void *expected5[] = {
 308                 (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
 309                 (void *)0x05
 310         };
 311         void *expected6[] = {
 312                 (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
 313                 (void *)0x05, (void *)0x00
 314         };
 315         void *expected7[] = {
 316                 (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
 317                 (void *)0x00, (void *)0x00, (void *)0x00, (void *)0x05,
 318                 (void *)0x00
 319         };
 320         void *expected8[] = {
 321                 (void *)0x04, (void *)0x00, (void *)0x00, (void *)0x00,
 322                 (void *)0x05, (void *)0x00
 323         };
 324         void *expected9[] = {
 325                 (void *)0x04, (void *)0x00, (void *)0x05, (void *)0x00
 326         };
 327         void *expectedA[] = { (void *)0x04, (void *)0x00 };
 328         void *expectedB[] = { (void *)0x04 };
 329
 330         git_vector_insert(&x, (void *)0x01);
 331         git_vector_insert(&x, (void *)0x02);
 332         git_vector_insert(&x, (void *)0x03);
 333         git_vector_insert(&x, (void *)0x04);
 334         git_vector_insert(&x, (void *)0x05);
 335         git_vector_insert(&x, (void *)0x06);
 336         git_vector_insert(&x, (void *)0x07);
 337         git_vector_insert(&x, (void *)0x08);
 338         git_vector_insert(&x, (void *)0x09);
 339         git_vector_insert(&x, (void *)0x0a);
 340
 341         git_vector_remove_range(&x, 0, 1);
 342         assert_vector(&x, expected1, ARRAY_SIZE(expected1));
 343
 344         git_vector_remove_range(&x, 1, 1);
 345         assert_vector(&x, expected2, ARRAY_SIZE(expected2));
 346
 347         git_vector_remove_range(&x, 4, 3);
 348         assert_vector(&x, expected3, ARRAY_SIZE(expected3));
 349
 350         git_vector_remove_range(&x, 3, 2);
 351         assert_vector(&x, expected4, ARRAY_SIZE(expected4));
 352
 353         git_vector_insert_null(&x, 0, 2);
 354         assert_vector(&x, expected5, ARRAY_SIZE(expected5));
 355
 356         git_vector_insert_null(&x, 5, 1);
 357         assert_vector(&x, expected6, ARRAY_SIZE(expected6));
 358
 359         git_vector_insert_null(&x, 4, 3);
 360         assert_vector(&x, expected7, ARRAY_SIZE(expected7));
 361
 362         git_vector_remove_range(&x, 0, 3);
 363         assert_vector(&x, expected8, ARRAY_SIZE(expected8));
 364
 365         git_vector_remove_range(&x, 1, 2);
 366         assert_vector(&x, expected9, ARRAY_SIZE(expected9));
 367
 368         git_vector_remove_range(&x, 2, 2);
 369         assert_vector(&x, expectedA, ARRAY_SIZE(expectedA));
 370
 371         git_vector_remove_range(&x, 1, 1);
 372         assert_vector(&x, expectedB, ARRAY_SIZE(expectedB));
 373
 374         git_vector_remove_range(&x, 0, 1);
 375         assert_vector(&x, NULL, 0);
 376
 377         git_vector_free(&x);
 378 }
 379
 380 void test_core_vector__reverse(void)
 381 {
 382         git_vector v = GIT_VECTOR_INIT;
 383         size_t i;
 384
 385         void *in1[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3};
 386         void *out1[] = {(void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};
 387
 388         void *in2[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3, (void *) 0x4};
 389         void *out2[] = {(void *) 0x4, (void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};
 390
 391         for (i = 0; i < 4; i++)
 392                 cl_git_pass(git_vector_insert(&v, in1[i]));
 393
 394         git_vector_reverse(&v);
 395
 396         for (i = 0; i < 4; i++)
 397                 cl_assert_equal_p(out1[i], git_vector_get(&v, i));
 398
 399         git_vector_clear(&v);
 400         for (i = 0; i < 5; i++)
 401                 cl_git_pass(git_vector_insert(&v, in2[i]));
 402
 403         git_vector_reverse(&v);
 404
 405         for (i = 0; i < 5; i++)
 406                 cl_assert_equal_p(out2[i], git_vector_get(&v, i));
 407
 408         git_vector_free(&v);
 409 }
 410
 411 void test_core_vector__dup_empty_vector(void)
 412 {
 413         git_vector v = GIT_VECTOR_INIT;
 414         git_vector dup = GIT_VECTOR_INIT;
 415         int dummy;
 416
 417         cl_assert_equal_i(0, v.length);
 418
 419         cl_git_pass(git_vector_dup(&dup, &v, v._cmp));
 420         cl_assert_equal_i(0, dup._alloc_size);
 421         cl_assert_equal_i(0, dup.length);
 422
 423         cl_git_pass(git_vector_insert(&dup, &dummy));
 424         cl_assert_equal_i(8, dup._alloc_size);
 425         cl_assert_equal_i(1, dup.length);
 426
 427         git_vector_free(&dup);
 428 }