src/xbt/dynar.c

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