src/xbt/dynar.cpp

   1 /* a generic DYNamic ARray implementation.                                  */
   2
   3 /* Copyright (c) 2004-2022. 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 /** @brief Destructor: kilkil a dynar and its content. */
 122 void xbt_dynar_free(xbt_dynar_t* dynar)
 123 {
 124   if (dynar && *dynar) {
 125     xbt_dynar_reset(*dynar);
 126     xbt_dynar_free_container(dynar);
 127   }
 128 }
 129
 130 /** @brief Count of dynar's elements */
 131 unsigned long xbt_dynar_length(const_xbt_dynar_t dynar)
 132 {
 133   return (dynar ? dynar->used : 0UL);
 134 }
 135
 136 /**@brief check if a dynar is empty */
 137 int xbt_dynar_is_empty(const_xbt_dynar_t dynar)
 138 {
 139   return (xbt_dynar_length(dynar) == 0);
 140 }
 141
 142 /** @brief Retrieve a copy of the Nth element of a dynar.
 143  *
 144  * @param dynar information dealer
 145  * @param idx index of the slot we want to retrieve
 146  * @param[out] dst where to put the result to.
 147  */
 148 void xbt_dynar_get_cpy(const_xbt_dynar_t dynar, unsigned long idx, void* dst)
 149 {
 150   _sanity_check_dynar(dynar);
 151   _check_inbound_idx(dynar, idx);
 152
 153   _xbt_dynar_get_elm(dst, dynar, idx);
 154 }
 155
 156 /** @brief Retrieve a pointer to the Nth element of a dynar.
 157  *
 158  * Note that the returned value is the actual content of the dynar.
 159  * Make a copy before fooling with it.
 160  */
 161 void* xbt_dynar_get_ptr(const_xbt_dynar_t dynar, unsigned long idx)
 162 {
 163   void *res;
 164   _sanity_check_dynar(dynar);
 165   _check_inbound_idx(dynar, idx);
 166
 167   res = _xbt_dynar_elm(dynar, idx);
 168   return res;
 169 }
 170
 171 void* xbt_dynar_set_at_ptr(const xbt_dynar_t dynar, unsigned long idx)
 172 {
 173   _sanity_check_dynar(dynar);
 174
 175   if (idx >= dynar->used) {
 176     _xbt_dynar_expand(dynar, idx + 1);
 177     if (idx > dynar->used) {
 178       memset(_xbt_dynar_elm(dynar, dynar->used), 0, (idx - dynar->used) * dynar->elmsize);
 179     }
 180     dynar->used = idx + 1;
 181   }
 182   return _xbt_dynar_elm(dynar, idx);
 183 }
 184
 185 /** @brief Make room for a new element, and return a pointer to it
 186  *
 187  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 188  * xbt_dynar_insert_at_as() does.
 189  */
 190 void* xbt_dynar_insert_at_ptr(xbt_dynar_t dynar, int idx)
 191 {
 192   void *res;
 193   unsigned long old_used;
 194   unsigned long new_used;
 195   long nb_shift;
 196
 197   _sanity_check_dynar(dynar);
 198   _sanity_check_idx(idx);
 199
 200   old_used = dynar->used;
 201   new_used = old_used + 1;
 202
 203   _xbt_dynar_expand(dynar, new_used);
 204
 205   nb_shift = old_used - idx;
 206
 207   if (nb_shift>0) {
 208     memmove(_xbt_dynar_elm(dynar, idx + 1), _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
 209   }
 210
 211   dynar->used = new_used;
 212   res = _xbt_dynar_elm(dynar, idx);
 213   return res;
 214 }
 215
 216 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
 217  *
 218  * Set the Nth element of a dynar, expanding the dynar if needed, and moving the previously existing value and all
 219  * subsequent ones to one position right in the dynar.
 220  */
 221 void xbt_dynar_insert_at(xbt_dynar_t dynar, int idx, const void* src)
 222 {
 223   /* checks done in xbt_dynar_insert_at_ptr */
 224   memcpy(xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
 225 }
 226
 227 /** @brief Remove the Nth element, sliding other values to the left
 228  *
 229  * Get the Nth element of a dynar, removing it from the dynar and moving all subsequent values to one position left in
 230  * the dynar.
 231  *
 232  * If the object argument of this function is a non-null pointer, the removed element is copied to this address. If not,
 233  * the element is freed using the free_f function passed at dynar creation.
 234  */
 235 void xbt_dynar_remove_at(xbt_dynar_t dynar, int idx, void* object)
 236 {
 237   _sanity_check_dynar(dynar);
 238   _check_inbound_idx(dynar, idx);
 239
 240   if (object) {
 241     _xbt_dynar_get_elm(object, dynar, idx);
 242   } else if (dynar->free_f) {
 243     dynar->free_f(_xbt_dynar_elm(dynar, idx));
 244   }
 245
 246   unsigned long nb_shift = dynar->used - 1 - idx;
 247
 248   if (nb_shift) {
 249     unsigned long offset = nb_shift * dynar->elmsize;
 250     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset);
 251   }
 252
 253   dynar->used--;
 254 }
 255
 256 /** @brief Returns a boolean indicating whether the element is part of the dynar
 257  *
 258  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 259  * what you want. It would compare the pointer values, not the pointed elements.
 260  */
 261 int xbt_dynar_member(const_xbt_dynar_t dynar, const void* elem)
 262 {
 263   for (unsigned long it = 0; it < dynar->used; it++)
 264     if (not memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 265       return 1;
 266     }
 267
 268   return 0;
 269 }
 270
 271 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 272  *
 273  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 274  * xbt_dynar_push_as() does.
 275  */
 276 void* xbt_dynar_push_ptr(xbt_dynar_t dynar)
 277 {
 278   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 279 }
 280
 281 /** @brief Add an element at the end of the dynar */
 282 void xbt_dynar_push(xbt_dynar_t dynar, const void* src)
 283 {
 284   /* checks done in xbt_dynar_insert_at_ptr */
 285   memcpy(xbt_dynar_insert_at_ptr(dynar, dynar->used), src, dynar->elmsize);
 286 }
 287
 288 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 289  *
 290  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 291  * xbt_dynar_pop_as() does.
 292  */
 293 void* xbt_dynar_pop_ptr(xbt_dynar_t dynar)
 294 {
 295   _check_populated_dynar(dynar);
 296   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 297   dynar->used--;
 298   return _xbt_dynar_elm(dynar, dynar->used);
 299 }
 300
 301 /** @brief Get and remove the last element of the dynar */
 302 void xbt_dynar_pop(xbt_dynar_t dynar, void* dst)
 303 {
 304   /* sanity checks done by remove_at */
 305   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 306   xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
 307 }
 308
 309 /** @brief Add an element at the beginning of the dynar.
 310  *
 311  * This is less efficient than xbt_dynar_push()
 312  */
 313 void xbt_dynar_unshift(xbt_dynar_t dynar, const void* src)
 314 {
 315   /* sanity checks done by insert_at */
 316   xbt_dynar_insert_at(dynar, 0, src);
 317 }
 318
 319 /** @brief Get and remove the first element of the dynar.
 320  *
 321  * This is less efficient than xbt_dynar_pop()
 322  */
 323 void xbt_dynar_shift(xbt_dynar_t dynar, void* dst)
 324 {
 325   /* sanity checks done by remove_at */
 326   xbt_dynar_remove_at(dynar, 0, dst);
 327 }
 328
 329 /** @brief Apply a function to each member of a dynar
 330  *
 331  * The mapped function may change the value of the element itself, but should not mess with the structure of the dynar.
 332  */
 333 void xbt_dynar_map(const_xbt_dynar_t dynar, void_f_pvoid_t op)
 334 {
 335   auto* const data            = static_cast<char*>(dynar->data);
 336   const unsigned long elmsize = dynar->elmsize;
 337   const unsigned long used = dynar->used;
 338
 339   _sanity_check_dynar(dynar);
 340
 341   for (unsigned long i = 0; i < used; i++) {
 342     char* elm = data + i * elmsize;
 343     op(elm);
 344   }
 345 }
 346
 347 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
 348  *
 349  * This function simply apply the classical qsort(3) function to the data stored in the dynar.
 350  * You should thus refer to the libc documentation, or to some online tutorial on how to write
 351  * a comparison function. Here is a quick example if you have integers in your dynar:
 352  *
 353  * @verbatim
 354    int cmpfunc (const void * a, const void * b) {
 355      int intA = *(int*)a;
 356      int intB = *(int*)b;
 357      return intA - intB;
 358    }
 359    @endverbatim
 360  *
 361  * And now, a function to sort a dynar of MSG hosts depending on their speed:
 362  * @verbatim
 363    int cmpfunc(const MSG_host_t a, const MSG_host_t b) {
 364      MSG_host_t hostA = *(MSG_host_t*)a;
 365      MSG_host_t hostB = *(MSG_host_t*)b;
 366      return MSG_host_get_speed(hostA) - MSG_host_get_speed(hostB);
 367    }
 368    @endverbatim
 369  *
 370  * @param dynar the dynar to sort
 371  * @param compar_fn comparison function of type (int (compar_fn*) (const void*) (const void*)).
 372  */
 373 void xbt_dynar_sort(const_xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn)
 374 {
 375   if (dynar->data != nullptr)
 376     qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
 377 }