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 GRAS_LOG_NEW_DEFAULT_SUBCATEGORY(dynar,tbx);
  14
  15 struct gras_dynar_s {
  16   size_t          size;
  17   size_t          used;
  18   size_t          elmsize;
  19   void           *data;
  20   void_f_pvoid_t *free;
  21 };
  22
  23 #define __sanity_check_dynar(dynar)       \
  24            gras_assert0(dynar,           \
  25                         "dynar is NULL")
  26 #define __sanity_check_idx(idx)                \
  27            gras_assert1(idx >= 0,             \
  28                         "dynar idx(=%d) < 0", \
  29                         idx)
  30 #define __check_inbound_idx(dynar, idx)                                                \
  31            gras_assert2(idx < dynar->used,                                             \
  32                         "dynar is not that long. You asked %d, but it's only %d long", \
  33                         idx, dynar->used)
  34 #define __check_sloppy_inbound_idx(dynar, idx)                                         \
  35            gras_assert2(idx <= dynar->used,                                            \
  36                         "dynar is not that long. You asked %d, but it's only %d long", \
  37                         idx, dynar->used)
  38 #define __check_populated_dynar(dynar)            \
  39            gras_assert1(dynar->used,              \
  40                         "dynar %p contains nothing",dynar)
  41
  42
  43 static inline
  44 void
  45 _gras_clear_mem(void * const ptr,
  46                 const size_t length) {
  47   memset(ptr, 0, length);
  48 }
  49
  50 static inline
  51 gras_error_t
  52 _gras_dynar_expand(gras_dynar_t * const dynar,
  53                    const int            nb) {
  54   gras_error_t errcode     = no_error;
  55   const size_t old_size    = dynar->size;
  56
  57   if (nb > old_size) {
  58     char * const old_data    = dynar->data;
  59
  60     const size_t elmsize     = dynar->elmsize;
  61     const size_t old_length  = old_size*elmsize;
  62
  63     const size_t used        = dynar->used;
  64     const size_t used_length = used*elmsize;
  65
  66     const size_t new_size    = nb > (2*(old_size+1)) ? nb : (2*(old_size+1));
  67     const size_t new_length  = new_size*elmsize;
  68     char * const new_data    = calloc(1, elmsize*new_size);
  69
  70     DEBUG3("expend %p from %d to %d elements", dynar, old_size, nb);
  71     if (!new_data)
  72       RAISE_MALLOC;
  73
  74     if (old_data) {
  75       memcpy(new_data, old_data, used_length);
  76       _gras_clear_mem(old_data, old_length);
  77       free(old_data);
  78     }
  79
  80     _gras_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 inline
  90 void *
  91 _gras_dynar_elm(const gras_dynar_t * const dynar,
  92                 const size_t               idx) {
  93   char * const data    = dynar->data;
  94   const size_t elmsize = dynar->elmsize;
  95
  96   return data + idx*elmsize;
  97 }
  98
  99 static inline
 100 void
 101 _gras_dynar_get_elm(void               * const dst,
 102                     const gras_dynar_t * const dynar,
 103                     const size_t               idx) {
 104   void * const elm     = _gras_dynar_elm(dynar, idx);
 105   const size_t elmsize = dynar->elmsize;
 106
 107   memcpy(dst, elm, elmsize);
 108 }
 109
 110 static inline
 111 void
 112 _gras_dynar_put_elm(const gras_dynar_t * const dynar,
 113                     const size_t               idx,
 114                     const void         * const src) {
 115   void * const elm     = _gras_dynar_elm(dynar, idx);
 116   const size_t elmsize = dynar->elmsize;
 117
 118   memcpy(elm, src, elmsize);
 119 }
 120
 121 /**
 122  * gras_dynar_new:
 123  * @whereto: pointer to where the dynar should be created
 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  * @Returns: malloc_error or no_error
 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 gras_error_t
 133 gras_dynar_new(gras_dynar_t   ** const p_dynar,
 134                const size_t            elmsize,
 135                void_f_pvoid_t  * const free_func) {
 136   gras_error_t  errcode = no_error;
 137   gras_dynar_t *dynar   = NULL;
 138
 139   if (!(dynar = calloc(1, sizeof(gras_dynar_t))))
 140     RAISE_MALLOC;
 141
 142   dynar->size    = 0;
 143   dynar->used    = 0;
 144   dynar->elmsize = elmsize;
 145   dynar->data    = NULL;
 146   dynar->free    = free_func;
 147
 148   *p_dynar = dynar;
 149
 150   return errcode;
 151 }
 152
 153 /**
 154  * gras_dynar_free_container:
 155  * @dynar: poor victim
 156  *
 157  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but not what
 158  * its contain points to.
 159  */
 160 void
 161 gras_dynar_free_container(gras_dynar_t * const dynar) {
 162   if (dynar) {
 163
 164     if (dynar->data) {
 165       _gras_clear_mem(dynar->data, dynar->size);
 166       free(dynar->data);
 167     }
 168
 169     _gras_clear_mem(dynar, sizeof(gras_dynar_t));
 170
 171     free(dynar);
 172   }
 173 }
 174
 175 /**
 176  * gras_dynar_reset:
 177  * @dynar: who to squeeze
 178  *
 179  * Frees the content and set the size to 0
 180  */
 181 void
 182 gras_dynar_reset(gras_dynar_t * const dynar) {
 183
 184   __sanity_check_dynar(dynar);
 185
 186   DEBUG1("Reset the dynar %p",dynar);
 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   DEBUG1("Pop %p",dynar);
 423   gras_dynar_remove_at(dynar, dynar->used-1, dst);
 424 }
 425
 426 /**
 427  * gras_dynar_unshift:
 428  * @dynar:
 429  * @src:
 430  * @Returns: malloc_error or no_error
 431  *
 432  * Add an element at the begining of the dynar (rather long, Use
 433  * gras_dynar_push() when possible)
 434  */
 435 gras_error_t
 436 gras_dynar_unshift(gras_dynar_t * const dynar,
 437                    const void   * const src) {
 438   __sanity_check_dynar(dynar);
 439   return gras_dynar_insert_at(dynar, 0, src);
 440 }
 441
 442 /**
 443  * gras_dynar_shift:
 444  * @dynar:
 445  * @dst:
 446  *
 447  * Get and remove the first element of the dynar (rather long, Use
 448  * gras_dynar_pop() when possible)
 449  */
 450 void
 451 gras_dynar_shift(gras_dynar_t * const dynar,
 452                  void         * const dst) {
 453
 454   __sanity_check_dynar(dynar);
 455   __check_populated_dynar(dynar);
 456   gras_dynar_remove_at(dynar, 0, dst);
 457 }
 458
 459 /**
 460  * gras_dynar_map:
 461  * @dynar:
 462  * @operator:
 463  *
 464  * Apply a function to each member of a dynar (this function may change the
 465  * value of the element itself, but should not mess with the dynar).
 466  */
 467 void
 468 gras_dynar_map(const gras_dynar_t * const dynar,
 469                void_f_pvoid_t     * const operator) {
 470
 471   __sanity_check_dynar(dynar);
 472
 473   {
 474     char         elm[64];
 475     const size_t used = dynar->used;
 476     size_t       i    = 0;
 477
 478     for (i = 0; i < used; i++) {
 479       _gras_dynar_get_elm(elm, dynar, i);
 480       operator(elm);
 481     }
 482   }
 483 }
 484
 485 /**
 486  * gras_dynar_first:
 487  *
 488  * Put the cursor at the begining of the dynar. (actually, one step before
 489  * the begining, so that you can iterate over the dynar with a for loop).
 490  *
 491  * Dynar cursor are as dumb as possible. If you insert or remove elements
 492  * from the dynar between the creation and end, you'll fuck up your
 493  * cursors.
 494  *
 495  */
 496 void
 497 gras_dynar_cursor_first(const gras_dynar_t * const dynar,
 498                         int                * const cursor) {
 499
 500   __sanity_check_dynar(dynar);
 501   DEBUG1("Set cursor on %p to the first position",dynar);
 502   *cursor = 0;
 503 }
 504
 505 /**
 506  * gras_dynar_cursor_step:
 507  *
 508  * Move the cursor to the next value (and return true), or return false.
 509  */
 510 void
 511 gras_dynar_cursor_step(const gras_dynar_t * const dynar,
 512                        int                * const cursor) {
 513
 514   __sanity_check_dynar(dynar);
 515   (*cursor)++;
 516 }
 517
 518 /**
 519  * gras_dynar_cursor_get:
 520  *
 521  * Get the current value of the cursor
 522  */
 523 int
 524 gras_dynar_cursor_get(const gras_dynar_t * const dynar,
 525                       int                * const cursor,
 526                       void               * const dst) {
 527
 528   __sanity_check_dynar(dynar);
 529   {
 530
 531     const int idx = *cursor;
 532
 533     if (idx >= dynar->used) {
 534       DEBUG1("Cursor on %p already on last elem",dynar);
 535       return FALSE;
 536     }
 537     DEBUG2("Cash out cursor on %p at %d",dynar,idx);
 538
 539     _gras_dynar_get_elm(dst, dynar, idx);
 540   }
 541   return TRUE;
 542
 543 }
 544
 545 /**
 546  * gras_dynar_cursor_rm:
 547  * @dynar:
 548  * @cursor:
 549  *
 550  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
 551  */
 552 void gras_dynar_cursor_rm(gras_dynar_t * dynar,
 553                           int          * const cursor) {
 554   void *dst;
 555
 556   if (dynar->elmsize > sizeof(void*)) {
 557     DEBUG0("Elements too big to fit into a pointer");
 558     if (dynar->free) {
 559       dst=malloc(dynar->elmsize);
 560       gras_dynar_remove_at(dynar,(*cursor)--,dst);
 561       (dynar->free)(dst);
 562       free(dst);
 563     } else {
 564       DEBUG0("Ok, we dont care about the element when no free function");
 565       gras_dynar_remove_at(dynar,(*cursor)--,NULL);
 566     }
 567
 568   } else {
 569     gras_dynar_remove_at(dynar,(*cursor)--,&dst);
 570     if (dynar->free)
 571       (dynar->free)(dst);
 572   }
 573 }