3 /* a generic DYNamic ARray */
5 /* Copyright (c) 2004 Martin Quinson. All rights reserved. */
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. */
11 #include "xbt/sysdep.h"
13 #include "xbt/error.h"
14 #include "xbt/dynar.h"
15 #include <sys/types.h>
17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
19 typedef struct xbt_dynar_s {
22 unsigned long elmsize;
24 void_f_pvoid_t *free_f;
27 #define __sanity_check_dynar(dynar) \
30 #define __sanity_check_idx(idx) \
31 xbt_assert1(idx >= 0, \
32 "dynar idx(=%d) < 0", \
34 #define __check_inbound_idx(dynar, idx) \
35 xbt_assert2(idx < dynar->used, \
36 "dynar is not that long. You asked %d, but it's only %lu long", \
37 (int) (idx), (unsigned long) dynar->used)
38 #define __check_sloppy_inbound_idx(dynar, idx) \
39 xbt_assert2(idx <= dynar->used, \
40 "dynar is not that long. You asked %d, but it's only %lu long", \
41 (int) (idx), (unsigned long) dynar->used)
42 #define __check_populated_dynar(dynar) \
43 xbt_assert1(dynar->used, \
44 "dynar %p contains nothing",(void*)dynar)
47 void _xbt_clear_mem(void * const ptr,
48 const unsigned long length) {
49 memset(ptr, 0, length);
54 _xbt_dynar_expand(xbt_dynar_t const dynar,
56 xbt_error_t errcode = no_error;
57 const unsigned long old_size = dynar->size;
60 char * const old_data = dynar->data;
62 const unsigned long elmsize = dynar->elmsize;
63 const unsigned long old_length = old_size*elmsize;
65 const unsigned long used = dynar->used;
66 const unsigned long used_length = used*elmsize;
68 const unsigned long new_size = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
69 const unsigned long new_length = new_size*elmsize;
70 char * const new_data = xbt_malloc0(elmsize*new_size);
72 DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
75 memcpy(new_data, old_data, used_length);
76 _xbt_clear_mem(old_data, old_length);
80 _xbt_clear_mem(new_data + used_length, new_length - used_length);
82 dynar->size = new_size;
83 dynar->data = new_data;
91 _xbt_dynar_elm(const xbt_dynar_t dynar,
92 const unsigned long idx) {
93 char * const data = dynar->data;
94 const unsigned long elmsize = dynar->elmsize;
96 return data + idx*elmsize;
101 _xbt_dynar_get_elm(void * const dst,
102 const xbt_dynar_t dynar,
103 const unsigned long idx) {
104 void * const elm = _xbt_dynar_elm(dynar, idx);
105 const unsigned long elmsize = dynar->elmsize;
107 memcpy(dst, elm, elmsize);
112 _xbt_dynar_put_elm(const xbt_dynar_t dynar,
113 const unsigned long idx,
114 const void * const src) {
115 void * const elm = _xbt_dynar_elm(dynar, idx);
116 const unsigned long elmsize = dynar->elmsize;
118 memcpy(elm, src, elmsize);
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).
126 * Creates a new dynar. If a free_func is provided, the elements have to be
127 * pointer of pointer. That is to say that dynars can contain either base
128 * types (int, char, double, etc) or pointer of pointers (struct **).
131 xbt_dynar_new(const unsigned long elmsize,
132 void_f_pvoid_t * const free_f) {
134 xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
138 dynar->elmsize = elmsize;
140 dynar->free_f = free_f;
146 * xbt_dynar_free_container:
147 * @dynar: poor victim
149 * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
150 * its contain points to.
153 xbt_dynar_free_container(xbt_dynar_t *dynar) {
154 if (dynar && *dynar) {
156 if ((*dynar)->data) {
157 _xbt_clear_mem((*dynar)->data, (*dynar)->size);
158 xbt_free((*dynar)->data);
161 _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
170 * @dynar: who to squeeze
172 * Frees the content and set the size to 0
175 xbt_dynar_reset(xbt_dynar_t const dynar) {
177 __sanity_check_dynar(dynar);
179 DEBUG1("Reset the dynar %p",(void*)dynar);
181 xbt_dynar_map(dynar, dynar->free_f);
185 xbt_free(dynar->data);
194 * @dynar: poor victim
196 * kilkil a dynar and its content
200 xbt_dynar_free(xbt_dynar_t * dynar) {
201 if (dynar && *dynar) {
202 xbt_dynar_reset(*dynar);
203 xbt_dynar_free_container(dynar);
209 * @dynar: the dynar we want to mesure
211 * Returns the count of elements in a dynar
214 xbt_dynar_length(const xbt_dynar_t dynar) {
215 return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
220 * @dynar: information dealer
221 * @idx: index of the slot we want to retrive
222 * @dst: where to pu the result to.
224 * Retrieve a copy of the Nth element of a dynar.
227 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
231 __sanity_check_dynar(dynar);
232 __sanity_check_idx(idx);
233 __check_inbound_idx(dynar, idx);
235 _xbt_dynar_get_elm(dst, dynar, idx);
240 * @dynar: information dealer
241 * @idx: index of the slot we want to retrive
242 * @dst: where to pu the result to.
244 * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of
245 * the dynar. Make a copy before fooling with it.
248 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
251 __sanity_check_dynar(dynar);
252 __sanity_check_idx(idx);
253 __check_inbound_idx(dynar, idx);
255 return _xbt_dynar_elm(dynar, idx);
262 * @src: What will be feeded to the dynar
264 * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
265 * the previous value at this position. If you want to free the previous content,
266 * use xbt_dynar_replace().
269 xbt_dynar_set(xbt_dynar_t dynar,
271 const void * const src) {
273 __sanity_check_dynar(dynar);
274 __sanity_check_idx(idx);
276 _xbt_dynar_expand(dynar, idx+1);
278 if (idx >= dynar->used) {
282 _xbt_dynar_put_elm(dynar, idx, src);
291 * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
292 * free the previous value at this position. If you don't want to free the
293 * previous content, use xbt_dynar_set().
296 xbt_dynar_replace(xbt_dynar_t dynar,
298 const void * const object) {
300 __sanity_check_dynar(dynar);
301 __sanity_check_idx(idx);
303 if (idx < dynar->used && dynar->free_f) {
304 void * const old_object = _xbt_dynar_elm(dynar, idx);
306 dynar->free_f(old_object);
309 xbt_dynar_set(dynar, idx, object);
313 * xbt_dynar_insert_at_ptr:
315 * Make room for a new element in the dynar, and return a pointer to
316 * its position. You can then use regular affectation to set its value
317 * instead of relying on the slow memcpy
320 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
323 __sanity_check_dynar(dynar);
324 __sanity_check_idx(idx);
325 __check_sloppy_inbound_idx(dynar, idx);
328 const unsigned long old_used = dynar->used;
329 const unsigned long new_used = old_used + 1;
331 _xbt_dynar_expand(dynar, new_used);
334 const unsigned long nb_shift = old_used - idx;
337 memmove(_xbt_dynar_elm(dynar, idx+1),
338 _xbt_dynar_elm(dynar, idx),
339 nb_shift * dynar->elmsize);
342 dynar->used = new_used;
343 return _xbt_dynar_elm(dynar,idx);
348 * xbt_dynar_insert_at:
351 * @src: What will be feeded to the dynar
353 * Set the Nth element of a dynar, expanding the dynar if needed, and
354 * moving the previously existing value and all subsequent ones to one
355 * position right in the dynar.
358 xbt_dynar_insert_at(xbt_dynar_t const dynar,
360 const void * const src) {
362 /* checks done in xbt_dynar_insert_at_ptr */
363 memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
369 * xbt_dynar_remove_at:
374 * Get the Nth element of a dynar, removing it from the dynar and moving
375 * all subsequent values to one position left in the dynar.
378 xbt_dynar_remove_at(xbt_dynar_t const dynar,
380 void * const object) {
382 __sanity_check_dynar(dynar);
383 __sanity_check_idx(idx);
384 __check_inbound_idx(dynar, idx);
387 _xbt_dynar_get_elm(object, dynar, idx);
390 const unsigned long old_used = dynar->used;
391 const unsigned long new_used = old_used - 1;
393 const unsigned long nb_shift = old_used-1 - idx;
394 const unsigned long elmsize = dynar->elmsize;
396 const unsigned long offset = nb_shift*elmsize;
398 void * const elm_src = _xbt_dynar_elm(dynar, idx+1);
399 void * const elm_dst = _xbt_dynar_elm(dynar, idx);
401 memmove(elm_dst, elm_src, offset);
403 dynar->used = new_used;
408 * xbt_dynar_push_ptr:
410 * Make room at the end of the dynar for a new element, and return a pointer to it
413 xbt_dynar_push_ptr(xbt_dynar_t const dynar) {
414 return xbt_dynar_insert_at_ptr(dynar, dynar->used);
422 * Add an element at the end of the dynar
425 xbt_dynar_push(xbt_dynar_t const dynar,
426 const void * const src) {
427 /* sanity checks done by insert_at */
428 xbt_dynar_insert_at(dynar, dynar->used, src);
436 * Make the last element of the dynar as unused and return a pointer to it.
439 xbt_dynar_pop_ptr(xbt_dynar_t const dynar) {
441 __check_populated_dynar(dynar);
442 DEBUG1("Pop %p",(void*)dynar);
444 return _xbt_dynar_elm(dynar,dynar->used);
452 * Get and remove the last element of the dynar
455 xbt_dynar_pop(xbt_dynar_t const dynar,
458 /* sanity checks done by remove_at */
459 DEBUG1("Pop %p",(void*)dynar);
460 xbt_dynar_remove_at(dynar, dynar->used-1, dst);
468 * Add an element at the begining of the dynar (rather long, Use
469 * xbt_dynar_push() when possible)
472 xbt_dynar_unshift(xbt_dynar_t const dynar,
473 const void * const src) {
475 /* sanity checks done by insert_at */
476 xbt_dynar_insert_at(dynar, 0, src);
484 * Get and remove the first element of the dynar (rather long, Use
485 * xbt_dynar_pop() when possible)
488 xbt_dynar_shift(xbt_dynar_t const dynar,
491 /* sanity checks done by remove_at */
492 xbt_dynar_remove_at(dynar, 0, dst);
500 * Apply a function to each member of a dynar (this function may change the
501 * value of the element itself, but should not mess with the dynar).
504 xbt_dynar_map(const xbt_dynar_t dynar,
505 void_f_pvoid_t * const operator) {
507 __sanity_check_dynar(dynar);
511 const unsigned long used = dynar->used;
514 for (i = 0; i < used; i++) {
515 _xbt_dynar_get_elm(elm, dynar, i);
522 * xbt_dynar_cursor_first:
524 * Put the cursor at the begining of the dynar. (actually, one step before
525 * the begining, so that you can iterate over the dynar with a for loop).
527 * Dynar cursor are as dumb as possible. If you insert or remove elements
528 * from the dynar between the creation and end, you'll fuck up your
533 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
534 int * const cursor) {
536 DEBUG1("Set cursor on %p to the first position",(void*)dynar);
541 * xbt_dynar_cursor_step:
543 * Move the cursor to the next value (and return true), or return false.
546 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
547 int * const cursor) {
553 * xbt_dynar_cursor_get:
555 * Get the current value of the cursor
558 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
562 __sanity_check_dynar(dynar);
565 const int idx = *cursor;
567 if (idx >= dynar->used) {
568 DEBUG1("Cursor on %p already on last elem",(void*)dynar);
571 DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
573 _xbt_dynar_get_elm(dst, dynar, idx);
580 * xbt_dynar_cursor_rm:
584 * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
586 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
587 int * const cursor) {
590 if (dynar->elmsize > sizeof(void*)) {
591 DEBUG0("Elements too big to fit into a pointer");
593 dst=xbt_malloc(dynar->elmsize);
594 xbt_dynar_remove_at(dynar,(*cursor)--,dst);
595 (dynar->free_f)(dst);
598 DEBUG0("Ok, we dont care about the element without free function");
599 xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
603 xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
605 (dynar->free_f)(dst);