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