src/xbt/dynar.c

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