From b6491c34258d1493b01c3bc9514c87f0abb96edc Mon Sep 17 00:00:00 2001 From: mquinson Date: Mon, 1 Mar 2004 20:52:56 +0000 Subject: [PATCH 1/1] A new data container coupling the facilities of a dynar with the ones of a dict git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@39 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- include/set.h | 72 ++++++++++++ src/xbt/set.c | 224 +++++++++++++++++++++++++++++++++++ testsuite/xbt/set_usage.c | 241 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 537 insertions(+) create mode 100644 include/set.h create mode 100644 src/xbt/set.c create mode 100644 testsuite/xbt/set_usage.c diff --git a/include/set.h b/include/set.h new file mode 100644 index 0000000000..efe493b7ab --- /dev/null +++ b/include/set.h @@ -0,0 +1,72 @@ +/* $Id$ */ + +/* gras/set.h -- api to a generic dictionary */ + +/* Authors: Martin Quinson */ +/* Copyright (C) 2004 the OURAGAN project. */ + +/* 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 _GRAS_SET_H +#define _GRAS_SET_H + +#ifdef __cplusplus +extern "C" +#endif + +/*####[ Type definition ]####################################################*/ +typedef struct gras_set_ gras_set_t; +typedef struct gras_set_elm_ { + unsigned int ID; + char *name; + unsigned int name_len; +} gras_set_elm_t; + +/*####[ Functions ]##########################################################*/ + +gras_error_t gras_set_new (gras_set_t **dst); +void gras_set_free(gras_set_t **set); + + +gras_error_t gras_set_add (gras_set_t *set, + gras_set_elm_t *elm, + void_f_pvoid_t *free_func); + +/*----[ gras_set_retrieve ]-------------------------------------------------*/ +/* Search the given #key#. data=NULL when not found. */ +/*---------------------------------------------------------------------------*/ +gras_error_t gras_set_get_by_name (gras_set_t *set, + const char *key, + /* OUT */gras_set_elm_t **dst); +gras_error_t gras_set_get_by_name_ext(gras_set_t *set, + const char *name, + int name_len, + /* OUT */gras_set_elm_t **dst); +gras_error_t gras_set_get_by_id (gras_set_t *set, + int id, + /* OUT */gras_set_elm_t **dst); + +/*####[ Cache cursor functions ]#############################################*/ +/* To traverse (simple) caches */ +/* Don't add or remove entries to the cache while traversing !!! */ +/*###########################################################################*/ +typedef struct gras_set_cursor_ gras_set_cursor_t; +/* creator/destructor */ +void gras_set_cursor_first (gras_set_t *set, + gras_set_cursor_t **cursor); +void gras_set_cursor_step (gras_set_cursor_t *cursor); +int gras_set_cursor_get_or_free (gras_set_cursor_t **cursor, + gras_set_elm_t **elm); + +#define gras_set_foreach(set,cursor,elm) \ + for (cursor=NULL, gras_set_cursor_first((set),&(cursor)) ; \ + gras_set_cursor_get_or_free(&(cursor),(gras_set_elm_t**)&(elm)); \ + gras_set_cursor_step(cursor) ) + +#ifdef __cplusplus +} +#endif + +#endif /* _GRAS_SET_H */ diff --git a/src/xbt/set.c b/src/xbt/set.c new file mode 100644 index 0000000000..d452b1a64e --- /dev/null +++ b/src/xbt/set.c @@ -0,0 +1,224 @@ +/* $Id$ */ + +/* set - data container consisting in dict+dynar */ + +/* Authors: Martin Quinson */ +/* Copyright (C) 2004 the GRAS posse. */ + +/* 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 "gras_private.h" + +GRAS_LOG_NEW_DEFAULT_SUBCATEGORY(set,GRAS); + +/*####[ Type definition ]####################################################*/ +struct gras_set_ { + gras_dict_t *dict; /* data stored by name */ + gras_dynar_t *dynar; /* data stored by ID */ +}; + +/*####[ Memory ]############################################################*/ +/** + * gras_set_new: + * @dst: where to + * + * Creates a new set. + */ +gras_error_t gras_set_new (gras_set_t **dst) { + gras_set_t *res=(gras_set_t*)malloc(sizeof(gras_set_t)); + gras_error_t errcode; + + if (!res) + RAISE_MALLOC; + + TRY(gras_dict_new (&(res->dict))); + TRY(gras_dynar_new(&(res->dynar), sizeof(void*),NULL)); + + *dst=res; + return no_error; +} + +/** + * gras_set_free: + * @set: + * + * Frees a set. + */ +void gras_set_free(gras_set_t **set) { + if (*set) { + gras_dict_free ( &( (*set)->dict ) ); + gras_dynar_free( (*set)->dynar ); + free(*set); + *set=NULL; + } +} + +/** + * gras_set_add: + * @set: set to populate + * @elm: element to add. + * @free_ctn: How to add the data + * + * Add an element to a set. + * + * elm->name must be set; + * elm->name_len is used as is unless it's <= 0 (in which case it's recomputed); + * elm->ID is attributed automatically. + */ +gras_error_t gras_set_add (gras_set_t *set, + gras_set_elm_t *elm, + void_f_pvoid_t *free_func) { + + gras_error_t errcode; + gras_set_elm_t *found_in_dict; + + if (elm->name_len <= 0) { + elm->name_len = strlen(elm->name); + } + + errcode = gras_dict_retrieve_ext (set->dict, + elm->name, elm->name_len, + (void**) &found_in_dict); + if (errcode == no_error) { + elm->ID=found_in_dict->ID; + DEBUG2("Reinsertion of key %s (id %d)", elm->name, elm->ID); + TRY(gras_dict_insert_ext(set->dict, elm->name, elm->name_len, elm, free_func)); + TRY(gras_dynar_set(set->dynar, elm->ID, &elm)); + return no_error; + + } else if (errcode != mismatch_error) { + return errcode; /* I expected mismatch_error */ + } + + elm->ID = gras_dynar_length( set->dynar ); + TRY(gras_dict_insert_ext(set->dict, elm->name, elm->name_len, elm, free_func)); + TRY(gras_dynar_set(set->dynar, elm->ID, &elm)); + DEBUG2("Insertion of key %s (id %d)", elm->name, elm->ID); + + return no_error; +} + +/** + * gras_set_get_by_name: + * @set: + * @name: Name of the searched cell + * @dst: where to put the found data into + * + * Retrieve a data stored in the cell by providing its name. + */ +gras_error_t gras_set_get_by_name (gras_set_t *set, + const char *name, + /* OUT */gras_set_elm_t **dst) { + + return gras_dict_retrieve_ext(set->dict, name, strlen(name), (void**) dst); +} +/** + * gras_set_get_by_name_ext: + * @set: + * @name: Name of the searched cell + * @name_len: length of the name, when strlen cannot be trusted + * @dst: where to put the found data into + * + * Retrieve a data stored in the cell by providing its name (and the length + * of the name, when strlen cannot be trusted because you don't use a char* + * as name, you weird guy). + */ +gras_error_t gras_set_get_by_name_ext(gras_set_t *set, + const char *name, + int name_len, + /* OUT */gras_set_elm_t **dst) { + + return gras_dict_retrieve_ext (set->dict, name, name_len, (void**)dst); +} + +/** + * gras_set_get_by_code: + * @set: + * @name: Name of the searched cell + * @name_len: length of the name, when strlen cannot be trusted + * @dst: where to put the found data into + * + * Retrieve a data stored in the cell by providing its name (and the length + * of the name, when strlen cannot be trusted because you don't use a char* + * as name, you weird guy). + */ +gras_error_t gras_set_get_by_id (gras_set_t *set, + int id, + /* OUT */gras_set_elm_t **dst) { + if (id < gras_dynar_length(set->dynar) && + id >= 0) { + gras_dynar_get(set->dynar,id,dst); + + } else { + DEBUG1("Cannot get ID %d: out of bound", id); + return mismatch_error; + } + return no_error; +} + +/*** + *** Cursors + ***/ +struct gras_set_cursor_ { + gras_set_t *set; + int val; +}; + +/** + * gras_set_cursor_first: + * @set: on what to let the cursor iterate + * @cursor: dest address + * + * Create the cursor if it does not exists. Rewind it in any case. + */ +void gras_set_cursor_first (gras_set_t *set, + gras_set_cursor_t **cursor) { + + if (set != NULL) { + if (!*cursor) { + DEBUG0("Create the cursor on first use"); + *cursor = (gras_set_cursor_t*)malloc(sizeof(gras_set_cursor_t)); + gras_assert0(*cursor, + "Malloc error during the creation of the cursor"); + } + (*cursor)->set = set; + gras_dynar_cursor_first(set->dynar, &( (*cursor)->val) ); + } else { + *cursor = NULL; + } +} + +/** + * gras_set_cursor_step: + * @cursor: the cursor + * + * Move to the next element. + */ +void gras_set_cursor_step (gras_set_cursor_t *cursor) { + gras_dynar_cursor_step(cursor->set->dynar, &( cursor->val ) ); +} + +/** + * gras_set_cursor_get_or_free: + * @cursor: the cursor + * @Returns: true if it's ok, false if there is no more data + * + * Get current data + */ +int gras_set_cursor_get_or_free (gras_set_cursor_t **curs, + gras_set_elm_t **elm) { + gras_set_cursor_t *cursor; + + if (!curs || !(*curs)) + return FALSE; + + cursor=*curs; + + if (! gras_dynar_cursor_get( cursor->set->dynar,&(cursor->val),elm) ) { + free(cursor); + *curs=NULL; + return FALSE; + } + return TRUE; +} diff --git a/testsuite/xbt/set_usage.c b/testsuite/xbt/set_usage.c new file mode 100644 index 0000000000..6db7d21324 --- /dev/null +++ b/testsuite/xbt/set_usage.c @@ -0,0 +1,241 @@ +/* $Id$ */ + +/* set_usage - A test of normal usage of a set */ + +/* Authors: Martin Quinson */ +/* Copyright (C) 2004 the OURAGAN project. */ + +/* 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 +#include + +#include + +GRAS_LOG_NEW_DEFAULT_CATEGORY(test); +GRAS_LOG_EXTERNAL_CATEGORY(set); + +typedef struct { + /* headers */ + unsigned int ID; + char *name; + unsigned int name_len; + + /* payload */ + char *data; +}my_elem_t; + +static gras_error_t fill(gras_set_t **set); +static gras_error_t debuged_add(gras_set_t *set,const char*key); +static gras_error_t debuged_add_with_data(gras_set_t *set, + const char *name, + const char *data); +static gras_error_t search_name(gras_set_t *set,const char*key); +static gras_error_t search_id(gras_set_t *head, + int id, + const char*expected_key); +static gras_error_t traverse(gras_set_t *set); + +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 gras_error_t debuged_add_with_data(gras_set_t *set, + const char *name, + const char *data) { + + gras_error_t errcode; + my_elem_t *elm; + + elm = (my_elem_t*)malloc(sizeof(my_elem_t)); + elm->name=strdup(name); + elm->name_len=0; + + elm->data=strdup(data); + + printf(" - Add %s ",name); + if (strcmp(name,data)) { + printf("(->%s)",data); + } + printf("\n"); + errcode=gras_set_add(set, + (gras_set_elm_t*)elm, + &my_elem_free); + return errcode; +} + +static gras_error_t debuged_add(gras_set_t *set, + const char *name) { + return debuged_add_with_data(set, name, name); +} + +static gras_error_t fill(gras_set_t **set) { + gras_error_t errcode; + printf("\n Fill in the data set\n"); + + TRY(gras_set_new(set)); + TRY(debuged_add(*set,"12")); + TRY(debuged_add(*set,"12a")); + TRY(debuged_add(*set,"12b")); + TRY(debuged_add(*set,"123")); + TRY(debuged_add(*set,"123456")); + // Child becomes child of what to add + TRY(debuged_add(*set,"1234")); + // Need of common ancestor + TRY(debuged_add(*set,"123457")); + + return no_error; +} + +static gras_error_t search_name(gras_set_t *head,const char*key) { + gras_error_t errcode; + my_elem_t *elm; + + errcode=gras_set_get_by_name(head,key,(gras_set_elm_t**)&elm); + printf(" - Search by name %s. Found %s (under ID %d)\n", + key, + elm? elm->data:"(null)", + elm? elm->ID:-1); + if (strcmp(key,elm->name)) { + printf(" The key (%s) is not the one expected (%s)\n", + key,elm->name); + return mismatch_error; + } + if (strcmp(elm->name,elm->data)) { + printf(" The name (%s) != data (%s)\n", + elm->name,elm->data); + return mismatch_error; + } + fflush(stdout); + return errcode; +} + +static gras_error_t search_id(gras_set_t *head,int id,const char*key) { + gras_error_t errcode; + my_elem_t *elm; + + errcode=gras_set_get_by_id(head,id,(gras_set_elm_t**)&elm); + printf(" - Search by id %d. Found %s (data %s)\n", + id, + elm? elm->name:"(null)", + elm? elm->data:"(null)"); + if (id != elm->ID) { + printf(" The found ID (%d) is not the one expected (%d)\n", + elm->ID,id); + return mismatch_error; + } + if (strcmp(key,elm->name)) { + printf(" The key (%s) is not the one expected (%s)\n", + elm->name,key); + return mismatch_error; + } + if (strcmp(elm->name,elm->data)) { + printf(" The name (%s) != data (%s)\n", + elm->name,elm->data); + return mismatch_error; + } + fflush(stdout); + return errcode; +} + + +static gras_error_t traverse(gras_set_t *set) { + gras_set_cursor_t *cursor=NULL; + my_elem_t *elm=NULL; + + gras_set_foreach(set,cursor,elm) { + gras_assert0(elm,"Dude ! Got a null elm during traversal!"); + printf(" - Id(%d): %s->%s\n",elm->ID,elm->name,elm->data); + if (strcmp(elm->name,elm->data)) { + printf("Key(%s) != value(%s). Abording\n",elm->name,elm->data); + abort(); + } + } + return no_error; +} + +void parse_log_opt(int argc, char **argv,const char *deft); + +int main(int argc,char **argv) { + gras_error_t errcode; + gras_set_t *set=NULL; + my_elem_t *elm; + + parse_log_opt(argc,argv,"set.thresh=verbose"); + + printf("\nData set: USAGE test:\n"); + + printf(" Traverse the empty set\n"); + TRYFAIL(traverse(set)); + + TRYFAIL(fill(&set)); + printf(" Free the data set\n"); + gras_set_free(&set); + printf(" Free the data set again\n"); + gras_set_free(&set); + + TRYFAIL(fill(&set)); + + printf(" - Change some values\n"); + printf(" - Change 123 to 'Changed 123'\n"); + TRYFAIL(debuged_add_with_data(set,"123","Changed 123")); + printf(" - Change 123 back to '123'\n"); + TRYFAIL(debuged_add_with_data(set,"123","123")); + printf(" - Change 12a to 'Dummy 12a'\n"); + TRYFAIL(debuged_add_with_data(set,"12a","Dummy 12a")); + printf(" - Change 12a to '12a'\n"); + TRYFAIL(debuged_add_with_data(set,"12a","12a")); + + // gras_dict_dump(head,(void (*)(void*))&printf); + printf(" - Traverse the resulting data set\n"); + TRYFAIL(traverse(set)); + + printf(" - Retrive values\n"); + TRYFAIL(gras_set_get_by_name(set,"123",(gras_set_elm_t**)&elm)); + assert(elm); + TRYFAIL(strcmp("123",elm->data)); + + TRYEXPECT(gras_set_get_by_name(set,"Can't be found",(gras_set_elm_t**)&elm), + mismatch_error); + TRYEXPECT(gras_set_get_by_name(set,"123 Can't be found",(gras_set_elm_t**)&elm), + mismatch_error); + TRYEXPECT(gras_set_get_by_name(set,"12345678 NOT",(gras_set_elm_t**)&elm), + mismatch_error); + + TRYFAIL(search_name(set,"12")); + TRYFAIL(search_name(set,"12a")); + TRYFAIL(search_name(set,"12b")); + TRYFAIL(search_name(set,"123")); + TRYFAIL(search_name(set,"123456")); + TRYFAIL(search_name(set,"1234")); + TRYFAIL(search_name(set,"123457")); + + TRYFAIL(search_id(set,0,"12")); + TRYFAIL(search_id(set,1,"12a")); + TRYFAIL(search_id(set,2,"12b")); + TRYFAIL(search_id(set,3,"123")); + TRYFAIL(search_id(set,4,"123456")); + TRYFAIL(search_id(set,5,"1234")); + TRYFAIL(search_id(set,6,"123457")); + + printf(" - Traverse the resulting data set\n"); + TRYFAIL(traverse(set)); + + // gras_dict_dump(head,(void (*)(void*))&printf); + + printf(" Free the data set (twice)\n"); + gras_set_free(&set); + gras_set_free(&set); + + printf(" - Traverse the resulting data set\n"); + TRYFAIL(traverse(set)); + + return 0; +} -- 2.20.1