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