src/xbt/dynar.c

   1 /* $Id$ */
   2
   3 /* a generic DYNamic ARray implementation.                                  */
   4
   5 /* Copyright (c) 2003, 2004 Martin Quinson. All rights reserved.            */
   6
   7 /* This program is free software; you can redistribute it and/or modify it
   8  * under the terms of the license (GNU LGPL) which comes with this package. */
   9
  10 #include "portable.h" /* SIZEOF_MAX */
  11 #include "xbt/misc.h"
  12 #include "xbt/sysdep.h"
  13 #include "xbt/log.h"
  14 #include "xbt/dynar.h"
  15 #include <sys/types.h>
  16
  17 #include "xbt/dynar_private.h" /* type definition, which we share with the
  18                                   code in charge of sending this across the net */
  19
  20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
  21
  22
  23 #define __sanity_check_dynar(dynar)       \
  24            xbt_assert0(dynar,           \
  25                         "dynar is NULL")
  26 #define __sanity_check_idx(idx)                \
  27            xbt_assert1(idx >= 0,             \
  28                         "dynar idx(=%d) < 0", \
  29                         (int) (idx))
  30 #define __check_inbound_idx(dynar, idx)                                                \
  31            xbt_assert2(idx < dynar->used,                                             \
  32                         "dynar is not that long. You asked %d, but it's only %lu long", \
  33                         (int) (idx), (unsigned long) dynar->used)
  34 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
  35            xbt_assert2(idx <= dynar->used,                                            \
  36                         "dynar is not that long. You asked %d, but it's only %lu long", \
  37                         (int) (idx), (unsigned long) dynar->used)
  38 #define __check_populated_dynar(dynar)            \
  39            xbt_assert1(dynar->used,              \
  40                         "dynar %p contains nothing",(void*)dynar)
  41
  42 static _XBT_INLINE
  43 void _xbt_clear_mem(void * const ptr,
  44                      const unsigned long length) {
  45   memset(ptr, 0, length);
  46 }
  47
  48 static _XBT_INLINE
  49 void
  50 _xbt_dynar_expand(xbt_dynar_t const dynar,
  51                    const int          nb) {
  52   const unsigned long old_size    = dynar->size;
  53
  54   if (nb > old_size) {
  55     char * const old_data    = (char *) dynar->data;
  56
  57     const unsigned long elmsize     = dynar->elmsize;
  58     const unsigned long old_length  = old_size*elmsize;
  59
  60     const unsigned long used        = dynar->used;
  61     const unsigned long used_length = used*elmsize;
  62
  63     const unsigned long new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
  64     const unsigned long new_length  = new_size*elmsize;
  65     char * const new_data    = (char *) xbt_malloc0(elmsize*new_size);
  66
  67     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
  68
  69     if (old_data) {
  70       memcpy(new_data, old_data, used_length);
  71       _xbt_clear_mem(old_data, old_length);
  72       free(old_data);
  73     }
  74
  75     _xbt_clear_mem(new_data + used_length, new_length - used_length);
  76
  77     dynar->size = new_size;
  78     dynar->data = new_data;
  79   }
  80 }
  81
  82 static _XBT_INLINE
  83 void *
  84 _xbt_dynar_elm(const xbt_dynar_t  dynar,
  85                 const unsigned long idx) {
  86   char * const data    = (char*) dynar->data;
  87   const unsigned long elmsize = dynar->elmsize;
  88
  89   return data + idx*elmsize;
  90 }
  91
  92 static _XBT_INLINE
  93 void
  94 _xbt_dynar_get_elm(void  * const       dst,
  95                     const xbt_dynar_t  dynar,
  96                     const unsigned long idx) {
  97   void * const elm     = _xbt_dynar_elm(dynar, idx);
  98   const unsigned long elmsize = dynar->elmsize;
  99
 100   memcpy(dst, elm, elmsize);
 101 }
 102
 103 static _XBT_INLINE
 104 void
 105 _xbt_dynar_put_elm(const xbt_dynar_t  dynar,
 106                     const unsigned long idx,
 107                     const void * const  src) {
 108   void * const elm     = _xbt_dynar_elm(dynar, idx);
 109   const unsigned long elmsize = dynar->elmsize;
 110
 111   memcpy(elm, src, elmsize);
 112 }
 113
 114 void
 115 xbt_dynar_dump(xbt_dynar_t dynar) {
 116   INFO5("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
 117         dynar->size, dynar->used, dynar->elmsize, dynar->data, dynar->free_f);
 118 }
 119
 120 /** @brief Constructor
 121  *
 122  * \param elmsize size of each element in the dynar
 123  * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
 124  *
 125  * Creates a new dynar. If a free_func is provided, the elements have to be
 126  * pointer of pointer. That is to say that dynars can contain either base
 127  * types (int, char, double, etc) or pointer of pointers (struct **).
 128  */
 129 xbt_dynar_t
 130 xbt_dynar_new(const unsigned long           elmsize,
 131                void_f_pvoid_t * const free_f) {
 132
 133   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
 134
 135   dynar->size    = 0;
 136   dynar->used    = 0;
 137   dynar->elmsize = elmsize;
 138   dynar->data    = NULL;
 139   dynar->free_f    = free_f;
 140
 141   return dynar;
 142 }
 143
 144 /** @brief Destructor of the structure not touching to the content
 145  *
 146  * \param dynar poor victim
 147  *
 148  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
 149  * is not touched (the \a free_f function is not used)
 150  */
 151 void
 152 xbt_dynar_free_container(xbt_dynar_t *dynar) {
 153   if (dynar && *dynar) {
 154
 155     if ((*dynar)->data) {
 156       _xbt_clear_mem((*dynar)->data, (*dynar)->size);
 157       free((*dynar)->data);
 158     }
 159
 160     _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
 161
 162     free(*dynar);
 163     *dynar=NULL;
 164   }
 165 }
 166
 167 /** @brief Frees the content and set the size to 0
 168  *
 169  * \param dynar who to squeeze
 170  */
 171 void
 172 xbt_dynar_reset(xbt_dynar_t const dynar) {
 173
 174   __sanity_check_dynar(dynar);
 175
 176   DEBUG1("Reset the dynar %p",(void*)dynar);
 177   if (dynar->free_f) {
 178     xbt_dynar_map(dynar, dynar->free_f);
 179   }
 180 /*
 181   if (dynar->data)
 182     free(dynar->data);
 183
 184   dynar->size = 0;
 185   */
 186   dynar->used = 0;
 187 /*  dynar->data = NULL;*/
 188 }
 189
 190 /** @brief Destructor
 191  *
 192  * \param dynar poor victim
 193  *
 194  * kilkil a dynar and its content
 195  */
 196
 197 void
 198 xbt_dynar_free(xbt_dynar_t * dynar) {
 199   if (dynar && *dynar) {
 200     xbt_dynar_reset(*dynar);
 201     xbt_dynar_free_container(dynar);
 202   }
 203 }
 204
 205 /** @brief Count of dynar's elements
 206  *
 207  * \param dynar the dynar we want to mesure
 208  */
 209 unsigned long
 210 xbt_dynar_length(const xbt_dynar_t dynar) {
 211   return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
 212 }
 213
 214 /** @brief Retrieve a copy of the Nth element of a dynar.
 215  *
 216  * \param dynar information dealer
 217  * \param idx index of the slot we want to retrive
 218  * \param[out] dst where to put the result to.
 219  */
 220 void
 221 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
 222                    const int          idx,
 223                    void       * const dst) {
 224
 225   __sanity_check_dynar(dynar);
 226   __sanity_check_idx(idx);
 227   __check_inbound_idx(dynar, idx);
 228
 229   _xbt_dynar_get_elm(dst, dynar, idx);
 230 }
 231
 232 /** @brief Retrieve a pointer to the Nth element of a dynar.
 233  *
 234  * \param dynar information dealer
 235  * \param idx index of the slot we want to retrieve
 236  * \return the \a idx-th element of \a dynar.
 237  *
 238  * \warning The returned value is the actual content of the dynar.
 239  * Make a copy before fooling with it.
 240  */
 241 void*
 242 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
 243            const int          idx) {
 244
 245   __sanity_check_dynar(dynar);
 246   __sanity_check_idx(idx);
 247   __check_inbound_idx(dynar, idx);
 248
 249   return _xbt_dynar_elm(dynar, idx);
 250 }
 251
 252 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
 253  *
 254  * \param dynar information dealer
 255  * \param idx index of the slot we want to modify
 256  * \param src What will be feeded to the dynar
 257  *
 258  * If you want to free the previous content, use xbt_dynar_replace().
 259  */
 260 void
 261 xbt_dynar_set(xbt_dynar_t         dynar,
 262                const int            idx,
 263                const void   * const src) {
 264
 265   __sanity_check_dynar(dynar);
 266   __sanity_check_idx(idx);
 267
 268   _xbt_dynar_expand(dynar, idx+1);
 269
 270   if (idx >= dynar->used) {
 271     dynar->used = idx+1;
 272   }
 273
 274   _xbt_dynar_put_elm(dynar, idx, src);
 275 }
 276
 277 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
 278  *
 279  * \param dynar
 280  * \param idx
 281  * \param object
 282  *
 283  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 284  * free the previous value at this position. If you don't want to free the
 285  * previous content, use xbt_dynar_set().
 286  */
 287 void
 288 xbt_dynar_replace(xbt_dynar_t         dynar,
 289                    const int            idx,
 290                    const void   * const object) {
 291
 292   __sanity_check_dynar(dynar);
 293   __sanity_check_idx(idx);
 294
 295   if (idx < dynar->used && dynar->free_f) {
 296     void * const old_object = _xbt_dynar_elm(dynar, idx);
 297
 298     dynar->free_f(old_object);
 299   }
 300
 301   xbt_dynar_set(dynar, idx, object);
 302 }
 303
 304 /** @brief Make room for a new element, and return a pointer to it
 305  *
 306  * You can then use regular affectation to set its value instead of relying
 307  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
 308  */
 309 void *
 310 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
 311                         const int            idx) {
 312
 313   __sanity_check_dynar(dynar);
 314   __sanity_check_idx(idx);
 315   __check_sloppy_inbound_idx(dynar, idx);
 316
 317   {
 318     const unsigned long old_used = dynar->used;
 319     const unsigned long new_used = old_used + 1;
 320
 321     _xbt_dynar_expand(dynar, new_used);
 322
 323     {
 324       const unsigned long nb_shift =  old_used - idx;
 325
 326       if (nb_shift)
 327          memmove(_xbt_dynar_elm(dynar, idx+1),
 328                  _xbt_dynar_elm(dynar, idx),
 329                  nb_shift * dynar->elmsize);
 330     }
 331
 332     dynar->used = new_used;
 333     return _xbt_dynar_elm(dynar,idx);
 334   }
 335 }
 336
 337 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
 338  *
 339  * Set the Nth element of a dynar, expanding the dynar if needed, and
 340  * moving the previously existing value and all subsequent ones to one
 341  * position right in the dynar.
 342  */
 343 void
 344 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
 345                     const int            idx,
 346                     const void   * const src) {
 347
 348   /* checks done in xbt_dynar_insert_at_ptr */
 349   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
 350          src,
 351          dynar->elmsize);
 352 }
 353
 354 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 355  *
 356  * Get the Nth element of a dynar, removing it from the dynar and moving
 357  * all subsequent values to one position left in the dynar.
 358  */
 359 void
 360 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
 361                      const int            idx,
 362                      void         * const object) {
 363
 364   unsigned long nb_shift;
 365   unsigned long offset;
 366
 367   __sanity_check_dynar(dynar);
 368   __sanity_check_idx(idx);
 369   __check_inbound_idx(dynar, idx);
 370
 371   if (object) {
 372     _xbt_dynar_get_elm(object, dynar, idx);
 373   } else if (dynar->free_f) {
 374     char elm[SIZEOF_MAX];
 375     _xbt_dynar_get_elm(elm, dynar, idx);
 376     (*dynar->free_f)(elm);
 377   }
 378
 379   nb_shift =  dynar->used-1 - idx;
 380   offset   =  nb_shift * dynar->elmsize;
 381
 382   memmove(_xbt_dynar_elm(dynar, idx),
 383           _xbt_dynar_elm(dynar, idx+1),
 384           offset);
 385
 386   dynar->used--;
 387 }
 388
 389 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 390  *
 391  * You can then use regular affectation to set its value instead of relying
 392  * on the slow memcpy. This is what xbt_dynar_push_as() does.
 393  */
 394 void *
 395 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
 396   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 397 }
 398
 399 /** @brief Add an element at the end of the dynar */
 400 void
 401 xbt_dynar_push(xbt_dynar_t  const dynar,
 402                 const void   * const src) {
 403   /* sanity checks done by insert_at */
 404   xbt_dynar_insert_at(dynar, dynar->used, src);
 405 }
 406
 407 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 408  *
 409  * You can then use regular affectation to set its value instead of relying
 410  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
 411  */
 412 void *
 413 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 414
 415   __check_populated_dynar(dynar);
 416   DEBUG1("Pop %p",(void*)dynar);
 417   dynar->used--;
 418   return _xbt_dynar_elm(dynar,dynar->used);
 419 }
 420
 421 /** @brief Get and remove the last element of the dynar */
 422 void
 423 xbt_dynar_pop(xbt_dynar_t  const dynar,
 424               void         * const dst) {
 425
 426   /* sanity checks done by remove_at */
 427   DEBUG1("Pop %p",(void*)dynar);
 428   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 429 }
 430
 431 /** @brief Add an element at the begining of the dynar.
 432  *
 433  * This is less efficient than xbt_dynar_push()
 434  */
 435 void
 436 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 437                    const void   * const src) {
 438
 439   /* sanity checks done by insert_at */
 440   xbt_dynar_insert_at(dynar, 0, src);
 441 }
 442
 443 /** @brief Get and remove the first element of the dynar.
 444  *
 445  * This is less efficient than xbt_dynar_pop()
 446  */
 447 void
 448 xbt_dynar_shift(xbt_dynar_t  const dynar,
 449                  void         * const dst) {
 450
 451   /* sanity checks done by remove_at */
 452   xbt_dynar_remove_at(dynar, 0, dst);
 453 }
 454
 455 /** @brief Apply a function to each member of a dynar
 456  *
 457  * The mapped function may change the value of the element itself,
 458  * but should not mess with the structure of the dynar.
 459  */
 460 void
 461 xbt_dynar_map(const xbt_dynar_t  dynar,
 462                void_f_pvoid_t     * const op) {
 463
 464   __sanity_check_dynar(dynar);
 465
 466   {
 467     char         elm[SIZEOF_MAX];
 468     const unsigned long used = dynar->used;
 469     unsigned long       i    = 0;
 470
 471     for (i = 0; i < used; i++) {
 472       _xbt_dynar_get_elm(elm, dynar, i);
 473       op(elm);
 474     }
 475   }
 476 }
 477
 478 /** @brief Put the cursor at the begining of the dynar.
 479  *
 480  * Actually, the cursor is set one step before the begining, so that you
 481  * can iterate over the dynar with a for loop.
 482  */
 483 void
 484 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 485                        int        * const cursor) {
 486
 487   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 488   *cursor = 0;
 489 }
 490
 491 /** @brief Move the cursor to the next value */
 492 void
 493 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 494                        int        * const cursor) {
 495
 496   (*cursor)++;
 497 }
 498
 499 /** @brief Get the data currently pointed by the cursor */
 500 int
 501 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 502                       int                * const cursor,
 503                       void               * const dst) {
 504
 505   __sanity_check_dynar(dynar);
 506   {
 507
 508     const int idx = *cursor;
 509
 510     if (idx >= dynar->used) {
 511       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 512       return FALSE;
 513     }
 514     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 515
 516     _xbt_dynar_get_elm(dst, dynar, idx);
 517   }
 518   return TRUE;
 519
 520 }
 521
 522 /** @brief Removes and free the entry pointed by the cursor
 523  *
 524  * This function can be used while traversing without problem.
 525  */
 526 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 527                           int          * const cursor) {
 528   void *dst;
 529
 530   if (dynar->elmsize > sizeof(void*)) {
 531     DEBUG0("Elements too big to fit into a pointer");
 532     if (dynar->free_f) {
 533       dst=xbt_malloc(dynar->elmsize);
 534       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 535       (dynar->free_f)(dst);
 536       free(dst);
 537     } else {
 538       DEBUG0("Ok, we dont care about the element without free function");
 539       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 540     }
 541
 542   } else {
 543     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 544     if (dynar->free_f)
 545       (dynar->free_f)(dst);
 546   }
 547 }
 548
 549 #ifdef SIMGRID_TEST
 550
 551 #define NB_ELEM 5000
 552
 553 XBT_TEST_SUITE("dynar","Dynar data container");
 554 XBT_LOG_EXTERNAL_CATEGORY(dynar);
 555 XBT_LOG_DEFAULT_CATEGORY(dynar);
 556
 557 XBT_TEST_UNIT("int",test_dynar_int,"Dyars of integers") {
 558    /* Vars_decl [doxygen cruft] */
 559    xbt_dynar_t d;
 560    int i,cpt,cursor;
 561    int *iptr;
 562
 563    xbt_test_add0("==== Traverse the empty dynar");
 564    d=xbt_dynar_new(sizeof(int),NULL);
 565    xbt_dynar_foreach(d,cursor,i){
 566      xbt_assert0(0,"Damnit, there is something in the empty dynar");
 567    }
 568    xbt_dynar_free(&d);
 569    xbt_dynar_free(&d);
 570
 571    xbt_test_add1("==== Push %d int, set them again 3 times, traverse them, shift them",
 572         NB_ELEM);
 573    /* Populate_ints [doxygen cruft] */
 574    /* 1. Populate the dynar */
 575    d=xbt_dynar_new(sizeof(int),NULL);
 576    for (cpt=0; cpt< NB_ELEM; cpt++) {
 577      xbt_dynar_push_as(d,int,cpt); /* This is faster (and possible only with scalars) */
 578      /* xbt_dynar_push(d,&cpt);       This would also work */
 579      xbt_test_log2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 580    }
 581
 582    /* 2. Traverse manually the dynar */
 583    for (cursor=0; cursor< NB_ELEM; cursor++) {
 584      iptr=xbt_dynar_get_ptr(d,cursor);
 585      xbt_test_assert2(cursor == *iptr,
 586                       "The retrieved value is not the same than the injected one (%d!=%d)",
 587                       cursor,cpt);
 588    }
 589
 590    /* 3. Traverse the dynar using the neat macro to that extend */
 591    xbt_dynar_foreach(d,cursor,cpt){
 592      xbt_test_assert2(cursor == cpt,
 593                       "The retrieved value is not the same than the injected one (%d!=%d)",
 594                       cursor,cpt);
 595    }
 596    /* end_of_traversal */
 597
 598    for (cpt=0; cpt< NB_ELEM; cpt++)
 599      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 600
 601    for (cpt=0; cpt< NB_ELEM; cpt++)
 602      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 603 /*     xbt_dynar_set(d,cpt,&cpt);*/
 604
 605    for (cpt=0; cpt< NB_ELEM; cpt++)
 606      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 607
 608    cpt=0;
 609    xbt_dynar_foreach(d,cursor,i){
 610      xbt_test_assert2(i == cpt,
 611                       "The retrieved value is not the same than the injected one (%d!=%d)",
 612                       i,cpt);
 613      cpt++;
 614    }
 615    xbt_test_assert2(cpt == NB_ELEM,
 616                     "Cannot retrieve my %d values. Last got one is %d",
 617                     NB_ELEM, cpt);
 618
 619    /* shifting [doxygen cruft] */
 620    /* 4. Shift all the values */
 621    for (cpt=0; cpt< NB_ELEM; cpt++) {
 622      xbt_dynar_shift(d,&i);
 623      xbt_test_assert2(i == cpt,
 624                       "The retrieved value is not the same than the injected one (%d!=%d)",
 625                       i,cpt);
 626      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 627    }
 628
 629    /* 5. Free the resources */
 630    xbt_dynar_free(&d);
 631    xbt_dynar_free(&d);
 632
 633
 634    xbt_test_add1("==== Unshift/pop %d int",NB_ELEM);
 635    d=xbt_dynar_new(sizeof(int),NULL);
 636    for (cpt=0; cpt< NB_ELEM; cpt++) {
 637      xbt_dynar_unshift(d,&cpt);
 638      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 639    }
 640    for (cpt=0; cpt< NB_ELEM; cpt++) {
 641      i=xbt_dynar_pop_as(d,int);
 642      xbt_test_assert2(i == cpt,
 643                       "The retrieved value is not the same than the injected one (%d!=%d)",
 644                       i,cpt);
 645      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 646    }
 647    xbt_dynar_free(&d);
 648    xbt_dynar_free(&d);
 649
 650
 651    xbt_test_add1("==== Push %d int, insert 1000 int in the middle, shift everything",NB_ELEM);
 652    d=xbt_dynar_new(sizeof(int),NULL);
 653    for (cpt=0; cpt< NB_ELEM; cpt++) {
 654      xbt_dynar_push_as(d,int,cpt);
 655      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 656    }
 657    for (cpt=0; cpt< 1000; cpt++) {
 658      xbt_dynar_insert_at_as(d,2500,int,cpt);
 659      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 660    }
 661
 662    for (cpt=0; cpt< 2500; cpt++) {
 663      xbt_dynar_shift(d,&i);
 664      xbt_test_assert2(i == cpt,
 665              "The retrieved value is not the same than the injected one at the begining (%d!=%d)",
 666                i,cpt);
 667      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 668    }
 669    for (cpt=999; cpt>=0; cpt--) {
 670      xbt_dynar_shift(d,&i);
 671      xbt_test_assert2(i == cpt,
 672            "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
 673                       i,cpt);
 674    }
 675    for (cpt=2500; cpt< NB_ELEM; cpt++) {
 676      xbt_dynar_shift(d,&i);
 677       xbt_test_assert2(i == cpt,
 678            "The retrieved value is not the same than the injected one at the end (%d!=%d)",
 679                        i,cpt);
 680    }
 681    xbt_dynar_free(&d);
 682    xbt_dynar_free(&d);
 683
 684
 685    xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest",NB_ELEM);
 686    d=xbt_dynar_new(sizeof(int),NULL);
 687    for (cpt=0; cpt< NB_ELEM; cpt++)
 688      xbt_dynar_push_as(d,int,cpt);
 689
 690    for (cpt=2000; cpt< 4000; cpt++) {
 691      xbt_dynar_remove_at(d,2000,&i);
 692      xbt_test_assert2(i == cpt,
 693                       "Remove a bad value. Got %d, expected %d",
 694                       i,cpt);
 695      DEBUG2("remove %d, length=%lu",cpt, xbt_dynar_length(d));
 696    }
 697    xbt_dynar_free(&d);
 698    xbt_dynar_free(&d);
 699 }
 700
 701 XBT_TEST_UNIT("double",test_dynar_double,"Dyars of doubles") {
 702    xbt_dynar_t d;
 703    int cpt,cursor;
 704    double d1,d2;
 705
 706    xbt_test_add0("==== Traverse the empty dynar");
 707    d=xbt_dynar_new(sizeof(int),NULL);
 708    xbt_dynar_foreach(d,cursor,cpt){
 709      xbt_test_assert0(FALSE,
 710              "Damnit, there is something in the empty dynar");
 711    }
 712    xbt_dynar_free(&d);
 713    xbt_dynar_free(&d);
 714
 715    xbt_test_add0("==== Push/shift 5000 doubles");
 716    d=xbt_dynar_new(sizeof(double),NULL);
 717    for (cpt=0; cpt< 5000; cpt++) {
 718      d1=(double)cpt;
 719      xbt_dynar_push(d,&d1);
 720    }
 721    xbt_dynar_foreach(d,cursor,d2){
 722      d1=(double)cursor;
 723      xbt_test_assert2(d1 == d2,
 724            "The retrieved value is not the same than the injected one (%f!=%f)",
 725                   d1,d2);
 726    }
 727    for (cpt=0; cpt< 5000; cpt++) {
 728      d1=(double)cpt;
 729      xbt_dynar_shift(d,&d2);
 730      xbt_test_assert2(d1 == d2,
 731            "The retrieved value is not the same than the injected one (%f!=%f)",
 732                   d1,d2);
 733    }
 734    xbt_dynar_free(&d);
 735    xbt_dynar_free(&d);
 736
 737
 738    xbt_test_add0("==== Unshift/pop 5000 doubles");
 739    d=xbt_dynar_new(sizeof(double),NULL);
 740    for (cpt=0; cpt< 5000; cpt++) {
 741      d1=(double)cpt;
 742      xbt_dynar_unshift(d,&d1);
 743    }
 744    for (cpt=0; cpt< 5000; cpt++) {
 745      d1=(double)cpt;
 746      xbt_dynar_pop(d,&d2);
 747      xbt_test_assert2 (d1 == d2,
 748            "The retrieved value is not the same than the injected one (%f!=%f)",
 749                    d1,d2);
 750    }
 751    xbt_dynar_free(&d);
 752    xbt_dynar_free(&d);
 753
 754
 755
 756    xbt_test_add0("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
 757    d=xbt_dynar_new(sizeof(double),NULL);
 758    for (cpt=0; cpt< 5000; cpt++) {
 759      d1=(double)cpt;
 760      xbt_dynar_push(d,&d1);
 761    }
 762    for (cpt=0; cpt< 1000; cpt++) {
 763      d1=(double)cpt;
 764      xbt_dynar_insert_at(d,2500,&d1);
 765    }
 766
 767    for (cpt=0; cpt< 2500; cpt++) {
 768      d1=(double)cpt;
 769      xbt_dynar_shift(d,&d2);
 770      xbt_test_assert2(d1 == d2,
 771            "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
 772                   d1,d2);
 773      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 774    }
 775    for (cpt=999; cpt>=0; cpt--) {
 776      d1=(double)cpt;
 777      xbt_dynar_shift(d,&d2);
 778      xbt_test_assert2 (d1 == d2,
 779            "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
 780                    d1,d2);
 781    }
 782    for (cpt=2500; cpt< 5000; cpt++) {
 783      d1=(double)cpt;
 784      xbt_dynar_shift(d,&d2);
 785      xbt_test_assert2 (d1 == d2,
 786            "The retrieved value is not the same than the injected one at the end (%f!=%f)",
 787                    d1,d2);
 788    }
 789    xbt_dynar_free(&d);
 790    xbt_dynar_free(&d);
 791
 792
 793    xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest");
 794    d=xbt_dynar_new(sizeof(double),NULL);
 795    for (cpt=0; cpt< 5000; cpt++) {
 796      d1=(double)cpt;
 797      xbt_dynar_push(d,&d1);
 798    }
 799    for (cpt=2000; cpt< 4000; cpt++) {
 800      d1=(double)cpt;
 801      xbt_dynar_remove_at(d,2000,&d2);
 802      xbt_test_assert2 (d1 == d2,
 803            "Remove a bad value. Got %f, expected %f",
 804                d2,d1);
 805    }
 806    xbt_dynar_free(&d);
 807    xbt_dynar_free(&d);
 808 }
 809
 810
 811 /* doxygen_first_cruft*/
 812
 813 /* The function we will use to free the data */
 814 static void free_string(void *d){
 815   free(*(void**)d);
 816 }
 817
 818 XBT_TEST_UNIT("string",test_dynar_string,"Dyars of strings") {
 819    xbt_dynar_t d;
 820    int cpt;
 821    char buf[1024];
 822    char *s1,*s2;
 823
 824    xbt_test_add0("==== Traverse the empty dynar");
 825    d=xbt_dynar_new(sizeof(char *),&free_string);
 826    xbt_dynar_foreach(d,cpt,s1){
 827      xbt_test_assert0(FALSE,
 828                   "Damnit, there is something in the empty dynar");
 829    }
 830    xbt_dynar_free(&d);
 831    xbt_dynar_free(&d);
 832
 833    xbt_test_add1("==== Push %d strings, set them again 3 times, shift them",NB_ELEM);
 834    d=xbt_dynar_new(sizeof(char*),&free_string);
 835    /* Populate_str [doxygen cruft] */
 836    /* 1. Populate the dynar */
 837    for (cpt=0; cpt< NB_ELEM; cpt++) {
 838      sprintf(buf,"%d",cpt);
 839      s1=strdup(buf);
 840      xbt_dynar_push(d,&s1);
 841    }
 842    for (cpt=0; cpt< NB_ELEM; cpt++) {
 843      sprintf(buf,"%d",cpt);
 844      s1=strdup(buf);
 845      xbt_dynar_replace(d,cpt,&s1);
 846    }
 847    for (cpt=0; cpt< NB_ELEM; cpt++) {
 848      sprintf(buf,"%d",cpt);
 849      s1=strdup(buf);
 850      xbt_dynar_replace(d,cpt,&s1);
 851    }
 852    for (cpt=0; cpt< NB_ELEM; cpt++) {
 853      sprintf(buf,"%d",cpt);
 854      s1=strdup(buf);
 855      xbt_dynar_replace(d,cpt,&s1);
 856    }
 857    for (cpt=0; cpt< NB_ELEM; cpt++) {
 858      sprintf(buf,"%d",cpt);
 859      xbt_dynar_shift(d,&s2);
 860      xbt_test_assert2 (!strcmp(buf,s2),
 861             "The retrieved value is not the same than the injected one (%s!=%s)",
 862                    buf,s2);
 863      free(s2);
 864    }
 865    xbt_dynar_free(&d);
 866    xbt_dynar_free(&d);
 867
 868
 869    xbt_test_add1("==== Unshift, traverse and pop %d strings",NB_ELEM);
 870    d=xbt_dynar_new(sizeof(char**),&free_string);
 871    for (cpt=0; cpt< NB_ELEM; cpt++) {
 872      sprintf(buf,"%d",cpt);
 873      s1=strdup(buf);
 874      xbt_dynar_unshift(d,&s1);
 875    }
 876    /* 2. Traverse the dynar with the macro */
 877    xbt_dynar_foreach(d,cpt,s1) {
 878      sprintf(buf,"%d",NB_ELEM - cpt -1);
 879      xbt_test_assert2 (!strcmp(buf,s1),
 880            "The retrieved value is not the same than the injected one (%s!=%s)",
 881                buf,s1);
 882    }
 883    /* 3. Traverse the dynar with the macro */
 884    for (cpt=0; cpt< NB_ELEM; cpt++) {
 885      sprintf(buf,"%d",cpt);
 886      xbt_dynar_pop(d,&s2);
 887      xbt_test_assert2 (!strcmp(buf,s2),
 888            "The retrieved value is not the same than the injected one (%s!=%s)",
 889                buf,s2);
 890      free(s2);
 891    }
 892    /* 4. Free the resources */
 893    xbt_dynar_free(&d);
 894    xbt_dynar_free(&d);
 895
 896
 897    xbt_test_add2("==== Push %d strings, insert %d strings in the middle, shift everything",NB_ELEM,NB_ELEM/5);
 898    d=xbt_dynar_new(sizeof(char*),&free_string);
 899    for (cpt=0; cpt< NB_ELEM; cpt++) {
 900      sprintf(buf,"%d",cpt);
 901      s1=strdup(buf);
 902      xbt_dynar_push(d,&s1);
 903    }
 904    for (cpt=0; cpt< NB_ELEM/5; cpt++) {
 905      sprintf(buf,"%d",cpt);
 906      s1=strdup(buf);
 907      xbt_dynar_insert_at(d,NB_ELEM/2,&s1);
 908    }
 909
 910    for (cpt=0; cpt< NB_ELEM/2; cpt++) {
 911      sprintf(buf,"%d",cpt);
 912      xbt_dynar_shift(d,&s2);
 913      xbt_test_assert2(!strcmp(buf,s2),
 914            "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
 915                buf,s2);
 916       free(s2);
 917    }
 918    for (cpt=(NB_ELEM/5)-1; cpt>=0; cpt--) {
 919      sprintf(buf,"%d",cpt);
 920      xbt_dynar_shift(d,&s2);
 921      xbt_test_assert2 (!strcmp(buf,s2),
 922            "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
 923                buf,s2);
 924      free(s2);
 925    }
 926    for (cpt=NB_ELEM/2; cpt< NB_ELEM; cpt++) {
 927      sprintf(buf,"%d",cpt);
 928      xbt_dynar_shift(d,&s2);
 929      xbt_test_assert2 (!strcmp(buf,s2),
 930            "The retrieved value is not the same than the injected one at the end (%s!=%s)",
 931                buf,s2);
 932      free(s2);
 933    }
 934    xbt_dynar_free(&d);
 935    xbt_dynar_free(&d);
 936
 937
 938    xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest",NB_ELEM,2*(NB_ELEM/5),4*(NB_ELEM/5));
 939    d=xbt_dynar_new(sizeof(char*),&free_string);
 940    for (cpt=0; cpt< NB_ELEM; cpt++) {
 941      sprintf(buf,"%d",cpt);
 942      s1=strdup(buf);
 943      xbt_dynar_push(d,&s1);
 944    }
 945    for (cpt=2*(NB_ELEM/5); cpt< 4*(NB_ELEM/5); cpt++) {
 946      sprintf(buf,"%d",cpt);
 947      xbt_dynar_remove_at(d,2*(NB_ELEM/5),&s2);
 948      xbt_test_assert2(!strcmp(buf,s2),
 949                   "Remove a bad value. Got %s, expected %s",
 950                   s2,buf);
 951       free(s2);
 952    }
 953    xbt_dynar_free(&d);
 954    xbt_dynar_free(&d);
 955 }
 956 #endif /* SIMGRID_TEST */