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_cpy:
 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 a copy of the Nth element of a dynar.
 227  */
 228 void
 229 gras_dynar_get_cpy(const gras_dynar_t * const dynar,
 230                    const int                  idx,
 231                    void               * const dst) {
 232
 233   __sanity_check_dynar(dynar);
 234   __sanity_check_idx(idx);
 235   __check_inbound_idx(dynar, idx);
 236
 237   _gras_dynar_get_elm(dst, dynar, idx);
 238 }
 239
 240 /**
 241  * gras_dynar_get:
 242  * @dynar: information dealer
 243  * @idx: index of the slot we want to retrive
 244  * @dst: where to pu the result to.
 245  *
 246  * Retrieve the Nth element of a dynar. Warning, the returned value is the actual content of
 247  * the dynar. Make a copy before fooling with it.
 248  */
 249 void*
 250 gras_dynar_get_ptr(const gras_dynar_t * const dynar,
 251                    const int                  idx) {
 252
 253   __sanity_check_dynar(dynar);
 254   __sanity_check_idx(idx);
 255   __check_inbound_idx(dynar, idx);
 256
 257   return _gras_dynar_elm(dynar, idx);
 258 }
 259
 260 /**
 261  * gras_dynar_set:
 262  * @dynar:
 263  * @idx:
 264  * @src: What will be feeded to the dynar
 265  *
 266  * Set the Nth element of a dynar, expanding the dynar if needed, BUT NOT freeing
 267  * the previous value at this position. If you want to free the previous content,
 268  * use gras_dynar_replace().
 269  */
 270 void
 271 gras_dynar_set(gras_dynar_t * const dynar,
 272                const int            idx,
 273                const void   * const src) {
 274
 275   __sanity_check_dynar(dynar);
 276   __sanity_check_idx(idx);
 277
 278   _gras_dynar_expand(dynar, idx+1);
 279
 280   if (idx >= dynar->used) {
 281     dynar->used = idx+1;
 282   }
 283
 284   _gras_dynar_put_elm(dynar, idx, src);
 285 }
 286
 287 /**
 288  * gras_dynar_remplace:
 289  * @dynar:
 290  * @idx:
 291  * @object:
 292  *
 293  * Set the Nth element of a dynar, expanding the dynar if needed, AND DO
 294  * free the previous value at this position. If you don't want to free the
 295  * previous content, use gras_dynar_set().
 296  */
 297 void
 298 gras_dynar_remplace(gras_dynar_t * const dynar,
 299                     const int            idx,
 300                     const void   * const object) {
 301
 302   __sanity_check_dynar(dynar);
 303   __sanity_check_idx(idx);
 304
 305   if (idx < dynar->used && dynar->free) {
 306     void * const old_object = _gras_dynar_elm(dynar, idx);
 307
 308     dynar->free(old_object);
 309   }
 310
 311   gras_dynar_set(dynar, idx, object);
 312 }
 313
 314 /**
 315  * gras_dynar_insert_at:
 316  * @dynar:
 317  * @idx:
 318  * @src: What will be feeded to the dynar
 319  *
 320  * Set the Nth element of a dynar, expanding the dynar if needed, and
 321  * moving the previously existing value and all subsequent ones to one
 322  * position right in the dynar.
 323  */
 324 void
 325 gras_dynar_insert_at(gras_dynar_t * const dynar,
 326                      const int            idx,
 327                      const void   * const src) {
 328
 329   __sanity_check_dynar(dynar);
 330   __sanity_check_idx(idx);
 331   __check_sloppy_inbound_idx(dynar, idx);
 332
 333   {
 334     const unsigned long old_used = dynar->used;
 335     const unsigned long new_used = old_used + 1;
 336
 337     _gras_dynar_expand(dynar, new_used);
 338
 339     {
 340       const unsigned long nb_shift =  old_used - idx;
 341       const unsigned long elmsize  =  dynar->elmsize;
 342
 343       const unsigned long offset   =  nb_shift*elmsize;
 344
 345       void * const elm_src  = _gras_dynar_elm(dynar, idx);
 346       void * const elm_dst  = _gras_dynar_elm(dynar, idx+1);
 347
 348       memmove(elm_dst, elm_src, offset);
 349     }
 350
 351     _gras_dynar_put_elm(dynar, idx, src);
 352     dynar->used = new_used;
 353   }
 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 unsigned long old_used = dynar->used;
 379     const unsigned long new_used = old_used - 1;
 380
 381     const unsigned long nb_shift =  old_used-1 - idx;
 382     const unsigned long elmsize  =  dynar->elmsize;
 383
 384     const unsigned long 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  *
 400  * Add an element at the end of the dynar
 401  */
 402 void
 403 gras_dynar_push(gras_dynar_t * const dynar,
 404                 const void   * const src) {
 405   __sanity_check_dynar(dynar);
 406   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   DEBUG1("Pop %p",(void*)dynar);
 422   gras_dynar_remove_at(dynar, dynar->used-1, dst);
 423 }
 424
 425 /**
 426  * gras_dynar_unshift:
 427  * @dynar:
 428  * @src:
 429  *
 430  * Add an element at the begining of the dynar (rather long, Use
 431  * gras_dynar_push() when possible)
 432  */
 433 void
 434 gras_dynar_unshift(gras_dynar_t * const dynar,
 435                    const void   * const src) {
 436   __sanity_check_dynar(dynar);
 437   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 unsigned long used = dynar->used;
 474     unsigned long       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",(void*)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",(void*)dynar);
 533       return FALSE;
 534     }
 535     DEBUG2("Cash out cursor on %p at %d",(void*)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   if (dynar->elmsize > sizeof(void*)) {
 555     DEBUG0("Elements too big to fit into a pointer");
 556     if (dynar->free) {
 557       dst=gras_malloc(dynar->elmsize);
 558       gras_dynar_remove_at(dynar,(*cursor)--,dst);
 559       (dynar->free)(dst);
 560       gras_free(dst);
 561     } else {
 562       DEBUG0("Ok, we dont care about the element when no free function");
 563       gras_dynar_remove_at(dynar,(*cursor)--,NULL);
 564     }
 565
 566   } else {
 567     gras_dynar_remove_at(dynar,(*cursor)--,&dst);
 568     if (dynar->free)
 569       (dynar->free)(dst);
 570   }
 571 }