3
\$\begingroup\$

I am interested in opinions of experienced C programmers about a certain approach to creating a "generic" dynamic array in C. The idea is to use macros to generate function declarations and definitions, and to avoid using void pointers (of course, this is nothing unheard of). For simplicity, I will only generate three basic functions - one to create such an array, one to destroy it, and one to append an element to the array.

It seems a practical approach, however, before starting to use this pattern all over, I would like to check if it makes sense and if it suffers from some major drawbacks (which I can not identify). So, let's get started.

First, let us define a few utility macros, whose purpose it primarily to avoid repeating boilerplate "safety" code (eg checking if returned pointers are NULL, etc):

// utils.h

#include <stdio.h>
#include <stdlib.h>

/* 
 * Exit with an error message.
 *
 * @param msg String literal, message to display.
*/
#define EXIT_ERROR(msg) \
    do { \
        printf("Error in %s at line %d: %s - terminating program.\n", __FILE__, __LINE__, msg); \
        exit(EXIT_FAILURE); \
    } while(0)

/* 
 * Macro which also checks if the pointer returned by malloc is NULL.
 *
 * @param ptr Name of pointer to which malloc is assigned.
 * @param size Multiple which determines size of malloc'd array
 * @param type Type of array element
*/
#define MALLOC_SAFE(ptr, size, type) \
    malloc((size) * sizeof(type)); \
    if (ptr == NULL) \
        EXIT_ERROR("Memory allocation failure")

/* 
 * Macro with additional safety actions to accompany realloc. If 
 * requested size if 0, frees the pointer. If the call to realloc 
 * returns NULL, terminates the program. Else, assigns the original 
 * pointer to the one returned by realloc.
 *
 * @param ptr Name of pointer to be realloc'd.
 * @param size Multiple which determines size of realloc'd array
 * @param type Type of array element
*/
#define REALLOC_SAFE(ptr, size, type) \
    do { \
        if (size == 0) \
            FREE_SAFE(ptr); \
        else { \
            type* p = realloc(ptr, (size) * sizeof(type)); \
            if (p == NULL) \
                EXIT_ERROR("Memory reallocation failure"); \
            ptr = p; \
        } \
    } while(0)


/* 
 * Macro which assigns the pointer to null after freeing. Useful
 * to avoid dangling pointers.

 *
 * @param ptr Name of pointer to free.
*/
#define FREE_SAFE(ptr) \
    do { \
        free(ptr); \
        ptr = NULL; \
    } while(0)

Next, let us define the header with macros used to generate declarations and definitions, respectively. Also, note that a benefit of this is to make the data type opaque.

// dynarr.h

#ifndef DYNARR_H
#define DYNARR_H

#include <stdlib.h>
#include "utils.h"

/* 
 * Macro which generates declarations of dynamic array functions, 
 * along with its opaque type declaration.
 * 
 * @param DYNARRAY_TYPE_NAME Name of the dynamic array type.
 * @param DYNARRAY_ITEM_TYPE Type of the item which the dynamic array 
 * shall contain.
*/
#define GEN_DYNARR_DECL(DYNARRAY_TYPE_NAME, DYNARRAY_ITEM_TYPE) \
    typedef struct DYNARRAY_TYPE_NAME DYNARRAY_TYPE_NAME; \
    DYNARRAY_TYPE_NAME* DYNARRAY_TYPE_NAME##_create (void); \
    void DYNARRAY_TYPE_NAME##_destroy (DYNARRAY_TYPE_NAME** d); \
    void DYNARRAY_TYPE_NAME##_append (DYNARRAY_TYPE_NAME* d, DYNARRAY_ITEM_TYPE item); \

/* 
 * Macro which generates definitions of dynamic array functions, 
 * along with its type definition.
 *
 * @param DYNARRAY_TYPE_NAME Name of the dynamic array type.
 * @param DYNARRAY_ITEM_TYPE Type of the item which the dynamic array 
 * shall contain.
*/
#define GEN_DYNARR_DEF(DYNARRAY_TYPE_NAME, DYNARRAY_ITEM_TYPE) \
    struct DYNARRAY_TYPE_NAME { \
        size_t capacity; \
        size_t size; \
        DYNARRAY_ITEM_TYPE* arr; \
    }; \
\
    DYNARRAY_TYPE_NAME* DYNARRAY_TYPE_NAME##_create (void) { \
        DYNARRAY_TYPE_NAME* d = MALLOC_SAFE(d, 1, DYNARRAY_TYPE_NAME); \
        d->capacity = 0; \
        d->size = 0; \
        d->arr = NULL; \
        return d; \
    } \
