src/xbt/dynar.c

   1 /* $Id$ */
   2
   3 /* a generic DYNamic ARray                                                  */
   4
   5 /* Copyright (c) 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  * xbt_dynar_new:
 123  * @elm_size: size of each element in the dynar
 124  * @free_func: 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  * xbt_dynar_free_container:
 147  * @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  * xbt_dynar_reset:
 170  * @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  * xbt_dynar_free:
 194  * @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  * xbt_dynar_length:
 209  * @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  * xbt_dynar_get_cpy:
 220  * @dynar: information dealer
 221  * @idx: index of the slot we want to retrive
 222  * @dst: where to pu 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  * xbt_dynar_get_ptr:
 240  * @dynar: information dealer
 241  * @idx: index of the slot we want to retrive
 242  * @dst: where to pu the result to.
 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  * xbt_dynar_set:
 260  * @dynar:
 261  * @idx:
 262  * @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  * xbt_dynar_replace:
 287  * @dynar:
 288  * @idx:
 289  * @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  * xbt_dynar_insert_at_ptr:
 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  * xbt_dynar_insert_at:
 349  * @dynar:
 350  * @idx:
 351  * @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  * xbt_dynar_remove_at:
 370  * @dynar:
 371  * @idx:
 372  * @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  * xbt_dynar_push_ptr:
 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  * xbt_dynar_push:
 419  * @dynar:
 420  * @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  * xbt_dynar_pop_ptr:
 433  * @dynar:
 434  * @dst:
 435  *
 436  * Make the last element of the dynar as unused and return a pointer to it.
 437  */
 438 void *
 439 xbt_dynar_pop_ptr(xbt_dynar_t  const dynar) {
 440
 441   __check_populated_dynar(dynar);
 442   DEBUG1("Pop %p",(void*)dynar);
 443   dynar->used--;
 444   return _xbt_dynar_elm(dynar,dynar->used);
 445 }
 446
 447 /**
 448  * xbt_dynar_pop:
 449  * @dynar:
 450  * @dst:
 451  *
 452  * Get and remove the last element of the dynar
 453  */
 454 void
 455 xbt_dynar_pop(xbt_dynar_t  const dynar,
 456                void         * const dst) {
 457
 458   /* sanity checks done by remove_at */
 459   DEBUG1("Pop %p",(void*)dynar);
 460   xbt_dynar_remove_at(dynar, dynar->used-1, dst);
 461 }
 462
 463 /**
 464  * xbt_dynar_unshift:
 465  * @dynar:
 466  * @src:
 467  *
 468  * Add an element at the begining of the dynar (rather long, Use
 469  * xbt_dynar_push() when possible)
 470  */
 471 void
 472 xbt_dynar_unshift(xbt_dynar_t  const dynar,
 473                    const void   * const src) {
 474
 475   /* sanity checks done by insert_at */
 476   xbt_dynar_insert_at(dynar, 0, src);
 477 }
 478
 479 /**
 480  * xbt_dynar_shift:
 481  * @dynar:
 482  * @dst:
 483  *
 484  * Get and remove the first element of the dynar (rather long, Use
 485  * xbt_dynar_pop() when possible)
 486  */
 487 void
 488 xbt_dynar_shift(xbt_dynar_t  const dynar,
 489                  void         * const dst) {
 490
 491   /* sanity checks done by remove_at */
 492   xbt_dynar_remove_at(dynar, 0, dst);
 493 }
 494
 495 /**
 496  * xbt_dynar_map:
 497  * @dynar:
 498  * @operator:
 499  *
 500  * Apply a function to each member of a dynar (this function may change the
 501  * value of the element itself, but should not mess with the dynar).
 502  */
 503 void
 504 xbt_dynar_map(const xbt_dynar_t  dynar,
 505                void_f_pvoid_t     * const operator) {
 506
 507   __sanity_check_dynar(dynar);
 508
 509   {
 510     char         elm[64];
 511     const unsigned long used = dynar->used;
 512     unsigned long       i    = 0;
 513
 514     for (i = 0; i < used; i++) {
 515       _xbt_dynar_get_elm(elm, dynar, i);
 516       operator(elm);
 517     }
 518   }
 519 }
 520
 521 /**
 522  * xbt_dynar_cursor_first:
 523  *
 524  * Put the cursor at the begining of the dynar. (actually, one step before
 525  * the begining, so that you can iterate over the dynar with a for loop).
 526  *
 527  * Dynar cursor are as dumb as possible. If you insert or remove elements
 528  * from the dynar between the creation and end, you'll fuck up your
 529  * cursors.
 530  *
 531  */
 532 void
 533 xbt_dynar_cursor_first(const xbt_dynar_t dynar,
 534                         int        * const cursor) {
 535
 536   DEBUG1("Set cursor on %p to the first position",(void*)dynar);
 537   *cursor = 0;
 538 }
 539
 540 /**
 541  * xbt_dynar_cursor_step:
 542  *
 543  * Move the cursor to the next value (and return true), or return false.
 544  */
 545 void
 546 xbt_dynar_cursor_step(const xbt_dynar_t dynar,
 547                        int        * const cursor) {
 548
 549   (*cursor)++;
 550 }
 551
 552 /**
 553  * xbt_dynar_cursor_get:
 554  *
 555  * Get the current value of the cursor
 556  */
 557 int
 558 xbt_dynar_cursor_get(const xbt_dynar_t dynar,
 559                       int                * const cursor,
 560                       void               * const dst) {
 561
 562   __sanity_check_dynar(dynar);
 563   {
 564
 565     const int idx = *cursor;
 566
 567     if (idx >= dynar->used) {
 568       DEBUG1("Cursor on %p already on last elem",(void*)dynar);
 569       return FALSE;
 570     }
 571     DEBUG2("Cash out cursor on %p at %d",(void*)dynar,idx);
 572
 573     _xbt_dynar_get_elm(dst, dynar, idx);
 574   }
 575   return TRUE;
 576
 577 }
 578
 579 /**
 580  * xbt_dynar_cursor_rm:
 581  * @dynar:
 582  * @cursor:
 583  *
 584  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
 585  */
 586 void xbt_dynar_cursor_rm(xbt_dynar_t dynar,
 587                           int          * const cursor) {
 588   void *dst;
 589
 590   if (dynar->elmsize > sizeof(void*)) {
 591     DEBUG0("Elements too big to fit into a pointer");
 592     if (dynar->free_f) {
 593       dst=xbt_malloc(dynar->elmsize);
 594       xbt_dynar_remove_at(dynar,(*cursor)--,dst);
 595       (dynar->free_f)(dst);
 596       xbt_free(dst);
 597     } else {
 598       DEBUG0("Ok, we dont care about the element without free function");
 599       xbt_dynar_remove_at(dynar,(*cursor)--,NULL);
 600     }
 601
 602   } else {
 603     xbt_dynar_remove_at(dynar,(*cursor)--,&dst);
 604     if (dynar->free_f)
 605       (dynar->free_f)(dst);
 606   }
 607 }