-/* $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. */
#include "xbt/dynar.h"
#include <sys/types.h>
-#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.
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;
if (old_data) {
memcpy(new_data, old_data, used_length);
- _xbt_clear_mem(old_data, old_length);
free(old_data);
}
}
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--;
}
*
* \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);
* 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)
{
_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);
}
* 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);
*
* \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)
{
* \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;
*
* 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);
* 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)
{
*
* 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;
* 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;
}
/** @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 */
* 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;
}
/** @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 */
*
* 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 */
*
* 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 */
* 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);
* 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 <tt>compar_fn</tt>
+ *
+ * \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
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",
}
/* 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);
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
"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);
"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 */
}
/*******************************************************************************/
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);
"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);
"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 */
"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");
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 */
}
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);
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);
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
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,
}
-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;
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);