src/xbt/set.c

   1 /* $Id$ */
   2
   3 /* set - data container consisting in dict+dynar                            */
   4
   5 /* Copyright (c) 2004 Martin Quinson. All rights reserved.                  */
   6
   7 /* This program is free software; you can redistribute it and/or modify it
   8  * under the terms of the license (GNU LGPL) which comes with this package. */
   9
  10 #include "xbt/misc.h"
  11 #include "xbt/sysdep.h"
  12 #include "xbt/log.h"
  13 #include "xbt/ex.h"
  14 #include "xbt/dynar.h"
  15 #include "xbt/dict.h"
  16
  17 #include "xbt/set.h"
  18
  19 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_set,xbt,
  20              "set: data container consisting in dict+dynar");
  21
  22 /*####[ Type definition ]####################################################*/
  23 typedef struct xbt_set_ {
  24   xbt_dict_t  dict;  /* data stored by name */
  25   xbt_dynar_t dynar; /* data stored by ID   */
  26   xbt_dynar_t available_ids; /* free places in the dynar */
  27 } s_xbt_set_t;
  28
  29 /*####[ Memory  ]############################################################*/
  30
  31 static int _xbt_set_get_id(xbt_set_t set);
  32
  33 /** @brief Constructor */
  34 xbt_set_t xbt_set_new(void) {
  35   xbt_set_t res = xbt_new(s_xbt_set_t, 1);
  36
  37   res->dict = xbt_dict_new();
  38   res->dynar = xbt_dynar_new(sizeof(void*), NULL);
  39   res->available_ids = xbt_dynar_new(sizeof(int), NULL);
  40
  41   return res;
  42 }
  43
  44 /** @brief Destructor */
  45 void  xbt_set_free(xbt_set_t *set) {
  46   if (*set) {
  47     xbt_dict_free ( &( (*set)->dict  ) );
  48     xbt_dynar_free( &( (*set)->dynar ) );
  49     xbt_dynar_free( &( (*set)->available_ids ) );
  50     free(*set);
  51     *set = NULL;
  52   }
  53 }
  54
  55 /* Compute an ID in order to add an element into the set. */
  56 static int _xbt_set_get_id(xbt_set_t set) {
  57   int id;
  58   if (xbt_dynar_length(set->available_ids) > 0) {
  59     /* if there are some available ids */
  60     xbt_dynar_pop(set->available_ids, &id);
  61   }
  62   else {
  63     /* otherwise we will add the element at the dynar end */
  64     id = xbt_dynar_length(set->dynar);
  65   }
  66   return id;
  67 }
  68
  69 /** @brief Add an element to a set.
  70  *
  71  * \param set set to populate
  72  * \param elm element to add.
  73  * \param free_func How to add the data
  74  *
  75  * elm->name must be set;
  76  * if elm->name_len <= 0, it is recomputed. If >0, it's used as is;
  77  * elm->ID is attributed automatically.
  78  */
  79 void xbt_set_add    (xbt_set_t      set,
  80                       xbt_set_elm_t  elm,
  81                       void_f_pvoid_t *free_func) {
  82
  83   int found = 1;
  84   xbt_set_elm_t found_in_dict = NULL;
  85   xbt_ex_t e;
  86
  87   VERB1("add %s to the set",elm->name);
  88
  89   if (elm->name_len <= 0) {
  90     elm->name_len = strlen(elm->name);
  91   }
  92
  93   TRY {
  94     found_in_dict = xbt_dict_get_ext (set->dict,
  95                                       elm->name, elm->name_len);
  96   } CATCH(e) {
  97     if (e.category != not_found_error)
  98       RETHROW;
  99     found = 0;
 100     elm->ID = _xbt_set_get_id(set);
 101     xbt_dict_set_ext(set->dict, elm->name, elm->name_len, elm, free_func);
 102     xbt_dynar_set(set->dynar, elm->ID, &elm);
 103     DEBUG2("Insertion of key '%s' (id %d)", elm->name, elm->ID);
 104     xbt_ex_free(e);
 105   }
 106
 107   if (found) {
 108     if (elm == found_in_dict) {
 109       DEBUG2("Ignoring request to insert the same element twice (key %s ; id %d)",
 110              elm->name, elm->ID);
 111       return;
 112     } else {
 113       elm->ID=found_in_dict->ID;
 114       DEBUG2("Reinsertion of key %s (id %d)", elm->name, elm->ID);
 115       xbt_dict_set_ext(set->dict, elm->name, elm->name_len, elm, free_func);
 116       xbt_dynar_set(set->dynar, elm->ID, &elm);
 117       return;
 118     }
 119   }
 120 }
 121
 122 /** @brief Remove an element from a set.
 123  *
 124  * \param set a set
 125  * \param elm element to remove
 126  */
 127 void xbt_set_remove (xbt_set_t set, xbt_set_elm_t elm) {
 128   int id = elm->ID;
 129   xbt_dynar_push_as(set->available_ids, int, id); /* this id becomes available now */
 130   xbt_dict_remove_ext(set->dict, elm->name, elm->name_len);
 131   elm = NULL;
 132   xbt_dynar_set(set->dynar, id, &elm);
 133 }
 134
 135 /** @brief Remove an element from a set providing its name.
 136  *
 137  * \param set a set
 138  * \param key name of the element to remove
 139  */
 140 void xbt_set_remove_by_name (xbt_set_t set, const char *key) {
 141   xbt_set_elm_t elm = xbt_set_get_by_name(set, key);
 142   xbt_set_remove(set, elm);
 143 }
 144
 145 /** @brief Remove an element from a set providing its name
 146  * and the length of the name.
 147  *
 148  * \param set a set
 149  * \param key name of the element to remove
 150  * \param key_len length of \a name
 151  */
 152 void xbt_set_remove_by_name_ext (xbt_set_t set, const char *key, int key_len) {
 153   xbt_set_elm_t elm = xbt_set_get_by_name_ext(set, key, key_len);
 154   xbt_set_remove(set, elm);
 155 }
 156
 157 /** @brief Remove an element from a set providing its id.
 158  *
 159  * \param set a set
 160  * \param id id of the element to remove
 161  */
 162 void xbt_set_remove_by_id (xbt_set_t set, int id) {
 163   xbt_set_elm_t elm = xbt_set_get_by_id(set, id);
 164   xbt_set_remove(set, elm);
 165 }
 166
 167 /** @brief Retrieve data by providing its name.
 168  *
 169  * \param set
 170  * \param name Name of the searched cell
 171  * \returns the data you're looking for
 172  */
 173 xbt_set_elm_t xbt_set_get_by_name    (xbt_set_t     set,
 174                                       const char     *name) {
 175   DEBUG1("Lookup key %s",name);
 176   return xbt_dict_get(set->dict, name);
 177 }
 178
 179 /** @brief Retrieve data by providing its name and the length of the name
 180  *
 181  * \param set
 182  * \param name Name of the searched cell
 183  * \param name_len length of the name, when strlen cannot be trusted
 184  * \returns the data you're looking for
 185  *
 186  * This is useful when strlen cannot be trusted because you don't use a char*
 187  * as name, you weirdo.
 188  */
 189 xbt_set_elm_t xbt_set_get_by_name_ext(xbt_set_t      set,
 190                                       const char     *name,
 191                                       int             name_len) {
 192
 193   return xbt_dict_get_ext (set->dict, name, name_len);
 194 }
 195
 196 /** @brief Retrieve data by providing its ID
 197  *
 198  * \param set
 199  * \param id what you're looking for
 200  * \returns the data you're looking for
 201  *
 202  * @warning, if the ID does not exists, you're getting into trouble
 203  */
 204 xbt_set_elm_t xbt_set_get_by_id (xbt_set_t set, int id) {
 205   xbt_set_elm_t res;
 206
 207   /* Don't bother checking the bounds, the dynar does so */
 208
 209   res = xbt_dynar_get_as(set->dynar,id, xbt_set_elm_t);
 210   if (res == NULL) {
 211     THROW1(not_found_error, 0, "Invalid id: %d", id);
 212   }
 213   DEBUG3("Lookup type of id %d (of %lu): %s",
 214          id, xbt_dynar_length(set->dynar), res->name);
 215
 216   return res;
 217 }
 218
 219 /**
 220  * \brief Returns the number of elements in the set
 221  * \param set a set
 222  * \return the number of elements in the set
 223  */
 224 unsigned long xbt_set_length (const xbt_set_t set) {
 225    return xbt_dynar_length(set->dynar);
 226 }
 227
 228 /***
 229  *** Cursors
 230  ***/
 231 typedef struct xbt_set_cursor_ {
 232   xbt_set_t set;
 233   int val;
 234 } s_xbt_set_cursor_t;
 235
 236 /** @brief Create the cursor if it does not exists, rewind it in any case. */
 237 void         xbt_set_cursor_first       (xbt_set_t         set,
 238                                           xbt_set_cursor_t *cursor) {
 239   xbt_dynar_t dynar;
 240
 241   if (set != NULL) {
 242     if (!*cursor) {
 243       DEBUG0("Create the cursor on first use");
 244       *cursor = xbt_new(s_xbt_set_cursor_t,1);
 245       xbt_assert0(*cursor,
 246                    "Malloc error during the creation of the cursor");
 247     }
 248     (*cursor)->set = set;
 249
 250     /* place the cursor on the first element */
 251     dynar = set->dynar;
 252     (*cursor)->val = 0;
 253     while (xbt_dynar_get_ptr(dynar, (*cursor)->val) == NULL) {
 254       (*cursor)->val++;
 255     }
 256
 257   } else {
 258     *cursor = NULL;
 259   }
 260 }
 261
 262 /** @brief Move to the next element.  */
 263 void         xbt_set_cursor_step        (xbt_set_cursor_t cursor) {
 264   xbt_dynar_t dynar = cursor->set->dynar;
 265   do {
 266     cursor->val++;
 267   }
 268   while (cursor->val < xbt_dynar_length(dynar) &&
 269          xbt_dynar_get_ptr(dynar, cursor->val) == NULL);
 270 }
 271
 272 /** @brief Get current data
 273  *
 274  * \return true if it's ok, false if there is no more data
 275  */
 276 int          xbt_set_cursor_get_or_free (xbt_set_cursor_t *curs,
 277                                           xbt_set_elm_t    *elm) {
 278   xbt_set_cursor_t cursor;
 279
 280   if (!curs || !(*curs))
 281     return FALSE;
 282
 283   cursor=*curs;
 284
 285   if (cursor->val >= xbt_dynar_length(cursor->set->dynar)) {
 286     free(cursor);
 287     *curs=NULL;
 288     return FALSE;
 289   }
 290
 291   xbt_dynar_get_cpy(cursor->set->dynar, cursor->val, elm);
 292   return TRUE;
 293 }
 294
 295 #ifdef SIMGRID_TEST
 296 #include "xbt.h"
 297 #include "xbt/ex.h"
 298
 299 XBT_TEST_SUITE("set","Set data container");
 300
 301 typedef struct  {
 302   /* headers */
 303   unsigned int ID;
 304   char        *name;
 305   unsigned int name_len;
 306
 307   /* payload */
 308   char         *data;
 309 } s_my_elem_t,*my_elem_t;
 310
 311
 312 static void my_elem_free(void *e) {
 313   my_elem_t elm=(my_elem_t)e;
 314
 315   if (elm) {
 316     free(elm->name);
 317     free(elm->data);
 318     free(elm);
 319   }
 320 }
 321
 322 static void debuged_add(xbt_set_t  set,
 323                         const char *name,
 324                         const char *data) {
 325   my_elem_t    elm;
 326
 327   elm = xbt_new(s_my_elem_t,1);
 328   elm->name=xbt_strdup(name);
 329   elm->name_len=0;
 330
 331   elm->data=xbt_strdup(data);
 332
 333   xbt_test_log2("Add %s (->%s)",name,data);
 334   xbt_set_add(set, (xbt_set_elm_t)elm, &my_elem_free);
 335 }
 336
 337 static void fill(xbt_set_t *set) {
 338   xbt_test_add0("Fill in the data set");
 339
 340   *set=xbt_set_new();
 341   debuged_add(*set,"12",     "12");
 342   debuged_add(*set,"12a",    "12a");
 343   debuged_add(*set,"12b",    "12b");
 344   debuged_add(*set,"123",    "123");
 345   debuged_add(*set,"123456", "123456");
 346   xbt_test_log0("Child becomes child of what to add");
 347   debuged_add(*set,"1234",   "1234");
 348   xbt_test_log0("Need of common ancestor");
 349   debuged_add(*set,"123457", "123457");
 350 }
 351
 352 static void search_name(xbt_set_t head,const char*key) {
 353   my_elem_t elm;
 354
 355   xbt_test_add1("Search by name %s",key);
 356   elm = (my_elem_t)xbt_set_get_by_name(head,key);
 357   xbt_test_log2(" Found %s (under ID %d)\n",
 358                 elm? elm->data:"(null)",
 359                 elm? elm->ID:-1);
 360   if (strcmp(key,elm->name))
 361     THROW2(mismatch_error,0,"The key (%s) is not the one expected (%s)",
 362            key,elm->name);
 363   if (strcmp(elm->name,elm->data))
 364     THROW2(mismatch_error,0,"The name (%s) != data (%s)",
 365            key,elm->name);
 366   fflush(stdout);
 367 }
 368
 369 static void search_id(xbt_set_t head,int id,const char*key) {
 370   my_elem_t elm;
 371
 372   xbt_test_add1("Search by id %d",id);
 373   elm = (my_elem_t) xbt_set_get_by_id(head,id);
 374   xbt_test_log2("Found %s (data %s)",
 375                 elm? elm->name:"(null)",
 376                 elm? elm->data:"(null)");
 377   if (id != elm->ID)
 378     THROW2(mismatch_error,0,"The found ID (%d) is not the one expected (%d)",
 379            elm->ID,id);
 380   if (strcmp(key,elm->name))
 381     THROW2(mismatch_error,0,"The key (%s) is not the one expected (%s)",
 382            elm->name,key);
 383   if (strcmp(elm->name,elm->data))
 384     THROW2(mismatch_error,0,"The name (%s) != data (%s)",
 385            elm->name,elm->data);
 386 }
 387
 388
 389 static void traverse(xbt_set_t set) {
 390   xbt_set_cursor_t cursor=NULL;
 391   my_elem_t         elm=NULL;
 392
 393   xbt_set_foreach(set,cursor,elm) {
 394     xbt_test_assert0(elm,"Dude ! Got a null elm during traversal!");
 395     xbt_test_log3("Id(%d):  %s->%s\n",elm->ID,elm->name,elm->data);
 396     xbt_test_assert2(!strcmp(elm->name,elm->data),
 397                      "Key(%s) != value(%s). Abording",
 398                      elm->name,elm->data);
 399   }
 400 }
 401
 402 static void search_not_found(xbt_set_t set, const char *data) {
 403   xbt_ex_t e;
 404
 405   xbt_test_add1("Search %s (expected not to be found)",data);
 406   TRY {
 407     xbt_set_get_by_name(set,data);
 408     THROW1(unknown_error,0,"Found something which shouldn't be there (%s)",data);
 409   } CATCH(e) {
 410     if (e.category != not_found_error)
 411       xbt_test_exception(e);
 412     xbt_ex_free(e);
 413   }
 414 }
 415
 416 xbt_set_t set = NULL;
 417
 418
 419 XBT_TEST_UNIT("basic",test_set_basic,"Basic usage") {
 420   set=NULL;
 421
 422   xbt_test_add0("Traverse the empty set");
 423   traverse(set);
 424
 425   xbt_test_add0("Free a data set");
 426   fill(&set);
 427   xbt_set_free(&set);
 428
 429   xbt_test_add0("Free the NULL data set");
 430   xbt_set_free(&set);
 431
 432 }
 433
 434 XBT_TEST_UNIT("change",test_set_change,"Changing some values") {
 435   fill(&set);
 436
 437   xbt_test_add0("Change 123 to 'Changed 123'");
 438   debuged_add(set,"123","Changed 123");
 439
 440   xbt_test_add0("Change 123 back to '123'");
 441   debuged_add(set,"123","123");
 442
 443   xbt_test_add0("Change 12a to 'Dummy 12a'");
 444   debuged_add(set,"12a","Dummy 12a");
 445
 446   xbt_test_add0("Change 12a to '12a'");
 447   debuged_add(set,"12a","12a");
 448
 449   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
 450   xbt_test_add0("Traverse the resulting data set");
 451   traverse(set);
 452 }
 453
 454 XBT_TEST_UNIT("retrieve",test_set_retrieve,"Retrieving some values") {
 455   my_elem_t elm;
 456
 457   xbt_test_add0("Search 123");
 458   elm = (my_elem_t) xbt_set_get_by_name(set,"123");
 459   xbt_test_assert0(elm,"elm must be there");
 460   xbt_assert(!strcmp("123",elm->data));
 461
 462   search_not_found(set,"Can't be found");
 463   search_not_found(set,"123 Can't be found");
 464   search_not_found(set,"12345678 NOT");
 465
 466   search_name(set,"12");
 467   search_name(set,"12a");
 468   search_name(set,"12b");
 469   search_name(set,"123");
 470   search_name(set,"123456");
 471   search_name(set,"1234");
 472   search_name(set,"123457");
 473
 474   search_id(set,0,"12");
 475   search_id(set,1,"12a");
 476   search_id(set,2,"12b");
 477   search_id(set,3,"123");
 478   search_id(set,4,"123456");
 479   search_id(set,5,"1234");
 480   search_id(set,6,"123457");
 481
 482   xbt_test_add0("Traverse the resulting data set");
 483   traverse(set);
 484
 485   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
 486
 487   xbt_test_add0("Free the data set (twice)");
 488   xbt_set_free(&set);
 489   xbt_set_free(&set);
 490
 491   xbt_test_add0("Traverse the resulting data set");
 492   traverse(set);
 493 }
 494
 495 XBT_TEST_UNIT("remove",test_set_remove,"Removing some values") {
 496   my_elem_t elm;
 497
 498   xbt_set_free(&set);
 499   fill(&set);
 500
 501   xbt_set_remove_by_name(set, "12a");
 502   search_not_found(set, "12a");
 503
 504   search_name(set,"12");
 505   search_name(set,"12b");
 506   search_name(set,"123");
 507   search_name(set,"123456");
 508   search_name(set,"1234");
 509   search_name(set,"123457");
 510
 511   search_id(set,0,"12");
 512   search_id(set,2,"12b");
 513   search_id(set,3,"123");
 514   search_id(set,4,"123456");
 515   search_id(set,5,"1234");
 516   search_id(set,6,"123457");
 517
 518   debuged_add(set, "12anew", "12anew");
 519   elm = (my_elem_t) xbt_set_get_by_id(set, 1);
 520   xbt_test_assert1(elm->ID == 1, "elm->ID is %d but should be 1", elm->ID);
 521 }
 522
 523 #endif /* SIMGRID_TEST */