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)
 194 {
 195         return (git_vector_get(v, idx) == (void *)0x001);
 196 }
 197
 198 /* Test removal based on callback */
 199 void test_core_vector__remove_matching(void)
 200 {
 201         git_vector x;
 202         size_t i;
 203         void *compare;
 204
 205         git_vector_init(&x, 1, NULL);
 206         git_vector_insert(&x, (void*) 0x001);
 207
 208         cl_assert(x.length == 1);
 209         git_vector_remove_matching(&x, remove_ones);
 210         cl_assert(x.length == 0);
 211
 212         git_vector_insert(&x, (void*) 0x001);
 213         git_vector_insert(&x, (void*) 0x001);
 214         git_vector_insert(&x, (void*) 0x001);
 215
 216         cl_assert(x.length == 3);
 217         git_vector_remove_matching(&x, remove_ones);
 218         cl_assert(x.length == 0);
 219
 220         git_vector_insert(&x, (void*) 0x002);
 221         git_vector_insert(&x, (void*) 0x001);
 222         git_vector_insert(&x, (void*) 0x002);
 223         git_vector_insert(&x, (void*) 0x001);
 224
 225         cl_assert(x.length == 4);
 226         git_vector_remove_matching(&x, remove_ones);
 227         cl_assert(x.length == 2);
 228
 229         git_vector_foreach(&x, i, compare) {
 230                 cl_assert(compare != (void *)0x001);
 231         }
 232
 233         git_vector_clear(&x);
 234
 235         git_vector_insert(&x, (void*) 0x001);
 236         git_vector_insert(&x, (void*) 0x002);
 237         git_vector_insert(&x, (void*) 0x002);
 238         git_vector_insert(&x, (void*) 0x001);
 239
 240         cl_assert(x.length == 4);
 241         git_vector_remove_matching(&x, remove_ones);
 242         cl_assert(x.length == 2);
 243
 244         git_vector_foreach(&x, i, compare) {
 245                 cl_assert(compare != (void *)0x001);
 246         }
 247
 248         git_vector_clear(&x);
 249
 250         git_vector_insert(&x, (void*) 0x002);
 251         git_vector_insert(&x, (void*) 0x001);
 252         git_vector_insert(&x, (void*) 0x002);
 253         git_vector_insert(&x, (void*) 0x001);
 254
 255         cl_assert(x.length == 4);
 256         git_vector_remove_matching(&x, remove_ones);
 257         cl_assert(x.length == 2);
 258
 259         git_vector_foreach(&x, i, compare) {
 260                 cl_assert(compare != (void *)0x001);
 261         }
 262
 263         git_vector_clear(&x);
 264
 265         git_vector_insert(&x, (void*) 0x002);
 266         git_vector_insert(&x, (void*) 0x003);
 267         git_vector_insert(&x, (void*) 0x002);
 268         git_vector_insert(&x, (void*) 0x003);
 269
 270         cl_assert(x.length == 4);
 271         git_vector_remove_matching(&x, remove_ones);
 272         cl_assert(x.length == 4);
 273
 274         git_vector_free(&x);
 275 }