src/xbt/dynar.c

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