src/xbt/dynar.cpp

   1 /* a generic DYNamic ARray implementation.                                  */
   2
   3 /* Copyright (c) 2004-2020. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/dynar.h"
  10 #include "simgrid/Exception.hpp"
  11 #include "xbt/ex.h"
  12 #include "xbt/log.h"
  13 #include "xbt/misc.h"
  14 #include "xbt/string.hpp"
  15 #include "xbt/sysdep.h"
  16 #include <sys/types.h>
  17
  18 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dyn, xbt, "Dynamic arrays");
  19
  20 static inline void _sanity_check_dynar(const_xbt_dynar_t dynar)
  21 {
  22   xbt_assert(dynar, "dynar is nullptr");
  23 }
  24
  25 static inline void _sanity_check_idx(int idx)
  26 {
  27   xbt_assert(idx >= 0, "dynar idx(=%d) < 0", idx);
  28 }
  29
  30 static inline void _check_inbound_idx(const_xbt_dynar_t dynar, int idx)
  31 {
  32   xbt_assert(idx >= 0 && idx < static_cast<int>(dynar->used),
  33              "dynar is not that long. You asked %d, but it's only %lu long", idx, dynar->used);
  34 }
  35
  36 static inline void _check_populated_dynar(const_xbt_dynar_t dynar)
  37 {
  38   xbt_assert(dynar->used > 0, "dynar %p is empty", dynar);
  39 }
  40
  41 static inline void _xbt_dynar_resize(xbt_dynar_t dynar, unsigned long new_size)
  42 {
  43   if (new_size != dynar->size) {
  44     dynar->size = new_size;
  45     dynar->data = xbt_realloc(dynar->data, new_size * dynar->elmsize);
  46   }
  47 }
  48
  49 static inline void _xbt_dynar_expand(xbt_dynar_t dynar, unsigned long nb)
  50 {
  51   const unsigned long old_size = dynar->size;
  52
  53   if (nb > old_size) {
  54     const unsigned long expand = 2 * (old_size + 1);
  55     _xbt_dynar_resize(dynar, (nb > expand ? nb : expand));
  56     XBT_DEBUG("expand %p from %lu to %lu elements", dynar, old_size, dynar->size);
  57   }
  58 }
  59
  60 static inline void* _xbt_dynar_elm(const_xbt_dynar_t dynar, unsigned long idx)
  61 {
  62   char *const data = (char *) dynar->data;
  63   const unsigned long elmsize = dynar->elmsize;
  64
  65   return data + idx * elmsize;
  66 }
  67
  68 static inline void _xbt_dynar_get_elm(void* dst, const_xbt_dynar_t dynar, unsigned long idx)
  69 {
  70   const void* const elm = _xbt_dynar_elm(dynar, idx);
  71   memcpy(dst, elm, dynar->elmsize);
  72 }
  73
  74 /** @brief Constructor
  75  *
  76  * @param elmsize size of each element in the dynar
  77  * @param free_f function to call each time we want to get rid of an element (or nullptr if nothing to do).
  78  *
  79  * Creates a new dynar. If a free_func is provided, the elements have to be pointer of pointer. That is to say that
  80  * dynars can contain either base types (int, char, double, etc) or pointer of pointers (struct **).
  81  */
  82 xbt_dynar_t xbt_dynar_new(const unsigned long elmsize, void_f_pvoid_t free_f)
  83 {
  84   xbt_dynar_t dynar = xbt_new0(s_xbt_dynar_t, 1);
  85
  86   dynar->size = 0;
  87   dynar->used = 0;
  88   dynar->elmsize = elmsize;
  89   dynar->data = nullptr;
  90   dynar->free_f = free_f;
  91
  92   return dynar;
  93 }
  94
  95 /** @brief Destructor of the structure not touching to the content
  96  *
  97  * @param dynar poor victim
  98  *
  99  * kilkil a dynar BUT NOT its content. Ie, the array is freed, but the content is not touched (the @a free_f function
 100  * is not used)
 101  */
 102 void xbt_dynar_free_container(xbt_dynar_t* dynar)
 103 {
 104   if (dynar && *dynar) {
 105     xbt_dynar_t d = *dynar;
 106     xbt_free(d->data);
 107     xbt_free(d);
 108     *dynar = nullptr;
 109   }
 110 }
 111
 112 /** @brief Frees the content and set the size to 0
 113  *
 114  * @param dynar who to squeeze
 115  */
 116 void xbt_dynar_reset(xbt_dynar_t dynar)
 117 {
 118   _sanity_check_dynar(dynar);
 119
 120   XBT_CDEBUG(xbt_dyn, "Reset the dynar %p", (void *) dynar);
 121   if (dynar->free_f) {
 122     xbt_dynar_map(dynar, dynar->free_f);
 123   }
 124   dynar->used = 0;
 125 }
 126
 127 /**
 128  * @brief Shrink the dynar by removing empty slots at the end of the internal array
 129  * @param dynar a dynar
 130  * @param empty_slots_wanted number of empty slots you want to keep at the end of the internal array for further
 131  * insertions
 132  *
 133  * Reduces the internal array size of the dynar to the number of elements plus @a empty_slots_wanted.
 134  * After removing elements from the dynar, you can call this function to make the dynar use less memory.
 135  * Set @a empty_slots_wanted to zero to reduce the dynar internal array as much as possible.
 136  * Note that if @a empty_slots_wanted is greater than the array size, the internal array is expanded instead of shrunk.
 137  */
 138 void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted)
 139 {
 140   _xbt_dynar_resize(dynar, dynar->used + empty_slots_wanted);
 141 }
 142
 143 /** @brief Destructor
 144  *
 145  * @param dynar poor victim
 146  *
 147  * kilkil a dynar and its content
 148  */
 149 void xbt_dynar_free(xbt_dynar_t* dynar)
 150 {
 151   if (dynar && *dynar) {
 152     xbt_dynar_reset(*dynar);
 153     xbt_dynar_free_container(dynar);
 154   }
 155 }
 156
 157 /** @brief Count of dynar's elements
 158  *
 159  * @param dynar the dynar we want to measure
 160  */
 161 unsigned long xbt_dynar_length(const_xbt_dynar_t dynar)
 162 {
 163   return (dynar ? (unsigned long) dynar->used : (unsigned long) 0);
 164 }
 165
 166 /**@brief check if a dynar is empty
 167  *
 168  *@param dynar the dynat we want to check
 169  */
 170 int xbt_dynar_is_empty(const_xbt_dynar_t dynar)
 171 {
 172   return (xbt_dynar_length(dynar) == 0);
 173 }
 174
 175 /** @brief Retrieve a copy of the Nth element of a dynar.
 176  *
 177  * @param dynar information dealer
 178  * @param idx index of the slot we want to retrieve
 179  * @param[out] dst where to put the result to.
 180  */
 181 void xbt_dynar_get_cpy(const_xbt_dynar_t dynar, unsigned long idx, void* dst)
 182 {
 183   _sanity_check_dynar(dynar);
 184   _check_inbound_idx(dynar, idx);
 185
 186   _xbt_dynar_get_elm(dst, dynar, idx);
 187 }
 188
 189 /** @brief Retrieve a pointer to the Nth element of a dynar.
 190  *
 191  * @param dynar information dealer
 192  * @param idx index of the slot we want to retrieve
 193  * @return the @a idx-th element of @a dynar.
 194  *
 195  * @warning The returned value is the actual content of the dynar.
 196  * Make a copy before fooling with it.
 197  */
 198 void* xbt_dynar_get_ptr(const_xbt_dynar_t dynar, unsigned long idx)
 199 {
 200   void *res;
 201   _sanity_check_dynar(dynar);
 202   _check_inbound_idx(dynar, idx);
 203
 204   res = _xbt_dynar_elm(dynar, idx);
 205   return res;
 206 }
 207
 208 void* xbt_dynar_set_at_ptr(const xbt_dynar_t dynar, unsigned long idx)
 209 {
 210   _sanity_check_dynar(dynar);
 211
 212   if (idx >= dynar->used) {
 213     _xbt_dynar_expand(dynar, idx + 1);
 214     if (idx > dynar->used) {
 215       memset(_xbt_dynar_elm(dynar, dynar->used), 0, (idx - dynar->used) * dynar->elmsize);
 216     }
 217     dynar->used = idx + 1;
 218   }
 219   return _xbt_dynar_elm(dynar, idx);
 220 }
 221
 222 /** @brief Make room for a new element, and return a pointer to it
 223  *
 224  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 225  * xbt_dynar_insert_at_as() does.
 226  */
 227 void* xbt_dynar_insert_at_ptr(xbt_dynar_t dynar, int idx)
 228 {
 229   void *res;
 230   unsigned long old_used;
 231   unsigned long new_used;
 232   long nb_shift;
 233
 234   _sanity_check_dynar(dynar);
 235   _sanity_check_idx(idx);
 236
 237   old_used = dynar->used;
 238   new_used = old_used + 1;
 239
 240   _xbt_dynar_expand(dynar, new_used);
 241
 242   nb_shift = old_used - idx;
 243
 244   if (nb_shift>0) {
 245     memmove(_xbt_dynar_elm(dynar, idx + 1), _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
 246   }
 247
 248   dynar->used = new_used;
 249   res = _xbt_dynar_elm(dynar, idx);
 250   return res;
 251 }
 252
 253 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
 254  *
 255  * Set the Nth element of a dynar, expanding the dynar if needed, and moving the previously existing value and all
 256  * subsequent ones to one position right in the dynar.
 257  */
 258 void xbt_dynar_insert_at(xbt_dynar_t dynar, int idx, const void* src)
 259 {
 260   /* checks done in xbt_dynar_insert_at_ptr */
 261   memcpy(xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
 262 }
 263
 264 /** @brief Remove the Nth dynar's element, sliding the previous values to the left
 265  *
 266  * Get the Nth element of a dynar, removing it from the dynar and moving all subsequent values to one position left in
 267  * the dynar.
 268  *
 269  * If the object argument of this function is a non-null pointer, the removed element is copied to this address. If not,
 270  * the element is freed using the free_f function passed at dynar creation.
 271  */
 272 void xbt_dynar_remove_at(xbt_dynar_t dynar, int idx, void* object)
 273 {
 274   _sanity_check_dynar(dynar);
 275   _check_inbound_idx(dynar, idx);
 276
 277   if (object) {
 278     _xbt_dynar_get_elm(object, dynar, idx);
 279   } else if (dynar->free_f) {
 280     dynar->free_f(_xbt_dynar_elm(dynar, idx));
 281   }
 282
 283   unsigned long nb_shift = dynar->used - 1 - idx;
 284
 285   if (nb_shift) {
 286     unsigned long offset = nb_shift * dynar->elmsize;
 287     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset);
 288   }
 289
 290   dynar->used--;
 291 }
 292
 293 /** @brief Returns the position of the element in the dynar (or -1 if not found)
 294  *
 295  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 296  * what you want. Check the documentation of xbt_dynar_search() for more info.
 297  *
 298  * Note that usually, the dynar indices are unsigned integers. If you have more than 2 million elements in your dynar,
 299  * this very function will not work (but the other will).
 300  */
 301 signed int xbt_dynar_search_or_negative(const_xbt_dynar_t dynar, const void* elem)
 302 {
 303   unsigned long it;
 304
 305   for (it = 0; it < dynar->used; it++)
 306     if (not memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 307       return it;
 308     }
 309
 310   return -1;
 311 }
 312
 313 /** @brief Returns a boolean indicating whether the element is part of the dynar
 314  *
 315  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 316  * what you want. Check the documentation of xbt_dynar_search() for more info.
 317  */
 318 int xbt_dynar_member(const_xbt_dynar_t dynar, const void* elem)
 319 {
 320   unsigned long it;
 321
 322   for (it = 0; it < dynar->used; it++)
 323     if (not memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 324       return 1;
 325     }
 326
 327   return 0;
 328 }
 329
 330 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 331  *
 332  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 333  * xbt_dynar_push_as() does.
 334  */
 335 void* xbt_dynar_push_ptr(xbt_dynar_t dynar)
 336 {
 337   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 338 }
 339
 340 /** @brief Add an element at the end of the dynar */
 341 void xbt_dynar_push(xbt_dynar_t dynar, const void* src)
 342 {
 343   /* checks done in xbt_dynar_insert_at_ptr */
 344   memcpy(xbt_dynar_insert_at_ptr(dynar, dynar->used), src, dynar->elmsize);
 345 }
 346
 347 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 348  *
 349  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 350  * xbt_dynar_pop_as() does.
 351  */
 352 void* xbt_dynar_pop_ptr(xbt_dynar_t dynar)
 353 {
 354   _check_populated_dynar(dynar);
 355   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 356   dynar->used--;
 357   return _xbt_dynar_elm(dynar, dynar->used);
 358 }
 359
 360 /** @brief Get and remove the last element of the dynar */
 361 void xbt_dynar_pop(xbt_dynar_t dynar, void* dst)
 362 {
 363   /* sanity checks done by remove_at */
 364   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 365   xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
 366 }
 367
 368 /** @brief Add an element at the beginning of the dynar.
 369  *
 370  * This is less efficient than xbt_dynar_push()
 371  */
 372 void xbt_dynar_unshift(xbt_dynar_t dynar, const void* src)
 373 {
 374   /* sanity checks done by insert_at */
 375   xbt_dynar_insert_at(dynar, 0, src);
 376 }
 377
 378 /** @brief Get and remove the first element of the dynar.
 379  *
 380  * This is less efficient than xbt_dynar_pop()
 381  */
 382 void xbt_dynar_shift(xbt_dynar_t dynar, void* dst)
 383 {
 384   /* sanity checks done by remove_at */
 385   xbt_dynar_remove_at(dynar, 0, dst);
 386 }
 387
 388 /** @brief Apply a function to each member of a dynar
 389  *
 390  * The mapped function may change the value of the element itself, but should not mess with the structure of the dynar.
 391  */
 392 void xbt_dynar_map(const_xbt_dynar_t dynar, void_f_pvoid_t op)
 393 {
 394   char *const data = (char *) dynar->data;
 395   const unsigned long elmsize = dynar->elmsize;
 396   const unsigned long used = dynar->used;
 397   unsigned long i;
 398
 399   _sanity_check_dynar(dynar);
 400
 401   for (i = 0; i < used; i++) {
 402     char* elm = (char*) data + i * elmsize;
 403     op(elm);
 404   }
 405 }
 406
 407 /** @brief Removes and free the entry pointed by the cursor
 408  *
 409  * This function can be used while traversing without problem.
 410  */
 411 void xbt_dynar_cursor_rm(xbt_dynar_t dynar, unsigned int* cursor)
 412 {
 413   xbt_dynar_remove_at(dynar, *cursor, nullptr);
 414   *cursor -= 1;
 415 }
 416
 417 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
 418  *
 419  * This function simply apply the classical qsort(3) function to the data stored in the dynar.
 420  * You should thus refer to the libc documentation, or to some online tutorial on how to write
 421  * a comparison function. Here is a quick example if you have integers in your dynar:
 422  *
 423  * @verbatim
 424  * int cmpfunc (const void * a, const void * b) {
 425  *   int intA = *(int*)a;
 426  *   int intB = *(int*)b;
 427  *   return intA - intB;
 428  * }
 429  * @endverbatim
 430  *
 431  * and now to sort a dynar of MSG hosts depending on their speed:
 432  * @verbatim
 433  * int cmpfunc(const MSG_host_t a, const MSG_host_t b) {
 434  *   MSG_host_t hostA = *(MSG_host_t*)a;
 435  *   MSG_host_t hostB = *(MSG_host_t*)b;
 436  *   return MSG_host_get_speed(hostA) - MSG_host_get_speed(hostB);
 437  * }
 438  * @endverbatim
 439  *
 440  * @param dynar the dynar to sort
 441  * @param compar_fn comparison function of type (int (compar_fn*) (const void*) (const void*)).
 442  */
 443 void xbt_dynar_sort(const_xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn)
 444 {
 445   if (dynar->data != nullptr)
 446     qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
 447 }
 448
 449 /** @brief Transform a dynar into a nullptr terminated array.
 450  *
 451  *  @param dynar the dynar to transform
 452  *  @return pointer to the first element of the array
 453  *
 454  *  Note: The dynar won't be usable afterwards.
 455  */
 456 void* xbt_dynar_to_array(xbt_dynar_t dynar)
 457 {
 458   void *res;
 459   xbt_dynar_shrink(dynar, 1);
 460   memset(xbt_dynar_push_ptr(dynar), 0, dynar->elmsize);
 461   res = dynar->data;
 462   xbt_free(dynar);
 463   return res;
 464 }