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