\
    void DYNARRAY_TYPE_NAME##_destroy (DYNARRAY_TYPE_NAME** d) { \
        if ((*d) == NULL) \
            return; \
        FREE_SAFE((*d)->arr); \
        FREE_SAFE((*d)); \
    } \
\
    void DYNARRAY_TYPE_NAME##_append (DYNARRAY_TYPE_NAME* d, DYNARRAY_ITEM_TYPE item) { \
        if (d->capacity == 0) {\
            d->capacity = 8; \
            REALLOC_SAFE(d->arr, d->capacity, DYNARRAY_ITEM_TYPE); \
        } \
        else if (d->size == d->capacity) { \
            size_t new_cap = 2 * d->capacity; \
            REALLOC_SAFE(d->arr, new_cap, DYNARRAY_ITEM_TYPE); \
            d->capacity = new_cap; \
        } \
        d->arr[d->size] = item; \
        d->size++; \
    }


#endif

Finally, let us actually use this. In the following header, we define two types of arrays:

// arrays.h

#ifndef ARRAYS_H
#define ARRAYS_H

#include "dynarr.h"

GEN_DYNARR_DECL(doublearr, double);

GEN_DYNARR_DECL(intarr, int);

#endif

Next, let us accompany the header with the following file:

// arrays.c

#include "arrays.h"


GEN_DYNARR_DEF(doublearr, double);

GEN_DYNARR_DEF(intarr, int);

Now, we can use it in a "dummy" main program:

// main.c

#include "arrays.h"


int main(void) {

    doublearr* a1 = doublearr_create();
    doublearr_append(a1, 1.1);
    doublearr_append(a1, 2.2);
    doublearr_destroy(&a1);

    intarr* a2 = intarr_create();
    intarr_append(a2, 1);
    intarr_append(a2, 2);
    intarr_destroy(&a2);

    return 0;
}

Of course, such an array is not yet useful, however, my main focus here is the concept.

\$\endgroup\$
3
  • \$\begingroup\$ @chux-ReinstateMonica Indeed, the magic number 8 is not necessary, hence I set it to 0. My initial idea was to have some small space allocated in advance, in order to avoid some additional checks when implementing the method to append an element to the array, however, this overhead is negligible. Also, I added some comments to the code. \$\endgroup\$ Mar 13 at 18:11
  • \$\begingroup\$ Additionally, I added a function to append an element to the array. Hopefully it is a bit clearer now how all of this should work. Also, note that if the capacity is zero, I set an initial capacity to 8 to save a few reallocations in the beginning. This is possibly not necessary, however, I am more interested in a general review of this concept, instead of concrete implementation details like this one. \$\endgroup\$ Mar 13 at 18:29
  • \$\begingroup\$ Best to put review goal "interested in a general review of this concept, instead of concrete implementation details like this one." in the post above. I see that conflicts a bit with "opinions ... about a certain approach to creating a "generic" dynamic array". IAC, code review is really about concrete examples. I too, also like to review general thoughts, but that is addition to specific code. \$\endgroup\$ Mar 13 at 21:35

2 Answers 2

2
\$\begingroup\$

Overall

A better than usual generic code.


Usage symmetry

Usage took the form of

namearr* x = namearr_create(); // creation
namearr_fun1(x, args);  // x not changed
namearr_fun2(&x, args); // x changed

As functions are added the asymmetry of needing to pass x or &x or assign becomes less clear.

I recommend a uniform style:

namearr_fun(&x, args); // x may or may not change - use `const`  to distinguish.

To approach RAII, perhaps 1 exception namearr* x = namearr_create();.


Keyword in middle?

Consider leading with keyword

// GEN_DYNARR_DECL(doublearr, double);
// GEN_DYNARR_DEF(doublearr, double);

DYNARR_GEN_DECL(doublearr, double);
DYNARR_GEN_DEF(doublearr, double);

// or simply
DYNARR_DECL(doublearr, double);
DYNARR_DEF(doublearr, double);

Increase uniformity in names

dynarr.h, DYNARRAY to dynarray.h, DYNARRAY or dynarr.h, DYNARR.


type not needed in *ALLOC_SAFE()

Example

//#define REALLOC_SAFE(ptr, size, type) \
... 
//            type* p = realloc(ptr, (size) * sizeof(type)); \

#define REALLOC_SAFE(ptr, size) \
... 
            void* p = realloc(ptr, (size) * sizeof *(ptr)); \

