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