X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/dff9e15c44ab6340d27215957c56fa72fad246a2..c2f496126e75748bcdcf40554f64c7c3e753acf7:/src/xbt/dynar.c diff --git a/src/xbt/dynar.c b/src/xbt/dynar.c index 68be6978b7..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. */ @@ -15,9 +14,6 @@ #include "xbt/dynar.h" #include -#include "xbt/dynar_private.h" /* type definition, which we share with the - code in charge of sending this across the net */ - /* IMPLEMENTATION NOTE ON SYNCHRONIZATION: every functions which name is prefixed by _ * assumes that the dynar is already locked if we have to. * Other functions (public ones) check for this. @@ -92,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; @@ -107,7 +102,6 @@ static XBT_INLINE if (old_data) { memcpy(new_data, old_data, used_length); - _xbt_clear_mem(old_data, old_length); free(old_data); } @@ -176,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--; } @@ -257,7 +253,7 @@ void xbt_dynar_free_container(xbt_dynar_t * dynar) * * \param dynar who to squeeze */ -void xbt_dynar_reset(xbt_dynar_t const dynar) +XBT_INLINE void xbt_dynar_reset(xbt_dynar_t const dynar) { _dynar_lock(dynar); @@ -293,7 +289,7 @@ 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) { @@ -302,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); } @@ -316,7 +312,7 @@ void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted) * kilkil a dynar and its content */ -void xbt_dynar_free(xbt_dynar_t * dynar) +XBT_INLINE void xbt_dynar_free(xbt_dynar_t * dynar) { if (dynar && *dynar) { xbt_dynar_reset(*dynar); @@ -334,18 +330,28 @@ void xbt_dynar_free_voidp(void *d) * * \param dynar the dynar we want to mesure */ -unsigned long xbt_dynar_length(const xbt_dynar_t dynar) +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 * \param idx index of the slot we want to retrieve * \param[out] dst where to put the result to. */ -void +XBT_INLINE void xbt_dynar_get_cpy(const xbt_dynar_t dynar, const unsigned long idx, void *const dst) { @@ -366,7 +372,7 @@ xbt_dynar_get_cpy(const xbt_dynar_t dynar, * \warning The returned value is the actual content of the dynar. * Make a copy before fooling with it. */ -void *xbt_dynar_get_ptr(const xbt_dynar_t dynar, const unsigned long idx) +XBT_INLINE void *xbt_dynar_get_ptr(const xbt_dynar_t dynar, const unsigned long idx) { void *res; @@ -405,7 +411,7 @@ _xbt_dynar_set(xbt_dynar_t dynar, * * If you want to free the previous content, use xbt_dynar_replace(). */ -void xbt_dynar_set(xbt_dynar_t dynar, const int idx, const void *const src) +XBT_INLINE void xbt_dynar_set(xbt_dynar_t dynar, const int idx, const void *const src) { _dynar_lock(dynar); @@ -490,7 +496,7 @@ void *xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar, const int idx) * moving the previously existing value and all subsequent ones to one * position right in the dynar. */ -void +XBT_INLINE void xbt_dynar_insert_at(xbt_dynar_t const dynar, const int idx, const void *const src) { @@ -524,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; @@ -562,7 +568,7 @@ int xbt_dynar_member(xbt_dynar_t const dynar, void *const elem) * You can then use regular affectation to set its value instead of relying * on the slow memcpy. This is what xbt_dynar_push_as() does. */ -void *xbt_dynar_push_ptr(xbt_dynar_t const dynar) +XBT_INLINE void *xbt_dynar_push_ptr(xbt_dynar_t const dynar) { void *res; @@ -576,7 +582,7 @@ void *xbt_dynar_push_ptr(xbt_dynar_t const dynar) } /** @brief Add an element at the end of the dynar */ -void xbt_dynar_push(xbt_dynar_t const dynar, const void *const src) +XBT_INLINE void xbt_dynar_push(xbt_dynar_t const dynar, const void *const src) { _dynar_lock(dynar); /* checks done in xbt_dynar_insert_at_ptr */ @@ -589,7 +595,7 @@ void xbt_dynar_push(xbt_dynar_t const dynar, const void *const src) * You can then use regular affectation to set its value instead of relying * on the slow memcpy. This is what xbt_dynar_pop_as() does. */ -void *xbt_dynar_pop_ptr(xbt_dynar_t const dynar) +XBT_INLINE void *xbt_dynar_pop_ptr(xbt_dynar_t const dynar) { void *res; @@ -603,7 +609,7 @@ void *xbt_dynar_pop_ptr(xbt_dynar_t const dynar) } /** @brief Get and remove the last element of the dynar */ -void xbt_dynar_pop(xbt_dynar_t const dynar, void *const dst) +XBT_INLINE void xbt_dynar_pop(xbt_dynar_t const dynar, void *const dst) { /* sanity checks done by remove_at */ @@ -617,7 +623,7 @@ void xbt_dynar_pop(xbt_dynar_t const dynar, void *const dst) * * This is less efficient than xbt_dynar_push() */ -void xbt_dynar_unshift(xbt_dynar_t const dynar, const void *const src) +XBT_INLINE void xbt_dynar_unshift(xbt_dynar_t const dynar, const void *const src) { /* sanity checks done by insert_at */ @@ -628,7 +634,7 @@ void xbt_dynar_unshift(xbt_dynar_t const dynar, const void *const src) * * This is less efficient than xbt_dynar_pop() */ -void xbt_dynar_shift(xbt_dynar_t const dynar, void *const dst) +XBT_INLINE void xbt_dynar_shift(xbt_dynar_t const dynar, void *const dst) { /* sanity checks done by remove_at */ @@ -656,76 +662,23 @@ static void _dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op) * operation, so make sure your function don't call any function * from xbt_dynar_* on it, or you'll get a deadlock. */ -void xbt_dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op) +XBT_INLINE void xbt_dynar_map(const xbt_dynar_t dynar, void_f_pvoid_t const op) { - _dynar_lock(dynar); _sanity_check_dynar(dynar); + _dynar_lock(dynar); _dynar_map(dynar, op); _dynar_unlock(dynar); } -/** @brief Put the cursor at the begining of the dynar. - * - * Actually, the cursor is set one step before the begining, so that you - * can iterate over the dynar with a for loop. - * - * @warning Do not call this function directly, but only through xbt_dynar_foreach. - */ -void -_xbt_dynar_cursor_first(const xbt_dynar_t dynar, unsigned int *const cursor) -{ - - _dynar_lock(dynar); - DEBUG1("Set cursor on %p to the first position", (void *) dynar); - *cursor = 0; -} - -/** @brief Move the cursor to the next value - * - * @warning Do not call this function directly, but only through xbt_dynar_foreach. - */ -void -_xbt_dynar_cursor_step(const xbt_dynar_t dynar, unsigned int *const cursor) -{ - - (*cursor)++; -} - -/** @brief Get the data currently pointed by the cursor - * - * @warning Do not call this function directly, but only through xbt_dynar_foreach. - */ -int -_xbt_dynar_cursor_get(const xbt_dynar_t dynar, - unsigned int *const cursor, void *const dst) -{ - - _sanity_check_dynar(dynar); - { - - const unsigned long idx = *cursor; - - if (idx >= dynar->used) { - DEBUG1("Cursor on %p already on last elem", (void *) dynar); - _dynar_unlock(dynar); - return FALSE; - } - DEBUG2("Cash out cursor on %p at %lu", (void *) dynar, idx); - - _xbt_dynar_get_elm(dst, dynar, idx); - } - return TRUE; - -} /** @brief Removes and free the entry pointed by the cursor * * This function can be used while traversing without problem. */ -void xbt_dynar_cursor_rm(xbt_dynar_t dynar, unsigned int *const cursor) +XBT_INLINE void xbt_dynar_cursor_rm(xbt_dynar_t dynar, unsigned int *const cursor) { _xbt_dynar_remove_at(dynar, (*cursor)--, NULL); @@ -737,11 +690,27 @@ void xbt_dynar_cursor_rm(xbt_dynar_t dynar, unsigned int *const cursor) * xbt_dynar_foreach loop, but shouldn't be called at the end of a * regular traversal reaching the end of the elements */ -void xbt_dynar_cursor_unlock(xbt_dynar_t dynar) +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 @@ -763,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", @@ -826,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); @@ -843,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 @@ -879,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); @@ -894,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 */ } /*******************************************************************************/ @@ -913,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); @@ -935,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); @@ -952,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 */ @@ -991,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"); @@ -1007,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 */ } @@ -1030,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); @@ -1066,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); @@ -1094,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 @@ -1137,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, @@ -1196,8 +1175,7 @@ static void poper_f(void *a) } -XBT_TEST_UNIT("synchronized int", test_dynar_sync_int, - "Synchronized dynars of integers") +XBT_TEST_UNIT("synchronized int", test_dynar_sync_int,"Synchronized dynars of integers") { /* Vars_decl [doxygen cruft] */ xbt_dynar_t d; @@ -1205,8 +1183,8 @@ XBT_TEST_UNIT("synchronized int", test_dynar_sync_int, xbt_test_add0("==== Have a pusher and a popper on the dynar"); d = xbt_dynar_new_sync(sizeof(int), NULL); - pusher = xbt_thread_create("pusher", pusher_f, d); - poper = xbt_thread_create("poper", poper_f, d); + pusher = xbt_thread_create("pusher", pusher_f, d,0/*not joinable*/); + poper = xbt_thread_create("poper", poper_f, d,0/*not joinable*/); xbt_thread_join(pusher); xbt_thread_join(poper); xbt_dynar_free(&d);