Logo AND Algorithmique Numérique Distribuée

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