Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Cosmetics: use XBT_LOG_EXTERNAL_DEFAULT_CATEGORY where possible.
[simgrid.git] / src / xbt / dynar.c
1 /* a generic DYNamic ARray implementation.                                  */
2
3 /* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. 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/dynar.h"
14 #include <sys/types.h>
15
16 /* IMPLEMENTATION NOTE ON SYNCHRONIZATION: every functions which name is prefixed by _
17  * assumes that the dynar is already locked if we have to.
18  * Other functions (public ones) check for this.
19  */
20
21 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dyn, xbt, "Dynamic arrays");
22
23 static XBT_INLINE void _dynar_lock(xbt_dynar_t dynar)
24 {
25   if (dynar->mutex)
26     xbt_mutex_acquire(dynar->mutex);
27 }
28
29 static XBT_INLINE void _dynar_unlock(xbt_dynar_t dynar)
30 {
31   if (dynar->mutex)
32     xbt_mutex_release(dynar->mutex);
33 }
34
35 static XBT_INLINE void _sanity_check_dynar(xbt_dynar_t dynar)
36 {
37   xbt_assert(dynar, "dynar is NULL");
38 }
39
40 static XBT_INLINE void _sanity_check_idx(int idx)
41 {
42   xbt_assert(idx >= 0, "dynar idx(=%d) < 0", (int) (idx));
43 }
44
45 static XBT_INLINE void _check_inbound_idx(xbt_dynar_t dynar, int idx)
46 {
47   if (idx < 0 || idx >= dynar->used) {
48     _dynar_unlock(dynar);
49     THROWF(bound_error, idx,
50            "dynar is not that long. You asked %d, but it's only %lu long",
51            (int) (idx), (unsigned long) dynar->used);
52   }
53 }
54
55 static XBT_INLINE void _check_sloppy_inbound_idx(xbt_dynar_t dynar,
56                                                  int idx)
57 {
58   if (idx > dynar->used) {
59     _dynar_unlock(dynar);
60     THROWF(bound_error, idx,
61            "dynar is not that long. You asked %d, but it's only %lu long (could have been equal to it)",
62            (int) (idx), (unsigned long) dynar->used);
63   }
64 }
65
66 static XBT_INLINE void _check_populated_dynar(xbt_dynar_t dynar)
67 {
68   if (dynar->used == 0) {
69     _dynar_unlock(dynar);
70     THROWF(bound_error, 0, "dynar %p is empty", dynar);
71   }
72 }
73
74 static void _dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op);
75
76 static XBT_INLINE
77 void _xbt_dynar_resize(xbt_dynar_t dynar, unsigned long new_size)
78 {
79   if (new_size != dynar->size) {
80     dynar->size = new_size;
81     dynar->data = xbt_realloc(dynar->data, new_size * dynar->elmsize);
82   }
83 }
84
85 static XBT_INLINE
86     void _xbt_dynar_expand(xbt_dynar_t const dynar, const unsigned long nb)
87 {
88   const unsigned long old_size = dynar->size;
89
90   if (nb > old_size) {
91     const unsigned long expand = 2 * (old_size + 1);
92     _xbt_dynar_resize(dynar, (nb > expand ? nb : expand));
93     XBT_DEBUG("expand %p from %lu to %lu elements",
94               dynar, old_size, dynar->size);
95   }
96 }
97
98 static XBT_INLINE
99     void *_xbt_dynar_elm(const xbt_dynar_t dynar, const unsigned long idx)
100 {
101   char *const data = (char *) dynar->data;
102   const unsigned long elmsize = dynar->elmsize;
103
104   return data + idx * elmsize;
105 }
106
107 static XBT_INLINE
108     void
109 _xbt_dynar_get_elm(void *const dst,
110                    const xbt_dynar_t dynar, const unsigned long idx)
111 {
112   void *const elm = _xbt_dynar_elm(dynar, idx);
113
114   memcpy(dst, elm, dynar->elmsize);
115 }
116
117 static XBT_INLINE
118     void
119 _xbt_dynar_put_elm(const xbt_dynar_t dynar,
120                    const unsigned long idx, const void *const src)
121 {
122   void *const elm = _xbt_dynar_elm(dynar, idx);
123   const unsigned long elmsize = dynar->elmsize;
124
125   memcpy(elm, src, elmsize);
126 }
127
128 static XBT_INLINE
129     void
130 _xbt_dynar_remove_at(xbt_dynar_t const dynar,
131                      const unsigned long idx, void *const object)
132 {
133
134   unsigned long nb_shift;
135   unsigned long offset;
136
137   _sanity_check_dynar(dynar);
138   _check_inbound_idx(dynar, idx);
139
140   if (object) {
141     _xbt_dynar_get_elm(object, dynar, idx);
142   } else if (dynar->free_f) {
143     dynar->free_f(_xbt_dynar_elm(dynar, idx));
144   }
145
146   nb_shift = dynar->used - 1 - idx;
147
148   if (nb_shift) {
149     offset = nb_shift * dynar->elmsize;
150     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1),
151             offset);
152   }
153
154   dynar->used--;
155 }
156
157 void xbt_dynar_dump(xbt_dynar_t dynar)
158 {
159   XBT_INFO("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
160         dynar->size, dynar->used, dynar->elmsize, dynar->data,
161         dynar->free_f);
162 }
163
164 /** @brief Constructor
165  *
166  * \param elmsize size of each element in the dynar
167  * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
168  *
169  * Creates a new dynar. If a free_func is provided, the elements have to be
170  * pointer of pointer. That is to say that dynars can contain either base
171  * types (int, char, double, etc) or pointer of pointers (struct **).
172  */
173 xbt_dynar_t
174 xbt_dynar_new(const unsigned long elmsize, void_f_pvoid_t const free_f)
175 {
176
177   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t, 1);
178
179   dynar->size = 0;
180   dynar->used = 0;
181   dynar->elmsize = elmsize;
182   dynar->data = NULL;
183   dynar->free_f = free_f;
184   dynar->mutex = NULL;
185
186   return dynar;
187 }
188
189 /** @brief Creates a synchronized dynar.
190  *
191  * Just like #xbt_dynar_new, but each access to the structure will be protected by a mutex
192  *
193  */
194 xbt_dynar_t
195 xbt_dynar_new_sync(const unsigned long elmsize,
196                    void_f_pvoid_t const free_f)
197 {
198   xbt_dynar_t res = xbt_dynar_new(elmsize, free_f);
199   res->mutex = xbt_mutex_init();
200   return res;
201 }
202
203 /** @brief Destructor of the structure not touching to the content
204  *
205  * \param dynar poor victim
206  *
207  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
208  * is not touched (the \a free_f function is not used)
209  */
210 void xbt_dynar_free_container(xbt_dynar_t * dynar)
211 {
212   if (dynar && *dynar) {
213     xbt_dynar_t d = *dynar;
214     free(d->data);
215     if (d->mutex)
216       xbt_mutex_destroy(d->mutex);
217     free(d);
218     *dynar = NULL;
219   }
220 }
221
222 /** @brief Frees the content and set the size to 0
223  *
224  * \param dynar who to squeeze
225  */
226 XBT_INLINE void xbt_dynar_reset(xbt_dynar_t const dynar)
227 {
228   _dynar_lock(dynar);
229
230   _sanity_check_dynar(dynar);
231
232   XBT_DEBUG("Reset the dynar %p", (void *) dynar);
233   if (dynar->free_f) {
234     _dynar_map(dynar, dynar->free_f);
235   }
236   dynar->used = 0;
237
238   _dynar_unlock(dynar);
239 }
240
241 /** @brief Merge dynar d2 into d1
242  *
243  * \param d1 dynar to keep
244  * \param d2 dynar to merge into d1. This dynar is free at end.
245  */
246 void xbt_dynar_merge(xbt_dynar_t *d1, xbt_dynar_t *d2)
247 {
248   if((*d1)->elmsize != (*d2)->elmsize)
249     xbt_die("Element size must are not equal");
250
251   const unsigned long elmsize = (*d1)->elmsize;
252
253   void *ptr = _xbt_dynar_elm((*d2), 0);
254   _xbt_dynar_resize(*d1, (*d1)->size + (*d2)->size);
255   void *elm = _xbt_dynar_elm((*d1), (*d1)->used);
256
257   memcpy(elm, ptr, ((*d2)->size)*elmsize);
258   (*d1)->used += (*d2)->used;
259   (*d2)->used = 0;
260   xbt_dynar_free(d2);
261 }
262
263 /**
264  * \brief Shrink the dynar by removing empty slots at the end of the internal array
265  * \param dynar a dynar
266  * \param empty_slots_wanted number of empty slots you want to keep at the end of the
267  * internal array for further insertions
268  *
269  * Reduces the internal array size of the dynar to the number of elements plus
270  * \a empty_slots_wanted.
271  * After removing elements from the dynar, you can call this function to make
272  * the dynar use less memory.
273  * Set \a empty_slots_wanted to zero to reduce the dynar internal array as much
274  * as possible.
275  * Note that if \a empty_slots_wanted is greater than the array size, the internal
276  * array is expanded instead of shriked.
277  */
278 void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted)
279 {
280   _dynar_lock(dynar);
281   _xbt_dynar_resize(dynar, dynar->used + empty_slots_wanted);
282   _dynar_unlock(dynar);
283 }
284
285 /** @brief Destructor
286  *
287  * \param dynar poor victim
288  *
289  * kilkil a dynar and its content
290  */
291
292 XBT_INLINE void xbt_dynar_free(xbt_dynar_t * dynar)
293 {
294   if (dynar && *dynar) {
295     xbt_dynar_reset(*dynar);
296     xbt_dynar_free_container(dynar);
297   }
298 }
299
300 /** \brief free a dynar passed as void* (handy to store dynar in dynars or dict) */
301 void xbt_dynar_free_voidp(void *d)
302 {
303   xbt_dynar_t dynar = (xbt_dynar_t)d;
304   xbt_dynar_free(&dynar);
305 }
306
307 /** @brief Count of dynar's elements
308  *
309  * \param dynar the dynar we want to mesure
310  */
311 XBT_INLINE unsigned long xbt_dynar_length(const xbt_dynar_t dynar)
312 {
313   return (dynar ? (unsigned long) dynar->used : (unsigned long) 0);
314 }
315
316  /**@brief check if a dynar is empty
317  *
318  *\param dynar the dynat we want to check
319  */
320
321 XBT_INLINE int xbt_dynar_is_empty(const xbt_dynar_t dynar)
322 {
323   return (xbt_dynar_length(dynar) == 0);
324 }
325
326 /** @brief Retrieve a copy of the Nth element of a dynar.
327  *
328  * \param dynar information dealer
329  * \param idx index of the slot we want to retrieve
330  * \param[out] dst where to put the result to.
331  */
332 XBT_INLINE void
333 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
334                   const unsigned long idx, void *const dst)
335 {
336   _dynar_lock(dynar);
337   _sanity_check_dynar(dynar);
338   _check_inbound_idx(dynar, idx);
339
340   _xbt_dynar_get_elm(dst, dynar, idx);
341   _dynar_unlock(dynar);
342 }
343
344 /** @brief Retrieve a pointer to the Nth element of a dynar.
345  *
346  * \param dynar information dealer
347  * \param idx index of the slot we want to retrieve
348  * \return the \a idx-th element of \a dynar.
349  *
350  * \warning The returned value is the actual content of the dynar.
351  * Make a copy before fooling with it.
352  */
353 XBT_INLINE void *xbt_dynar_get_ptr(const xbt_dynar_t dynar,
354                                    const unsigned long idx)
355 {
356
357   void *res;
358   _dynar_lock(dynar);
359   _sanity_check_dynar(dynar);
360   _check_inbound_idx(dynar, idx);
361
362   res = _xbt_dynar_elm(dynar, idx);
363   _dynar_unlock(dynar);
364   return res;
365 }
366
367 /* not synchronized */
368 static XBT_INLINE void *_xbt_dynar_set_at_ptr(const xbt_dynar_t dynar,
369                                               const unsigned long idx)
370 {
371   _sanity_check_dynar(dynar);
372
373   if (idx >= dynar->used) {
374     _xbt_dynar_expand(dynar, idx + 1);
375     if (idx > dynar->used) {
376       memset(_xbt_dynar_elm(dynar, dynar->used), 0,
377              (idx - dynar->used) * dynar->elmsize);
378     }
379     dynar->used = idx + 1;
380   }
381   return _xbt_dynar_elm(dynar, idx);
382 }
383
384 XBT_INLINE void *xbt_dynar_set_at_ptr(const xbt_dynar_t dynar,
385                                       const unsigned long idx)
386 {
387   void *res;
388   _dynar_lock(dynar);
389   res = _xbt_dynar_set_at_ptr(dynar, idx);
390   _dynar_unlock(dynar);
391   return res;
392 }
393
394 static void XBT_INLINE          /* not synchronized */
395 _xbt_dynar_set(xbt_dynar_t dynar,
396                const unsigned long idx, const void *const src)
397 {
398   memcpy(_xbt_dynar_set_at_ptr(dynar, idx), src, dynar->elmsize);
399 }
400
401 /** @brief Set the Nth element of a dynar (expanded if needed). Previous value at this position is NOT freed
402  *
403  * \param dynar information dealer
404  * \param idx index of the slot we want to modify
405  * \param src What will be feeded to the dynar
406  *
407  * If you want to free the previous content, use xbt_dynar_replace().
408  */
409 XBT_INLINE void xbt_dynar_set(xbt_dynar_t dynar, const int idx,
410                               const void *const src)
411 {
412
413   _dynar_lock(dynar);
414   _xbt_dynar_set(dynar, idx, src);
415   _dynar_unlock(dynar);
416 }
417
418 /** @brief Set the Nth element of a dynar (expanded if needed). Previous value is freed
419  *
420  * \param dynar
421  * \param idx
422  * \param object
423  *
424  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
425  * free the previous value at this position. If you don't want to free the
426  * previous content, use xbt_dynar_set().
427  */
428 void
429 xbt_dynar_replace(xbt_dynar_t dynar,
430                   const unsigned long idx, const void *const object)
431 {
432   _dynar_lock(dynar);
433   _sanity_check_dynar(dynar);
434
435   if (idx < dynar->used && dynar->free_f) {
436     void *const old_object = _xbt_dynar_elm(dynar, idx);
437
438     dynar->free_f(old_object);
439   }
440
441   _xbt_dynar_set(dynar, idx, object);
442   _dynar_unlock(dynar);
443 }
444
445 static XBT_INLINE void *_xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
446                                                  const unsigned long idx)
447 {
448   void *res;
449   unsigned long old_used;
450   unsigned long new_used;
451   long nb_shift;
452
453   _sanity_check_dynar(dynar);
454   _sanity_check_idx(idx);
455
456   old_used = dynar->used;
457   new_used = old_used + 1;
458
459   _xbt_dynar_expand(dynar, new_used);
460
461   nb_shift = old_used - idx;
462
463   if (nb_shift>0) {
464     memmove(_xbt_dynar_elm(dynar, idx + 1),
465             _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
466   }
467
468   dynar->used = new_used;
469   res = _xbt_dynar_elm(dynar, idx);
470   return res;
471 }
472
473 /** @brief Make room for a new element, and return a pointer to it
474  *
475  * You can then use regular affectation to set its value instead of relying
476  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
477  */
478 void *xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar, const int idx)
479 {
480   void *res;
481
482   _dynar_lock(dynar);
483   res = _xbt_dynar_insert_at_ptr(dynar, idx);
484   _dynar_unlock(dynar);
485   return res;
486 }
487
488 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
489  *
490  * Set the Nth element of a dynar, expanding the dynar if needed, and
491  * moving the previously existing value and all subsequent ones to one
492  * position right in the dynar.
493  */
494 XBT_INLINE void
495 xbt_dynar_insert_at(xbt_dynar_t const dynar,
496                     const int idx, const void *const src)
497 {
498
499   _dynar_lock(dynar);
500   /* checks done in xbt_dynar_insert_at_ptr */
501   memcpy(_xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
502   _dynar_unlock(dynar);
503 }
504
505 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
506  *
507  * Get the Nth element of a dynar, removing it from the dynar and moving
508  * all subsequent values to one position left in the dynar.
509  *
510  * If the object argument of this function is a non-null pointer, the removed
511  * element is copied to this address. If not, the element is freed using the
512  * free_f function passed at dynar creation.
513  */
514 void
515 xbt_dynar_remove_at(xbt_dynar_t const dynar,
516                     const int idx, void *const object)
517 {
518
519   _dynar_lock(dynar);
520   _xbt_dynar_remove_at(dynar, idx, object);
521   _dynar_unlock(dynar);
522 }
523
524 /** @brief Returns the position of the element in the dynar
525  *
526  * Raises not_found_error if not found.
527  */
528 unsigned int xbt_dynar_search(xbt_dynar_t const dynar, void *const elem)
529 {
530   unsigned long it;
531
532   _dynar_lock(dynar);
533   for (it = 0; it < dynar->used; it++)
534     if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
535       _dynar_unlock(dynar);
536       return it;
537     }
538
539   _dynar_unlock(dynar);
540   THROWF(not_found_error, 0, "Element %p not part of dynar %p", elem,
541          dynar);
542 }
543
544 /** @brief Returns a boolean indicating whether the element is part of the dynar */
545 int xbt_dynar_member(xbt_dynar_t const dynar, void *const elem)
546 {
547
548   xbt_ex_t e;
549
550   TRY {
551     xbt_dynar_search(dynar, elem);
552   }
553   CATCH(e) {
554     if (e.category == not_found_error) {
555       xbt_ex_free(e);
556       return 0;
557     }
558     RETHROW;
559   }
560   return 1;
561 }
562
563 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
564  *
565  * You can then use regular affectation to set its value instead of relying
566  * on the slow memcpy. This is what xbt_dynar_push_as() does.
567  */
568 XBT_INLINE void *xbt_dynar_push_ptr(xbt_dynar_t const dynar)
569 {
570   void *res;
571
572   /* we have to inline xbt_dynar_insert_at_ptr here to make sure that
573      dynar->used don't change between reading it and getting the lock
574      within xbt_dynar_insert_at_ptr */
575   _dynar_lock(dynar);
576   res = _xbt_dynar_insert_at_ptr(dynar, dynar->used);
577   _dynar_unlock(dynar);
578   return res;
579 }
580
581 /** @brief Add an element at the end of the dynar */
582 XBT_INLINE void xbt_dynar_push(xbt_dynar_t const dynar,
583                                const void *const src)
584 {
585   _dynar_lock(dynar);
586   /* checks done in xbt_dynar_insert_at_ptr */
587   memcpy(_xbt_dynar_insert_at_ptr(dynar, dynar->used), src,
588          dynar->elmsize);
589   _dynar_unlock(dynar);
590 }
591
592 /** @brief Mark the last dynar's element as unused and return a pointer to it.
593  *
594  * You can then use regular affectation to set its value instead of relying
595  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
596  */
597 XBT_INLINE void *xbt_dynar_pop_ptr(xbt_dynar_t const dynar)
598 {
599   void *res;
600
601   _dynar_lock(dynar);
602   _check_populated_dynar(dynar);
603   XBT_DEBUG("Pop %p", (void *) dynar);
604   dynar->used--;
605   res = _xbt_dynar_elm(dynar, dynar->used);
606   _dynar_unlock(dynar);
607   return res;
608 }
609
610 /** @brief Get and remove the last element of the dynar */
611 XBT_INLINE void xbt_dynar_pop(xbt_dynar_t const dynar, void *const dst)
612 {
613
614   /* sanity checks done by remove_at */
615   XBT_DEBUG("Pop %p", (void *) dynar);
616   _dynar_lock(dynar);
617   _xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
618   _dynar_unlock(dynar);
619 }
620
621 /** @brief Add an element at the begining of the dynar.
622  *
623  * This is less efficient than xbt_dynar_push()
624  */
625 XBT_INLINE void xbt_dynar_unshift(xbt_dynar_t const dynar,
626                                   const void *const src)
627 {
628
629   /* sanity checks done by insert_at */
630   xbt_dynar_insert_at(dynar, 0, src);
631 }
632
633 /** @brief Get and remove the first element of the dynar.
634  *
635  * This is less efficient than xbt_dynar_pop()
636  */
637 XBT_INLINE void xbt_dynar_shift(xbt_dynar_t const dynar, void *const dst)
638 {
639
640   /* sanity checks done by remove_at */
641   xbt_dynar_remove_at(dynar, 0, dst);
642 }
643
644 static void _dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op)
645 {
646   char *const data = (char *) dynar->data;
647   const unsigned long elmsize = dynar->elmsize;
648   const unsigned long used = dynar->used;
649   unsigned long i;
650
651   for (i = 0; i < used; i++) {
652     char* elm = (char*) data + i * elmsize;
653     op(elm);
654   }
655 }
656
657 /** @brief Apply a function to each member of a dynar
658  *
659  * The mapped function may change the value of the element itself,
660  * but should not mess with the structure of the dynar.
661  *
662  * If the dynar is synchronized, it is locked during the whole map
663  * operation, so make sure your function don't call any function
664  * from xbt_dynar_* on it, or you'll get a deadlock.
665  */
666 XBT_INLINE void xbt_dynar_map(const xbt_dynar_t dynar,
667                               void_f_pvoid_t const op)
668 {
669
670   _sanity_check_dynar(dynar);
671   _dynar_lock(dynar);
672
673   _dynar_map(dynar, op);
674
675   _dynar_unlock(dynar);
676 }
677
678
679 /** @brief Removes and free the entry pointed by the cursor
680  *
681  * This function can be used while traversing without problem.
682  */
683 XBT_INLINE void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
684                                     unsigned int *const cursor)
685 {
686
687   _xbt_dynar_remove_at(dynar, (*cursor)--, NULL);
688 }
689
690 /** @brief Unlocks a synchronized dynar when you want to break the traversal
691  *
692  * This function must be used if you <tt>break</tt> the
693  * xbt_dynar_foreach loop, but shouldn't be called at the end of a
694  * regular traversal reaching the end of the elements
695  */
696 XBT_INLINE void xbt_dynar_cursor_unlock(xbt_dynar_t dynar)
697 {
698   _dynar_unlock(dynar);
699 }
700
701 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
702  *
703  * \param dynar the dynar to sort
704  * \param compar_fn comparison function of type (int (compar_fn*) (void*) (void*)).
705  *
706  * Remark: if the elements stored in the dynar are structures, the compar_fn
707  * function has to retrieve the field to sort first.
708  */
709 XBT_INLINE void xbt_dynar_sort(xbt_dynar_t dynar,
710                                int_f_cpvoid_cpvoid_t compar_fn)
711 {
712
713   _dynar_lock(dynar);
714
715 #ifdef HAVE_MERGESORT
716   mergesort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
717 #else
718   qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
719 #endif
720   _dynar_unlock(dynar);
721 }
722
723 /** @brief Transform a dynar into a NULL terminated array
724  *
725  * \param dynar the dynar to transform
726  */
727 XBT_INLINE void * xbt_dynar_to_array (xbt_dynar_t dynar)
728 {
729   void *res;
730   xbt_dynar_shrink(dynar, 1);
731   memset(xbt_dynar_push_ptr(dynar), 0, dynar->elmsize);
732   res = dynar->data;
733   if (dynar->mutex)
734     xbt_mutex_destroy(dynar->mutex);
735   free(dynar);
736   return res;
737 }
738
739 /*
740  * Return 0 if d1 and d2 are equal and 1 if not equal
741  */
742 XBT_INLINE int xbt_dynar_compare(xbt_dynar_t d1, xbt_dynar_t d2,
743                                         int(*compar)(const void *, const void *))
744 {
745         int i ;
746         int size;
747         if((!d1) && (!d2)) return 0;
748         if((!d1) || (!d2))
749         {
750                 XBT_DEBUG("NULL dynar d1=%p d2=%p",d1,d2);
751                 xbt_dynar_free(&d2);
752                 return 1;
753         }
754         if((d1->elmsize)!=(d2->elmsize))
755         {
756                 XBT_DEBUG("Size of elmsize d1=%lu d2=%lu",d1->elmsize,d2->elmsize);
757                 xbt_dynar_free(&d2);
758                 return 1; // xbt_die
759         }
760         if(xbt_dynar_length(d1) != xbt_dynar_length(d2))
761         {
762                 XBT_DEBUG("Size of dynar d1=%lu d2=%lu",xbt_dynar_length(d1),xbt_dynar_length(d2));
763                 xbt_dynar_free(&d2);
764                 return 1;
765         }
766
767         size = xbt_dynar_length(d1);
768         for(i=0;i<size;i++)
769         {
770                 void *data1 = xbt_dynar_get_as(d1, i, void *);
771                 void *data2 = xbt_dynar_get_as(d2, i, void *);
772                 XBT_DEBUG("link[%d] d1=%p d2=%p",i,data1,data2);
773                 if(compar(data1,data2)){
774                         xbt_dynar_free(&d2);
775                         return 1;
776                 }
777         }
778         xbt_dynar_free(&d2);
779         return 0;
780 }
781
782 #ifdef SIMGRID_TEST
783
784 #define NB_ELEM 5000
785
786 XBT_TEST_SUITE("dynar", "Dynar data container");
787 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(xbt_dyn);
788
789 XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers")
790 {
791   /* Vars_decl [doxygen cruft] */
792   xbt_dynar_t d;
793   int i, cpt;
794   unsigned int cursor;
795   int *iptr;
796
797   xbt_test_add("==== Traverse the empty dynar");
798   d = xbt_dynar_new(sizeof(int), NULL);
799   xbt_dynar_foreach(d, cursor, i) {
800     xbt_die( "Damnit, there is something in the empty dynar");
801   }
802   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
803   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
804   /* in your code is naturally the way to go outside a regression test */
805
806   xbt_test_add
807       ("==== Push %d int, set them again 3 times, traverse them, shift them",
808        NB_ELEM);
809   /* Populate_ints [doxygen cruft] */
810   /* 1. Populate the dynar */
811   d = xbt_dynar_new(sizeof(int), NULL);
812   for (cpt = 0; cpt < NB_ELEM; cpt++) {
813     xbt_dynar_push_as(d, int, cpt);     /* This is faster (and possible only with scalars) */
814     /* xbt_dynar_push(d,&cpt);       This would also work */
815     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
816   }
817
818   /* 2. Traverse manually the dynar */
819   for (cursor = 0; cursor < NB_ELEM; cursor++) {
820     iptr = xbt_dynar_get_ptr(d, cursor);
821     xbt_test_assert(cursor == *iptr,
822                      "The retrieved value is not the same than the injected one (%u!=%d)",
823                      cursor, cpt);
824   }
825
826   /* 3. Traverse the dynar using the neat macro to that extend */
827   xbt_dynar_foreach(d, cursor, cpt) {
828     xbt_test_assert(cursor == cpt,
829                      "The retrieved value is not the same than the injected one (%u!=%d)",
830                      cursor, cpt);
831   }
832   /* end_of_traversal */
833
834   for (cpt = 0; cpt < NB_ELEM; cpt++)
835     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
836
837   for (cpt = 0; cpt < NB_ELEM; cpt++)
838     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
839   /*     xbt_dynar_set(d,cpt,&cpt); */
840
841   for (cpt = 0; cpt < NB_ELEM; cpt++)
842     *(int *) xbt_dynar_get_ptr(d, cpt) = cpt;
843
844   cpt = 0;
845   xbt_dynar_foreach(d, cursor, i) {
846     xbt_test_assert(i == cpt,
847                      "The retrieved value is not the same than the injected one (%d!=%d)",
848                      i, cpt);
849     cpt++;
850   }
851   xbt_test_assert(cpt == NB_ELEM,
852                    "Cannot retrieve my %d values. Last got one is %d",
853                    NB_ELEM, cpt);
854
855   /* shifting [doxygen cruft] */
856   /* 4. Shift all the values */
857   for (cpt = 0; cpt < NB_ELEM; cpt++) {
858     xbt_dynar_shift(d, &i);
859     xbt_test_assert(i == cpt,
860                      "The retrieved value is not the same than the injected one (%d!=%d)",
861                      i, cpt);
862     xbt_test_log("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
863   }
864
865   /* 5. Free the resources */
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("==== Unshift/pop %d int", NB_ELEM);
871   d = xbt_dynar_new(sizeof(int), NULL);
872   for (cpt = 0; cpt < NB_ELEM; cpt++) {
873     xbt_dynar_unshift(d, &cpt);
874     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
875   }
876   for (cpt = 0; cpt < NB_ELEM; cpt++) {
877     i = xbt_dynar_pop_as(d, int);
878     xbt_test_assert(i == cpt,
879                      "The retrieved value is not the same than the injected one (%d!=%d)",
880                      i, cpt);
881     xbt_test_log("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
882   }
883   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
884   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
885   /* in your code is naturally the way to go outside a regression test */
886
887
888   xbt_test_add
889       ("==== Push %d int, insert 1000 int in the middle, shift everything",
890        NB_ELEM);
891   d = xbt_dynar_new(sizeof(int), NULL);
892   for (cpt = 0; cpt < NB_ELEM; cpt++) {
893     xbt_dynar_push_as(d, int, cpt);
894     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
895   }
896   for (cpt = 0; cpt < NB_ELEM/5; cpt++) {
897     xbt_dynar_insert_at_as(d, NB_ELEM/2, int, cpt);
898     XBT_DEBUG("Push %d, length=%lu", cpt, xbt_dynar_length(d));
899   }
900
901   for (cpt = 0; cpt < NB_ELEM/2; cpt++) {
902     xbt_dynar_shift(d, &i);
903     xbt_test_assert(i == cpt,
904                      "The retrieved value is not the same than the injected one at the begining (%d!=%d)",
905                      i, cpt);
906     XBT_DEBUG("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
907   }
908   for (cpt = 999; cpt >= 0; cpt--) {
909     xbt_dynar_shift(d, &i);
910     xbt_test_assert(i == cpt,
911                      "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
912                      i, cpt);
913   }
914   for (cpt = 2500; cpt < NB_ELEM; cpt++) {
915     xbt_dynar_shift(d, &i);
916     xbt_test_assert(i == cpt,
917                      "The retrieved value is not the same than the injected one at the end (%d!=%d)",
918                      i, cpt);
919   }
920   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
921   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
922   /* in your code is naturally the way to go outside a regression test */
923
924   xbt_test_add("==== Push %d int, remove 2000-4000. free the rest",
925                 NB_ELEM);
926   d = xbt_dynar_new(sizeof(int), NULL);
927   for (cpt = 0; cpt < NB_ELEM; cpt++)
928     xbt_dynar_push_as(d, int, cpt);
929
930   for (cpt = 2000; cpt < 4000; cpt++) {
931     xbt_dynar_remove_at(d, 2000, &i);
932     xbt_test_assert(i == cpt,
933                      "Remove a bad value. Got %d, expected %d", i, cpt);
934     XBT_DEBUG("remove %d, length=%lu", cpt, xbt_dynar_length(d));
935   }
936   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
937   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
938   /* in your code is naturally the way to go outside a regression test */
939 }
940
941 /*******************************************************************************/
942 /*******************************************************************************/
943 /*******************************************************************************/
944 XBT_TEST_UNIT("insert",test_dynar_insert,"Using the xbt_dynar_insert and xbt_dynar_remove functions")
945 {
946   xbt_dynar_t d = xbt_dynar_new(sizeof(unsigned int), NULL);
947   unsigned int cursor;
948   int cpt;
949
950   xbt_test_add("==== Insert %d int, traverse them, remove them",NB_ELEM);
951   /* Populate_ints [doxygen cruft] */
952   /* 1. Populate the dynar */
953   for (cpt = 0; cpt < NB_ELEM; cpt++) {
954     xbt_dynar_insert_at(d, cpt, &cpt);
955     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
956   }
957
958   /* 3. Traverse the dynar */
959   xbt_dynar_foreach(d, cursor, cpt) {
960     xbt_test_assert(cursor == cpt,
961                      "The retrieved value is not the same than the injected one (%u!=%d)",
962                      cursor, cpt);
963   }
964   /* end_of_traversal */
965
966   /* Re-fill with the same values using set_as (and re-verify) */
967   for (cpt = 0; cpt < NB_ELEM; cpt++)
968     xbt_dynar_set_as(d, cpt, int, cpt);
969   xbt_dynar_foreach(d, cursor, cpt)
970     xbt_test_assert(cursor == cpt,
971                      "The retrieved value is not the same than the injected one (%u!=%d)",
972                      cursor, cpt);
973
974   for (cpt = 0; cpt < NB_ELEM; cpt++) {
975     int val;
976     xbt_dynar_remove_at(d,0,&val);
977     xbt_test_assert(cpt == val,
978                      "The retrieved value is not the same than the injected one (%u!=%d)",
979                      cursor, cpt);
980   }
981   xbt_test_assert(xbt_dynar_is_empty(d),
982                    "There is still %lu elements in the dynar after removing everything",
983                    xbt_dynar_length(d));
984   xbt_dynar_free(&d);
985
986   /* ********************* */
987   xbt_test_add("==== Insert %d int in reverse order, traverse them, remove them",NB_ELEM);
988   d = xbt_dynar_new(sizeof(int), NULL);
989   for (cpt = NB_ELEM-1; cpt >=0; cpt--) {
990     xbt_dynar_replace(d, cpt, &cpt);
991     xbt_test_log("Push %d, length=%lu", cpt, xbt_dynar_length(d));
992   }
993
994   /* 3. Traverse the dynar */
995   xbt_dynar_foreach(d, cursor, cpt) {
996     xbt_test_assert(cursor == cpt,
997                      "The retrieved value is not the same than the injected one (%u!=%d)",
998                      cursor, cpt);
999   }
1000   /* end_of_traversal */
1001
1002   for (cpt =NB_ELEM-1; cpt >=0; cpt--) {
1003     int val;
1004     xbt_dynar_remove_at(d,xbt_dynar_length(d)-1,&val);
1005     xbt_test_assert(cpt == val,
1006                      "The retrieved value is not the same than the injected one (%u!=%d)",
1007                      cursor, cpt);
1008   }
1009   xbt_test_assert(xbt_dynar_is_empty(d),
1010                    "There is still %lu elements in the dynar after removing everything",
1011                    xbt_dynar_length(d));
1012   xbt_dynar_free(&d);
1013 }
1014
1015 /*******************************************************************************/
1016 /*******************************************************************************/
1017 /*******************************************************************************/
1018 XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles")
1019 {
1020   xbt_dynar_t d;
1021   int cpt;
1022   unsigned int cursor;
1023   double d1, d2;
1024
1025   xbt_test_add("==== Traverse the empty dynar");
1026   d = xbt_dynar_new(sizeof(int), NULL);
1027   xbt_dynar_foreach(d, cursor, cpt) {
1028     xbt_test_assert(FALSE,
1029                      "Damnit, there is something in the empty dynar");
1030   }
1031   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1032   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1033   /* in your code is naturally the way to go outside a regression test */
1034
1035   xbt_test_add("==== Push/shift 5000 doubles");
1036   d = xbt_dynar_new(sizeof(double), NULL);
1037   for (cpt = 0; cpt < 5000; cpt++) {
1038     d1 = (double) cpt;
1039     xbt_dynar_push(d, &d1);
1040   }
1041   xbt_dynar_foreach(d, cursor, d2) {
1042     d1 = (double) cursor;
1043     xbt_test_assert(d1 == d2,
1044                      "The retrieved value is not the same than the injected one (%f!=%f)",
1045                      d1, d2);
1046   }
1047   for (cpt = 0; cpt < 5000; cpt++) {
1048     d1 = (double) cpt;
1049     xbt_dynar_shift(d, &d2);
1050     xbt_test_assert(d1 == d2,
1051                      "The retrieved value is not the same than the injected one (%f!=%f)",
1052                      d1, d2);
1053   }
1054   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1055   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1056   /* in your code is naturally the way to go outside a regression test */
1057
1058   xbt_test_add("==== Unshift/pop 5000 doubles");
1059   d = xbt_dynar_new(sizeof(double), NULL);
1060   for (cpt = 0; cpt < 5000; cpt++) {
1061     d1 = (double) cpt;
1062     xbt_dynar_unshift(d, &d1);
1063   }
1064   for (cpt = 0; cpt < 5000; cpt++) {
1065     d1 = (double) cpt;
1066     xbt_dynar_pop(d, &d2);
1067     xbt_test_assert(d1 == d2,
1068                      "The retrieved value is not the same than the injected one (%f!=%f)",
1069                      d1, d2);
1070   }
1071   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1072   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1073   /* in your code is naturally the way to go outside a regression test */
1074
1075
1076
1077   xbt_test_add
1078       ("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
1079   d = xbt_dynar_new(sizeof(double), NULL);
1080   for (cpt = 0; cpt < 5000; cpt++) {
1081     d1 = (double) cpt;
1082     xbt_dynar_push(d, &d1);
1083   }
1084   for (cpt = 0; cpt < 1000; cpt++) {
1085     d1 = (double) cpt;
1086     xbt_dynar_insert_at(d, 2500, &d1);
1087   }
1088
1089   for (cpt = 0; cpt < 2500; cpt++) {
1090     d1 = (double) cpt;
1091     xbt_dynar_shift(d, &d2);
1092     xbt_test_assert(d1 == d2,
1093                      "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
1094                      d1, d2);
1095     XBT_DEBUG("Pop %d, length=%lu", cpt, xbt_dynar_length(d));
1096   }
1097   for (cpt = 999; cpt >= 0; cpt--) {
1098     d1 = (double) cpt;
1099     xbt_dynar_shift(d, &d2);
1100     xbt_test_assert(d1 == d2,
1101                      "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
1102                      d1, d2);
1103   }
1104   for (cpt = 2500; cpt < 5000; cpt++) {
1105     d1 = (double) cpt;
1106     xbt_dynar_shift(d, &d2);
1107     xbt_test_assert(d1 == d2,
1108                      "The retrieved value is not the same than the injected one at the end (%f!=%f)",
1109                      d1, d2);
1110   }
1111   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1112   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1113   /* in your code is naturally the way to go outside a regression test */
1114
1115
1116   xbt_test_add("==== Push 5000 double, remove 2000-4000. free the rest");
1117   d = xbt_dynar_new(sizeof(double), NULL);
1118   for (cpt = 0; cpt < 5000; cpt++) {
1119     d1 = (double) cpt;
1120     xbt_dynar_push(d, &d1);
1121   }
1122   for (cpt = 2000; cpt < 4000; cpt++) {
1123     d1 = (double) cpt;
1124     xbt_dynar_remove_at(d, 2000, &d2);
1125     xbt_test_assert(d1 == d2,
1126                      "Remove a bad value. Got %f, expected %f", d2, d1);
1127   }
1128   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1129   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1130   /* in your code is naturally the way to go outside a regression test */
1131 }
1132
1133
1134 /* doxygen_string_cruft */
1135
1136 /*******************************************************************************/
1137 /*******************************************************************************/
1138 /*******************************************************************************/
1139 XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings")
1140 {
1141   xbt_dynar_t d;
1142   int cpt;
1143   unsigned int iter;
1144   char buf[1024];
1145   char *s1, *s2;
1146
1147   xbt_test_add("==== Traverse the empty dynar");
1148   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1149   xbt_dynar_foreach(d, iter, s1) {
1150     xbt_test_assert(FALSE,
1151                      "Damnit, there is something in the empty dynar");
1152   }
1153   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1154   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1155   /* in your code is naturally the way to go outside a regression test */
1156
1157   xbt_test_add("==== Push %d strings, set them again 3 times, shift them",
1158                 NB_ELEM);
1159   /* Populate_str [doxygen cruft] */
1160   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1161   /* 1. Populate the dynar */
1162   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1163     sprintf(buf, "%d", cpt);
1164     s1 = strdup(buf);
1165     xbt_dynar_push(d, &s1);
1166   }
1167   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1168     sprintf(buf, "%d", cpt);
1169     s1 = strdup(buf);
1170     xbt_dynar_replace(d, cpt, &s1);
1171   }
1172   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1173     sprintf(buf, "%d", cpt);
1174     s1 = strdup(buf);
1175     xbt_dynar_replace(d, cpt, &s1);
1176   }
1177   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1178     sprintf(buf, "%d", cpt);
1179     s1 = strdup(buf);
1180     xbt_dynar_replace(d, cpt, &s1);
1181   }
1182   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1183     sprintf(buf, "%d", cpt);
1184     xbt_dynar_shift(d, &s2);
1185     xbt_test_assert(!strcmp(buf, s2),
1186                      "The retrieved value is not the same than the injected one (%s!=%s)",
1187                      buf, s2);
1188     free(s2);
1189   }
1190   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1191   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1192   /* in your code is naturally the way to go outside a regression test */
1193
1194   xbt_test_add("==== Unshift, traverse and pop %d strings", NB_ELEM);
1195   d = xbt_dynar_new(sizeof(char **), &xbt_free_ref);
1196   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1197     sprintf(buf, "%d", cpt);
1198     s1 = strdup(buf);
1199     xbt_dynar_unshift(d, &s1);
1200   }
1201   /* 2. Traverse the dynar with the macro */
1202   xbt_dynar_foreach(d, iter, s1) {
1203     sprintf(buf, "%u", NB_ELEM - iter - 1);
1204     xbt_test_assert(!strcmp(buf, s1),
1205                      "The retrieved value is not the same than the injected one (%s!=%s)",
1206                      buf, s1);
1207   }
1208   /* 3. Traverse the dynar with the macro */
1209   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1210     sprintf(buf, "%d", cpt);
1211     xbt_dynar_pop(d, &s2);
1212     xbt_test_assert(!strcmp(buf, s2),
1213                      "The retrieved value is not the same than the injected one (%s!=%s)",
1214                      buf, s2);
1215     free(s2);
1216   }
1217   /* 4. Free the resources */
1218   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1219   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1220   /* in your code is naturally the way to go outside a regression test */
1221
1222
1223   xbt_test_add
1224       ("==== Push %d strings, insert %d strings in the middle, shift everything",
1225        NB_ELEM, NB_ELEM / 5);
1226   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1227   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1228     sprintf(buf, "%d", cpt);
1229     s1 = strdup(buf);
1230     xbt_dynar_push(d, &s1);
1231   }
1232   for (cpt = 0; cpt < NB_ELEM / 5; cpt++) {
1233     sprintf(buf, "%d", cpt);
1234     s1 = strdup(buf);
1235     xbt_dynar_insert_at(d, NB_ELEM / 2, &s1);
1236   }
1237
1238   for (cpt = 0; cpt < NB_ELEM / 2; cpt++) {
1239     sprintf(buf, "%d", cpt);
1240     xbt_dynar_shift(d, &s2);
1241     xbt_test_assert(!strcmp(buf, s2),
1242                      "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
1243                      buf, s2);
1244     free(s2);
1245   }
1246   for (cpt = (NB_ELEM / 5) - 1; cpt >= 0; cpt--) {
1247     sprintf(buf, "%d", cpt);
1248     xbt_dynar_shift(d, &s2);
1249     xbt_test_assert(!strcmp(buf, s2),
1250                      "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
1251                      buf, s2);
1252     free(s2);
1253   }
1254   for (cpt = NB_ELEM / 2; cpt < NB_ELEM; cpt++) {
1255     sprintf(buf, "%d", cpt);
1256     xbt_dynar_shift(d, &s2);
1257     xbt_test_assert(!strcmp(buf, s2),
1258                      "The retrieved value is not the same than the injected one at the end (%s!=%s)",
1259                      buf, s2);
1260     free(s2);
1261   }
1262   xbt_dynar_free(&d);           /* This code is used both as example and as regression test, so we try to */
1263   xbt_dynar_free(&d);           /* free the struct twice here to check that it's ok, but freeing  it only once */
1264   /* in your code is naturally the way to go outside a regression test */
1265
1266
1267   xbt_test_add("==== Push %d strings, remove %d-%d. free the rest",
1268                 NB_ELEM, 2 * (NB_ELEM / 5), 4 * (NB_ELEM / 5));
1269   d = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
1270   for (cpt = 0; cpt < NB_ELEM; cpt++) {
1271     sprintf(buf, "%d", cpt);
1272     s1 = strdup(buf);
1273     xbt_dynar_push(d, &s1);
1274   }
1275   for (cpt = 2 * (NB_ELEM / 5); cpt < 4 * (NB_ELEM / 5); cpt++) {
1276     sprintf(buf, "%d", cpt);
1277     xbt_dynar_remove_at(d, 2 * (NB_ELEM / 5), &s2);
1278     xbt_test_assert(!strcmp(buf, s2),
1279                      "Remove a bad value. Got %s, expected %s", s2, buf);
1280     free(s2);
1281   }
1282   xbt_dynar_free(&d);           /* end_of_doxygen */
1283 }
1284
1285
1286 /*******************************************************************************/
1287 /*******************************************************************************/
1288 /*******************************************************************************/
1289 #include "xbt/synchro.h"
1290 static void pusher_f(void *a)
1291 {
1292   xbt_dynar_t d = (xbt_dynar_t) a;
1293   int i;
1294   for (i = 0; i < 500; i++) {
1295     xbt_dynar_push(d, &i);
1296   }
1297 }
1298
1299 static void poper_f(void *a)
1300 {
1301   xbt_dynar_t d = (xbt_dynar_t) a;
1302   volatile int i;
1303   int data;
1304   xbt_ex_t e;
1305
1306   for (i = 0; i < 500; i++) {
1307     TRY {
1308       xbt_dynar_pop(d, &data);
1309     }
1310     CATCH(e) {
1311       if (e.category == bound_error) {
1312         xbt_ex_free(e);
1313         i--;
1314       } else {
1315         RETHROW;
1316       }
1317     }
1318   }
1319 }
1320
1321
1322 XBT_TEST_UNIT("synchronized int", test_dynar_sync_int, "Synchronized dynars of integers")
1323 {
1324   /* Vars_decl [doxygen cruft] */
1325   xbt_dynar_t d;
1326   xbt_thread_t pusher, poper;
1327
1328   xbt_test_add("==== Have a pusher and a popper on the dynar");
1329   d = xbt_dynar_new_sync(sizeof(int), NULL);
1330   pusher = xbt_thread_create("pusher", pusher_f, d, 0 /*not joinable */ );
1331   poper = xbt_thread_create("poper", poper_f, d, 0 /*not joinable */ );
1332   xbt_thread_join(pusher);
1333   xbt_thread_join(poper);
1334   xbt_dynar_free(&d);
1335 }
1336
1337 #endif                          /* SIMGRID_TEST */