1
\$\begingroup\$

Since it is quite a hurdle to manage dynamic arrays in C I wrote a simple generic wrapper to handle a pool of pointers. To prevent internal fragmentation when deleting and appending again I store the real indexes in a secondary index array. Do you see any flaws in my code? Would you have any suggestions ?

#ifndef __1512006__POOL__H__
#define __1512006__POOL__H__

#include <stddef.h> /* size_t */
#include <string.h> /* memcpy */

#define RATIO 2

/**
 * Fields' description
 *
 * ** pool **
 *  This is a "dynamic" array containing pointers to elements of the type
 *  `type`. This array is hidden and shall not be accessed directly, the
 *  order of the element is not predictible.
 *
 * ** index **
 *  This array serves as an index for the "dynamic" array pool, using this
 *  indirection prevents internal fragmentation when element are released
 *  from the pool. ``index[nb_elts]'' should always be a place ready to use
 *  to push new elements.
 *
 *  ** nb_elts **
 *   That is the number of currently recorded element in the pool.
 *
 *  ** pool_size **
 *   That is the real size of the pool.
 *
 *  ** type_size **
 *   This field stores the type's size so that the type has not to be passed
 *   to every macro. But only those that declare new instance of type `type'.
 *
 *  ** cpy **
 *   A function to properly handle the copy of composite types.
 */
#define POOL_DECL(type, name)                                                  \
  static struct (type)##_pool {                                                \
    (type) * pool;                                                             \
    size_t * index;                                                            \
    size_t nb_elts;                                                            \
    size_t pool_size;                                                          \
    size_t type_size;                                                          \
    (type) * (*cpy) ((type) *);                                                \
  } (name)

#define POOL_INIT(type, name, base, cpy) do {                                  \
  int i = 0;                                                                   \
  (name).cpy = cpy;                                                            \
  (name).nb_elts = 0;                                                          \
  (name).pool_size = base;                                                     \
  (name).type_size = sizeof((type));                                           \
  (name).pool = calloc((base), (name).type_size);                              \
  (name).index = calloc((base), size(size_t));                                 \
  for (i = 0 ; i < base ; ++i) {                                               \
    (name).index[i] = i;                                                       \
  }                                                                            \
while (0 /* constcond */)

#define POOL_FLUSH(name) do {                                                  \
  free((name).pool), (name).pool = NULL;                                       \
  free((name).index), (name).index = NULL;                                       \
  (name).nb_elts = 0;                                                          \
  (name).pool_size = 0;                                                        \
while (0 /* constcond */)

/* The core of the mini-library: append values to the pool.
 *
 * Two possible cases:
 *  - There is enough place for a new element, then fine, push it a copy of it
 *    at `index[nb_elts]'.
 *  - There is not enough place for a new element. So,
 *      1. Duplicate the element
 *      2. Create a new pool RATIO times larger
 *      3. Create a new index RATIO times larger
 *      4. Copy the old pool in the new and delete the old one
 *      5. Recreate the index and delete the old one
 *      6. Store the duplicate of the element
 */
#define POOL_APPEND(name, type, elt) do {                                      \
  (type) * new_elt = (name).cpy(elt);                                          \
  if ((name).nb_elts >= (name).pool_size) {                                    \
    int i = 0;                                                                 \
    (type) * new_pool = calloc(RATIO * (name).pool_size, (name).type_size);    \
    size_t * new_index = calloc(RATIO * (name).pool_size, sizeof(size_t));     \
    memcpy(new_pool, (name).pool, (name).pool_size * (name).type_size);        \
    memcpy(new_index, (name).index, (name).pool_size * sizeof(size_t));        \
    free((name).pool), (name).pool = NULL;                                     \
    free((name).index), (name).index = NULL;                                   \
    (name).pool = new_pool;                                                    \
    (name).index = new_index;                                                  \
    (name).pool_size = RATIO * (name).pool_size;                               \
    for (int i = nb_elts ; i < (name).pool_size ; ++i)                         \
      (name).index[i] = i;                                                     \
    }                                                                          \
  }                                                                            \
  (name).pool[(name).index[(name).nb_elts++]] = new_elt;                       \
while (0 /* constcond */)

/* Swap position `i' and `j' in name.index using the fact that name.index is 
 * made of unsigned int. (RISK OF OVERFLOW)
 */
#define POOL_SWAP(name, i, j) do {                                             \
  (name).index[i] = (name).index[i] + (name).index[j];                         \
  (name).index[j] = (name).index[i] - (name).index[j];                         \
  (name).index[i] = (name).index[i] - (name).index[j];                         \
while (0 /* constcond */)

