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