Logo AND Algorithmique Numérique Distribuée

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