#Nasty Hack
I grant that it's a hack but I'd like to know of a platform where the following doesn't fix the alignment issue:
typedef struct {
size_t size;
size_t position;
size_t slots;
size_t padding;//NOT USED.
} Index;
The alignment issue is that although `malloc(.)` returns a universally aligned address, the `sizeof(Index)` may not be a multiple of the alignment of the element type.
So for example if `sizeof(size_t)==4` (i.e. typical 32-bit platform) it is likely that the `Index` in the OP will be such that `sizeof(Index)=12` but if the elements are say `double` requiring alignment of 8 the array will start at an address that is 4 mod 8 not 0 mod 8 as required. Operations on the elements as `double` 'in situ' will have undefined behaviour.
The reason my hack will work is that given there is no reason to pad `Index` then as I propose it `sizeof(Index)=4*sizeof(size_t)` giving 4 byte alignment off the bat.
If `sizeof(size_t)==2` (e.g. 16-bit platform) it will be 8 byte aligned.
If `sizeof(size_t)==4` (e.g. 32-bit platform) it will be 16 byte aligned.
If `sizeof(size_t)==8` (e.g. 64-bit platform) it will be 32 byte aligned.
So the 'breaking' case is a platform with a data type having an alignment greater than 4 times the word size. I know of none and think such a thing unlikely.
#Doing It Properly
If you want to do it all properly you need to work out the alignment of the stored type.
There is no guaranteed standard way to achieve that.
In C++11 you can use `alignof(.)` but this is a C challenge.
The most portable way (I know of) is:
#include <stddef.h> //Defines offsetof(.,.) macro.
#define alignment_of(type) offsetof(struct { char w;type v;},v)
Here's a skeleton of a fixed dynamic array.
I leave completion as an exercise.
Noteworthy features are:
1. Addresses alignment using best available practice (above).
2. Uses 1 for error and 0 for success. That is so ingrained it is beyond a matter of taste. See comments.
3. Engages in a bit of type punning to provide a bit of type-safety. `void*` parameters are asking for trouble.
4. Adds a bit of type-safety by size checking values pushed onto the array.
I would suggest 1 & 2 are mandatory but 3 & 4 are ideas to consider.
#include <stdint.h>//Defines MAX_SIZE
#include <stddef.h>//Defines the little known offsetof macro.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>//Defines memcpy(.,.,.). I know! I know!
//Defined as a macro so we can implement a bit of dynamic type safety.
#define da_push_back(DA,ELEM) da_push_back_(&(DA),&(ELEM),sizeof(ELEM))
//Best known practice for determining type alignment in C.
#define alignment_of(type) offsetof(struct { char w;type v;},v)
#define da_new(type,slots) da_new_(sizeof(type),slots,alignment_of(type),#type)
//Overwhelming convention is to use zero as 'success' and non-zero as 'error'.
//This allows the definition of diagnostic error codes and meaningful constructs
// like int error=da_thing(); if(error){ handle error... }
const int DA_SUCCESS=0;
const int DA_ERROR=1;
struct dynamic_struct;
typedef struct dynamic_struct* dynamic_array;
typedef struct {
size_t size;
size_t position;
size_t slots;
size_t offset;//This will be store the amount of dynamically calculated alignment padding.
const char* name;//Optional run-time type info. See stringizing # in macro.
} Index;
dynamic_array da_new_(size_t size,size_t slots,size_t align,const char* name){
//Get alignment for both elements & Index.
size_t falign=alignment_of(Index);
if(falign<align){
falign=align;
}
//offset will be the padding to go before Index.
const size_t over=sizeof(Index)%falign;
const size_t offset=over==0?0:falign-over;
//Allocate the padding the Index and the slots.
const size_t headersize=offset+sizeof(Index);
char*const block=malloc(headersize+size*slots);
if(block==NULL){
return NULL;//allocation failed - behave like malloc(.).
}
//Notice we are padding at the start.
//If we pad between Index and the elements we get in to a muddle.
//To find the index from the array we need the offset but it's in the Index!
//It's important to remember this offset so we can free the right point at the end.
Index* index=(Index*)(block+offset);
index->size=size;
index->position=0;
index->slots=slots;
index->offset=offset;
index->name=name;
return (dynamic_array)(block+headersize);
}
Index* da_get_index(dynamic_array da){
return ((Index*)da)-1;
}
const char* da_get_typename(dynamic_array da){
return da_get_index(da)->name;
}
size_t da_get_slots(dynamic_array da){
return da_get_index(da)->slots;
}
int da_delete(dynamic_array da){
//remember kids only render unto free(.) what malloc(.) has rendered unto thee.
//Or calloc(.) or realloc(.) obviously. But you get the point.
//We need to find the bottom of the block including any offset padding.
Index*const index=da_get_index(da);
const size_t offset=index->offset;
void*const block=((char*const)index)-offset;
free(block);
return DA_SUCCESS;
}
//We pass in sizecheck from the macro as a bit of type safety.
//Obviously this is no guarantee but will at least protect against some gross errors.
int da_push_back_(dynamic_array* da,const void*const element,const size_t sizecheck){
Index* index=da_get_index(*da);
const size_t size=index->size;
const size_t position=index->position;
const size_t slots=index->slots;
if(sizecheck!=size){
return DA_ERROR;//element not compatible with array...
}
if(position>=slots){
size_t newslots;
if(slots>SIZE_MAX/2){
if(slots==SIZE_MAX){
return DA_ERROR;//Exceeded size_t.
}
newslots=SIZE_MAX;
}else{
newslots=slots==0?1:slots*2;
}
const size_t offset=index->offset;
const size_t headersize=offset+sizeof(Index);
void*block=((char*)index)-offset;
char* newblock=realloc(block,headersize+newslots*size);
if(newblock==NULL){
return DA_ERROR;//Re-allocation failed.
}
*da=(dynamic_array)(newblock+headersize);
index=da_get_index(*da);
index->slots=newslots;
}
char* array=(char*)*da;
memcpy(array+position*size,element,size);
++(index->position);
return DA_SUCCESS;
}
void* da_get_array(dynamic_array da){
return da;
}
int main(void) {
int errors=0;
dynamic_array array=da_new(double,3);
double val=-2.718;
errors+=da_push_back(array,val);
double*access=da_get_array(array);
access[1]=1234.0;
access[2]=3.1415926535;
printf("type-name is \"%s\"\n",da_get_typename(array));
printf("%p %f %f %f\n",(void *)access,access[0],access[1],access[2]);
da_delete(array);
dynamic_array grow=da_new(int,3);
if(da_get_slots(grow)<3){
++errors;
}
int vint=99;
errors+=da_push_back(grow,vint);
vint=88;
errors+=da_push_back(grow,vint);
vint=77;
errors+=da_push_back(grow,vint);
//Now we make it grow...
vint=66;
errors+=da_push_back(grow,vint);
if(da_get_slots(grow)<4){
++errors;
}
int* ints=da_get_array(grow);
if(ints[0]!=99||ints[1]!=88||ints[2]!=77||ints[3]!=66){
++errors;
}
printf("%d %d %d %d\n",ints[0],ints[1],ints[2],ints[3]);
da_delete(grow);
dynamic_array longd=da_new(long double,10);
//Stringizing will 'normalise' the white-space in the typename.
//The source has multiple white-space characters
if(strcmp("long double",da_get_typename(longd))!=0){
++errors;
}
da_delete(longd);
//But it will consider aliases to be different.
//Notice how these two arrays have the same type but not type-name.
dynamic_array uinta=da_new(unsigned,10);
if(strcmp("unsigned",da_get_typename(uinta))!=0){
++errors;
}
dynamic_array uintb=da_new(unsigned int,10);
if(strcmp("unsigned int",da_get_typename(uintb))!=0){
++errors;
}
da_delete(uinta);
da_delete(uintb);
if(errors!=0){
printf("ERRORS - %d\n",errors);
}else{
printf("** SUCCESS **\n");
}
return errors==0?EXIT_SUCCESS:EXIT_FAILURE;
}