3 /* a generic DYNamic ARray implementation. */
5 /* Copyright (c) 2003, 2004 Martin Quinson. All rights reserved. */
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. */
10 #include "portable.h" /* SIZEOF_MAX */
12 #include "xbt/sysdep.h"
15 #include "xbt/dynar.h"
16 #include <sys/types.h>
18 #include "xbt/dynar_private.h" /* type definition, which we share with the
19 code in charge of sending this across the net */
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.
26 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dyn,xbt,"Dynamic arrays");
28 static XBT_INLINE void _dynar_lock(xbt_dynar_t dynar) {
30 xbt_mutex_acquire(dynar->mutex);
32 static XBT_INLINE void _dynar_unlock(xbt_dynar_t dynar) {
34 xbt_mutex_release(dynar->mutex);
36 static XBT_INLINE void _sanity_check_dynar(xbt_dynar_t dynar) {
37 xbt_assert0(dynar, "dynar is NULL");
39 static XBT_INLINE void _sanity_check_idx(int idx) {
40 xbt_assert1(idx >= 0, "dynar idx(=%d) < 0", (int) (idx));
43 static XBT_INLINE void _check_inbound_idx(xbt_dynar_t dynar, int idx) {
44 if (idx<0 || idx>=dynar->used) {
46 THROW2(bound_error,idx,
47 "dynar is not that long. You asked %d, but it's only %lu long",
48 (int) (idx), (unsigned long) dynar->used);
51 static XBT_INLINE void _check_sloppy_inbound_idx(xbt_dynar_t dynar, int idx) {
52 if (idx > dynar->used) {
54 THROW2(bound_error,idx,
55 "dynar is not that long. You asked %d, but it's only %lu long (could have been equal to it)",
56 (int) (idx), (unsigned long) dynar->used);
59 static XBT_INLINE void _check_populated_dynar(xbt_dynar_t dynar) {
60 if (dynar->used == 0) {
62 THROW1(bound_error,0, "dynar %p is empty", dynar);
66 static void _dynar_map(const xbt_dynar_t dynar,
67 void_f_pvoid_t const op);
70 void _xbt_clear_mem(void * const ptr,
71 const unsigned long length) {
72 memset(ptr, 0, length);
77 _xbt_dynar_expand(xbt_dynar_t const dynar,
78 const unsigned long nb) {
79 const unsigned long old_size = dynar->size;
82 char * const old_data = (char *) dynar->data;
84 const unsigned long elmsize = dynar->elmsize;
85 const unsigned long old_length = old_size*elmsize;
87 const unsigned long used = dynar->used;
88 const unsigned long used_length = used*elmsize;
90 const unsigned long new_size = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
91 const unsigned long new_length = new_size*elmsize;
92 char * const new_data = (char *) xbt_malloc0(elmsize*new_size);
94 DEBUG3("expend %p from %lu to %lu elements", (void*)dynar, (unsigned long)old_size, nb);
97 memcpy(new_data, old_data, used_length);
98 _xbt_clear_mem(old_data, old_length);
102 _xbt_clear_mem(new_data + used_length, new_length - used_length);
104 dynar->size = new_size;
105 dynar->data = new_data;
111 _xbt_dynar_elm(const xbt_dynar_t dynar,
112 const unsigned long idx) {
113 char * const data = (char*) dynar->data;
114 const unsigned long elmsize = dynar->elmsize;
116 return data + idx*elmsize;
121 _xbt_dynar_get_elm(void * const dst,
122 const xbt_dynar_t dynar,
123 const unsigned long idx) {
124 void * const elm = _xbt_dynar_elm(dynar, idx);
126 memcpy(dst, elm, dynar->elmsize);
131 _xbt_dynar_put_elm(const xbt_dynar_t dynar,
132 const unsigned long idx,
133 const void * const src) {
134 void * const elm = _xbt_dynar_elm(dynar, idx);
135 const unsigned long elmsize = dynar->elmsize;
137 memcpy(elm, src, elmsize);
142 _xbt_dynar_remove_at(xbt_dynar_t const dynar,
143 const unsigned long idx,
144 void * const object) {
146 unsigned long nb_shift;
147 unsigned long offset;
149 _sanity_check_dynar(dynar);
150 _check_inbound_idx(dynar, idx);
153 _xbt_dynar_get_elm(object, dynar, idx);
154 } else if (dynar->free_f) {
155 if (dynar->elmsize <= SIZEOF_MAX) {
156 char elm[SIZEOF_MAX];
157 _xbt_dynar_get_elm(elm, dynar, idx);
158 (*dynar->free_f)(elm);
160 char *elm=malloc(dynar->elmsize);
161 _xbt_dynar_get_elm(elm, dynar, idx);
162 (*dynar->free_f)(elm);
167 nb_shift = dynar->used-1 - idx;
168 offset = nb_shift * dynar->elmsize;
170 memmove(_xbt_dynar_elm(dynar, idx),
171 _xbt_dynar_elm(dynar, idx+1),
178 xbt_dynar_dump(xbt_dynar_t dynar) {
179 INFO5("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
180 dynar->size, dynar->used, dynar->elmsize, dynar->data, dynar->free_f);
183 /** @brief Constructor
185 * \param elmsize size of each element in the dynar
186 * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
188 * Creates a new dynar. If a free_func is provided, the elements have to be
189 * pointer of pointer. That is to say that dynars can contain either base
190 * types (int, char, double, etc) or pointer of pointers (struct **).
193 xbt_dynar_new(const unsigned long elmsize,
194 void_f_pvoid_t const free_f) {
196 xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
200 dynar->elmsize = elmsize;
202 dynar->free_f = free_f;
208 /** @brief Creates a synchronized dynar.
210 * Just like #xbt_dynar_new, but each access to the structure will be protected by a mutex
214 xbt_dynar_new_sync(const unsigned long elmsize,
215 void_f_pvoid_t const free_f) {
216 xbt_dynar_t res = xbt_dynar_new(elmsize,free_f);
217 res->mutex = xbt_mutex_init();
221 /** @brief Destructor of the structure not touching to the content
223 * \param dynar poor victim
225 * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
226 * is not touched (the \a free_f function is not used)
229 xbt_dynar_free_container(xbt_dynar_t *dynar) {
230 if (dynar && *dynar) {
232 if ((*dynar)->data) {
233 _xbt_clear_mem((*dynar)->data, (*dynar)->size);
234 free((*dynar)->data);
238 xbt_mutex_destroy((*dynar)->mutex);
240 _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
247 /** @brief Frees the content and set the size to 0
249 * \param dynar who to squeeze
252 xbt_dynar_reset(xbt_dynar_t const dynar) {
255 _sanity_check_dynar(dynar);
257 DEBUG1("Reset the dynar %p",(void*)dynar);
259 _dynar_map(dynar, dynar->free_f);
269 _dynar_unlock(dynar);
271 /* dynar->data = NULL;*/
275 * \brief Shrink the dynar by removing empty slots at the end of the internal array
276 * \param dynar a dynar
277 * \param empty_slots_wanted number of empty slots you want to keep at the end of the
278 * internal array for further insertions
280 * Reduces the internal array size of the dynar to the number of elements plus
281 * \a empty_slots_wanted.
282 * After removing elements from the dynar, you can call this function to make
283 * the dynar use less memory.
284 * Set \a empty_slots_wanted to zero to reduce the dynar internal array as much
286 * Note that if \a empty_slots_wanted is greater than the array size, the internal
287 * array is not expanded and nothing is done.
289 void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted) {
290 unsigned long size_wanted;
294 size_wanted = dynar->used + empty_slots_wanted;
295 if (size_wanted < dynar->size) {
296 dynar->size = size_wanted;
297 dynar->data = xbt_realloc(dynar->data, sizeof(void*) * dynar->size);
299 _dynar_unlock(dynar);
302 /** @brief Destructor
304 * \param dynar poor victim
306 * kilkil a dynar and its content
310 xbt_dynar_free(xbt_dynar_t * dynar) {
311 if (dynar && *dynar) {
312 xbt_dynar_reset(*dynar);
313 xbt_dynar_free_container(dynar);
316 /** \brief free a dynar passed as void* (handy to store dynar in dynars or dict) */
317 void xbt_dynar_free_voidp(void *d) {
318 xbt_dynar_free( (xbt_dynar_t*) d);
321 /** @brief Count of dynar's elements
323 * \param dynar the dynar we want to mesure
326 xbt_dynar_length(const xbt_dynar_t dynar) {
327 return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
330 /** @brief Retrieve a copy of the Nth element of a dynar.
332 * \param dynar information dealer
333 * \param idx index of the slot we want to retrieve
334 * \param[out] dst where to put the result to.
337 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
338 const unsigned long idx,
341 _sanity_check_dynar(dynar);
342 _check_inbound_idx(dynar, idx);
344 _xbt_dynar_get_elm(dst, dynar, idx);
345 _dynar_unlock(dynar);
348 /** @brief Retrieve a pointer to the Nth element of a dynar.
350 * \param dynar information dealer
351 * \param idx index of the slot we want to retrieve
352 * \return the \a idx-th element of \a dynar.
354 * \warning The returned value is the actual content of the dynar.
355 * Make a copy before fooling with it.
358 xbt_dynar_get_ptr(const xbt_dynar_t dynar, const unsigned long idx) {
362 _sanity_check_dynar(dynar);
363 _check_inbound_idx(dynar, idx);
365 res = _xbt_dynar_elm(dynar, idx);
366 _dynar_unlock(dynar);
371 static void XBT_INLINE /* not synchronized */
372 _xbt_dynar_set(xbt_dynar_t dynar,
373 const unsigned long idx,
374 const void * const src) {
376 _sanity_check_dynar(dynar);
377 _sanity_check_idx(idx);
379 _xbt_dynar_expand(dynar, idx+1);
381 if (idx >= dynar->used) {
385 _xbt_dynar_put_elm(dynar, idx, src);
388 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
390 * \param dynar information dealer
391 * \param idx index of the slot we want to modify
392 * \param src What will be feeded to the dynar
394 * If you want to free the previous content, use xbt_dynar_replace().
397 xbt_dynar_set(xbt_dynar_t dynar,
399 const void * const src) {
402 _xbt_dynar_set(dynar,idx,src);
403 _dynar_unlock(dynar);
406 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
412 * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
413 * free the previous value at this position. If you don't want to free the
414 * previous content, use xbt_dynar_set().
417 xbt_dynar_replace(xbt_dynar_t dynar,
418 const unsigned long idx,
419 const void * const object) {
421 _sanity_check_dynar(dynar);
422 _sanity_check_idx(idx);
424 if (idx < dynar->used && dynar->free_f) {
425 void * const old_object = _xbt_dynar_elm(dynar, idx);
427 (*(dynar->free_f))(old_object);
430 _xbt_dynar_set(dynar, idx, object);
431 _dynar_unlock(dynar);
434 static XBT_INLINE void *
435 _xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
436 const unsigned long idx) {
438 unsigned long old_used;
439 unsigned long new_used;
440 unsigned long nb_shift;
442 _sanity_check_dynar(dynar);
443 _sanity_check_idx(idx);
444 _check_sloppy_inbound_idx(dynar, idx);
446 old_used = dynar->used;
447 new_used = old_used + 1;
449 _xbt_dynar_expand(dynar, new_used);
451 nb_shift = old_used - idx;
454 memmove(_xbt_dynar_elm(dynar, idx+1),
455 _xbt_dynar_elm(dynar, idx),
456 nb_shift * dynar->elmsize);
458 dynar->used = new_used;
459 res = _xbt_dynar_elm(dynar,idx);
463 /** @brief Make room for a new element, and return a pointer to it
465 * You can then use regular affectation to set its value instead of relying
466 * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
469 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
474 res = _xbt_dynar_insert_at_ptr(dynar,idx);
475 _dynar_unlock(dynar);
479 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
481 * Set the Nth element of a dynar, expanding the dynar if needed, and
482 * moving the previously existing value and all subsequent ones to one
483 * position right in the dynar.
486 xbt_dynar_insert_at(xbt_dynar_t const dynar,
488 const void * const src) {
491 /* checks done in xbt_dynar_insert_at_ptr */
492 memcpy(_xbt_dynar_insert_at_ptr(dynar,idx),
495 _dynar_unlock(dynar);
498 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
500 * Get the Nth element of a dynar, removing it from the dynar and moving
501 * all subsequent values to one position left in the dynar.
503 * If the object argument of this function is a non-null pointer, the removed
504 * element is copied to this address. If not, the element is freed using the
505 * free_f function passed at dynar creation.
508 xbt_dynar_remove_at(xbt_dynar_t const dynar,
510 void * const object) {
513 _xbt_dynar_remove_at(dynar, idx, object);
514 _dynar_unlock(dynar);
517 /** @brief Returns the position of the element in the dynar
519 * Raises not_found_error if not found.
522 xbt_dynar_search(xbt_dynar_t const dynar,
527 for (it=0; it< dynar->used; it++)
528 if (!memcmp(_xbt_dynar_elm(dynar, it),elem,dynar->elmsize)) {
529 _dynar_unlock(dynar);
533 _dynar_unlock(dynar);
534 THROW2(not_found_error,0,"Element %p not part of dynar %p",elem,dynar);
537 /** @brief Returns a boolean indicating whether the element is part of the dynar */
539 xbt_dynar_member(xbt_dynar_t const dynar,
545 xbt_dynar_search(dynar,elem);
547 if (e.category == not_found_error) {
556 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
558 * You can then use regular affectation to set its value instead of relying
559 * on the slow memcpy. This is what xbt_dynar_push_as() does.
562 xbt_dynar_push_ptr(xbt_dynar_t const dynar) {
565 /* we have to inline xbt_dynar_insert_at_ptr here to make sure that
566 dynar->used don't change between reading it and getting the lock
567 within xbt_dynar_insert_at_ptr */
569 res = _xbt_dynar_insert_at_ptr(dynar,dynar->used);
570 _dynar_unlock(dynar);
574 /** @brief Add an element at the end of the dynar */
576 xbt_dynar_push(xbt_dynar_t const dynar,
577 const void * const src) {
579 /* checks done in xbt_dynar_insert_at_ptr */
580 memcpy(_xbt_dynar_insert_at_ptr(dynar,dynar->used),
583 _dynar_unlock(dynar);
586 /** @brief Mark the last dynar's element as unused and return a pointer to it.
588 * You can then use regular affectation to set its value instead of relying
589 * on the slow memcpy. This is what xbt_dynar_pop_as() does.
592 xbt_dynar_pop_ptr(xbt_dynar_t const dynar) {
596 _check_populated_dynar(dynar);
597 DEBUG1("Pop %p",(void*)dynar);
599 res = _xbt_dynar_elm(dynar,dynar->used);
600 _dynar_unlock(dynar);
604 /** @brief Get and remove the last element of the dynar */
606 xbt_dynar_pop(xbt_dynar_t const dynar,
609 /* sanity checks done by remove_at */
610 DEBUG1("Pop %p",(void*)dynar);
612 _xbt_dynar_remove_at(dynar, dynar->used-1, dst);
613 _dynar_unlock(dynar);
616 /** @brief Add an element at the begining of the dynar.
618 * This is less efficient than xbt_dynar_push()
621 xbt_dynar_unshift(xbt_dynar_t const dynar,
622 const void * const src) {
624 /* sanity checks done by insert_at */
625 xbt_dynar_insert_at(dynar, 0, src);
628 /** @brief Get and remove the first element of the dynar.
630 * This is less efficient than xbt_dynar_pop()
633 xbt_dynar_shift(xbt_dynar_t const dynar,
636 /* sanity checks done by remove_at */
637 xbt_dynar_remove_at(dynar, 0, dst);
640 static void _dynar_map(const xbt_dynar_t dynar,
641 void_f_pvoid_t const op) {
642 char elm[SIZEOF_MAX];
643 const unsigned long used = dynar->used;
646 for (i = 0; i < used; i++) {
647 _xbt_dynar_get_elm(elm, dynar, i);
652 /** @brief Apply a function to each member of a dynar
654 * The mapped function may change the value of the element itself,
655 * but should not mess with the structure of the dynar.
657 * If the dynar is synchronized, it is locked during the whole map
658 * operation, so make sure your function don't call any function
659 * from xbt_dynar_* on it, or you'll get a deadlock.
662 xbt_dynar_map(const xbt_dynar_t dynar,
663 void_f_pvoid_t const op) {
666 _sanity_check_dynar(dynar);
668 _dynar_map(dynar,op);
670 _dynar_unlock(dynar);
673 /** @brief Put the cursor at the begining of the dynar.
675 * Actually, the cursor is set one step before the begining, so that you
676 * can iterate over the dynar with a for loop.
678 * @warning Do not call this function directly, but only through xbt_dynar_foreach.
681 _xbt_dynar_cursor_first(const xbt_dynar_t dynar,
682 unsigned int * const cursor) {
685 DEBUG1("Set cursor on %p to the first position",(void*)dynar);
689 /** @brief Move the cursor to the next value
691 * @warning Do not call this function directly, but only through xbt_dynar_foreach.
694 _xbt_dynar_cursor_step(const xbt_dynar_t dynar,
695 unsigned int * const cursor) {
700 /** @brief Get the data currently pointed by the cursor
702 * @warning Do not call this function directly, but only through xbt_dynar_foreach.
705 _xbt_dynar_cursor_get(const xbt_dynar_t dynar,
706 unsigned int * const cursor,
709 _sanity_check_dynar(dynar);
712 const unsigned long idx = *cursor;
714 if (idx >= dynar->used) {
715 DEBUG1("Cursor on %p already on last elem",(void*)dynar);
716 _dynar_unlock(dynar);
719 DEBUG2("Cash out cursor on %p at %lu",(void*)dynar,idx);
721 _xbt_dynar_get_elm(dst, dynar, idx);
727 /** @brief Removes and free the entry pointed by the cursor
729 * This function can be used while traversing without problem.
731 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
732 unsigned int * const cursor) {
734 _xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
737 /** @brief Unlocks a synchronized dynar when you want to break the traversal
739 * This function must be used if you <tt>break</tt> the
740 * xbt_dynar_foreach loop, but shouldn't be called at the end of a
741 * regular traversal reaching the end of the elements
743 void xbt_dynar_cursor_unlock(xbt_dynar_t dynar) {
744 _dynar_unlock(dynar);
751 XBT_TEST_SUITE("dynar","Dynar data container");
752 XBT_LOG_EXTERNAL_CATEGORY(xbt_dyn);
753 XBT_LOG_DEFAULT_CATEGORY(xbt_dyn);
755 XBT_TEST_UNIT("int",test_dynar_int,"Dynars of integers") {
756 /* Vars_decl [doxygen cruft] */
762 xbt_test_add0("==== Traverse the empty dynar");
763 d=xbt_dynar_new(sizeof(int),NULL);
764 xbt_dynar_foreach(d,cursor,i){
765 xbt_assert0(0,"Damnit, there is something in the empty dynar");
770 xbt_test_add1("==== Push %d int, set them again 3 times, traverse them, shift them",
772 /* Populate_ints [doxygen cruft] */
773 /* 1. Populate the dynar */
774 d=xbt_dynar_new(sizeof(int),NULL);
775 for (cpt=0; cpt< NB_ELEM; cpt++) {
776 xbt_dynar_push_as(d,int,cpt); /* This is faster (and possible only with scalars) */
777 /* xbt_dynar_push(d,&cpt); This would also work */
778 xbt_test_log2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
781 /* 2. Traverse manually the dynar */
782 for (cursor=0; cursor< NB_ELEM; cursor++) {
783 iptr=xbt_dynar_get_ptr(d,cursor);
784 xbt_test_assert2(cursor == *iptr,
785 "The retrieved value is not the same than the injected one (%d!=%d)",
789 /* 3. Traverse the dynar using the neat macro to that extend */
790 xbt_dynar_foreach(d,cursor,cpt){
791 xbt_test_assert2(cursor == cpt,
792 "The retrieved value is not the same than the injected one (%d!=%d)",
795 /* end_of_traversal */
797 for (cpt=0; cpt< NB_ELEM; cpt++)
798 *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
800 for (cpt=0; cpt< NB_ELEM; cpt++)
801 *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
802 /* xbt_dynar_set(d,cpt,&cpt);*/
804 for (cpt=0; cpt< NB_ELEM; cpt++)
805 *(int*)xbt_dynar_get_ptr(d,cpt) = cpt;
808 xbt_dynar_foreach(d,cursor,i){
809 xbt_test_assert2(i == cpt,
810 "The retrieved value is not the same than the injected one (%d!=%d)",
814 xbt_test_assert2(cpt == NB_ELEM,
815 "Cannot retrieve my %d values. Last got one is %d",
818 /* shifting [doxygen cruft] */
819 /* 4. Shift all the values */
820 for (cpt=0; cpt< NB_ELEM; cpt++) {
821 xbt_dynar_shift(d,&i);
822 xbt_test_assert2(i == cpt,
823 "The retrieved value is not the same than the injected one (%d!=%d)",
825 xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
828 /* 5. Free the resources */
833 xbt_test_add1("==== Unshift/pop %d int",NB_ELEM);
834 d=xbt_dynar_new(sizeof(int),NULL);
835 for (cpt=0; cpt< NB_ELEM; cpt++) {
836 xbt_dynar_unshift(d,&cpt);
837 DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
839 for (cpt=0; cpt< NB_ELEM; cpt++) {
840 i=xbt_dynar_pop_as(d,int);
841 xbt_test_assert2(i == cpt,
842 "The retrieved value is not the same than the injected one (%d!=%d)",
844 xbt_test_log2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
850 xbt_test_add1("==== Push %d int, insert 1000 int in the middle, shift everything",NB_ELEM);
851 d=xbt_dynar_new(sizeof(int),NULL);
852 for (cpt=0; cpt< NB_ELEM; cpt++) {
853 xbt_dynar_push_as(d,int,cpt);
854 DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
856 for (cpt=0; cpt< 1000; cpt++) {
857 xbt_dynar_insert_at_as(d,2500,int,cpt);
858 DEBUG2("Push %d, length=%lu",cpt, xbt_dynar_length(d));
861 for (cpt=0; cpt< 2500; 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 at the begining (%d!=%d)",
866 DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
868 for (cpt=999; cpt>=0; cpt--) {
869 xbt_dynar_shift(d,&i);
870 xbt_test_assert2(i == cpt,
871 "The retrieved value is not the same than the injected one in the middle (%d!=%d)",
874 for (cpt=2500; cpt< NB_ELEM; cpt++) {
875 xbt_dynar_shift(d,&i);
876 xbt_test_assert2(i == cpt,
877 "The retrieved value is not the same than the injected one at the end (%d!=%d)",
884 xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest",NB_ELEM);
885 d=xbt_dynar_new(sizeof(int),NULL);
886 for (cpt=0; cpt< NB_ELEM; cpt++)
887 xbt_dynar_push_as(d,int,cpt);
889 for (cpt=2000; cpt< 4000; cpt++) {
890 xbt_dynar_remove_at(d,2000,&i);
891 xbt_test_assert2(i == cpt,
892 "Remove a bad value. Got %d, expected %d",
894 DEBUG2("remove %d, length=%lu",cpt, xbt_dynar_length(d));
899 /*******************************************************************************/
900 /*******************************************************************************/
901 /*******************************************************************************/
902 XBT_TEST_UNIT("double",test_dynar_double,"Dynars of doubles") {
908 xbt_test_add0("==== Traverse the empty dynar");
909 d=xbt_dynar_new(sizeof(int),NULL);
910 xbt_dynar_foreach(d,cursor,cpt){
911 xbt_test_assert0(FALSE,
912 "Damnit, there is something in the empty dynar");
917 xbt_test_add0("==== Push/shift 5000 doubles");
918 d=xbt_dynar_new(sizeof(double),NULL);
919 for (cpt=0; cpt< 5000; cpt++) {
921 xbt_dynar_push(d,&d1);
923 xbt_dynar_foreach(d,cursor,d2){
925 xbt_test_assert2(d1 == d2,
926 "The retrieved value is not the same than the injected one (%f!=%f)",
929 for (cpt=0; cpt< 5000; cpt++) {
931 xbt_dynar_shift(d,&d2);
932 xbt_test_assert2(d1 == d2,
933 "The retrieved value is not the same than the injected one (%f!=%f)",
940 xbt_test_add0("==== Unshift/pop 5000 doubles");
941 d=xbt_dynar_new(sizeof(double),NULL);
942 for (cpt=0; cpt< 5000; cpt++) {
944 xbt_dynar_unshift(d,&d1);
946 for (cpt=0; cpt< 5000; cpt++) {
948 xbt_dynar_pop(d,&d2);
949 xbt_test_assert2 (d1 == d2,
950 "The retrieved value is not the same than the injected one (%f!=%f)",
958 xbt_test_add0("==== Push 5000 doubles, insert 1000 doubles in the middle, shift everything");
959 d=xbt_dynar_new(sizeof(double),NULL);
960 for (cpt=0; cpt< 5000; cpt++) {
962 xbt_dynar_push(d,&d1);
964 for (cpt=0; cpt< 1000; cpt++) {
966 xbt_dynar_insert_at(d,2500,&d1);
969 for (cpt=0; cpt< 2500; cpt++) {
971 xbt_dynar_shift(d,&d2);
972 xbt_test_assert2(d1 == d2,
973 "The retrieved value is not the same than the injected one at the begining (%f!=%f)",
975 DEBUG2("Pop %d, length=%lu",cpt, xbt_dynar_length(d));
977 for (cpt=999; cpt>=0; 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 in the middle (%f!=%f)",
984 for (cpt=2500; cpt< 5000; cpt++) {
986 xbt_dynar_shift(d,&d2);
987 xbt_test_assert2 (d1 == d2,
988 "The retrieved value is not the same than the injected one at the end (%f!=%f)",
995 xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest");
996 d=xbt_dynar_new(sizeof(double),NULL);
997 for (cpt=0; cpt< 5000; cpt++) {
999 xbt_dynar_push(d,&d1);
1001 for (cpt=2000; cpt< 4000; cpt++) {
1003 xbt_dynar_remove_at(d,2000,&d2);
1004 xbt_test_assert2 (d1 == d2,
1005 "Remove a bad value. Got %f, expected %f",
1013 /* doxygen_string_cruft */
1015 /*******************************************************************************/
1016 /*******************************************************************************/
1017 /*******************************************************************************/
1018 XBT_TEST_UNIT("string",test_dynar_string,"Dynars of strings") {
1025 xbt_test_add0("==== Traverse the empty dynar");
1026 d=xbt_dynar_new(sizeof(char *),&xbt_free_ref);
1027 xbt_dynar_foreach(d,iter,s1){
1028 xbt_test_assert0(FALSE,
1029 "Damnit, there is something in the empty dynar");
1034 xbt_test_add1("==== Push %d strings, set them again 3 times, shift them",NB_ELEM);
1035 /* Populate_str [doxygen cruft] */
1036 d=xbt_dynar_new(sizeof(char*),&xbt_free_ref);
1037 /* 1. Populate the dynar */
1038 for (cpt=0; cpt< NB_ELEM; cpt++) {
1039 sprintf(buf,"%d",cpt);
1041 xbt_dynar_push(d,&s1);
1043 for (cpt=0; cpt< NB_ELEM; cpt++) {
1044 sprintf(buf,"%d",cpt);
1046 xbt_dynar_replace(d,cpt,&s1);
1048 for (cpt=0; cpt< NB_ELEM; cpt++) {
1049 sprintf(buf,"%d",cpt);
1051 xbt_dynar_replace(d,cpt,&s1);
1053 for (cpt=0; cpt< NB_ELEM; cpt++) {
1054 sprintf(buf,"%d",cpt);
1056 xbt_dynar_replace(d,cpt,&s1);
1058 for (cpt=0; cpt< NB_ELEM; cpt++) {
1059 sprintf(buf,"%d",cpt);
1060 xbt_dynar_shift(d,&s2);
1061 xbt_test_assert2 (!strcmp(buf,s2),
1062 "The retrieved value is not the same than the injected one (%s!=%s)",
1070 xbt_test_add1("==== Unshift, traverse and pop %d strings",NB_ELEM);
1071 d=xbt_dynar_new(sizeof(char**),&xbt_free_ref);
1072 for (cpt=0; cpt< NB_ELEM; cpt++) {
1073 sprintf(buf,"%d",cpt);
1075 xbt_dynar_unshift(d,&s1);
1077 /* 2. Traverse the dynar with the macro */
1078 xbt_dynar_foreach(d,iter,s1) {
1079 sprintf(buf,"%d",NB_ELEM - iter -1);
1080 xbt_test_assert2 (!strcmp(buf,s1),
1081 "The retrieved value is not the same than the injected one (%s!=%s)",
1084 /* 3. Traverse the dynar with the macro */
1085 for (cpt=0; cpt< NB_ELEM; cpt++) {
1086 sprintf(buf,"%d",cpt);
1087 xbt_dynar_pop(d,&s2);
1088 xbt_test_assert2 (!strcmp(buf,s2),
1089 "The retrieved value is not the same than the injected one (%s!=%s)",
1093 /* 4. Free the resources */
1098 xbt_test_add2("==== Push %d strings, insert %d strings in the middle, shift everything",NB_ELEM,NB_ELEM/5);
1099 d=xbt_dynar_new(sizeof(char*),&xbt_free_ref);
1100 for (cpt=0; cpt< NB_ELEM; cpt++) {
1101 sprintf(buf,"%d",cpt);
1103 xbt_dynar_push(d,&s1);
1105 for (cpt=0; cpt< NB_ELEM/5; cpt++) {
1106 sprintf(buf,"%d",cpt);
1108 xbt_dynar_insert_at(d,NB_ELEM/2,&s1);
1111 for (cpt=0; cpt< NB_ELEM/2; cpt++) {
1112 sprintf(buf,"%d",cpt);
1113 xbt_dynar_shift(d,&s2);
1114 xbt_test_assert2(!strcmp(buf,s2),
1115 "The retrieved value is not the same than the injected one at the begining (%s!=%s)",
1119 for (cpt=(NB_ELEM/5)-1; cpt>=0; cpt--) {
1120 sprintf(buf,"%d",cpt);
1121 xbt_dynar_shift(d,&s2);
1122 xbt_test_assert2 (!strcmp(buf,s2),
1123 "The retrieved value is not the same than the injected one in the middle (%s!=%s)",
1127 for (cpt=NB_ELEM/2; cpt< NB_ELEM; cpt++) {
1128 sprintf(buf,"%d",cpt);
1129 xbt_dynar_shift(d,&s2);
1130 xbt_test_assert2 (!strcmp(buf,s2),
1131 "The retrieved value is not the same than the injected one at the end (%s!=%s)",
1139 xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest",NB_ELEM,2*(NB_ELEM/5),4*(NB_ELEM/5));
1140 d=xbt_dynar_new(sizeof(char*),&xbt_free_ref);
1141 for (cpt=0; cpt< NB_ELEM; cpt++) {
1142 sprintf(buf,"%d",cpt);
1144 xbt_dynar_push(d,&s1);
1146 for (cpt=2*(NB_ELEM/5); cpt< 4*(NB_ELEM/5); cpt++) {
1147 sprintf(buf,"%d",cpt);
1148 xbt_dynar_remove_at(d,2*(NB_ELEM/5),&s2);
1149 xbt_test_assert2(!strcmp(buf,s2),
1150 "Remove a bad value. Got %s, expected %s",
1154 xbt_dynar_free(&d); /* end_of_doxygen */
1158 /*******************************************************************************/
1159 /*******************************************************************************/
1160 /*******************************************************************************/
1161 #include "xbt/synchro.h"
1162 static void pusher_f(void *a) {
1163 xbt_dynar_t d=(xbt_dynar_t)a;
1165 for (i=0; i<500; i++) {
1166 xbt_dynar_push(d,&i);
1169 static void poper_f(void *a) {
1170 xbt_dynar_t d=(xbt_dynar_t)a;
1175 for (i=0; i<500; i++) {
1177 xbt_dynar_pop(d,&data);
1179 if (e.category == bound_error) {
1190 XBT_TEST_UNIT("synchronized int",test_dynar_sync_int,"Synchronized dynars of integers") {
1191 /* Vars_decl [doxygen cruft] */
1193 xbt_thread_t pusher,poper;
1195 xbt_test_add0("==== Have a pusher and a popper on the dynar");
1196 d=xbt_dynar_new_sync(sizeof(int),NULL);
1197 pusher = xbt_thread_create("pusher",pusher_f,d);
1198 poper = xbt_thread_create("poper",poper_f,d);
1199 xbt_thread_join(pusher);
1200 xbt_thread_join(poper);
1204 #endif /* SIMGRID_TEST */