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 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
  22
  23
  24 #define __sanity_check_dynar(dynar)       \
  25            xbt_assert0(dynar,           \
  26                         "dynar is NULL")
  27 #define __sanity_check_idx(idx)                \
  28            xbt_assert1(idx >= 0,             \
  29                         "dynar idx(=%d) < 0", \
  30                         (int) (idx))
  31 #define __check_inbound_idx(dynar, idx)                                                \
  32            xbt_assert2(idx < dynar->used,                                             \
  33                         "dynar is not that long. You asked %d, but it's only %lu long", \
  34                         (int) (idx), (unsigned long) dynar->used)
  35 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
  36            xbt_assert2(idx <= dynar->used,                                            \
  37                         "dynar is not that long. You asked %d, but it's only %lu long (could have been equal to it)", \
  38                         (int) (idx), (unsigned long) dynar->used)
  39 #define __check_populated_dynar(dynar)            \
  40            xbt_assert1(dynar->used,              \
  41                         "dynar %p contains nothing",(void*)dynar)
  42
  43 static _XBT_INLINE
  44 void _xbt_clear_mem(void * const ptr,
  45                      const unsigned long length) {
  46   memset(ptr, 0, length);
  47 }
  48
  49 static _XBT_INLINE
  50 void
  51 _xbt_dynar_expand(xbt_dynar_t const dynar,
  52                    const int          nb) {
  53   const unsigned long old_size    = dynar->size;
  54
  55   if (nb > old_size) {
  56     char * const old_data    = (char *) dynar->data;
  57
  58     const unsigned long elmsize     = dynar->elmsize;
  59     const unsigned long old_length  = old_size*elmsize;
  60
  61     const unsigned long used        = dynar->used;
  62     const unsigned long used_length = used*elmsize;
  63
  64     const unsigned long new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
  65     const unsigned long new_length  = new_size*elmsize;
  66     char * const new_data    = (char *) xbt_malloc0(elmsize*new_size);
  67
  68     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
  69
  70     if (old_data) {
  71       memcpy(new_data, old_data, used_length);
  72       _xbt_clear_mem(old_data, old_length);
  73       free(old_data);
  74     }
  75
  76     _xbt_clear_mem(new_data + used_length, new_length - used_length);
  77
  78     dynar->size = new_size;
  79     dynar->data = new_data;
  80   }
  81 }
  82
  83 static _XBT_INLINE
  84 void *
  85 _xbt_dynar_elm(const xbt_dynar_t  dynar,
  86                 const unsigned long idx) {
  87   char * const data    = (char*) dynar->data;
  88   const unsigned long elmsize = dynar->elmsize;
  89
  90   return data + idx*elmsize;
  91 }
  92
  93 static _XBT_INLINE
  94 void
  95 _xbt_dynar_get_elm(void  * const       dst,
  96                     const xbt_dynar_t  dynar,
  97                     const unsigned long idx) {
  98   void * const elm     = _xbt_dynar_elm(dynar, idx);
  99
 100   memcpy(dst, elm, dynar->elmsize);
 101 }
 102
 103 static _XBT_INLINE
 104 void
 105 _xbt_dynar_put_elm(const xbt_dynar_t  dynar,
 106                     const unsigned long idx,
 107                     const void * const  src) {
 108   void * const elm     = _xbt_dynar_elm(dynar, idx);
 109   const unsigned long elmsize = dynar->elmsize;
 110
 111   memcpy(elm, src, elmsize);
 112 }
 113
 114 void
 115 xbt_dynar_dump(xbt_dynar_t dynar) {
 116   INFO5("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
 117         dynar->size, dynar->used, dynar->elmsize, dynar->data, dynar->free_f);
 118 }
 119
 120 /** @brief Constructor
 121  *
 122  * \param elmsize size of each element in the dynar
 123  * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
 124  *
 125  * Creates a new dynar. If a free_func is provided, the elements have to be
 126  * pointer of pointer. That is to say that dynars can contain either base
 127  * types (int, char, double, etc) or pointer of pointers (struct **).
 128  */
 129 xbt_dynar_t
 130 xbt_dynar_new(const unsigned long           elmsize,
 131                void_f_pvoid_t * const free_f) {
 132
 133   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
 134
 135   dynar->size    = 0;
 136   dynar->used    = 0;
 137   dynar->elmsize = elmsize;
 138   dynar->data    = NULL;
 139   dynar->free_f    = free_f;
 140
 141   return dynar;
 142 }
 143
 144 /** @brief Destructor of the structure not touching to the content
 145  *
 146  * \param dynar poor victim
 147  *
 148  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
 149  * is not touched (the \a free_f function is not used)
 150  */
 151 void
 152 xbt_dynar_free_container(xbt_dynar_t *dynar) {
 153   if (dynar && *dynar) {
 154
 155     if ((*dynar)->data) {
 156       _xbt_clear_mem((*dynar)->data, (*dynar)->size);
 157       free((*dynar)->data);
 158     }
 159
 160     _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
 161
 162     free(*dynar);
 163     *dynar=NULL;
 164   }
 165 }
 166
 167 /** @brief Frees the content and set the size to 0
 168  *
 169  * \param dynar who to squeeze
 170  */
 171 void
 172 xbt_dynar_reset(xbt_dynar_t const dynar) {
 173
 174   __sanity_check_dynar(dynar);
 175
 176   DEBUG1("Reset the dynar %p",(void*)dynar);
 177   if (dynar->free_f) {
 178     xbt_dynar_map(dynar, dynar->free_f);
 179   }
 180 /*
 181   if (dynar->data)
 182     free(dynar->data);
 183
 184   dynar->size = 0;
 185   */
 186   dynar->used = 0;
 187 /*  dynar->data = NULL;*/
 188 }
 189
 190 /** @brief Destructor
 191  *
 192  * \param dynar poor victim
 193  *
 194  * kilkil a dynar and its content
 195  */
 196
 197 void
 198 xbt_dynar_free(xbt_dynar_t * dynar) {
 199   if (dynar && *dynar) {
 200     xbt_dynar_reset(*dynar);
 201     xbt_dynar_free_container(dynar);
 202   }
 203 }
 204 /** \brief free a dynar passed as void* (handy to store dynar in dynars or dict) */
 205 void xbt_dynar_free_voidp(void *d) {
 206    xbt_dynar_free( (xbt_dynar_t*) d);
 207 }
 208
 209 /** @brief Count of dynar's elements
 210  *
 211  * \param dynar the dynar we want to mesure
 212  */
 213 unsigned long
 214 xbt_dynar_length(const xbt_dynar_t dynar) {
 215   return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
 216 }
 217
 218 /** @brief Retrieve a copy of the Nth element of a dynar.
 219  *
 220  * \param dynar information dealer
 221  * \param idx index of the slot we want to retrieve
 222  * \param[out] dst where to put the result to.
 223  */
 224 void
 225 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
 226                    const int          idx,
 227                    void       * const dst) {
 228
 229   __sanity_check_dynar(dynar);
 230   __sanity_check_idx(idx);
 231   __check_inbound_idx(dynar, idx);
 232
 233   _xbt_dynar_get_elm(dst, dynar, idx);
 234 }
 235
 236 /** @brief Retrieve a pointer to the Nth element of a dynar.
 237  *
 238  * \param dynar information dealer
 239  * \param idx index of the slot we want to retrieve
 240  * \return the \a idx-th element of \a dynar.
 241  *
 242  * \warning The returned value is the actual content of the dynar.
 243  * Make a copy before fooling with it.
 244  */
 245 void*
 246 xbt_dynar_get_ptr(const xbt_dynar_t dynar, const int idx) {
 247
 248   __sanity_check_dynar(dynar);
 249   __sanity_check_idx(idx);
 250   __check_inbound_idx(dynar, idx);
 251
 252   return _xbt_dynar_elm(dynar, idx);
 253 }
 254
 255 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
 256  *
 257  * \param dynar information dealer
 258  * \param idx index of the slot we want to modify
 259  * \param src What will be feeded to the dynar
 260  *
 261  * If you want to free the previous content, use xbt_dynar_replace().
 262  */
 263 void
 264 xbt_dynar_set(xbt_dynar_t         dynar,
 265                const int            idx,
 266                const void   * const src) {
 267
 268   __sanity_check_dynar(dynar);
 269   __sanity_check_idx(idx);
 270
 271   _xbt_dynar_expand(dynar, idx+1);
 272
 273   if (idx >= dynar->used) {
 274     dynar->used = idx+1;
 275   }
 276
 277   _xbt_dynar_put_elm(dynar, idx, src);
 278 }
 279
 280 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
 281  *
 282  * \param dynar
 283  * \param idx
 284  * \param object
 285  *
 286  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 287  * free the previous value at this position. If you don't want to free the
 288  * previous content, use xbt_dynar_set().
 289  */
 290 void
 291 xbt_dynar_replace(xbt_dynar_t         dynar,
 292                    const int            idx,
 293                    const void   * const object) {
 294
 295   __sanity_check_dynar(dynar);
 296   __sanity_check_idx(idx);
 297
 298   if (idx < dynar->used && dynar->free_f) {
 299     void * const old_object = _xbt_dynar_elm(dynar, idx);
 300
 301     dynar->free_f(old_object);
 302   }
 303
 304   xbt_dynar_set(dynar, idx, object);
 305 }
 306
 307 /** @brief Make room for a new element, and return a pointer to it
 308  *
 309  * You can then use regular affectation to set its value instead of relying
 310  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
 311  */
 312 void *
 313 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
 314                         const int            idx) {
 315
 316   __sanity_check_dynar(dynar);
 317   __sanity_check_idx(idx);
 318   __check_sloppy_inbound_idx(dynar, idx);
 319
 320   {
 321     const unsigned long old_used = dynar->used;
 322     const unsigned long new_used = old_used + 1;
 323
 324     _xbt_dynar_expand(dynar, new_used);
 325
 326     {
 327       const unsigned long nb_shift =  old_used - idx;
 328
 329       if (nb_shift)
 330          memmove(_xbt_dynar_elm(dynar, idx+1),
 331                  _xbt_dynar_elm(dynar, idx),
 332                  nb_shift * dynar->elmsize);
 333     }
 334
 335     dynar->used = new_used;
 336     return _xbt_dynar_elm(dynar,idx);
 337   }
 338 }
 339
 340 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
 341  *
 342  * Set the Nth element of a dynar, expanding the dynar if needed, and
 343  * moving the previously existing value and all subsequent ones to one
 344  * position right in the dynar.
 345  */
 346 void
 347 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
 348                     const int            idx,
 349                     const void   * const src) {
 350
 351   /* checks done in xbt_dynar_insert_at_ptr */
 352   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
 353          src,
 354          dynar->elmsize);
 355 }
 356
 357 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 358  *
 359  * Get the Nth element of a dynar, removing it from the dynar and moving
 360  * all subsequent values to one position left in the dynar.
 361  */
 362 void
 363 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
 364                      const int            idx,
 365                      void         * const object) {
 366
 367   unsigned long nb_shift;
 368   unsigned long offset;
 369
 370   __sanity_check_dynar(dynar);
 371   __sanity_check_idx(idx);
 372   __check_inbound_idx(dynar, idx);
 373
 374   if (object) {
 375     _xbt_dynar_get_elm(object, dynar, idx);
 376   } else if (dynar->free_f) {
 377     char elm[SIZEOF_MAX];
 378     _xbt_dynar_get_elm(elm, dynar, idx);
 379     (*dynar->free_f)(elm);
 380   }
 381
 382   nb_shift =  dynar->used-1 - idx;
 383   offset   =  nb_shift * dynar->elmsize;
 384
 385   memmove(_xbt_dynar_elm(dynar, idx),
 386           _xbt_dynar_elm(dynar, idx+1),
 387           offset);
 388
 389   dynar->used--;
 390 }
 391
 392 /** @brief Returns the position of the element in the dynar
 393  *
 394  * Raises not_found_error if not found.
 395  */
 396 int
 397 xbt_dynar_search(xbt_dynar_t  const dynar,
 398                  void        *const elem) {
 399   int it;
 400
 401   for (it=0; it< dynar->size; it++)
 402     if (!memcmp(_xbt_dynar_elm(dynar, it),elem,dynar->elmsize))
 403       return it;
 404
 405   THROW2(not_found_error,0,"Element %p not part of dynar %p",elem,dynar);
 406 }
 407
 408 /** @brief Returns a boolean indicating whether the element is part of the dynar */
 409 int
 410 xbt_dynar_member(xbt_dynar_t  const dynar,
 411                  void        *const elem) {
 412
 413   xbt_ex_t e;
 414
 415   TRY {
 416      xbt_dynar_search(dynar,elem);
 417   } CATCH(e) {
 418      if (e.category == not_found_error) {
 419         xbt_ex_free(e);
 420         return 0;
 421      }
 422      RETHROW;
 423   }
 424   return 1;
 425 }
 426
 427 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 428  *
 429  * You can then use regular affectation to set its value instead of relying
 430  * on the slow memcpy. This is what xbt_dynar_push_as() does.
 431  */
 432 void *
 433 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
 434   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 435 }
 436
 437 /** @brief Add an element at the end of the dynar */
 438 void
 439 xbt_dynar_push(xbt_dynar_t  const dynar,
 440                 const void   * const src) {
 441   /* sanity checks done by insert_at */
 442   xbt_dynar_insert_at(dynar, dynar->used, src);
 443 }
 444
 445 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 446  *
 447  * You can then use regular affectation to set its value instead of relying
 448  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
 449  */
 450 void *
 451 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 452
 453   __check_populated_dynar(dynar);
 454   DEBUG1("Pop %p",(void*)dynar);
 455   dynar->used--;
 456   return _xbt_dynar_elm(dynar,dynar->used);
 457 }
 458
 459 /** @brief Get and remove the last element of the dynar */
 460 void
 461 xbt_dynar_pop(xbt_dynar_t  const dynar,
 462               void         * const dst) {
 463
 464   /* sanity checks done by remove_at */
 465   DEBUG1("Pop %p",(void*)dynar);
 466   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 467 }
 468
 469 /** @brief Add an element at the begining of the dynar.
 470  *
 471  * This is less efficient than xbt_dynar_push()
 472  */
 473 void
 474 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 475                    const void   * const src) {
 476
 477   /* sanity checks done by insert_at */
 478   xbt_dynar_insert_at(dynar, 0, src);
 479 }
 480
 481 /** @brief Get and remove the first element of the dynar.
 482  *
 483  * This is less efficient than xbt_dynar_pop()
 484  */
 485 void
 486 xbt_dynar_shift(xbt_dynar_t  const dynar,
 487                  void         * const dst) {
 488
 489   /* sanity checks done by remove_at */
 490   xbt_dynar_remove_at(dynar, 0, dst);
 491 }
 492
 493 /** @brief Apply a function to each member of a dynar
 494  *
 495  * The mapped function may change the value of the element itself,
 496  * but should not mess with the structure of the dynar.
 497  */
 498 void
 499 xbt_dynar_map(const xbt_dynar_t  dynar,
 500                void_f_pvoid_t     * const op) {
 501
 502   __sanity_check_dynar(dynar);
 503
 504   {
 505     char         elm[SIZEOF_MAX];
 506     const unsigned long used = dynar->used;
 507     unsigned long       i    = 0;
 508
 509     for (i = 0; i < used; i++) {
 510       _xbt_dynar_get_elm(elm, dynar, i);
 511       op(elm);
 512     }
 513   }
 514 }
 515
 516 /** @brief Put the cursor at the begining of the dynar.
 517  *
 518  * Actually, the cursor is set one step before the begining, so that you
 519  * can iterate over the dynar with a for loop.
 520  */
 521 void
 522 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 523                        int        * const cursor) {
 524
 525   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 526   *cursor = 0;
 527 }
 528
 529 /** @brief Move the cursor to the next value */
 530 void
 531 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 532                        int        * const cursor) {
 533
 534   (*cursor)++;
 535 }
 536
 537 /** @brief Get the data currently pointed by the cursor */
 538 int
 539 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 540                       int                * const cursor,
 541                       void               * const dst) {
 542
 543   __sanity_check_dynar(dynar);
 544   {
 545
 546     const int idx = *cursor;
 547
 548     if (idx >= dynar->used) {
 549       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 550       return FALSE;
 551     }
 552     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 553
 554     _xbt_dynar_get_elm(dst, dynar, idx);
 555   }
 556   return TRUE;
 557
 558 }
 559
 560 /** @brief Removes and free the entry pointed by the cursor
 561  *
 562  * This function can be used while traversing without problem.
 563  */
 564 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 565                           int          * const cursor) {
 566   void *dst;
 567
 568   if (dynar->elmsize > sizeof(void*)) {
 569     DEBUG0("Elements too big to fit into a pointer");
 570     if (dynar->free_f) {
 571       dst=xbt_malloc(dynar->elmsize);
 572       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 573       (dynar->free_f)(dst);
 574       free(dst);
 575     } else {
 576       DEBUG0("Ok, we dont care about the element without free function");
 577       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 578     }
 579
 580   } else {
 581     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 582     if (dynar->free_f)
 583       (dynar->free_f)(dst);
 584   }
 585 }
 586
 587 #ifdef SIMGRID_TEST
 588
 589 #define NB_ELEM 5000
 590
 591 XBT_TEST_SUITE("dynar","Dynar data container");
 592 XBT_LOG_EXTERNAL_CATEGORY(dynar);
 593 XBT_LOG_DEFAULT_CATEGORY(dynar);
 594
 595 XBT_TEST_UNIT("int",test_dynar_int,"Dyars of integers") {
 596    /* Vars_decl [doxygen cruft] */
 597    xbt_dynar_t d;
 598    int i,cpt,cursor;
 599    int *iptr;
 600
 601    xbt_test_add0("==== Traverse the empty dynar");
 602    d=xbt_dynar_new(sizeof(int),NULL);
 603    xbt_dynar_foreach(d,cursor,i){
 604      xbt_assert0(0,"Damnit, there is something in the empty dynar");
 605    }
 606    xbt_dynar_free(&d);
 607    xbt_dynar_free(&d);
 608
 609    xbt_test_add1("==== Push %d int, set them again 3 times, traverse them, shift them",
 610         NB_ELEM);
 611    /* Populate_ints [doxygen cruft] */
 612    /* 1. Populate the dynar */
 613    d=xbt_dynar_new(sizeof(int),NULL);
 614    for (cpt=0; cpt< NB_ELEM; cpt++) {
 615      xbt_dynar_push_as(d,int,cpt); /* This is faster (and possible only with scalars) */
 616      /* xbt_dynar_push(d,&cpt);       This would also work */
 617      xbt_test_log2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 618    }
 619
 620    /* 2. Traverse manually the dynar */
 621    for (cursor=0; cursor< NB_ELEM; cursor++) {
 622      iptr=xbt_dynar_get_ptr(d,cursor);
 623      xbt_test_assert2(cursor == *iptr,
 624                       "The retrieved value is not the same than the injected one (%d!=%d)",
 625                       cursor,cpt);
 626    }
 627
 628    /* 3. Traverse the dynar using the neat macro to that extend */
 629    xbt_dynar_foreach(d,cursor,cpt){
 630      xbt_test_assert2(cursor == cpt,
 631                       "The retrieved value is not the same than the injected one (%d!=%d)",
 632                       cursor,cpt);
 633    }
 634    /* end_of_traversal */
 635
 636    for (cpt=0; cpt< NB_ELEM; cpt++)
 637      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 638
 639    for (cpt=0; cpt< NB_ELEM; cpt++)
 640      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 641 /*     xbt_dynar_set(d,cpt,&cpt);*/
 642
 643    for (cpt=0; cpt< NB_ELEM; cpt++)
 644      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 645
 646    cpt=0;
 647    xbt_dynar_foreach(d,cursor,i){
 648      xbt_test_assert2(i == cpt,
 649                       "The retrieved value is not the same than the injected one (%d!=%d)",
 650                       i,cpt);
 651      cpt++;
 652    }
 653    xbt_test_assert2(cpt == NB_ELEM,
 654                     "Cannot retrieve my %d values. Last got one is %d",
 655                     NB_ELEM, cpt);
 656
 657    /* shifting [doxygen cruft] */
 658    /* 4. Shift all the values */
 659    for (cpt=0; cpt< NB_ELEM; cpt++) {
 660      xbt_dynar_shift(d,&i);
 661      xbt_test_assert2(i == cpt,
 662                       "The retrieved value is not the same than the injected one (%d!=%d)",
 663                       i,cpt);
 664      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 665    }
 666
 667    /* 5. Free the resources */
 668    xbt_dynar_free(&d);
 669    xbt_dynar_free(&d);
 670
 671
 672    xbt_test_add1("==== Unshift/pop %d int",NB_ELEM);
 673    d=xbt_dynar_new(sizeof(int),NULL);
 674    for (cpt=0; cpt< NB_ELEM; cpt++) {
 675      xbt_dynar_unshift(d,&cpt);
 676      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 677    }
 678    for (cpt=0; cpt< NB_ELEM; cpt++) {
 679      i=xbt_dynar_pop_as(d,int);
 680      xbt_test_assert2(i == cpt,
 681                       "The retrieved value is not the same than the injected one (%d!=%d)",
 682                       i,cpt);
 683      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 684    }
 685    xbt_dynar_free(&d);
 686    xbt_dynar_free(&d);
 687
 688
 689    xbt_test_add1("==== Push %d int, insert 1000 int in the middle, shift everything",NB_ELEM);
 690    d=xbt_dynar_new(sizeof(int),NULL);
 691    for (cpt=0; cpt< NB_ELEM; cpt++) {
 692      xbt_dynar_push_as(d,int,cpt);
 693      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 694    }
 695    for (cpt=0; cpt< 1000; cpt++) {
 696      xbt_dynar_insert_at_as(d,2500,int,cpt);
 697      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 698    }
 699
 700    for (cpt=0; cpt< 2500; cpt++) {
 701      xbt_dynar_shift(d,&i);
 702      xbt_test_assert2(i == cpt,
 703              "The retrieved value is not the same than the injected one at the begining (%d!=%d)",
 704                i,cpt);
 705      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 706    }
 707    for (cpt=999; cpt>=0; cpt--) {
 708      xbt_dynar_shift(d,&i);
 709      xbt_test_assert2(i == cpt,
 710            "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
 711                       i,cpt);
 712    }
 713    for (cpt=2500; cpt< NB_ELEM; cpt++) {
 714      xbt_dynar_shift(d,&i);
 715       xbt_test_assert2(i == cpt,
 716            "The retrieved value is not the same than the injected one at the end (%d!=%d)",
 717                        i,cpt);
 718    }
 719    xbt_dynar_free(&d);
 720    xbt_dynar_free(&d);
 721
 722
 723    xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest",NB_ELEM);
 724    d=xbt_dynar_new(sizeof(int),NULL);
 725    for (cpt=0; cpt< NB_ELEM; cpt++)
 726      xbt_dynar_push_as(d,int,cpt);
 727
 728    for (cpt=2000; cpt< 4000; cpt++) {
 729      xbt_dynar_remove_at(d,2000,&i);
 730      xbt_test_assert2(i == cpt,
 731                       "Remove a bad value. Got %d, expected %d",
 732                       i,cpt);
 733      DEBUG2("remove %d, length=%lu",cpt, xbt_dynar_length(d));
 734    }
 735    xbt_dynar_free(&d);
 736    xbt_dynar_free(&d);
 737 }
 738
 739 XBT_TEST_UNIT("double",test_dynar_double,"Dyars of doubles") {
 740    xbt_dynar_t d;
 741    int cpt,cursor;
 742    double d1,d2;
 743
 744    xbt_test_add0("==== Traverse the empty dynar");
 745    d=xbt_dynar_new(sizeof(int),NULL);
 746    xbt_dynar_foreach(d,cursor,cpt){
 747      xbt_test_assert0(FALSE,
 748              "Damnit, there is something in the empty dynar");
 749    }
 750    xbt_dynar_free(&d);
 751    xbt_dynar_free(&d);
 752
 753    xbt_test_add0("==== Push/shift 5000 doubles");
 754    d=xbt_dynar_new(sizeof(double),NULL);
 755    for (cpt=0; cpt< 5000; cpt++) {
 756      d1=(double)cpt;
 757      xbt_dynar_push(d,&d1);
 758    }
 759    xbt_dynar_foreach(d,cursor,d2){
 760      d1=(double)cursor;
 761      xbt_test_assert2(d1 == d2,
 762            "The retrieved value is not the same than the injected one (%f!=%f)",
 763                   d1,d2);
 764    }
 765    for (cpt=0; cpt< 5000; cpt++) {
 766      d1=(double)cpt;
 767      xbt_dynar_shift(d,&d2);
 768      xbt_test_assert2(d1 == d2,
 769            "The retrieved value is not the same than the injected one (%f!=%f)",
 770                   d1,d2);
 771    }
 772    xbt_dynar_free(&d);
 773    xbt_dynar_free(&d);
 774
 775
 776    xbt_test_add0("==== Unshift/pop 5000 doubles");
 777    d=xbt_dynar_new(sizeof(double),NULL);
 778    for (cpt=0; cpt< 5000; cpt++) {
 779      d1=(double)cpt;
 780      xbt_dynar_unshift(d,&d1);
 781    }
 782    for (cpt=0; cpt< 5000; cpt++) {
 783      d1=(double)cpt;
 784      xbt_dynar_pop(d,&d2);
 785      xbt_test_assert2 (d1 == d2,
 786            "The retrieved value is not the same than the injected one (%f!=%f)",
 787                    d1,d2);
 788    }
 789    xbt_dynar_free(&d);
 790    xbt_dynar_free(&d);
 791
 792
 793
 794    xbt_test_add0("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
 795    d=xbt_dynar_new(sizeof(double),NULL);
 796    for (cpt=0; cpt< 5000; cpt++) {
 797      d1=(double)cpt;
 798      xbt_dynar_push(d,&d1);
 799    }
 800    for (cpt=0; cpt< 1000; cpt++) {
 801      d1=(double)cpt;
 802      xbt_dynar_insert_at(d,2500,&d1);
 803    }
 804
 805    for (cpt=0; cpt< 2500; cpt++) {
 806      d1=(double)cpt;
 807      xbt_dynar_shift(d,&d2);
 808      xbt_test_assert2(d1 == d2,
 809            "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
 810                   d1,d2);
 811      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 812    }
 813    for (cpt=999; cpt>=0; cpt--) {
 814      d1=(double)cpt;
 815      xbt_dynar_shift(d,&d2);
 816      xbt_test_assert2 (d1 == d2,
 817            "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
 818                    d1,d2);
 819    }
 820    for (cpt=2500; cpt< 5000; cpt++) {
 821      d1=(double)cpt;
 822      xbt_dynar_shift(d,&d2);
 823      xbt_test_assert2 (d1 == d2,
 824            "The retrieved value is not the same than the injected one at the end (%f!=%f)",
 825                    d1,d2);
 826    }
 827    xbt_dynar_free(&d);
 828    xbt_dynar_free(&d);
 829
 830
 831    xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest");
 832    d=xbt_dynar_new(sizeof(double),NULL);
 833    for (cpt=0; cpt< 5000; cpt++) {
 834      d1=(double)cpt;
 835      xbt_dynar_push(d,&d1);
 836    }
 837    for (cpt=2000; cpt< 4000; cpt++) {
 838      d1=(double)cpt;
 839      xbt_dynar_remove_at(d,2000,&d2);
 840      xbt_test_assert2 (d1 == d2,
 841            "Remove a bad value. Got %f, expected %f",
 842                d2,d1);
 843    }
 844    xbt_dynar_free(&d);
 845    xbt_dynar_free(&d);
 846 }
 847
 848
 849 /* doxygen_string_cruft */
 850
 851 /* The function we will use to free the data */
 852 static void free_string(void *d){
 853   free(*(void**)d);
 854 }
 855
 856 XBT_TEST_UNIT("string",test_dynar_string,"Dyars of strings") {
 857    xbt_dynar_t d;
 858    int cpt;
 859    char buf[1024];
 860    char *s1,*s2;
 861
 862    xbt_test_add0("==== Traverse the empty dynar");
 863    d=xbt_dynar_new(sizeof(char *),&free_string);
 864    xbt_dynar_foreach(d,cpt,s1){
 865      xbt_test_assert0(FALSE,
 866                   "Damnit, there is something in the empty dynar");
 867    }
 868    xbt_dynar_free(&d);
 869    xbt_dynar_free(&d);
 870
 871    xbt_test_add1("==== Push %d strings, set them again 3 times, shift them",NB_ELEM);
 872    /* Populate_str [doxygen cruft] */
 873    d=xbt_dynar_new(sizeof(char*),&free_string);
 874    /* 1. Populate the dynar */
 875    for (cpt=0; cpt< NB_ELEM; cpt++) {
 876      sprintf(buf,"%d",cpt);
 877      s1=strdup(buf);
 878      xbt_dynar_push(d,&s1);
 879    }
 880    for (cpt=0; cpt< NB_ELEM; cpt++) {
 881      sprintf(buf,"%d",cpt);
 882      s1=strdup(buf);
 883      xbt_dynar_replace(d,cpt,&s1);
 884    }
 885    for (cpt=0; cpt< NB_ELEM; cpt++) {
 886      sprintf(buf,"%d",cpt);
 887      s1=strdup(buf);
 888      xbt_dynar_replace(d,cpt,&s1);
 889    }
 890    for (cpt=0; cpt< NB_ELEM; cpt++) {
 891      sprintf(buf,"%d",cpt);
 892      s1=strdup(buf);
 893      xbt_dynar_replace(d,cpt,&s1);
 894    }
 895    for (cpt=0; cpt< NB_ELEM; cpt++) {
 896      sprintf(buf,"%d",cpt);
 897      xbt_dynar_shift(d,&s2);
 898      xbt_test_assert2 (!strcmp(buf,s2),
 899             "The retrieved value is not the same than the injected one (%s!=%s)",
 900                    buf,s2);
 901      free(s2);
 902    }
 903    xbt_dynar_free(&d);
 904    xbt_dynar_free(&d);
 905
 906
 907    xbt_test_add1("==== Unshift, traverse and pop %d strings",NB_ELEM);
 908    d=xbt_dynar_new(sizeof(char**),&free_string);
 909    for (cpt=0; cpt< NB_ELEM; cpt++) {
 910      sprintf(buf,"%d",cpt);
 911      s1=strdup(buf);
 912      xbt_dynar_unshift(d,&s1);
 913    }
 914    /* 2. Traverse the dynar with the macro */
 915    xbt_dynar_foreach(d,cpt,s1) {
 916      sprintf(buf,"%d",NB_ELEM - cpt -1);
 917      xbt_test_assert2 (!strcmp(buf,s1),
 918            "The retrieved value is not the same than the injected one (%s!=%s)",
 919                buf,s1);
 920    }
 921    /* 3. Traverse the dynar with the macro */
 922    for (cpt=0; cpt< NB_ELEM; cpt++) {
 923      sprintf(buf,"%d",cpt);
 924      xbt_dynar_pop(d,&s2);
 925      xbt_test_assert2 (!strcmp(buf,s2),
 926            "The retrieved value is not the same than the injected one (%s!=%s)",
 927                buf,s2);
 928      free(s2);
 929    }
 930    /* 4. Free the resources */
 931    xbt_dynar_free(&d);
 932    xbt_dynar_free(&d);
 933
 934
 935    xbt_test_add2("==== Push %d strings, insert %d strings in the middle, shift everything",NB_ELEM,NB_ELEM/5);
 936    d=xbt_dynar_new(sizeof(char*),&free_string);
 937    for (cpt=0; cpt< NB_ELEM; cpt++) {
 938      sprintf(buf,"%d",cpt);
 939      s1=strdup(buf);
 940      xbt_dynar_push(d,&s1);
 941    }
 942    for (cpt=0; cpt< NB_ELEM/5; cpt++) {
 943      sprintf(buf,"%d",cpt);
 944      s1=strdup(buf);
 945      xbt_dynar_insert_at(d,NB_ELEM/2,&s1);
 946    }
 947
 948    for (cpt=0; cpt< NB_ELEM/2; cpt++) {
 949      sprintf(buf,"%d",cpt);
 950      xbt_dynar_shift(d,&s2);
 951      xbt_test_assert2(!strcmp(buf,s2),
 952            "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
 953                buf,s2);
 954       free(s2);
 955    }
 956    for (cpt=(NB_ELEM/5)-1; cpt>=0; cpt--) {
 957      sprintf(buf,"%d",cpt);
 958      xbt_dynar_shift(d,&s2);
 959      xbt_test_assert2 (!strcmp(buf,s2),
 960            "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
 961                buf,s2);
 962      free(s2);
 963    }
 964    for (cpt=NB_ELEM/2; cpt< NB_ELEM; cpt++) {
 965      sprintf(buf,"%d",cpt);
 966      xbt_dynar_shift(d,&s2);
 967      xbt_test_assert2 (!strcmp(buf,s2),
 968            "The retrieved value is not the same than the injected one at the end (%s!=%s)",
 969                buf,s2);
 970      free(s2);
 971    }
 972    xbt_dynar_free(&d);
 973    xbt_dynar_free(&d);
 974
 975
 976    xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest",NB_ELEM,2*(NB_ELEM/5),4*(NB_ELEM/5));
 977    d=xbt_dynar_new(sizeof(char*),&free_string);
 978    for (cpt=0; cpt< NB_ELEM; cpt++) {
 979      sprintf(buf,"%d",cpt);
 980      s1=strdup(buf);
 981      xbt_dynar_push(d,&s1);
 982    }
 983    for (cpt=2*(NB_ELEM/5); cpt< 4*(NB_ELEM/5); cpt++) {
 984      sprintf(buf,"%d",cpt);
 985      xbt_dynar_remove_at(d,2*(NB_ELEM/5),&s2);
 986      xbt_test_assert2(!strcmp(buf,s2),
 987                   "Remove a bad value. Got %s, expected %s",
 988                   s2,buf);
 989       free(s2);
 990    }
 991    xbt_dynar_free(&d); /* end_of_doxygen */
 992 }
 993 #endif /* SIMGRID_TEST */