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