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 }