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