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    = (char *) 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    = (char *) 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    = (char*) 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   */
 186   dynar->used = 0;
 187 /*  dynar->data = NULL;*/
 188 }
 189
 190 /** @brief Destructor
 191  *
 192  * \param dynar poor victim
 193  *
 194  * kilkil a dynar and its content
 195  */
 196
 197 void
 198 xbt_dynar_free(xbt_dynar_t * dynar) {
 199   if (dynar && *dynar) {
 200     xbt_dynar_reset(*dynar);
 201     xbt_dynar_free_container(dynar);
 202   }
 203 }
 204
 205 /** @brief Count of dynar's elements
 206  *
 207  * \param dynar the dynar we want to mesure
 208  */
 209 unsigned long
 210 xbt_dynar_length(const xbt_dynar_t dynar) {
 211   return (dynar ? (unsigned long) dynar->used : (unsigned long)0);
 212 }
 213
 214 /** @brief Retrieve a copy of the Nth element of a dynar.
 215  *
 216  * \param dynar information dealer
 217  * \param idx index of the slot we want to retrive
 218  * \param[out] dst where to put the result to.
 219  */
 220 void
 221 xbt_dynar_get_cpy(const xbt_dynar_t dynar,
 222                    const int          idx,
 223                    void       * const dst) {
 224
 225   __sanity_check_dynar(dynar);
 226   __sanity_check_idx(idx);
 227   __check_inbound_idx(dynar, idx);
 228
 229   _xbt_dynar_get_elm(dst, dynar, idx);
 230 }
 231
 232 /** @brief Retrieve a pointer to the Nth element of a dynar.
 233  *
 234  * \param dynar information dealer
 235  * \param idx index of the slot we want to retrieve
 236  * \return the \a idx-th element of \a dynar.
 237  *
 238  * \warning The returned value is the actual content of the dynar.
 239  * Make a copy before fooling with it.
 240  */
 241 void*
 242 xbt_dynar_get_ptr(const xbt_dynar_t dynar,
 243            const int          idx) {
 244
 245   __sanity_check_dynar(dynar);
 246   __sanity_check_idx(idx);
 247   __check_inbound_idx(dynar, idx);
 248
 249   return _xbt_dynar_elm(dynar, idx);
 250 }
 251
 252 /** @brief Set the Nth element of a dynar (expended if needed). Previous value at this position is NOT freed
 253  *
 254  * \param dynar information dealer
 255  * \param idx index of the slot we want to modify
 256  * \param src What will be feeded to the dynar
 257  *
 258  * If you want to free the previous content, use xbt_dynar_replace().
 259  */
 260 void
 261 xbt_dynar_set(xbt_dynar_t         dynar,
 262                const int            idx,
 263                const void   * const src) {
 264
 265   __sanity_check_dynar(dynar);
 266   __sanity_check_idx(idx);
 267
 268   _xbt_dynar_expand(dynar, idx+1);
 269
 270   if (idx >= dynar->used) {
 271     dynar->used = idx+1;
 272   }
 273
 274   _xbt_dynar_put_elm(dynar, idx, src);
 275 }
 276
 277 /** @brief Set the Nth element of a dynar (expended if needed). Previous value is freed
 278  *
 279  * \param dynar
 280  * \param idx
 281  * \param object
 282  *
 283  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 284  * free the previous value at this position. If you don't want to free the
 285  * previous content, use xbt_dynar_set().
 286  */
 287 void
 288 xbt_dynar_replace(xbt_dynar_t         dynar,
 289                    const int            idx,
 290                    const void   * const object) {
 291
 292   __sanity_check_dynar(dynar);
 293   __sanity_check_idx(idx);
 294
 295   if (idx < dynar->used && dynar->free_f) {
 296     void * const old_object = _xbt_dynar_elm(dynar, idx);
 297
 298     dynar->free_f(old_object);
 299   }
 300
 301   xbt_dynar_set(dynar, idx, object);
 302 }
 303
 304 /** @brief Make room for a new element, and return a pointer to it
 305  *
 306  * You can then use regular affectation to set its value instead of relying
 307  * on the slow memcpy. This is what xbt_dynar_insert_at_as() does.
 308  */
 309 void *
 310 xbt_dynar_insert_at_ptr(xbt_dynar_t const dynar,
 311                         const int            idx) {
 312
 313   __sanity_check_dynar(dynar);
 314   __sanity_check_idx(idx);
 315   __check_sloppy_inbound_idx(dynar, idx);
 316
 317   {
 318     const unsigned long old_used = dynar->used;
 319     const unsigned long new_used = old_used + 1;
 320
 321     _xbt_dynar_expand(dynar, new_used);
 322
 323     {
 324       const unsigned long nb_shift =  old_used - idx;
 325
 326       if (nb_shift)
 327          memmove(_xbt_dynar_elm(dynar, idx+1),
 328                  _xbt_dynar_elm(dynar, idx),
 329                  nb_shift * dynar->elmsize);
 330     }
 331
 332     dynar->used = new_used;
 333     return _xbt_dynar_elm(dynar,idx);
 334   }
 335 }
 336
 337 /** @brief Set the Nth dynar's element, expending the dynar and sliding the previous values to the right
 338  *
 339  * Set the Nth element of a dynar, expanding the dynar if needed, and
 340  * moving the previously existing value and all subsequent ones to one
 341  * position right in the dynar.
 342  */
 343 void
 344 xbt_dynar_insert_at(xbt_dynar_t  const dynar,
 345                     const int            idx,
 346                     const void   * const src) {
 347
 348   /* checks done in xbt_dynar_insert_at_ptr */
 349   memcpy(xbt_dynar_insert_at_ptr(dynar,idx),
 350          src,
 351          dynar->elmsize);
 352 }
 353
 354 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 355  *
 356  * Get the Nth element of a dynar, removing it from the dynar and moving
 357  * all subsequent values to one position left in the dynar.
 358  */
 359 void
 360 xbt_dynar_remove_at(xbt_dynar_t  const dynar,
 361                      const int            idx,
 362                      void         * const object) {
 363
 364   unsigned long nb_shift;
 365   unsigned long offset;
 366
 367   __sanity_check_dynar(dynar);
 368   __sanity_check_idx(idx);
 369   __check_inbound_idx(dynar, idx);
 370
 371   if (object) {
 372     _xbt_dynar_get_elm(object, dynar, idx);
 373   } else if (dynar->free_f) {
 374     char elm[SIZEOF_MAX];
 375     _xbt_dynar_get_elm(elm, dynar, idx);
 376     (*dynar->free_f)(elm);
 377   }
 378
 379   nb_shift =  dynar->used-1 - idx;
 380   offset   =  nb_shift * dynar->elmsize;
 381
 382   memmove(_xbt_dynar_elm(dynar, idx),
 383           _xbt_dynar_elm(dynar, idx+1),
 384           offset);
 385
 386   dynar->used--;
 387 }
 388
 389 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 390  *
 391  * You can then use regular affectation to set its value instead of relying
 392  * on the slow memcpy. This is what xbt_dynar_push_as() does.
 393  */
 394 void *
 395 xbt_dynar_push_ptr(xbt_dynar_t  const dynar) {
 396   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 397 }
 398
 399 /** @brief Add an element at the end of the dynar */
 400 void
 401 xbt_dynar_push(xbt_dynar_t  const dynar,
 402                 const void   * const src) {
 403   /* sanity checks done by insert_at */
 404   xbt_dynar_insert_at(dynar, dynar->used, src);
 405 }
 406
 407 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 408  *
 409  * You can then use regular affectation to set its value instead of relying
 410  * on the slow memcpy. This is what xbt_dynar_pop_as() does.
 411  */
 412 void *
 413 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 414
 415   __check_populated_dynar(dynar);
 416   DEBUG1("Pop %p",(void*)dynar);
 417   dynar->used--;
 418   return _xbt_dynar_elm(dynar,dynar->used);
 419 }
 420
 421 /** @brief Get and remove the last element of the dynar */
 422 void
 423 xbt_dynar_pop(xbt_dynar_t  const dynar,
 424               void         * const dst) {
 425
 426   /* sanity checks done by remove_at */
 427   DEBUG1("Pop %p",(void*)dynar);
 428   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 429 }
 430
 431 /** @brief Add an element at the begining of the dynar.
 432  *
 433  * This is less efficient than xbt_dynar_push()
 434  */
 435 void
 436 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 437                    const void   * const src) {
 438
 439   /* sanity checks done by insert_at */
 440   xbt_dynar_insert_at(dynar, 0, src);
 441 }
 442
 443 /** @brief Get and remove the first element of the dynar.
 444  *
 445  * This is less efficient than xbt_dynar_pop()
 446  */
 447 void
 448 xbt_dynar_shift(xbt_dynar_t  const dynar,
 449                  void         * const dst) {
 450
 451   /* sanity checks done by remove_at */
 452   xbt_dynar_remove_at(dynar, 0, dst);
 453 }
 454
 455 /** @brief Apply a function to each member of a dynar
 456  *
 457  * The mapped function may change the value of the element itself,
 458  * but should not mess with the structure of the dynar.
 459  */
 460 void
 461 xbt_dynar_map(const xbt_dynar_t  dynar,
 462                void_f_pvoid_t     * const op) {
 463
 464   __sanity_check_dynar(dynar);
 465
 466   {
 467     char         elm[SIZEOF_MAX];
 468     const unsigned long used = dynar->used;
 469     unsigned long       i    = 0;
 470
 471     for (i = 0; i < used; i++) {
 472       _xbt_dynar_get_elm(elm, dynar, i);
 473       op(elm);
 474     }
 475   }
 476 }
 477
 478 /** @brief Put the cursor at the begining of the dynar.
 479  *
 480  * Actually, the cursor is set one step before the begining, so that you
 481  * can iterate over the dynar with a for loop.
 482  */
 483 void
 484 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 485                        int        * const cursor) {
 486
 487   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 488   *cursor = 0;
 489 }
 490
 491 /** @brief Move the cursor to the next value */
 492 void
 493 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 494                        int        * const cursor) {
 495
 496   (*cursor)++;
 497 }
 498
 499 /** @brief Get the data currently pointed by the cursor */
 500 int
 501 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 502                       int                * const cursor,
 503                       void               * const dst) {
 504
 505   __sanity_check_dynar(dynar);
 506   {
 507
 508     const int idx = *cursor;
 509
 510     if (idx >= dynar->used) {
 511       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 512       return FALSE;
 513     }
 514     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 515
 516     _xbt_dynar_get_elm(dst, dynar, idx);
 517   }
 518   return TRUE;
 519
 520 }
 521
 522 /** @brief Removes and free the entry pointed by the cursor
 523  *
 524  * This function can be used while traversing without problem.
 525  */
 526 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 527                           int          * const cursor) {
 528   void *dst;
 529
 530   if (dynar->elmsize > sizeof(void*)) {
 531     DEBUG0("Elements too big to fit into a pointer");
 532     if (dynar->free_f) {
 533       dst=xbt_malloc(dynar->elmsize);
 534       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 535       (dynar->free_f)(dst);
 536       free(dst);
 537     } else {
 538       DEBUG0("Ok, we dont care about the element without free function");
 539       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 540     }
 541
 542   } else {
 543     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 544     if (dynar->free_f)
 545       (dynar->free_f)(dst);
 546   }
 547 }