src/xbt/dynar.c

   1 /* $Id$ */
   2
   3 /* a generic DYNamic ARray implementation.                                  */
   4
   5 /* Copyright (c) 2003, 2004 Martin Quinson. All rights reserved.            */
   6
   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. */
   9
  10 #include "portable.h" /* SIZEOF_MAX */
  11 #include "xbt/misc.h"
  12 #include "xbt/sysdep.h"
  13 #include "xbt/log.h"
  14 #include "xbt/error.h"
  15 #include "xbt/dynar.h"
  16 #include <sys/types.h>
  17
  18 #include "xbt/dynar_private.h" /* type definition, which we share with the
  19                                   code in charge of sending this across the net */
  20
  21 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,xbt,"Dynamic arrays");
  22
  23
  24 #define __sanity_check_dynar(dynar)       \
  25            xbt_assert0(dynar,           \
  26                         "dynar is NULL")
  27 #define __sanity_check_idx(idx)                \
  28            xbt_assert1(idx >= 0,             \
  29                         "dynar idx(=%d) < 0", \
  30                         (int) (idx))
  31 #define __check_inbound_idx(dynar, idx)                                                \
  32            xbt_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            xbt_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            xbt_assert1(dynar->used,              \
  41                         "dynar %p contains nothing",(void*)dynar)
  42
  43 static _XBT_INLINE
  44 void _xbt_clear_mem(void * const ptr,
  45                      const unsigned long length) {
  46   memset(ptr, 0, length);
  47 }
  48
  49 static _XBT_INLINE
  50 xbt_error_t
  51 _xbt_dynar_expand(xbt_dynar_t const dynar,
  52                    const int          nb) {
  53   xbt_error_t errcode     = no_error;
  54   const unsigned long old_size    = dynar->size;
  55
  56   if (nb > old_size) {
  57     char * const old_data    = dynar->data;
  58
  59     const unsigned long elmsize     = dynar->elmsize;
  60     const unsigned long old_length  = old_size*elmsize;
  61
  62     const unsigned long used        = dynar->used;
  63     const unsigned long used_length = used*elmsize;
  64
  65     const unsigned long new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
  66     const unsigned long new_length  = new_size*elmsize;
  67     char * const new_data    = xbt_malloc0(elmsize*new_size);
  68
  69     DEBUG3("expend %p from %lu to %d elements", (void*)dynar, (unsigned long)old_size, nb);
  70
  71     if (old_data) {
  72       memcpy(new_data, old_data, used_length);
  73       _xbt_clear_mem(old_data, old_length);
  74       free(old_data);
  75     }
  76
  77     _xbt_clear_mem(new_data + used_length, new_length - used_length);
  78
  79     dynar->size = new_size;
  80     dynar->data = new_data;
  81   }
  82
  83   return errcode;
  84 }
  85
  86 static _XBT_INLINE
  87 void *
  88 _xbt_dynar_elm(const xbt_dynar_t  dynar,
  89                 const unsigned long idx) {
  90   char * const data    = dynar->data;
  91   const unsigned long elmsize = dynar->elmsize;
  92
  93   return data + idx*elmsize;
  94 }
  95
  96 static _XBT_INLINE
  97 void
  98 _xbt_dynar_get_elm(void  * const       dst,
  99                     const xbt_dynar_t  dynar,
 100                     const unsigned long idx) {
 101   void * const elm     = _xbt_dynar_elm(dynar, idx);
 102   const unsigned long elmsize = dynar->elmsize;
 103
 104   memcpy(dst, elm, elmsize);
 105 }
 106
 107 static _XBT_INLINE
 108 void
 109 _xbt_dynar_put_elm(const xbt_dynar_t  dynar,
 110                     const unsigned long idx,
 111                     const void * const  src) {
 112   void * const elm     = _xbt_dynar_elm(dynar, idx);
 113   const unsigned long elmsize = dynar->elmsize;
 114
 115   memcpy(elm, src, elmsize);
 116 }
 117
 118 /** @brief Constructor
 119  *
 120  * \param elmsize size of each element in the dynar
 121  * \param free_f function to call each time we want to get rid of an element (or NULL if nothing to do).
 122  *
 123  * Creates a new dynar. If a free_func is provided, the elements have to be
 124  * pointer of pointer. That is to say that dynars can contain either base
 125  * types (int, char, double, etc) or pointer of pointers (struct **).
 126  */
 127 xbt_dynar_t
 128 xbt_dynar_new(const unsigned long           elmsize,
 129                void_f_pvoid_t * const free_f) {
 130
 131   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t,1);
 132
 133   dynar->size    = 0;
 134   dynar->used    = 0;
 135   dynar->elmsize = elmsize;
 136   dynar->data    = NULL;
 137   dynar->free_f    = free_f;
 138
 139   return dynar;
 140 }
 141
 142 /** @brief Destructor of the structure not touching to the content
 143  *
 144  * \param dynar poor victim
 145  *
 146  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content
 147  * is not touched (the \a free_f function is not used)
 148  */
 149 void
 150 xbt_dynar_free_container(xbt_dynar_t *dynar) {
 151   if (dynar && *dynar) {
 152
 153     if ((*dynar)->data) {
 154       _xbt_clear_mem((*dynar)->data, (*dynar)->size);
 155       free((*dynar)->data);
 156     }
 157
 158     _xbt_clear_mem(*dynar, sizeof(s_xbt_dynar_t));
 159
 160     free(*dynar);
 161     *dynar=NULL;
 162   }
 163 }
 164
 165 /** @brief Frees the content and set the size to 0
 166  *
 167  * \param dynar who to squeeze
 168  */
 169 void
 170 xbt_dynar_reset(xbt_dynar_t const dynar) {
 171
 172   __sanity_check_dynar(dynar);
 173
 174   DEBUG1("Reset the dynar %p",(void*)dynar);
 175   if (dynar->free_f) {
 176     xbt_dynar_map(dynar, dynar->free_f);
 177   }
 178
 179   if (dynar->data)
 180     free(dynar->data);
 181
 182   dynar->size = 0;
 183   dynar->used = 0;
 184   dynar->data = NULL;
 185 }
 186
 187 /** @brief Destructor
 188  *
 189  * \param dynar poor victim
 190  *
 191  * kilkil a dynar and its content
 192  */
 193
 194 void
 195 xbt_dynar_free(xbt_dynar_t * dynar) {
 196   if (dynar && *dynar) {
 197     xbt_dynar_reset(*dynar);
 198     xbt_dynar_free_container(dynar);
 199   }
 200 }
 201
 202 /** @brief Count of dynar's elements
 203  *
 204  * \param dynar the dynar we want to mesure
 205  */
 206 unsigned long
 207 xbt_dynar_length(const xbt_dynar_t dynar) {
 208   return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
 209 }
 210
 211 /** @brief Retrieve a copy of the Nth element of a dynar.
 212  *
 213  * \param dynar information dealer
 214  * \param idx index of the slot we want to retrive
 215  * \param[out] dst where to put the result to.
 216  */
 217 void
 218 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
 219                    const int          idx,
 220                    void       * const dst) {
 221
 222   __sanity_check_dynar(dynar);
 223   __sanity_check_idx(idx);
 224   __check_inbound_idx(dynar, idx);
 225
 226   _xbt_dynar_get_elm(dst, dynar, idx);
 227 }
 228
 229 /** @brief Retrieve a pointer to the Nth element of a dynar.
 230  *
 231  * \param dynar information dealer
 232  * \param idx index of the slot we want to retrieve
 233  * \return the \a idx-th element of \a dynar.
 234  *
 235  * \warning The returned value is the actual content of the dynar.
 236  * Make a copy before fooling with it.
 237  */
 238 void*
 239 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
 240                    const int          idx) {
 241
 242   __sanity_check_dynar(dynar);
 243   __sanity_check_idx(idx);
 244   __check_inbound_idx(dynar, idx);
 245
 246   return _xbt_dynar_elm(dynar, idx);
 247 }
 248
 249 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
 250  *
 251  * \param dynar information dealer
 252  * \param idx index of the slot we want to modify
 253  * \param src What will be feeded to the dynar
 254  *
 255  * If you want to free the previous content, use xbt_dynar_replace().
 256  */
 257 void
 258 xbt_dynar_set(xbt_dynar_t         dynar,
 259                const int            idx,
 260                const void   * const src) {
 261
 262   __sanity_check_dynar(dynar);
 263   __sanity_check_idx(idx);
 264
 265   _xbt_dynar_expand(dynar, idx+1);
 266
 267   if (idx >= dynar->used) {
 268     dynar->used = idx+1;
 269   }
 270
 271   _xbt_dynar_put_elm(dynar, idx, src);
 272 }
 273
 274 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
 275  *
 276  * \param dynar
 277  * \param idx
 278  * \param object
 279  *
 280  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 281  * free the previous value at this position. If you don't want to free the
 282  * previous content, use xbt_dynar_set().
 283  */
 284 void
 285 xbt_dynar_replace(xbt_dynar_t         dynar,
 286                    const int            idx,
 287                    const void   * const object) {
 288
 289   __sanity_check_dynar(dynar);
 290   __sanity_check_idx(idx);
 291
 292   if (idx < dynar->used && dynar->free_f) {
 293     void * const old_object = _xbt_dynar_elm(dynar, idx);
 294
 295     dynar->free_f(old_object);
 296   }
 297
 298   xbt_dynar_set(dynar, idx, object);
 299 }
 300
 301 /** @brief Make room for a new element, and return a pointer to it
 302  *
 303  * You can then use regular affectation to set its value instead of relying
 304  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
 305  */
 306 void *
 307 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
 308                         const int            idx) {
 309
 310   __sanity_check_dynar(dynar);
 311   __sanity_check_idx(idx);
 312   __check_sloppy_inbound_idx(dynar, idx);
 313
 314   {
 315     const unsigned long old_used = dynar->used;
 316     const unsigned long new_used = old_used + 1;
 317
 318     _xbt_dynar_expand(dynar, new_used);
 319
 320     {
 321       const unsigned long nb_shift =  old_used - idx;
 322
 323       if (nb_shift)
 324          memmove(_xbt_dynar_elm(dynar, idx+1),
 325                  _xbt_dynar_elm(dynar, idx),
 326                  nb_shift * dynar->elmsize);
 327     }
 328
 329     dynar->used = new_used;
 330     return _xbt_dynar_elm(dynar,idx);
 331   }
 332 }
 333
 334 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
 335  *
 336  * Set the Nth element of a dynar, expanding the dynar if needed, and
 337  * moving the previously existing value and all subsequent ones to one
 338  * position right in the dynar.
 339  */
 340 void
 341 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
 342                     const int            idx,
 343                     const void   * const src) {
 344
 345   /* checks done in xbt_dynar_insert_at_ptr */
 346   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
 347          src,
 348          dynar->elmsize);
 349 }
 350
 351 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 352  *
 353  * Get the Nth element of a dynar, removing it from the dynar and moving
 354  * all subsequent values to one position left in the dynar.
 355  */
 356 void
 357 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
 358                      const int            idx,
 359                      void         * const object) {
 360
 361   __sanity_check_dynar(dynar);
 362   __sanity_check_idx(idx);
 363   __check_inbound_idx(dynar, idx);
 364
 365   if (object)
 366     _xbt_dynar_get_elm(object, dynar, idx);
 367
 368   {
 369     const unsigned long old_used = dynar->used;
 370     const unsigned long new_used = old_used - 1;
 371
 372     const unsigned long nb_shift =  old_used-1 - idx;
 373     const unsigned long elmsize  =  dynar->elmsize;
 374
 375     const unsigned long offset   =  nb_shift*elmsize;
 376
 377     void * const elm_src  = _xbt_dynar_elm(dynar, idx+1);
 378     void * const elm_dst  = _xbt_dynar_elm(dynar, idx);
 379
 380     memmove(elm_dst, elm_src, offset);
 381
 382     dynar->used = new_used;
 383   }
 384 }
 385
 386 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 387  *
 388  * You can then use regular affectation to set its value instead of relying
 389  * on the slow memcpy. This is what xbt_dynar_push_as() does.
 390  */
 391 void *
 392 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
 393   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 394 }
 395
 396 /** @brief Add an element at the end of the dynar */
 397 void
 398 xbt_dynar_push(xbt_dynar_t  const dynar,
 399                 const void   * const src) {
 400   /* sanity checks done by insert_at */
 401   xbt_dynar_insert_at(dynar, dynar->used, src);
 402 }
 403
 404 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 405  *
 406  * You can then use regular affectation to set its value instead of relying
 407  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
 408  */
 409 void *
 410 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 411
 412   __check_populated_dynar(dynar);
 413   DEBUG1("Pop %p",(void*)dynar);
 414   dynar->used--;
 415   return _xbt_dynar_elm(dynar,dynar->used);
 416 }
 417
 418 /** @brief Get and remove the last element of the dynar */
 419 void
 420 xbt_dynar_pop(xbt_dynar_t  const dynar,
 421                void         * const dst) {
 422
 423   /* sanity checks done by remove_at */
 424   DEBUG1("Pop %p",(void*)dynar);
 425   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 426 }
 427
 428 /** @brief Add an element at the begining of the dynar.
 429  *
 430  * This is less efficient than xbt_dynar_push()
 431  */
 432 void
 433 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 434                    const void   * const src) {
 435
 436   /* sanity checks done by insert_at */
 437   xbt_dynar_insert_at(dynar, 0, src);
 438 }
 439
 440 /** @brief Get and remove the first element of the dynar.
 441  *
 442  * This is less efficient than xbt_dynar_pop()
 443  */
 444 void
 445 xbt_dynar_shift(xbt_dynar_t  const dynar,
 446                  void         * const dst) {
 447
 448   /* sanity checks done by remove_at */
 449   xbt_dynar_remove_at(dynar, 0, dst);
 450 }
 451
 452 /** @brief Apply a function to each member of a dynar
 453  *
 454  * The mapped function may change the value of the element itself,
 455  * but should not mess with the structure of the dynar.
 456  */
 457 void
 458 xbt_dynar_map(const xbt_dynar_t  dynar,
 459                void_f_pvoid_t     * const operator) {
 460
 461   __sanity_check_dynar(dynar);
 462
 463   {
 464     char         elm[SIZEOF_MAX];
 465     const unsigned long used = dynar->used;
 466     unsigned long       i    = 0;
 467
 468     for (i = 0; i < used; i++) {
 469       _xbt_dynar_get_elm(elm, dynar, i);
 470       operator(elm);
 471     }
 472   }
 473 }
 474
 475 /** @brief Put the cursor at the begining of the dynar.
 476  *
 477  * Actually, the cursor is set one step before the begining, so that you
 478  * can iterate over the dynar with a for loop.
 479  */
 480 void
 481 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 482                        int        * const cursor) {
 483
 484   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 485   *cursor = 0;
 486 }
 487
 488 /** @brief Move the cursor to the next value */
 489 void
 490 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 491                        int        * const cursor) {
 492
 493   (*cursor)++;
 494 }
 495
 496 /** @brief Get the data currently pointed by the cursor */
 497 int
 498 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 499                       int                * const cursor,
 500                       void               * const dst) {
 501
 502   __sanity_check_dynar(dynar);
 503   {
 504
 505     const int idx = *cursor;
 506
 507     if (idx >= dynar->used) {
 508       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 509       return FALSE;
 510     }
 511     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 512
 513     _xbt_dynar_get_elm(dst, dynar, idx);
 514   }
 515   return TRUE;
 516
 517 }
 518
 519 /** @brief Removes and free the entry pointed by the cursor
 520  *
 521  * This function can be used while traversing without problem.
 522  */
 523 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 524                           int          * const cursor) {
 525   void *dst;
 526
 527   if (dynar->elmsize > sizeof(void*)) {
 528     DEBUG0("Elements too big to fit into a pointer");
 529     if (dynar->free_f) {
 530       dst=xbt_malloc(dynar->elmsize);
 531       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 532       (dynar->free_f)(dst);
 533       free(dst);
 534     } else {
 535       DEBUG0("Ok, we dont care about the element without free function");
 536       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 537     }
 538
 539   } else {
 540     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 541     if (dynar->free_f)
 542       (dynar->free_f)(dst);
 543   }
 544 }