/* Release the element whose index is `index' 
To do this the new freed `index' is pushed at the end of the used indexes */
#define POOL_RELEASE(name, index) do {                                         \
  POOL_SWAP((name), (index), (name).nb_elts);                                  \ 
  --(name).nb_elt;                                                             \
while (0 /* constcond */)

#endif /* __1512006__POOL__H */
\$\endgroup\$
3
\$\begingroup\$

Instead of magical macro define a set of generic functions for managing the pool and define the macros to pass the sizeof (as needed) to those functions. In fact you store the sizeof of the type which is all you really need.

typedef struct dynamic_pool {
    (void) * pool;
    size_t * index;
    size_t nb_elts;
    size_t pool_size;
    size_t type_size;
    void (*cpy) ((void) *, (void) *);
    void (*destr) ((void) *);
} dynamic_pool;

If you are going to initialize the data anyway then just use malloc instead of calloc.

void init_pool(dynamic_pool* pool, int typeSize, int initialSize, void (*cpy) ((void) *, (void) *),
        void (*destr) ((void) *) ){
  int i = 0;
  pool->cpy = cpy;
  pool->destr= destr;
  pool->nb_elts = 0;
  pool->pool_size = initialSize;
  pool->type_size = typeSize;
  pool->pool = malloc(initialSize* pool->type_size);
  memset(pool->pool, 0, initialSize* pool->type_size);
  pool->index = malloc(initialSize * sizeof(size_t));
  for (i = 0 ; i < base ; ++i) {
    pool->index[i] = i;
  }
}

void noop(void*){}

// convenience initializer for simple types
void init_pool_simple_type(dynamic_pool* pool, int typeSize, int initialSize){
    init_pool(pool, typeSize, initialSize, memcpy, noop);
}

When growing the array you calloc, memcpy and free. Instead realloc and memset the appended data to 0 for the pool or initialize for the indices.

void pool_append(dynamic_pool* pool, void* elt){

  if ((pool).nb_elts >= (pool).pool_size) {
    int i = 0;
    size_t new_pool_size = RATIO * pool->pool_size;
    pool->pool = realloc(pool->pool, new_pool_size * pool->type_size);
    memset(&pool->pool[pool->pool_size], 0, (new_pool_size - pool->pool_size) * pool->type_size);
    size_t * new_index = realloc(pool->index, new_pool_size * sizeof(size_t));

    for (int i = pool->pool_size ; i < new_pool_size ; ++i)
      (name).index[i] = i;
    }
    pool->pool_size = new_pool_size;

  }     
  pool->cpy(pool->pool[name->index[pool->nb_elts++]] ,elt);
}

The passed in cpy function returns a pointer even though you keep the elements by value.

Speaking of you don't let the user code specify a destruction function that would let them avoid leaks.

void pool_release(dynamic_pool* pool, int index){ 
  pool->destr(pool->pool[pool->index[pool->nb_elts]]);
  memset(pool->pool[pool->index[pool->nb_elts]], 0, pool->type_size);
  pool_swap(pool, index, pool->nb_elts);
  --pool->nb_elt;
}

Instead let cpy take 2 pointer a destination and a origin so putting the value in will be:

pool->cpy(pool->pool[name->index[pool->nb_elts++]] ,elt);

There is no need for the fancy xor-like swap. just use a temporary:

void pool_swap(dynamic_pool* pool, int i, int j){ 
   size_t temp = pool->index[i];
   pool->index[i] = name->index[j];
   pool->index[j] = temp;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your advices. I take notes and I will append the destruction function which I forget to take into account. I did not use realloc because since I was not checking a single value for malloc & cie it was a bit like playing with fire. Why do you prefer generic functions over magic macros ? (I know that is not recommended to abuse the preprocessor) the main reason I can think of is that it is really hard to debug macros. Nevertheless, in this case, using functions make more sense but for generic list/tree I prefer the macro way. \$\endgroup\$ – 永劫回帰 Dec 4 '15 at 11:58
  • 1
    \$\begingroup\$ code bloat and debugability, With macros you force-inline the manipulation functions which could make the calling code complicated enough that it itself cannot be inlined. Also the shear amount of (name) in each macro could wreck havock because each time it is referenced in the macro the argument is reevaluated. This means POOL_INIT(many_pools[i++], ...)will not do what you think it does. \$\endgroup\$ – ratchet freak Dec 4 '15 at 12:11
  • \$\begingroup\$ Yes, that is true. I am convinced enough. Thanks. And yes, using bli++ as an argument can clearly be awful. Your example would break the system since each line with a (name) would evaluate to a different pool ... \$\endgroup\$ – 永劫回帰 Dec 4 '15 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.