3 /* a generic DYNamic ARray implementation. */
5 /* Copyright (c) 2003, 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 /** \defgroup XBT_dynar A generic dynamic array
18 * \brief This section describes the API to generic dynamic array (vector).
22 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
24 typedef struct xbt_dynar_s {
27 unsigned long elmsize;
29 void_f_pvoid_t *free_f;
32 #define __sanity_check_dynar(dynar) \
35 #define __sanity_check_idx(idx) \
36 xbt_assert1(idx >= 0, \
37 "dynar idx(=%d) < 0", \
39 #define __check_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_sloppy_inbound_idx(dynar, idx) \
44 xbt_assert2(idx <= dynar->used, \
45 "dynar is not that long. You asked %d, but it's only %lu long", \
46 (int) (idx), (unsigned long) dynar->used)
47 #define __check_populated_dynar(dynar) \
48 xbt_assert1(dynar->used, \
49 "dynar %p contains nothing",(void*)dynar)
52 void _xbt_clear_mem(void * const ptr,
53 const unsigned long length) {
54 memset(ptr, 0, length);
59 _xbt_dynar_expand(xbt_dynar_t const dynar,
61 xbt_error_t errcode = no_error;
62 const unsigned long old_size = dynar->size;
65 char * const old_data = dynar->data;
67 const unsigned long elmsize = dynar->elmsize;
68 const unsigned long old_length = old_size*elmsize;
70 const unsigned long used = dynar->used;
71 const unsigned long used_length = used*elmsize;
73 const unsigned long new_size = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
74 const unsigned long new_length = new_size*elmsize;
75 char * const new_data = xbt_malloc0(elmsize*new_size);
77 DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
80 memcpy(new_data, old_data, used_length);
81 _xbt_clear_mem(old_data, old_length);
85 _xbt_clear_mem(new_data + used_length, new_length - used_length);
87 dynar->size = new_size;
88 dynar->data = new_data;
96 _xbt_dynar_elm(const xbt_dynar_t dynar,
97 const unsigned long idx) {
98 char * const data = dynar->data;
99 const unsigned long elmsize = dynar->elmsize;
101 return data + idx*elmsize;
106 _xbt_dynar_get_elm(void * const dst,
107 const xbt_dynar_t dynar,
108 const unsigned long idx) {
109 void * const elm = _xbt_dynar_elm(dynar, idx);
110 const unsigned long elmsize = dynar->elmsize;
112 memcpy(dst, elm, elmsize);
117 _xbt_dynar_put_elm(const xbt_dynar_t dynar,
118 const unsigned long idx,
119 const void * const src) {
120 void * const elm = _xbt_dynar_elm(dynar, idx);
121 const unsigned long elmsize = dynar->elmsize;
123 memcpy(elm, src, elmsize);
128 * \param elmsize size of each element in the dynar
129 * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
131 * Creates a new dynar. If a free_func is provided, the elements have to be
132 * pointer of pointer. That is to say that dynars can contain either base
133 * types (int, char, double, etc) or pointer of pointers (struct **).
136 xbt_dynar_new(const unsigned long elmsize,
137 void_f_pvoid_t * const free_f) {
139 xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
143 dynar->elmsize = elmsize;
145 dynar->free_f = free_f;
152 * \param dynar poor victim
154 * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
155 * its contain points to.
158 xbt_dynar_free_container(xbt_dynar_t *dynar) {
159 if (dynar && *dynar) {
161 if ((*dynar)->data) {
162 _xbt_clear_mem((*dynar)->data, (*dynar)->size);
163 xbt_free((*dynar)->data);
166 _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
175 * \param dynar who to squeeze
177 * Frees the content and set the size to 0
180 xbt_dynar_reset(xbt_dynar_t const dynar) {
182 __sanity_check_dynar(dynar);
184 DEBUG1("Reset the dynar %p",(void*)dynar);
186 xbt_dynar_map(dynar, dynar->free_f);
190 xbt_free(dynar->data);
199 * \param dynar poor victim
201 * kilkil a dynar and its content
205 xbt_dynar_free(xbt_dynar_t * dynar) {
206 if (dynar && *dynar) {
207 xbt_dynar_reset(*dynar);
208 xbt_dynar_free_container(dynar);
214 * \param dynar the dynar we want to mesure
216 * Returns the count of elements in a dynar
219 xbt_dynar_length(const xbt_dynar_t dynar) {
220 return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
225 * \param dynar information dealer
226 * \param idx index of the slot we want to retrive
227 * \param[out] dst where to put the result to.
229 * Retrieve a copy of the Nth element of a dynar.
232 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
236 __sanity_check_dynar(dynar);
237 __sanity_check_idx(idx);
238 __check_inbound_idx(dynar, idx);
240 _xbt_dynar_get_elm(dst, dynar, idx);
245 * \param dynar information dealer
246 * \param idx index of the slot we want to retrieve
247 * \return the #idx-th element of #dynar.
249 * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of
250 * the dynar. Make a copy before fooling with it.
253 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
256 __sanity_check_dynar(dynar);
257 __sanity_check_idx(idx);
258 __check_inbound_idx(dynar, idx);
260 return _xbt_dynar_elm(dynar, idx);
265 * \param dynar information dealer
266 * \param idx index of the slot we want to modify
267 * \param src What will be feeded to the dynar
269 * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
270 * the previous value at this position. If you want to free the previous content,
271 * use xbt_dynar_replace().
274 xbt_dynar_set(xbt_dynar_t dynar,
276 const void * const src) {
278 __sanity_check_dynar(dynar);
279 __sanity_check_idx(idx);
281 _xbt_dynar_expand(dynar, idx+1);
283 if (idx >= dynar->used) {
287 _xbt_dynar_put_elm(dynar, idx, src);
296 * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
297 * free the previous value at this position. If you don't want to free the
298 * previous content, use xbt_dynar_set().
301 xbt_dynar_replace(xbt_dynar_t dynar,
303 const void * const object) {
305 __sanity_check_dynar(dynar);
306 __sanity_check_idx(idx);
308 if (idx < dynar->used && dynar->free_f) {
309 void * const old_object = _xbt_dynar_elm(dynar, idx);
311 dynar->free_f(old_object);
314 xbt_dynar_set(dynar, idx, object);
320 * Make room for a new element in the dynar, and return a pointer to
321 * its position. You can then use regular affectation to set its value
322 * instead of relying on the slow memcpy
325 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
328 __sanity_check_dynar(dynar);
329 __sanity_check_idx(idx);
330 __check_sloppy_inbound_idx(dynar, idx);
333 const unsigned long old_used = dynar->used;
334 const unsigned long new_used = old_used + 1;
336 _xbt_dynar_expand(dynar, new_used);
339 const unsigned long nb_shift = old_used - idx;
342 memmove(_xbt_dynar_elm(dynar, idx+1),
343 _xbt_dynar_elm(dynar, idx),
344 nb_shift * dynar->elmsize);
347 dynar->used = new_used;
348 return _xbt_dynar_elm(dynar,idx);
356 * \param src What will be feeded to the dynar
358 * Set the Nth element of a dynar, expanding the dynar if needed, and
359 * moving the previously existing value and all subsequent ones to one
360 * position right in the dynar.
363 xbt_dynar_insert_at(xbt_dynar_t const dynar,
365 const void * const src) {
367 /* checks done in xbt_dynar_insert_at_ptr */
368 memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
379 * Get the Nth element of a dynar, removing it from the dynar and moving
380 * all subsequent values to one position left in the dynar.
383 xbt_dynar_remove_at(xbt_dynar_t const dynar,
385 void * const object) {
387 __sanity_check_dynar(dynar);
388 __sanity_check_idx(idx);
389 __check_inbound_idx(dynar, idx);
392 _xbt_dynar_get_elm(object, dynar, idx);
395 const unsigned long old_used = dynar->used;
396 const unsigned long new_used = old_used - 1;
398 const unsigned long nb_shift = old_used-1 - idx;
399 const unsigned long elmsize = dynar->elmsize;
401 const unsigned long offset = nb_shift*elmsize;
403 void * const elm_src = _xbt_dynar_elm(dynar, idx+1);
404 void * const elm_dst = _xbt_dynar_elm(dynar, idx);
406 memmove(elm_dst, elm_src, offset);
408 dynar->used = new_used;
415 * Make room at the end of the dynar for a new element, and return a pointer to it
418 xbt_dynar_push_ptr(xbt_dynar_t const dynar) {
419 return xbt_dynar_insert_at_ptr(dynar, dynar->used);
427 * Add an element at the end of the dynar
430 xbt_dynar_push(xbt_dynar_t const dynar,
431 const void * const src) {
432 /* sanity checks done by insert_at */
433 xbt_dynar_insert_at(dynar, dynar->used, src);
440 * Make the last element of the dynar as unused and return a pointer to it.
443 xbt_dynar_pop_ptr(xbt_dynar_t const dynar) {
445 __check_populated_dynar(dynar);
446 DEBUG1("Pop %p",(void*)dynar);
448 return _xbt_dynar_elm(dynar,dynar->used);
456 * Get and remove the last element of the dynar
459 xbt_dynar_pop(xbt_dynar_t const dynar,
462 /* sanity checks done by remove_at */
463 DEBUG1("Pop %p",(void*)dynar);
464 xbt_dynar_remove_at(dynar, dynar->used-1, dst);
472 * Add an element at the begining of the dynar (rather long, Use
473 * xbt_dynar_push() when possible)
476 xbt_dynar_unshift(xbt_dynar_t const dynar,
477 const void * const src) {
479 /* sanity checks done by insert_at */
480 xbt_dynar_insert_at(dynar, 0, src);
488 * Get and remove the first element of the dynar (rather long, Use
489 * xbt_dynar_pop() when possible)
492 xbt_dynar_shift(xbt_dynar_t const dynar,
495 /* sanity checks done by remove_at */
496 xbt_dynar_remove_at(dynar, 0, dst);
504 * Apply a function to each member of a dynar (this function may change the
505 * value of the element itself, but should not mess with the dynar).
508 xbt_dynar_map(const xbt_dynar_t dynar,
509 void_f_pvoid_t * const operator) {
511 __sanity_check_dynar(dynar);
515 const unsigned long used = dynar->used;
518 for (i = 0; i < used; i++) {
519 _xbt_dynar_get_elm(elm, dynar, i);
528 * Put the cursor at the begining of the dynar. (actually, one step before
529 * the begining, so that you can iterate over the dynar with a for loop).
531 * Dynar cursor are as dumb as possible. If you insert or remove elements
532 * from the dynar between the creation and end, you'll fuck up your
537 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
538 int * const cursor) {
540 DEBUG1("Set cursor on %p to the first position",(void*)dynar);
547 * Move the cursor to the next value (and return true), or return false.
550 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
551 int * const cursor) {
559 * Get the current value of the cursor
562 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
566 __sanity_check_dynar(dynar);
569 const int idx = *cursor;
571 if (idx >= dynar->used) {
572 DEBUG1("Cursor on %p already on last elem",(void*)dynar);
575 DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
577 _xbt_dynar_get_elm(dst, dynar, idx);
588 * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
590 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
591 int * const cursor) {
594 if (dynar->elmsize > sizeof(void*)) {
595 DEBUG0("Elements too big to fit into a pointer");
597 dst=xbt_malloc(dynar->elmsize);
598 xbt_dynar_remove_at(dynar,(*cursor)--,dst);
599 (dynar->free_f)(dst);
602 DEBUG0("Ok, we dont care about the element without free function");
603 xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
607 xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
609 (dynar->free_f)(dst);