+++ /dev/null
-/* xbt/set.h -- api to a generic dictionary */
-
-/* Copyright (c) 2004-2007, 2009-2010, 2012-2014. 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. */
-
-#ifndef _XBT_SET_H
-#define _XBT_SET_H
-
-#include "xbt/misc.h" /* SG_BEGIN_DECL */
-#include "xbt/function_types.h"
-
-SG_BEGIN_DECL()
-
-/** @addtogroup XBT_set
- * @brief A data container consisting in \ref XBT_dict and \ref XBT_dynar
- *
- * The elements stored in such a data structure can be retrieve both by
- * name and by ID. For this to work, the first fields of the structures
- * stored must begin with the following fields:
-\verbatim
- struct {
- unsigned int ID;
- char *name;
- unsigned int name_len;
- // my other fields, constituting the payload
- } my_element_type_t;
-\endverbatim
- *
- * Since we are casting elements around, no protection is ensured by the
- * compiler. It is thus safer to define the headers using the macro
- * defined to that extend:
- *
-\verbatim
-struct {
- XBT_SET_HEADERS;
-
- // my other fields, constituting the payload
-} my_element_type_t;
-\endverbatim
- *
- * It is now possible to remove an element from such a data structure.
- *
- * @todo
- * Such a datastructure was necessary/useful to store the GRAS type
- * descriptions, but it should be reworked to become generic.
- *
- */
-/** @defgroup XBT_set_cons Set and set elements, constructor/destructor
- * @ingroup XBT_set
- *
- * @{
- */
-/** \brief Opaque type representing a set */
-typedef struct xbt_set_ *xbt_set_t;
-
-#define XBT_SET_HEADERS \
- unsigned int ID; \
- char *name; \
- unsigned int name_len
-
-/** \brief It must be possible to cast set elements to this type */
-typedef struct xbt_set_elm_ {
- unsigned int ID; /**< Identificator (system assigned) */
- char *name; /**< Name (user assigned) */
- unsigned int name_len;
- /**< Length of the name */
-} s_xbt_set_elm_t, *xbt_set_elm_t;
-
-/*####[ Functions ]##########################################################*/
-XBT_PUBLIC(xbt_set_t) xbt_set_new(void);
-XBT_PUBLIC(void) xbt_set_free(xbt_set_t * set);
-
-/** @} */
-/** @defgroup XBT_set_basic Sets basic usage
- * @ingroup XBT_set
- *
- * @{
- */
-
-XBT_PUBLIC(void) xbt_set_add(xbt_set_t set, xbt_set_elm_t elm,
- void_f_pvoid_t free_func);
-XBT_PUBLIC(void) xbt_set_remove(xbt_set_t set, xbt_set_elm_t elm);
-XBT_PUBLIC(void) xbt_set_remove_by_name(xbt_set_t set, const char *key);
-XBT_PUBLIC(xbt_set_elm_t) xbt_set_get_by_name_or_null(xbt_set_t set,
- const char *key);
-XBT_PUBLIC(void) xbt_set_remove_by_name_ext(xbt_set_t set, const char *key,
- int key_len);
-XBT_PUBLIC(void) xbt_set_remove_by_id(xbt_set_t set, int id);
-
-XBT_PUBLIC(xbt_set_elm_t) xbt_set_get_by_name(xbt_set_t set,
- const char *key);
-XBT_PUBLIC(xbt_set_elm_t) xbt_set_get_by_name_ext(xbt_set_t set,
- const char *key,
- int key_len);
-XBT_PUBLIC(xbt_set_elm_t) xbt_set_get_by_id(xbt_set_t set, int id);
-
-XBT_PUBLIC(unsigned long) xbt_set_length(const xbt_set_t set);
-
-
-/** @} */
-/** @defgroup XBT_set_curs Sets cursors
- * @ingroup XBT_set
- *
- * \warning Don't add or remove entries to the cache while traversing
- *
- * @{
- */
-
-/** @brief Cursor type */
-typedef struct xbt_set_cursor_ *xbt_set_cursor_t;
-
-XBT_PUBLIC(void) xbt_set_cursor_first(xbt_set_t set,
- xbt_set_cursor_t * cursor);
-XBT_PUBLIC(void) xbt_set_cursor_step(xbt_set_cursor_t cursor);
-XBT_PUBLIC(int) xbt_set_cursor_get_or_free(xbt_set_cursor_t * cursor,
- xbt_set_elm_t * elm);
-
-/** @brief Iterates over the whole set
- * @hideinitializer
- */
-#define xbt_set_foreach(set,cursor,elm) \
- for ((cursor) = NULL, xbt_set_cursor_first((set),&(cursor)) ; \
- xbt_set_cursor_get_or_free(&(cursor),(xbt_set_elm_t*)&(elm)); \
- xbt_set_cursor_step(cursor) )
-
-/* @} */
-SG_END_DECL()
-#endif /* _XBT_SET_H */
+++ /dev/null
-/* set - data container consisting in dict+dynar */
-
-/* Copyright (c) 2004-2014. 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/misc.h"
-#include "xbt/sysdep.h"
-#include "xbt/log.h"
-#include "xbt/ex.h"
-#include "xbt/dynar.h"
-#include "xbt/dict.h"
-
-#include "xbt/set.h"
-
-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_set, xbt,
- "set: data container consisting in dict+dynar");
-
-/*####[ Type definition ]####################################################*/
-typedef struct xbt_set_ {
- xbt_dict_t dict; /* data stored by name */
- xbt_dynar_t dynar; /* data stored by ID */
- xbt_dynar_t available_ids; /* free places in the dynar */
-} s_xbt_set_t;
-
-/*####[ Memory ]############################################################*/
-
-static int _xbt_set_get_id(xbt_set_t set);
-
-/** @brief Constructor */
-xbt_set_t xbt_set_new(void)
-{
- xbt_set_t res = xbt_new(s_xbt_set_t, 1);
-
- res->dict = xbt_dict_new();
- res->dynar = xbt_dynar_new(sizeof(void *), NULL);
- res->available_ids = xbt_dynar_new(sizeof(int), NULL);
-
- return res;
-}
-
-/** @brief Destructor */
-void xbt_set_free(xbt_set_t * set)
-{
- if (*set) {
- xbt_dict_free(&((*set)->dict));
- xbt_dynar_free(&((*set)->dynar));
- xbt_dynar_free(&((*set)->available_ids));
- free(*set);
- *set = NULL;
- }
-}
-
-/* Compute an ID in order to add an element into the set. */
-static int _xbt_set_get_id(xbt_set_t set)
-{
- int id;
- if (!xbt_dynar_is_empty(set->available_ids)) {
- /* if there are some available ids */
- xbt_dynar_pop(set->available_ids, &id);
- } else {
- /* otherwise we will add the element at the dynar end */
- id = xbt_dynar_length(set->dynar);
- }
- return id;
-}
-
-/** @brief Add an element to a set.
- *
- * \param set set to populate
- * \param elm element to add.
- * \param free_func how to free the data
- *
- * elm->name must be set;
- * if elm->name_len <= 0, it is recomputed. If >0, it's used as is;
- * elm->ID is attributed automatically.
- */
-void xbt_set_add(xbt_set_t set, xbt_set_elm_t elm,
- void_f_pvoid_t free_func)
-{
-
- int found = 1;
- xbt_set_elm_t found_in_dict = NULL;
- xbt_ex_t e;
-
- XBT_VERB("add %s to the set", elm->name);
-
- if (elm->name_len <= 0) {
- elm->name_len = strlen(elm->name);
- }
-
- TRY {
- found_in_dict = xbt_dict_get_ext(set->dict, elm->name, elm->name_len);
- }
- CATCH(e) {
- if (e.category != not_found_error)
- RETHROW;
- found = 0;
- elm->ID = _xbt_set_get_id(set);
- xbt_dict_set_ext(set->dict, elm->name, elm->name_len, elm, free_func);
- xbt_dynar_set(set->dynar, elm->ID, &elm);
- XBT_DEBUG("Insertion of key '%s' (id %u)", elm->name, elm->ID);
- xbt_ex_free(e);
- }
-
- if (found) {
- if (elm == found_in_dict) {
- XBT_DEBUG
- ("Ignoring request to insert the same element twice (key %s ; id %u)",
- elm->name, elm->ID);
- return;
- } else {
- elm->ID = found_in_dict->ID;
- XBT_DEBUG("Reinsertion of key %s (id %u)", elm->name, elm->ID);
- xbt_dict_set_ext(set->dict, elm->name, elm->name_len, elm,
- free_func);
- xbt_dynar_set(set->dynar, elm->ID, &elm);
- return;
- }
- }
-}
-
-/** @brief Remove an element from a set.
- *
- * \param set a set
- * \param elm element to remove
- */
-void xbt_set_remove(xbt_set_t set, xbt_set_elm_t elm)
-{
- int id = elm->ID;
- xbt_dynar_push_as(set->available_ids, int, id); /* this id becomes available now */
- xbt_dict_remove_ext(set->dict, elm->name, elm->name_len);
- elm = NULL;
- xbt_dynar_set(set->dynar, id, &elm);
-}
-
-/** @brief Remove an element from a set providing its name.
- *
- * \param set a set
- * \param key name of the element to remove
- */
-void xbt_set_remove_by_name(xbt_set_t set, const char *key)
-{
- xbt_set_elm_t elm = xbt_set_get_by_name(set, key);
- xbt_set_remove(set, elm);
-}
-
-/** @brief Remove an element from a set providing its name
- * and the length of the name.
- *
- * \param set a set
- * \param key name of the element to remove
- * \param key_len length of \a name
- */
-void xbt_set_remove_by_name_ext(xbt_set_t set, const char *key,
- int key_len)
-{
- xbt_set_elm_t elm = xbt_set_get_by_name_ext(set, key, key_len);
- xbt_set_remove(set, elm);
-}
-
-/** @brief Remove an element from a set providing its id.
- *
- * \param set a set
- * \param id id of the element to remove
- */
-void xbt_set_remove_by_id(xbt_set_t set, int id)
-{
- xbt_set_elm_t elm = xbt_set_get_by_id(set, id);
- xbt_set_remove(set, elm);
-}
-
-/** @brief Retrieve data by providing its name.
- *
- * \param set
- * \param name Name of the searched cell
- * \returns the data you're looking for
- */
-xbt_set_elm_t xbt_set_get_by_name(xbt_set_t set, const char *name)
-{
- XBT_DEBUG("Lookup key %s", name);
- return xbt_dict_get(set->dict, name);
-}
-
-/** @brief Retrieve data by providing its name.
- *
- * \param set
- * \param name Name of the searched cell
- * \returns the data you're looking for, returns NULL if not found
- */
-xbt_set_elm_t xbt_set_get_by_name_or_null(xbt_set_t set, const char *name)
-{
- XBT_DEBUG("Lookup key %s", name);
- return xbt_dict_get_or_null(set->dict, name);
-}
-
-/** @brief Retrieve data by providing its name and the length of the name
- *
- * \param set
- * \param name Name of the searched cell
- * \param name_len length of the name, when strlen cannot be trusted
- * \returns the data you're looking for
- *
- * This is useful when strlen cannot be trusted because you don't use a char*
- * as name, you weirdo.
- */
-xbt_set_elm_t xbt_set_get_by_name_ext(xbt_set_t set,
- const char *name, int name_len)
-{
-
- return xbt_dict_get_ext(set->dict, name, name_len);
-}
-
-/** @brief Retrieve data by providing its ID
- *
- * \param set
- * \param id what you're looking for
- * \returns the data you're looking for
- *
- * @warning, if the ID does not exists, you're getting into trouble
- */
-xbt_set_elm_t xbt_set_get_by_id(xbt_set_t set, int id)
-{
- xbt_set_elm_t res;
-
- /* Don't bother checking the bounds, the dynar does so */
-
- res = xbt_dynar_get_as(set->dynar, id, xbt_set_elm_t);
- if (res == NULL) {
- THROWF(not_found_error, 0, "Invalid id: %d", id);
- }
- XBT_DEBUG("Lookup type of id %d (of %lu): %s",
- id, xbt_dynar_length(set->dynar), res->name);
-
- return res;
-}
-
-/**
- * \brief Returns the number of elements in the set
- * \param set a set
- * \return the number of elements in the set
- */
-unsigned long xbt_set_length(const xbt_set_t set)
-{
- return xbt_dynar_length(set->dynar);
-}
-
-/***
- *** Cursors
- ***/
-typedef struct xbt_set_cursor_ {
- xbt_set_t set;
- unsigned int val;
-} s_xbt_set_cursor_t;
-
-/** @brief Create the cursor if it does not exists, rewind it in any case. */
-void xbt_set_cursor_first(xbt_set_t set, xbt_set_cursor_t * cursor)
-{
- xbt_dynar_t dynar;
-
- if (set != NULL) {
- if (!*cursor) {
- XBT_DEBUG("Create the cursor on first use");
- *cursor = xbt_new(s_xbt_set_cursor_t, 1);
- xbt_assert(*cursor,
- "Malloc error during the creation of the cursor");
- }
- (*cursor)->set = set;
-
- /* place the cursor on the first element */
- dynar = set->dynar;
- (*cursor)->val = 0;
- while (xbt_dynar_get_ptr(dynar, (*cursor)->val) == NULL) {
- (*cursor)->val++;
- }
-
- } else {
- *cursor = NULL;
- }
-}
-
-/** @brief Move to the next element. */
-void xbt_set_cursor_step(xbt_set_cursor_t cursor)
-{
- xbt_dynar_t dynar = cursor->set->dynar;
- do {
- cursor->val++;
- }
- while (cursor->val < xbt_dynar_length(dynar) &&
- xbt_dynar_get_ptr(dynar, cursor->val) == NULL);
-}
-
-/** @brief Get current data
- *
- * \return true if it's ok, false if there is no more data
- */
-int xbt_set_cursor_get_or_free(xbt_set_cursor_t * curs,
- xbt_set_elm_t * elm)
-{
- xbt_set_cursor_t cursor;
-
- if (!curs || !(*curs))
- return FALSE;
-
- cursor = *curs;
-
- if (cursor->val >= xbt_dynar_length(cursor->set->dynar)) {
- free(cursor);
- *curs = NULL;
- return FALSE;
- }
-
- xbt_dynar_get_cpy(cursor->set->dynar, cursor->val, elm);
- return TRUE;
-}
-
-#ifdef SIMGRID_TEST
-#include "xbt.h"
-#include "xbt/ex.h"
-
-XBT_TEST_SUITE("set", "Set data container");
-
-typedef struct {
- /* headers */
- unsigned int ID;
- char *name;
- unsigned int name_len;
-
- /* payload */
- char *data;
-} s_my_elem_t, *my_elem_t;
-
-
-static void my_elem_free(void *e)
-{
- my_elem_t elm = (my_elem_t) e;
-
- if (elm) {
- free(elm->name);
- free(elm->data);
- free(elm);
- }
-}
-
-static void debuged_add(xbt_set_t set, const char *name, const char *data)
-{
- my_elem_t elm;
-
- elm = xbt_new(s_my_elem_t, 1);
- elm->name = xbt_strdup(name);
- elm->name_len = 0;
-
- elm->data = xbt_strdup(data);
-
- xbt_test_log("Add %s (->%s)", name, data);
- xbt_set_add(set, (xbt_set_elm_t) elm, &my_elem_free);
-}
-
-static void fill(xbt_set_t * set)
-{
- xbt_test_add("Fill in the data set");
-
- *set = xbt_set_new();
- debuged_add(*set, "12", "12");
- debuged_add(*set, "12a", "12a");
- debuged_add(*set, "12b", "12b");
- debuged_add(*set, "123", "123");
- debuged_add(*set, "123456", "123456");
- xbt_test_log("Child becomes child of what to add");
- debuged_add(*set, "1234", "1234");
- xbt_test_log("Need of common ancestor");
- debuged_add(*set, "123457", "123457");
-}
-
-static void search_name(xbt_set_t head, const char *key)
-{
- my_elem_t elm;
-
- xbt_test_add("Search by name %s", key);
- elm = (my_elem_t) xbt_set_get_by_name(head, key);
- xbt_test_log(" Found %s (under ID %u)\n",
- elm ? elm->data : "(null)", elm ? elm->ID : -1);
- if (elm == NULL)
- THROWF(mismatch_error, 0,
- "Got a null elm for name %s", key);
- if (strcmp(key, elm->name))
- THROWF(mismatch_error, 0, "The key (%s) is not the one expected (%s)",
- key, elm->name);
- if (strcmp(elm->name, elm->data))
- THROWF(mismatch_error, 0, "The name (%s) != data (%s)", key,
- elm->name);
- fflush(stdout);
-}
-
-static void search_id(xbt_set_t head, int id, const char *key)
-{
- my_elem_t elm;
-
- xbt_test_add("Search by id %d", id);
- elm = (my_elem_t) xbt_set_get_by_id(head, id);
- xbt_test_log("Found %s (data %s)",
- elm ? elm->name : "(null)", elm ? elm->data : "(null)");
- if (elm == NULL)
- THROWF(mismatch_error, 0,
- "Got a null elm for id %d", id);
- if (id != elm->ID)
- THROWF(mismatch_error, 0,
- "The found ID (%u) is not the one expected (%d)", elm->ID, id);
- if (strcmp(key, elm->name))
- THROWF(mismatch_error, 0, "The key (%s) is not the one expected (%s)",
- elm->name, key);
- if (strcmp(elm->name, elm->data))
- THROWF(mismatch_error, 0, "The name (%s) != data (%s)",
- elm->name, elm->data);
-}
-
-
-static void traverse(xbt_set_t set)
-{
- xbt_set_cursor_t cursor = NULL;
- my_elem_t elm = NULL;
-
- xbt_set_foreach(set, cursor, elm) {
- xbt_test_assert(elm, "Dude ! Got a null elm during traversal!");
- if (!elm)
- continue;
- xbt_test_log("Id(%u): %s->%s\n", elm->ID, elm->name, elm->data);
- xbt_test_assert(!strcmp(elm->name, elm->data),
- "Key(%s) != value(%s). Aborting", elm->name,
- elm->data);
- }
-}
-
-static void search_not_found(xbt_set_t set, const char *data)
-{
- xbt_ex_t e;
-
- xbt_test_add("Search %s (expected not to be found)", data);
- TRY {
- xbt_set_get_by_name(set, data);
- THROWF(unknown_error, 0,
- "Found something which shouldn't be there (%s)", data);
- }
- CATCH(e) {
- if (e.category != not_found_error)
- xbt_test_exception(e);
- xbt_ex_free(e);
- }
-}
-
-xbt_set_t set = NULL;
-
-
-XBT_TEST_UNIT("basic", test_set_basic, "Basic usage")
-{
- set = NULL;
-
- xbt_test_add("Traverse the empty set");
- traverse(set);
-
- xbt_test_add("Free a data set");
- fill(&set);
- xbt_set_free(&set);
-
- xbt_test_add("Free the NULL data set");
- xbt_set_free(&set);
-
-}
-
-XBT_TEST_UNIT("change", test_set_change, "Changing some values")
-{
- fill(&set);
-
- xbt_test_add("Change 123 to 'Changed 123'");
- debuged_add(set, "123", "Changed 123");
-
- xbt_test_add("Change 123 back to '123'");
- debuged_add(set, "123", "123");
-
- xbt_test_add("Change 12a to 'Dummy 12a'");
- debuged_add(set, "12a", "Dummy 12a");
-
- xbt_test_add("Change 12a to '12a'");
- debuged_add(set, "12a", "12a");
-
- /* xbt_dict_dump(head,(void (*)(void*))&printf); */
- xbt_test_add("Traverse the resulting data set");
- traverse(set);
-}
-
-XBT_TEST_UNIT("retrieve", test_set_retrieve, "Retrieving some values")
-{
- my_elem_t elm;
-
- xbt_test_add("Search 123");
- elm = (my_elem_t) xbt_set_get_by_name(set, "123");
- xbt_test_assert(elm, "elm must be there");
- xbt_assert(elm && !strcmp("123", elm->data));
-
- search_not_found(set, "Can't be found");
- search_not_found(set, "123 Can't be found");
- search_not_found(set, "12345678 NOT");
-
- search_name(set, "12");
- search_name(set, "12a");
- search_name(set, "12b");
- search_name(set, "123");
- search_name(set, "123456");
- search_name(set, "1234");
- search_name(set, "123457");
-
- search_id(set, 0, "12");
- search_id(set, 1, "12a");
- search_id(set, 2, "12b");
- search_id(set, 3, "123");
- search_id(set, 4, "123456");
- search_id(set, 5, "1234");
- search_id(set, 6, "123457");
-
- xbt_test_add("Traverse the resulting data set");
- traverse(set);
-
- /* xbt_dict_dump(head,(void (*)(void*))&printf); */
-
- xbt_test_add("Free the data set (twice)");
- xbt_set_free(&set);
- xbt_set_free(&set);
-
- xbt_test_add("Traverse the resulting data set");
- traverse(set);
-}
-
-XBT_TEST_UNIT("remove", test_set_remove, "Removing some values")
-{
- my_elem_t elm;
-
- fill(&set);
-
- xbt_set_remove_by_name(set, "12a");
- search_not_found(set, "12a");
-
- search_name(set, "12");
- search_name(set, "12b");
- search_name(set, "123");
- search_name(set, "123456");
- search_name(set, "1234");
- search_name(set, "123457");
-
- search_id(set, 0, "12");
- search_id(set, 2, "12b");
- search_id(set, 3, "123");
- search_id(set, 4, "123456");
- search_id(set, 5, "1234");
- search_id(set, 6, "123457");
-
- debuged_add(set, "12anew", "12anew");
- elm = (my_elem_t) xbt_set_get_by_id(set, 1);
- xbt_test_assert(elm->ID == 1, "elm->ID is %u but should be 1", elm->ID);
-
- xbt_set_free(&set);
-}
-
-#endif /* SIMGRID_TEST */
