From b582c36a70a50b376da63ceacf2354d1a47c5ac7 Mon Sep 17 00:00:00 2001 From: mquinson Date: Wed, 5 May 2010 16:12:31 +0000 Subject: [PATCH] New data container: setset (set of sets of elements) git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@7692 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- ChangeLog | 1 + include/xbt/setset.h | 71 +++++++ src/Makefile.am | 3 +- src/xbt/setset.c | 409 +++++++++++++++++++++++++++++++++++++++ src/xbt/setset_private.h | 69 +++++++ 5 files changed, 552 insertions(+), 1 deletion(-) create mode 100644 include/xbt/setset.h create mode 100644 src/xbt/setset.c create mode 100644 src/xbt/setset_private.h diff --git a/ChangeLog b/ChangeLog index d2fb74a704..ad90087c5b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,6 +1,7 @@ SimGrid (3.5) unstable; urgency=low XBT + * New data container: setset (set of sets of elements) * New function: xbt_dict_cursor_set_data() * New function: xbt_fifo_get_last_item() * Bug fix in xbt_dynar_shrink(): use the right element size diff --git a/include/xbt/setset.h b/include/xbt/setset.h new file mode 100644 index 0000000000..e5e461800b --- /dev/null +++ b/include/xbt/setset.h @@ -0,0 +1,71 @@ +#ifndef _XBT_SETSET_H +#define _XBT_SETSET_H +#include "xbt/misc.h" + +typedef struct s_xbt_setset *xbt_setset_t; + +typedef struct s_xbt_setset_set *xbt_setset_set_t; + +typedef struct s_xbt_setset_cursor *xbt_setset_cursor_t; + +#define XBT_SETSET_HEADERS \ + unsigned long ID + +/* Constructor */ +xbt_setset_t xbt_setset_new(unsigned int size); + +/* Destructor */ +void xbt_setset_destroy(xbt_setset_t setset); + +/* Create a new set in the setset */ +xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset); + +/* Destroy a set in the setset */ +void xbt_setset_destroy_set(xbt_setset_set_t); + +/* Insert an element into a set */ +void xbt_setset_set_insert(xbt_setset_set_t set, void* obj); + +/* Remove an element from a set */ +void xbt_setset_set_remove(xbt_setset_set_t set, void* obj); + +/* Remove all the elements of a set */ +void xbt_setset_set_reset(xbt_setset_set_t set); + +/* Select one element of a set */ +void *xbt_setset_set_choose(xbt_setset_set_t set); + +/* Extract one element of a set */ +void *xbt_setset_set_extract(xbt_setset_set_t set); + +/* Test if an element belongs to a set */ +int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj); + +/* Get the number of elements in a set */ +int xbt_setset_set_size(xbt_setset_set_t set); + +/* Add all elements of set2 to set1 */ +void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2); + +/* Substract all elements of set2 from set1 */ +void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2); + +/* Intersect set1 and set2 storing the result in set1 */ +void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2); + +/* Get the cursor to point to the first element of a set */ +void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor); + +/* Get the data pointed by a cursor */ +int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data); + +/* Advance a cursor to the next element */ +void xbt_setset_cursor_next(xbt_setset_cursor_t cursor); + + +#define xbt_setset_foreach(set, cursor, data) \ + for(xbt_setset_cursor_first(set, &cursor); \ + xbt_setset_cursor_get_data(cursor, (void **)&data); \ + xbt_setset_cursor_next(cursor)) + +#endif \ No newline at end of file diff --git a/src/Makefile.am b/src/Makefile.am index f30c30a634..dbe4cd4f8d 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -169,7 +169,8 @@ XBT_SRC=\ \ xbt/config.c \ xbt/cunit.c \ - xbt/graphxml_parse.c + xbt/graphxml_parse.c \ + xbt/setset.c XBT_RL_SRC = \ xbt/xbt_rl_synchro.c \ diff --git a/src/xbt/setset.c b/src/xbt/setset.c new file mode 100644 index 0000000000..cbdb2b8f21 --- /dev/null +++ b/src/xbt/setset.c @@ -0,0 +1,409 @@ +#include +#include +#include "setset_private.h" +#include "xbt/sysdep.h" + +/** + * \brief Create a new setset data structure + * \param size The initial size of the setset (in number of elements) + * \return The created setset + */ +xbt_setset_t xbt_setset_new(unsigned int size) +{ + xbt_setset_elm_entry_t first_elm = NULL; + xbt_setset_t setset = xbt_new0(s_xbt_setset_t, 1); + setset->elm_array = xbt_dynar_new(sizeof(u_xbt_setset_elm_entry_t), NULL); + setset->sets = xbt_fifo_new(); + /* Expand the elements dynar to the size indicated by the user, */ + /* then create the first element, get a pointer to it and add it to the */ + /* free elements list */ + xbt_dynar_shrink(setset->elm_array, size); + first_elm = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array); + first_elm->free.next = 0; + return setset; +} + +/** + * \brief Destroy a setset and free all it's resources + * \param The setset to destroy + */ +void xbt_setset_destroy(xbt_setset_t setset) +{ + xbt_dynar_free(&setset->elm_array); + xbt_fifo_free(setset->sets); + xbt_free(setset); + /* FIXME: check if we should trash the stored objects */ +} + +/* Add an element to the setset, this will assign to it an index */ +xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj) +{ + xbt_setset_elm_entry_t new_entry = NULL; + xbt_setset_elm_t e = (xbt_setset_elm_t)obj; + xbt_assert0(e->ID == 0, "Adding element with non NULL ID"); + xbt_setset_elm_entry_t first_elm = + (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, 0); + + /* Before create a new elm entry check if there is one in the free elm list.*/ + /* If there is not free elm entries, then create a new one */ + if(first_elm->free.next != 0){ + e->ID = first_elm->free.next; + new_entry = (xbt_setset_elm_entry_t)xbt_dynar_get_ptr(setset->elm_array, first_elm->free.next); + first_elm->free.next = new_entry->free.next; + }else{ + new_entry = (xbt_setset_elm_entry_t)xbt_dynar_push_ptr(setset->elm_array); + e->ID = xbt_dynar_length(setset->elm_array) - 1; + } + /* Initialize the new element data structure and add it to the hash */ + new_entry->info.refcount = 0; + new_entry->info.obj = e; + return new_entry; +} + +/* Remove from the setset the object stored at idx */ +void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx) +{ + xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx); + xbt_setset_elm_entry_t first_free = NULL; + + /* Decrease the refcount and proceed only if it is 0 */ + if(--e_entry->info.refcount > 0) + return; + + /* Erase object ID */ + e_entry->info.obj->ID = 0; + + /* Link the elm entry to the list of free ones */ + first_free = xbt_dynar_get_ptr(setset->elm_array, 0); + e_entry->free.next = first_free->free.next; + first_free->free.next = idx; +} + +/* Get the object associated to a given index */ +/* WARNING: it must be a valid index! */ +void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx) +{ + xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx); + return e_entry->info.obj; +} + +/* Increase the refcount of an element */ +void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx) +{ + xbt_setset_elm_entry_t e_entry = xbt_dynar_get_ptr(setset->elm_array, idx); + e_entry->info.refcount++; +} + +/** + * \brief Add a new set to the setset + * \param setset The setset that will contain the created set + * \returns The created set + */ +xbt_setset_set_t xbt_setset_new_set(xbt_setset_t setset) +{ + xbt_setset_set_t newset = xbt_new0(s_xbt_setset_set_t, 1); + newset->setset = setset; + newset->elmcount = 0; + newset->size = xbt_dynar_length(setset->elm_array) / BITS_INT + 1; + newset->bitmap = xbt_new0(unsigned int, newset->size); + xbt_fifo_unshift(setset->sets, newset); + return newset; +} + +/** + * \brief Destroy a set in the setset + * \param set The set to destroy + */ +void xbt_setset_destroy_set(xbt_setset_set_t set) +{ + xbt_setset_set_reset(set); + xbt_free(set->bitmap); + xbt_fifo_remove(set->setset->sets, set); + xbt_free(set); + + return; +} + +/** + * \brief Insert an element into a set + * \param set The set where the element is going to be added + * \param obj The element to add + */ +void xbt_setset_set_insert(xbt_setset_set_t set, void* obj) +{ + xbt_setset_elm_t e = (xbt_setset_elm_t)obj; + + if(e->ID == 0) + _xbt_setset_elm_add(set->setset, e); + + /* Check if we need to expand the bitmap */ + if(set->size * BITS_INT - 1 < e->ID){ + set->bitmap = xbt_realloc(set->bitmap, (e->ID / BITS_INT + 1) * sizeof(int)); + memset(&set->bitmap[set->size], 0, ((e->ID / BITS_INT + 1) - set->size) * sizeof(int)); + set->size = (e->ID / BITS_INT + 1); + } + + if(!_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){ + set->elmcount++; + _xbt_setset_elm_use(set->setset, e->ID); + _set_bit(e->ID, set->bitmap); + } + + return; +} + +/** + * \brief Remove an element from a set + * \param set The set from which the element is going to be removed + * \param obj The element to remove + */ +void xbt_setset_set_remove(xbt_setset_set_t set, void* obj) +{ + xbt_setset_elm_t e = (xbt_setset_elm_t)obj; + if(e->ID != 0){ + /* If the index of the object is between the bitmap then unset it, otherwise + do not do anything, because we already know it is not in the set */ + if(set->size * BITS_INT >= e->ID){ + if(_is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT])){ + set->elmcount--; + _unset_bit(e->ID, set->bitmap); + _xbt_setset_elm_remove(set->setset, e->ID); + } + } + } + return; +} + +/** + * \brief Remove all the elements of a set + * \param set The set to empty + */ +void xbt_setset_set_reset(xbt_setset_set_t set) +{ + int i,k; + /* Traverse the set and remove every element */ + for(i=0; i < set->size; i++){ + if(set->bitmap[i] != 0){ + for(k=0; k < BITS_INT; k++){ + if(_is_bit_set(k,set->bitmap[i])){ + _xbt_setset_elm_remove(set->setset, i * BITS_INT + k); + } + } + } + } + set->elmcount = 0; +} + +/** + * \brief Choose one element of a set (but do not remove it) + * \param set The set + * \return An element that belongs to set \a set + */ +void *xbt_setset_set_choose(xbt_setset_set_t set) +{ + int i,k; + /* Traverse the set and return the first element */ + for(i=0; i < set->size; i++){ + if(set->bitmap[i] != 0){ + for(k=0; k < BITS_INT; k++){ + if(_is_bit_set(k,set->bitmap[i])){ + return _xbt_setset_idx_to_obj(set->setset, i * BITS_INT + k); + } + } + } + } + return NULL; +} + +/** + * \brief Extract one element of a set (it removes it) + * \param set The set + * \return An element that belonged to set \a set + */ +void *xbt_setset_set_extract(xbt_setset_set_t set) +{ + void *obj = xbt_setset_set_choose(set); + if(obj){ + xbt_setset_set_remove(set, obj); + } + return obj; +} + + +/** + * \brief Test if an element belongs to a set + * \param set The set + * \param obj The element + * \return TRUE if the element \a obj belongs to set \a set + */ +int xbt_setset_set_belongs(xbt_setset_set_t set, void* obj) +{ + xbt_setset_elm_t e = (xbt_setset_elm_t)obj; + if(e->ID != 0 && e->ID <= set->size * BITS_INT){ + return _is_bit_set(e->ID % BITS_INT, set->bitmap[e->ID / BITS_INT]); + } + return FALSE; +} + +int xbt_setset_set_size(xbt_setset_set_t set) +{ + return set->elmcount; +} + + +/** + * \brief Add two sets + * Add two sets storing the result in the first one + * \param set1 The first set + * \param set2 The second set + */ +void xbt_setset_add(xbt_setset_set_t set1, xbt_setset_set_t set2) +{ + if(set1->size < set2->size){ + xbt_realloc(set1->bitmap, set2->size * sizeof(unsigned int)); + set1->size = set2->size; + } + + int i,k; + /* Traverse the second set and add every element that is not member of the + first set to it */ + for(i=0; i < set2->size; i++){ + if(set2->bitmap[i] != 0){ + for(k=0; k < BITS_INT; k++){ + if(_is_bit_set(k,set2->bitmap[i]) && !_is_bit_set(k, set1->bitmap[i])){ + set1->elmcount++; + _xbt_setset_elm_use(set1->setset, i * BITS_INT + k); + _set_bit(i * BITS_INT + k, set1->bitmap); + } + } + } + } + return; +} + +/** + * \brief Substract two sets + * Substract two sets storing the result in the first one + * \param set1 The first set + * \param set2 The second set + */ +void xbt_setset_substract(xbt_setset_set_t set1, xbt_setset_set_t set2) +{ + int i,k; + /* Traverse the second set and remove every element that is member of it to + the first set */ + for(i=0; i < min(set1->size,set2->size); i++){ + if(set2->bitmap[i] != 0){ + for(k=0; k < BITS_INT; k++){ + if(_is_bit_set(k,set2->bitmap[i]) && _is_bit_set(k, set1->bitmap[i])){ + set1->elmcount--; + _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k); + _unset_bit(i * BITS_INT + k, set1->bitmap); + } + } + } + } + return; +} + +/** + * \brief Intersect two sets + * Intersect two sets storing the result in the first one + * \param set1 The first set + * \param set2 The second set + */ +void xbt_setset_intersect(xbt_setset_set_t set1, xbt_setset_set_t set2) +{ + int i,k; + /* Traverse the first set and remove every element that is not member of the second set */ + for(i=0; i < set1->size; i++){ + if(set1->bitmap[i] != 0){ + for(k=0; k < BITS_INT; k++){ + if(_is_bit_set(k, set1->bitmap[i]) && + (i >= set2->size || !_is_bit_set(k,set2->bitmap[i]))){ + set1->elmcount--; + _xbt_setset_elm_remove(set1->setset, i * BITS_INT + k); + _unset_bit(i * BITS_INT + k, set1->bitmap); + } + } + } + } + return; +} + +/* Get the cursor to point to the first element of a set */ +void xbt_setset_cursor_first(xbt_setset_set_t set, xbt_setset_cursor_t *cursor) +{ + (*cursor) = xbt_new0(s_xbt_setset_cursor_t, 1); + (*cursor)->set = set; + int i,k; + /* Traverse the set and point the cursor to the first element */ + for(i=0; i < set->size; i++){ + if(set->bitmap[i] != 0){ + for(k=0; k < BITS_INT; k++){ + if(_is_bit_set(k,set->bitmap[i])){ + (*cursor)->idx = i * BITS_INT + k; + return; + } + } + } + } +} + +/* Get the data pointed by a cursor */ +int xbt_setset_cursor_get_data(xbt_setset_cursor_t cursor, void **data) +{ + if(cursor->idx == 0){ + xbt_free(cursor); + *data = NULL; + return FALSE; + }else{ + *data = _xbt_setset_idx_to_obj(cursor->set->setset, cursor->idx); + return TRUE; + } +} + +/* Advance a cursor to the next element */ +void xbt_setset_cursor_next(xbt_setset_cursor_t cursor) +{ + int i,k; + cursor->idx++; + /* Traverse the set and point the cursor to the first element */ + for(i = cursor->idx / BITS_INT; i < cursor->set->size; i++){ + if(cursor->set->bitmap[i] != 0){ + for(k = cursor->idx % BITS_INT; k < BITS_INT; k++){ + if(_is_bit_set(k,cursor->set->bitmap[i])){ + cursor->idx = i * BITS_INT + k; + return; + } + } + } + } + cursor->idx = 0; +} + +/* Check if the nth bit of an integer is set or not*/ +unsigned int _is_bit_set(unsigned int bit, unsigned int integer) +{ + return (0x1 << bit) & integer ? TRUE : FALSE; +} + +/* Set the nth bit of an array of integers */ +void _set_bit(unsigned int bit, unsigned int *bitmap) +{ + bitmap[bit / BITS_INT] |= 0x1 << (bit % BITS_INT); +} + +/* Unset the nth bit of an array of integers */ +void _unset_bit(unsigned int bit, unsigned int *bitmap) +{ + bitmap[bit / BITS_INT] &= ~(0x1 << (bit % BITS_INT)); +} + + + + + + + + diff --git a/src/xbt/setset_private.h b/src/xbt/setset_private.h new file mode 100644 index 0000000000..4daf3a9074 --- /dev/null +++ b/src/xbt/setset_private.h @@ -0,0 +1,69 @@ +#include "xbt/dict.h" +#include "xbt/dynar.h" +#include "xbt/setset.h" +#include "xbt/fifo.h" + +#define BITS_INT (8 * sizeof(int)) + +typedef struct s_xbt_setset_elm { + XBT_SETSET_HEADERS; +} s_xbt_setset_elm_t, *xbt_setset_elm_t; + +typedef union u_xbt_setset_elm_entry { + /* Information when the entry is being used */ + struct { + unsigned int refcount; + xbt_setset_elm_t obj; + } info; + /* Information when the entry is free */ + struct { + unsigned long next; + } free; +} u_xbt_setset_elm_entry_t, *xbt_setset_elm_entry_t; + +typedef struct s_xbt_setset_set { + xbt_setset_t setset; /* setset that contains this set */ + unsigned int elmcount; /* number of elements */ + unsigned int size; /* in integers */ + unsigned int *bitmap; /* the bit array */ +} s_xbt_setset_set_t; + +typedef struct s_xbt_setset { + xbt_dynar_t elm_array; /* of s_xbt_setset_elm_entry_t, to find elements by index */ + xbt_fifo_t sets; /* of s_xbt_setset_set_t, memberships in actual sets of setset */ +} s_xbt_setset_t; + +typedef struct s_xbt_setset_cursor { + int idx; /* Actual postition of the cursor (bit number) */ + xbt_setset_set_t set; /* The set associated to the cursor */ +} s_xbt_setset_cursor_t; + +/* Some internal functions */ + +/* Add an object to the setset, this will calculate its index */ +xbt_setset_elm_entry_t _xbt_setset_elm_add(xbt_setset_t setset, void *obj); + +/* Remove from the setset the object stored at idx */ +void _xbt_setset_elm_remove(xbt_setset_t setset, unsigned long idx); + +/* Increase the refcount of an element */ +void _xbt_setset_elm_use(xbt_setset_t setset, unsigned long idx); + +/* Get the object associated to a given index */ +void *_xbt_setset_idx_to_obj(xbt_setset_t setset, unsigned long idx); + +/* Check if the nth bit of an integer is set or not*/ +unsigned int _is_bit_set(unsigned int bit, unsigned int integer); + +/* Set the nth bit of an array of integers */ +void _set_bit(unsigned int bit, unsigned int *bitmap); + +/* Unset the nth bit of an array of integers */ +void _unset_bit(unsigned int bit, unsigned int *bitmap); + + + + + + + -- 2.20.1