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(xbt_dyn,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     if (dynar->elmsize <= SIZEOF_MAX) {
 378        char elm[SIZEOF_MAX];
 379        _xbt_dynar_get_elm(elm, dynar, idx);
 380        (*dynar->free_f)(elm);
 381     } else {
 382        char *elm=malloc(dynar->elmsize);
 383        _xbt_dynar_get_elm(elm, dynar, idx);
 384        (*dynar->free_f)(elm);
 385        free(elm);
 386     }
 387   }
 388
 389   nb_shift =  dynar->used-1 - idx;
 390   offset   =  nb_shift * dynar->elmsize;
 391
 392   memmove(_xbt_dynar_elm(dynar, idx),
 393           _xbt_dynar_elm(dynar, idx+1),
 394           offset);
 395
 396   dynar->used--;
 397 }
 398
 399 /** @brief Returns the position of the element in the dynar
 400  *
 401  * Raises not_found_error if not found.
 402  */
 403 int
 404 xbt_dynar_search(xbt_dynar_t  const dynar,
 405                  void        *const elem) {
 406   int it;
 407
 408   for (it=0; it< dynar->size; it++)
 409     if (!memcmp(_xbt_dynar_elm(dynar, it),elem,dynar->elmsize))
 410       return it;
 411
 412   THROW2(not_found_error,0,"Element %p not part of dynar %p",elem,dynar);
 413 }
 414
 415 /** @brief Returns a boolean indicating whether the element is part of the dynar */
 416 int
 417 xbt_dynar_member(xbt_dynar_t  const dynar,
 418                  void        *const elem) {
 419
 420   xbt_ex_t e;
 421
 422   TRY {
 423      xbt_dynar_search(dynar,elem);
 424   } CATCH(e) {
 425      if (e.category == not_found_error) {
 426         xbt_ex_free(e);
 427         return 0;
 428      }
 429      RETHROW;
 430   }
 431   return 1;
 432 }
 433
 434 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 435  *
 436  * You can then use regular affectation to set its value instead of relying
 437  * on the slow memcpy. This is what xbt_dynar_push_as() does.
 438  */
 439 void *
 440 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
 441   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 442 }
 443
 444 /** @brief Add an element at the end of the dynar */
 445 void
 446 xbt_dynar_push(xbt_dynar_t  const dynar,
 447                 const void   * const src) {
 448   /* sanity checks done by insert_at */
 449   xbt_dynar_insert_at(dynar, dynar->used, src);
 450 }
 451
 452 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 453  *
 454  * You can then use regular affectation to set its value instead of relying
 455  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
 456  */
 457 void *
 458 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 459
 460   __check_populated_dynar(dynar);
 461   DEBUG1("Pop %p",(void*)dynar);
 462   dynar->used--;
 463   return _xbt_dynar_elm(dynar,dynar->used);
 464 }
 465
 466 /** @brief Get and remove the last element of the dynar */
 467 void
 468 xbt_dynar_pop(xbt_dynar_t  const dynar,
 469               void         * const dst) {
 470
 471   /* sanity checks done by remove_at */
 472   DEBUG1("Pop %p",(void*)dynar);
 473   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 474 }
 475
 476 /** @brief Add an element at the begining of the dynar.
 477  *
 478  * This is less efficient than xbt_dynar_push()
 479  */
 480 void
 481 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 482                    const void   * const src) {
 483
 484   /* sanity checks done by insert_at */
 485   xbt_dynar_insert_at(dynar, 0, src);
 486 }
 487
 488 /** @brief Get and remove the first element of the dynar.
 489  *
 490  * This is less efficient than xbt_dynar_pop()
 491  */
 492 void
 493 xbt_dynar_shift(xbt_dynar_t  const dynar,
 494                  void         * const dst) {
 495
 496   /* sanity checks done by remove_at */
 497   xbt_dynar_remove_at(dynar, 0, dst);
 498 }
 499
 500 /** @brief Apply a function to each member of a dynar
 501  *
 502  * The mapped function may change the value of the element itself,
 503  * but should not mess with the structure of the dynar.
 504  */
 505 void
 506 xbt_dynar_map(const xbt_dynar_t  dynar,
 507                void_f_pvoid_t     * const op) {
 508
 509   __sanity_check_dynar(dynar);
 510
 511   {
 512     char         elm[SIZEOF_MAX];
 513     const unsigned long used = dynar->used;
 514     unsigned long       i    = 0;
 515
 516     for (i = 0; i < used; i++) {
 517       _xbt_dynar_get_elm(elm, dynar, i);
 518       op(elm);
 519     }
 520   }
 521 }
 522
 523 /** @brief Put the cursor at the begining of the dynar.
 524  *
 525  * Actually, the cursor is set one step before the begining, so that you
 526  * can iterate over the dynar with a for loop.
 527  */
 528 void
 529 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 530                        int        * const cursor) {
 531
 532   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 533   *cursor = 0;
 534 }
 535
 536 /** @brief Move the cursor to the next value */
 537 void
 538 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 539                        int        * const cursor) {
 540
 541   (*cursor)++;
 542 }
 543
 544 /** @brief Get the data currently pointed by the cursor */
 545 int
 546 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 547                       int                * const cursor,
 548                       void               * const dst) {
 549
 550   __sanity_check_dynar(dynar);
 551   {
 552
 553     const int idx = *cursor;
 554
 555     if (idx >= dynar->used) {
 556       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 557       return FALSE;
 558     }
 559     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 560
 561     _xbt_dynar_get_elm(dst, dynar, idx);
 562   }
 563   return TRUE;
 564
 565 }
 566
 567 /** @brief Removes and free the entry pointed by the cursor
 568  *
 569  * This function can be used while traversing without problem.
 570  */
 571 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 572                           int          * const cursor) {
 573   void *dst;
 574
 575   if (dynar->elmsize > sizeof(void*)) {
 576     DEBUG0("Elements too big to fit into a pointer");
 577     if (dynar->free_f) {
 578       dst=xbt_malloc(dynar->elmsize);
 579       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 580       (dynar->free_f)(dst);
 581       free(dst);
 582     } else {
 583       DEBUG0("Ok, we dont care about the element without free function");
 584       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 585     }
 586
 587   } else {
 588     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 589     if (dynar->free_f)
 590       (dynar->free_f)(dst);
 591   }
 592 }
 593
 594 #ifdef SIMGRID_TEST
 595
 596 #define NB_ELEM 5000
 597
 598 XBT_TEST_SUITE("dynar","Dynar data container");
 599 XBT_LOG_EXTERNAL_CATEGORY(xbt_dyn);
 600 XBT_LOG_DEFAULT_CATEGORY(xbt_dyn);
 601
 602 XBT_TEST_UNIT("int",test_dynar_int,"Dyars of integers") {
 603    /* Vars_decl [doxygen cruft] */
 604    xbt_dynar_t d;
 605    int i,cpt,cursor;
 606    int *iptr;
 607
 608    xbt_test_add0("==== Traverse the empty dynar");
 609    d=xbt_dynar_new(sizeof(int),NULL);
 610    xbt_dynar_foreach(d,cursor,i){
 611      xbt_assert0(0,"Damnit, there is something in the empty dynar");
 612    }
 613    xbt_dynar_free(&d);
 614    xbt_dynar_free(&d);
 615
 616    xbt_test_add1("==== Push %d int, set them again 3 times, traverse them, shift them",
 617         NB_ELEM);
 618    /* Populate_ints [doxygen cruft] */
 619    /* 1. Populate the dynar */
 620    d=xbt_dynar_new(sizeof(int),NULL);
 621    for (cpt=0; cpt< NB_ELEM; cpt++) {
 622      xbt_dynar_push_as(d,int,cpt); /* This is faster (and possible only with scalars) */
 623      /* xbt_dynar_push(d,&cpt);       This would also work */
 624      xbt_test_log2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 625    }
 626
 627    /* 2. Traverse manually the dynar */
 628    for (cursor=0; cursor< NB_ELEM; cursor++) {
 629      iptr=xbt_dynar_get_ptr(d,cursor);
 630      xbt_test_assert2(cursor == *iptr,
 631                       "The retrieved value is not the same than the injected one (%d!=%d)",
 632                       cursor,cpt);
 633    }
 634
 635    /* 3. Traverse the dynar using the neat macro to that extend */
 636    xbt_dynar_foreach(d,cursor,cpt){
 637      xbt_test_assert2(cursor == cpt,
 638                       "The retrieved value is not the same than the injected one (%d!=%d)",
 639                       cursor,cpt);
 640    }
 641    /* end_of_traversal */
 642
 643    for (cpt=0; cpt< NB_ELEM; cpt++)
 644      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 645
 646    for (cpt=0; cpt< NB_ELEM; cpt++)
 647      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 648 /*     xbt_dynar_set(d,cpt,&cpt);*/
 649
 650    for (cpt=0; cpt< NB_ELEM; cpt++)
 651      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 652
 653    cpt=0;
 654    xbt_dynar_foreach(d,cursor,i){
 655      xbt_test_assert2(i == cpt,
 656                       "The retrieved value is not the same than the injected one (%d!=%d)",
 657                       i,cpt);
 658      cpt++;
 659    }
 660    xbt_test_assert2(cpt == NB_ELEM,
 661                     "Cannot retrieve my %d values. Last got one is %d",
 662                     NB_ELEM, cpt);
 663
 664    /* shifting [doxygen cruft] */
 665    /* 4. Shift all the values */
 666    for (cpt=0; cpt< NB_ELEM; cpt++) {
 667      xbt_dynar_shift(d,&i);
 668      xbt_test_assert2(i == cpt,
 669                       "The retrieved value is not the same than the injected one (%d!=%d)",
 670                       i,cpt);
 671      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 672    }
 673
 674    /* 5. Free the resources */
 675    xbt_dynar_free(&d);
 676    xbt_dynar_free(&d);
 677
 678
 679    xbt_test_add1("==== Unshift/pop %d int",NB_ELEM);
 680    d=xbt_dynar_new(sizeof(int),NULL);
 681    for (cpt=0; cpt< NB_ELEM; cpt++) {
 682      xbt_dynar_unshift(d,&cpt);
 683      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 684    }
 685    for (cpt=0; cpt< NB_ELEM; cpt++) {
 686      i=xbt_dynar_pop_as(d,int);
 687      xbt_test_assert2(i == cpt,
 688                       "The retrieved value is not the same than the injected one (%d!=%d)",
 689                       i,cpt);
 690      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 691    }
 692    xbt_dynar_free(&d);
 693    xbt_dynar_free(&d);
 694
 695
 696    xbt_test_add1("==== Push %d int, insert 1000 int in the middle, shift everything",NB_ELEM);
 697    d=xbt_dynar_new(sizeof(int),NULL);
 698    for (cpt=0; cpt< NB_ELEM; cpt++) {
 699      xbt_dynar_push_as(d,int,cpt);
 700      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 701    }
 702    for (cpt=0; cpt< 1000; cpt++) {
 703      xbt_dynar_insert_at_as(d,2500,int,cpt);
 704      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 705    }
 706
 707    for (cpt=0; cpt< 2500; 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 at the begining (%d!=%d)",
 711                i,cpt);
 712      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 713    }
 714    for (cpt=999; cpt>=0; cpt--) {
 715      xbt_dynar_shift(d,&i);
 716      xbt_test_assert2(i == cpt,
 717            "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
 718                       i,cpt);
 719    }
 720    for (cpt=2500; cpt< NB_ELEM; cpt++) {
 721      xbt_dynar_shift(d,&i);
 722       xbt_test_assert2(i == cpt,
 723            "The retrieved value is not the same than the injected one at the end (%d!=%d)",
 724                        i,cpt);
 725    }
 726    xbt_dynar_free(&d);
 727    xbt_dynar_free(&d);
 728
 729
 730    xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest",NB_ELEM);
 731    d=xbt_dynar_new(sizeof(int),NULL);
 732    for (cpt=0; cpt< NB_ELEM; cpt++)
 733      xbt_dynar_push_as(d,int,cpt);
 734
 735    for (cpt=2000; cpt< 4000; cpt++) {
 736      xbt_dynar_remove_at(d,2000,&i);
 737      xbt_test_assert2(i == cpt,
 738                       "Remove a bad value. Got %d, expected %d",
 739                       i,cpt);
 740      DEBUG2("remove %d, length=%lu",cpt, xbt_dynar_length(d));
 741    }
 742    xbt_dynar_free(&d);
 743    xbt_dynar_free(&d);
 744 }
 745
 746 XBT_TEST_UNIT("double",test_dynar_double,"Dyars of doubles") {
 747    xbt_dynar_t d;
 748    int cpt,cursor;
 749    double d1,d2;
 750
 751    xbt_test_add0("==== Traverse the empty dynar");
 752    d=xbt_dynar_new(sizeof(int),NULL);
 753    xbt_dynar_foreach(d,cursor,cpt){
 754      xbt_test_assert0(FALSE,
 755              "Damnit, there is something in the empty dynar");
 756    }
 757    xbt_dynar_free(&d);
 758    xbt_dynar_free(&d);
 759
 760    xbt_test_add0("==== Push/shift 5000 doubles");
 761    d=xbt_dynar_new(sizeof(double),NULL);
 762    for (cpt=0; cpt< 5000; cpt++) {
 763      d1=(double)cpt;
 764      xbt_dynar_push(d,&d1);
 765    }
 766    xbt_dynar_foreach(d,cursor,d2){
 767      d1=(double)cursor;
 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    for (cpt=0; cpt< 5000; cpt++) {
 773      d1=(double)cpt;
 774      xbt_dynar_shift(d,&d2);
 775      xbt_test_assert2(d1 == d2,
 776            "The retrieved value is not the same than the injected one (%f!=%f)",
 777                   d1,d2);
 778    }
 779    xbt_dynar_free(&d);
 780    xbt_dynar_free(&d);
 781
 782
 783    xbt_test_add0("==== Unshift/pop 5000 doubles");
 784    d=xbt_dynar_new(sizeof(double),NULL);
 785    for (cpt=0; cpt< 5000; cpt++) {
 786      d1=(double)cpt;
 787      xbt_dynar_unshift(d,&d1);
 788    }
 789    for (cpt=0; cpt< 5000; cpt++) {
 790      d1=(double)cpt;
 791      xbt_dynar_pop(d,&d2);
 792      xbt_test_assert2 (d1 == d2,
 793            "The retrieved value is not the same than the injected one (%f!=%f)",
 794                    d1,d2);
 795    }
 796    xbt_dynar_free(&d);
 797    xbt_dynar_free(&d);
 798
 799
 800
 801    xbt_test_add0("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
 802    d=xbt_dynar_new(sizeof(double),NULL);
 803    for (cpt=0; cpt< 5000; cpt++) {
 804      d1=(double)cpt;
 805      xbt_dynar_push(d,&d1);
 806    }
 807    for (cpt=0; cpt< 1000; cpt++) {
 808      d1=(double)cpt;
 809      xbt_dynar_insert_at(d,2500,&d1);
 810    }
 811
 812    for (cpt=0; cpt< 2500; cpt++) {
 813      d1=(double)cpt;
 814      xbt_dynar_shift(d,&d2);
 815      xbt_test_assert2(d1 == d2,
 816            "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
 817                   d1,d2);
 818      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 819    }
 820    for (cpt=999; cpt>=0; 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 in the middle (%f!=%f)",
 825                    d1,d2);
 826    }
 827    for (cpt=2500; cpt< 5000; cpt++) {
 828      d1=(double)cpt;
 829      xbt_dynar_shift(d,&d2);
 830      xbt_test_assert2 (d1 == d2,
 831            "The retrieved value is not the same than the injected one at the end (%f!=%f)",
 832                    d1,d2);
 833    }
 834    xbt_dynar_free(&d);
 835    xbt_dynar_free(&d);
 836
 837
 838    xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest");
 839    d=xbt_dynar_new(sizeof(double),NULL);
 840    for (cpt=0; cpt< 5000; cpt++) {
 841      d1=(double)cpt;
 842      xbt_dynar_push(d,&d1);
 843    }
 844    for (cpt=2000; cpt< 4000; cpt++) {
 845      d1=(double)cpt;
 846      xbt_dynar_remove_at(d,2000,&d2);
 847      xbt_test_assert2 (d1 == d2,
 848            "Remove a bad value. Got %f, expected %f",
 849                d2,d1);
 850    }
 851    xbt_dynar_free(&d);
 852    xbt_dynar_free(&d);
 853 }
 854
 855
 856 /* doxygen_string_cruft */
 857
 858 /* The function we will use to free the data */
 859 static void free_string(void *d){
 860   free(*(void**)d);
 861 }
 862
 863 XBT_TEST_UNIT("string",test_dynar_string,"Dyars of strings") {
 864    xbt_dynar_t d;
 865    int cpt;
 866    char buf[1024];
 867    char *s1,*s2;
 868
 869    xbt_test_add0("==== Traverse the empty dynar");
 870    d=xbt_dynar_new(sizeof(char *),&free_string);
 871    xbt_dynar_foreach(d,cpt,s1){
 872      xbt_test_assert0(FALSE,
 873                   "Damnit, there is something in the empty dynar");
 874    }
 875    xbt_dynar_free(&d);
 876    xbt_dynar_free(&d);
 877
 878    xbt_test_add1("==== Push %d strings, set them again 3 times, shift them",NB_ELEM);
 879    /* Populate_str [doxygen cruft] */
 880    d=xbt_dynar_new(sizeof(char*),&free_string);
 881    /* 1. Populate the dynar */
 882    for (cpt=0; cpt< NB_ELEM; cpt++) {
 883      sprintf(buf,"%d",cpt);
 884      s1=strdup(buf);
 885      xbt_dynar_push(d,&s1);
 886    }
 887    for (cpt=0; cpt< NB_ELEM; cpt++) {
 888      sprintf(buf,"%d",cpt);
 889      s1=strdup(buf);
 890      xbt_dynar_replace(d,cpt,&s1);
 891    }
 892    for (cpt=0; cpt< NB_ELEM; cpt++) {
 893      sprintf(buf,"%d",cpt);
 894      s1=strdup(buf);
 895      xbt_dynar_replace(d,cpt,&s1);
 896    }
 897    for (cpt=0; cpt< NB_ELEM; cpt++) {
 898      sprintf(buf,"%d",cpt);
 899      s1=strdup(buf);
 900      xbt_dynar_replace(d,cpt,&s1);
 901    }
 902    for (cpt=0; cpt< NB_ELEM; cpt++) {
 903      sprintf(buf,"%d",cpt);
 904      xbt_dynar_shift(d,&s2);
 905      xbt_test_assert2 (!strcmp(buf,s2),
 906             "The retrieved value is not the same than the injected one (%s!=%s)",
 907                    buf,s2);
 908      free(s2);
 909    }
 910    xbt_dynar_free(&d);
 911    xbt_dynar_free(&d);
 912
 913
 914    xbt_test_add1("==== Unshift, traverse and pop %d strings",NB_ELEM);
 915    d=xbt_dynar_new(sizeof(char**),&free_string);
 916    for (cpt=0; cpt< NB_ELEM; cpt++) {
 917      sprintf(buf,"%d",cpt);
 918      s1=strdup(buf);
 919      xbt_dynar_unshift(d,&s1);
 920    }
 921    /* 2. Traverse the dynar with the macro */
 922    xbt_dynar_foreach(d,cpt,s1) {
 923      sprintf(buf,"%d",NB_ELEM - cpt -1);
 924      xbt_test_assert2 (!strcmp(buf,s1),
 925            "The retrieved value is not the same than the injected one (%s!=%s)",
 926                buf,s1);
 927    }
 928    /* 3. Traverse the dynar with the macro */
 929    for (cpt=0; cpt< NB_ELEM; cpt++) {
 930      sprintf(buf,"%d",cpt);
 931      xbt_dynar_pop(d,&s2);
 932      xbt_test_assert2 (!strcmp(buf,s2),
 933            "The retrieved value is not the same than the injected one (%s!=%s)",
 934                buf,s2);
 935      free(s2);
 936    }
 937    /* 4. Free the resources */
 938    xbt_dynar_free(&d);
 939    xbt_dynar_free(&d);
 940
 941
 942    xbt_test_add2("==== Push %d strings, insert %d strings in the middle, shift everything",NB_ELEM,NB_ELEM/5);
 943    d=xbt_dynar_new(sizeof(char*),&free_string);
 944    for (cpt=0; cpt< NB_ELEM; cpt++) {
 945      sprintf(buf,"%d",cpt);
 946      s1=strdup(buf);
 947      xbt_dynar_push(d,&s1);
 948    }
 949    for (cpt=0; cpt< NB_ELEM/5; cpt++) {
 950      sprintf(buf,"%d",cpt);
 951      s1=strdup(buf);
 952      xbt_dynar_insert_at(d,NB_ELEM/2,&s1);
 953    }
 954
 955    for (cpt=0; cpt< NB_ELEM/2; cpt++) {
 956      sprintf(buf,"%d",cpt);
 957      xbt_dynar_shift(d,&s2);
 958      xbt_test_assert2(!strcmp(buf,s2),
 959            "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
 960                buf,s2);
 961       free(s2);
 962    }
 963    for (cpt=(NB_ELEM/5)-1; cpt>=0; cpt--) {
 964      sprintf(buf,"%d",cpt);
 965      xbt_dynar_shift(d,&s2);
 966      xbt_test_assert2 (!strcmp(buf,s2),
 967            "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
 968                buf,s2);
 969      free(s2);
 970    }
 971    for (cpt=NB_ELEM/2; cpt< NB_ELEM; cpt++) {
 972      sprintf(buf,"%d",cpt);
 973      xbt_dynar_shift(d,&s2);
 974      xbt_test_assert2 (!strcmp(buf,s2),
 975            "The retrieved value is not the same than the injected one at the end (%s!=%s)",
 976                buf,s2);
 977      free(s2);
 978    }
 979    xbt_dynar_free(&d);
 980    xbt_dynar_free(&d);
 981
 982
 983    xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest",NB_ELEM,2*(NB_ELEM/5),4*(NB_ELEM/5));
 984    d=xbt_dynar_new(sizeof(char*),&free_string);
 985    for (cpt=0; cpt< NB_ELEM; cpt++) {
 986      sprintf(buf,"%d",cpt);
 987      s1=strdup(buf);
 988      xbt_dynar_push(d,&s1);
 989    }
 990    for (cpt=2*(NB_ELEM/5); cpt< 4*(NB_ELEM/5); cpt++) {
 991      sprintf(buf,"%d",cpt);
 992      xbt_dynar_remove_at(d,2*(NB_ELEM/5),&s2);
 993      xbt_test_assert2(!strcmp(buf,s2),
 994                   "Remove a bad value. Got %s, expected %s",
 995                   s2,buf);
 996       free(s2);
 997    }
 998    xbt_dynar_free(&d); /* end_of_doxygen */
 999 }
1000 #endif /* SIMGRID_TEST */