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