NULL ?

_destroy() sets the pointer to NULL, OK. Yet other functions like _append() do not check if the pointer is NULL. So I guess code is hoping for observable undefined behavior when an append happens after the destroy rather than defined behavior?


Magic 8

"I set an initial capacity to 8 to save a few reallocations in the beginning." assumes most arrays will be big. If most are small, then wasted space.

So save memory or time? One of those is finite.

I like new_size = old_size*2 + 1. Handles zero well and approach to SIZE_MAX.


Missing functions

Look forward to the size_t _size(), size_t _safe_set(index, data), type _safe_get(), int _apply(int fun(void * state, type), void * state), type _safe_sort(tbd) functions.


Suicide notes deserve stderr

// printf("Error in %s at line %d: %s - terminating program.\n",
//     __FILE__, __LINE__, msg);
fprintf(stderr, "Error in %s at line %d: \"%s\" - terminating program.\n", 
    __FILE__, __LINE__, msg);

Given an error that leads to exit, I like to put sentinels about the msg to add clarity to a potentially rarely tested message.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Thanks for the comments, all of them make perfect sense. Regarding the NULL? comment, this came to my mind, but I decided to omit the check, since I assumed the additional condition could affect performance in a negative manner. However, I did some testing now and I realized that the average execution time of the append function is very similar for both cases (tested appending 10^8 times to an array). I assume this should not come as a surprise - presumably gcc is clever enough to make the difference negligible. \$\endgroup\$ Mar 14 at 16:38
  • \$\begingroup\$ I find coding defensively saves my time in development as errors are more quickly detected and solved - the run-time cost overwhelmingly neglible. \$\endgroup\$ Mar 14 at 16:43
  • \$\begingroup\$ Oh, an additional point came to mind regarding the _destroy function: all of this is nice if the data type contained in the array is a type which itself does not contain dynamic memory allocated types. However, say I used a pointer to a struct as the underlying type, and say the struct itself contains a malloc'd array. Possibly a user-specified specific _destroy method could be "let to be defined", and if defined, the _destroy function could be made to call it. I need to look into this further. \$\endgroup\$ Mar 14 at 16:51
  • 1
    \$\begingroup\$ @JohnKimble "Possibly a user-specified specific _destroy method" ... and after awhile then you will re-invent C++. IMO, consider the bounds of your goal to prevent that. I recommend to stick to POD for now. \$\endgroup\$ Mar 14 at 16:58
2
\$\begingroup\$

This isn't really a code review, but are you aware that type-generic programming can be done with standard C _Generic? That comes with the huge advantage of being type safe, unlike the average dangerous function-like macro in C. Everything happens at compile-time. The only minor issue is that all supported types need to be known in advance.

Given two arrays of different types, we can apply the same function-like macro on both of them, like this:

int*  int_find  (size_t size, int array[size],  int  key);
char* char_find (size_t size, char array[size], char key):

#define array_find(size, array, key) \
  _Generic(&(array),                 \
    int(*)[]:  int_find,             \
    char(*)[]: char_find) (size, array, key)

The macro calls the type-specific functions, so all parameters must match.

We even can take it to the extreme by using an X-macro containing a list of all supported types, then have the code generated based on that:

#define SUPPORTED_TYPES(X)           \
  X(int)                             \
  X(char)                            \

#define find_decl(type) type* type##_find (size_t size, type array[size], type key);
SUPPORTED_TYPES(find_decl)

#define find_def(type)               \
type* type##_find (size_t size, type array[size], type key) \
{                                    \
  for(size_t i=0; i<size; i++)       \
  {                                  \
    if(array[i] == key)              \
      return &array[i];              \
  }                                  \
  return NULL;                       \
}
SUPPORTED_TYPES(find_def)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Minor: "macro calls the type-specific functions, so all parameters must match." --> "all" overstates. With size, array, key, only array needs to match closely as part of _Generic. size, key go thought the usual conversions. \$\endgroup\$ Mar 14 at 16:16
  • \$\begingroup\$ @Lundin I am aware of the existence of _Generic, however, I find my approach to be a bit more straightforward, at least with my level of knowledge. In any case, I will study the proposed code. \$\endgroup\$ Mar 14 at 20:01
  • \$\begingroup\$ @JohnKimble There's both better type safety and less layers in-between this way. Though if you wish to implement some C++ vector-like container, there's probably no sensible way to avoid dynamic memory and a struct. \$\endgroup\$
    – Lundin
    Mar 15 at 7:39

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.