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 "simgrid/Exception.hpp"
   9 #include "xbt/dynar.h"
  10 #include "xbt/ex.h"
  11 #include "xbt/log.h"
  12 #include "xbt/misc.h"
  13 #include "xbt/sysdep.h"
  14 #include <sys/types.h>
  15
  16 #include "src/include/catch.hpp"
  17
  18 #define NB_ELEM 5000
  19
  20 TEST_CASE("xbt::dynar: generic C vector", "dynar")
  21 {
  22
  23   SECTION("Dynars of integers")
  24   {
  25     /* Vars_decl [doxygen cruft] */
  26     int i;
  27     unsigned int cursor;
  28
  29     INFO("==== Traverse the empty dynar");
  30     xbt_dynar_t d = xbt_dynar_new(sizeof(int), nullptr);
  31     xbt_dynar_foreach (d, cursor, i) {
  32       xbt_die("Damnit, there is something in the empty dynar");
  33     }
  34     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
  35     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
  36     /* in your code is naturally the way to go outside a regression test */
  37
  38     INFO("==== Push " << NB_ELEM << " int, set them again 3 times, traverse them, shift them");
  39     /* Populate_ints [doxygen cruft] */
  40     /* 1. Populate the dynar */
  41     d = xbt_dynar_new(sizeof(int), nullptr);
  42     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
  43       xbt_dynar_push_as(d, int, cpt); /* This is faster (and possible only with scalars) */
  44       /* xbt_dynar_push(d,&cpt);       This would also work */
  45     }
  46
  47     /* 2. Traverse manually the dynar */
  48     for (cursor = 0; cursor < NB_ELEM; cursor++) {
  49       int* iptr = (int*)xbt_dynar_get_ptr(d, cursor);
  50       REQUIRE(cursor == (unsigned int)*iptr); // The retrieved value is not the same than the injected one
  51     }
  52
  53     /* 3. Traverse the dynar using the neat macro to that extend */
  54     int cpt;
  55     xbt_dynar_foreach (d, cursor, cpt) {
  56       REQUIRE(cursor == (unsigned int)cpt); // The retrieved value is not the same than the injected one
  57     }
  58     /* end_of_traversal */
  59
  60     for (int cpt = 0; cpt < NB_ELEM; cpt++)
  61       *(int*)xbt_dynar_get_ptr(d, cpt) = cpt;
  62
  63     for (int cpt = 0; cpt < NB_ELEM; cpt++)
  64       *(int*)xbt_dynar_get_ptr(d, cpt) = cpt;
  65
  66     for (int cpt = 0; cpt < NB_ELEM; cpt++)
  67       *(int*)xbt_dynar_get_ptr(d, cpt) = cpt;
  68
  69     cpt = 0;
  70     xbt_dynar_foreach (d, cursor, i) {
  71       REQUIRE(i == cpt); // The retrieved value is not the same than the injected one
  72       cpt++;
  73     }
  74     REQUIRE(cpt == NB_ELEM); // Cannot retrieve all my values. cpt is the last one I got
  75
  76     /* shifting [doxygen cruft] */
  77     /* 4. Shift all the values */
  78     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
  79       xbt_dynar_shift(d, &i);
  80       REQUIRE(i == cpt); // The retrieved value is not the same than the injected one
  81     }
  82     REQUIRE(xbt_dynar_is_empty(d));
  83
  84     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
  85       xbt_dynar_push_as(d, int, -1);
  86     }
  87     int* pi;
  88     xbt_dynar_foreach_ptr(d, cursor, pi) { *pi = 0; }
  89     xbt_dynar_foreach (d, cursor, i) {
  90       REQUIRE(i == 0); // The value is not the same as the expected one.
  91     }
  92     xbt_dynar_foreach_ptr(d, cursor, pi) { *pi = 1; }
  93     xbt_dynar_foreach (d, cursor, i) {
  94       REQUIRE(i == 1); // The value is not the same as the expected one
  95     }
  96
  97     /* 5. Free the resources */
  98     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
  99     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 100     /* in your code is naturally the way to go outside a regression test */
 101
 102     INFO("==== Unshift/pop " << NB_ELEM << " int");
 103     d = xbt_dynar_new(sizeof(int), nullptr);
 104     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
 105       xbt_dynar_unshift(d, &cpt);
 106     }
 107     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
 108       i = xbt_dynar_pop_as(d, int);
 109       REQUIRE(i == cpt); // The retrieved value is not the same than the injected one
 110     }
 111     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 112     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 113     /* in your code is naturally the way to go outside a regression test */
 114
 115     INFO("==== Push " << NB_ELEM << "%d int, insert 1000 int in the middle, shift everything");
 116     d = xbt_dynar_new(sizeof(int), nullptr);
 117     for (cpt = 0; cpt < NB_ELEM; cpt++) {
 118       xbt_dynar_push_as(d, int, cpt);
 119     }
 120     for (cpt = 0; cpt < NB_ELEM / 5; cpt++) {
 121       xbt_dynar_insert_at_as(d, NB_ELEM / 2, int, cpt);
 122     }
 123
 124     for (cpt = 0; cpt < NB_ELEM / 2; cpt++) {
 125       xbt_dynar_shift(d, &i);
 126       REQUIRE(i == cpt); // The retrieved value is not the same than the injected one at the begining
 127     }
 128     for (cpt = 999; cpt >= 0; cpt--) {
 129       xbt_dynar_shift(d, &i);
 130       REQUIRE(i == cpt); // The retrieved value is not the same than the injected one in the middle
 131     }
 132     for (cpt = 2500; cpt < NB_ELEM; cpt++) {
 133       xbt_dynar_shift(d, &i);
 134       REQUIRE(i == cpt); // The retrieved value is not the same than the injected one at the end
 135     }
 136     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 137     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 138     /* in your code is naturally the way to go outside a regression test */
 139
 140     INFO("==== Push " << NB_ELEM << " int, remove 2000-4000. free the rest");
 141     d = xbt_dynar_new(sizeof(int), nullptr);
 142     for (cpt = 0; cpt < NB_ELEM; cpt++)
 143       xbt_dynar_push_as(d, int, cpt);
 144
 145     for (cpt = 2000; cpt < 4000; cpt++) {
 146       xbt_dynar_remove_at(d, 2000, &i);
 147       REQUIRE(i == cpt); // Remove a bad value
 148     }
 149     xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */
 150     xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing  it only once */
 151     /* in your code is naturally the way to go outside a regression test */
 152   }
 153
 154   /*******************************************************************************/
 155   SECTION("Using the xbt_dynar_insert and xbt_dynar_remove functions")
 156   {
 157     xbt_dynar_t d = xbt_dynar_new(sizeof(unsigned int), nullptr);
 158     unsigned int cursor;
 159
 160     INFO("==== Insert " << NB_ELEM << " int, traverse them, remove them");
 161     /* Populate_ints [doxygen cruft] */
 162     /* 1. Populate the dynar */
 163     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
 164       xbt_dynar_insert_at(d, cpt, &cpt);
 165     }
 166
 167     /* 3. Traverse the dynar */
 168     int cpt;
 169     xbt_dynar_foreach (d, cursor, cpt) {
 170       REQUIRE(cursor == (unsigned int)cpt); // The retrieved value is not the same than the injected one
 171     }
 172     /* end_of_traversal */
 173
 174     /* Re-fill with the same values using set_as (and re-verify) */
 175     for (int cpt = 0; cpt < NB_ELEM; cpt++)
 176       xbt_dynar_set_as(d, cpt, int, cpt);
 177     xbt_dynar_foreach (d, cursor, cpt)
 178       REQUIRE(cursor == (unsigned int)cpt); // The retrieved value is not the same than the injected one
 179
 180     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
 181       int val;
 182       xbt_dynar_remove_at(d, 0, &val);
 183       REQUIRE(cpt == val); // The retrieved value is not the same than the injected one
 184     }
 185     REQUIRE(xbt_dynar_is_empty(d));
 186     xbt_dynar_free(&d);
 187
 188     /* ********************* */
 189     INFO("==== Insert " << NB_ELEM << " int in reverse order, traverse them, remove them");
 190     d = xbt_dynar_new(sizeof(int), nullptr);
 191     for (int cpt = NB_ELEM - 1; cpt >= 0; cpt--) {
 192       xbt_dynar_replace(d, cpt, &cpt);
 193     }
 194
 195     /* 3. Traverse the dynar */
 196     xbt_dynar_foreach (d, cursor, cpt) {
 197       REQUIRE(cursor == (unsigned)cpt); // The retrieved value is not the same than the injected one
 198     }
 199     /* end_of_traversal */
 200
 201     for (cpt = NB_ELEM - 1; cpt >= 0; cpt--) {
 202       int val;
 203       xbt_dynar_remove_at(d, xbt_dynar_length(d) - 1, &val);
 204       REQUIRE(cpt == val); // The retrieved value is not the same than the injected one
 205     }
 206     REQUIRE(xbt_dynar_is_empty(d));
 207     xbt_dynar_free(&d);
 208   }
 209
 210   /*******************************************************************************/
 211   SECTION("Dynars of doubles")
 212   {
 213     xbt_dynar_t d;
 214     int cpt;
 215     unsigned int cursor;
 216     double d1, 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 (cpt = 0; cpt < 5000; cpt++) {
 230       d1 = (double)cpt;
 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 (cpt = 0; cpt < 5000; cpt++) {
 238       d1 = (double)cpt;
 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 (cpt = 0; cpt < 5000; cpt++) {
 249       d1 = (double)cpt;
 250       xbt_dynar_unshift(d, &d1);
 251     }
 252     for (cpt = 0; cpt < 5000; cpt++) {
 253       d1 = (double)cpt;
 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 (cpt = 0; cpt < 5000; cpt++) {
 264       d1 = (double)cpt;
 265       xbt_dynar_push(d, &d1);
 266     }
 267     for (cpt = 0; cpt < 1000; cpt++) {
 268       d1 = (double)cpt;
 269       xbt_dynar_insert_at(d, 2500, &d1);
 270     }
 271
 272     for (cpt = 0; cpt < 2500; 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 at the begining
 276     }
 277     for (cpt = 999; cpt >= 0; 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 in the middle
 281     }
 282     for (cpt = 2500; cpt < 5000; cpt++) {
 283       d1 = (double)cpt;
 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 (cpt = 0; cpt < 5000; cpt++) {
 294       d1 = (double)cpt;
 295       xbt_dynar_push(d, &d1);
 296     }
 297     for (cpt = 2000; cpt < 4000; cpt++) {
 298       d1 = (double)cpt;
 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, *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 cpt = 0; cpt < NB_ELEM; cpt++) {
 328       snprintf(buf, 1023, "%d", cpt);
 329       s1 = xbt_strdup(buf);
 330       xbt_dynar_push(d, &s1);
 331     }
 332     for (int i = 0; i < 3; i++) {
 333       for (int cpt = 0; cpt < NB_ELEM; cpt++) {
 334         snprintf(buf, 1023, "%d", cpt);
 335         s1 = xbt_strdup(buf);
 336         xbt_dynar_replace(d, cpt, &s1);
 337       }
 338     }
 339     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
 340       snprintf(buf, 1023, "%d", cpt);
 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 cpt = 0; cpt < NB_ELEM; cpt++) {
 352       snprintf(buf, 1023, "%d", cpt);
 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 cpt = 0; cpt < NB_ELEM; cpt++) {
 363       snprintf(buf, 1023, "%d", cpt);
 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 cpt = 0; cpt < NB_ELEM; cpt++) {
 376       snprintf(buf, 1023, "%d", cpt);
 377       s1 = xbt_strdup(buf);
 378       xbt_dynar_push(d, &s1);
 379     }
 380     for (int cpt = 0; cpt < NB_ELEM / 5; cpt++) {
 381       snprintf(buf, 1023, "%d", cpt);
 382       s1 = xbt_strdup(buf);
 383       xbt_dynar_insert_at(d, NB_ELEM / 2, &s1);
 384     }
 385
 386     for (int cpt = 0; cpt < NB_ELEM / 2; cpt++) {
 387       snprintf(buf, 1023, "%d", cpt);
 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 cpt = (NB_ELEM / 5) - 1; cpt >= 0; cpt--) {
 393       snprintf(buf, 1023, "%d", cpt);
 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 cpt = NB_ELEM / 2; cpt < NB_ELEM; cpt++) {
 399       snprintf(buf, 1023, "%d", cpt);
 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 cpt = 0; cpt < NB_ELEM; cpt++) {
 412       snprintf(buf, 1023, "%d", cpt);
 413       s1 = xbt_strdup(buf);
 414       xbt_dynar_push(d, &s1);
 415     }
 416     for (int cpt = 2 * (NB_ELEM / 5); cpt < 4 * (NB_ELEM / 5); cpt++) {
 417       snprintf(buf, 1023, "%d", cpt);
 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 }