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