X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/71c8117a9137c59bece62c17a3277fdccd362d0a..ea39fd08c260e7faa92334952d4acd37e3892b6c:/src/xbt/dynar.c diff --git a/src/xbt/dynar.c b/src/xbt/dynar.c index c630ff0796..21dd9c49f0 100644 --- a/src/xbt/dynar.c +++ b/src/xbt/dynar.c @@ -238,6 +238,28 @@ XBT_INLINE void xbt_dynar_reset(xbt_dynar_t const dynar) _dynar_unlock(dynar); } +/** @brief Merge dynar d2 into d1 + * + * \param d1 dynar to keep + * \param d2 dynar to merge into d1. This dynar is free at end. + */ +void xbt_dynar_merge(xbt_dynar_t *d1, xbt_dynar_t *d2) +{ + if((*d1)->elmsize != (*d2)->elmsize) + xbt_die("Element size must are not equal"); + + const unsigned long elmsize = (*d1)->elmsize; + + void *ptr = _xbt_dynar_elm((*d2), 0); + _xbt_dynar_resize(*d1, (*d1)->size + (*d2)->size); + void *elm = _xbt_dynar_elm((*d1), (*d1)->used); + + memcpy(elm, ptr, ((*d2)->size)*elmsize); + (*d1)->used += (*d2)->used; + (*d2)->used = 0; + xbt_dynar_free(d2); +} + /** * \brief Shrink the dynar by removing empty slots at the end of the internal array * \param dynar a dynar @@ -501,7 +523,9 @@ xbt_dynar_remove_at(xbt_dynar_t const dynar, /** @brief Returns the position of the element in the dynar * - * Raises not_found_error if not found. + * Raises not_found_error if not found. If you have less than 2 millions elements, + * you probably want to use #xbt_dynar_search_or_negative() instead, so that you + * don't have to TRY/CATCH on element not found. */ unsigned int xbt_dynar_search(xbt_dynar_t const dynar, void *const elem) { @@ -519,6 +543,26 @@ unsigned int xbt_dynar_search(xbt_dynar_t const dynar, void *const elem) dynar); } +/** @brief Returns the position of the element in the dynar (or -1 if not found) + * + * Note that usually, the dynar indices are unsigned integers. If you have more + * than 2 million elements in your dynar, this very function will not work (but the other will). + */ +signed int xbt_dynar_search_or_negative(xbt_dynar_t const dynar, void *const elem) +{ + unsigned long it; + + _dynar_lock(dynar); + for (it = 0; it < dynar->used; it++) + if (!memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) { + _dynar_unlock(dynar); + return it; + } + + _dynar_unlock(dynar); + return -1; +} + /** @brief Returns a boolean indicating whether the element is part of the dynar */ int xbt_dynar_member(xbt_dynar_t const dynar, void *const elem) { @@ -698,8 +742,55 @@ XBT_INLINE void xbt_dynar_sort(xbt_dynar_t dynar, _dynar_unlock(dynar); } -/** @brief Transform a dynar into a NULL terminated array +/** @brief Sorts a dynar according to their color assuming elements can have only three colors. + * Since there are only three colors, it is linear and much faster than a classical sort. + * See for example http://en.wikipedia.org/wiki/Dutch_national_flag_problem * + * \param dynar the dynar to sort + * \param color the color function of type (int (compar_fn*) (void*) (void*)). The return value of color is assumed to be 0, 1, or 2. + * + * At the end of the call, elements with color 0 are at the beginning of the dynar, elements with color 2 are at the end and elements with color 1 are in the middle. + * + * Remark: if the elements stored in the dynar are structures, the color + * function has to retrieve the field to sort first. + */ +XBT_PUBLIC(void) xbt_dynar_three_way_partition(xbt_dynar_t const dynar, + int_f_pvoid_t color) +{ + _dynar_lock(dynar); + unsigned long int i; + unsigned long int p = -1; + unsigned long int q = dynar->used; + const unsigned long elmsize = dynar->elmsize; + void *tmp = xbt_malloc(elmsize); + void *elm; + + for (i = 0; i < q;) { + void *elmi = _xbt_dynar_elm(dynar, i); + int colori = color(elmi); + + if (colori == 1) { + ++i; + } else { + if (colori == 0) { + elm = _xbt_dynar_elm(dynar, ++p); + ++i; + } else { /* colori == 2 */ + elm = _xbt_dynar_elm(dynar, --q); + } + if (elm != elmi) { + memcpy(tmp, elm, elmsize); + memcpy(elm, elmi, elmsize); + memcpy(elmi, tmp, elmsize); + } + } + } + _dynar_unlock(dynar); + xbt_free(tmp); +} + +/** @brief Transform a dynar into a NULL terminated array. + * The dynar won't be usable afterwards. * \param dynar the dynar to transform */ XBT_INLINE void * xbt_dynar_to_array (xbt_dynar_t dynar) @@ -718,43 +809,43 @@ XBT_INLINE void * xbt_dynar_to_array (xbt_dynar_t dynar) * Return 0 if d1 and d2 are equal and 1 if not equal */ XBT_INLINE int xbt_dynar_compare(xbt_dynar_t d1, xbt_dynar_t d2, - int(*compar)(const void *, const void *)) + int(*compar)(const void *, const void *)) { - int i ; - int size; - if((!d1) && (!d2)) return 0; - if((!d1) || (!d2)) - { - XBT_DEBUG("NULL dynar d1=%p d2=%p",d1,d2); - xbt_dynar_free(&d2); - return 1; - } - if((d1->elmsize)!=(d2->elmsize)) - { - XBT_DEBUG("Size of elmsize d1=%ld d2=%ld",d1->elmsize,d2->elmsize); - xbt_dynar_free(&d2); - return 1; // xbt_die - } - if(xbt_dynar_length(d1) != xbt_dynar_length(d2)) - { - XBT_DEBUG("Size of dynar d1=%ld d2=%ld",xbt_dynar_length(d1),xbt_dynar_length(d2)); - xbt_dynar_free(&d2); - return 1; - } - - size = xbt_dynar_length(d1); - for(i=0;ielmsize)!=(d2->elmsize)) + { + XBT_DEBUG("Size of elmsize d1=%lu d2=%lu",d1->elmsize,d2->elmsize); + xbt_dynar_free(&d2); + return 1; // xbt_die + } + if(xbt_dynar_length(d1) != xbt_dynar_length(d2)) + { + XBT_DEBUG("Size of dynar d1=%lu d2=%lu",xbt_dynar_length(d1),xbt_dynar_length(d2)); + xbt_dynar_free(&d2); + return 1; + } + + size = xbt_dynar_length(d1); + for(i=0;i