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>
19 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
21 typedef struct xbt_dynar_s {
24 unsigned long elmsize;
26 void_f_pvoid_t *free_f;
29 #define __sanity_check_dynar(dynar) \
32 #define __sanity_check_idx(idx) \
33 xbt_assert1(idx >= 0, \
34 "dynar idx(=%d) < 0", \
36 #define __check_inbound_idx(dynar, idx) \
37 xbt_assert2(idx < dynar->used, \
38 "dynar is not that long. You asked %d, but it's only %lu long", \
39 (int) (idx), (unsigned long) dynar->used)
40 #define __check_sloppy_inbound_idx(dynar, idx) \
41 xbt_assert2(idx <= dynar->used, \
42 "dynar is not that long. You asked %d, but it's only %lu long", \
43 (int) (idx), (unsigned long) dynar->used)
44 #define __check_populated_dynar(dynar) \
45 xbt_assert1(dynar->used, \
46 "dynar %p contains nothing",(void*)dynar)
49 void _xbt_clear_mem(void * const ptr,
50 const unsigned long length) {
51 memset(ptr, 0, length);
56 _xbt_dynar_expand(xbt_dynar_t const dynar,
58 xbt_error_t errcode = no_error;
59 const unsigned long old_size = dynar->size;
62 char * const old_data = dynar->data;
64 const unsigned long elmsize = dynar->elmsize;
65 const unsigned long old_length = old_size*elmsize;
67 const unsigned long used = dynar->used;
68 const unsigned long used_length = used*elmsize;
70 const unsigned long new_size = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
71 const unsigned long new_length = new_size*elmsize;
72 char * const new_data = xbt_malloc0(elmsize*new_size);
74 DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
77 memcpy(new_data, old_data, used_length);
78 _xbt_clear_mem(old_data, old_length);
82 _xbt_clear_mem(new_data + used_length, new_length - used_length);
84 dynar->size = new_size;
85 dynar->data = new_data;
93 _xbt_dynar_elm(const xbt_dynar_t dynar,
94 const unsigned long idx) {
95 char * const data = dynar->data;
96 const unsigned long elmsize = dynar->elmsize;
98 return data + idx*elmsize;
103 _xbt_dynar_get_elm(void * const dst,
104 const xbt_dynar_t dynar,
105 const unsigned long idx) {
106 void * const elm = _xbt_dynar_elm(dynar, idx);
107 const unsigned long elmsize = dynar->elmsize;
109 memcpy(dst, elm, elmsize);
114 _xbt_dynar_put_elm(const xbt_dynar_t dynar,
115 const unsigned long idx,
116 const void * const src) {
117 void * const elm = _xbt_dynar_elm(dynar, idx);
118 const unsigned long elmsize = dynar->elmsize;
120 memcpy(elm, src, elmsize);
123 /** @brief Constructor
125 * \param elmsize size of each element in the dynar
126 * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
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 **).
133 xbt_dynar_new(const unsigned long elmsize,
134 void_f_pvoid_t * const free_f) {
136 xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
140 dynar->elmsize = elmsize;
142 dynar->free_f = free_f;
147 /** @brief Destructor of the structure not touching to the content
149 * \param dynar poor victim
151 * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
152 * is not touched (the \a free_f function is not used)
155 xbt_dynar_free_container(xbt_dynar_t *dynar) {
156 if (dynar && *dynar) {
158 if ((*dynar)->data) {
159 _xbt_clear_mem((*dynar)->data, (*dynar)->size);
160 free((*dynar)->data);
163 _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
170 /** @brief Frees the content and set the size to 0
172 * \param dynar who to squeeze
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);
192 /** @brief Destructor
194 * \param 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);
207 /** @brief Count of dynar's elements
209 * \param dynar the dynar we want to mesure
212 xbt_dynar_length(const xbt_dynar_t dynar) {
213 return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
216 /** @brief Retrieve a copy of the Nth element of a dynar.
218 * \param dynar information dealer
219 * \param idx index of the slot we want to retrive
220 * \param[out] dst where to put the result to.
223 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
227 __sanity_check_dynar(dynar);
228 __sanity_check_idx(idx);
229 __check_inbound_idx(dynar, idx);
231 _xbt_dynar_get_elm(dst, dynar, idx);
234 /** @brief Retrieve a pointer to the Nth element of a dynar.
236 * \param dynar information dealer
237 * \param idx index of the slot we want to retrieve
238 * \return the \a idx-th element of \a dynar.
240 * \warning The returned value is the actual content of the dynar.
241 * Make a copy before fooling with it.
244 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
247 __sanity_check_dynar(dynar);
248 __sanity_check_idx(idx);
249 __check_inbound_idx(dynar, idx);
251 return _xbt_dynar_elm(dynar, idx);
254 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
256 * \param dynar information dealer
257 * \param idx index of the slot we want to modify
258 * \param src What will be feeded to the dynar
260 * If you want to free the previous content, use xbt_dynar_replace().
263 xbt_dynar_set(xbt_dynar_t dynar,
265 const void * const src) {
267 __sanity_check_dynar(dynar);
268 __sanity_check_idx(idx);
270 _xbt_dynar_expand(dynar, idx+1);
272 if (idx >= dynar->used) {
276 _xbt_dynar_put_elm(dynar, idx, src);
279 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
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 xbt_dynar_set().
290 xbt_dynar_replace(xbt_dynar_t dynar,
292 const void * const object) {
294 __sanity_check_dynar(dynar);
295 __sanity_check_idx(idx);
297 if (idx < dynar->used && dynar->free_f) {
298 void * const old_object = _xbt_dynar_elm(dynar, idx);
300 dynar->free_f(old_object);
303 xbt_dynar_set(dynar, idx, object);
306 /** @brief Make room for a new element, and return a pointer to it
308 * You can then use regular affectation to set its value instead of relying
309 * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
312 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
315 __sanity_check_dynar(dynar);
316 __sanity_check_idx(idx);
317 __check_sloppy_inbound_idx(dynar, idx);
320 const unsigned long old_used = dynar->used;
321 const unsigned long new_used = old_used + 1;
323 _xbt_dynar_expand(dynar, new_used);
326 const unsigned long nb_shift = old_used - idx;
329 memmove(_xbt_dynar_elm(dynar, idx+1),
330 _xbt_dynar_elm(dynar, idx),
331 nb_shift * dynar->elmsize);
334 dynar->used = new_used;
335 return _xbt_dynar_elm(dynar,idx);
339 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
341 * Set the Nth element of a dynar, expanding the dynar if needed, and
342 * moving the previously existing value and all subsequent ones to one
343 * position right in the dynar.
346 xbt_dynar_insert_at(xbt_dynar_t const dynar,
348 const void * const src) {
350 /* checks done in xbt_dynar_insert_at_ptr */
351 memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
356 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
358 * Get the Nth element of a dynar, removing it from the dynar and moving
359 * all subsequent values to one position left in the dynar.
362 xbt_dynar_remove_at(xbt_dynar_t const dynar,
364 void * const object) {
366 __sanity_check_dynar(dynar);
367 __sanity_check_idx(idx);
368 __check_inbound_idx(dynar, idx);
371 _xbt_dynar_get_elm(object, dynar, idx);
374 const unsigned long old_used = dynar->used;
375 const unsigned long new_used = old_used - 1;
377 const unsigned long nb_shift = old_used-1 - idx;
378 const unsigned long elmsize = dynar->elmsize;
380 const unsigned long offset = nb_shift*elmsize;
382 void * const elm_src = _xbt_dynar_elm(dynar, idx+1);
383 void * const elm_dst = _xbt_dynar_elm(dynar, idx);
385 memmove(elm_dst, elm_src, offset);
387 dynar->used = new_used;
391 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
393 * You can then use regular affectation to set its value instead of relying
394 * on the slow memcpy. This is what xbt_dynar_push_as() does.
397 xbt_dynar_push_ptr(xbt_dynar_t const dynar) {
398 return xbt_dynar_insert_at_ptr(dynar, dynar->used);
401 /** @brief Add an element at the end of the dynar */
403 xbt_dynar_push(xbt_dynar_t const dynar,
404 const void * const src) {
405 /* sanity checks done by insert_at */
406 xbt_dynar_insert_at(dynar, dynar->used, src);
409 /** @brief Mark the last dynar's element as unused and return a pointer to it.
411 * You can then use regular affectation to set its value instead of relying
412 * on the slow memcpy. This is what xbt_dynar_pop_as() does.
415 xbt_dynar_pop_ptr(xbt_dynar_t const dynar) {
417 __check_populated_dynar(dynar);
418 DEBUG1("Pop %p",(void*)dynar);
420 return _xbt_dynar_elm(dynar,dynar->used);
423 /** @brief Get and remove the last element of the dynar */
425 xbt_dynar_pop(xbt_dynar_t const dynar,
428 /* sanity checks done by remove_at */
429 DEBUG1("Pop %p",(void*)dynar);
430 xbt_dynar_remove_at(dynar, dynar->used-1, dst);
433 /** @brief Add an element at the begining of the dynar.
435 * This is less efficient than xbt_dynar_push()
438 xbt_dynar_unshift(xbt_dynar_t const dynar,
439 const void * const src) {
441 /* sanity checks done by insert_at */
442 xbt_dynar_insert_at(dynar, 0, src);
445 /** @brief Get and remove the first element of the dynar.
447 * This is less efficient than xbt_dynar_pop()
450 xbt_dynar_shift(xbt_dynar_t const dynar,
453 /* sanity checks done by remove_at */
454 xbt_dynar_remove_at(dynar, 0, dst);
457 /** @brief Apply a function to each member of a dynar
459 * The mapped function may change the value of the element itself,
460 * but should not mess with the structure of the dynar.
463 xbt_dynar_map(const xbt_dynar_t dynar,
464 void_f_pvoid_t * const operator) {
466 __sanity_check_dynar(dynar);
470 const unsigned long used = dynar->used;
473 for (i = 0; i < used; i++) {
474 _xbt_dynar_get_elm(elm, dynar, i);
480 /** @brief Put the cursor at the begining of the dynar.
482 * Actually, the cursor is set one step before the begining, so that you
483 * can iterate over the dynar with a for loop.
486 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
487 int * const cursor) {
489 DEBUG1("Set cursor on %p to the first position",(void*)dynar);
493 /** @brief Move the cursor to the next value */
495 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
496 int * const cursor) {
501 /** @brief Get the data currently pointed by the cursor */
503 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
507 __sanity_check_dynar(dynar);
510 const int idx = *cursor;
512 if (idx >= dynar->used) {
513 DEBUG1("Cursor on %p already on last elem",(void*)dynar);
516 DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
518 _xbt_dynar_get_elm(dst, dynar, idx);
524 /** @brief Removes and free the entry pointed by the cursor
526 * This function can be used while traversing without problem.
528 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
529 int * const cursor) {
532 if (dynar->elmsize > sizeof(void*)) {
533 DEBUG0("Elements too big to fit into a pointer");
535 dst=xbt_malloc(dynar->elmsize);
536 xbt_dynar_remove_at(dynar,(*cursor)--,dst);
537 (dynar->free_f)(dst);
540 DEBUG0("Ok, we dont care about the element without free function");
541 xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
545 xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
547 (dynar->free_f)(dst);