Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
I think I just killed a simcall
[simgrid.git] / src / xbt / dynar.cpp
1 /* a generic DYNamic ARray implementation.                                  */
2
3 /* Copyright (c) 2004-2015. The SimGrid Team.
4  * All rights reserved.                                                     */
5
6 /* This program is free software; you can redistribute it and/or modify it
7  * under the terms of the license (GNU LGPL) which comes with this package. */
8
9 #include "xbt/misc.h"
10 #include "xbt/sysdep.h"
11 #include "xbt/log.h"
12 #include "xbt/ex.h"
13 #include <xbt/ex.hpp>
14 #include "xbt/dynar.h"
15 #include <sys/types.h>
16
17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dyn, xbt, "Dynamic arrays");
18
19 static inline void _sanity_check_dynar(xbt_dynar_t dynar)
20 {
21   xbt_assert(dynar, "dynar is nullptr");
22 }
23
24 static inline void _sanity_check_idx(int idx)
25 {
26   xbt_assert(idx >= 0, "dynar idx(=%d) < 0", idx);
27 }
28
29 static inline void _check_inbound_idx(xbt_dynar_t dynar, int idx)
30 {
31   if (idx < 0 || idx >= static_cast<int>(dynar->used)) {
32     THROWF(bound_error, idx, "dynar is not that long. You asked %d, but it's only %lu long",
33            idx, static_cast<unsigned long>(dynar->used));
34   }
35 }
36
37 static inline void _check_populated_dynar(xbt_dynar_t dynar)
38 {
39   if (dynar->used == 0) {
40     THROWF(bound_error, 0, "dynar %p is empty", dynar);
41   }
42 }
43
44 static inline void _xbt_dynar_resize(xbt_dynar_t dynar, unsigned long new_size)
45 {
46   if (new_size != dynar->size) {
47     dynar->size = new_size;
48     dynar->data = xbt_realloc(dynar->data, new_size * dynar->elmsize);
49   }
50 }
51
52 static inline void _xbt_dynar_expand(xbt_dynar_t const dynar, const unsigned long nb)
53 {
54   const unsigned long old_size = dynar->size;
55
56   if (nb > old_size) {
57     const unsigned long expand = 2 * (old_size + 1);
58     _xbt_dynar_resize(dynar, (nb > expand ? nb : expand));
59     XBT_DEBUG("expand %p from %lu to %lu elements", dynar, old_size, dynar->size);
60   }
61 }
62
63 static inline void *_xbt_dynar_elm(const xbt_dynar_t dynar, const unsigned long idx)
64 {
65   char *const data = (char *) dynar->data;
66   const unsigned long elmsize = dynar->elmsize;
67
68   return data + idx * elmsize;
69 }
70
71 static inline void _xbt_dynar_get_elm(void *const dst, const xbt_dynar_t dynar, const unsigned long idx)
72 {
73   void *const elm = _xbt_dynar_elm(dynar, idx);
74
75   memcpy(dst, elm, dynar->elmsize);
76 }
77
78 extern "C" void xbt_dynar_dump(xbt_dynar_t dynar)
79 {
80   XBT_INFO("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
81         dynar->size, dynar->used, dynar->elmsize, dynar->data, dynar->free_f);
82 }
83
84 /** @brief Constructor
85  *
86  * \param elmsize size of each element in the dynar
87  * \param free_f function to call each time we want to get rid of an element (or nullptr if nothing to do).
88  *
89  * Creates a new dynar. If a free_func is provided, the elements have to be pointer of pointer. That is to say that
90  * dynars can contain either base types (int, char, double, etc) or pointer of pointers (struct **).
91  */
92 extern "C" xbt_dynar_t xbt_dynar_new(const unsigned long elmsize, void_f_pvoid_t const free_f)
93 {
94   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t, 1);
95
96   dynar->size = 0;
97   dynar->used = 0;
98   dynar->elmsize = elmsize;
99   dynar->data = nullptr;
100   dynar->free_f = free_f;
101
102   return dynar;
103 }
104
105 /** @brief Initialize a dynar structure that was not malloc'ed
106  * This can be useful to keep temporary dynars on the stack
107  */
108 extern "C" void xbt_dynar_init(xbt_dynar_t dynar, const unsigned long elmsize, void_f_pvoid_t const free_f)
109 {
110   dynar->size    = 0;
111   dynar->used    = 0;
112   dynar->elmsize = elmsize;
113   dynar->data    = nullptr;
114   dynar->free_f  = free_f;
115 }
116
117 /** @brief Destroy a dynar that was created with xbt_dynar_init */
118 extern "C" void xbt_dynar_free_data(xbt_dynar_t dynar)
119 {
120   xbt_dynar_reset(dynar);
121   if (dynar)
122     free(dynar->data);
123 }
124
125 /** @brief Destructor of the structure not touching to the content
126  *
127  * \param dynar poor victim
128  *
129  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content is not touched (the \a free_f function
130  * is not used)
131  */
132 extern "C" void xbt_dynar_free_container(xbt_dynar_t* dynar)
133 {
134   if (dynar && *dynar) {
135     xbt_dynar_t d = *dynar;
136     free(d->data);
137     free(d);
138     *dynar = nullptr;
139   }
140 }
141
142 /** @brief Frees the content and set the size to 0
143  *
144  * \param dynar who to squeeze
145  */
146 extern "C" void xbt_dynar_reset(xbt_dynar_t const dynar)
147 {
148   _sanity_check_dynar(dynar);
149
150   XBT_CDEBUG(xbt_dyn, "Reset the dynar %p", (void *) dynar);
151   if (dynar->free_f) {
152     xbt_dynar_map(dynar, dynar->free_f);
153   }
154   dynar->used = 0;
155 }
156
157 /** @brief Merge dynar d2 into d1
158  *
159  * \param d1 dynar to keep
160  * \param d2 dynar to merge into d1. This dynar is free at end.
161  */
162 extern "C" void xbt_dynar_merge(xbt_dynar_t* d1, xbt_dynar_t* d2)
163 {
164   if((*d1)->elmsize != (*d2)->elmsize)
165     xbt_die("Element size must are not equal");
166
167   const unsigned long elmsize = (*d1)->elmsize;
168
169   void *ptr = _xbt_dynar_elm((*d2), 0);
170   _xbt_dynar_resize(*d1, (*d1)->size + (*d2)->size);
171   void *elm = _xbt_dynar_elm((*d1), (*d1)->used);
172
173   memcpy(elm, ptr, ((*d2)->size)*elmsize);
174   (*d1)->used += (*d2)->used;
175   (*d2)->used = 0;
176   xbt_dynar_free(d2);
177 }
178
179 /**
180  * \brief Shrink the dynar by removing empty slots at the end of the internal array
181  * \param dynar a dynar
182  * \param empty_slots_wanted number of empty slots you want to keep at the end of the internal array for further
183  * insertions
184  *
185  * Reduces the internal array size of the dynar to the number of elements plus \a empty_slots_wanted.
186  * After removing elements from the dynar, you can call this function to make the dynar use less memory.
187  * Set \a empty_slots_wanted to zero to reduce the dynar internal array as much as possible.
188  * Note that if \a empty_slots_wanted is greater than the array size, the internal array is expanded instead of shrunk.
189  */
190 extern "C" void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted)
191 {
192   _xbt_dynar_resize(dynar, dynar->used + empty_slots_wanted);
193 }
194
195 /** @brief Destructor
196  *
197  * \param dynar poor victim
198  *
199  * kilkil a dynar and its content
200  */
201 extern "C" void xbt_dynar_free(xbt_dynar_t* dynar)
202 {
203   if (dynar && *dynar) {
204     xbt_dynar_reset(*dynar);
205     xbt_dynar_free_container(dynar);
206   }
207 }
208
209 /** \brief free a dynar passed as void* (handy to store dynar in dynars or dict) */
210 extern "C" void xbt_dynar_free_voidp(void* d)
211 {
212   xbt_dynar_t dynar = (xbt_dynar_t)d;
213   xbt_dynar_free(&dynar);
214 }
215
216 /** @brief Count of dynar's elements
217  *
218  * \param dynar the dynar we want to mesure
219  */
220 extern "C" unsigned long xbt_dynar_length(const xbt_dynar_t dynar)
221 {
222   return (dynar ? (unsigned long) dynar->used : (unsigned long) 0);
223 }
224
225  /**@brief check if a dynar is empty
226  *
227  *\param dynar the dynat we want to check
228  */
229 extern "C" int xbt_dynar_is_empty(const xbt_dynar_t dynar)
230 {
231   return (xbt_dynar_length(dynar) == 0);
232 }
233
234 /** @brief Retrieve a copy of the Nth element of a dynar.
235  *
236  * \param dynar information dealer
237  * \param idx index of the slot we want to retrieve
238  * \param[out] dst where to put the result to.
239  */
240 extern "C" void xbt_dynar_get_cpy(const xbt_dynar_t dynar, const unsigned long idx, void* const dst)
241 {
242   _sanity_check_dynar(dynar);
243   _check_inbound_idx(dynar, idx);
244
245   _xbt_dynar_get_elm(dst, dynar, idx);
246 }
247
248 /** @brief Retrieve a pointer to the Nth element of a dynar.
249  *
250  * \param dynar information dealer
251  * \param idx index of the slot we want to retrieve
252  * \return the \a idx-th element of \a dynar.
253  *
254  * \warning The returned value is the actual content of the dynar.
255  * Make a copy before fooling with it.
256  */
257 extern "C" void* xbt_dynar_get_ptr(const xbt_dynar_t dynar, const unsigned long idx)
258 {
259   void *res;
260   _sanity_check_dynar(dynar);
261   _check_inbound_idx(dynar, idx);
262
263   res = _xbt_dynar_elm(dynar, idx);
264   return res;
265 }
266
267 extern "C" void* xbt_dynar_set_at_ptr(const xbt_dynar_t dynar, const unsigned long idx)
268 {
269   _sanity_check_dynar(dynar);
270
271   if (idx >= dynar->used) {
272     _xbt_dynar_expand(dynar, idx + 1);
273     if (idx > dynar->used) {
274       memset(_xbt_dynar_elm(dynar, dynar->used), 0, (idx - dynar->used) * dynar->elmsize);
275     }
276     dynar->used = idx + 1;
277   }
278   return _xbt_dynar_elm(dynar, idx);
279 }
280
281 /** @brief Set the Nth element of a dynar (expanded if needed). Previous value at this position is NOT freed
282  *
283  * \param dynar information dealer
284  * \param idx index of the slot we want to modify
285  * \param src What will be feeded to the dynar
286  *
287  * If you want to free the previous content, use xbt_dynar_replace().
288  */
289 extern "C" void xbt_dynar_set(xbt_dynar_t dynar, const int idx, const void* const src)
290 {
291   memcpy(xbt_dynar_set_at_ptr(dynar, idx), src, dynar->elmsize);
292 }
293
294 /** @brief Set the Nth element of a dynar (expanded if needed). Previous value is freed
295  *
296  * \param dynar
297  * \param idx
298  * \param object
299  *
300  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO free the previous value at this position. If
301  * you don't want to free the previous content, use xbt_dynar_set().
302  */
303 extern "C" void xbt_dynar_replace(xbt_dynar_t dynar, const unsigned long idx, const void* const object)
304 {
305   _sanity_check_dynar(dynar);
306
307   if (idx < dynar->used && dynar->free_f) {
308     void *const old_object = _xbt_dynar_elm(dynar, idx);
309
310     dynar->free_f(old_object);
311   }
312
313   xbt_dynar_set(dynar, idx, object);
314 }
315
316 /** @brief Make room for a new element, and return a pointer to it
317  *
318  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
319  * xbt_dynar_insert_at_as() does.
320  */
321 extern "C" void* xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar, const int idx)
322 {
323   void *res;
324   unsigned long old_used;
325   unsigned long new_used;
326   long nb_shift;
327
328   _sanity_check_dynar(dynar);
329   _sanity_check_idx(idx);
330
331   old_used = dynar->used;
332   new_used = old_used + 1;
333
334   _xbt_dynar_expand(dynar, new_used);
335
336   nb_shift = old_used - idx;
337
338   if (nb_shift>0) {
339     memmove(_xbt_dynar_elm(dynar, idx + 1), _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
340   }
341
342   dynar->used = new_used;
343   res = _xbt_dynar_elm(dynar, idx);
344   return res;
345 }
346
347 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
348  *
349  * Set the Nth element of a dynar, expanding the dynar if needed, and moving the previously existing value and all
350  * subsequent ones to one position right in the dynar.
351  */
352 extern "C" void xbt_dynar_insert_at(xbt_dynar_t const dynar, const int idx, const void* const src)
353 {
354   /* checks done in xbt_dynar_insert_at_ptr */
355   memcpy(xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
356 }
357
358 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
359  *
360  * Get the Nth element of a dynar, removing it from the dynar and moving all subsequent values to one position left in
361  * the dynar.
362  *
363  * If the object argument of this function is a non-null pointer, the removed element is copied to this address. If not,
364  * the element is freed using the free_f function passed at dynar creation.
365  */
366 extern "C" void xbt_dynar_remove_at(xbt_dynar_t const dynar, const int idx, void* const object)
367 {
368   unsigned long nb_shift;
369   unsigned long offset;
370
371   _sanity_check_dynar(dynar);
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     dynar->free_f(_xbt_dynar_elm(dynar, idx));
378   }
379
380   nb_shift = dynar->used - 1 - idx;
381
382   if (nb_shift) {
383     offset = nb_shift * dynar->elmsize;
384     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset);
385   }
386
387   dynar->used--;
388 }
389
390 /** @brief Remove a slice of the dynar, sliding the rest of the values to the left
391  *
392  * This function removes an n-sized slice that starts at element idx. It is equivalent to xbt_dynar_remove_at with a
393  * nullptr object argument if n equals to 1.
394  *
395  * Each of the removed elements is freed using the free_f function passed at dynar creation.
396  */
397 extern "C" void xbt_dynar_remove_n_at(xbt_dynar_t const dynar, const unsigned int n, const int idx)
398 {
399   unsigned long nb_shift;
400   unsigned long offset;
401   unsigned long cur;
402
403   if (!n)
404     return;
405
406   _sanity_check_dynar(dynar);
407   _check_inbound_idx(dynar, idx);
408   _check_inbound_idx(dynar, idx + n - 1);
409
410   if (dynar->free_f) {
411     for (cur = idx; cur < idx + n; cur++) {
412       dynar->free_f(_xbt_dynar_elm(dynar, cur));
413     }
414   }
415
416   nb_shift = dynar->used - n - idx;
417
418   if (nb_shift) {
419     offset = nb_shift * dynar->elmsize;
420     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + n), offset);
421   }
422
423   dynar->used -= n;
424 }
425
426 /** @brief Returns the position of the element in the dynar
427  *
428  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function compares the
429  * pointer value, not what's pointed. The only solution to search for a pointed value is then to write the foreach loop
430  * yourself:
431  * \code
432  * signed int position = -1;
433  * xbt_dynar_foreach(dynar, iter, elem) {
434  *    if (!memcmp(elem, searched_element, sizeof(*elem))) {
435  *        position = iter;
436  *        break;
437  *    }
438  * }
439  * \endcode
440  * 
441  * Raises not_found_error if not found. If you have less than 2 millions elements, you probably want to use
442  * #xbt_dynar_search_or_negative() instead, so that you don't have to TRY/CATCH on element not found.
443  */
444 extern "C" unsigned int xbt_dynar_search(xbt_dynar_t const dynar, void* const elem)
445 {
446   unsigned long it;
447
448   for (it = 0; it < dynar->used; it++)
449     if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
450       return it;
451     }
452
453   THROWF(not_found_error, 0, "Element %p not part of dynar %p", elem, dynar);
454   return -1; // Won't happen, just to please eclipse
455 }
456
457 /** @brief Returns the position of the element in the dynar (or -1 if not found)
458  *
459  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
460  * what you want. Check the documentation of xbt_dynar_search() for more info.
461  * 
462  * Note that usually, the dynar indices are unsigned integers. If you have more than 2 million elements in your dynar,
463  * this very function will not work (but the other will).
464  */
465 extern "C" signed int xbt_dynar_search_or_negative(xbt_dynar_t const dynar, void* const elem)
466 {
467   unsigned long it;
468
469   for (it = 0; it < dynar->used; it++)
470     if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
471       return it;
472     }
473
474   return -1;
475 }
476
477 /** @brief Returns a boolean indicating whether the element is part of the dynar 
478  *
479  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
480  * what you want. Check the documentation of xbt_dynar_search() for more info.
481  */
482 extern "C" int xbt_dynar_member(xbt_dynar_t const dynar, void* const elem)
483 {
484   unsigned long it;
485
486   for (it = 0; it < dynar->used; it++)
487     if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
488       return 1;
489     }
490
491   return 0;
492 }
493
494 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
495  *
496  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
497  * xbt_dynar_push_as() does.
498  */
499 extern "C" void* xbt_dynar_push_ptr(xbt_dynar_t const dynar)
500 {
501   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
502 }
503
504 /** @brief Add an element at the end of the dynar */
505 extern "C" void xbt_dynar_push(xbt_dynar_t const dynar, const void* const src)
506 {
507   /* checks done in xbt_dynar_insert_at_ptr */
508   memcpy(xbt_dynar_insert_at_ptr(dynar, dynar->used), src, dynar->elmsize);
509 }
510
511 /** @brief Mark the last dynar's element as unused and return a pointer to it.
512  *
513  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
514  * xbt_dynar_pop_as() does.
515  */
516 extern "C" void* xbt_dynar_pop_ptr(xbt_dynar_t const dynar)
517 {
518   _check_populated_dynar(dynar);
519   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
520   dynar->used--;
521   return _xbt_dynar_elm(dynar, dynar->used);
522 }
523
524 /** @brief Get and remove the last element of the dynar */
525 extern "C" void xbt_dynar_pop(xbt_dynar_t const dynar, void* const dst)
526 {
527   /* sanity checks done by remove_at */
528   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
529   xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
530 }
531
532 /** @brief Add an element at the begining of the dynar.
533  *
534  * This is less efficient than xbt_dynar_push()
535  */
536 extern "C" void xbt_dynar_unshift(xbt_dynar_t const dynar, const void* const src)
537 {
538   /* sanity checks done by insert_at */
539   xbt_dynar_insert_at(dynar, 0, src);
540 }
541
542 /** @brief Get and remove the first element of the dynar.
543  *
544  * This is less efficient than xbt_dynar_pop()
545  */
546 extern "C" void xbt_dynar_shift(xbt_dynar_t const dynar, void* const dst)
547 {
548   /* sanity checks done by remove_at */
549   xbt_dynar_remove_at(dynar, 0, dst);
550 }
551
552 /** @brief Apply a function to each member of a dynar
553  *
554  * The mapped function may change the value of the element itself, but should not mess with the structure of the dynar.
555  */
556 extern "C" void xbt_dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op)
557 {
558   char *const data = (char *) dynar->data;
559   const unsigned long elmsize = dynar->elmsize;
560   const unsigned long used = dynar->used;
561   unsigned long i;
562
563   _sanity_check_dynar(dynar);
564
565   for (i = 0; i < used; i++) {
566     char* elm = (char*) data + i * elmsize;
567     op(elm);
568   }
569 }
570
571 /** @brief Removes and free the entry pointed by the cursor
572  *
573  * This function can be used while traversing without problem.
574  */
575 extern "C" void xbt_dynar_cursor_rm(xbt_dynar_t dynar, unsigned int* const cursor)
576 {
577   xbt_dynar_remove_at(dynar, (*cursor)--, nullptr);
578 }
579
580 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
581  *
582  * This function simply apply the classical qsort(3) function to the data stored in the dynar.
583  * You should thus refer to the libc documentation, or to some online tutorial on how to write
584  * a comparison function. Here is a quick example if you have integers in your dynar:
585  *
586  * @verbatim
587  * int cmpfunc (const void * a, const void * b) {
588  *   int intA = *(int*)a;
589  *   int intB = *(int*)b;
590  *   return intA - intB;
591  * }
592  * @endverbatim
593  *
594  * and now to sort a dynar of MSG hosts depending on their speed:
595  * @verbatim
596  * int cmpfunc(const MSG_host_t a, const MSG_host_t b) {
597  *   MSG_host_t hostA = *(MSG_host_t*)a;
598  *   MSG_host_t hostB = *(MSG_host_t*)b;
599  *   return MSG_host_get_speed(hostA) - MSG_host_get_speed(hostB);
600  * }
601  * @endverbatim
602  *
603  * \param dynar the dynar to sort
604  * \param compar_fn comparison function of type (int (compar_fn*) (const void*) (const void*)).
605  */
606 extern "C" void xbt_dynar_sort(xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn)
607 {
608   if (dynar->data != nullptr)
609     qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
610 }
611
612 static int strcmp_voidp(const void *pa, const void *pb) {
613   return strcmp(*(const char **)pa, *(const char **)pb);
614 }
615
616 /** @brief Sorts a dynar of strings (ie, char* data) */
617 extern "C" xbt_dynar_t xbt_dynar_sort_strings(xbt_dynar_t dynar)
618 {
619   xbt_dynar_sort(dynar, strcmp_voidp);
620   return dynar; // to enable functional uses
621 }
622
623 /** @brief Sorts a dynar according to their color assuming elements can have only three colors.
624  * Since there are only three colors, it is linear and much faster than a classical sort.
625  * See for example http://en.wikipedia.org/wiki/Dutch_national_flag_problem
626  *
627  * \param dynar the dynar to sort
628  * \param color the color function of type (int (compar_fn*) (void*) (void*)). The return value of color is assumed to
629  *        be 0, 1, or 2.
630  *
631  * At the end of the call, elements with color 0 are at the beginning of the dynar, elements with color 2 are at the
632  * end and elements with color 1 are in the middle.
633  *
634  * Remark: if the elements stored in the dynar are structures, the color function has to retrieve the field to sort
635  * first.
636  */
637 extern "C" void xbt_dynar_three_way_partition(xbt_dynar_t const dynar, int_f_pvoid_t color)
638 {
639   unsigned long int i;
640   unsigned long int p = -1;
641   unsigned long int q = dynar->used;
642   const unsigned long elmsize = dynar->elmsize;
643   char* tmp[elmsize];
644   void *elm;
645
646   for (i = 0; i < q;) {
647     void *elmi = _xbt_dynar_elm(dynar, i);
648     int colori = color(elmi);
649
650     if (colori == 1) {
651       ++i;
652     } else {
653       if (colori == 0) {
654         ++p;
655         elm = _xbt_dynar_elm(dynar, p);
656         ++i;
657       } else {                  /* colori == 2 */
658         --q;
659         elm = _xbt_dynar_elm(dynar, q);
660       }
661       if (elm != elmi) {
662         memcpy(tmp,  elm,  elmsize);
663         memcpy(elm,  elmi, elmsize);
664         memcpy(elmi, tmp,  elmsize);
665       }
666     }
667   }
668 }
669
670 /** @brief Transform a dynar into a nullptr terminated array. 
671  *
672  *  \param dynar the dynar to transform
673  *  \return pointer to the first element of the array
674  *
675  *  Note: The dynar won't be usable afterwards.
676  */
677 extern "C" void* xbt_dynar_to_array(xbt_dynar_t dynar)
678 {
679   void *res;
680   xbt_dynar_shrink(dynar, 1);
681   memset(xbt_dynar_push_ptr(dynar), 0, dynar->elmsize);
682   res = dynar->data;
683   free(dynar);
684   return res;
685 }
686
687 /** @brief Compare two dynars
688  *
689  *  \param d1 first dynar to compare
690  *  \param d2 second dynar to compare
691  *  \param compar function to use to compare elements
692  *  \return 0 if d1 and d2 are equal and 1 if not equal
693  *
694  *  d1 and d2 should be dynars of pointers. The compar function takes two  elements and returns 0 when they are
695  *  considered equal, and a value different of zero when they are considered different. Finally, d2 is destroyed
696  *  afterwards.
697  */
698 extern "C" int xbt_dynar_compare(xbt_dynar_t d1, xbt_dynar_t d2, int (*compar)(const void*, const void*))
699 {
700   int i ;
701   int size;
702   if((!d1) && (!d2))
703     return 0;
704   if((!d1) || (!d2)) {
705     XBT_DEBUG("nullptr dynar d1=%p d2=%p",d1,d2);
706     xbt_dynar_free(&d2);
707     return 1;
708   }
709   if((d1->elmsize)!=(d2->elmsize)) {
710     XBT_DEBUG("Size of elmsize d1=%lu d2=%lu",d1->elmsize,d2->elmsize);
711     xbt_dynar_free(&d2);
712     return 1; // xbt_die
713   }
714   if(xbt_dynar_length(d1) != xbt_dynar_length(d2)) {
715     XBT_DEBUG("Size of dynar d1=%lu d2=%lu",xbt_dynar_length(d1),xbt_dynar_length(d2));
716     xbt_dynar_free(&d2);
717     return 1;
718   }
719
720   size = xbt_dynar_length(d1);
721   for(i=0;i<size;i++) {
722     void *data1 = xbt_dynar_get_as(d1, i, void *);
723     void *data2 = xbt_dynar_get_as(d2, i, void *);
724     XBT_DEBUG("link[%d] d1=%p d2=%p",i,data1,data2);
725     if(compar(data1,data2)){
726       xbt_dynar_free(&d2);
727       return 1;
728     }
729   }
730   xbt_dynar_free(&d2);
731   return 0;
732 }
733
734 #ifdef SIMGRID_TEST
735
736 #define NB_ELEM 5000
737
738 XBT_TEST_SUITE("dynar", "Dynar data container");
739 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(xbt_dyn);
740
741 XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers")
742 {
743   /* Vars_decl [doxygen cruft] */
744   int i;
745   unsigned int cursor;
746   int *iptr;
747
748   xbt_test_add("==== Traverse the empty dynar");
749   xbt_dynar_t d = xbt_dynar_new(sizeof(int), nullptr);
750   xbt_dynar_foreach(d, cursor, i) {
751     xbt_die( "Damnit, there is something in the empty dynar");
752   }
753   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
754   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
755   /* in your code is naturally the way to go outside a regression test */
756
757   xbt_test_add("==== Push %d int, set them again 3 times, traverse them, shift them", NB_ELEM);
758   /* Populate_ints [doxygen cruft] */
759   /* 1. Populate the dynar */
760   d = xbt_dynar_new(sizeof(int), nullptr);
761   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
762     xbt_dynar_push_as(d, int, cpt);     /* This is faster (and possible only with scalars) */
763     /* xbt_dynar_push(d,&cpt);       This would also work */
764     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
765   }
766
767   /* 2. Traverse manually the dynar */
768   for (cursor = 0; cursor < NB_ELEM; cursor++) {
769     iptr = (int*) xbt_dynar_get_ptr(d, cursor);
770     xbt_test_assert(cursor == (unsigned int)*iptr, "The retrieved value is not the same than the injected one (%u!=%d)",
771                     cursor, *iptr);
772   }
773
774   /* 3. Traverse the dynar using the neat macro to that extend */
775   int cpt;
776   xbt_dynar_foreach(d, cursor, cpt) {
777     xbt_test_assert(cursor == (unsigned int) cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
778   }
779   /* end_of_traversal */
780
781   for (int cpt = 0; cpt < NB_ELEM; cpt++)
782     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
783
784   for (int cpt = 0; cpt < NB_ELEM; cpt++)
785     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
786   /*     xbt_dynar_set(d,cpt,&cpt); */
787
788   for (int cpt = 0; cpt < NB_ELEM; cpt++)
789     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
790
791   cpt = 0;
792   xbt_dynar_foreach(d, cursor, i) {
793     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one (%d!=%d)", i, cpt);
794     cpt++;
795   }
796   xbt_test_assert(cpt == NB_ELEM, "Cannot retrieve my %d values. Last got one is %d", NB_ELEM, cpt);
797
798   /* shifting [doxygen cruft] */
799   /* 4. Shift all the values */
800   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
801     xbt_dynar_shift(d, &i);
802     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one (%d!=%d)", i, cpt);
803     xbt_test_log("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
804   }
805
806   int* pi;
807   xbt_dynar_foreach_ptr(d, cursor, pi) {
808     *pi = 0;
809   }
810   xbt_dynar_foreach(d, cursor, i) {
811     xbt_test_assert(i == 0, "The value is not the same as the expected one.");
812   }
813   xbt_dynar_foreach_ptr(d, cursor, pi) {
814     *pi = 1;
815   }
816   xbt_dynar_foreach(d, cursor, i) {
817     xbt_test_assert(i == 1, "The value is not the same as the expected one.");
818   }
819
820   /* 5. Free the resources */
821   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
822   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
823   /* in your code is naturally the way to go outside a regression test */
824
825   xbt_test_add("==== Unshift/pop %d int", NB_ELEM);
826   d = xbt_dynar_new(sizeof(int), nullptr);
827   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
828     xbt_dynar_unshift(d, &cpt);
829     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
830   }
831   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
832     i = xbt_dynar_pop_as(d, int);
833     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one (%d!=%d)", i, cpt);
834     xbt_test_log("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
835   }
836   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
837   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
838   /* in your code is naturally the way to go outside a regression test */
839
840   xbt_test_add ("==== Push %d int, insert 1000 int in the middle, shift everything", NB_ELEM);
841   d = xbt_dynar_new(sizeof(int), nullptr);
842   for (cpt = 0; cpt < NB_ELEM; cpt++) {
843     xbt_dynar_push_as(d, int, cpt);
844     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
845   }
846   for (cpt = 0; cpt < NB_ELEM/5; cpt++) {
847     xbt_dynar_insert_at_as(d, NB_ELEM/2, int, cpt);
848     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
849   }
850
851   for (cpt = 0; cpt < NB_ELEM/2; cpt++) {
852     xbt_dynar_shift(d, &i);
853     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one at the begining (%d!=%d)",
854                      i, cpt);
855     XBT_DEBUG("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
856   }
857   for (cpt = 999; cpt >= 0; cpt--) {
858     xbt_dynar_shift(d, &i);
859     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
860                      i, cpt);
861   }
862   for (cpt = 2500; cpt < NB_ELEM; cpt++) {
863     xbt_dynar_shift(d, &i);
864     xbt_test_assert(i == cpt, "The retrieved value is not the same than the injected one at the end (%d!=%d)", i, cpt);
865   }
866   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
867   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
868   /* in your code is naturally the way to go outside a regression test */
869
870   xbt_test_add("==== Push %d int, remove 2000-4000. free the rest", NB_ELEM);
871   d = xbt_dynar_new(sizeof(int), nullptr);
872   for (cpt = 0; cpt < NB_ELEM; cpt++)
873     xbt_dynar_push_as(d, int, cpt);
874
875   for (cpt = 2000; cpt < 4000; cpt++) {
876     xbt_dynar_remove_at(d, 2000, &i);
877     xbt_test_assert(i == cpt, "Remove a bad value. Got %d, expected %d", i, cpt);
878     XBT_DEBUG("remove %d, length=%lu", cpt, xbt_dynar_length(d));
879   }
880   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
881   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
882   /* in your code is naturally the way to go outside a regression test */
883 }
884
885 /*******************************************************************************/
886 XBT_TEST_UNIT("insert",test_dynar_insert,"Using the xbt_dynar_insert and xbt_dynar_remove functions")
887 {
888   xbt_dynar_t d = xbt_dynar_new(sizeof(unsigned int), nullptr);
889   unsigned int cursor;
890
891   xbt_test_add("==== Insert %d int, traverse them, remove them",NB_ELEM);
892   /* Populate_ints [doxygen cruft] */
893   /* 1. Populate the dynar */
894   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
895     xbt_dynar_insert_at(d, cpt, &cpt);
896     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
897   }
898
899   /* 3. Traverse the dynar */
900   int cpt;
901   xbt_dynar_foreach(d, cursor, cpt) {
902     xbt_test_assert(cursor == (unsigned int) cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
903   }
904   /* end_of_traversal */
905
906   /* Re-fill with the same values using set_as (and re-verify) */
907   for (int cpt = 0; cpt < NB_ELEM; cpt++)
908     xbt_dynar_set_as(d, cpt, int, cpt);
909   xbt_dynar_foreach(d, cursor, cpt)
910     xbt_test_assert(cursor == (unsigned int) cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
911
912   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
913     int val;
914     xbt_dynar_remove_at(d,0,&val);
915     xbt_test_assert(cpt == val, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
916   }
917   xbt_test_assert(xbt_dynar_is_empty(d), "There is still %lu elements in the dynar after removing everything",
918                    xbt_dynar_length(d));
919   xbt_dynar_free(&d);
920
921   /* ********************* */
922   xbt_test_add("==== Insert %d int in reverse order, traverse them, remove them",NB_ELEM);
923   d = xbt_dynar_new(sizeof(int), nullptr);
924   for (int cpt = NB_ELEM - 1; cpt >= 0; cpt--) {
925     xbt_dynar_replace(d, cpt, &cpt);
926     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
927   }
928
929   /* 3. Traverse the dynar */
930   xbt_dynar_foreach(d, cursor, cpt) {
931     xbt_test_assert(cursor == (unsigned) cpt, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
932   }
933   /* end_of_traversal */
934
935   for (cpt =NB_ELEM-1; cpt >=0; cpt--) {
936     int val;
937     xbt_dynar_remove_at(d,xbt_dynar_length(d)-1,&val);
938     xbt_test_assert(cpt == val, "The retrieved value is not the same than the injected one (%u!=%d)", cursor, cpt);
939   }
940   xbt_test_assert(xbt_dynar_is_empty(d), "There is still %lu elements in the dynar after removing everything",
941                    xbt_dynar_length(d));
942   xbt_dynar_free(&d);
943 }
944
945 /*******************************************************************************/
946 XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles")
947 {
948   xbt_dynar_t d;
949   int cpt;
950   unsigned int cursor;
951   double d1, d2;
952
953   xbt_test_add("==== Traverse the empty dynar");
954   d = xbt_dynar_new(sizeof(int), nullptr);
955   xbt_dynar_foreach(d, cursor, cpt) {
956     xbt_test_assert(FALSE, "Damnit, there is something in the empty dynar");
957   }
958   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
959   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
960   /* in your code is naturally the way to go outside a regression test */
961
962   xbt_test_add("==== Push/shift 5000 doubles");
963   d = xbt_dynar_new(sizeof(double), nullptr);
964   for (cpt = 0; cpt < 5000; cpt++) {
965     d1 = (double) cpt;
966     xbt_dynar_push(d, &d1);
967   }
968   xbt_dynar_foreach(d, cursor, d2) {
969     d1 = (double) cursor;
970     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2);
971   }
972   for (cpt = 0; cpt < 5000; cpt++) {
973     d1 = (double) cpt;
974     xbt_dynar_shift(d, &d2);
975     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2);
976   }
977   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
978   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
979   /* in your code is naturally the way to go outside a regression test */
980
981   xbt_test_add("==== Unshift/pop 5000 doubles");
982   d = xbt_dynar_new(sizeof(double), nullptr);
983   for (cpt = 0; cpt < 5000; cpt++) {
984     d1 = (double) cpt;
985     xbt_dynar_unshift(d, &d1);
986   }
987   for (cpt = 0; cpt < 5000; cpt++) {
988     d1 = (double) cpt;
989     xbt_dynar_pop(d, &d2);
990     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2);
991   }
992   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
993   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
994   /* in your code is naturally the way to go outside a regression test */
995
996   xbt_test_add("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
997   d = xbt_dynar_new(sizeof(double), nullptr);
998   for (cpt = 0; cpt < 5000; cpt++) {
999     d1 = (double) cpt;
1000     xbt_dynar_push(d, &d1);
1001   }
1002   for (cpt = 0; cpt < 1000; cpt++) {
1003     d1 = (double) cpt;
1004     xbt_dynar_insert_at(d, 2500, &d1);
1005   }
1006
1007   for (cpt = 0; cpt < 2500; cpt++) {
1008     d1 = (double) cpt;
1009     xbt_dynar_shift(d, &d2);
1010     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
1011                      d1, d2);
1012     XBT_DEBUG("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
1013   }
1014   for (cpt = 999; cpt >= 0; cpt--) {
1015     d1 = (double) cpt;
1016     xbt_dynar_shift(d, &d2);
1017     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
1018                      d1, d2);
1019   }
1020   for (cpt = 2500; cpt < 5000; cpt++) {
1021     d1 = (double) cpt;
1022     xbt_dynar_shift(d, &d2);
1023     xbt_test_assert(d1 == d2, "The retrieved value is not the same than the injected one at the end (%f!=%f)", d1, d2);
1024   }
1025   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1026   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1027   /* in your code is naturally the way to go outside a regression test */
1028
1029   xbt_test_add("==== Push 5000 double, remove 2000-4000. free the rest");
1030   d = xbt_dynar_new(sizeof(double), nullptr);
1031   for (cpt = 0; cpt < 5000; cpt++) {
1032     d1 = (double) cpt;
1033     xbt_dynar_push(d, &d1);
1034   }
1035   for (cpt = 2000; cpt < 4000; cpt++) {
1036     d1 = (double) cpt;
1037     xbt_dynar_remove_at(d, 2000, &d2);
1038     xbt_test_assert(d1 == d2, "Remove a bad value. Got %f, expected %f", d2, d1);
1039   }
1040   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1041   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1042   /* in your code is naturally the way to go outside a regression test */
1043 }
1044
1045 /* doxygen_string_cruft */
1046
1047 /*******************************************************************************/
1048 XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings")
1049 {
1050   unsigned int iter;
1051   char buf[1024];
1052   char *s1, *s2;
1053
1054   xbt_test_add("==== Traverse the empty dynar");
1055   xbt_dynar_t d = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
1056   xbt_dynar_foreach(d, iter, s1) {
1057     xbt_test_assert(FALSE, "Damnit, there is something in the empty dynar");
1058   }
1059   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1060   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1061   /* in your code is naturally the way to go outside a regression test */
1062
1063   xbt_test_add("==== Push %d strings, set them again 3 times, shift them", NB_ELEM);
1064   /* Populate_str [doxygen cruft] */
1065   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1066   /* 1. Populate the dynar */
1067   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1068     snprintf(buf,1023, "%d", cpt);
1069     s1 = xbt_strdup(buf);
1070     xbt_dynar_push(d, &s1);
1071   }
1072   for (int i = 0 ; i < 3 ; i++) {
1073     for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1074       snprintf(buf,1023, "%d", cpt);
1075       s1 = xbt_strdup(buf);
1076       xbt_dynar_replace(d, cpt, &s1);
1077     }
1078   }
1079   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1080     snprintf(buf,1023, "%d", cpt);
1081     xbt_dynar_shift(d, &s2);
1082     xbt_test_assert(!strcmp(buf, s2), "The retrieved value is not the same than the injected one (%s!=%s)", buf, s2);
1083     free(s2);
1084   }
1085   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1086   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1087   /* in your code is naturally the way to go outside a regression test */
1088
1089   xbt_test_add("==== Unshift, traverse and pop %d strings", NB_ELEM);
1090   d = xbt_dynar_new(sizeof(char **), &xbt_free_ref);
1091   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1092     snprintf(buf,1023, "%d", cpt);
1093     s1 = xbt_strdup(buf);
1094     xbt_dynar_unshift(d, &s1);
1095   }
1096   /* 2. Traverse the dynar with the macro */
1097   xbt_dynar_foreach(d, iter, s1) {
1098     snprintf(buf,1023, "%u", NB_ELEM - iter - 1);
1099     xbt_test_assert(!strcmp(buf, s1), "The retrieved value is not the same than the injected one (%s!=%s)", buf, s1);
1100   }
1101   /* 3. Traverse the dynar with the macro */
1102   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1103     snprintf(buf,1023, "%d", cpt);
1104     xbt_dynar_pop(d, &s2);
1105     xbt_test_assert(!strcmp(buf, s2), "The retrieved value is not the same than the injected one (%s!=%s)", buf, s2);
1106     free(s2);
1107   }
1108   /* 4. Free the resources */
1109   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1110   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1111   /* in your code is naturally the way to go outside a regression test */
1112
1113   xbt_test_add("==== Push %d strings, insert %d strings in the middle, shift everything", NB_ELEM, NB_ELEM / 5);
1114   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1115   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1116     snprintf(buf,1023, "%d", cpt);
1117     s1 = xbt_strdup(buf);
1118     xbt_dynar_push(d, &s1);
1119   }
1120   for (int cpt = 0; cpt < NB_ELEM / 5; cpt++) {
1121     snprintf(buf,1023, "%d", cpt);
1122     s1 = xbt_strdup(buf);
1123     xbt_dynar_insert_at(d, NB_ELEM / 2, &s1);
1124   }
1125
1126   for (int cpt = 0; cpt < NB_ELEM / 2; cpt++) {
1127     snprintf(buf,1023, "%d", cpt);
1128     xbt_dynar_shift(d, &s2);
1129     xbt_test_assert(!strcmp(buf, s2),
1130                      "The retrieved value is not the same than the injected one at the begining (%s!=%s)", buf, s2);
1131     free(s2);
1132   }
1133   for (int cpt = (NB_ELEM / 5) - 1; cpt >= 0; cpt--) {
1134     snprintf(buf,1023, "%d", cpt);
1135     xbt_dynar_shift(d, &s2);
1136     xbt_test_assert(!strcmp(buf, s2),
1137                      "The retrieved value is not the same than the injected one in the middle (%s!=%s)", buf, s2);
1138     free(s2);
1139   }
1140   for (int cpt = NB_ELEM / 2; cpt < NB_ELEM; cpt++) {
1141     snprintf(buf,1023, "%d", cpt);
1142     xbt_dynar_shift(d, &s2);
1143     xbt_test_assert(!strcmp(buf, s2), "The retrieved value is not the same than the injected one at the end (%s!=%s)",
1144                      buf, s2);
1145     free(s2);
1146   }
1147   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1148   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1149   /* in your code is naturally the way to go outside a regression test */
1150
1151   xbt_test_add("==== Push %d strings, remove %d-%d. free the rest", NB_ELEM, 2 * (NB_ELEM / 5), 4 * (NB_ELEM / 5));
1152   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1153   for (int cpt = 0; cpt < NB_ELEM; cpt++) {
1154     snprintf(buf,1023, "%d", cpt);
1155     s1 = xbt_strdup(buf);
1156     xbt_dynar_push(d, &s1);
1157   }
1158   for (int cpt = 2 * (NB_ELEM / 5); cpt < 4 * (NB_ELEM / 5); cpt++) {
1159     snprintf(buf,1023, "%d", cpt);
1160     xbt_dynar_remove_at(d, 2 * (NB_ELEM / 5), &s2);
1161     xbt_test_assert(!strcmp(buf, s2), "Remove a bad value. Got %s, expected %s", s2, buf);
1162     free(s2);
1163   }
1164   xbt_dynar_free(&d);           /* end_of_doxygen */
1165 }
1166 #endif                          /* SIMGRID_TEST */