src/test/vector.c

   1 /*****************************************************************************
   2  * vector.c : Test for vlc_vector macros
   3  *****************************************************************************
   4  * Copyright (C) 2018 VLC authors and VideoLAN
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU Lesser General Public License as published by
   8  * the Free Software Foundation; either version 2.1 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  19  *****************************************************************************/
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include "config.h"
  23 #endif
  24
  25 #undef NDEBUG
  26
  27 #include <assert.h>
  28
  29 #include <vlc_common.h>
  30 #include <vlc_vector.h>
  31
  32 static void test_vector_insert_remove(void)
  33 {
  34     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
  35
  36     bool ok;
  37
  38     ok = vlc_vector_push(&vec, 42);
  39     assert(ok);
  40     assert(vec.data[0] == 42);
  41     assert(vec.size == 1);
  42
  43     ok = vlc_vector_push(&vec, 37);
  44     assert(ok);
  45     assert(vec.size == 2);
  46     assert(vec.data[0] == 42);
  47     assert(vec.data[1] == 37);
  48
  49     ok = vlc_vector_insert(&vec, 1, 100);
  50     assert(ok);
  51     assert(vec.size == 3);
  52     assert(vec.data[0] == 42);
  53     assert(vec.data[1] == 100);
  54     assert(vec.data[2] == 37);
  55
  56     ok = vlc_vector_push(&vec, 77);
  57     assert(ok);
  58     assert(vec.size == 4);
  59     assert(vec.data[0] == 42);
  60     assert(vec.data[1] == 100);
  61     assert(vec.data[2] == 37);
  62     assert(vec.data[3] == 77);
  63
  64     vlc_vector_remove(&vec, 1);
  65     assert(vec.size == 3);
  66     assert(vec.data[0] == 42);
  67     assert(vec.data[1] == 37);
  68     assert(vec.data[2] == 77);
  69
  70     vlc_vector_clear(&vec);
  71     assert(vec.size == 0);
  72
  73     vlc_vector_destroy(&vec);
  74 }
  75
  76 static void test_vector_push_array(void)
  77 {
  78     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
  79     bool ok;
  80
  81     ok = vlc_vector_push(&vec, 3); assert(ok);
  82     ok = vlc_vector_push(&vec, 14); assert(ok);
  83     ok = vlc_vector_push(&vec, 15); assert(ok);
  84     ok = vlc_vector_push(&vec, 92); assert(ok);
  85     ok = vlc_vector_push(&vec, 65); assert(ok);
  86     assert(vec.size == 5);
  87
  88     int items[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  89     ok = vlc_vector_push_all(&vec, items, 8);
  90
  91     assert(ok);
  92     assert(vec.size == 13);
  93     assert(vec.data[0] == 3);
  94     assert(vec.data[1] == 14);
  95     assert(vec.data[2] == 15);
  96     assert(vec.data[3] == 92);
  97     assert(vec.data[4] == 65);
  98     assert(vec.data[5] == 1);
  99     assert(vec.data[6] == 2);
 100     assert(vec.data[7] == 3);
 101     assert(vec.data[8] == 4);
 102     assert(vec.data[9] == 5);
 103     assert(vec.data[10] == 6);
 104     assert(vec.data[11] == 7);
 105     assert(vec.data[12] == 8);
 106
 107     vlc_vector_destroy(&vec);
 108 }
 109
 110 static void test_vector_insert_array(void)
 111 {
 112     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 113     bool ok;
 114
 115     ok = vlc_vector_push(&vec, 3); assert(ok);
 116     ok = vlc_vector_push(&vec, 14); assert(ok);
 117     ok = vlc_vector_push(&vec, 15); assert(ok);
 118     ok = vlc_vector_push(&vec, 92); assert(ok);
 119     ok = vlc_vector_push(&vec, 65); assert(ok);
 120     assert(vec.size == 5);
 121
 122     int items[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 123     ok = vlc_vector_insert_all(&vec, 3, items, 8);
 124     assert(ok);
 125     assert(vec.size == 13);
 126     assert(vec.data[0] == 3);
 127     assert(vec.data[1] == 14);
 128     assert(vec.data[2] == 15);
 129     assert(vec.data[3] == 1);
 130     assert(vec.data[4] == 2);
 131     assert(vec.data[5] == 3);
 132     assert(vec.data[6] == 4);
 133     assert(vec.data[7] == 5);
 134     assert(vec.data[8] == 6);
 135     assert(vec.data[9] == 7);
 136     assert(vec.data[10] == 8);
 137     assert(vec.data[11] == 92);
 138     assert(vec.data[12] == 65);
 139
 140     vlc_vector_destroy(&vec);
 141 }
 142
 143 static void test_vector_remove_slice(void)
 144 {
 145     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 146
 147     bool ok;
 148
 149     for (int i = 0; i < 100; ++i)
 150     {
 151         ok = vlc_vector_push(&vec, i);
 152         assert(ok);
 153     }
 154
 155     assert(vec.size == 100);
 156
 157     vlc_vector_remove_slice(&vec, 32, 60);
 158     assert(vec.size == 40);
 159     assert(vec.data[31] == 31);
 160     assert(vec.data[32] == 92);
 161
 162     vlc_vector_destroy(&vec);
 163 }
 164
 165 static void test_vector_swap_remove(void)
 166 {
 167     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 168
 169     bool ok;
 170
 171     ok = vlc_vector_push(&vec, 3); assert(ok);
 172     ok = vlc_vector_push(&vec, 14); assert(ok);
 173     ok = vlc_vector_push(&vec, 15); assert(ok);
 174     ok = vlc_vector_push(&vec, 92); assert(ok);
 175     ok = vlc_vector_push(&vec, 65); assert(ok);
 176     assert(vec.size == 5);
 177
 178     vlc_vector_swap_remove(&vec, 1);
 179     assert(vec.size == 4);
 180     assert(vec.data[0] == 3);
 181     assert(vec.data[1] == 65);
 182     assert(vec.data[2] == 15);
 183     assert(vec.data[3] == 92);
 184
 185     vlc_vector_destroy(&vec);
 186 }
 187
 188 static void test_vector_index_of(void)
 189 {
 190     struct VLC_VECTOR(int) vec;
 191     vlc_vector_init(&vec);
 192
 193     bool ok;
 194
 195     for (int i = 0; i < 10; ++i)
 196     {
 197         ok = vlc_vector_push(&vec, i);
 198         assert(ok);
 199     }
 200
 201     ssize_t idx;
 202
 203     vlc_vector_index_of(&vec, 0, &idx);
 204     assert(idx == 0);
 205
 206     vlc_vector_index_of(&vec, 1, &idx);
 207     assert(idx == 1);
 208
 209     vlc_vector_index_of(&vec, 4, &idx);
 210     assert(idx == 4);
 211
 212     vlc_vector_index_of(&vec, 9, &idx);
 213     assert(idx == 9);
 214
 215     vlc_vector_index_of(&vec, 12, &idx);
 216     assert(idx == -1);
 217
 218     vlc_vector_destroy(&vec);
 219 }
 220
 221 static void test_vector_foreach(void)
 222 {
 223     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 224
 225     bool ok;
 226
 227     for (int i = 0; i < 10; ++i)
 228     {
 229         ok = vlc_vector_push(&vec, i);
 230         assert(ok);
 231     }
 232
 233     int count = 0;
 234     int item;
 235     vlc_vector_foreach(item, &vec)
 236     {
 237         assert(item == count);
 238         count++;
 239     }
 240     assert(count == 10);
 241
 242     vlc_vector_destroy(&vec);
 243 }
 244
 245 static void test_vector_grow()
 246 {
 247     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 248
 249     bool ok;
 250
 251     for (int i = 0; i < 50; ++i)
 252     {
 253         ok = vlc_vector_push(&vec, i); /* append */
 254         assert(ok);
 255     }
 256
 257     assert(vec.cap >= 50);
 258     assert(vec.size == 50);
 259
 260     for (int i = 0; i < 25; ++i)
 261     {
 262         ok = vlc_vector_insert(&vec, 20, i); /* insert in the middle */
 263         assert(ok);
 264     }
 265
 266     assert(vec.cap >= 75);
 267     assert(vec.size == 75);
 268
 269     for (int i = 0; i < 25; ++i)
 270     {
 271         ok = vlc_vector_insert(&vec, 0, i); /* prepend */
 272         assert(ok);
 273     }
 274
 275     assert(vec.cap >= 100);
 276     assert(vec.size == 100);
 277
 278     for (int i = 0; i < 50; ++i)
 279         vlc_vector_remove(&vec, 20); /* remove from the middle */
 280
 281     assert(vec.cap >= 50);
 282     assert(vec.size == 50);
 283
 284     for (int i = 0; i < 25; ++i)
 285         vlc_vector_remove(&vec, 0); /* remove from the head */
 286
 287     assert(vec.cap >= 25);
 288     assert(vec.size == 25);
 289
 290     for (int i = 24; i >=0; --i)
 291         vlc_vector_remove(&vec, i); /* remove from the tail */
 292
 293     assert(vec.size == 0);
 294
 295     vlc_vector_destroy(&vec);
 296 }
 297
 298 static void test_vector_exp_growth(void)
 299 {
 300     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 301
 302     size_t oldcap = vec.cap;
 303     int realloc_count = 0;
 304     bool ok;
 305     for (int i = 0; i < 10000; ++i)
 306     {
 307         ok = vlc_vector_push(&vec, i);
 308         assert(ok);
 309         if (vec.cap != oldcap)
 310         {
 311             realloc_count++;
 312             oldcap = vec.cap;
 313         }
 314     }
 315
 316     /* Test speciically for an expected growth factor of 1.5. In practice, the
 317      * result is even lower (19) due to the first alloc of size 10 */
 318     assert(realloc_count <= 23); /* ln(10000) / ln(1.5) ~= 23 */
 319
 320     realloc_count = 0;
 321     for (int i = 9999; i >= 0; --i)
 322     {
 323         vlc_vector_remove(&vec, i);
 324         if (vec.cap != oldcap)
 325         {
 326             realloc_count++;
 327             oldcap = vec.cap;
 328         }
 329     }
 330
 331     assert(realloc_count <= 23); /* same expectations for removals */
 332     assert(realloc_count > 0); /* vlc_vector_remove() must autoshrink */
 333
 334     vlc_vector_destroy(&vec);
 335 }
 336
 337 static void test_vector_reserve(void)
 338 {
 339     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 340
 341     bool ok;
 342
 343     ok = vlc_vector_reserve(&vec, 800);
 344     assert(ok);
 345     assert(vec.cap >= 800);
 346     assert(vec.size == 0);
 347
 348     size_t initial_cap = vec.cap;
 349
 350     for (int i = 0; i < 800; ++i)
 351     {
 352         ok = vlc_vector_push(&vec, i);
 353         assert(ok);
 354         assert(vec.cap == initial_cap); /* no realloc */
 355     }
 356
 357     vlc_vector_destroy(&vec);
 358 }
 359
 360 static void test_vector_shrink_to_fit(void)
 361 {
 362     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 363
 364     bool ok;
 365
 366     ok = vlc_vector_reserve(&vec, 800);
 367     assert(ok);
 368     for (int i = 0; i < 250; ++i)
 369     {
 370         ok = vlc_vector_push(&vec, i);
 371         assert(ok);
 372     }
 373
 374     assert(vec.cap >= 800);
 375     assert(vec.size == 250);
 376
 377     vlc_vector_shrink_to_fit(&vec);
 378     assert(vec.cap == 250);
 379     assert(vec.size == 250);
 380
 381     vlc_vector_destroy(&vec);
 382 }
 383
 384 static void test_vector_move(void)
 385 {
 386     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 387
 388     for (int i = 0; i < 7; ++i)
 389     {
 390         bool ok = vlc_vector_push(&vec, i);
 391         assert(ok);
 392     }
 393
 394     /* move item at 1 so that its new position is 4 */
 395     vlc_vector_move(&vec, 1, 4);
 396
 397     assert(vec.size == 7);
 398     assert(vec.data[0] == 0);
 399     assert(vec.data[1] == 2);
 400     assert(vec.data[2] == 3);
 401     assert(vec.data[3] == 4);
 402     assert(vec.data[4] == 1);
 403     assert(vec.data[5] == 5);
 404     assert(vec.data[6] == 6);
 405
 406     vlc_vector_destroy(&vec);
 407 }
 408
 409 static void test_vector_move_slice_forward(void)
 410 {
 411     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 412
 413     for (int i = 0; i < 10; ++i)
 414     {
 415         bool ok = vlc_vector_push(&vec, i);
 416         assert(ok);
 417     }
 418
 419     /* move slice {2, 3, 4, 5} so that its new position is 5 */
 420     vlc_vector_move_slice(&vec, 2, 4, 5);
 421
 422     assert(vec.size == 10);
 423     assert(vec.data[0] == 0);
 424     assert(vec.data[1] == 1);
 425     assert(vec.data[2] == 6);
 426     assert(vec.data[3] == 7);
 427     assert(vec.data[4] == 8);
 428     assert(vec.data[5] == 2);
 429     assert(vec.data[6] == 3);
 430     assert(vec.data[7] == 4);
 431     assert(vec.data[8] == 5);
 432     assert(vec.data[9] == 9);
 433
 434     vlc_vector_destroy(&vec);
 435 }
 436
 437 static void test_vector_move_slice_backward(void)
 438 {
 439     struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
 440
 441     for (int i = 0; i < 10; ++i)
 442     {
 443         bool ok = vlc_vector_push(&vec, i);
 444         assert(ok);
 445     }
 446
 447     /* move slice {5, 6, 7} so that its new position is 2 */
 448     vlc_vector_move_slice(&vec, 5, 3, 2);
 449
 450     assert(vec.size == 10);
 451     assert(vec.data[0] == 0);
 452     assert(vec.data[1] == 1);
 453     assert(vec.data[2] == 5);
 454     assert(vec.data[3] == 6);
 455     assert(vec.data[4] == 7);
 456     assert(vec.data[5] == 2);
 457     assert(vec.data[6] == 3);
 458     assert(vec.data[7] == 4);
 459     assert(vec.data[8] == 8);
 460     assert(vec.data[9] == 9);
 461
 462     vlc_vector_destroy(&vec);
 463 }
 464
 465 int main(void) {
 466     test_vector_insert_remove();
 467     test_vector_push_array();
 468     test_vector_insert_array();
 469     test_vector_remove_slice();
 470     test_vector_swap_remove();
 471     test_vector_move();
 472     test_vector_move_slice_forward();
 473     test_vector_move_slice_backward();
 474     test_vector_index_of();
 475     test_vector_foreach();
 476     test_vector_grow();
 477     test_vector_exp_growth();
 478     test_vector_reserve();
 479     test_vector_shrink_to_fit();
 480     return 0;
 481 }