Logo AND Algorithmique Numérique Distribuée

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