src/xbt/dynar.c

   1 /* a generic DYNamic ARray implementation.                                  */
   2
   3 /* Copyright (c) 2004-2015. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/misc.h"
  10 #include "xbt/sysdep.h"
  11 #include "xbt/log.h"
  12 #include "xbt/ex.h"
  13 #include "xbt/dynar.h"
  14 #include <sys/types.h>
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dyn, xbt, "Dynamic arrays");
  17
  18 static inline void _sanity_check_dynar(xbt_dynar_t dynar)
  19 {
  20   xbt_assert(dynar, "dynar is NULL");
  21 }
  22
  23 static inline void _sanity_check_idx(int idx)
  24 {
  25   xbt_assert(idx >= 0, "dynar idx(=%d) < 0", (int) (idx));
  26 }
  27
  28 static inline void _check_inbound_idx(xbt_dynar_t dynar, int idx)
  29 {
  30   if (idx < 0 || idx >= (int)dynar->used) {
  31     THROWF(bound_error, idx, "dynar is not that long. You asked %d, but it's only %lu long",
  32            (int) (idx), (unsigned long) dynar->used);
  33   }
  34 }
  35
  36 static inline void _check_populated_dynar(xbt_dynar_t dynar)
  37 {
  38   if (dynar->used == 0) {
  39     THROWF(bound_error, 0, "dynar %p is empty", dynar);
  40   }
  41 }
  42
  43 static inline void _xbt_dynar_resize(xbt_dynar_t dynar, unsigned long new_size)
  44 {
  45   if (new_size != dynar->size) {
  46     dynar->size = new_size;
  47     dynar->data = xbt_realloc(dynar->data, new_size * dynar->elmsize);
  48   }
  49 }
  50
  51 static inline void _xbt_dynar_expand(xbt_dynar_t const dynar, const unsigned long nb)
  52 {
  53   const unsigned long old_size = dynar->size;
  54
  55   if (nb > old_size) {
  56     const unsigned long expand = 2 * (old_size + 1);
  57     _xbt_dynar_resize(dynar, (nb > expand ? nb : expand));
  58     XBT_DEBUG("expand %p from %lu to %lu elements", dynar, old_size, dynar->size);
  59   }
  60 }
  61
  62 static inline void *_xbt_dynar_elm(const xbt_dynar_t dynar, const unsigned long idx)
  63 {
  64   char *const data = (char *) dynar->data;
  65   const unsigned long elmsize = dynar->elmsize;
  66
  67   return data + idx * elmsize;
  68 }
  69
  70 static inline void _xbt_dynar_get_elm(void *const dst, const xbt_dynar_t dynar, const unsigned long idx)
  71 {
  72   void *const elm = _xbt_dynar_elm(dynar, idx);
  73
  74   memcpy(dst, elm, dynar->elmsize);
  75 }
  76
  77 void xbt_dynar_dump(xbt_dynar_t dynar)
  78 {
  79   XBT_INFO("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
  80         dynar->size, dynar->used, dynar->elmsize, dynar->data, dynar->free_f);
  81 }
  82
  83 /** @brief Constructor
  84  *
  85  * \param elmsize size of each element in the dynar
  86  * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
  87  *
  88  * Creates a new dynar. If a free_func is provided, the elements have to be pointer of pointer. That is to say that
  89  * dynars can contain either base types (int, char, double, etc) or pointer of pointers (struct **).
  90  */
  91 xbt_dynar_t xbt_dynar_new(const unsigned long elmsize, void_f_pvoid_t const free_f)
  92 {
  93   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t, 1);
  94
  95   dynar->size = 0;
  96   dynar->used = 0;
  97   dynar->elmsize = elmsize;
  98   dynar->data = NULL;
  99   dynar->free_f = free_f;
 100
 101   return dynar;
 102 }
 103
 104 /** @brief Destructor of the structure not touching to the content
 105  *
 106  * \param dynar poor victim
 107  *
 108  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content is not touched (the \a free_f function
 109  * is not used)
 110  */
 111 void xbt_dynar_free_container(xbt_dynar_t * dynar)
 112 {
 113   if (dynar && *dynar) {
 114     xbt_dynar_t d = *dynar;
 115     free(d->data);
 116     free(d);
 117     *dynar = NULL;
 118   }
 119 }
 120
 121 /** @brief Frees the content and set the size to 0
 122  *
 123  * \param dynar who to squeeze
 124  */
 125 inline void xbt_dynar_reset(xbt_dynar_t const dynar)
 126 {
 127   _sanity_check_dynar(dynar);
 128
 129   XBT_CDEBUG(xbt_dyn, "Reset the dynar %p", (void *) dynar);
 130   if (dynar->free_f) {
 131     xbt_dynar_map(dynar, dynar->free_f);
 132   }
 133   dynar->used = 0;
 134 }
 135
 136 /** @brief Merge dynar d2 into d1
 137  *
 138  * \param d1 dynar to keep
 139  * \param d2 dynar to merge into d1. This dynar is free at end.
 140  */
 141 void xbt_dynar_merge(xbt_dynar_t *d1, xbt_dynar_t *d2)
 142 {
 143   if((*d1)->elmsize != (*d2)->elmsize)
 144     xbt_die("Element size must are not equal");
 145
 146   const unsigned long elmsize = (*d1)->elmsize;
 147
 148   void *ptr = _xbt_dynar_elm((*d2), 0);
 149   _xbt_dynar_resize(*d1, (*d1)->size + (*d2)->size);
 150   void *elm = _xbt_dynar_elm((*d1), (*d1)->used);
 151
 152   memcpy(elm, ptr, ((*d2)->size)*elmsize);
 153   (*d1)->used += (*d2)->used;
 154   (*d2)->used = 0;
 155   xbt_dynar_free(d2);
 156 }
 157
 158 /**
 159  * \brief Shrink the dynar by removing empty slots at the end of the internal array
 160  * \param dynar a dynar
 161  * \param empty_slots_wanted number of empty slots you want to keep at the end of the internal array for further
 162  * insertions
 163  *
 164  * Reduces the internal array size of the dynar to the number of elements plus \a empty_slots_wanted.
 165  * After removing elements from the dynar, you can call this function to make the dynar use less memory.
 166  * Set \a empty_slots_wanted to zero to reduce the dynar internal array as much as possible.
 167  * Note that if \a empty_slots_wanted is greater than the array size, the internal array is expanded instead of shrunk.
 168  */
 169 void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted)
 170 {
 171   _xbt_dynar_resize(dynar, dynar->used + empty_slots_wanted);
 172 }
 173
 174 /** @brief Destructor
 175  *
 176  * \param dynar poor victim
 177  *
 178  * kilkil a dynar and its content
 179  */
 180 inline void xbt_dynar_free(xbt_dynar_t * dynar)
 181 {
 182   if (dynar && *dynar) {
 183     xbt_dynar_reset(*dynar);
 184     xbt_dynar_free_container(dynar);
 185   }
 186 }
 187
 188 /** \brief free a dynar passed as void* (handy to store dynar in dynars or dict) */
 189 void xbt_dynar_free_voidp(void *d)
 190 {
 191   xbt_dynar_t dynar = (xbt_dynar_t)d;
 192   xbt_dynar_free(&dynar);
 193 }
 194
 195 /** @brief Count of dynar's elements
 196  *
 197  * \param dynar the dynar we want to mesure
 198  */
 199 inline unsigned long xbt_dynar_length(const xbt_dynar_t dynar)
 200 {
 201   return (dynar ? (unsigned long) dynar->used : (unsigned long) 0);
 202 }
 203
 204  /**@brief check if a dynar is empty
 205  *
 206  *\param dynar the dynat we want to check
 207  */
 208
 209 inline int xbt_dynar_is_empty(const xbt_dynar_t dynar)
 210 {
 211   return (xbt_dynar_length(dynar) == 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 retrieve
 218  * \param[out] dst where to put the result to.
 219  */
 220 inline void xbt_dynar_get_cpy(const xbt_dynar_t dynar, const unsigned long idx, void *const dst)
 221 {
 222   _sanity_check_dynar(dynar);
 223   _check_inbound_idx(dynar, idx);
 224
 225   _xbt_dynar_get_elm(dst, dynar, idx);
 226 }
 227
 228 /** @brief Retrieve a pointer to the Nth element of a dynar.
 229  *
 230  * \param dynar information dealer
 231  * \param idx index of the slot we want to retrieve
 232  * \return the \a idx-th element of \a dynar.
 233  *
 234  * \warning The returned value is the actual content of the dynar.
 235  * Make a copy before fooling with it.
 236  */
 237 inline void *xbt_dynar_get_ptr(const xbt_dynar_t dynar, const unsigned long idx)
 238 {
 239   void *res;
 240   _sanity_check_dynar(dynar);
 241   _check_inbound_idx(dynar, idx);
 242
 243   res = _xbt_dynar_elm(dynar, idx);
 244   return res;
 245 }
 246
 247 inline void *xbt_dynar_set_at_ptr(const xbt_dynar_t dynar, const unsigned long idx)
 248 {
 249   _sanity_check_dynar(dynar);
 250
 251   if (idx >= dynar->used) {
 252     _xbt_dynar_expand(dynar, idx + 1);
 253     if (idx > dynar->used) {
 254       memset(_xbt_dynar_elm(dynar, dynar->used), 0, (idx - dynar->used) * dynar->elmsize);
 255     }
 256     dynar->used = idx + 1;
 257   }
 258   return _xbt_dynar_elm(dynar, idx);
 259 }
 260
 261 /** @brief Set the Nth element of a dynar (expanded if needed). Previous value at this position is NOT freed
 262  *
 263  * \param dynar information dealer
 264  * \param idx index of the slot we want to modify
 265  * \param src What will be feeded to the dynar
 266  *
 267  * If you want to free the previous content, use xbt_dynar_replace().
 268  */
 269 inline void xbt_dynar_set(xbt_dynar_t dynar, const int idx, const void *const src)
 270 {
 271   memcpy(xbt_dynar_set_at_ptr(dynar, idx), src, dynar->elmsize);
 272 }
 273
 274 /** @brief Set the Nth element of a dynar (expanded if needed). Previous value is freed
 275  *
 276  * \param dynar
 277  * \param idx
 278  * \param object
 279  *
 280  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO free the previous value at this position. If
 281  * you don't want to free the previous content, use xbt_dynar_set().
 282  */
 283 void xbt_dynar_replace(xbt_dynar_t dynar, const unsigned long idx, const void *const object)
 284 {
 285   _sanity_check_dynar(dynar);
 286
 287   if (idx < dynar->used && dynar->free_f) {
 288     void *const old_object = _xbt_dynar_elm(dynar, idx);
 289
 290     dynar->free_f(old_object);
 291   }
 292
 293   xbt_dynar_set(dynar, idx, object);
 294 }
 295
 296 /** @brief Make room for a new element, and return a pointer to it
 297  *
 298  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 299  * xbt_dynar_insert_at_as() does.
 300  */
 301 void *xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar, const int idx)
 302 {
 303   void *res;
 304   unsigned long old_used;
 305   unsigned long new_used;
 306   long nb_shift;
 307
 308   _sanity_check_dynar(dynar);
 309   _sanity_check_idx(idx);
 310
 311   old_used = dynar->used;
 312   new_used = old_used + 1;
 313
 314   _xbt_dynar_expand(dynar, new_used);
 315
 316   nb_shift = old_used - idx;
 317
 318   if (nb_shift>0) {
 319     memmove(_xbt_dynar_elm(dynar, idx + 1), _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
 320   }
 321
 322   dynar->used = new_used;
 323   res = _xbt_dynar_elm(dynar, idx);
 324   return res;
 325 }
 326
 327 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
 328  *
 329  * Set the Nth element of a dynar, expanding the dynar if needed, and moving the previously existing value and all
 330  * subsequent ones to one position right in the dynar.
 331  */
 332 inline void xbt_dynar_insert_at(xbt_dynar_t const dynar, const int idx, const void *const src)
 333 {
 334   /* checks done in xbt_dynar_insert_at_ptr */
 335   memcpy(xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
 336 }
 337
 338 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 339  *
 340  * Get the Nth element of a dynar, removing it from the dynar and moving all subsequent values to one position left in
 341  * the dynar.
 342  *
 343  * If the object argument of this function is a non-null pointer, the removed element is copied to this address. If not,
 344  * the element is freed using the free_f function passed at dynar creation.
 345  */
 346 void xbt_dynar_remove_at(xbt_dynar_t const dynar, const int idx, void *const object)
 347 {
 348   unsigned long nb_shift;
 349   unsigned long offset;
 350
 351   _sanity_check_dynar(dynar);
 352   _check_inbound_idx(dynar, idx);
 353
 354   if (object) {
 355     _xbt_dynar_get_elm(object, dynar, idx);
 356   } else if (dynar->free_f) {
 357     dynar->free_f(_xbt_dynar_elm(dynar, idx));
 358   }
 359
 360   nb_shift = dynar->used - 1 - idx;
 361
 362   if (nb_shift) {
 363     offset = nb_shift * dynar->elmsize;
 364     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset);
 365   }
 366
 367   dynar->used--;
 368 }
 369
 370 /** @brief Remove a slice of the dynar, sliding the rest of the values to the left
 371  *
 372  * This function removes an n-sized slice that starts at element idx. It is equivalent to xbt_dynar_remove_at with a
 373  * NULL object argument if n equals to 1.
 374  *
 375  * Each of the removed elements is freed using the free_f function passed at dynar creation.
 376  */
 377 void xbt_dynar_remove_n_at(xbt_dynar_t const dynar, const unsigned int n, const int idx)
 378 {
 379   unsigned long nb_shift;
 380   unsigned long offset;
 381   unsigned long cur;
 382
 383   if (!n) return;
 384
 385   _sanity_check_dynar(dynar);
 386   _check_inbound_idx(dynar, idx);
 387   _check_inbound_idx(dynar, idx + n - 1);
 388
 389   if (dynar->free_f) {
 390     for (cur = idx; cur < idx + n; cur++) {
 391       dynar->free_f(_xbt_dynar_elm(dynar, cur));
 392     }
 393   }
 394
 395   nb_shift = dynar->used - n - idx;
 396
 397   if (nb_shift) {
 398     offset = nb_shift * dynar->elmsize;
 399     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + n), offset);
 400   }
 401
 402   dynar->used -= n;
 403 }
 404
 405 /** @brief Returns the position of the element in the dynar
 406  *
 407  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function compares the
 408  * pointer value, not what's pointed. The only solution to search for a pointed value is then to write the foreach loop
 409  * yourself:
 410  * \code
 411  * signed int position = -1;
 412  * xbt_dynar_foreach(dynar, iter, elem) {
 413  *    if (!memcmp(elem, searched_element, sizeof(*elem))) {
 414  *        position = iter;
 415  *        break;
 416  *    }
 417  * }
 418  * \endcode
 419  *
 420  * Raises not_found_error if not found. If you have less than 2 millions elements, you probably want to use
 421  * #xbt_dynar_search_or_negative() instead, so that you don't have to TRY/CATCH on element not found.
 422  */
 423 unsigned int xbt_dynar_search(xbt_dynar_t const dynar, void *const elem)
 424 {
 425   unsigned long it;
 426
 427   for (it = 0; it < dynar->used; it++)
 428     if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 429       return it;
 430     }
 431
 432   THROWF(not_found_error, 0, "Element %p not part of dynar %p", elem, dynar);
 433   return -1; // Won't happen, just to please eclipse
 434 }
 435
 436 /** @brief Returns the position of the element in the dynar (or -1 if not found)
 437  *
 438  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 439  * what you want. Check the documentation of xbt_dynar_search() for more info.
 440  *
 441  * Note that usually, the dynar indices are unsigned integers. If you have more than 2 million elements in your dynar,
 442  * this very function will not work (but the other will).
 443  */
 444 signed int xbt_dynar_search_or_negative(xbt_dynar_t const dynar, void *const elem)
 445 {
 446   unsigned long it;
 447
 448   for (it = 0; it < dynar->used; it++)
 449     if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 450       return it;
 451     }
 452
 453   return -1;
 454 }
 455
 456 /** @brief Returns a boolean indicating whether the element is part of the dynar
 457  *
 458  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 459  * what you want. Check the documentation of xbt_dynar_search() for more info.
 460  */
 461 int xbt_dynar_member(xbt_dynar_t const dynar, void *const elem)
 462 {
 463   xbt_ex_t e;
 464
 465   TRY {
 466     xbt_dynar_search(dynar, elem);
 467   } CATCH(e) {
 468     if (e.category == not_found_error) {
 469       xbt_ex_free(e);
 470       return 0;
 471     }
 472     RETHROW;
 473   }
 474   return 1;
 475 }
 476
 477 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 478  *
 479  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 480  * xbt_dynar_push_as() does.
 481  */
 482 inline void *xbt_dynar_push_ptr(xbt_dynar_t const dynar)
 483 {
 484   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 485 }
 486
 487 /** @brief Add an element at the end of the dynar */
 488 inline void xbt_dynar_push(xbt_dynar_t const dynar, const void *const src)
 489 {
 490   /* checks done in xbt_dynar_insert_at_ptr */
 491   memcpy(xbt_dynar_insert_at_ptr(dynar, dynar->used), src, dynar->elmsize);
 492 }
 493
 494 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 495  *
 496  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 497  * xbt_dynar_pop_as() does.
 498  */
 499 inline void *xbt_dynar_pop_ptr(xbt_dynar_t const dynar)
 500 {
 501   _check_populated_dynar(dynar);
 502   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 503   dynar->used--;
 504   return _xbt_dynar_elm(dynar, dynar->used);
 505 }
 506
 507 /** @brief Get and remove the last element of the dynar */
 508 inline void xbt_dynar_pop(xbt_dynar_t const dynar, void *const dst)
 509 {
 510   /* sanity checks done by remove_at */
 511   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 512   xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
 513 }
 514
 515 /** @brief Add an element at the begining of the dynar.
 516  *
 517  * This is less efficient than xbt_dynar_push()
 518  */
 519 inline void xbt_dynar_unshift(xbt_dynar_t const dynar, const void *const src)
 520 {
 521   /* sanity checks done by insert_at */
 522   xbt_dynar_insert_at(dynar, 0, src);
 523 }
 524
 525 /** @brief Get and remove the first element of the dynar.
 526  *
 527  * This is less efficient than xbt_dynar_pop()
 528  */
 529 inline void xbt_dynar_shift(xbt_dynar_t const dynar, void *const dst)
 530 {
 531   /* sanity checks done by remove_at */
 532   xbt_dynar_remove_at(dynar, 0, dst);
 533 }
 534
 535 /** @brief Apply a function to each member of a dynar
 536  *
 537  * The mapped function may change the value of the element itself, but should not mess with the structure of the dynar.
 538  */
 539 inline void xbt_dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op)
 540 {
 541   char *const data = (char *) dynar->data;
 542   const unsigned long elmsize = dynar->elmsize;
 543   const unsigned long used = dynar->used;
 544   unsigned long i;
 545
 546   _sanity_check_dynar(dynar);
 547
 548   for (i = 0; i < used; i++) {
 549     char* elm = (char*) data + i * elmsize;
 550     op(elm);
 551   }
 552 }
 553
 554 /** @brief Removes and free the entry pointed by the cursor
 555  *
 556  * This function can be used while traversing without problem.
 557  */
 558 inline void xbt_dynar_cursor_rm(xbt_dynar_t dynar, unsigned int *const cursor)
 559 {
 560   xbt_dynar_remove_at(dynar, (*cursor)--, NULL);
 561 }
 562
 563 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
 564  *
 565  * \param dynar the dynar to sort
 566  * \param compar_fn comparison function of type (int (compar_fn*) (void*) (void*)).
 567  *
 568  * Remark: if the elements stored in the dynar are structures, the compar_fn function has to retrieve the field to sort
 569  * first.
 570  */
 571 inline void xbt_dynar_sort(xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn)
 572 {
 573   qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
 574 }
 575
 576 static int strcmp_voidp(const void *pa, const void *pb) {
 577   return strcmp(*(const char **)pa, *(const char **)pb);
 578 }
 579
 580 /** @brief Sorts a dynar of strings (ie, char* data) */
 581 xbt_dynar_t xbt_dynar_sort_strings(xbt_dynar_t dynar)
 582 {
 583   xbt_dynar_sort(dynar, strcmp_voidp);
 584   return dynar; // to enable functional uses
 585 }
 586
 587 /** @brief Sorts a dynar according to their color assuming elements can have only three colors.
 588  * Since there are only three colors, it is linear and much faster than a classical sort.
 589  * See for example http://en.wikipedia.org/wiki/Dutch_national_flag_problem
 590  *
 591  * \param dynar the dynar to sort
 592  * \param color the color function of type (int (compar_fn*) (void*) (void*)). The return value of color is assumed to
 593  *        be 0, 1, or 2.
 594  *
 595  * At the end of the call, elements with color 0 are at the beginning of the dynar, elements with color 2 are at the
 596  * end and elements with color 1 are in the middle.
 597  *
 598  * Remark: if the elements stored in the dynar are structures, the color function has to retrieve the field to sort
 599  * first.
 600  */
 601 XBT_PUBLIC(void) xbt_dynar_three_way_partition(xbt_dynar_t const dynar, int_f_pvoid_t color)
 602 {
 603   unsigned long int i;
 604   unsigned long int p = -1;
 605   unsigned long int q = dynar->used;
 606   const unsigned long elmsize = dynar->elmsize;
 607   void *tmp = xbt_malloc(elmsize);
 608   void *elm;
 609
 610   for (i = 0; i < q;) {
 611     void *elmi = _xbt_dynar_elm(dynar, i);
 612     int colori = color(elmi);
 613
 614     if (colori == 1) {
 615       ++i;
 616     } else {
 617       if (colori == 0) {
 618         elm = _xbt_dynar_elm(dynar, ++p);
 619         ++i;
 620       } else {                  /* colori == 2 */
 621         elm = _xbt_dynar_elm(dynar, --q);
 622       }
 623       if (elm != elmi) {
 624         memcpy(tmp,  elm,  elmsize);
 625         memcpy(elm,  elmi, elmsize);
 626         memcpy(elmi, tmp,  elmsize);
 627       }
 628     }
 629   }
 630   xbt_free(tmp);
 631 }
 632
 633 /** @brief Transform a dynar into a NULL terminated array.
 634  *
 635  *  \param dynar the dynar to transform
 636  *  \return pointer to the first element of the array
 637  *
 638  *  Note: The dynar won't be usable afterwards.
 639  */
 640 inline void *xbt_dynar_to_array(xbt_dynar_t dynar)
 641 {
 642   void *res;
 643   xbt_dynar_shrink(dynar, 1);
 644   memset(xbt_dynar_push_ptr(dynar), 0, dynar->elmsize);
 645   res = dynar->data;
 646   free(dynar);
 647   return res;
 648 }
 649
 650 /** @brief Compare two dynars
 651  *
 652  *  \param d1 first dynar to compare
 653  *  \param d2 second dynar to compare
 654  *  \param compar function to use to compare elements
 655  *  \return 0 if d1 and d2 are equal and 1 if not equal
 656  *
 657  *  d1 and d2 should be dynars of pointers. The compar function takes two  elements and returns 0 when they are
 658  *  considered equal, and a value different of zero when they are considered different. Finally, d2 is destroyed
 659  *  afterwards.
 660  */
 661 int xbt_dynar_compare(xbt_dynar_t d1, xbt_dynar_t d2, int(*compar)(const void *, const void *))
 662 {
 663   int i ;
 664   int size;
 665   if((!d1) && (!d2)) return 0;
 666   if((!d1) || (!d2))
 667   {
 668     XBT_DEBUG("NULL dynar d1=%p d2=%p",d1,d2);
 669     xbt_dynar_free(&d2);
 670     return 1;
 671   }
 672   if((d1->elmsize)!=(d2->elmsize)) {
 673     XBT_DEBUG("Size of elmsize d1=%lu d2=%lu",d1->elmsize,d2->elmsize);
 674     xbt_dynar_free(&d2);
 675     return 1; // xbt_die
 676   }
 677   if(xbt_dynar_length(d1) != xbt_dynar_length(d2)) {
 678     XBT_DEBUG("Size of dynar d1=%lu d2=%lu",xbt_dynar_length(d1),xbt_dynar_length(d2));
 679     xbt_dynar_free(&d2);
 680     return 1;
 681   }
 682
 683   size = xbt_dynar_length(d1);
 684   for(i=0;i<size;i++) {
 685     void *data1 = xbt_dynar_get_as(d1, i, void *);
 686     void *data2 = xbt_dynar_get_as(d2, i, void *);
 687     XBT_DEBUG("link[%d] d1=%p d2=%p",i,data1,data2);
 688     if(compar(data1,data2)){
 689       xbt_dynar_free(&d2);
 690       return 1;
 691     }
 692   }
 693   xbt_dynar_free(&d2);
 694   return 0;
 695 }
 696
 697 #ifdef SIMGRID_TEST
 698
 699 #define NB_ELEM 5000
 700
 701 XBT_TEST_SUITE("dynar", "Dynar data container");
 702 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(xbt_dyn);
 703
 704 XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers")
 705 {
 706   /* Vars_decl [doxygen cruft] */
 707   xbt_dynar_t d;
 708   int i, cpt;
 709   unsigned int cursor;
 710   int *iptr;
 711
 712   xbt_test_add("==== Traverse the empty dynar");
 713   d = xbt_dynar_new(sizeof(int), NULL);
 714   xbt_dynar_foreach(d, cursor, i) {
 715     xbt_die( "Damnit, there is something in the empty dynar");
 716   }
 717   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 718   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 719   /* in your code is naturally the way to go outside a regression test */
 720
 721   xbt_test_add("==== Push %d int, set them again 3 times, traverse them, shift them", NB_ELEM);
 722   /* Populate_ints [doxygen cruft] */
 723   /* 1. Populate the dynar */
 724   d = xbt_dynar_new(sizeof(int), NULL);
 725   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 726     xbt_dynar_push_as(d, int, cpt);     /* This is faster (and possible only with scalars) */
 727     /* xbt_dynar_push(d,&cpt);       This would also work */
 728     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
 729   }
 730
 731   /* 2. Traverse manually the dynar */
 732   for (cursor = 0; cursor < NB_ELEM; cursor++) {
 733     iptr = xbt_dynar_get_ptr(d, cursor);
 734     xbt_test_assert(cursor == *iptr, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 735   }
 736
 737   /* 3. Traverse the dynar using the neat macro to that extend */
 738   xbt_dynar_foreach(d, cursor, cpt) {
 739     xbt_test_assert(cursor == cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 740   }
 741   /* end_of_traversal */
 742
 743   for (cpt = 0; cpt < NB_ELEM; cpt++)
 744     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
 745
 746   for (cpt = 0; cpt < NB_ELEM; cpt++)
 747     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
 748   /*     xbt_dynar_set(d,cpt,&cpt); */
 749
 750   for (cpt = 0; cpt < NB_ELEM; cpt++)
 751     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
 752
 753   cpt = 0;
 754   xbt_dynar_foreach(d, cursor, i) {
 755     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one (%d!=%d)", i, cpt);
 756     cpt++;
 757   }
 758   xbt_test_assert(cpt == NB_ELEM, "Cannot retrieve my %d values. Last got one is %d", NB_ELEM, cpt);
 759
 760   /* shifting [doxygen cruft] */
 761   /* 4. Shift all the values */
 762   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 763     xbt_dynar_shift(d, &i);
 764     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one (%d!=%d)", i, cpt);
 765     xbt_test_log("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
 766   }
 767
 768   int* pi;
 769   xbt_dynar_foreach_ptr(d, cursor, pi) {
 770     *pi = 0;
 771   }
 772   xbt_dynar_foreach(d, cursor, i) {
 773     xbt_test_assert(i == 0, "The value is not the same as the expected one.");
 774   }
 775   xbt_dynar_foreach_ptr(d, cursor, pi) {
 776     *pi = 1;
 777   }
 778   xbt_dynar_foreach(d, cursor, i) {
 779     xbt_test_assert(i == 1, "The value is not the same as the expected one.");
 780   }
 781
 782   /* 5. Free the resources */
 783   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 784   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 785   /* in your code is naturally the way to go outside a regression test */
 786
 787   xbt_test_add("==== Unshift/pop %d int", NB_ELEM);
 788   d = xbt_dynar_new(sizeof(int), NULL);
 789   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 790     xbt_dynar_unshift(d, &cpt);
 791     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
 792   }
 793   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 794     i = xbt_dynar_pop_as(d, int);
 795     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one (%d!=%d)", i, cpt);
 796     xbt_test_log("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
 797   }
 798   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 799   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 800   /* in your code is naturally the way to go outside a regression test */
 801
 802   xbt_test_add ("==== Push %d int, insert 1000 int in the middle, shift everything", NB_ELEM);
 803   d = xbt_dynar_new(sizeof(int), NULL);
 804   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 805     xbt_dynar_push_as(d, int, cpt);
 806     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
 807   }
 808   for (cpt = 0; cpt < NB_ELEM/5; cpt++) {
 809     xbt_dynar_insert_at_as(d, NB_ELEM/2, int, cpt);
 810     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
 811   }
 812
 813   for (cpt = 0; cpt < NB_ELEM/2; cpt++) {
 814     xbt_dynar_shift(d, &i);
 815     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one at the begining (%d!=%d)",
 816                      i, cpt);
 817     XBT_DEBUG("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
 818   }
 819   for (cpt = 999; cpt >= 0; cpt--) {
 820     xbt_dynar_shift(d, &i);
 821     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
 822                      i, cpt);
 823   }
 824   for (cpt = 2500; cpt < NB_ELEM; cpt++) {
 825     xbt_dynar_shift(d, &i);
 826     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one at the end (%d!=%d)", i, cpt);
 827   }
 828   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 829   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 830   /* in your code is naturally the way to go outside a regression test */
 831
 832   xbt_test_add("==== Push %d int, remove 2000-4000. free the rest", NB_ELEM);
 833   d = xbt_dynar_new(sizeof(int), NULL);
 834   for (cpt = 0; cpt < NB_ELEM; cpt++)
 835     xbt_dynar_push_as(d, int, cpt);
 836
 837   for (cpt = 2000; cpt < 4000; cpt++) {
 838     xbt_dynar_remove_at(d, 2000, &i);
 839     xbt_test_assert(i == cpt, "Remove a bad value. Got %d, expected %d", i, cpt);
 840     XBT_DEBUG("remove %d, length=%lu", cpt, xbt_dynar_length(d));
 841   }
 842   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 843   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 844   /* in your code is naturally the way to go outside a regression test */
 845 }
 846
 847 /*******************************************************************************/
 848 XBT_TEST_UNIT("insert",test_dynar_insert,"Using the xbt_dynar_insert and xbt_dynar_remove functions")
 849 {
 850   xbt_dynar_t d = xbt_dynar_new(sizeof(unsigned int), NULL);
 851   unsigned int cursor;
 852   int cpt;
 853
 854   xbt_test_add("==== Insert %d int, traverse them, remove them",NB_ELEM);
 855   /* Populate_ints [doxygen cruft] */
 856   /* 1. Populate the dynar */
 857   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 858     xbt_dynar_insert_at(d, cpt, &cpt);
 859     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
 860   }
 861
 862   /* 3. Traverse the dynar */
 863   xbt_dynar_foreach(d, cursor, cpt) {
 864     xbt_test_assert(cursor == cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 865   }
 866   /* end_of_traversal */
 867
 868   /* Re-fill with the same values using set_as (and re-verify) */
 869   for (cpt = 0; cpt < NB_ELEM; cpt++)
 870     xbt_dynar_set_as(d, cpt, int, cpt);
 871   xbt_dynar_foreach(d, cursor, cpt)
 872     xbt_test_assert(cursor == cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 873
 874   for (cpt = 0; cpt < NB_ELEM; cpt++) {
 875     int val;
 876     xbt_dynar_remove_at(d,0,&val);
 877     xbt_test_assert(cpt == val, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 878   }
 879   xbt_test_assert(xbt_dynar_is_empty(d), "There is still %lu elements in the dynar after removing everything",
 880                    xbt_dynar_length(d));
 881   xbt_dynar_free(&d);
 882
 883   /* ********************* */
 884   xbt_test_add("==== Insert %d int in reverse order, traverse them, remove them",NB_ELEM);
 885   d = xbt_dynar_new(sizeof(int), NULL);
 886   for (cpt = NB_ELEM-1; cpt >=0; cpt--) {
 887     xbt_dynar_replace(d, cpt, &cpt);
 888     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
 889   }
 890
 891   /* 3. Traverse the dynar */
 892   xbt_dynar_foreach(d, cursor, cpt) {
 893     xbt_test_assert(cursor == cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 894   }
 895   /* end_of_traversal */
 896
 897   for (cpt =NB_ELEM-1; cpt >=0; cpt--) {
 898     int val;
 899     xbt_dynar_remove_at(d,xbt_dynar_length(d)-1,&val);
 900     xbt_test_assert(cpt == val, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
 901   }
 902   xbt_test_assert(xbt_dynar_is_empty(d), "There is still %lu elements in the dynar after removing everything",
 903                    xbt_dynar_length(d));
 904   xbt_dynar_free(&d);
 905 }
 906
 907 /*******************************************************************************/
 908 XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles")
 909 {
 910   xbt_dynar_t d;
 911   int cpt;
 912   unsigned int cursor;
 913   double d1, d2;
 914
 915   xbt_test_add("==== Traverse the empty dynar");
 916   d = xbt_dynar_new(sizeof(int), NULL);
 917   xbt_dynar_foreach(d, cursor, cpt) {
 918     xbt_test_assert(FALSE, "Damnit, there is something in the empty dynar");
 919   }
 920   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 921   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 922   /* in your code is naturally the way to go outside a regression test */
 923
 924   xbt_test_add("==== Push/shift 5000 doubles");
 925   d = xbt_dynar_new(sizeof(double), NULL);
 926   for (cpt = 0; cpt < 5000; cpt++) {
 927     d1 = (double) cpt;
 928     xbt_dynar_push(d, &d1);
 929   }
 930   xbt_dynar_foreach(d, cursor, d2) {
 931     d1 = (double) cursor;
 932     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2);
 933   }
 934   for (cpt = 0; cpt < 5000; cpt++) {
 935     d1 = (double) cpt;
 936     xbt_dynar_shift(d, &d2);
 937     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2);
 938   }
 939   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 940   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 941   /* in your code is naturally the way to go outside a regression test */
 942
 943   xbt_test_add("==== Unshift/pop 5000 doubles");
 944   d = xbt_dynar_new(sizeof(double), NULL);
 945   for (cpt = 0; cpt < 5000; cpt++) {
 946     d1 = (double) cpt;
 947     xbt_dynar_unshift(d, &d1);
 948   }
 949   for (cpt = 0; cpt < 5000; cpt++) {
 950     d1 = (double) cpt;
 951     xbt_dynar_pop(d, &d2);
 952     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2);
 953   }
 954   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 955   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 956   /* in your code is naturally the way to go outside a regression test */
 957
 958   xbt_test_add("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
 959   d = xbt_dynar_new(sizeof(double), NULL);
 960   for (cpt = 0; cpt < 5000; cpt++) {
 961     d1 = (double) cpt;
 962     xbt_dynar_push(d, &d1);
 963   }
 964   for (cpt = 0; cpt < 1000; cpt++) {
 965     d1 = (double) cpt;
 966     xbt_dynar_insert_at(d, 2500, &d1);
 967   }
 968
 969   for (cpt = 0; cpt < 2500; cpt++) {
 970     d1 = (double) cpt;
 971     xbt_dynar_shift(d, &d2);
 972     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
 973                      d1, d2);
 974     XBT_DEBUG("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
 975   }
 976   for (cpt = 999; cpt >= 0; cpt--) {
 977     d1 = (double) cpt;
 978     xbt_dynar_shift(d, &d2);
 979     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
 980                      d1, d2);
 981   }
 982   for (cpt = 2500; cpt < 5000; cpt++) {
 983     d1 = (double) cpt;
 984     xbt_dynar_shift(d, &d2);
 985     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one at the end (%f!=%f)", d1, d2);
 986   }
 987   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
 988   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
 989   /* in your code is naturally the way to go outside a regression test */
 990
 991   xbt_test_add("==== Push 5000 double, remove 2000-4000. free the rest");
 992   d = xbt_dynar_new(sizeof(double), NULL);
 993   for (cpt = 0; cpt < 5000; cpt++) {
 994     d1 = (double) cpt;
 995     xbt_dynar_push(d, &d1);
 996   }
 997   for (cpt = 2000; cpt < 4000; cpt++) {
 998     d1 = (double) cpt;
 999     xbt_dynar_remove_at(d, 2000, &d2);
1000     xbt_test_assert(d1 == d2, "Remove a bad value. Got %f, expected %f", d2, d1);
1001   }
1002   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1003   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1004   /* in your code is naturally the way to go outside a regression test */
1005 }
1006
1007 /* doxygen_string_cruft */
1008
1009 /*******************************************************************************/
1010 XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings")
1011 {
1012   xbt_dynar_t d;
1013   int cpt;
1014   unsigned int iter;
1015   char buf[1024];
1016   char *s1, *s2;
1017
1018   xbt_test_add("==== Traverse the empty dynar");
1019   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1020   xbt_dynar_foreach(d, iter, s1) {
1021     xbt_test_assert(FALSE, "Damnit, there is something in the empty dynar");
1022   }
1023   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1024   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1025   /* in your code is naturally the way to go outside a regression test */
1026
1027   xbt_test_add("==== Push %d strings, set them again 3 times, shift them", NB_ELEM);
1028   /* Populate_str [doxygen cruft] */
1029   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1030   /* 1. Populate the dynar */
1031   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1032     sprintf(buf, "%d", cpt);
1033     s1 = xbt_strdup(buf);
1034     xbt_dynar_push(d, &s1);
1035   }
1036   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1037     sprintf(buf, "%d", cpt);
1038     s1 = xbt_strdup(buf);
1039     xbt_dynar_replace(d, cpt, &s1);
1040   }
1041   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1042     sprintf(buf, "%d", cpt);
1043     s1 = xbt_strdup(buf);
1044     xbt_dynar_replace(d, cpt, &s1);
1045   }
1046   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1047     sprintf(buf, "%d", cpt);
1048     s1 = xbt_strdup(buf);
1049     xbt_dynar_replace(d, cpt, &s1);
1050   }
1051   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1052     sprintf(buf, "%d", cpt);
1053     xbt_dynar_shift(d, &s2);
1054     xbt_test_assert(!strcmp(buf, s2), "The retrieved value is not the same than the injected one (%s!=%s)", buf, s2);
1055     free(s2);
1056   }
1057   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1058   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1059   /* in your code is naturally the way to go outside a regression test */
1060
1061   xbt_test_add("==== Unshift, traverse and pop %d strings", NB_ELEM);
1062   d = xbt_dynar_new(sizeof(char **), &xbt_free_ref);
1063   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1064     sprintf(buf, "%d", cpt);
1065     s1 = xbt_strdup(buf);
1066     xbt_dynar_unshift(d, &s1);
1067   }
1068   /* 2. Traverse the dynar with the macro */
1069   xbt_dynar_foreach(d, iter, s1) {
1070     sprintf(buf, "%u", NB_ELEM - iter - 1);
1071     xbt_test_assert(!strcmp(buf, s1), "The retrieved value is not the same than the injected one (%s!=%s)", buf, s1);
1072   }
1073   /* 3. Traverse the dynar with the macro */
1074   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1075     sprintf(buf, "%d", cpt);
1076     xbt_dynar_pop(d, &s2);
1077     xbt_test_assert(!strcmp(buf, s2), "The retrieved value is not the same than the injected one (%s!=%s)", buf, s2);
1078     free(s2);
1079   }
1080   /* 4. Free the resources */
1081   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1082   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1083   /* in your code is naturally the way to go outside a regression test */
1084
1085   xbt_test_add("==== Push %d strings, insert %d strings in the middle, shift everything", NB_ELEM, NB_ELEM / 5);
1086   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1087   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1088     sprintf(buf, "%d", cpt);
1089     s1 = xbt_strdup(buf);
1090     xbt_dynar_push(d, &s1);
1091   }
1092   for (cpt = 0; cpt < NB_ELEM / 5; cpt++) {
1093     sprintf(buf, "%d", cpt);
1094     s1 = xbt_strdup(buf);
1095     xbt_dynar_insert_at(d, NB_ELEM / 2, &s1);
1096   }
1097
1098   for (cpt = 0; cpt < NB_ELEM / 2; cpt++) {
1099     sprintf(buf, "%d", cpt);
1100     xbt_dynar_shift(d, &s2);
1101     xbt_test_assert(!strcmp(buf, s2),
1102                      "The retrieved value is not the same than the injected one at the begining (%s!=%s)", buf, s2);
1103     free(s2);
1104   }
1105   for (cpt = (NB_ELEM / 5) - 1; cpt >= 0; cpt--) {
1106     sprintf(buf, "%d", cpt);
1107     xbt_dynar_shift(d, &s2);
1108     xbt_test_assert(!strcmp(buf, s2),
1109                      "The retrieved value is not the same than the injected one in the middle (%s!=%s)", buf, s2);
1110     free(s2);
1111   }
1112   for (cpt = NB_ELEM / 2; cpt < NB_ELEM; cpt++) {
1113     sprintf(buf, "%d", cpt);
1114     xbt_dynar_shift(d, &s2);
1115     xbt_test_assert(!strcmp(buf, s2), "The retrieved value is not the same than the injected one at the end (%s!=%s)",
1116                      buf, s2);
1117     free(s2);
1118   }
1119   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1120   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1121   /* in your code is naturally the way to go outside a regression test */
1122
1123   xbt_test_add("==== Push %d strings, remove %d-%d. free the rest", NB_ELEM, 2 * (NB_ELEM / 5), 4 * (NB_ELEM / 5));
1124   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1125   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1126     sprintf(buf, "%d", cpt);
1127     s1 = xbt_strdup(buf);
1128     xbt_dynar_push(d, &s1);
1129   }
1130   for (cpt = 2 * (NB_ELEM / 5); cpt < 4 * (NB_ELEM / 5); cpt++) {
1131     sprintf(buf, "%d", cpt);
1132     xbt_dynar_remove_at(d, 2 * (NB_ELEM / 5), &s2);
1133     xbt_test_assert(!strcmp(buf, s2), "Remove a bad value. Got %s, expected %s", s2, buf);
1134     free(s2);
1135   }
1136   xbt_dynar_free(&d);           /* end_of_doxygen */
1137 }
1138 #endif                          /* SIMGRID_TEST */