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