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/dynar.h"
  15 #include <sys/types.h>
  16
  17 #include "xbt/dynar_private.h" /* type definition, which we share with the
  18                                   code in charge of sending this across the net */
  19
  20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
  21
  22
  23 #define __sanity_check_dynar(dynar)       \
  24            xbt_assert0(dynar,           \
  25                         "dynar is NULL")
  26 #define __sanity_check_idx(idx)                \
  27            xbt_assert1(idx >= 0,             \
  28                         "dynar idx(=%d) < 0", \
  29                         (int) (idx))
  30 #define __check_inbound_idx(dynar, idx)                                                \
  31            xbt_assert2(idx < dynar->used,                                             \
  32                         "dynar is not that long. You asked %d, but it's only %lu long", \
  33                         (int) (idx), (unsigned long) dynar->used)
  34 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
  35            xbt_assert2(idx <= dynar->used,                                            \
  36                         "dynar is not that long. You asked %d, but it's only %lu long", \
  37                         (int) (idx), (unsigned long) dynar->used)
  38 #define __check_populated_dynar(dynar)            \
  39            xbt_assert1(dynar->used,              \
  40                         "dynar %p contains nothing",(void*)dynar)
  41
  42 static _XBT_INLINE
  43 void _xbt_clear_mem(void * const ptr,
  44                      const unsigned long length) {
  45   memset(ptr, 0, length);
  46 }
  47
  48 static _XBT_INLINE
  49 void
  50 _xbt_dynar_expand(xbt_dynar_t const dynar,
  51                    const int          nb) {
  52   const unsigned long old_size    = dynar->size;
  53
  54   if (nb > old_size) {
  55     char * const old_data    = (char *) dynar->data;
  56
  57     const unsigned long elmsize     = dynar->elmsize;
  58     const unsigned long old_length  = old_size*elmsize;
  59
  60     const unsigned long used        = dynar->used;
  61     const unsigned long used_length = used*elmsize;
  62
  63     const unsigned long new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
  64     const unsigned long new_length  = new_size*elmsize;
  65     char * const new_data    = (char *) xbt_malloc0(elmsize*new_size);
  66
  67     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
  68
  69     if (old_data) {
  70       memcpy(new_data, old_data, used_length);
  71       _xbt_clear_mem(old_data, old_length);
  72       free(old_data);
  73     }
  74
  75     _xbt_clear_mem(new_data + used_length, new_length - used_length);
  76
  77     dynar->size = new_size;
  78     dynar->data = new_data;
  79   }
  80 }
  81
  82 static _XBT_INLINE
  83 void *
  84 _xbt_dynar_elm(const xbt_dynar_t  dynar,
  85                 const unsigned long idx) {
  86   char * const data    = (char*) dynar->data;
  87   const unsigned long elmsize = dynar->elmsize;
  88
  89   return data + idx*elmsize;
  90 }
  91
  92 static _XBT_INLINE
  93 void
  94 _xbt_dynar_get_elm(void  * const       dst,
  95                     const xbt_dynar_t  dynar,
  96                     const unsigned long idx) {
  97   void * const elm     = _xbt_dynar_elm(dynar, idx);
  98   const unsigned long elmsize = dynar->elmsize;
  99
 100   memcpy(dst, elm, 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 retrive
 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,
 247            const int          idx) {
 248
 249   __sanity_check_dynar(dynar);
 250   __sanity_check_idx(idx);
 251   __check_inbound_idx(dynar, idx);
 252
 253   return _xbt_dynar_elm(dynar, idx);
 254 }
 255
 256 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
 257  *
 258  * \param dynar information dealer
 259  * \param idx index of the slot we want to modify
 260  * \param src What will be feeded to the dynar
 261  *
 262  * If you want to free the previous content, use xbt_dynar_replace().
 263  */
 264 void
 265 xbt_dynar_set(xbt_dynar_t         dynar,
 266                const int            idx,
 267                const void   * const src) {
 268
 269   __sanity_check_dynar(dynar);
 270   __sanity_check_idx(idx);
 271
 272   _xbt_dynar_expand(dynar, idx+1);
 273
 274   if (idx >= dynar->used) {
 275     dynar->used = idx+1;
 276   }
 277
 278   _xbt_dynar_put_elm(dynar, idx, src);
 279 }
 280
 281 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
 282  *
 283  * \param dynar
 284  * \param idx
 285  * \param object
 286  *
 287  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 288  * free the previous value at this position. If you don't want to free the
 289  * previous content, use xbt_dynar_set().
 290  */
 291 void
 292 xbt_dynar_replace(xbt_dynar_t         dynar,
 293                    const int            idx,
 294                    const void   * const object) {
 295
 296   __sanity_check_dynar(dynar);
 297   __sanity_check_idx(idx);
 298
 299   if (idx < dynar->used && dynar->free_f) {
 300     void * const old_object = _xbt_dynar_elm(dynar, idx);
 301
 302     dynar->free_f(old_object);
 303   }
 304
 305   xbt_dynar_set(dynar, idx, object);
 306 }
 307
 308 /** @brief Make room for a new element, and return a pointer to it
 309  *
 310  * You can then use regular affectation to set its value instead of relying
 311  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
 312  */
 313 void *
 314 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
 315                         const int            idx) {
 316
 317   __sanity_check_dynar(dynar);
 318   __sanity_check_idx(idx);
 319   __check_sloppy_inbound_idx(dynar, idx);
 320
 321   {
 322     const unsigned long old_used = dynar->used;
 323     const unsigned long new_used = old_used + 1;
 324
 325     _xbt_dynar_expand(dynar, new_used);
 326
 327     {
 328       const unsigned long nb_shift =  old_used - idx;
 329
 330       if (nb_shift)
 331          memmove(_xbt_dynar_elm(dynar, idx+1),
 332                  _xbt_dynar_elm(dynar, idx),
 333                  nb_shift * dynar->elmsize);
 334     }
 335
 336     dynar->used = new_used;
 337     return _xbt_dynar_elm(dynar,idx);
 338   }
 339 }
 340
 341 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
 342  *
 343  * Set the Nth element of a dynar, expanding the dynar if needed, and
 344  * moving the previously existing value and all subsequent ones to one
 345  * position right in the dynar.
 346  */
 347 void
 348 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
 349                     const int            idx,
 350                     const void   * const src) {
 351
 352   /* checks done in xbt_dynar_insert_at_ptr */
 353   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
 354          src,
 355          dynar->elmsize);
 356 }
 357
 358 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 359  *
 360  * Get the Nth element of a dynar, removing it from the dynar and moving
 361  * all subsequent values to one position left in the dynar.
 362  */
 363 void
 364 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
 365                      const int            idx,
 366                      void         * const object) {
 367
 368   unsigned long nb_shift;
 369   unsigned long offset;
 370
 371   __sanity_check_dynar(dynar);
 372   __sanity_check_idx(idx);
 373   __check_inbound_idx(dynar, idx);
 374
 375   if (object) {
 376     _xbt_dynar_get_elm(object, dynar, idx);
 377   } else if (dynar->free_f) {
 378     char elm[SIZEOF_MAX];
 379     _xbt_dynar_get_elm(elm, dynar, idx);
 380     (*dynar->free_f)(elm);
 381   }
 382
 383   nb_shift =  dynar->used-1 - idx;
 384   offset   =  nb_shift * dynar->elmsize;
 385
 386   memmove(_xbt_dynar_elm(dynar, idx),
 387           _xbt_dynar_elm(dynar, idx+1),
 388           offset);
 389
 390   dynar->used--;
 391 }
 392
 393 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 394  *
 395  * You can then use regular affectation to set its value instead of relying
 396  * on the slow memcpy. This is what xbt_dynar_push_as() does.
 397  */
 398 void *
 399 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
 400   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 401 }
 402
 403 /** @brief Add an element at the end of the dynar */
 404 void
 405 xbt_dynar_push(xbt_dynar_t  const dynar,
 406                 const void   * const src) {
 407   /* sanity checks done by insert_at */
 408   xbt_dynar_insert_at(dynar, dynar->used, src);
 409 }
 410
 411 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 412  *
 413  * You can then use regular affectation to set its value instead of relying
 414  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
 415  */
 416 void *
 417 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 418
 419   __check_populated_dynar(dynar);
 420   DEBUG1("Pop %p",(void*)dynar);
 421   dynar->used--;
 422   return _xbt_dynar_elm(dynar,dynar->used);
 423 }
 424
 425 /** @brief Get and remove the last element of the dynar */
 426 void
 427 xbt_dynar_pop(xbt_dynar_t  const dynar,
 428               void         * const dst) {
 429
 430   /* sanity checks done by remove_at */
 431   DEBUG1("Pop %p",(void*)dynar);
 432   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 433 }
 434
 435 /** @brief Add an element at the begining of the dynar.
 436  *
 437  * This is less efficient than xbt_dynar_push()
 438  */
 439 void
 440 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 441                    const void   * const src) {
 442
 443   /* sanity checks done by insert_at */
 444   xbt_dynar_insert_at(dynar, 0, src);
 445 }
 446
 447 /** @brief Get and remove the first element of the dynar.
 448  *
 449  * This is less efficient than xbt_dynar_pop()
 450  */
 451 void
 452 xbt_dynar_shift(xbt_dynar_t  const dynar,
 453                  void         * const dst) {
 454
 455   /* sanity checks done by remove_at */
 456   xbt_dynar_remove_at(dynar, 0, dst);
 457 }
 458
 459 /** @brief Apply a function to each member of a dynar
 460  *
 461  * The mapped function may change the value of the element itself,
 462  * but should not mess with the structure of the dynar.
 463  */
 464 void
 465 xbt_dynar_map(const xbt_dynar_t  dynar,
 466                void_f_pvoid_t     * const op) {
 467
 468   __sanity_check_dynar(dynar);
 469
 470   {
 471     char         elm[SIZEOF_MAX];
 472     const unsigned long used = dynar->used;
 473     unsigned long       i    = 0;
 474
 475     for (i = 0; i < used; i++) {
 476       _xbt_dynar_get_elm(elm, dynar, i);
 477       op(elm);
 478     }
 479   }
 480 }
 481
 482 /** @brief Put the cursor at the begining of the dynar.
 483  *
 484  * Actually, the cursor is set one step before the begining, so that you
 485  * can iterate over the dynar with a for loop.
 486  */
 487 void
 488 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 489                        int        * const cursor) {
 490
 491   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 492   *cursor = 0;
 493 }
 494
 495 /** @brief Move the cursor to the next value */
 496 void
 497 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 498                        int        * const cursor) {
 499
 500   (*cursor)++;
 501 }
 502
 503 /** @brief Get the data currently pointed by the cursor */
 504 int
 505 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 506                       int                * const cursor,
 507                       void               * const dst) {
 508
 509   __sanity_check_dynar(dynar);
 510   {
 511
 512     const int idx = *cursor;
 513
 514     if (idx >= dynar->used) {
 515       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 516       return FALSE;
 517     }
 518     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 519
 520     _xbt_dynar_get_elm(dst, dynar, idx);
 521   }
 522   return TRUE;
 523
 524 }
 525
 526 /** @brief Removes and free the entry pointed by the cursor
 527  *
 528  * This function can be used while traversing without problem.
 529  */
 530 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 531                           int          * const cursor) {
 532   void *dst;
 533
 534   if (dynar->elmsize > sizeof(void*)) {
 535     DEBUG0("Elements too big to fit into a pointer");
 536     if (dynar->free_f) {
 537       dst=xbt_malloc(dynar->elmsize);
 538       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 539       (dynar->free_f)(dst);
 540       free(dst);
 541     } else {
 542       DEBUG0("Ok, we dont care about the element without free function");
 543       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 544     }
 545
 546   } else {
 547     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 548     if (dynar->free_f)
 549       (dynar->free_f)(dst);
 550   }
 551 }
 552
 553 #ifdef SIMGRID_TEST
 554
 555 #define NB_ELEM 5000
 556
 557 XBT_TEST_SUITE("dynar","Dynar data container");
 558 XBT_LOG_EXTERNAL_CATEGORY(dynar);
 559 XBT_LOG_DEFAULT_CATEGORY(dynar);
 560
 561 XBT_TEST_UNIT("int",test_dynar_int,"Dyars of integers") {
 562    /* Vars_decl [doxygen cruft] */
 563    xbt_dynar_t d;
 564    int i,cpt,cursor;
 565    int *iptr;
 566
 567    xbt_test_add0("==== Traverse the empty dynar");
 568    d=xbt_dynar_new(sizeof(int),NULL);
 569    xbt_dynar_foreach(d,cursor,i){
 570      xbt_assert0(0,"Damnit, there is something in the empty dynar");
 571    }
 572    xbt_dynar_free(&d);
 573    xbt_dynar_free(&d);
 574
 575    xbt_test_add1("==== Push %d int, set them again 3 times, traverse them, shift them",
 576         NB_ELEM);
 577    /* Populate_ints [doxygen cruft] */
 578    /* 1. Populate the dynar */
 579    d=xbt_dynar_new(sizeof(int),NULL);
 580    for (cpt=0; cpt< NB_ELEM; cpt++) {
 581      xbt_dynar_push_as(d,int,cpt); /* This is faster (and possible only with scalars) */
 582      /* xbt_dynar_push(d,&cpt);       This would also work */
 583      xbt_test_log2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 584    }
 585
 586    /* 2. Traverse manually the dynar */
 587    for (cursor=0; cursor< NB_ELEM; cursor++) {
 588      iptr=xbt_dynar_get_ptr(d,cursor);
 589      xbt_test_assert2(cursor == *iptr,
 590                       "The retrieved value is not the same than the injected one (%d!=%d)",
 591                       cursor,cpt);
 592    }
 593
 594    /* 3. Traverse the dynar using the neat macro to that extend */
 595    xbt_dynar_foreach(d,cursor,cpt){
 596      xbt_test_assert2(cursor == cpt,
 597                       "The retrieved value is not the same than the injected one (%d!=%d)",
 598                       cursor,cpt);
 599    }
 600    /* end_of_traversal */
 601
 602    for (cpt=0; cpt< NB_ELEM; cpt++)
 603      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 604
 605    for (cpt=0; cpt< NB_ELEM; cpt++)
 606      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 607 /*     xbt_dynar_set(d,cpt,&cpt);*/
 608
 609    for (cpt=0; cpt< NB_ELEM; cpt++)
 610      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
 611
 612    cpt=0;
 613    xbt_dynar_foreach(d,cursor,i){
 614      xbt_test_assert2(i == cpt,
 615                       "The retrieved value is not the same than the injected one (%d!=%d)",
 616                       i,cpt);
 617      cpt++;
 618    }
 619    xbt_test_assert2(cpt == NB_ELEM,
 620                     "Cannot retrieve my %d values. Last got one is %d",
 621                     NB_ELEM, cpt);
 622
 623    /* shifting [doxygen cruft] */
 624    /* 4. Shift all the values */
 625    for (cpt=0; cpt< NB_ELEM; cpt++) {
 626      xbt_dynar_shift(d,&i);
 627      xbt_test_assert2(i == cpt,
 628                       "The retrieved value is not the same than the injected one (%d!=%d)",
 629                       i,cpt);
 630      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 631    }
 632
 633    /* 5. Free the resources */
 634    xbt_dynar_free(&d);
 635    xbt_dynar_free(&d);
 636
 637
 638    xbt_test_add1("==== Unshift/pop %d int",NB_ELEM);
 639    d=xbt_dynar_new(sizeof(int),NULL);
 640    for (cpt=0; cpt< NB_ELEM; cpt++) {
 641      xbt_dynar_unshift(d,&cpt);
 642      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 643    }
 644    for (cpt=0; cpt< NB_ELEM; cpt++) {
 645      i=xbt_dynar_pop_as(d,int);
 646      xbt_test_assert2(i == cpt,
 647                       "The retrieved value is not the same than the injected one (%d!=%d)",
 648                       i,cpt);
 649      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 650    }
 651    xbt_dynar_free(&d);
 652    xbt_dynar_free(&d);
 653
 654
 655    xbt_test_add1("==== Push %d int, insert 1000 int in the middle, shift everything",NB_ELEM);
 656    d=xbt_dynar_new(sizeof(int),NULL);
 657    for (cpt=0; cpt< NB_ELEM; cpt++) {
 658      xbt_dynar_push_as(d,int,cpt);
 659      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 660    }
 661    for (cpt=0; cpt< 1000; cpt++) {
 662      xbt_dynar_insert_at_as(d,2500,int,cpt);
 663      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
 664    }
 665
 666    for (cpt=0; cpt< 2500; 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 at the begining (%d!=%d)",
 670                i,cpt);
 671      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 672    }
 673    for (cpt=999; cpt>=0; cpt--) {
 674      xbt_dynar_shift(d,&i);
 675      xbt_test_assert2(i == cpt,
 676            "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
 677                       i,cpt);
 678    }
 679    for (cpt=2500; cpt< NB_ELEM; cpt++) {
 680      xbt_dynar_shift(d,&i);
 681       xbt_test_assert2(i == cpt,
 682            "The retrieved value is not the same than the injected one at the end (%d!=%d)",
 683                        i,cpt);
 684    }
 685    xbt_dynar_free(&d);
 686    xbt_dynar_free(&d);
 687
 688
 689    xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest",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
 694    for (cpt=2000; cpt< 4000; cpt++) {
 695      xbt_dynar_remove_at(d,2000,&i);
 696      xbt_test_assert2(i == cpt,
 697                       "Remove a bad value. Got %d, expected %d",
 698                       i,cpt);
 699      DEBUG2("remove %d, length=%lu",cpt, xbt_dynar_length(d));
 700    }
 701    xbt_dynar_free(&d);
 702    xbt_dynar_free(&d);
 703 }
 704
 705 XBT_TEST_UNIT("double",test_dynar_double,"Dyars of doubles") {
 706    xbt_dynar_t d;
 707    int cpt,cursor;
 708    double d1,d2;
 709
 710    xbt_test_add0("==== Traverse the empty dynar");
 711    d=xbt_dynar_new(sizeof(int),NULL);
 712    xbt_dynar_foreach(d,cursor,cpt){
 713      xbt_test_assert0(FALSE,
 714              "Damnit, there is something in the empty dynar");
 715    }
 716    xbt_dynar_free(&d);
 717    xbt_dynar_free(&d);
 718
 719    xbt_test_add0("==== Push/shift 5000 doubles");
 720    d=xbt_dynar_new(sizeof(double),NULL);
 721    for (cpt=0; cpt< 5000; cpt++) {
 722      d1=(double)cpt;
 723      xbt_dynar_push(d,&d1);
 724    }
 725    xbt_dynar_foreach(d,cursor,d2){
 726      d1=(double)cursor;
 727      xbt_test_assert2(d1 == d2,
 728            "The retrieved value is not the same than the injected one (%f!=%f)",
 729                   d1,d2);
 730    }
 731    for (cpt=0; cpt< 5000; cpt++) {
 732      d1=(double)cpt;
 733      xbt_dynar_shift(d,&d2);
 734      xbt_test_assert2(d1 == d2,
 735            "The retrieved value is not the same than the injected one (%f!=%f)",
 736                   d1,d2);
 737    }
 738    xbt_dynar_free(&d);
 739    xbt_dynar_free(&d);
 740
 741
 742    xbt_test_add0("==== Unshift/pop 5000 doubles");
 743    d=xbt_dynar_new(sizeof(double),NULL);
 744    for (cpt=0; cpt< 5000; cpt++) {
 745      d1=(double)cpt;
 746      xbt_dynar_unshift(d,&d1);
 747    }
 748    for (cpt=0; cpt< 5000; cpt++) {
 749      d1=(double)cpt;
 750      xbt_dynar_pop(d,&d2);
 751      xbt_test_assert2 (d1 == d2,
 752            "The retrieved value is not the same than the injected one (%f!=%f)",
 753                    d1,d2);
 754    }
 755    xbt_dynar_free(&d);
 756    xbt_dynar_free(&d);
 757
 758
 759
 760    xbt_test_add0("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
 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    for (cpt=0; cpt< 1000; cpt++) {
 767      d1=(double)cpt;
 768      xbt_dynar_insert_at(d,2500,&d1);
 769    }
 770
 771    for (cpt=0; cpt< 2500; cpt++) {
 772      d1=(double)cpt;
 773      xbt_dynar_shift(d,&d2);
 774      xbt_test_assert2(d1 == d2,
 775            "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
 776                   d1,d2);
 777      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
 778    }
 779    for (cpt=999; cpt>=0; cpt--) {
 780      d1=(double)cpt;
 781      xbt_dynar_shift(d,&d2);
 782      xbt_test_assert2 (d1 == d2,
 783            "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
 784                    d1,d2);
 785    }
 786    for (cpt=2500; cpt< 5000; cpt++) {
 787      d1=(double)cpt;
 788      xbt_dynar_shift(d,&d2);
 789      xbt_test_assert2 (d1 == d2,
 790            "The retrieved value is not the same than the injected one at the end (%f!=%f)",
 791                    d1,d2);
 792    }
 793    xbt_dynar_free(&d);
 794    xbt_dynar_free(&d);
 795
 796
 797    xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest");
 798    d=xbt_dynar_new(sizeof(double),NULL);
 799    for (cpt=0; cpt< 5000; cpt++) {
 800      d1=(double)cpt;
 801      xbt_dynar_push(d,&d1);
 802    }
 803    for (cpt=2000; cpt< 4000; cpt++) {
 804      d1=(double)cpt;
 805      xbt_dynar_remove_at(d,2000,&d2);
 806      xbt_test_assert2 (d1 == d2,
 807            "Remove a bad value. Got %f, expected %f",
 808                d2,d1);
 809    }
 810    xbt_dynar_free(&d);
 811    xbt_dynar_free(&d);
 812 }
 813
 814
 815 /* doxygen_string_cruft */
 816
 817 /* The function we will use to free the data */
 818 static void free_string(void *d){
 819   free(*(void**)d);
 820 }
 821
 822 XBT_TEST_UNIT("string",test_dynar_string,"Dyars of strings") {
 823    xbt_dynar_t d;
 824    int cpt;
 825    char buf[1024];
 826    char *s1,*s2;
 827
 828    xbt_test_add0("==== Traverse the empty dynar");
 829    d=xbt_dynar_new(sizeof(char *),&free_string);
 830    xbt_dynar_foreach(d,cpt,s1){
 831      xbt_test_assert0(FALSE,
 832                   "Damnit, there is something in the empty dynar");
 833    }
 834    xbt_dynar_free(&d);
 835    xbt_dynar_free(&d);
 836
 837    xbt_test_add1("==== Push %d strings, set them again 3 times, shift them",NB_ELEM);
 838    /* Populate_str [doxygen cruft] */
 839    d=xbt_dynar_new(sizeof(char*),&free_string);
 840    /* 1. Populate the dynar */
 841    for (cpt=0; cpt< NB_ELEM; cpt++) {
 842      sprintf(buf,"%d",cpt);
 843      s1=strdup(buf);
 844      xbt_dynar_push(d,&s1);
 845    }
 846    for (cpt=0; cpt< NB_ELEM; cpt++) {
 847      sprintf(buf,"%d",cpt);
 848      s1=strdup(buf);
 849      xbt_dynar_replace(d,cpt,&s1);
 850    }
 851    for (cpt=0; cpt< NB_ELEM; cpt++) {
 852      sprintf(buf,"%d",cpt);
 853      s1=strdup(buf);
 854      xbt_dynar_replace(d,cpt,&s1);
 855    }
 856    for (cpt=0; cpt< NB_ELEM; cpt++) {
 857      sprintf(buf,"%d",cpt);
 858      s1=strdup(buf);
 859      xbt_dynar_replace(d,cpt,&s1);
 860    }
 861    for (cpt=0; cpt< NB_ELEM; cpt++) {
 862      sprintf(buf,"%d",cpt);
 863      xbt_dynar_shift(d,&s2);
 864      xbt_test_assert2 (!strcmp(buf,s2),
 865             "The retrieved value is not the same than the injected one (%s!=%s)",
 866                    buf,s2);
 867      free(s2);
 868    }
 869    xbt_dynar_free(&d);
 870    xbt_dynar_free(&d);
 871
 872
 873    xbt_test_add1("==== Unshift, traverse and pop %d strings",NB_ELEM);
 874    d=xbt_dynar_new(sizeof(char**),&free_string);
 875    for (cpt=0; cpt< NB_ELEM; cpt++) {
 876      sprintf(buf,"%d",cpt);
 877      s1=strdup(buf);
 878      xbt_dynar_unshift(d,&s1);
 879    }
 880    /* 2. Traverse the dynar with the macro */
 881    xbt_dynar_foreach(d,cpt,s1) {
 882      sprintf(buf,"%d",NB_ELEM - cpt -1);
 883      xbt_test_assert2 (!strcmp(buf,s1),
 884            "The retrieved value is not the same than the injected one (%s!=%s)",
 885                buf,s1);
 886    }
 887    /* 3. Traverse the dynar with the macro */
 888    for (cpt=0; cpt< NB_ELEM; cpt++) {
 889      sprintf(buf,"%d",cpt);
 890      xbt_dynar_pop(d,&s2);
 891      xbt_test_assert2 (!strcmp(buf,s2),
 892            "The retrieved value is not the same than the injected one (%s!=%s)",
 893                buf,s2);
 894      free(s2);
 895    }
 896    /* 4. Free the resources */
 897    xbt_dynar_free(&d);
 898    xbt_dynar_free(&d);
 899
 900
 901    xbt_test_add2("==== Push %d strings, insert %d strings in the middle, shift everything",NB_ELEM,NB_ELEM/5);
 902    d=xbt_dynar_new(sizeof(char*),&free_string);
 903    for (cpt=0; cpt< NB_ELEM; cpt++) {
 904      sprintf(buf,"%d",cpt);
 905      s1=strdup(buf);
 906      xbt_dynar_push(d,&s1);
 907    }
 908    for (cpt=0; cpt< NB_ELEM/5; cpt++) {
 909      sprintf(buf,"%d",cpt);
 910      s1=strdup(buf);
 911      xbt_dynar_insert_at(d,NB_ELEM/2,&s1);
 912    }
 913
 914    for (cpt=0; cpt< NB_ELEM/2; cpt++) {
 915      sprintf(buf,"%d",cpt);
 916      xbt_dynar_shift(d,&s2);
 917      xbt_test_assert2(!strcmp(buf,s2),
 918            "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
 919                buf,s2);
 920       free(s2);
 921    }
 922    for (cpt=(NB_ELEM/5)-1; cpt>=0; cpt--) {
 923      sprintf(buf,"%d",cpt);
 924      xbt_dynar_shift(d,&s2);
 925      xbt_test_assert2 (!strcmp(buf,s2),
 926            "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
 927                buf,s2);
 928      free(s2);
 929    }
 930    for (cpt=NB_ELEM/2; cpt< NB_ELEM; cpt++) {
 931      sprintf(buf,"%d",cpt);
 932      xbt_dynar_shift(d,&s2);
 933      xbt_test_assert2 (!strcmp(buf,s2),
 934            "The retrieved value is not the same than the injected one at the end (%s!=%s)",
 935                buf,s2);
 936      free(s2);
 937    }
 938    xbt_dynar_free(&d);
 939    xbt_dynar_free(&d);
 940
 941
 942    xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest",NB_ELEM,2*(NB_ELEM/5),4*(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=2*(NB_ELEM/5); cpt< 4*(NB_ELEM/5); cpt++) {
 950      sprintf(buf,"%d",cpt);
 951      xbt_dynar_remove_at(d,2*(NB_ELEM/5),&s2);
 952      xbt_test_assert2(!strcmp(buf,s2),
 953                   "Remove a bad value. Got %s, expected %s",
 954                   s2,buf);
 955       free(s2);
 956    }
 957    xbt_dynar_free(&d); /* end_of_doxygen */
 958 }
 959 #endif /* SIMGRID_TEST */