Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
in gras_dynar_cursor_rm, we want to get the content to free it if there is a
[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 "gras_private.h"
12
13 GRAS_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,tbx);
14
15 struct gras_dynar_s {
16   size_t          size;
17   size_t          used;
18   size_t          elmsize;
19   void           *data;
20   void_f_pvoid_t *free;
21 };
22
23 #define __sanity_check_dynar(dynar)       \
24            gras_assert0(dynar,           \
25                         "dynar is NULL")
26 #define __sanity_check_idx(idx)                \
27            gras_assert1(idx >= 0,             \
28                         "dynar idx(=%d) < 0", \
29                         idx)
30 #define __check_inbound_idx(dynar, idx)                                                \
31            gras_assert2(idx < dynar->used,                                             \
32                         "dynar is not that long. You asked %d, but it's only %d long", \
33                         idx, dynar->used)
34 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
35            gras_assert2(idx <= dynar->used,                                            \
36                         "dynar is not that long. You asked %d, but it's only %d long", \
37                         idx, dynar->used)
38 #define __check_populated_dynar(dynar)            \
39            gras_assert0(dynar->used,              \
40                         "dynar contains nothing")
41
42
43 static inline
44 void
45 _gras_clear_mem(void * const ptr,
46                 const size_t length) {
47   memset(ptr, 0, length);
48 }
49
50 static inline
51 gras_error_t
52 _gras_dynar_expand(gras_dynar_t * const dynar,
53                    const int            nb) {
54   gras_error_t errcode     = no_error;
55   const size_t old_size    = dynar->size;
56
57   if (nb > old_size) {
58     char * const old_data    = dynar->data;
59
60     const size_t elmsize     = dynar->elmsize;
61     const size_t old_length  = old_size*elmsize;
62
63     const size_t used        = dynar->used;
64     const size_t used_length = used*elmsize;
65
66     const size_t new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
67     const size_t new_length  = new_size*elmsize;
68     char * const new_data    = calloc(1, elmsize*new_size);
69
70     DEBUG3("expend %p from %d to %d elements", dynar, old_size, nb);
71     if (!new_data)
72       RAISE_MALLOC;
73
74     if (old_data) {
75       memcpy(new_data, old_data, used_length);
76       _gras_clear_mem(old_data, old_length);
77       free(old_data);
78     }
79
80     _gras_clear_mem(new_data + used_length, new_length - used_length);
81
82     dynar->size = new_size;
83     dynar->data = new_data;
84   }
85
86   return errcode;
87 }
88
89 static inline
90 void *
91 _gras_dynar_elm(const gras_dynar_t * const dynar,
92                 const size_t               idx) {
93   char * const data    = dynar->data;
94   const size_t elmsize = dynar->elmsize;
95
96   return data + idx*elmsize;
97 }
98
99 static inline
100 void
101 _gras_dynar_get_elm(void               * const dst,
102                     const gras_dynar_t * const dynar,
103                     const size_t               idx) {
104   void * const elm     = _gras_dynar_elm(dynar, idx);
105   const size_t elmsize = dynar->elmsize;
106
107   memcpy(dst, elm, elmsize);
108 }
109
110 static inline
111 void
112 _gras_dynar_put_elm(const gras_dynar_t * const dynar,
113                     const size_t               idx,
114                     const void         * const src) {
115   void * const elm     = _gras_dynar_elm(dynar, idx);
116   const size_t elmsize = dynar->elmsize;
117
118   memcpy(elm, src, elmsize);
119 }
120
121 /**
122  * gras_dynar_new:
123  * @whereto: pointer to where the dynar should be created
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  * @Returns: malloc_error or no_error
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 gras_error_t
133 gras_dynar_new(gras_dynar_t   ** const p_dynar,
134                const size_t            elmsize,
135                void_f_pvoid_t  * const free_func) {
136   gras_error_t  errcode = no_error;
137   gras_dynar_t *dynar   = NULL;
138
139   if (!(dynar = calloc(1, sizeof(gras_dynar_t))))
140     RAISE_MALLOC;
141
142   dynar->size    = 0;
143   dynar->used    = 0;
144   dynar->elmsize = elmsize;
145   dynar->data    = NULL;
146   dynar->free    = free_func;
147
148   *p_dynar = dynar;
149
150   return errcode;
151 }
152
153 /**
154  * gras_dynar_free_container:
155  * @dynar: poor victim
156  *
157  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
158  * its contain points to.
159  */
160 void
161 gras_dynar_free_container(gras_dynar_t * const dynar) {
162   if (dynar) {
163
164     if (dynar->data) {
165       _gras_clear_mem(dynar->data, dynar->size);
166       free(dynar->data);
167     }
168
169     _gras_clear_mem(dynar, sizeof(gras_dynar_t));
170
171     free(dynar);
172   }
173 }
174
175 /**
176  * gras_dynar_reset:
177  * @dynar: who to squeeze
178  *
179  * Frees the content and set the size to 0
180  */
181 void
182 gras_dynar_reset(gras_dynar_t * const dynar) {
183
184   __sanity_check_dynar(dynar);
185
186   if (dynar->free) {
187     gras_dynar_map(dynar, dynar->free);
188   }
189
190   if (dynar->data) {
191     _gras_clear_mem(dynar->data, dynar->size);
192     free(dynar->data);
193   }
194
195   dynar->size = 0;
196   dynar->used = 0;
197   dynar->data = NULL;
198 }
199
200 /**
201  * gras_dynar_free:
202  * @dynar: poor victim
203  *
204  * kilkil a dynar and its content
205  */
206
207 void
208 gras_dynar_free(gras_dynar_t * const dynar) {
209   if (dynar) {
210     gras_dynar_reset(dynar);
211     gras_dynar_free_container(dynar);
212   }
213 }
214
215 /**
216  * gras_dynar_length:
217  * @dynar: the dynar we want to mesure
218  *
219  * Returns the count of elements in a dynar
220  */
221 size_t
222 gras_dynar_length(const gras_dynar_t * const dynar) {
223   return (dynar ? dynar->used : (size_t)0);
224 }
225
226 /**
227  * gras_dynar_get:
228  * @dynar: information dealer
229  * @idx: index of the slot we want to retrive
230  * @dst: where to pu the result to.
231  *
232  * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of 
233  * the dynar. Make a copy before fooling with it.
234  */
235 void
236 gras_dynar_get(const gras_dynar_t * const dynar,
237                const int                  idx,
238                void               * const dst) {
239
240   __sanity_check_dynar(dynar);
241   __sanity_check_idx(idx);
242   __check_inbound_idx(dynar, idx);
243
244   _gras_dynar_get_elm(dst, dynar, idx);
245 }
246
247 /**
248  * gras_dynar_set:
249  * @dynar:
250  * @idx:
251  * @src: What will be feeded to the dynar
252  * @Returns: malloc_error or no_error
253  *
254  * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
255  * the previous value at this position. If you want to free the previous content,
256  * use gras_dynar_remplace().
257  */
258 gras_error_t
259 gras_dynar_set(gras_dynar_t * const dynar,
260                const int            idx,
261                const void   * const src) {
262   gras_error_t errcode = no_error;
263
264   __sanity_check_dynar(dynar);
265   __sanity_check_idx(idx);
266
267   TRY(_gras_dynar_expand(dynar, idx+1));
268
269   if (idx >= dynar->used) {
270     dynar->used = idx+1;
271   }
272
273   _gras_dynar_put_elm(dynar, idx, src);
274
275   return errcode;
276 }
277
278 /**
279  * gras_dynar_remplace:
280  * @dynar:
281  * @idx:
282  * @object:
283  * @Returns: malloc_error or no_error
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 gras_dynar_set().
288  */
289 gras_error_t
290 gras_dynar_remplace(gras_dynar_t * const dynar,
291                     const int            idx,
292                     const void   * const object) {
293   gras_error_t errcode = no_error;
294
295   __sanity_check_dynar(dynar);
296   __sanity_check_idx(idx);
297
298   if (idx < dynar->used && dynar->free) {
299     void * const old_object = _gras_dynar_elm(dynar, idx);
300
301     dynar->free(old_object);
302   }
303
304   errcode = gras_dynar_set(dynar, idx, object);
305
306   return errcode;
307 }
308
309 /**
310  * gras_dynar_insert_at:
311  * @dynar:
312  * @idx:
313  * @src: What will be feeded to the dynar
314  * @Returns: malloc_error or no_error
315  *
316  * Set the Nth element of a dynar, expanding the dynar if needed, and
317  * moving the previously existing value and all subsequent ones to one
318  * position right in the dynar.
319  */
320 gras_error_t
321 gras_dynar_insert_at(gras_dynar_t * const dynar,
322                      const int            idx,
323                      const void   * const src) {
324   gras_error_t errcode = no_error;
325
326   __sanity_check_dynar(dynar);
327   __sanity_check_idx(idx);
328   __check_sloppy_inbound_idx(dynar, idx);
329
330   {
331     const size_t old_used = dynar->used;
332     const size_t new_used = old_used + 1;
333
334     TRY(_gras_dynar_expand(dynar, new_used));
335
336     {
337       const size_t nb_shift =  old_used - idx;
338       const size_t elmsize  =  dynar->elmsize;
339
340       const size_t offset   =  nb_shift*elmsize;
341
342       void * const elm_src  = _gras_dynar_elm(dynar, idx);
343       void * const elm_dst  = _gras_dynar_elm(dynar, idx+1);
344
345       memmove(elm_dst, elm_src, offset);
346     }
347
348     _gras_dynar_put_elm(dynar, idx, src);
349     dynar->used = new_used;
350   }
351
352   return errcode;
353 }
354
355 /**
356  * gras_dynar_remove_at:
357  * @dynar: 
358  * @idx:
359  * @object:
360  *
361  * Get the Nth element of a dynar, removing it from the dynar and moving
362  * all subsequent values to one position left in the dynar.
363  */
364 void
365 gras_dynar_remove_at(gras_dynar_t * const dynar,
366                      const int            idx,
367                      void         * const object) {
368
369   __sanity_check_dynar(dynar);
370   __sanity_check_idx(idx);
371   __check_inbound_idx(dynar, idx);
372
373   if (object)
374     _gras_dynar_get_elm(object, dynar, idx);
375
376   {
377     const size_t old_used = dynar->used;
378     const size_t new_used = old_used - 1;
379
380     const size_t nb_shift =  old_used-1 - idx;
381     const size_t elmsize  =  dynar->elmsize;
382
383     const size_t offset   =  nb_shift*elmsize;
384
385     void * const elm_src  = _gras_dynar_elm(dynar, idx+1);
386     void * const elm_dst  = _gras_dynar_elm(dynar, idx);
387
388     memmove(elm_dst, elm_src, offset);
389
390     dynar->used = new_used;
391   }
392 }
393
394 /**
395  * gras_dynar_push:
396  * @dynar:
397  * @src:
398  * @Returns: malloc_error or no_error
399  *
400  * Add an element at the end of the dynar
401  */
402 gras_error_t
403 gras_dynar_push(gras_dynar_t * const dynar,
404                 const void   * const src) {
405   __sanity_check_dynar(dynar);
406   return gras_dynar_insert_at(dynar, dynar->used, src);
407 }
408
409 /**
410  * gras_dynar_pop:
411  * @dynar:
412  * @dst:
413  *
414  * Get and remove the last element of the dynar
415  */
416 void
417 gras_dynar_pop(gras_dynar_t * const dynar,
418                void         * const dst) {
419   __sanity_check_dynar(dynar);
420   __check_populated_dynar(dynar);
421   gras_dynar_remove_at(dynar, dynar->used-1, dst);
422 }
423
424 /**
425  * gras_dynar_unshift:
426  * @dynar:
427  * @src:
428  * @Returns: malloc_error or no_error
429  *
430  * Add an element at the begining of the dynar (rather long, Use
431  * gras_dynar_push() when possible)
432  */
433 gras_error_t
434 gras_dynar_unshift(gras_dynar_t * const dynar,
435                    const void   * const src) {
436   __sanity_check_dynar(dynar);
437   return gras_dynar_insert_at(dynar, 0, src);
438 }
439
440 /**
441  * gras_dynar_shift:
442  * @dynar:
443  * @dst:
444  *
445  * Get and remove the first element of the dynar (rather long, Use
446  * gras_dynar_pop() when possible)
447  */
448 void
449 gras_dynar_shift(gras_dynar_t * const dynar,
450                  void         * const dst) {
451
452   __sanity_check_dynar(dynar);
453   __check_populated_dynar(dynar);
454   gras_dynar_remove_at(dynar, 0, dst);
455 }
456
457 /**
458  * gras_dynar_map:
459  * @dynar:
460  * @operator:
461  *
462  * Apply a function to each member of a dynar (this function may change the
463  * value of the element itself, but should not mess with the dynar).
464  */
465 void
466 gras_dynar_map(const gras_dynar_t * const dynar,
467                void_f_pvoid_t     * const operator) {
468
469   __sanity_check_dynar(dynar);
470
471   {
472     char         elm[64];
473     const size_t used = dynar->used;
474     size_t       i    = 0;
475
476     for (i = 0; i < used; i++) {
477       _gras_dynar_get_elm(elm, dynar, i);
478       operator(elm);
479     }
480   }
481 }
482
483 /**
484  * gras_dynar_first:
485  *
486  * Put the cursor at the begining of the dynar. (actually, one step before
487  * the begining, so that you can iterate over the dynar with a for loop).
488  *
489  * Dynar cursor are as dumb as possible. If you insert or remove elements
490  * from the dynar between the creation and end, you'll fuck up your
491  * cursors.
492  *
493  */
494 void
495 gras_dynar_cursor_first(const gras_dynar_t * const dynar,
496                         int                * const cursor) {
497
498   __sanity_check_dynar(dynar);
499   DEBUG1("Set cursor on %p to the first position",dynar);
500   *cursor = 0;
501 }
502
503 /**
504  * gras_dynar_cursor_step:
505  *
506  * Move the cursor to the next value (and return true), or return false.
507  */
508 void
509 gras_dynar_cursor_step(const gras_dynar_t * const dynar,
510                        int                * const cursor) {
511   
512   __sanity_check_dynar(dynar);
513   (*cursor)++;
514 }
515
516 /**
517  * gras_dynar_cursor_get:
518  *
519  * Get the current value of the cursor
520  */
521 int
522 gras_dynar_cursor_get(const gras_dynar_t * const dynar,
523                       int                * const cursor,
524                       void               * const dst) {
525
526   __sanity_check_dynar(dynar);
527   {
528
529     const int idx = *cursor;
530
531     if (idx >= dynar->used) {
532       DEBUG1("Cursor on %p already on last elem",dynar);
533       return FALSE;
534     }
535     DEBUG2("Cash out cursor on %p at %d",dynar,idx);
536
537     _gras_dynar_get_elm(dst, dynar, idx);
538   }
539   return TRUE;
540
541 }
542
543 /**
544  * gras_dynar_cursor_rm:
545  * @dynar:
546  * @cursor:
547  *
548  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
549  */
550 void gras_dynar_cursor_rm(gras_dynar_t * dynar,
551                           int          * const cursor) {
552   void *dst;
553
554   if (dynar->elmsize > sizeof(void*)) {
555     DEBUG0("Elements too big to fit into a pointer");
556     if (dynar->free) {
557       dst=malloc(dynar->elmsize);
558       gras_dynar_remove_at(dynar,(*cursor)--,dst);
559       (dynar->free)(dst);
560       free(dst);
561     } else {
562       DEBUG0("Ok, we dont care about the element when no free function");
563       gras_dynar_remove_at(dynar,(*cursor)--,NULL);
564     }
565       
566   } else {
567     gras_dynar_remove_at(dynar,(*cursor)--,&dst);
568     if (dynar->free)
569       (dynar->free)(dst);
570   }
571 }