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