5
\$\begingroup\$

I made my own dynamic array type using void pointers. I'd like to know what you think of my implementation. void pointers are nice but I fear they may be inefficient. The compiler cannot tell what you are doing because it has no size information. Either way i like the flexibility and the fact that i do not have to use macros as much. But what are your thoughts on this? I am still working on it and am still finding some minor bugs here and there. It has been a fun project to work on.

main.c

#include "array.h"
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

void log_int(void *p);

int main(int argc, char const *argv[])
{
    /* declare an integer array. */
    int *a = array_alloc(sizeof(*a), log_int);

    array_reserve(a, 32);

    /*
        append a list 1 - 9 
        fixed functions usually take in local arrays 
            or variadic macro arguments. 
    */
    array_give_fixed(a, 1, 2, 3, 4, 5, 6, 7, 8, 9);

    /* 
        array_take usually stores the values taken 
            from an array into a buffer.
        Passing NULL causes each elelemnt taken to have 
            its destructor called.
    */
    array_take(a, NULL, 3);

    int i[2];
    /* array_take returns the number of elements taken. */
    for(; array_take_fixed(a, i); )
    {
        fprintf(stdout, "%d ", i[0]);
        fprintf(stdout, "%d\n", i[1]);
    }
    
    /*
        array_free calls each elements destructor 
            and frees the array itself. 
    */
    array_free(a);
    return 0;
}

void log_int(void *p)
{
    int *i = p;
    fprintf(stderr, "integer popped %d\n", *i);
}

array.h

#ifndef ARRAY_H
#define ARRAY_H

#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#define COUNT(a) (sizeof(a) / sizeof *a)

typedef struct {
    void (*freeElem)(void *);
    size_t szElem;
    size_t ctElem;
    size_t cpElem;
} Array_Header;

void *array_alloc(size_t szElem, void (*freeElem)(void *));
void array_free_impl(void *a);
void *array_reserve_impl(void *a, size_t capacity);
void *array_push_impl(void *a, const void *elem);
void array_pop(void *a);
void *array_give_impl(void *a, const void *elems, size_t n);
size_t array_take(void *a, void *elems, size_t n);
size_t array_szElem(const void *a);
size_t array_ctElem(const void *a);
size_t array_cpElem(const void *a);

#define array_reserve(a, capacity) do { a = array_reserve_impl(a, capacity); } while(0)
#define array_push(a, elem) do { a = array_push_impl(a, elem); } while(0)
#define array_give(a, elems, n) do { a = array_give_impl(a, elems, n); } while(0)

#define array_give_fixed(p, ...) \
    do { \
        p = array_give_impl( \
            p, &(__typeof__(*p)[]){__VA_ARGS__}, \
            sizeof((__typeof__(*p)[]){__VA_ARGS__}) \
            / sizeof(__typeof__(*p))); \
    } while(0)

#define array_take_fixed(p, a) \
    array_take(p, a, sizeof(a) / sizeof(*a))

#define array_free(a) do { array_free_impl(a); a = NULL; } while(0)

#endif /* ARRAY_H */

array.c

#include "array.h"

void *array_alloc(size_t szElem, void (*freeElem)(void *))
{
    void *a = malloc(sizeof(Array_Header));
    Array_Header *header = a;
    header->freeElem = freeElem;
    header->szElem = szElem;
    header->ctElem = 0;
    header->cpElem = 0;
    return header + 1;
}

void array_free_impl(void *a)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    if(header->freeElem)
    {
        unsigned char *begin = a;
        unsigned char *end = begin + header->ctElem * header->szElem;
        for(; begin != end; begin += header->szElem)
        {
            header->freeElem(begin);
        }
    }
    free(header);
}

void *array_reserve_impl(void *a, size_t capacity)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    if(capacity > header->cpElem)
    {
        header->cpElem = capacity;
        header = realloc(header, sizeof(*header) + header->cpElem * header->szElem);
        a = header + 1;
        assert(header);
    }
    return header + 1;
}

void *array_push_impl(void *a, const void *elem)
{
    assert(a);
    assert(elem);
    Array_Header *header = (Array_Header *)a - 1;
    if(header->ctElem + 1 > header->cpElem)
    {
        header->cpElem = (header->cpElem + 1) * 2;
        header = realloc(header, sizeof(*header) + header->cpElem * header->szElem);
        a = header + 1;
        assert(header);
    }
    memcpy((unsigned char *)a + header->ctElem * header->szElem, elem, header->szElem);
    ++header->ctElem;
    return header + 1;
}

