Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Some work to get it ansi compliant, still much to doo
[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",(void*)dynar)
42
43 static _GRAS_INLINE 
44 void _gras_clear_mem(void * const ptr,
45                      const size_t length) {
46   memset(ptr, 0, length);
47 }
48
49 static _GRAS_INLINE
50 gras_error_t
51 _gras_dynar_expand(gras_dynar_t * const dynar,
52                    const int            nb) {
53   gras_error_t errcode     = no_error;
54   const size_t old_size    = dynar->size;
55
56   if (nb > old_size) {
57     char * const old_data    = dynar->data;
58
59     const size_t elmsize     = dynar->elmsize;
60     const size_t old_length  = old_size*elmsize;
61
62     const size_t used        = dynar->used;
63     const size_t used_length = used*elmsize;
64
65     const size_t new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
66     const size_t new_length  = new_size*elmsize;
67     char * const new_data    = gras_malloc0(elmsize*new_size);
68
69     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
70     if (!new_data)
71       RAISE_MALLOC;
72
73     if (old_data) {
74       memcpy(new_data, old_data, used_length);
75       _gras_clear_mem(old_data, old_length);
76       gras_free(old_data);
77     }
78
79     _gras_clear_mem(new_data + used_length, new_length - used_length);
80
81     dynar->size = new_size;
82     dynar->data = new_data;
83   }
84
85   return errcode;
86 }
87
88 static _GRAS_INLINE
89 void *
90 _gras_dynar_elm(const gras_dynar_t * const dynar,
91                 const size_t               idx) {
92   char * const data    = dynar->data;
93   const size_t elmsize = dynar->elmsize;
94
95   return data + idx*elmsize;
96 }
97
98 static _GRAS_INLINE
99 void
100 _gras_dynar_get_elm(void               * const dst,
101                     const gras_dynar_t * const dynar,
102                     const size_t               idx) {
103   void * const elm     = _gras_dynar_elm(dynar, idx);
104   const size_t elmsize = dynar->elmsize;
105
106   memcpy(dst, elm, elmsize);
107 }
108
109 static _GRAS_INLINE
110 void
111 _gras_dynar_put_elm(const gras_dynar_t * const dynar,
112                     const size_t               idx,
113                     const void         * const src) {
114   void * const elm     = _gras_dynar_elm(dynar, idx);
115   const size_t elmsize = dynar->elmsize;
116
117   memcpy(elm, src, elmsize);
118 }
119
120 /**
121  * gras_dynar_new:
122  * @whereto: pointer to where the dynar should be created
123  * @elm_size: size of each element in the dynar
124  * @free_func: function to call each time we want to get rid of an element (or NULL if nothing to do).
125  * @Returns: malloc_error or no_error
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 gras_error_t
132 gras_dynar_new(gras_dynar_t   ** const p_dynar,
133                const size_t            elmsize,
134                void_f_pvoid_t  * const free_func) {
135   gras_error_t  errcode = no_error;
136   gras_dynar_t *dynar   = NULL;
137
138   if (!(dynar = gras_new0(gras_dynar_t,1)))
139     RAISE_MALLOC;
140
141   dynar->size    = 0;
142   dynar->used    = 0;
143   dynar->elmsize = elmsize;
144   dynar->data    = NULL;
145   dynar->free    = free_func;
146
147   *p_dynar = dynar;
148
149   return errcode;
150 }
151
152 /**
153  * gras_dynar_free_container:
154  * @dynar: poor victim
155  *
156  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
157  * its contain points to.
158  */
159 void
160 gras_dynar_free_container(gras_dynar_t * const dynar) {
161   if (dynar) {
162
163     if (dynar->data) {
164       _gras_clear_mem(dynar->data, dynar->size);
165       gras_free(dynar->data);
166     }
167
168     _gras_clear_mem(dynar, sizeof(gras_dynar_t));
169
170     gras_free(dynar);
171   }
172 }
173
174 /**
175  * gras_dynar_reset:
176  * @dynar: who to squeeze
177  *
178  * Frees the content and set the size to 0
179  */
180 void
181 gras_dynar_reset(gras_dynar_t * const dynar) {
182
183   __sanity_check_dynar(dynar);
184
185   DEBUG1("Reset the dynar %p",(void*)dynar);
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     gras_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 unsigned long
222 gras_dynar_length(const gras_dynar_t * const dynar) {
223   return (dynar ? (unsigned long) dynar->used : (unsigned long)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   DEBUG1("Pop %p",(void*)dynar);
422   gras_dynar_remove_at(dynar, dynar->used-1, dst);
423 }
424
425 /**
426  * gras_dynar_unshift:
427  * @dynar:
428  * @src:
429  * @Returns: malloc_error or no_error
430  *
431  * Add an element at the begining of the dynar (rather long, Use
432  * gras_dynar_push() when possible)
433  */
434 gras_error_t
435 gras_dynar_unshift(gras_dynar_t * const dynar,
436                    const void   * const src) {
437   __sanity_check_dynar(dynar);
438   return gras_dynar_insert_at(dynar, 0, src);
439 }
440
441 /**
442  * gras_dynar_shift:
443  * @dynar:
444  * @dst:
445  *
446  * Get and remove the first element of the dynar (rather long, Use
447  * gras_dynar_pop() when possible)
448  */
449 void
450 gras_dynar_shift(gras_dynar_t * const dynar,
451                  void         * const dst) {
452
453   __sanity_check_dynar(dynar);
454   __check_populated_dynar(dynar);
455   gras_dynar_remove_at(dynar, 0, dst);
456 }
457
458 /**
459  * gras_dynar_map:
460  * @dynar:
461  * @operator:
462  *
463  * Apply a function to each member of a dynar (this function may change the
464  * value of the element itself, but should not mess with the dynar).
465  */
466 void
467 gras_dynar_map(const gras_dynar_t * const dynar,
468                void_f_pvoid_t     * const operator) {
469
470   __sanity_check_dynar(dynar);
471
472   {
473     char         elm[64];
474     const size_t used = dynar->used;
475     size_t       i    = 0;
476
477     for (i = 0; i < used; i++) {
478       _gras_dynar_get_elm(elm, dynar, i);
479       operator(elm);
480     }
481   }
482 }
483
484 /**
485  * gras_dynar_first:
486  *
487  * Put the cursor at the begining of the dynar. (actually, one step before
488  * the begining, so that you can iterate over the dynar with a for loop).
489  *
490  * Dynar cursor are as dumb as possible. If you insert or remove elements
491  * from the dynar between the creation and end, you'll fuck up your
492  * cursors.
493  *
494  */
495 void
496 gras_dynar_cursor_first(const gras_dynar_t * const dynar,
497                         int                * const cursor) {
498
499   __sanity_check_dynar(dynar);
500   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
501   *cursor = 0;
502 }
503
504 /**
505  * gras_dynar_cursor_step:
506  *
507  * Move the cursor to the next value (and return true), or return false.
508  */
509 void
510 gras_dynar_cursor_step(const gras_dynar_t * const dynar,
511                        int                * const cursor) {
512   
513   __sanity_check_dynar(dynar);
514   (*cursor)++;
515 }
516
517 /**
518  * gras_dynar_cursor_get:
519  *
520  * Get the current value of the cursor
521  */
522 int
523 gras_dynar_cursor_get(const gras_dynar_t * const dynar,
524                       int                * const cursor,
525                       void               * const dst) {
526
527   __sanity_check_dynar(dynar);
528   {
529
530     const int idx = *cursor;
531
532     if (idx >= dynar->used) {
533       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
534       return FALSE;
535     }
536     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
537
538     _gras_dynar_get_elm(dst, dynar, idx);
539   }
540   return TRUE;
541
542 }
543
544 /**
545  * gras_dynar_cursor_rm:
546  * @dynar:
547  * @cursor:
548  *
549  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
550  */
551 void gras_dynar_cursor_rm(gras_dynar_t * dynar,
552                           int          * const cursor) {
553   void *dst;
554
555   if (dynar->elmsize > sizeof(void*)) {
556     DEBUG0("Elements too big to fit into a pointer");
557     if (dynar->free) {
558       dst=gras_malloc(dynar->elmsize);
559       gras_dynar_remove_at(dynar,(*cursor)--,dst);
560       (dynar->free)(dst);
561       gras_free(dst);
562     } else {
563       DEBUG0("Ok, we dont care about the element when no free function");
564       gras_dynar_remove_at(dynar,(*cursor)--,NULL);
565     }
566       
567   } else {
568     gras_dynar_remove_at(dynar,(*cursor)--,&dst);
569     if (dynar->free)
570       (dynar->free)(dst);
571   }
572 }