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