Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Add the possibility to remove an item in the middle of the list.
[simgrid.git] / src / xbt / dynar.c
1 /* $Id$ */
2
3 /* a generic DYNamic ARray                                                  */
4
5 /* Authors: Martin Quinson                                                  */
6 /* Copyright (C) 2003 the OURAGAN project.                                  */
7
8 /* This program is free software; you can redistribute it and/or modify it
9    under the terms of the license (GNU LGPL) which comes with this package. */
10
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 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
19
20 typedef struct xbt_dynar_s {
21   unsigned long          size;
22   unsigned long          used;
23   unsigned long          elmsize;
24   void           *data;
25   void_f_pvoid_t *free_f;
26 } s_xbt_dynar_t;
27
28 #define __sanity_check_dynar(dynar)       \
29            xbt_assert0(dynar,           \
30                         "dynar is NULL")
31 #define __sanity_check_idx(idx)                \
32            xbt_assert1(idx >= 0,             \
33                         "dynar idx(=%d) < 0", \
34                         (int) (idx))
35 #define __check_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_sloppy_inbound_idx(dynar, idx)                                         \
40            xbt_assert2(idx <= dynar->used,                                            \
41                         "dynar is not that long. You asked %d, but it's only %lu long", \
42                         (int) (idx), (unsigned long) dynar->used)
43 #define __check_populated_dynar(dynar)            \
44            xbt_assert1(dynar->used,              \
45                         "dynar %p contains nothing",(void*)dynar)
46
47 static _XBT_INLINE 
48 void _xbt_clear_mem(void * const ptr,
49                      const unsigned long length) {
50   memset(ptr, 0, length);
51 }
52
53 static _XBT_INLINE
54 xbt_error_t
55 _xbt_dynar_expand(xbt_dynar_t const dynar,
56                    const int          nb) {
57   xbt_error_t errcode     = no_error;
58   const unsigned long old_size    = dynar->size;
59
60   if (nb > old_size) {
61     char * const old_data    = dynar->data;
62
63     const unsigned long elmsize     = dynar->elmsize;
64     const unsigned long old_length  = old_size*elmsize;
65
66     const unsigned long used        = dynar->used;
67     const unsigned long used_length = used*elmsize;
68
69     const unsigned long new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
70     const unsigned long new_length  = new_size*elmsize;
71     char * const new_data    = xbt_malloc0(elmsize*new_size);
72
73     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
74
75     if (old_data) {
76       memcpy(new_data, old_data, used_length);
77       _xbt_clear_mem(old_data, old_length);
78       xbt_free(old_data);
79     }
80
81     _xbt_clear_mem(new_data + used_length, new_length - used_length);
82
83     dynar->size = new_size;
84     dynar->data = new_data;
85   }
86
87   return errcode;
88 }
89
90 static _XBT_INLINE
91 void *
92 _xbt_dynar_elm(const xbt_dynar_t  dynar,
93                 const unsigned long idx) {
94   char * const data    = dynar->data;
95   const unsigned long elmsize = dynar->elmsize;
96
97   return data + idx*elmsize;
98 }
99
100 static _XBT_INLINE
101 void
102 _xbt_dynar_get_elm(void  * const       dst,
103                     const xbt_dynar_t  dynar,
104                     const unsigned long idx) {
105   void * const elm     = _xbt_dynar_elm(dynar, idx);
106   const unsigned long elmsize = dynar->elmsize;
107
108   memcpy(dst, elm, elmsize);
109 }
110
111 static _XBT_INLINE
112 void
113 _xbt_dynar_put_elm(const xbt_dynar_t  dynar,
114                     const unsigned long idx,
115                     const void * const  src) {
116   void * const elm     = _xbt_dynar_elm(dynar, idx);
117   const unsigned long elmsize = dynar->elmsize;
118
119   memcpy(elm, src, elmsize);
120 }
121
122 /**
123  * xbt_dynar_new:
124  * @elm_size: size of each element in the dynar
125  * @free_func: function to call each time we want to get rid of an element (or NULL if nothing to do).
126  *
127  * Creates a new dynar. If a free_func is provided, the elements have to be
128  * pointer of pointer. That is to say that dynars can contain either base
129  * types (int, char, double, etc) or pointer of pointers (struct **).
130  */
131 xbt_dynar_t 
132 xbt_dynar_new(const unsigned long           elmsize,
133                void_f_pvoid_t * const free_f) {
134    
135   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
136
137   dynar->size    = 0;
138   dynar->used    = 0;
139   dynar->elmsize = elmsize;
140   dynar->data    = NULL;
141   dynar->free_f    = free_f;
142
143   return dynar;
144 }
145
146 /**
147  * xbt_dynar_free_container:
148  * @dynar: poor victim
149  *
150  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
151  * its contain points to.
152  */
153 void
154 xbt_dynar_free_container(xbt_dynar_t *dynar) {
155   if (dynar && *dynar) {
156
157     if ((*dynar)->data) {
158       _xbt_clear_mem((*dynar)->data, (*dynar)->size);
159       xbt_free((*dynar)->data);
160     }
161
162     _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
163
164     xbt_free(*dynar);
165     *dynar=NULL;
166   }
167 }
168
169 /**
170  * xbt_dynar_reset:
171  * @dynar: who to squeeze
172  *
173  * Frees the content and set the size to 0
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     xbt_free(dynar->data);
187
188   dynar->size = 0;
189   dynar->used = 0;
190   dynar->data = NULL;
191 }
192
193 /**
194  * xbt_dynar_free:
195  * @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 /**
209  * xbt_dynar_length:
210  * @dynar: the dynar we want to mesure
211  *
212  * Returns the count of elements in a dynar
213  */
214 unsigned long
215 xbt_dynar_length(const xbt_dynar_t dynar) {
216   return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
217 }
218
219 /**
220  * xbt_dynar_get_cpy:
221  * @dynar: information dealer
222  * @idx: index of the slot we want to retrive
223  * @dst: where to pu the result to.
224  *
225  * Retrieve a copy of the Nth element of a dynar.
226  */
227 void
228 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
229                    const int          idx,
230                    void       * const dst) {
231
232   __sanity_check_dynar(dynar);
233   __sanity_check_idx(idx);
234   __check_inbound_idx(dynar, idx);
235
236   _xbt_dynar_get_elm(dst, dynar, idx);
237 }
238
239 /**
240  * xbt_dynar_get_ptr:
241  * @dynar: information dealer
242  * @idx: index of the slot we want to retrive
243  * @dst: where to pu the result to.
244  *
245  * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of 
246  * the dynar. Make a copy before fooling with it.
247  */
248 void*
249 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
250                    const int          idx) {
251
252   __sanity_check_dynar(dynar);
253   __sanity_check_idx(idx);
254   __check_inbound_idx(dynar, idx);
255
256   return _xbt_dynar_elm(dynar, idx);
257 }
258
259 /**
260  * xbt_dynar_set:
261  * @dynar:
262  * @idx:
263  * @src: What will be feeded to the dynar
264  *
265  * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
266  * the previous value at this position. If you want to free the previous content,
267  * use xbt_dynar_replace().
268  */
269 void
270 xbt_dynar_set(xbt_dynar_t         dynar,
271                const int            idx,
272                const void   * const src) {
273
274   __sanity_check_dynar(dynar);
275   __sanity_check_idx(idx);
276
277   _xbt_dynar_expand(dynar, idx+1);
278
279   if (idx >= dynar->used) {
280     dynar->used = idx+1;
281   }
282
283   _xbt_dynar_put_elm(dynar, idx, src);
284 }
285
286 /**
287  * xbt_dynar_replace:
288  * @dynar:
289  * @idx:
290  * @object:
291  *
292  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
293  * free the previous value at this position. If you don't want to free the
294  * previous content, use xbt_dynar_set().
295  */
296 void
297 xbt_dynar_replace(xbt_dynar_t         dynar,
298                    const int            idx,
299                    const void   * const object) {
300
301   __sanity_check_dynar(dynar);
302   __sanity_check_idx(idx);
303
304   if (idx < dynar->used && dynar->free_f) {
305     void * const old_object = _xbt_dynar_elm(dynar, idx);
306
307     dynar->free_f(old_object);
308   }
309
310   xbt_dynar_set(dynar, idx, object);
311 }
312
313 /**
314  * xbt_dynar_insert_at_ptr:
315  * 
316  * Make room for a new element in the dynar, and return a pointer to
317  * its position. You can then use regular affectation to set its value
318  * instead of relying on the slow memcpy
319  */
320 void *
321 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
322                          const int            idx) {
323    
324   __sanity_check_dynar(dynar);
325   __sanity_check_idx(idx);
326   __check_sloppy_inbound_idx(dynar, idx);
327
328   {
329     const unsigned long old_used = dynar->used;
330     const unsigned long new_used = old_used + 1;
331
332     _xbt_dynar_expand(dynar, new_used);
333
334     {
335       const unsigned long nb_shift =  old_used - idx;
336
337       if (nb_shift)
338          memmove(_xbt_dynar_elm(dynar, idx+1), 
339                  _xbt_dynar_elm(dynar, idx), 
340                  nb_shift * dynar->elmsize);
341     }
342
343     dynar->used = new_used;
344     return _xbt_dynar_elm(dynar,idx);
345   }
346 }
347
348 /**
349  * xbt_dynar_insert_at:
350  * @dynar:
351  * @idx:
352  * @src: What will be feeded to the dynar
353  *
354  * Set the Nth element of a dynar, expanding the dynar if needed, and
355  * moving the previously existing value and all subsequent ones to one
356  * position right in the dynar.
357  */
358 void
359 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
360                      const int            idx,
361                      const void   * const src) {
362
363   /* checks done in xbt_dynar_insert_at_ptr */
364   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
365          src,
366          dynar->elmsize);
367 }
368
369 /**
370  * xbt_dynar_remove_at:
371  * @dynar: 
372  * @idx:
373  * @object:
374  *
375  * Get the Nth element of a dynar, removing it from the dynar and moving
376  * all subsequent values to one position left in the dynar.
377  */
378 void
379 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
380                      const int            idx,
381                      void         * const object) {
382
383   __sanity_check_dynar(dynar);
384   __sanity_check_idx(idx);
385   __check_inbound_idx(dynar, idx);
386
387   if (object)
388     _xbt_dynar_get_elm(object, dynar, idx);
389
390   {
391     const unsigned long old_used = dynar->used;
392     const unsigned long new_used = old_used - 1;
393
394     const unsigned long nb_shift =  old_used-1 - idx;
395     const unsigned long elmsize  =  dynar->elmsize;
396
397     const unsigned long offset   =  nb_shift*elmsize;
398
399     void * const elm_src  = _xbt_dynar_elm(dynar, idx+1);
400     void * const elm_dst  = _xbt_dynar_elm(dynar, idx);
401
402     memmove(elm_dst, elm_src, offset);
403
404     dynar->used = new_used;
405   }
406 }
407
408 /**
409  * xbt_dynar_push_ptr:
410  * 
411  * Make room at the end of the dynar for a new element, and return a pointer to it
412  */
413 void *
414 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
415   return xbt_dynar_insert_at_ptr(dynar, dynar->used);    
416 }
417
418 /**
419  * xbt_dynar_push:
420  * @dynar:
421  * @src:
422  *
423  * Add an element at the end of the dynar
424  */
425 void
426 xbt_dynar_push(xbt_dynar_t  const dynar,
427                 const void   * const src) {
428   /* sanity checks done by insert_at */
429   xbt_dynar_insert_at(dynar, dynar->used, src); 
430 }
431
432 /**
433  * xbt_dynar_pop_ptr:
434  * @dynar:
435  * @dst:
436  *
437  * Make the last element of the dynar as unused and return a pointer to it.
438  */
439 void *
440 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
441
442   __check_populated_dynar(dynar);
443   DEBUG1("Pop %p",(void*)dynar);
444   dynar->used--;
445   return _xbt_dynar_elm(dynar,dynar->used);
446 }
447
448 /**
449  * xbt_dynar_pop:
450  * @dynar:
451  * @dst:
452  *
453  * Get and remove the last element of the dynar
454  */
455 void
456 xbt_dynar_pop(xbt_dynar_t  const dynar,
457                void         * const dst) {
458
459   /* sanity checks done by remove_at */
460   DEBUG1("Pop %p",(void*)dynar);
461   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
462 }
463
464 /**
465  * xbt_dynar_unshift:
466  * @dynar:
467  * @src:
468  *
469  * Add an element at the begining of the dynar (rather long, Use
470  * xbt_dynar_push() when possible)
471  */
472 void
473 xbt_dynar_unshift(xbt_dynar_t  const dynar,
474                    const void   * const src) {
475   
476   /* sanity checks done by insert_at */
477   xbt_dynar_insert_at(dynar, 0, src);
478 }
479
480 /**
481  * xbt_dynar_shift:
482  * @dynar:
483  * @dst:
484  *
485  * Get and remove the first element of the dynar (rather long, Use
486  * xbt_dynar_pop() when possible)
487  */
488 void
489 xbt_dynar_shift(xbt_dynar_t  const dynar,
490                  void         * const dst) {
491
492   /* sanity checks done by remove_at */
493   xbt_dynar_remove_at(dynar, 0, dst);
494 }
495
496 /**
497  * xbt_dynar_map:
498  * @dynar:
499  * @operator:
500  *
501  * Apply a function to each member of a dynar (this function may change the
502  * value of the element itself, but should not mess with the dynar).
503  */
504 void
505 xbt_dynar_map(const xbt_dynar_t  dynar,
506                void_f_pvoid_t     * const operator) {
507
508   __sanity_check_dynar(dynar);
509
510   {
511     char         elm[64];
512     const unsigned long used = dynar->used;
513     unsigned long       i    = 0;
514
515     for (i = 0; i < used; i++) {
516       _xbt_dynar_get_elm(elm, dynar, i);
517       operator(elm);
518     }
519   }
520 }
521
522 /**
523  * xbt_dynar_cursor_first:
524  *
525  * Put the cursor at the begining of the dynar. (actually, one step before
526  * the begining, so that you can iterate over the dynar with a for loop).
527  *
528  * Dynar cursor are as dumb as possible. If you insert or remove elements
529  * from the dynar between the creation and end, you'll fuck up your
530  * cursors.
531  *
532  */
533 void
534 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
535                         int        * const cursor) {
536
537   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
538   *cursor = 0;
539 }
540
541 /**
542  * xbt_dynar_cursor_step:
543  *
544  * Move the cursor to the next value (and return true), or return false.
545  */
546 void
547 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
548                        int        * const cursor) {
549   
550   (*cursor)++;
551 }
552
553 /**
554  * xbt_dynar_cursor_get:
555  *
556  * Get the current value of the cursor
557  */
558 int
559 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
560                       int                * const cursor,
561                       void               * const dst) {
562
563   __sanity_check_dynar(dynar);
564   {
565
566     const int idx = *cursor;
567
568     if (idx >= dynar->used) {
569       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
570       return FALSE;
571     }
572     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
573
574     _xbt_dynar_get_elm(dst, dynar, idx);
575   }
576   return TRUE;
577
578 }
579
580 /**
581  * xbt_dynar_cursor_rm:
582  * @dynar:
583  * @cursor:
584  *
585  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
586  */
587 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
588                           int          * const cursor) {
589   void *dst;
590
591   if (dynar->elmsize > sizeof(void*)) {
592     DEBUG0("Elements too big to fit into a pointer");
593     if (dynar->free_f) {
594       dst=xbt_malloc(dynar->elmsize);
595       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
596       (dynar->free_f)(dst);
597       xbt_free(dst);
598     } else {
599       DEBUG0("Ok, we dont care about the element without free function");
600       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
601     }
602       
603   } else {
604     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
605     if (dynar->free_f)
606       (dynar->free_f)(dst);
607   }
608 }