Logo AND Algorithmique Numérique Distribuée

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