Logo AND Algorithmique Numérique Distribuée

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