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
 196   _sanity_check_dynar(dynar);
 197   _sanity_check_idx(idx);
 198
 199   old_used = dynar->used;
 200   new_used = old_used + 1;
 201
 202   _xbt_dynar_expand(dynar, new_used);
 203
 204   if (long nb_shift = old_used - idx; nb_shift > 0) {
 205     memmove(_xbt_dynar_elm(dynar, idx + 1), _xbt_dynar_elm(dynar, idx), nb_shift * dynar->elmsize);
 206   }
 207
 208   dynar->used = new_used;
 209   res = _xbt_dynar_elm(dynar, idx);
 210   return res;
 211 }
 212
 213 /** @brief Set the Nth dynar's element, expanding the dynar and sliding the previous values to the right
 214  *
 215  * Set the Nth element of a dynar, expanding the dynar if needed, and moving the previously existing value and all
 216  * subsequent ones to one position right in the dynar.
 217  */
 218 void xbt_dynar_insert_at(xbt_dynar_t dynar, int idx, const void* src)
 219 {
 220   /* checks done in xbt_dynar_insert_at_ptr */
 221   memcpy(xbt_dynar_insert_at_ptr(dynar, idx), src, dynar->elmsize);
 222 }
 223
 224 /** @brief Remove the Nth element, sliding other values to the left
 225  *
 226  * Get the Nth element of a dynar, removing it from the dynar and moving all subsequent values to one position left in
 227  * the dynar.
 228  *
 229  * If the object argument of this function is a non-null pointer, the removed element is copied to this address. If not,
 230  * the element is freed using the free_f function passed at dynar creation.
 231  */
 232 void xbt_dynar_remove_at(xbt_dynar_t dynar, int idx, void* object)
 233 {
 234   _sanity_check_dynar(dynar);
 235   _check_inbound_idx(dynar, idx);
 236
 237   if (object) {
 238     _xbt_dynar_get_elm(object, dynar, idx);
 239   } else if (dynar->free_f) {
 240     dynar->free_f(_xbt_dynar_elm(dynar, idx));
 241   }
 242
 243   if (unsigned long nb_shift = dynar->used - 1 - idx; nb_shift > 0) {
 244     unsigned long offset = nb_shift * dynar->elmsize;
 245     memmove(_xbt_dynar_elm(dynar, idx), _xbt_dynar_elm(dynar, idx + 1), offset);
 246   }
 247
 248   dynar->used--;
 249 }
 250
 251 /** @brief Returns a boolean indicating whether the element is part of the dynar
 252  *
 253  * Beware that if your dynar contains pointed values (such as strings) instead of scalar, this function is probably not
 254  * what you want. It would compare the pointer values, not the pointed elements.
 255  */
 256 int xbt_dynar_member(const_xbt_dynar_t dynar, const void* elem)
 257 {
 258   for (unsigned long it = 0; it < dynar->used; it++)
 259     if (not memcmp(_xbt_dynar_elm(dynar, it), elem, dynar->elmsize)) {
 260       return 1;
 261     }
 262
 263   return 0;
 264 }
 265
 266 /** @brief Make room at the end of the dynar for a new element, and return a pointer to it.
 267  *
 268  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 269  * xbt_dynar_push_as() does.
 270  */
 271 void* xbt_dynar_push_ptr(xbt_dynar_t dynar)
 272 {
 273   return xbt_dynar_insert_at_ptr(dynar, dynar->used);
 274 }
 275
 276 /** @brief Add an element at the end of the dynar */
 277 void xbt_dynar_push(xbt_dynar_t dynar, const void* src)
 278 {
 279   /* checks done in xbt_dynar_insert_at_ptr */
 280   memcpy(xbt_dynar_insert_at_ptr(dynar, dynar->used), src, dynar->elmsize);
 281 }
 282
 283 /** @brief Mark the last dynar's element as unused and return a pointer to it.
 284  *
 285  * You can then use regular affectation to set its value instead of relying on the slow memcpy. This is what
 286  * xbt_dynar_pop_as() does.
 287  */
 288 void* xbt_dynar_pop_ptr(xbt_dynar_t dynar)
 289 {
 290   _check_populated_dynar(dynar);
 291   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 292   dynar->used--;
 293   return _xbt_dynar_elm(dynar, dynar->used);
 294 }
 295
 296 /** @brief Get and remove the last element of the dynar */
 297 void xbt_dynar_pop(xbt_dynar_t dynar, void* dst)
 298 {
 299   /* sanity checks done by remove_at */
 300   XBT_CDEBUG(xbt_dyn, "Pop %p", (void *) dynar);
 301   xbt_dynar_remove_at(dynar, dynar->used - 1, dst);
 302 }
 303
 304 /** @brief Add an element at the beginning of the dynar.
 305  *
 306  * This is less efficient than xbt_dynar_push()
 307  */
 308 void xbt_dynar_unshift(xbt_dynar_t dynar, const void* src)
 309 {
 310   /* sanity checks done by insert_at */
 311   xbt_dynar_insert_at(dynar, 0, src);
 312 }
 313
 314 /** @brief Get and remove the first element of the dynar.
 315  *
 316  * This is less efficient than xbt_dynar_pop()
 317  */
 318 void xbt_dynar_shift(xbt_dynar_t dynar, void* dst)
 319 {
 320   /* sanity checks done by remove_at */
 321   xbt_dynar_remove_at(dynar, 0, dst);
 322 }
 323
 324 /** @brief Apply a function to each member of a dynar
 325  *
 326  * The mapped function may change the value of the element itself, but should not mess with the structure of the dynar.
 327  */
 328 void xbt_dynar_map(const_xbt_dynar_t dynar, void_f_pvoid_t op)
 329 {
 330   auto* const data            = static_cast<char*>(dynar->data);
 331   const unsigned long elmsize = dynar->elmsize;
 332   const unsigned long used = dynar->used;
 333
 334   _sanity_check_dynar(dynar);
 335
 336   for (unsigned long i = 0; i < used; i++) {
 337     char* elm = data + i * elmsize;
 338     op(elm);
 339   }
 340 }
 341
 342 /** @brief Sorts a dynar according to the function <tt>compar_fn</tt>
 343  *
 344  * This function simply apply the classical qsort(3) function to the data stored in the dynar.
 345  * You should thus refer to the libc documentation, or to some online tutorial on how to write
 346  * a comparison function. Here is a quick example if you have integers in your dynar:
 347  *
 348  * @verbatim
 349    int cmpfunc (const void * a, const void * b) {
 350      int intA = *(int*)a;
 351      int intB = *(int*)b;
 352      return intA - intB;
 353    }
 354    @endverbatim
 355  *
 356  * And now, a function to sort a dynar of MSG hosts depending on their speed:
 357  * @verbatim
 358    int cmpfunc(const MSG_host_t a, const MSG_host_t b) {
 359      MSG_host_t hostA = *(MSG_host_t*)a;
 360      MSG_host_t hostB = *(MSG_host_t*)b;
 361      return MSG_host_get_speed(hostA) - MSG_host_get_speed(hostB);
 362    }
 363    @endverbatim
 364  *
 365  * @param dynar the dynar to sort
 366  * @param compar_fn comparison function of type (int (compar_fn*) (const void*) (const void*)).
 367  */
 368 void xbt_dynar_sort(const_xbt_dynar_t dynar, int_f_cpvoid_cpvoid_t compar_fn)
 369 {
 370   if (dynar->data != nullptr)
 371     qsort(dynar->data, dynar->used, dynar->elmsize, compar_fn);
 372 }