4
\$\begingroup\$

Here is the interface of my generic dynamic array;

/* dynamic array interface */

#ifndef DA_HEADER
#define DA_HEADER

#include <stdlib.h> /* size_t */

/* creates a new dynamic array, with each element of "size" bytes */
void *danew(size_t unitsize);

/* returns pointer to element after the last element */
void *daend(void *arr);

/* appends new element after last element 
   return pointer to array head
*/
void *daappend(void *arr, const void *elem);


/*
    removes the last element and returns a pointer to it or null if empty
*/
void *dapop(void *arr);

/*
  frees the array
*/
void dafree(void *arr);

#endif /* DA_HEADER */

and this is the implementation of my generic dynamic array:

/* dynamic array implementation */

#include <string.h> /* memcpy */
#include <stdlib.h> /* free */
#include "xalloc.h" /* xmalloc, xrealloc */

struct dynamic_array {
        size_t cap;
        size_t len;
        size_t unitsize;
        char data[1];
};

#define DATAOFFSET ((unsigned long)(((struct dynamic_array*)0)->data))
#define DA_STRUCT(DATAPTR) (struct dynamic_array *)((char *)DATAPTR-DATAOFFSET)

void *danew(size_t unitsize)
{
        /* -1 because we already have one byte in struct */
        struct dynamic_array *da = xmalloc(sizeof(struct dynamic_array) +
                                          unitsize - 1);

        da->cap = 1;
        da->len = 0;
        da->unitsize = unitsize;

        return &(da->data);
}

static __inline struct dynamic_array *__dagrow(struct dynamic_array *da,
                                                            size_t size)
{
        while(size > da->cap)
                da->cap = 2*da->cap;

        /* -1 because we already have one byte in sizeof(struct) */
        return xrealloc(da, sizeof(struct dynamic_array) + da->unitsize*da->cap
                                                         - 1);
}

void *daappend(void *arr, const void *elem)
{
        struct dynamic_array *da = DA_STRUCT(arr);
        da = __dagrow(da, da->len + 1);
        memcpy(&da->data[da->unitsize * da->len++], elem, da->unitsize);
        return &da->data;
}

void *dapop(void *arr)
{
        struct dynamic_array *da = DA_STRUCT(arr);
        if(!da->len)
                return NULL;

        return &da->data[da->unitsize * --da->len];
}

void *daend(void *arr)
{
        struct dynamic_array *da = DA_STRUCT(arr);
        return &da->data[da->unitsize * da->len];
}

void dafree(void *arr)
{
        struct dynamic_array *da = DA_STRUCT(arr);
        free(da);
}

And this is the example usage:

#include <stdio.h>

#include "dynamic_array.h"

struct foo {
        int number;
        char *text;
};

int main()
{
        struct foo *myfoos = danew(sizeof(struct foo));
        struct foo *tmp_ptr;
        struct foo tmp;
        int i;
        int numbers[] = {1,2,3,4,5};
        char *texts[] = {"ali", "veli","osman","zekiye","mahmut"};

        for (i=0; i < 5; i++) {
                tmp.number = numbers[i];
                tmp.text   = texts[i];
                myfoos = daappend(myfoos, &tmp);
        }

        /* Random access */
        printf("3rd element is number: %d, text: %s", myfoos[2].number,
                                                      myfoos[2].text);

        printf("Accessing sequentially\n");
        /* Sequential access */
        for (tmp_ptr = myfoos; tmp_ptr != daend(myfoos); tmp_ptr++) {
                printf("current element: number: %d, text: %s\n", tmp_ptr->number,
                                                                tmp_ptr->text);
        }

        printf("Accessing LIFO\n");
        /* LIFO access */
        while((tmp_ptr = dapop(myfoos)))
                printf("current element number: %d, text: %s\n", tmp_ptr->number,
                                                               tmp_ptr->text);



        return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I've removed the generics tag. C doesn't support generics in the way other languages do and the tag isn't appropriate here. \$\endgroup\$ – nhgrif Mar 31 '15 at 12:00
3
\$\begingroup\$
  • An array is expected to provide random access. This structure looks more like LIFO stack.

  • xrealloc is highly non-portable (requires publib) and provides a dubious benefit at the cost of unconditional program termination on error. I highly recommend to stick to the standard, and let the client decide how to react.

\$\endgroup\$
  • \$\begingroup\$ Sorry, I guess the example was lacking, my implementation does provide random access. Edited the example in question. Moreover, I have my own version of xrealloc, didn't include it in question because I thought it was not relevant. \$\endgroup\$ – yasar Apr 1 '15 at 14:59
2
\$\begingroup\$
  1. naming da* + all lower case makes it hard to parse the difference between the prefix and the name of the function, instead either pick da_snake_case or daCamelCase.

  2. returning void* is not ideal instead create a opaque (incomplete) struct and just let the use pass pointers to that struct around:

    struct DynamicArray;
    
    DynamicArray* danew(size_t unitsize);
    
\$\endgroup\$
  • \$\begingroup\$ I am returning void* so that it can be casted into correct pointer type. I don't return the address of struct, but instead address of data so that pointer can be used like a regular array. \$\endgroup\$ – yasar Apr 1 '15 at 15:01
  • \$\begingroup\$ I see, the returned value doubles as the data pointer and the handle for your functions \$\endgroup\$ – ratchet freak Apr 1 '15 at 15:01

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.