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