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