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_assert0(dynar->used,              \
  40                         "dynar contains nothing")
  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   if (dynar->free) {
 187     gras_dynar_map(dynar, dynar->free);
 188   }
 189
 190   if (dynar->data) {
 191     _gras_clear_mem(dynar->data, dynar->size);
 192     free(dynar->data);
 193   }
 194
 195   dynar->size = 0;
 196   dynar->used = 0;
 197   dynar->data = NULL;
 198 }
 199
 200 /**
 201  * gras_dynar_free:
 202  * @dynar: poor victim
 203  *
 204  * kilkil a dynar and its content
 205  */
 206
 207 void
 208 gras_dynar_free(gras_dynar_t * const dynar) {
 209   if (dynar) {
 210     gras_dynar_reset(dynar);
 211     gras_dynar_free_container(dynar);
 212   }
 213 }
 214
 215 /**
 216  * gras_dynar_length:
 217  * @dynar: the dynar we want to mesure
 218  *
 219  * Returns the count of elements in a dynar
 220  */
 221 size_t
 222 gras_dynar_length(const gras_dynar_t * const dynar) {
 223   return (dynar ? dynar->used : (size_t)0);
 224 }
 225
 226 /**
 227  * gras_dynar_get:
 228  * @dynar: information dealer
 229  * @idx: index of the slot we want to retrive
 230  * @dst: where to pu the result to.
 231  *
 232  * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of
 233  * the dynar. Make a copy before fooling with it.
 234  */
 235 void
 236 gras_dynar_get(const gras_dynar_t * const dynar,
 237                const int                  idx,
 238                void               * const dst) {
 239
 240   __sanity_check_dynar(dynar);
 241   __sanity_check_idx(idx);
 242   __check_inbound_idx(dynar, idx);
 243
 244   _gras_dynar_get_elm(dst, dynar, idx);
 245 }
 246
 247 /**
 248  * gras_dynar_set:
 249  * @dynar:
 250  * @idx:
 251  * @src: What will be feeded to the dynar
 252  * @Returns: malloc_error or no_error
 253  *
 254  * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
 255  * the previous value at this position. If you want to free the previous content,
 256  * use gras_dynar_remplace().
 257  */
 258 gras_error_t
 259 gras_dynar_set(gras_dynar_t * const dynar,
 260                const int            idx,
 261                const void   * const src) {
 262   gras_error_t errcode = no_error;
 263
 264   __sanity_check_dynar(dynar);
 265   __sanity_check_idx(idx);
 266
 267   TRY(_gras_dynar_expand(dynar, idx+1));
 268
 269   if (idx >= dynar->used) {
 270     dynar->used = idx+1;
 271   }
 272
 273   _gras_dynar_put_elm(dynar, idx, src);
 274
 275   return errcode;
 276 }
 277
 278 /**
 279  * gras_dynar_remplace:
 280  * @dynar:
 281  * @idx:
 282  * @object:
 283  * @Returns: malloc_error or no_error
 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 gras_dynar_set().
 288  */
 289 gras_error_t
 290 gras_dynar_remplace(gras_dynar_t * const dynar,
 291                     const int            idx,
 292                     const void   * const object) {
 293   gras_error_t errcode = no_error;
 294
 295   __sanity_check_dynar(dynar);
 296   __sanity_check_idx(idx);
 297
 298   if (idx < dynar->used && dynar->free) {
 299     void * const old_object = _gras_dynar_elm(dynar, idx);
 300
 301     dynar->free(old_object);
 302   }
 303
 304   errcode = gras_dynar_set(dynar, idx, object);
 305
 306   return errcode;
 307 }
 308
 309 /**
 310  * gras_dynar_insert_at:
 311  * @dynar:
 312  * @idx:
 313  * @src: What will be feeded to the dynar
 314  * @Returns: malloc_error or no_error
 315  *
 316  * Set the Nth element of a dynar, expanding the dynar if needed, and
 317  * moving the previously existing value and all subsequent ones to one
 318  * position right in the dynar.
 319  */
 320 gras_error_t
 321 gras_dynar_insert_at(gras_dynar_t * const dynar,
 322                      const int            idx,
 323                      const void   * const src) {
 324   gras_error_t errcode = no_error;
 325
 326   __sanity_check_dynar(dynar);
 327   __sanity_check_idx(idx);
 328   __check_sloppy_inbound_idx(dynar, idx);
 329
 330   {
 331     const size_t old_used = dynar->used;
 332     const size_t new_used = old_used + 1;
 333
 334     TRY(_gras_dynar_expand(dynar, new_used));
 335
 336     {
 337       const size_t nb_shift =  old_used - idx;
 338       const size_t elmsize  =  dynar->elmsize;
 339
 340       const size_t offset   =  nb_shift*elmsize;
 341
 342       void * const elm_src  = _gras_dynar_elm(dynar, idx);
 343       void * const elm_dst  = _gras_dynar_elm(dynar, idx+1);
 344
 345       memmove(elm_dst, elm_src, offset);
 346     }
 347
 348     _gras_dynar_put_elm(dynar, idx, src);
 349     dynar->used = new_used;
 350   }
 351
 352   return errcode;
 353 }
 354
 355 /**
 356  * gras_dynar_remove_at:
 357  * @dynar:
 358  * @idx:
 359  * @object:
 360  *
 361  * Get the Nth element of a dynar, removing it from the dynar and moving
 362  * all subsequent values to one position left in the dynar.
 363  */
 364 void
 365 gras_dynar_remove_at(gras_dynar_t * const dynar,
 366                      const int            idx,
 367                      void         * const object) {
 368
 369   __sanity_check_dynar(dynar);
 370   __sanity_check_idx(idx);
 371   __check_inbound_idx(dynar, idx);
 372
 373   if (object)
 374     _gras_dynar_get_elm(object, dynar, idx);
 375
 376   {
 377     const size_t old_used = dynar->used;
 378     const size_t new_used = old_used - 1;
 379
 380     const size_t nb_shift =  old_used-1 - idx;
 381     const size_t elmsize  =  dynar->elmsize;
 382
 383     const size_t offset   =  nb_shift*elmsize;
 384
 385     void * const elm_src  = _gras_dynar_elm(dynar, idx+1);
 386     void * const elm_dst  = _gras_dynar_elm(dynar, idx);
 387
 388     memmove(elm_dst, elm_src, offset);
 389
 390     dynar->used = new_used;
 391   }
 392 }
 393
 394 /**
 395  * gras_dynar_push:
 396  * @dynar:
 397  * @src:
 398  * @Returns: malloc_error or no_error
 399  *
 400  * Add an element at the end of the dynar
 401  */
 402 gras_error_t
 403 gras_dynar_push(gras_dynar_t * const dynar,
 404                 const void   * const src) {
 405   __sanity_check_dynar(dynar);
 406   return gras_dynar_insert_at(dynar, dynar->used, src);
 407 }
 408
 409 /**
 410  * gras_dynar_pop:
 411  * @dynar:
 412  * @dst:
 413  *
 414  * Get and remove the last element of the dynar
 415  */
 416 void
 417 gras_dynar_pop(gras_dynar_t * const dynar,
 418                void         * const dst) {
 419   __sanity_check_dynar(dynar);
 420   __check_populated_dynar(dynar);
 421   gras_dynar_remove_at(dynar, dynar->used-1, dst);
 422 }
 423
 424 /**
 425  * gras_dynar_unshift:
 426  * @dynar:
 427  * @src:
 428  * @Returns: malloc_error or no_error
 429  *
 430  * Add an element at the begining of the dynar (rather long, Use
 431  * gras_dynar_push() when possible)
 432  */
 433 gras_error_t
 434 gras_dynar_unshift(gras_dynar_t * const dynar,
 435                    const void   * const src) {
 436   __sanity_check_dynar(dynar);
 437   return gras_dynar_insert_at(dynar, 0, src);
 438 }
 439
 440 /**
 441  * gras_dynar_shift:
 442  * @dynar:
 443  * @dst:
 444  *
 445  * Get and remove the first element of the dynar (rather long, Use
 446  * gras_dynar_pop() when possible)
 447  */
 448 void
 449 gras_dynar_shift(gras_dynar_t * const dynar,
 450                  void         * const dst) {
 451
 452   __sanity_check_dynar(dynar);
 453   __check_populated_dynar(dynar);
 454   gras_dynar_remove_at(dynar, 0, dst);
 455 }
 456
 457 /**
 458  * gras_dynar_map:
 459  * @dynar:
 460  * @operator:
 461  *
 462  * Apply a function to each member of a dynar (this function may change the
 463  * value of the element itself, but should not mess with the dynar).
 464  */
 465 void
 466 gras_dynar_map(const gras_dynar_t * const dynar,
 467                void_f_pvoid_t     * const operator) {
 468
 469   __sanity_check_dynar(dynar);
 470
 471   {
 472     char         elm[64];
 473     const size_t used = dynar->used;
 474     size_t       i    = 0;
 475
 476     for (i = 0; i < used; i++) {
 477       _gras_dynar_get_elm(elm, dynar, i);
 478       operator(elm);
 479     }
 480   }
 481 }
 482
 483 /**
 484  * gras_dynar_first:
 485  *
 486  * Put the cursor at the begining of the dynar. (actually, one step before
 487  * the begining, so that you can iterate over the dynar with a for loop).
 488  *
 489  * Dynar cursor are as dumb as possible. If you insert or remove elements
 490  * from the dynar between the creation and end, you'll fuck up your
 491  * cursors.
 492  *
 493  */
 494 void
 495 gras_dynar_cursor_first(const gras_dynar_t * const dynar,
 496                         int                * const cursor) {
 497
 498   __sanity_check_dynar(dynar);
 499   DEBUG1("Set cursor on %p to the first position",dynar);
 500   *cursor = 0;
 501 }
 502
 503 /**
 504  * gras_dynar_cursor_step:
 505  *
 506  * Move the cursor to the next value (and return true), or return false.
 507  */
 508 void
 509 gras_dynar_cursor_step(const gras_dynar_t * const dynar,
 510                        int                * const cursor) {
 511
 512   __sanity_check_dynar(dynar);
 513   (*cursor)++;
 514 }
 515
 516 /**
 517  * gras_dynar_cursor_get:
 518  *
 519  * Get the current value of the cursor
 520  */
 521 int
 522 gras_dynar_cursor_get(const gras_dynar_t * const dynar,
 523                       int                * const cursor,
 524                       void               * const dst) {
 525
 526   __sanity_check_dynar(dynar);
 527   {
 528
 529     const int idx = *cursor;
 530
 531     if (idx >= dynar->used) {
 532       DEBUG1("Cursor on %p already on last elem",dynar);
 533       return FALSE;
 534     }
 535     DEBUG2("Cash out cursor on %p at %d",dynar,idx);
 536
 537     _gras_dynar_get_elm(dst, dynar, idx);
 538   }
 539   return TRUE;
 540
 541 }
 542
 543 /**
 544  * gras_dynar_cursor_rm:
 545  * @dynar:
 546  * @cursor:
 547  *
 548  * Remove (free) the entry pointed by the cursor, for use in the middle of a foreach
 549  */
 550 void gras_dynar_cursor_rm(gras_dynar_t * dynar,
 551                           int          * const cursor) {
 552   void *dst;
 553
 554   gras_dynar_remove_at(dynar,(*cursor)--,&dst);
 555   if (dynar->free)
 556     (dynar->free)(dst);
 557 }