Logo AND Algorithmique Numérique Distribuée

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