Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
reduce the amount of logging; don't exit the process until after its last use (in...
[simgrid.git] / src / xbt / dynar.c
1 /* $Id$ */
2
3 /* a generic DYNamic ARray implementation.                                  */
4
5 /* Copyright (c) 2003, 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 "portable.h" /* SIZEOF_MAX */
11 #include "xbt/misc.h"
12 #include "xbt/sysdep.h"
13 #include "xbt/log.h"
14 #include "xbt/error.h"
15 #include "xbt/dynar.h"
16 #include <sys/types.h>
17
18 #include "xbt/dynar_private.h" /* type definition, which we share with the 
19                                   code in charge of sending this across the net */
20
21 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
22
23
24 #define __sanity_check_dynar(dynar)       \
25            xbt_assert0(dynar,           \
26                         "dynar is NULL")
27 #define __sanity_check_idx(idx)                \
28            xbt_assert1(idx >= 0,             \
29                         "dynar idx(=%d) < 0", \
30                         (int) (idx))
31 #define __check_inbound_idx(dynar, idx)                                                \
32            xbt_assert2(idx < dynar->used,                                             \
33                         "dynar is not that long. You asked %d, but it's only %lu long", \
34                         (int) (idx), (unsigned long) dynar->used)
35 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
36            xbt_assert2(idx <= dynar->used,                                            \
37                         "dynar is not that long. You asked %d, but it's only %lu long", \
38                         (int) (idx), (unsigned long) dynar->used)
39 #define __check_populated_dynar(dynar)            \
40            xbt_assert1(dynar->used,              \
41                         "dynar %p contains nothing",(void*)dynar)
42
43 static _XBT_INLINE 
44 void _xbt_clear_mem(void * const ptr,
45                      const unsigned long length) {
46   memset(ptr, 0, length);
47 }
48
49 static _XBT_INLINE
50 xbt_error_t
51 _xbt_dynar_expand(xbt_dynar_t const dynar,
52                    const int          nb) {
53   xbt_error_t errcode     = no_error;
54   const unsigned long old_size    = dynar->size;
55
56   if (nb > old_size) {
57     char * const old_data    = dynar->data;
58
59     const unsigned long elmsize     = dynar->elmsize;
60     const unsigned long old_length  = old_size*elmsize;
61
62     const unsigned long used        = dynar->used;
63     const unsigned long used_length = used*elmsize;
64
65     const unsigned long new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
66     const unsigned long new_length  = new_size*elmsize;
67     char * const new_data    = xbt_malloc0(elmsize*new_size);
68
69     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
70
71     if (old_data) {
72       memcpy(new_data, old_data, used_length);
73       _xbt_clear_mem(old_data, old_length);
74       free(old_data);
75     }
76
77     _xbt_clear_mem(new_data + used_length, new_length - used_length);
78
79     dynar->size = new_size;
80     dynar->data = new_data;
81   }
82
83   return errcode;
84 }
85
86 static _XBT_INLINE
87 void *
88 _xbt_dynar_elm(const xbt_dynar_t  dynar,
89                 const unsigned long idx) {
90   char * const data    = dynar->data;
91   const unsigned long elmsize = dynar->elmsize;
92
93   return data + idx*elmsize;
94 }
95
96 static _XBT_INLINE
97 void
98 _xbt_dynar_get_elm(void  * const       dst,
99                     const xbt_dynar_t  dynar,
100                     const unsigned long idx) {
101   void * const elm     = _xbt_dynar_elm(dynar, idx);
102   const unsigned long elmsize = dynar->elmsize;
103
104   memcpy(dst, elm, elmsize);
105 }
106
107 static _XBT_INLINE
108 void
109 _xbt_dynar_put_elm(const xbt_dynar_t  dynar,
110                     const unsigned long idx,
111                     const void * const  src) {
112   void * const elm     = _xbt_dynar_elm(dynar, idx);
113   const unsigned long elmsize = dynar->elmsize;
114
115   memcpy(elm, src, elmsize);
116 }
117
118 void
119 xbt_dynar_dump(xbt_dynar_t dynar) {
120   INFO5("Dynar dump: size=%lu; used=%lu; elmsize=%lu; data=%p; free_f=%p",
121         dynar->size, dynar->used, dynar->elmsize, dynar->data, dynar->free_f);
122 }       
123
124 /** @brief Constructor
125  * 
126  * \param elmsize size of each element in the dynar
127  * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
128  *
129  * Creates a new dynar. If a free_func is provided, the elements have to be
130  * pointer of pointer. That is to say that dynars can contain either base
131  * types (int, char, double, etc) or pointer of pointers (struct **).
132  */
133 xbt_dynar_t 
134 xbt_dynar_new(const unsigned long           elmsize,
135                void_f_pvoid_t * const free_f) {
136    
137   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
138
139   dynar->size    = 0;
140   dynar->used    = 0;
141   dynar->elmsize = elmsize;
142   dynar->data    = NULL;
143   dynar->free_f    = free_f;
144
145   return dynar;
146 }
147
148 /** @brief Destructor of the structure not touching to the content
149  * 
150  * \param dynar poor victim
151  *
152  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
153  * is not touched (the \a free_f function is not used)
154  */
155 void
156 xbt_dynar_free_container(xbt_dynar_t *dynar) {
157   if (dynar && *dynar) {
158
159     if ((*dynar)->data) {
160       _xbt_clear_mem((*dynar)->data, (*dynar)->size);
161       free((*dynar)->data);
162     }
163
164     _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
165
166     free(*dynar);
167     *dynar=NULL;
168   }
169 }
170
171 /** @brief Frees the content and set the size to 0
172  *
173  * \param dynar who to squeeze
174  */
175 void
176 xbt_dynar_reset(xbt_dynar_t const dynar) {
177
178   __sanity_check_dynar(dynar);
179
180   DEBUG1("Reset the dynar %p",(void*)dynar);
181   if (dynar->free_f) {
182     xbt_dynar_map(dynar, dynar->free_f);
183   }
184
185   if (dynar->data)
186     free(dynar->data);
187
188   dynar->size = 0;
189   dynar->used = 0;
190   dynar->data = NULL;
191 }
192
193 /** @brief Destructor
194  * 
195  * \param dynar poor victim
196  *
197  * kilkil a dynar and its content
198  */
199
200 void
201 xbt_dynar_free(xbt_dynar_t * dynar) {
202   if (dynar && *dynar) {
203     xbt_dynar_reset(*dynar);
204     xbt_dynar_free_container(dynar);
205   }
206 }
207
208 /** @brief Count of dynar's elements
209  * 
210  * \param dynar the dynar we want to mesure
211  */
212 unsigned long
213 xbt_dynar_length(const xbt_dynar_t dynar) {
214   return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
215 }
216
217 /** @brief Retrieve a copy of the Nth element of a dynar.
218  *
219  * \param dynar information dealer
220  * \param idx index of the slot we want to retrive
221  * \param[out] dst where to put the result to.
222  */
223 void
224 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
225                    const int          idx,
226                    void       * const dst) {
227
228   __sanity_check_dynar(dynar);
229   __sanity_check_idx(idx);
230   __check_inbound_idx(dynar, idx);
231
232   _xbt_dynar_get_elm(dst, dynar, idx);
233 }
234
235 /** @brief Retrieve a pointer to the Nth element of a dynar.
236  *
237  * \param dynar information dealer
238  * \param idx index of the slot we want to retrieve
239  * \return the \a idx-th element of \a dynar.
240  *
241  * \warning The returned value is the actual content of the dynar. 
242  * Make a copy before fooling with it.
243  */
244 void*
245 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
246                    const int          idx) {
247
248   __sanity_check_dynar(dynar);
249   __sanity_check_idx(idx);
250   __check_inbound_idx(dynar, idx);
251
252   return _xbt_dynar_elm(dynar, idx);
253 }
254
255 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
256  * 
257  * \param dynar information dealer
258  * \param idx index of the slot we want to modify
259  * \param src What will be feeded to the dynar
260  *
261  * If you want to free the previous content, use xbt_dynar_replace().
262  */
263 void
264 xbt_dynar_set(xbt_dynar_t         dynar,
265                const int            idx,
266                const void   * const src) {
267
268   __sanity_check_dynar(dynar);
269   __sanity_check_idx(idx);
270
271   _xbt_dynar_expand(dynar, idx+1);
272
273   if (idx >= dynar->used) {
274     dynar->used = idx+1;
275   }
276
277   _xbt_dynar_put_elm(dynar, idx, src);
278 }
279
280 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
281  *
282  * \param dynar
283  * \param idx
284  * \param object
285  *
286  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
287  * free the previous value at this position. If you don't want to free the
288  * previous content, use xbt_dynar_set().
289  */
290 void
291 xbt_dynar_replace(xbt_dynar_t         dynar,
292                    const int            idx,
293                    const void   * const object) {
294
295   __sanity_check_dynar(dynar);
296   __sanity_check_idx(idx);
297
298   if (idx < dynar->used && dynar->free_f) {
299     void * const old_object = _xbt_dynar_elm(dynar, idx);
300
301     dynar->free_f(old_object);
302   }
303
304   xbt_dynar_set(dynar, idx, object);
305 }
306
307 /** @brief Make room for a new element, and return a pointer to it
308  * 
309  * You can then use regular affectation to set its value instead of relying 
310  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
311  */
312 void *
313 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
314                         const int            idx) {
315    
316   __sanity_check_dynar(dynar);
317   __sanity_check_idx(idx);
318   __check_sloppy_inbound_idx(dynar, idx);
319
320   {
321     const unsigned long old_used = dynar->used;
322     const unsigned long new_used = old_used + 1;
323
324     _xbt_dynar_expand(dynar, new_used);
325
326     {
327       const unsigned long nb_shift =  old_used - idx;
328
329       if (nb_shift)
330          memmove(_xbt_dynar_elm(dynar, idx+1), 
331                  _xbt_dynar_elm(dynar, idx), 
332                  nb_shift * dynar->elmsize);
333     }
334
335     dynar->used = new_used;
336     return _xbt_dynar_elm(dynar,idx);
337   }
338 }
339
340 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
341  * 
342  * Set the Nth element of a dynar, expanding the dynar if needed, and
343  * moving the previously existing value and all subsequent ones to one
344  * position right in the dynar.
345  */
346 void
347 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
348                     const int            idx,
349                     const void   * const src) {
350
351   /* checks done in xbt_dynar_insert_at_ptr */
352   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
353          src,
354          dynar->elmsize);
355 }
356
357 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
358  *
359  * Get the Nth element of a dynar, removing it from the dynar and moving
360  * all subsequent values to one position left in the dynar.
361  */
362 void
363 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
364                      const int            idx,
365                      void         * const object) {
366
367   __sanity_check_dynar(dynar);
368   __sanity_check_idx(idx);
369   __check_inbound_idx(dynar, idx);
370
371   if (object)
372     _xbt_dynar_get_elm(object, dynar, idx);
373
374   {
375     const unsigned long old_used = dynar->used;
376     const unsigned long new_used = old_used - 1;
377
378     const unsigned long nb_shift =  old_used-1 - idx;
379     const unsigned long elmsize  =  dynar->elmsize;
380
381     const unsigned long offset   =  nb_shift*elmsize;
382
383     void * const elm_src  = _xbt_dynar_elm(dynar, idx+1);
384     void * const elm_dst  = _xbt_dynar_elm(dynar, idx);
385
386     memmove(elm_dst, elm_src, offset);
387
388     dynar->used = new_used;
389   }
390 }
391
392 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
393  *
394  * You can then use regular affectation to set its value instead of relying 
395  * on the slow memcpy. This is what xbt_dynar_push_as() does.
396  */
397 void *
398 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
399   return xbt_dynar_insert_at_ptr(dynar, dynar->used);    
400 }
401
402 /** @brief Add an element at the end of the dynar */
403 void
404 xbt_dynar_push(xbt_dynar_t  const dynar,
405                 const void   * const src) {
406   /* sanity checks done by insert_at */
407   xbt_dynar_insert_at(dynar, dynar->used, src); 
408 }
409
410 /** @brief Mark the last dynar's element as unused and return a pointer to it.
411  *
412  * You can then use regular affectation to set its value instead of relying 
413  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
414  */
415 void *
416 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
417
418   __check_populated_dynar(dynar);
419   DEBUG1("Pop %p",(void*)dynar);
420   dynar->used--;
421   return _xbt_dynar_elm(dynar,dynar->used);
422 }
423
424 /** @brief Get and remove the last element of the dynar */
425 void
426 xbt_dynar_pop(xbt_dynar_t  const dynar,
427                void         * const dst) {
428
429   /* sanity checks done by remove_at */
430   DEBUG1("Pop %p",(void*)dynar);
431   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
432 }
433
434 /** @brief Add an element at the begining of the dynar.
435  *
436  * This is less efficient than xbt_dynar_push()
437  */
438 void
439 xbt_dynar_unshift(xbt_dynar_t  const dynar,
440                    const void   * const src) {
441   
442   /* sanity checks done by insert_at */
443   xbt_dynar_insert_at(dynar, 0, src);
444 }
445
446 /** @brief Get and remove the first element of the dynar.
447  *
448  * This is less efficient than xbt_dynar_pop()
449  */
450 void
451 xbt_dynar_shift(xbt_dynar_t  const dynar,
452                  void         * const dst) {
453
454   /* sanity checks done by remove_at */
455   xbt_dynar_remove_at(dynar, 0, dst);
456 }
457
458 /** @brief Apply a function to each member of a dynar
459  *
460  * The mapped function may change the value of the element itself, 
461  * but should not mess with the structure of the dynar.
462  */
463 void
464 xbt_dynar_map(const xbt_dynar_t  dynar,
465                void_f_pvoid_t     * const operator) {
466
467   __sanity_check_dynar(dynar);
468
469   {
470     char         elm[SIZEOF_MAX];
471     const unsigned long used = dynar->used;
472     unsigned long       i    = 0;
473
474     for (i = 0; i < used; i++) {
475       _xbt_dynar_get_elm(elm, dynar, i);
476       operator(elm);
477     }
478   }
479 }
480
481 /** @brief Put the cursor at the begining of the dynar.
482  *
483  * Actually, the cursor is set one step before the begining, so that you
484  * can iterate over the dynar with a for loop.
485  */
486 void
487 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
488                        int        * const cursor) {
489
490   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
491   *cursor = 0;
492 }
493
494 /** @brief Move the cursor to the next value */
495 void
496 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
497                        int        * const cursor) {
498   
499   (*cursor)++;
500 }
501
502 /** @brief Get the data currently pointed by the cursor */
503 int
504 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
505                       int                * const cursor,
506                       void               * const dst) {
507
508   __sanity_check_dynar(dynar);
509   {
510
511     const int idx = *cursor;
512
513     if (idx >= dynar->used) {
514       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
515       return FALSE;
516     }
517     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
518
519     _xbt_dynar_get_elm(dst, dynar, idx);
520   }
521   return TRUE;
522
523 }
524
525 /** @brief Removes and free the entry pointed by the cursor 
526  *
527  * This function can be used while traversing without problem.
528  */
529 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
530                           int          * const cursor) {
531   void *dst;
532
533   if (dynar->elmsize > sizeof(void*)) {
534     DEBUG0("Elements too big to fit into a pointer");
535     if (dynar->free_f) {
536       dst=xbt_malloc(dynar->elmsize);
537       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
538       (dynar->free_f)(dst);
539       free(dst);
540     } else {
541       DEBUG0("Ok, we dont care about the element without free function");
542       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
543     }
544       
545   } else {
546     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
547     if (dynar->free_f)
548       (dynar->free_f)(dst);
549   }
550 }