src/xbt/dynar_test.cpp

   1 /* a generic DYNamic ARray implementation.                                  */
   2
   3 /* Copyright (c) 2004-2019. The SimGrid Team. All rights reserved.          */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 #include "xbt/dynar.h"
   9 #include "xbt/sysdep.h"
  10
  11 #include "catch.hpp"
  12
  13 constexpr int NB_ELEM = 5000;
  14
  15 TEST_CASE("xbt::dynar: generic C vector", "dynar")
  16 {
  17
  18   SECTION("Dynars of integers")
  19   {
  20     /* Vars_decl [doxygen cruft] */
  21     int cpt;
  22     unsigned int cursor;
  23
  24     INFO("==== Traverse the empty dynar");
  25     xbt_dynar_t d = xbt_dynar_new(sizeof(int), nullptr);
  26     xbt_dynar_foreach (d, cursor, cpt) {
  27       xbt_die("Damnit, there is something in the empty dynar");
  28     }
  29     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
  30     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
  31     /* in your code is naturally the way to go outside a regression test */
  32
  33     INFO("==== Push " << NB_ELEM << " int, set them again 3 times, traverse them, shift them");
  34     /* Populate_ints [doxygen cruft] */
  35     /* 1. Populate the dynar */
  36     d = xbt_dynar_new(sizeof(int), nullptr);
  37     for (int i = 0; i < NB_ELEM; i++) {
  38       xbt_dynar_push_as(d, int, i); /* This is faster (and possible only with scalars) */
  39       /* xbt_dynar_push(d, &i);      This would also work */
  40     }
  41
  42     /* 2. Traverse manually the dynar */
  43     for (int i = 0; i < NB_ELEM; i++) {
  44       int* iptr = (int*)xbt_dynar_get_ptr(d, i);
  45       REQUIRE(i == *iptr); // The retrieved value is not the same than the injected one
  46     }
  47
  48     /* 3. Traverse the dynar using the neat macro to that extend */
  49     xbt_dynar_foreach (d, cursor, cpt) {
  50       REQUIRE(cursor == (unsigned int)cpt); // The retrieved value is not the same than the injected one
  51     }
  52     /* end_of_traversal */
  53
  54     for (int i = 0; i < NB_ELEM; i++)
  55       *(int*)xbt_dynar_get_ptr(d, i) = i;
  56
  57     for (int i = 0; i < NB_ELEM; i++)
  58       *(int*)xbt_dynar_get_ptr(d, i) = i;
  59
  60     for (int i = 0; i < NB_ELEM; i++)
  61       *(int*)xbt_dynar_get_ptr(d, i) = i;
  62
  63     int count = 0;
  64     xbt_dynar_foreach (d, cursor, cpt) {
  65       REQUIRE(cpt == count); // The retrieved value is not the same than the injected one
  66       count++;
  67     }
  68     REQUIRE(count == NB_ELEM); // Cannot retrieve all my values. cpt is the last one I got
  69
  70     /* shifting [doxygen cruft] */
  71     /* 4. Shift all the values */
  72     for (int i = 0; i < NB_ELEM; i++) {
  73       int val;
  74       xbt_dynar_shift(d, &val);
  75       REQUIRE(val == i); // The retrieved value is not the same than the injected one
  76     }
  77     REQUIRE(xbt_dynar_is_empty(d));
  78
  79     for (int i = 0; i < NB_ELEM; i++) {
  80       xbt_dynar_push_as(d, int, -1);
  81     }
  82     int* pi;
  83     xbt_dynar_foreach_ptr(d, cursor, pi) { *pi = 0; }
  84     xbt_dynar_foreach (d, cursor, cpt) {
  85       REQUIRE(cpt == 0); // The value is not the same as the expected one.
  86     }
  87     xbt_dynar_foreach_ptr(d, cursor, pi) { *pi = 1; }
  88     xbt_dynar_foreach (d, cursor, cpt) {
  89       REQUIRE(cpt == 1); // The value is not the same as the expected one
  90     }
  91
  92     /* 5. Free the resources */
  93     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
  94     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
  95     /* in your code is naturally the way to go outside a regression test */
  96
  97     INFO("==== Unshift/pop " << NB_ELEM << " int");
  98     d = xbt_dynar_new(sizeof(int), nullptr);
  99     for (int i = 0; i < NB_ELEM; i++) {
 100       xbt_dynar_unshift(d, &i);
 101     }
 102     for (int i = 0; i < NB_ELEM; i++) {
 103       int val = xbt_dynar_pop_as(d, int);
 104       REQUIRE(val == i); // The retrieved value is not the same than the injected one
 105     }
 106     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 107     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 108     /* in your code is naturally the way to go outside a regression test */
 109
 110     INFO("==== Push " << NB_ELEM << "%d int, insert 1000 int in the middle, shift everything");
 111     d = xbt_dynar_new(sizeof(int), nullptr);
 112     for (int i = 0; i < NB_ELEM; i++) {
 113       xbt_dynar_push_as(d, int, i);
 114     }
 115     for (int i = 0; i < NB_ELEM / 5; i++) {
 116       xbt_dynar_insert_at_as(d, NB_ELEM / 2, int, i);
 117     }
 118
 119     for (int i = 0; i < NB_ELEM / 2; i++) {
 120       int val;
 121       xbt_dynar_shift(d, &val);
 122       REQUIRE(val == i); // The retrieved value is not the same than the injected one at the begining
 123     }
 124     for (int i = 999; i >= 0; i--) {
 125       int val;
 126       xbt_dynar_shift(d, &val);
 127       REQUIRE(val == i); // The retrieved value is not the same than the injected one in the middle
 128     }
 129     for (int i = 2500; i < NB_ELEM; i++) {
 130       int val;
 131       xbt_dynar_shift(d, &val);
 132       REQUIRE(val == i); // The retrieved value is not the same than the injected one at the end
 133     }
 134     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 135     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 136     /* in your code is naturally the way to go outside a regression test */
 137
 138     INFO("==== Push " << NB_ELEM << " int, remove 2000-4000. free the rest");
 139     d = xbt_dynar_new(sizeof(int), nullptr);
 140     for (int i = 0; i < NB_ELEM; i++)
 141       xbt_dynar_push_as(d, int, i);
 142
 143     for (int i = 2000; i < 4000; i++) {
 144       int val;
 145       xbt_dynar_remove_at(d, 2000, &val);
 146       REQUIRE(val == i); // Remove a bad value
 147     }
 148     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 149     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 150     /* in your code is naturally the way to go outside a regression test */
 151   }
 152
 153   /*******************************************************************************/
 154   SECTION("Using the xbt_dynar_insert and xbt_dynar_remove functions")
 155   {
 156     xbt_dynar_t d = xbt_dynar_new(sizeof(unsigned int), nullptr);
 157     unsigned int cursor;
 158
 159     INFO("==== Insert " << NB_ELEM << " int, traverse them, remove them");
 160     /* Populate_ints [doxygen cruft] */
 161     /* 1. Populate the dynar */
 162     for (int i = 0; i < NB_ELEM; i++) {
 163       xbt_dynar_insert_at(d, i, &i);
 164     }
 165
 166     /* 3. Traverse the dynar */
 167     int cpt;
 168     xbt_dynar_foreach (d, cursor, cpt) {
 169       REQUIRE(cursor == (unsigned int)cpt); // The retrieved value is not the same than the injected one
 170     }
 171     /* end_of_traversal */
 172
 173     /* Re-fill with the same values using set_as (and re-verify) */
 174     for (int i = 0; i < NB_ELEM; i++)
 175       xbt_dynar_set_as(d, i, int, i);
 176     xbt_dynar_foreach (d, cursor, cpt)
 177       REQUIRE(cursor == (unsigned int)cpt); // The retrieved value is not the same than the injected one
 178
 179     for (int i = 0; i < NB_ELEM; i++) {
 180       int val;
 181       xbt_dynar_remove_at(d, 0, &val);
 182       REQUIRE(i == val); // The retrieved value is not the same than the injected one
 183     }
 184     REQUIRE(xbt_dynar_is_empty(d));
 185     xbt_dynar_free(&d);
 186
 187     /* ********************* */
 188     INFO("==== Insert " << NB_ELEM << " int in reverse order, traverse them, remove them");
 189     d = xbt_dynar_new(sizeof(int), nullptr);
 190     for (int i = NB_ELEM - 1; i >= 0; i--) {
 191       xbt_dynar_replace(d, i, &i);
 192     }
 193
 194     /* 3. Traverse the dynar */
 195     xbt_dynar_foreach (d, cursor, cpt) {
 196       REQUIRE(cursor == (unsigned)cpt); // The retrieved value is not the same than the injected one
 197     }
 198     /* end_of_traversal */
 199
 200     for (int i = NB_ELEM - 1; i >= 0; i--) {
 201       int val;
 202       xbt_dynar_remove_at(d, xbt_dynar_length(d) - 1, &val);
 203       REQUIRE(val == i); // The retrieved value is not the same than the injected one
 204     }
 205     REQUIRE(xbt_dynar_is_empty(d));
 206     xbt_dynar_free(&d);
 207   }
 208
 209   /*******************************************************************************/
 210   SECTION("Dynars of doubles")
 211   {
 212     xbt_dynar_t d;
 213     int cpt;
 214     unsigned int cursor;
 215     double d1;
 216     double d2;
 217
 218     INFO("==== Traverse the empty dynar");
 219     d = xbt_dynar_new(sizeof(int), nullptr);
 220     xbt_dynar_foreach (d, cursor, cpt) {
 221       REQUIRE(false); // Damnit, there is something in the empty dynar
 222     }
 223     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 224     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 225     /* in your code is naturally the way to go outside a regression test */
 226
 227     INFO("==== Push/shift 5000 doubles");
 228     d = xbt_dynar_new(sizeof(double), nullptr);
 229     for (int i = 0; i < 5000; i++) {
 230       d1 = (double)i;
 231       xbt_dynar_push(d, &d1);
 232     }
 233     xbt_dynar_foreach (d, cursor, d2) {
 234       d1 = (double)cursor;
 235       REQUIRE(d1 == d2); // The retrieved value is not the same than the injected one
 236     }
 237     for (int i = 0; i < 5000; i++) {
 238       d1 = (double)i;
 239       xbt_dynar_shift(d, &d2);
 240       REQUIRE(d1 == d2); // The retrieved value is not the same than the injected one
 241     }
 242     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 243     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 244     /* in your code is naturally the way to go outside a regression test */
 245
 246     INFO("==== Unshift/pop 5000 doubles");
 247     d = xbt_dynar_new(sizeof(double), nullptr);
 248     for (int i = 0; i < 5000; i++) {
 249       d1 = (double)i;
 250       xbt_dynar_unshift(d, &d1);
 251     }
 252     for (int i = 0; i < 5000; i++) {
 253       d1 = (double)i;
 254       xbt_dynar_pop(d, &d2);
 255       REQUIRE(d1 == d2); // The retrieved value is not the same than the injected one
 256     }
 257     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 258     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 259     /* in your code is naturally the way to go outside a regression test */
 260
 261     INFO("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
 262     d = xbt_dynar_new(sizeof(double), nullptr);
 263     for (int i = 0; i < 5000; i++) {
 264       d1 = (double)i;
 265       xbt_dynar_push(d, &d1);
 266     }
 267     for (int i = 0; i < 1000; i++) {
 268       d1 = (double)i;
 269       xbt_dynar_insert_at(d, 2500, &d1);
 270     }
 271
 272     for (int i = 0; i < 2500; i++) {
 273       d1 = (double)i;
 274       xbt_dynar_shift(d, &d2);
 275       REQUIRE(d1 == d2); // The retrieved value is not the same than the injected one at the begining
 276     }
 277     for (int i = 999; i >= 0; i--) {
 278       d1 = (double)i;
 279       xbt_dynar_shift(d, &d2);
 280       REQUIRE(d1 == d2); // The retrieved value is not the same than the injected one in the middle
 281     }
 282     for (int i = 2500; i < 5000; i++) {
 283       d1 = (double)i;
 284       xbt_dynar_shift(d, &d2);
 285       REQUIRE(d1 == d2); // The retrieved value is not the same than the injected one at the end
 286     }
 287     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 288     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 289     /* in your code is naturally the way to go outside a regression test */
 290
 291     INFO("==== Push 5000 double, remove 2000-4000. free the rest");
 292     d = xbt_dynar_new(sizeof(double), nullptr);
 293     for (int i = 0; i < 5000; i++) {
 294       d1 = (double)i;
 295       xbt_dynar_push(d, &d1);
 296     }
 297     for (int i = 2000; i < 4000; i++) {
 298       d1 = (double)i;
 299       xbt_dynar_remove_at(d, 2000, &d2);
 300       REQUIRE(d1 == d2); // Remove a bad value
 301     }
 302     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 303     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 304     /* in your code is naturally the way to go outside a regression test */
 305   }
 306
 307   /*******************************************************************************/
 308   SECTION("Dynars of strings")
 309   {
 310     unsigned int iter;
 311     char buf[1024];
 312     char* s1;
 313     char* s2;
 314
 315     INFO("==== Traverse the empty dynar");
 316     xbt_dynar_t d = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 317     xbt_dynar_foreach (d, iter, s1) {
 318       REQUIRE(false); // Damnit, there is something in the empty dynar"
 319     }
 320     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 321     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 322     /* in your code is naturally the way to go outside a regression test */
 323
 324     INFO("==== Push " << NB_ELEM << " strings, set them again 3 times, shift them");
 325     /* Populate_str [doxygen cruft] */
 326     d = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 327     /* 1. Populate the dynar */
 328     for (int i = 0; i < NB_ELEM; i++) {
 329       snprintf(buf, 1023, "%d", i);
 330       s1 = xbt_strdup(buf);
 331       xbt_dynar_push(d, &s1);
 332     }
 333     for (int k = 0; k < 3; k++) {
 334       for (int i = 0; i < NB_ELEM; i++) {
 335         snprintf(buf, 1023, "%d", i);
 336         s1 = xbt_strdup(buf);
 337         xbt_dynar_replace(d, i, &s1);
 338       }
 339     }
 340     for (int i = 0; i < NB_ELEM; i++) {
 341       snprintf(buf, 1023, "%d", i);
 342       xbt_dynar_shift(d, &s2);
 343       REQUIRE(not strcmp(buf, s2)); // The retrieved value is not the same than the injected one
 344       xbt_free(s2);
 345     }
 346     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 347     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 348     /* in your code is naturally the way to go outside a regression test */
 349
 350     INFO("==== Unshift, traverse and pop " << NB_ELEM << " strings");
 351     d = xbt_dynar_new(sizeof(char**), &xbt_free_ref);
 352     for (int i = 0; i < NB_ELEM; i++) {
 353       snprintf(buf, 1023, "%d", i);
 354       s1 = xbt_strdup(buf);
 355       xbt_dynar_unshift(d, &s1);
 356     }
 357     /* 2. Traverse the dynar with the macro */
 358     xbt_dynar_foreach (d, iter, s1) {
 359       snprintf(buf, 1023, "%u", NB_ELEM - iter - 1);
 360       REQUIRE(not strcmp(buf, s1)); // The retrieved value is not the same than the injected one
 361     }
 362     /* 3. Traverse the dynar with the macro */
 363     for (int i = 0; i < NB_ELEM; i++) {
 364       snprintf(buf, 1023, "%d", i);
 365       xbt_dynar_pop(d, &s2);
 366       REQUIRE(not strcmp(buf, s2)); // The retrieved value is not the same than the injected one
 367       xbt_free(s2);
 368     }
 369     /* 4. Free the resources */
 370     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 371     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 372     /* in your code is naturally the way to go outside a regression test */
 373
 374     INFO("==== Push " << NB_ELEM << " strings, insert " << (NB_ELEM / 5) << " strings in the middle, shift everything");
 375     d = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 376     for (int i = 0; i < NB_ELEM; i++) {
 377       snprintf(buf, 1023, "%d", i);
 378       s1 = xbt_strdup(buf);
 379       xbt_dynar_push(d, &s1);
 380     }
 381     for (int i = 0; i < NB_ELEM / 5; i++) {
 382       snprintf(buf, 1023, "%d", i);
 383       s1 = xbt_strdup(buf);
 384       xbt_dynar_insert_at(d, NB_ELEM / 2, &s1);
 385     }
 386
 387     for (int i = 0; i < NB_ELEM / 2; i++) {
 388       snprintf(buf, 1023, "%d", i);
 389       xbt_dynar_shift(d, &s2);
 390       REQUIRE(not strcmp(buf, s2)); // The retrieved value is not the same than the injected one at the beginning
 391       xbt_free(s2);
 392     }
 393     for (int i = (NB_ELEM / 5) - 1; i >= 0; i--) {
 394       snprintf(buf, 1023, "%d", i);
 395       xbt_dynar_shift(d, &s2);
 396       REQUIRE(not strcmp(buf, s2)); // The retrieved value is not the same than the injected one in the middle
 397       xbt_free(s2);
 398     }
 399     for (int i = NB_ELEM / 2; i < NB_ELEM; i++) {
 400       snprintf(buf, 1023, "%d", i);
 401       xbt_dynar_shift(d, &s2);
 402       REQUIRE(not strcmp(buf, s2)); // The retrieved value is not the same than the injected one at the end
 403       xbt_free(s2);
 404     }
 405     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 406     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 407     /* in your code is naturally the way to go outside a regression test */
 408
 409     INFO("==== Push " << NB_ELEM << " strings, remove " << (2 * NB_ELEM / 5) << "-" << (4 * NB_ELEM / 5)
 410                       << ". free the rest");
 411     d = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 412     for (int i = 0; i < NB_ELEM; i++) {
 413       snprintf(buf, 1023, "%d", i);
 414       s1 = xbt_strdup(buf);
 415       xbt_dynar_push(d, &s1);
 416     }
 417     for (int i = 2 * (NB_ELEM / 5); i < 4 * (NB_ELEM / 5); i++) {
 418       snprintf(buf, 1023, "%d", i);
 419       xbt_dynar_remove_at(d, 2 * (NB_ELEM / 5), &s2);
 420       REQUIRE(not strcmp(buf, s2)); // Remove a bad value
 421       xbt_free(s2);
 422     }
 423     xbt_dynar_free(&d); /* end_of_doxygen */
 424   }
 425 }