src/xbt/set.c

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