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 "gras_private.h"
  12
  13
  14 GRAS_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,GRAS);
  15
  16 struct gras_dynar_s {
  17   size_t          size;
  18   size_t          used;
  19   size_t          elmsize;
  20   void           *data;
  21   void_f_pvoid_t *free;
  22 };
  23
  24 #define __sanity_check_dynar(dynar)       \
  25            gras_assert0(dynar,           \
  26                         "dynar is NULL")
  27 #define __sanity_check_idx(idx)                \
  28            gras_assert1(idx >= 0,             \
  29                         "dynar idx(=%d) < 0", \
  30                         idx)
  31 #define __check_inbound_idx(dynar, idx)                                                \
  32            gras_assert2(idx < dynar->used,                                             \
  33                         "dynar is not that long. You asked %d, but it's only %d long", \
  34                         idx, dynar->used)
  35 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
  36            gras_assert2(idx <= dynar->used,                                            \
  37                         "dynar is not that long. You asked %d, but it's only %d long", \
  38                         idx, dynar->used)
  39 #define __check_populated_dynar(dynar)            \
  40            gras_assert0(dynar->used,              \
  41                         "dynar contains nothing")
  42
  43
  44 static inline
  45 void
  46 _gras_clear_mem(void * const ptr,
  47                 const size_t length) {
  48   memset(ptr, 0, length);
  49 }
  50
  51 static inline
  52 gras_error_t
  53 _gras_dynar_expand(gras_dynar_t * const dynar,
  54                    const int            nb) {
  55   gras_error_t errcode     = no_error;
  56   const size_t old_size    = dynar->size;
  57
  58   if (nb > old_size) {
  59     char * const old_data    = dynar->data;
  60
  61     const size_t elmsize     = dynar->elmsize;
  62     const size_t old_length  = old_size*elmsize;
  63
  64     const size_t used        = dynar->used;
  65     const size_t used_length = used*elmsize;
  66
  67     const size_t new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
  68     const size_t new_length  = new_size*elmsize;
  69     char * const new_data    = calloc(1, elmsize*new_size);
  70
  71     DEBUG3("expend %p from %d to %d elements", dynar, old_size, nb);
  72     if (!new_data)
  73       RAISE_MALLOC;
  74
  75     if (old_data) {
  76       memcpy(new_data, old_data, used_length);
  77       _gras_clear_mem(old_data, old_length);
  78       free(old_data);
  79     }
  80
  81     _gras_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 inline
  91 void *
  92 _gras_dynar_elm(const gras_dynar_t * const dynar,
  93                 const size_t               idx) {
  94   char * const data    = dynar->data;
  95   const size_t elmsize = dynar->elmsize;
  96
  97   return data + idx*elmsize;
  98 }
  99
 100 static inline
 101 void
 102 _gras_dynar_get_elm(void               * const dst,
 103                     const gras_dynar_t * const dynar,
 104                     const size_t               idx) {
 105   void * const elm     = _gras_dynar_elm(dynar, idx);
 106   const size_t elmsize = dynar->elmsize;
 107
 108   memcpy(dst, elm, elmsize);
 109 }
 110
 111 static inline
 112 void
 113 _gras_dynar_put_elm(const gras_dynar_t * const dynar,
 114                     const size_t               idx,
 115                     const void         * const src) {
 116   void * const elm     = _gras_dynar_elm(dynar, idx);
 117   const size_t elmsize = dynar->elmsize;
 118
 119   memcpy(elm, src, elmsize);
 120 }
 121
 122 /**
 123  * gras_dynar_new:
 124  * @whereto: pointer to where the dynar should be created
 125  * @elm_size: size of each element in the dynar
 126  * @free_func: function to call each time we want to get rid of an element (or NULL if nothing to do).
 127  * @Returns: malloc_error or no_error
 128  *
 129  * Creates a new dynar. If a free_func is provided, the elements have to be
 130  * pointer of pointer. That is to say that dynars can contain either base
 131  * types (int, char, double, etc) or pointer of pointers (struct **).
 132  */
 133 gras_error_t
 134 gras_dynar_new(gras_dynar_t   ** const p_dynar,
 135                const size_t            elmsize,
 136                void_f_pvoid_t  * const free_func) {
 137   gras_error_t  errcode = no_error;
 138   gras_dynar_t *dynar   = NULL;
 139
 140   if (!(dynar = calloc(1, sizeof(gras_dynar_t))))
 141     RAISE_MALLOC;
 142
 143   dynar->size    = 0;
 144   dynar->used    = 0;
 145   dynar->elmsize = elmsize;
 146   dynar->data    = NULL;
 147   dynar->free    = free_func;
 148
 149   *p_dynar = dynar;
 150
 151   return errcode;
 152 }
 153
 154 /**
 155  * gras_dynar_free_container:
 156  * @dynar: poor victim
 157  *
 158  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
 159  * its contain points to.
 160  */
 161 void
 162 gras_dynar_free_container(gras_dynar_t * const dynar) {
 163   if (dynar) {
 164
 165     if (dynar->data) {
 166       _gras_clear_mem(dynar->data, dynar->size);
 167       free(dynar->data);
 168     }
 169
 170     _gras_clear_mem(dynar, sizeof(gras_dynar_t));
 171
 172     free(dynar);
 173   }
 174 }
 175
 176 /**
 177  * gras_dynar_reset:
 178  * @dynar: who to squeeze
 179  *
 180  * Frees the content and set the size to 0
 181  */
 182 void
 183 gras_dynar_reset(gras_dynar_t * const dynar) {
 184
 185   __sanity_check_dynar(dynar);
 186
 187   if (dynar->free) {
 188     gras_dynar_map(dynar, dynar->free);
 189   }
 190
 191   if (dynar->data) {
 192     _gras_clear_mem(dynar->data, dynar->size);
 193     free(dynar->data);
 194   }
 195
 196   dynar->size = 0;
 197   dynar->used = 0;
 198   dynar->data = NULL;
 199 }
 200
 201 /**
 202  * gras_dynar_free:
 203  * @dynar: poor victim
 204  *
 205  * kilkil a dynar and its content
 206  */
 207
 208 void
 209 gras_dynar_free(gras_dynar_t * const dynar) {
 210   if (dynar) {
 211     gras_dynar_reset(dynar);
 212     gras_dynar_free_container(dynar);
 213   }
 214 }
 215
 216 /**
 217  * gras_dynar_length:
 218  * @dynar: the dynar we want to mesure
 219  *
 220  * Returns the count of elements in a dynar
 221  */
 222 size_t
 223 gras_dynar_length(const gras_dynar_t * const dynar) {
 224   return (dynar ? dynar->used : (size_t)0);
 225 }
 226
 227 /**
 228  * gras_dynar_get:
 229  * @dynar: information dealer
 230  * @idx: index of the slot we want to retrive
 231  * @dst: where to pu the result to.
 232  *
 233  * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of
 234  * the dynar. Make a copy before fooling with it.
 235  */
 236 void
 237 gras_dynar_get(const gras_dynar_t * const dynar,
 238                const int                  idx,
 239                void               * const dst) {
 240
 241   __sanity_check_dynar(dynar);
 242   __sanity_check_idx(idx);
 243   __check_inbound_idx(dynar, idx);
 244
 245   _gras_dynar_get_elm(dst, dynar, idx);
 246 }
 247
 248 /**
 249  * gras_dynar_set:
 250  * @dynar:
 251  * @idx:
 252  * @src: What will be feeded to the dynar
 253  * @Returns: malloc_error or no_error
 254  *
 255  * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
 256  * the previous value at this position. If you want to free the previous content,
 257  * use gras_dynar_remplace().
 258  */
 259 gras_error_t
 260 gras_dynar_set(gras_dynar_t * const dynar,
 261                const int            idx,
 262                const void   * const src) {
 263   gras_error_t errcode = no_error;
 264
 265   __sanity_check_dynar(dynar);
 266   __sanity_check_idx(idx);
 267
 268   TRY(_gras_dynar_expand(dynar, idx+1));
 269
 270   if (idx >= dynar->used) {
 271     dynar->used = idx+1;
 272   }
 273
 274   _gras_dynar_put_elm(dynar, idx, src);
 275
 276   return errcode;
 277 }
 278
 279 /**
 280  * gras_dynar_remplace:
 281  * @dynar:
 282  * @idx:
 283  * @object:
 284  * @Returns: malloc_error or no_error
 285  *
 286  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 287  * free the previous value at this position. If you don't want to free the
 288  * previous content, use gras_dynar_set().
 289  */
 290 gras_error_t
 291 gras_dynar_remplace(gras_dynar_t * const dynar,
 292                     const int            idx,
 293                     const void   * const object) {
 294   gras_error_t errcode = no_error;
 295
 296   __sanity_check_dynar(dynar);
 297   __sanity_check_idx(idx);
 298
 299   if (idx < dynar->used && dynar->free) {
 300     void * const old_object = _gras_dynar_elm(dynar, idx);
 301
 302     dynar->free(old_object);
 303   }
 304
 305   errcode = gras_dynar_set(dynar, idx, object);
 306
 307   return errcode;
 308 }
 309
 310 /**
 311  * gras_dynar_insert_at:
 312  * @dynar:
 313  * @idx:
 314  * @src: What will be feeded to the dynar
 315  * @Returns: malloc_error or no_error
 316  *
 317  * Set the Nth element of a dynar, expanding the dynar if needed, and
 318  * moving the previously existing value and all subsequent ones to one
 319  * position right in the dynar.
 320  */
 321 gras_error_t
 322 gras_dynar_insert_at(gras_dynar_t * const dynar,
 323                      const int            idx,
 324                      const void   * const src) {
 325   gras_error_t errcode = no_error;
 326
 327   __sanity_check_dynar(dynar);
 328   __sanity_check_idx(idx);
 329   __check_sloppy_inbound_idx(dynar, idx);
 330
 331   {
 332     const size_t old_used = dynar->used;
 333     const size_t new_used = old_used + 1;
 334
 335     TRY(_gras_dynar_expand(dynar, new_used));
 336
 337     {
 338       const size_t nb_shift =  old_used - idx;
 339       const size_t elmsize  =  dynar->elmsize;
 340
 341       const size_t offset   =  nb_shift*elmsize;
 342
 343       void * const elm_src  = _gras_dynar_elm(dynar, idx);
 344       void * const elm_dst  = _gras_dynar_elm(dynar, idx+1);
 345
 346       memmove(elm_dst, elm_src, offset);
 347     }
 348
 349     _gras_dynar_put_elm(dynar, idx, src);
 350     dynar->used = new_used;
 351   }
 352
 353   return errcode;
 354 }
 355
 356 /**
 357  * gras_dynar_remove_at:
 358  * @dynar:
 359  * @idx:
 360  * @object:
 361  *
 362  * Get the Nth element of a dynar, removing it from the dynar and moving
 363  * all subsequent values to one position left in the dynar.
 364  */
 365 void
 366 gras_dynar_remove_at(gras_dynar_t * const dynar,
 367                      const int            idx,
 368                      void         * const object) {
 369
 370   __sanity_check_dynar(dynar);
 371   __sanity_check_idx(idx);
 372   __check_inbound_idx(dynar, idx);
 373
 374   if (object)
 375     _gras_dynar_get_elm(object, dynar, idx);
 376
 377   {
 378     const size_t old_used = dynar->used;
 379     const size_t new_used = old_used - 1;
 380
 381     const size_t nb_shift =  old_used-1 - idx;
 382     const size_t elmsize  =  dynar->elmsize;
 383
 384     const size_t offset   =  nb_shift*elmsize;
 385
 386     void * const elm_src  = _gras_dynar_elm(dynar, idx+1);
 387     void * const elm_dst  = _gras_dynar_elm(dynar, idx);
 388
 389     memmove(elm_dst, elm_src, offset);
 390
 391     dynar->used = new_used;
 392   }
 393 }
 394
 395 /**
 396  * gras_dynar_push:
 397  * @dynar:
 398  * @src:
 399  * @Returns: malloc_error or no_error
 400  *
 401  * Add an element at the end of the dynar
 402  */
 403 gras_error_t
 404 gras_dynar_push(gras_dynar_t * const dynar,
 405                 const void   * const src) {
 406   __sanity_check_dynar(dynar);
 407   return gras_dynar_insert_at(dynar, dynar->used, src);
 408 }
 409
 410 /**
 411  * gras_dynar_pop:
 412  * @dynar:
 413  * @dst:
 414  *
 415  * Get and remove the last element of the dynar
 416  */
 417 void
 418 gras_dynar_pop(gras_dynar_t * const dynar,
 419                void         * const dst) {
 420   __sanity_check_dynar(dynar);
 421   __check_populated_dynar(dynar);
 422   gras_dynar_remove_at(dynar, dynar->used-1, dst);
 423 }
 424
 425 /**
 426  * gras_dynar_unshift:
 427  * @dynar:
 428  * @src:
 429  * @Returns: malloc_error or no_error
 430  *
 431  * Add an element at the begining of the dynar (rather long, Use
 432  * gras_dynar_push() when possible)
 433  */
 434 gras_error_t
 435 gras_dynar_unshift(gras_dynar_t * const dynar,
 436                    const void   * const src) {
 437   __sanity_check_dynar(dynar);
 438   return gras_dynar_insert_at(dynar, 0, src);
 439 }
 440
 441 /**
 442  * gras_dynar_shift:
 443  * @dynar:
 444  * @dst:
 445  *
 446  * Get and remove the first element of the dynar (rather long, Use
 447  * gras_dynar_pop() when possible)
 448  */
 449 void
 450 gras_dynar_shift(gras_dynar_t * const dynar,
 451                  void         * const dst) {
 452
 453   __sanity_check_dynar(dynar);
 454   __check_populated_dynar(dynar);
 455   gras_dynar_remove_at(dynar, 0, dst);
 456 }
 457
 458 /**
 459  * gras_dynar_map:
 460  * @dynar:
 461  * @operator:
 462  *
 463  * Apply a function to each member of a dynar (this function may change the
 464  * value of the element itself, but should not mess with the dynar).
 465  */
 466 void
 467 gras_dynar_map(const gras_dynar_t * const dynar,
 468                void_f_pvoid_t     * const operator) {
 469
 470   __sanity_check_dynar(dynar);
 471
 472   {
 473     char         elm[64];
 474     const size_t used = dynar->used;
 475     size_t       i    = 0;
 476
 477     for (i = 0; i < used; i++) {
 478       _gras_dynar_get_elm(elm, dynar, i);
 479       operator(elm);
 480     }
 481   }
 482 }
 483
 484 /**
 485  * gras_dynar_first:
 486  *
 487  * Put the cursor at the begining of the dynar. (actually, one step before
 488  * the begining, so that you can iterate over the dynar with a for loop).
 489  *
 490  * Dynar cursor are as dumb as possible. If you insert or remove elements
 491  * from the dynar between the creation and end, you'll fuck up your
 492  * cursors.
 493  *
 494  */
 495 void
 496 gras_dynar_cursor_first(const gras_dynar_t * const dynar,
 497                         int                * const cursor) {
 498
 499   __sanity_check_dynar(dynar);
 500   DEBUG1("Set cursor on %p to the first position",dynar);
 501   *cursor = 0;
 502 }
 503
 504 /**
 505  * gras_dynar_cursor_step:
 506  *
 507  * Move the cursor to the next value (and return true), or return false.
 508  */
 509 void
 510 gras_dynar_cursor_step(const gras_dynar_t * const dynar,
 511                        int                * const cursor) {
 512
 513   __sanity_check_dynar(dynar);
 514   (*cursor)++;
 515 }
 516
 517 /**
 518  * gras_dynar_cursor_get:
 519  *
 520  * Get the current value of the cursor
 521  */
 522 int
 523 gras_dynar_cursor_get(const gras_dynar_t * const dynar,
 524                       int                * const cursor,
 525                       void               * const dst) {
 526
 527   __sanity_check_dynar(dynar);
 528   {
 529
 530     const int idx = *cursor;
 531
 532     if (idx >= dynar->used) {
 533       DEBUG1("Cursor on %p already on last elem",dynar);
 534       return FALSE;
 535     }
 536     DEBUG2("Cash out cursor on %p at %d",dynar,idx);
 537
 538     _gras_dynar_get_elm(dst, dynar, idx);
 539   }
 540   return TRUE;
 541
 542 }
 543
 544 /**
 545  * gras_dynar_cursor_rm:
 546  * @dynar:
 547  * @cursor:
 548  *
 549  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
 550  */
 551 void gras_dynar_cursor_rm(gras_dynar_t * dynar,
 552                           int          * const cursor) {
 553   void *dst;
 554
 555   gras_dynar_remove_at(dynar,(*cursor)--,&dst);
 556   if (dynar->free)
 557     (dynar->free)(dst);
 558 }