src/xbt/dynar_test.cpp

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