void array_pop(void *a)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    if(header->ctElem > 0)
    {
        --header->ctElem;
        if(header->freeElem)
        {
            unsigned char *p = (unsigned char *)a + header->ctElem * header->szElem;
            header->freeElem(p);
        }
    }
}

void *array_give_impl(void *a, const void *elems, size_t n)
{
    assert(a);
    assert(elems);
    Array_Header *header = (Array_Header *)a - 1;
    if(header->ctElem + n > header->cpElem)
    {
        header->cpElem = (header->cpElem + n) * 2;
        header = realloc(header, sizeof *header + header->cpElem * header->szElem);
        a = header + 1;
        assert(header);
    }
    memcpy((unsigned char *)a + header->ctElem * header->szElem, elems, n * header->szElem);
    header->ctElem += n;
    return header + 1;
}

size_t array_take(void *a, void *elems, size_t n)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    // if(header->ctElem >= n)
    n = n > header->ctElem ? header->ctElem : n;
    {
        header->ctElem -= n;
        if(elems)
        {
            memcpy(elems, (unsigned char *)a + header->ctElem * header->szElem, n * header->szElem);
        }
        else
        {
            unsigned char *begin = (unsigned char *)a + header->ctElem * header->szElem;
            unsigned char *end = begin + n * header->szElem;
            for(; begin != end; begin += header->szElem)
                header->freeElem(begin);
        }
    }
    return n;
}

size_t array_ctElem(const void *a)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    return header->ctElem;
}

size_t array_cpElem(const void *a)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    return header->cpElem;
}

size_t array_szElem(const void *a)
{
    assert(a);
    Array_Header *header = (Array_Header *)a - 1;
    return header->szElem;
}

```
\$\endgroup\$
3
  • \$\begingroup\$ Title should explain what the code is about, hope I understood it right in my edit. \$\endgroup\$
    – convert
    Feb 22, 2023 at 12:32
  • \$\begingroup\$ You seem to be mixing void pointers and macros in the same file; is there any reason why? \$\endgroup\$
    – Neil
    Feb 23, 2023 at 6:53
  • \$\begingroup\$ Interface seemed nice but its alright without all those macros. I have taken them out for now. \$\endgroup\$ Feb 23, 2023 at 7:32

1 Answer 1

8
\$\begingroup\$

Much feedback on the recent Array List C implementation applies here too.

() around macro parameters

Good practice to enclose a macro parameters with (), yet a still remain problematic. Example:

// #define array_push(a, elem) do { a = array_push_impl(a, elem); } while(0)
#define array_push(a, elem) do { a = array_push_impl((a), (elem)); } while(0)

Check allocation success

void *a = malloc(sizeof(Array_Header));
if (a == NULL) return NULL;  // add

.h file: only code necessary #include for the headers.

#include <assert.h> and perhaps others not needed in the .h file. Remove them.

Unnecessary struct

typedef struct { ... } Array_Header; not needed in the .h file. Move to the .c file.

Even better, re-define functions to use a pointer to Array_Header.


Array alignment

As OP wants to use header + 1 as the start of an array of any type, additional padding may be needed in Array_Header. Since *alloc() returns a pointer good for all alignments, to make certain header + 1 is also aligned for any type use a FAM of type max_align_t (which is an object type whose alignment is the greatest fundamental alignment).

typedef struct {
    void (*freeElem)(void *);
    size_t szElem;
    size_t ctElem;
    size_t cpElem;
    max_align_t a[]; // Add
} Array_Header;
\$\endgroup\$
10
  • \$\begingroup\$ Thanks for the feedback. So i should move most of the headers to the source file. I am not sure about re-defining the functions to take in a Array_Header* then I would not be able to use it like a regular array via sub scripting. About the first comment on the macro, I did it this way so i would not have to pass address of a but i guess i could make the macro pass the address for me. \$\endgroup\$ Feb 22, 2023 at 4:48
  • \$\begingroup\$ @lead Also: As is, header + 1 returns a pointer that may not meet alignment requirements of the type. More on that later. \$\endgroup\$ Feb 22, 2023 at 4:54
  • \$\begingroup\$ I think the formula for calculating padding between two structs a and b is. ``` x = sizeof each element in a y = sizeof first element in b then padding between a and b is p = y - x % y if x % y != 0 ``` \$\endgroup\$ Feb 22, 2023 at 6:12
  • \$\begingroup\$ @LeadVaxeral Rather than attempt to calculate the padding (yours is insufficient here), answer update. \$\endgroup\$ Feb 22, 2023 at 13:19
  • 2
    \$\begingroup\$ Yeah, would be much better without all the macros. \$\endgroup\$ Feb 22, 2023 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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