Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
* Check that sem_timedwait is available (since it's not on mac osx)
[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_lock(dynar->mutex)
31 #define _dynar_unlock(dynar) \
32            if (dynar->mutex) \
33               xbt_mutex_unlock(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 %d 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   return xbt_dynar_insert_at_ptr(dynar, dynar->used);    
557 }
558
559 /** @brief Add an element at the end of the dynar */
560 void
561 xbt_dynar_push(xbt_dynar_t  const dynar,
562                 const void   * const src) {
563   /* sanity checks done by insert_at */
564   xbt_dynar_insert_at(dynar, dynar->used, src); 
565 }
566
567 /** @brief Mark the last dynar's element as unused and return a pointer to it.
568  *
569  * You can then use regular affectation to set its value instead of relying 
570  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
571  */
572 void *
573 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
574   void *res;
575    
576   _dynar_lock(dynar);
577   _check_populated_dynar(dynar);
578   DEBUG1("Pop %p",(void*)dynar);
579   dynar->used--;
580   res = _xbt_dynar_elm(dynar,dynar->used);
581   _dynar_unlock(dynar);
582   return res;
583 }
584
585 /** @brief Get and remove the last element of the dynar */
586 void
587 xbt_dynar_pop(xbt_dynar_t  const dynar,
588               void         * const dst) {
589
590   /* sanity checks done by remove_at */
591   DEBUG1("Pop %p",(void*)dynar);
592   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
593 }
594
595 /** @brief Add an element at the begining of the dynar.
596  *
597  * This is less efficient than xbt_dynar_push()
598  */
599 void
600 xbt_dynar_unshift(xbt_dynar_t  const dynar,
601                    const void   * const src) {
602   
603   /* sanity checks done by insert_at */
604   xbt_dynar_insert_at(dynar, 0, src);
605 }
606
607 /** @brief Get and remove the first element of the dynar.
608  *
609  * This is less efficient than xbt_dynar_pop()
610  */
611 void
612 xbt_dynar_shift(xbt_dynar_t  const dynar,
613                  void         * const dst) {
614
615   /* sanity checks done by remove_at */
616   xbt_dynar_remove_at(dynar, 0, dst);
617 }
618
619 static void _dynar_map(const xbt_dynar_t  dynar,
620                        void_f_pvoid_t     const op) {
621   char         elm[SIZEOF_MAX];
622   const unsigned long used = dynar->used;
623   unsigned long       i    = 0;
624
625   for (i = 0; i < used; i++) {
626     _xbt_dynar_get_elm(elm, dynar, i);
627     (*op)(elm);
628   }
629 }
630
631 /** @brief Apply a function to each member of a dynar
632  *
633  * The mapped function may change the value of the element itself, 
634  * but should not mess with the structure of the dynar. 
635  *
636  * If the dynar is synchronized, it is locked during the whole map
637  * operation, so make sure your function don't call any function 
638  * from xbt_dynar_* on it, or you'll get a deadlock.
639  */
640 void
641 xbt_dynar_map(const xbt_dynar_t  dynar,
642                void_f_pvoid_t     const op) {
643
644   _dynar_lock(dynar);
645   _sanity_check_dynar(dynar);
646
647   _dynar_map(dynar,op);
648
649   _dynar_unlock(dynar);
650 }
651
652 /** @brief Put the cursor at the begining of the dynar.
653  *
654  * Actually, the cursor is set one step before the begining, so that you
655  * can iterate over the dynar with a for loop. 
656  *
657  * @warning Do not call this function directly, but only through xbt_dynar_foreach.
658  */
659 void
660 _xbt_dynar_cursor_first(const xbt_dynar_t dynar,
661                        int        * const cursor) {
662
663   _dynar_lock(dynar);
664   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
665   *cursor = 0;
666 }
667
668 /** @brief Move the cursor to the next value 
669  *
670  * @warning Do not call this function directly, but only through xbt_dynar_foreach.
671  */
672 void
673 _xbt_dynar_cursor_step(const xbt_dynar_t dynar,
674                        int        * const cursor) {
675   
676   (*cursor)++;
677 }
678
679 /** @brief Get the data currently pointed by the cursor
680  * 
681  * @warning Do not call this function directly, but only through xbt_dynar_foreach.
682  */
683 int
684 _xbt_dynar_cursor_get(const xbt_dynar_t dynar,
685                       int                * const cursor,
686                       void               * const dst) {
687
688   _sanity_check_dynar(dynar);
689   {
690
691     const unsigned long idx = *cursor;
692
693     if (idx >= dynar->used) {
694       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
695       _dynar_unlock(dynar);
696       return FALSE;
697     }
698     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
699
700     _xbt_dynar_get_elm(dst, dynar, idx);
701   }
702   return TRUE;
703
704 }
705
706 /** @brief Removes and free the entry pointed by the cursor 
707  *
708  * This function can be used while traversing without problem.
709  */
710 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
711                           int          * const cursor) {
712   
713   _xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
714 }
715
716 /** @brief Unlocks a synchronized dynar when you want to break the traversal
717  *
718  * This function must be used if you <tt>break</tt> the
719  * xbt_dynar_foreach loop, but shouldn't be called at the end of a
720  * regular traversal reaching the end of the elements
721  */
722 void xbt_dynar_cursor_unlock(xbt_dynar_t dynar) {
723   _dynar_unlock(dynar);
724 }
725
726 #ifdef SIMGRID_TEST
727
728 #define NB_ELEM 5000
729
730 XBT_TEST_SUITE("dynar","Dynar data container");
731 XBT_LOG_EXTERNAL_CATEGORY(xbt_dyn);
732 XBT_LOG_DEFAULT_CATEGORY(xbt_dyn);
733
734 XBT_TEST_UNIT("int",test_dynar_int,"Dynars of integers") {
735    /* Vars_decl [doxygen cruft] */
736    xbt_dynar_t d;
737    int i,cpt,cursor;
738    int *iptr;
739    
740    xbt_test_add0("==== Traverse the empty dynar");
741    d=xbt_dynar_new(sizeof(int),NULL);
742    xbt_dynar_foreach(d,cursor,i){
743      xbt_assert0(0,"Damnit, there is something in the empty dynar");
744    }
745    xbt_dynar_free(&d);
746    xbt_dynar_free(&d);
747
748    xbt_test_add1("==== Push %d int, set them again 3 times, traverse them, shift them",
749         NB_ELEM);
750    /* Populate_ints [doxygen cruft] */
751    /* 1. Populate the dynar */
752    d=xbt_dynar_new(sizeof(int),NULL);
753    for (cpt=0; cpt< NB_ELEM; cpt++) {
754      xbt_dynar_push_as(d,int,cpt); /* This is faster (and possible only with scalars) */
755      /* xbt_dynar_push(d,&cpt);       This would also work */
756      xbt_test_log2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
757    }
758    
759    /* 2. Traverse manually the dynar */
760    for (cursor=0; cursor< NB_ELEM; cursor++) {
761      iptr=xbt_dynar_get_ptr(d,cursor);
762      xbt_test_assert2(cursor == *iptr,
763                       "The retrieved value is not the same than the injected one (%d!=%d)",
764                       cursor,cpt);
765    }
766    
767    /* 3. Traverse the dynar using the neat macro to that extend */
768    xbt_dynar_foreach(d,cursor,cpt){
769      xbt_test_assert2(cursor == cpt,
770                       "The retrieved value is not the same than the injected one (%d!=%d)",
771                       cursor,cpt);
772    }
773    /* end_of_traversal */
774    
775    for (cpt=0; cpt< NB_ELEM; cpt++)
776      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
777
778    for (cpt=0; cpt< NB_ELEM; cpt++) 
779      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
780 /*     xbt_dynar_set(d,cpt,&cpt);*/
781    
782    for (cpt=0; cpt< NB_ELEM; cpt++) 
783      *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
784    
785    cpt=0;
786    xbt_dynar_foreach(d,cursor,i){
787      xbt_test_assert2(i == cpt,
788                       "The retrieved value is not the same than the injected one (%d!=%d)",
789                       i,cpt);
790      cpt++;
791    }
792    xbt_test_assert2(cpt == NB_ELEM,
793                     "Cannot retrieve my %d values. Last got one is %d",
794                     NB_ELEM, cpt);
795
796    /* shifting [doxygen cruft] */
797    /* 4. Shift all the values */
798    for (cpt=0; cpt< NB_ELEM; cpt++) {
799      xbt_dynar_shift(d,&i);
800      xbt_test_assert2(i == cpt,
801                       "The retrieved value is not the same than the injected one (%d!=%d)",
802                       i,cpt);
803      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
804    }
805    
806    /* 5. Free the resources */
807    xbt_dynar_free(&d);
808    xbt_dynar_free(&d);
809
810    
811    xbt_test_add1("==== Unshift/pop %d int",NB_ELEM);
812    d=xbt_dynar_new(sizeof(int),NULL);
813    for (cpt=0; cpt< NB_ELEM; cpt++) {
814      xbt_dynar_unshift(d,&cpt);
815      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
816    }
817    for (cpt=0; cpt< NB_ELEM; cpt++) {
818      i=xbt_dynar_pop_as(d,int);
819      xbt_test_assert2(i == cpt,
820                       "The retrieved value is not the same than the injected one (%d!=%d)",
821                       i,cpt);
822      xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
823    }
824    xbt_dynar_free(&d);
825    xbt_dynar_free(&d);
826
827    
828    xbt_test_add1("==== Push %d int, insert 1000 int in the middle, shift everything",NB_ELEM);
829    d=xbt_dynar_new(sizeof(int),NULL);
830    for (cpt=0; cpt< NB_ELEM; cpt++) {
831      xbt_dynar_push_as(d,int,cpt);
832      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
833    }
834    for (cpt=0; cpt< 1000; cpt++) {
835      xbt_dynar_insert_at_as(d,2500,int,cpt);
836      DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
837    }
838
839    for (cpt=0; cpt< 2500; cpt++) {
840      xbt_dynar_shift(d,&i);
841      xbt_test_assert2(i == cpt,
842              "The retrieved value is not the same than the injected one at the begining (%d!=%d)",
843                i,cpt);
844      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
845    }
846    for (cpt=999; cpt>=0; cpt--) {
847      xbt_dynar_shift(d,&i);
848      xbt_test_assert2(i == cpt,
849            "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
850                       i,cpt);
851    }
852    for (cpt=2500; cpt< NB_ELEM; cpt++) {
853      xbt_dynar_shift(d,&i);
854       xbt_test_assert2(i == cpt,
855            "The retrieved value is not the same than the injected one at the end (%d!=%d)",
856                        i,cpt);
857    }
858    xbt_dynar_free(&d);
859    xbt_dynar_free(&d);
860
861
862    xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest",NB_ELEM);
863    d=xbt_dynar_new(sizeof(int),NULL);
864    for (cpt=0; cpt< NB_ELEM; cpt++) 
865      xbt_dynar_push_as(d,int,cpt);
866    
867    for (cpt=2000; cpt< 4000; cpt++) {
868      xbt_dynar_remove_at(d,2000,&i);
869      xbt_test_assert2(i == cpt,
870                       "Remove a bad value. Got %d, expected %d",
871                       i,cpt);
872      DEBUG2("remove %d, length=%lu",cpt, xbt_dynar_length(d));
873    }
874    xbt_dynar_free(&d);
875    xbt_dynar_free(&d);
876 }
877 /*******************************************************************************/
878 /*******************************************************************************/
879 /*******************************************************************************/
880 XBT_TEST_UNIT("double",test_dynar_double,"Dynars of doubles") {
881    xbt_dynar_t d;
882    int cpt,cursor;
883    double d1,d2;
884    
885    xbt_test_add0("==== Traverse the empty dynar");
886    d=xbt_dynar_new(sizeof(int),NULL);
887    xbt_dynar_foreach(d,cursor,cpt){
888      xbt_test_assert0(FALSE,
889              "Damnit, there is something in the empty dynar");
890    }
891    xbt_dynar_free(&d);
892    xbt_dynar_free(&d);
893
894    xbt_test_add0("==== Push/shift 5000 doubles");
895    d=xbt_dynar_new(sizeof(double),NULL);
896    for (cpt=0; cpt< 5000; cpt++) {
897      d1=(double)cpt;
898      xbt_dynar_push(d,&d1);
899    }
900    xbt_dynar_foreach(d,cursor,d2){
901      d1=(double)cursor;
902      xbt_test_assert2(d1 == d2,
903            "The retrieved value is not the same than the injected one (%f!=%f)",
904                   d1,d2);
905    }
906    for (cpt=0; cpt< 5000; cpt++) {
907      d1=(double)cpt;
908      xbt_dynar_shift(d,&d2);
909      xbt_test_assert2(d1 == d2,
910            "The retrieved value is not the same than the injected one (%f!=%f)",
911                   d1,d2);
912    }
913    xbt_dynar_free(&d);
914    xbt_dynar_free(&d);
915
916
917    xbt_test_add0("==== Unshift/pop 5000 doubles");
918    d=xbt_dynar_new(sizeof(double),NULL);
919    for (cpt=0; cpt< 5000; cpt++) {
920      d1=(double)cpt;
921      xbt_dynar_unshift(d,&d1);
922    }
923    for (cpt=0; cpt< 5000; cpt++) {
924      d1=(double)cpt;
925      xbt_dynar_pop(d,&d2);
926      xbt_test_assert2 (d1 == d2,
927            "The retrieved value is not the same than the injected one (%f!=%f)",
928                    d1,d2);
929    }
930    xbt_dynar_free(&d);
931    xbt_dynar_free(&d);
932
933
934
935    xbt_test_add0("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
936    d=xbt_dynar_new(sizeof(double),NULL);
937    for (cpt=0; cpt< 5000; cpt++) {
938      d1=(double)cpt;
939      xbt_dynar_push(d,&d1);
940    }
941    for (cpt=0; cpt< 1000; cpt++) {
942      d1=(double)cpt;
943      xbt_dynar_insert_at(d,2500,&d1);
944    }
945
946    for (cpt=0; cpt< 2500; cpt++) {
947      d1=(double)cpt;
948      xbt_dynar_shift(d,&d2);
949      xbt_test_assert2(d1 == d2,
950            "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
951                   d1,d2);
952      DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
953    }
954    for (cpt=999; cpt>=0; cpt--) {
955      d1=(double)cpt;
956      xbt_dynar_shift(d,&d2);
957      xbt_test_assert2 (d1 == d2,
958            "The retrieved value is not the same than the injected one in the middle (%f!=%f)",
959                    d1,d2);
960    }
961    for (cpt=2500; cpt< 5000; cpt++) {
962      d1=(double)cpt;
963      xbt_dynar_shift(d,&d2);
964      xbt_test_assert2 (d1 == d2,
965            "The retrieved value is not the same than the injected one at the end (%f!=%f)",
966                    d1,d2);
967    }
968    xbt_dynar_free(&d);
969    xbt_dynar_free(&d);
970
971
972    xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest");
973    d=xbt_dynar_new(sizeof(double),NULL);
974    for (cpt=0; cpt< 5000; cpt++) {
975      d1=(double)cpt;
976      xbt_dynar_push(d,&d1);
977    }
978    for (cpt=2000; cpt< 4000; cpt++) {
979      d1=(double)cpt;
980      xbt_dynar_remove_at(d,2000,&d2);
981      xbt_test_assert2 (d1 == d2,
982            "Remove a bad value. Got %f, expected %f",
983                d2,d1);
984    }
985    xbt_dynar_free(&d);
986    xbt_dynar_free(&d);
987 }
988
989
990 /* doxygen_string_cruft */
991
992 /* The function we will use to free the data */
993 static void free_string(void *d){
994   free(*(void**)d);
995 }
996
997 /*******************************************************************************/
998 /*******************************************************************************/
999 /*******************************************************************************/
1000 XBT_TEST_UNIT("string",test_dynar_string,"Dyars of strings") {
1001    xbt_dynar_t d;
1002    int cpt;
1003    char buf[1024];
1004    char *s1,*s2;
1005    
1006    xbt_test_add0("==== Traverse the empty dynar");
1007    d=xbt_dynar_new(sizeof(char *),&free_string);
1008    xbt_dynar_foreach(d,cpt,s1){
1009      xbt_test_assert0(FALSE,
1010                   "Damnit, there is something in the empty dynar");
1011    }
1012    xbt_dynar_free(&d);
1013    xbt_dynar_free(&d);
1014
1015    xbt_test_add1("==== Push %d strings, set them again 3 times, shift them",NB_ELEM);
1016    /* Populate_str [doxygen cruft] */
1017    d=xbt_dynar_new(sizeof(char*),&free_string);
1018    /* 1. Populate the dynar */
1019    for (cpt=0; cpt< NB_ELEM; cpt++) {
1020      sprintf(buf,"%d",cpt);
1021      s1=strdup(buf);
1022      xbt_dynar_push(d,&s1);
1023    }
1024    for (cpt=0; cpt< NB_ELEM; cpt++) {
1025      sprintf(buf,"%d",cpt);
1026      s1=strdup(buf);
1027      xbt_dynar_replace(d,cpt,&s1);
1028    }
1029    for (cpt=0; cpt< NB_ELEM; cpt++) {
1030      sprintf(buf,"%d",cpt);
1031      s1=strdup(buf);
1032      xbt_dynar_replace(d,cpt,&s1);
1033    }
1034    for (cpt=0; cpt< NB_ELEM; cpt++) {
1035      sprintf(buf,"%d",cpt);
1036      s1=strdup(buf);
1037      xbt_dynar_replace(d,cpt,&s1);
1038    }
1039    for (cpt=0; cpt< NB_ELEM; cpt++) {
1040      sprintf(buf,"%d",cpt);
1041      xbt_dynar_shift(d,&s2);
1042      xbt_test_assert2 (!strcmp(buf,s2),
1043             "The retrieved value is not the same than the injected one (%s!=%s)",
1044                    buf,s2);
1045      free(s2);
1046    }
1047    xbt_dynar_free(&d);
1048    xbt_dynar_free(&d);
1049
1050
1051    xbt_test_add1("==== Unshift, traverse and pop %d strings",NB_ELEM);
1052    d=xbt_dynar_new(sizeof(char**),&free_string);
1053    for (cpt=0; cpt< NB_ELEM; cpt++) {
1054      sprintf(buf,"%d",cpt);
1055      s1=strdup(buf);
1056      xbt_dynar_unshift(d,&s1);
1057    }
1058    /* 2. Traverse the dynar with the macro */
1059    xbt_dynar_foreach(d,cpt,s1) {
1060      sprintf(buf,"%d",NB_ELEM - cpt -1);
1061      xbt_test_assert2 (!strcmp(buf,s1),
1062            "The retrieved value is not the same than the injected one (%s!=%s)",
1063                buf,s1);
1064    }
1065    /* 3. Traverse the dynar with the macro */
1066    for (cpt=0; cpt< NB_ELEM; cpt++) {
1067      sprintf(buf,"%d",cpt);
1068      xbt_dynar_pop(d,&s2);
1069      xbt_test_assert2 (!strcmp(buf,s2),
1070            "The retrieved value is not the same than the injected one (%s!=%s)",
1071                buf,s2);
1072      free(s2);
1073    }
1074    /* 4. Free the resources */
1075    xbt_dynar_free(&d);
1076    xbt_dynar_free(&d);
1077
1078
1079    xbt_test_add2("==== Push %d strings, insert %d strings in the middle, shift everything",NB_ELEM,NB_ELEM/5);
1080    d=xbt_dynar_new(sizeof(char*),&free_string);
1081    for (cpt=0; cpt< NB_ELEM; cpt++) {
1082      sprintf(buf,"%d",cpt);
1083      s1=strdup(buf);
1084      xbt_dynar_push(d,&s1);
1085    }
1086    for (cpt=0; cpt< NB_ELEM/5; cpt++) {
1087      sprintf(buf,"%d",cpt);
1088      s1=strdup(buf);
1089      xbt_dynar_insert_at(d,NB_ELEM/2,&s1);
1090    }
1091
1092    for (cpt=0; cpt< NB_ELEM/2; cpt++) {
1093      sprintf(buf,"%d",cpt);
1094      xbt_dynar_shift(d,&s2);
1095      xbt_test_assert2(!strcmp(buf,s2),
1096            "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
1097                buf,s2);
1098       free(s2);
1099    }
1100    for (cpt=(NB_ELEM/5)-1; cpt>=0; cpt--) {
1101      sprintf(buf,"%d",cpt);
1102      xbt_dynar_shift(d,&s2);
1103      xbt_test_assert2 (!strcmp(buf,s2),
1104            "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
1105                buf,s2);
1106      free(s2);
1107    }
1108    for (cpt=NB_ELEM/2; cpt< NB_ELEM; cpt++) {
1109      sprintf(buf,"%d",cpt);
1110      xbt_dynar_shift(d,&s2);
1111      xbt_test_assert2 (!strcmp(buf,s2),
1112            "The retrieved value is not the same than the injected one at the end (%s!=%s)",
1113                buf,s2);
1114      free(s2);
1115    }
1116    xbt_dynar_free(&d);
1117    xbt_dynar_free(&d);
1118
1119
1120    xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest",NB_ELEM,2*(NB_ELEM/5),4*(NB_ELEM/5));
1121    d=xbt_dynar_new(sizeof(char*),&free_string);
1122    for (cpt=0; cpt< NB_ELEM; cpt++) {
1123      sprintf(buf,"%d",cpt);
1124      s1=strdup(buf);
1125      xbt_dynar_push(d,&s1);
1126    }
1127    for (cpt=2*(NB_ELEM/5); cpt< 4*(NB_ELEM/5); cpt++) {
1128      sprintf(buf,"%d",cpt);
1129      xbt_dynar_remove_at(d,2*(NB_ELEM/5),&s2);
1130      xbt_test_assert2(!strcmp(buf,s2),
1131                   "Remove a bad value. Got %s, expected %s",
1132                   s2,buf);
1133       free(s2);
1134    }
1135    xbt_dynar_free(&d); /* end_of_doxygen */
1136 }
1137
1138
1139 /*******************************************************************************/
1140 /*******************************************************************************/
1141 /*******************************************************************************/
1142 #include "xbt/synchro.h"
1143 static void pusher_f(void *a) {
1144    xbt_dynar_t d=(xbt_dynar_t)a;
1145    int i;
1146    for (i=0; i<500; i++) {
1147       xbt_dynar_push(d,&i);
1148    }
1149 }
1150 static void poper_f(void *a) {
1151    xbt_dynar_t d=(xbt_dynar_t)a;
1152    int i;
1153    int data;
1154    xbt_ex_t e;
1155    
1156    for (i=0; i<500; i++) {
1157       TRY {      
1158          xbt_dynar_pop(d,&data);
1159       } CATCH(e) {
1160          if (e.category == bound_error) {
1161             xbt_ex_free(e);
1162             i--;
1163          } else {
1164             RETHROW;
1165          }
1166       }
1167    }
1168 }
1169
1170    
1171 XBT_TEST_UNIT("synchronized int",test_dynar_sync_int,"Synchronized dynars of integers") {
1172    /* Vars_decl [doxygen cruft] */
1173    xbt_dynar_t d;
1174    xbt_thread_t pusher,poper;
1175    
1176    xbt_test_add0("==== Have a pusher and a popper on the dynar");
1177    d=xbt_dynar_new_sync(sizeof(int),NULL);
1178    pusher = xbt_thread_create("pusher",pusher_f,d);
1179    poper = xbt_thread_create("poper",poper_f,d);
1180    xbt_thread_join(pusher);
1181    xbt_thread_join(poper);
1182    xbt_dynar_free(&d);
1183 }
1184
1185 #endif /* SIMGRID_TEST */