X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/1fd91c16cd08f9f18179241091be71423fff55ae..16046da568d3d690d7dfdedc12c4416f71984acb:/src/xbt/dynar.c diff --git a/src/xbt/dynar.c b/src/xbt/dynar.c index a6a159e5c6..e289e655f0 100644 --- a/src/xbt/dynar.c +++ b/src/xbt/dynar.c @@ -1,8 +1,7 @@ -/* $Id$ */ - /* a generic DYNamic ARray implementation. */ -/* Copyright (c) 2003, 2004 Martin Quinson. All rights reserved. */ +/* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team. + * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ @@ -89,7 +88,6 @@ static XBT_INLINE char *const old_data = (char *) dynar->data; const unsigned long elmsize = dynar->elmsize; - const unsigned long old_length = old_size * elmsize; const unsigned long used = dynar->used; const unsigned long used_length = used * elmsize; @@ -172,9 +170,11 @@ _xbt_dynar_remove_at(xbt_dynar_t const dynar, } nb_shift = dynar->used - 1 - idx; - offset = nb_shift * dynar->elmsize; - memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset); + if (nb_shift) { + offset = nb_shift * dynar->elmsize; + memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset); + } dynar->used--; } @@ -289,7 +289,7 @@ XBT_INLINE void xbt_dynar_reset(xbt_dynar_t const dynar) * Set \a empty_slots_wanted to zero to reduce the dynar internal array as much * as possible. * Note that if \a empty_slots_wanted is greater than the array size, the internal - * array is not expanded and nothing is done. + * array is expanded instead of shriked. */ void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted) { @@ -298,9 +298,9 @@ void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted) _dynar_lock(dynar); size_wanted = dynar->used + empty_slots_wanted; - if (size_wanted < dynar->size) { + if (size_wanted != dynar->size) { dynar->size = size_wanted; - dynar->data = xbt_realloc(dynar->data, sizeof(void *) * dynar->size); + dynar->data = xbt_realloc(dynar->data, dynar->elmsize * dynar->size); } _dynar_unlock(dynar); } @@ -335,6 +335,16 @@ XBT_INLINE unsigned long xbt_dynar_length(const xbt_dynar_t dynar) return (dynar ? (unsigned long) dynar->used : (unsigned long) 0); } +/**@brief check if a dynar is empty + * + *\param dynar the dynat we want to check + */ + +XBT_INLINE int xbt_dynar_is_empty(const xbt_dynar_t dynar) +{ + return (xbt_dynar_length(dynar) == 0); +} + /** @brief Retrieve a copy of the Nth element of a dynar. * * \param dynar information dealer @@ -520,7 +530,7 @@ xbt_dynar_remove_at(xbt_dynar_t const dynar, * * Raises not_found_error if not found. */ -int xbt_dynar_search(xbt_dynar_t const dynar, void *const elem) +unsigned int xbt_dynar_search(xbt_dynar_t const dynar, void *const elem) { unsigned long it; @@ -685,6 +695,22 @@ XBT_INLINE void xbt_dynar_cursor_unlock(xbt_dynar_t dynar) _dynar_unlock(dynar); } +/** @brief Sorts a dynar according to the function compar_fn + * + * \param compar_fn comparison function of type (int (compar_fn*) (void*) (void*)). + * + * Remark: if the elements stored in the dynar are structures, the compar_fn + * function has to retrieve the field to sort first. + */ +XBT_INLINE void xbt_dynar_sort(xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn){ + + _dynar_lock(dynar); + + qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn); + + _dynar_unlock(dynar); +} + #ifdef SIMGRID_TEST #define NB_ELEM 5000 @@ -706,8 +732,9 @@ XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers") xbt_dynar_foreach(d, cursor, i) { xbt_assert0(0, "Damnit, there is something in the empty dynar"); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add1 ("==== Push %d int, set them again 3 times, traverse them, shift them", @@ -769,9 +796,9 @@ XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers") } /* 5. Free the resources */ - xbt_dynar_free(&d); - xbt_dynar_free(&d); - + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add1("==== Unshift/pop %d int", NB_ELEM); d = xbt_dynar_new(sizeof(int), NULL); @@ -786,8 +813,9 @@ XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers") i, cpt); xbt_test_log2("Pop %d, length=%lu", cpt, xbt_dynar_length(d)); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add1 @@ -822,9 +850,9 @@ XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers") "The retrieved value is not the same than the injected one at the end (%d!=%d)", i, cpt); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); - + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add1("==== Push %d int, remove 2000-4000. free the rest", NB_ELEM); d = xbt_dynar_new(sizeof(int), NULL); @@ -837,8 +865,9 @@ XBT_TEST_UNIT("int", test_dynar_int, "Dynars of integers") "Remove a bad value. Got %d, expected %d", i, cpt); DEBUG2("remove %d, length=%lu", cpt, xbt_dynar_length(d)); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ } /*******************************************************************************/ @@ -856,8 +885,9 @@ XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles") xbt_dynar_foreach(d, cursor, cpt) { xbt_test_assert0(FALSE, "Damnit, there is something in the empty dynar"); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add0("==== Push/shift 5000 doubles"); d = xbt_dynar_new(sizeof(double), NULL); @@ -878,9 +908,9 @@ XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles") "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); - + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add0("==== Unshift/pop 5000 doubles"); d = xbt_dynar_new(sizeof(double), NULL); @@ -895,8 +925,9 @@ XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles") "The retrieved value is not the same than the injected one (%f!=%f)", d1, d2); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ @@ -934,8 +965,9 @@ XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles") "The retrieved value is not the same than the injected one at the end (%f!=%f)", d1, d2); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add0("==== Push 5000 double, remove 2000-4000. free the rest"); @@ -950,8 +982,9 @@ XBT_TEST_UNIT("double", test_dynar_double, "Dynars of doubles") xbt_test_assert2(d1 == d2, "Remove a bad value. Got %f, expected %f", d2, d1); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ } @@ -973,8 +1006,9 @@ XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings") xbt_dynar_foreach(d, iter, s1) { xbt_test_assert0(FALSE, "Damnit, there is something in the empty dynar"); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add1("==== Push %d strings, set them again 3 times, shift them", NB_ELEM); @@ -1009,9 +1043,9 @@ XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings") buf, s2); free(s2); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); - + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add1("==== Unshift, traverse and pop %d strings", NB_ELEM); d = xbt_dynar_new(sizeof(char **), &xbt_free_ref); @@ -1037,8 +1071,9 @@ XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings") free(s2); } /* 4. Free the resources */ - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add2 @@ -1080,8 +1115,9 @@ XBT_TEST_UNIT("string", test_dynar_string, "Dynars of strings") buf, s2); free(s2); } - xbt_dynar_free(&d); - xbt_dynar_free(&d); + xbt_dynar_free(&d); /* This code is used both as example and as regression test, so we try to */ + xbt_dynar_free(&d); /* free the struct twice here to check that it's ok, but freeing it only once */ + /* in your code is naturally the way to go outside a regression test */ xbt_test_add3("==== Push %d strings, remove %d-%d. free the rest", NB_ELEM,