src/xbt/dynar.cpp

   1 /* a generic DYNamic ARray implementation.                                  */
   2
   3 /* Copyright (c) 2004-2021. 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   auto* const data            = static_cast<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 /**
  75  * Creates a new dynar. If a @c free_f is provided, the elements have to be pointer of pointer. That is to say that
  76  * dynars can contain either base types (int, char, double, etc) or pointer of pointers (struct **).
  77  *
  78  * @param elmsize size of each element in the dynar
  79  * @param free_f function to call each time we want to get rid of an element (or nullptr if nothing to do).
  80  */
  81 xbt_dynar_t xbt_dynar_new(const unsigned long elmsize, void_f_pvoid_t free_f)
  82 {
  83   auto* dynar = xbt_new0(s_xbt_dynar_t, 1);
  84
  85   dynar->size = 0;
  86   dynar->used = 0;
  87   dynar->elmsize = elmsize;
  88   dynar->data = nullptr;
  89   dynar->free_f = free_f;
  90
  91   return dynar;
  92 }
  93
  94 /** Destructor of the structure leaving the content unmodified. Ie, the array is freed, but the content is not touched
  95  * (the @a free_f function is not used).
  96  *
  97  * @param dynar poor victim
  98  */
  99 void xbt_dynar_free_container(xbt_dynar_t* dynar)
 100 {
 101   if (dynar && *dynar) {
 102     xbt_dynar_t d = *dynar;
 103     xbt_free(d->data);
 104     xbt_free(d);
 105     *dynar = nullptr;
 106   }
 107 }
 108
 109 /** @brief Frees the content and set the size to 0 */
 110 void xbt_dynar_reset(xbt_dynar_t dynar)
 111 {
 112   _sanity_check_dynar(dynar);
 113
 114   XBT_CDEBUG(xbt_dyn, "Reset the dynar %p", (void *) dynar);
 115   if (dynar->free_f) {
 116     xbt_dynar_map(dynar, dynar->free_f);
 117   }
 118   dynar->used = 0;
 119 }
 120
 121 /**
 122  * Shrinks (reduces) the dynar by removing empty slots in the internal storage to save memory.
 123  * If @c empty_slots_wanted is not zero, this operation preserves that amount of empty slot, for fast future additions.
 124  * Note that if @c empty_slots_wanted is large enough, the internal array is expanded instead of shrunk.
 125  *
 126  * @param dynar a dynar
 127  * @param empty_slots_wanted number of empty slots elements that can be inserted the internal storage without resizing it
 128  */
 129 void xbt_dynar_shrink(xbt_dynar_t dynar, int empty_slots_wanted)
 130 {
 131   _xbt_dynar_resize(dynar, dynar->used + empty_slots_wanted);
 132 }
 133
 134 /** @brief Destructor: kilkil a dynar and its content. */
 135 void xbt_dynar_free(xbt_dynar_t* dynar)
 136 {
 137   if (dynar && *dynar) {
 138     xbt_dynar_reset(*dynar);
 139     xbt_dynar_free_container(dynar);
 140   }
 141 }
 142
 143 /** @brief Count of dynar's elements */
 144 unsigned long xbt_dynar_length(const_xbt_dynar_t dynar)
 145 {
 146   return (dynar ? dynar->used : 0UL);
 147 }
 148
 149 /**@brief check if a dynar is empty */
 150 int xbt_dynar_is_empty(const_xbt_dynar_t dynar)
 151 {
 152   return (xbt_dynar_length(dynar) == 0);
 153 }
 154
 155 /** @brief Retrieve a copy of the Nth element of a dynar.
 156  *
 157  * @param dynar information dealer
 158  * @param idx index of the slot we want to retrieve
 159  * @param[out] dst where to put the result to.
 160  */
 161 void xbt_dynar_get_cpy(const_xbt_dynar_t dynar, unsigned long idx, void* dst)
 162 {
 163   _sanity_check_dynar(dynar);
 164   _check_inbound_idx(dynar, idx);
 165
 166   _xbt_dynar_get_elm(dst, dynar, idx);
 167 }
 168
 169 /** @brief Retrieve a pointer to the Nth element of a dynar.
 170  *
 171  * Note that the returned value is the actual content of the dynar.
 172  * Make a copy before fooling with it.
 173  */
 174 void* xbt_dynar_get_ptr(const_xbt_dynar_t dynar, unsigned long idx)
 175 {
 176   void *res;
 177   _sanity_check_dynar(dynar);
 178   _check_inbound_idx(dynar, idx);
 179
 180   res = _xbt_dynar_elm(dynar, idx);
 181   return res;
 182 }
 183
 184 void* xbt_dynar_set_at_ptr(const xbt_dynar_t dynar, unsigned long idx)
 185 {
 186   _sanity_check_dynar(dynar);
 187
 188   if (idx >= dynar->used) {
 189     _xbt_dynar_expand(dynar, idx + 1);
 190     if (idx > dynar->used) {
 191       memset(_xbt_dynar_elm(dynar, dynar->used), 0, (idx - dynar->used) * dynar->elmsize);
 192     }
 193     dynar->used = idx + 1;
 194   }
 195   return _xbt_dynar_elm(dynar, idx);
 196 }
 197
 198 /** @brief Make room for a new element, and return a pointer to it
 199  *
 200  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 201  * xbt_dynar_insert_at_as() does.
 202  */
 203 void* xbt_dynar_insert_at_ptr(xbt_dynar_t dynar, int idx)
 204 {
 205   void *res;
 206   unsigned long old_used;
 207   unsigned long new_used;
 208   long nb_shift;
 209
 210   _sanity_check_dynar(dynar);
 211   _sanity_check_idx(idx);
 212
 213   old_used = dynar->used;
 214   new_used = old_used + 1;
 215
 216   _xbt_dynar_expand(dynar, new_used);
 217
 218   nb_shift = old_used - idx;
 219
 220   if (nb_shift>0) {
 221     memmove(_xbt_dynar_elm(dynar, idx + 1), _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
 222   }
 223
 224   dynar->used = new_used;
 225   res = _xbt_dynar_elm(dynar, idx);
 226   return res;
 227 }
 228
 229 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
 230  *
 231  * Set the Nth element of a dynar, expanding the dynar if needed, and moving the previously existing value and all
 232  * subsequent ones to one position right in the dynar.
 233  */
 234 void xbt_dynar_insert_at(xbt_dynar_t dynar, int idx, const void* src)
 235 {
 236   /* checks done in xbt_dynar_insert_at_ptr */
 237   memcpy(xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
 238 }
 239
 240 /** @brief Remove the Nth element, sliding other values to the left
 241  *
 242  * Get the Nth element of a dynar, removing it from the dynar and moving all subsequent values to one position left in
 243  * the dynar.
 244  *
 245  * If the object argument of this function is a non-null pointer, the removed element is copied to this address. If not,
 246  * the element is freed using the free_f function passed at dynar creation.
 247  */
 248 void xbt_dynar_remove_at(xbt_dynar_t dynar, int idx, void* object)
 249 {
 250   _sanity_check_dynar(dynar);
 251   _check_inbound_idx(dynar, idx);
 252
 253   if (object) {
 254     _xbt_dynar_get_elm(object, dynar, idx);
 255   } else if (dynar->free_f) {
 256     dynar->free_f(_xbt_dynar_elm(dynar, idx));
 257   }
 258
 259   unsigned long nb_shift = dynar->used - 1 - idx;
 260
 261   if (nb_shift) {
 262     unsigned long offset = nb_shift * dynar->elmsize;
 263     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset);
 264   }
 265
 266   dynar->used--;
 267 }
 268
 269 /** @brief Returns a boolean indicating whether the element is part of the dynar
 270  *
 271  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 272  * what you want. It would compare the pointer values, not the pointed elements.
 273  */
 274 int xbt_dynar_member(const_xbt_dynar_t dynar, const void* elem)
 275 {
 276   for (unsigned long it = 0; it < dynar->used; it++)
 277     if (not memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 278       return 1;
 279     }
 280
 281   return 0;
 282 }
 283
 284 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 285  *
 286  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 287  * xbt_dynar_push_as() does.
 288  */
 289 void* xbt_dynar_push_ptr(xbt_dynar_t dynar)
 290 {
 291   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 292 }
 293
 294 /** @brief Add an element at the end of the dynar */
 295 void xbt_dynar_push(xbt_dynar_t dynar, const void* src)
 296 {
 297   /* checks done in xbt_dynar_insert_at_ptr */
 298   memcpy(xbt_dynar_insert_at_ptr(dynar, dynar->used), src, dynar->elmsize);
 299 }
 300
 301 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 302  *
 303  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 304  * xbt_dynar_pop_as() does.
 305  */
 306 void* xbt_dynar_pop_ptr(xbt_dynar_t dynar)
 307 {
 308   _check_populated_dynar(dynar);
 309   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 310   dynar->used--;
 311   return _xbt_dynar_elm(dynar, dynar->used);
 312 }
 313
 314 /** @brief Get and remove the last element of the dynar */
 315 void xbt_dynar_pop(xbt_dynar_t dynar, void* dst)
 316 {
 317   /* sanity checks done by remove_at */
 318   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 319   xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
 320 }
 321
 322 /** @brief Add an element at the beginning of the dynar.
 323  *
 324  * This is less efficient than xbt_dynar_push()
 325  */
 326 void xbt_dynar_unshift(xbt_dynar_t dynar, const void* src)
 327 {
 328   /* sanity checks done by insert_at */
 329   xbt_dynar_insert_at(dynar, 0, src);
 330 }
 331
 332 /** @brief Get and remove the first element of the dynar.
 333  *
 334  * This is less efficient than xbt_dynar_pop()
 335  */
 336 void xbt_dynar_shift(xbt_dynar_t dynar, void* dst)
 337 {
 338   /* sanity checks done by remove_at */
 339   xbt_dynar_remove_at(dynar, 0, dst);
 340 }
 341
 342 /** @brief Apply a function to each member of a dynar
 343  *
 344  * The mapped function may change the value of the element itself, but should not mess with the structure of the dynar.
 345  */
 346 void xbt_dynar_map(const_xbt_dynar_t dynar, void_f_pvoid_t op)
 347 {
 348   auto* const data            = static_cast<char*>(dynar->data);
 349   const unsigned long elmsize = dynar->elmsize;
 350   const unsigned long used = dynar->used;
 351
 352   _sanity_check_dynar(dynar);
 353
 354   for (unsigned long i = 0; i < used; i++) {
 355     char* elm = data + i * elmsize;
 356     op(elm);
 357   }
 358 }
 359
 360 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
 361  *
 362  * This function simply apply the classical qsort(3) function to the data stored in the dynar.
 363  * You should thus refer to the libc documentation, or to some online tutorial on how to write
 364  * a comparison function. Here is a quick example if you have integers in your dynar:
 365  *
 366  * @verbatim
 367    int cmpfunc (const void * a, const void * b) {
 368      int intA = *(int*)a;
 369      int intB = *(int*)b;
 370      return intA - intB;
 371    }
 372    @endverbatim
 373  *
 374  * And now, a function to sort a dynar of MSG hosts depending on their speed:
 375  * @verbatim
 376    int cmpfunc(const MSG_host_t a, const MSG_host_t b) {
 377      MSG_host_t hostA = *(MSG_host_t*)a;
 378      MSG_host_t hostB = *(MSG_host_t*)b;
 379      return MSG_host_get_speed(hostA) - MSG_host_get_speed(hostB);
 380    }
 381    @endverbatim
 382  *
 383  * @param dynar the dynar to sort
 384  * @param compar_fn comparison function of type (int (compar_fn*) (const void*) (const void*)).
 385  */
 386 void xbt_dynar_sort(const_xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn)
 387 {
 388   if (dynar->data != nullptr)
 389     qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
 390 }
 391
 392 /** @brief Transform a dynar into a nullptr terminated array.
 393  *
 394  *  @param dynar the dynar to transform
 395  *  @return pointer to the first element of the array
 396  *
 397  *  Note: The dynar won't be usable afterwards.
 398  */
 399 void* xbt_dynar_to_array(xbt_dynar_t dynar) // XBT_ATTRIB_DEPRECATED_v331
 400 {
 401   void* res;
 402   xbt_dynar_shrink(dynar, 1);
 403   memset(xbt_dynar_push_ptr(dynar), 0, dynar->elmsize);
 404   res = dynar->data;
 405   xbt_free(dynar);
 406   return res;
 407 }