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