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