Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
ab89031e2228e82662ca9b5d49a48a7f1f1b16b1
[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 */