Is ((size_t *)(vec))[-1] a violation of strict-aliasing?
The part of the Standard that would cause problems with this kind of code is not the "strict aliasing rule", but rather the specification of pointer arithmetic. The behavior of + and - on pointers is only defined in cases where the original pointer and the result would both point within or "just past" the "same array object", but the Standard is rather vague as to what "array object" is identified by a pointer that is cast from a pointer of another type.
Given e.g.
struct foo { int length; int dat[10]; };
void test(struct foo *p, int index)
{
if (index < p->length) p->dat[index]++;
return p->length;
}
the Standard does not require that an implementation allow for the possibility that index might be -1, p->dat-1 might yield the address of p->length, and consequently p->length might get incremented between the if and the return. The way subscripting is defined, however, the code would be equivalent to:
struct foo { int length; int dat[10]; };
void test(struct foo *p, int index)
{
int *pp = p->dat;
if (index < p->length) pp[index]++;
return p->length;
}
which would in turn be equivalent to:
struct foo { int length; int dat[10]; };
void test(struct foo *p, int index)
{
int *pp = (int*)&p->dat;
if (index < p->length) pp[index]++;
return p->length;
}
which starts to look very similar to what you're doing. An implementation which is suitable for low-level memory management should have no trouble processing such code usefully, but the Standard makes no attempt to forbid implementations which are specialized for tasks that don't involve low-level memory management from making assumptions that would render them unsuitable for tasks that do.
The way this library handles memory does not violate strict aliasing.
Although not mentioned by name in the C standard, strict aliasing basically means you can't access an object of one type as if it were an object of another type. These rules are spelled out in section 6.5, paragraphs 6 and 7:
6 The effective type of an object for an access to its stored value is the declared type of the object, if any. 87) If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value. If a value is copied into an object having no declared type using memcpy or memmove , or is copied as an array of character type, then the effective type of the modified object for that access and for subsequent accesses that do not modify the value is the effective type of the object from which the value is copied, if it has one. For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access.
7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types: 88)
- a type compatible with the effective type of the object,
- a qualified version of a type compatible with the effective type of the object,
- a type that is the signed or unsigned type corresponding to the effective type of the object,
- a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
- an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
- a character type.
87) Allocated objects have no declared type.
88) The intent of this list is to specify those circumstances in which an object may or may not be aliased.
For example, the following violates strict aliasing:
float x = 3.14;
unsigned int *i = (unsigned int *)&x;
printf("value of x: %f, representation of x: %08x\n", x, *i);
Because it tries to read a float as if it were an int.
The way the vector library works does not attempt to do this.
Let's take a look at how a vector is created by the library:
#define vector_grow(vec, count) \
do { \
if(!(vec)) { \
size_t *__p = malloc((count) * sizeof(*(vec)) + (sizeof(size_t) * 2)); \
assert(__p); \
(vec) = (void *)(&__p[2]); \
vector_set_capacity((vec), (count)); \
vector_set_size((vec), 0); \
} else { \
size_t *__p1 = &((size_t *)(vec))[-2]; \
size_t *__p2 = realloc(__p1, ((count) * sizeof(*(vec))+ (sizeof(size_t) * 2))); \
assert(__p2); \
(vec) = (void *)(&__p2[2]); \
vector_set_capacity((vec), (count)); \
} \
} while(0)
And suppose it is called like this:
int *v = NULL;
vector_grow(v, 10);
Because v is NULL, the if part of the macro is entered. It allocates space for 10 int plus 2 size_t. Immediately after the malloc the memory pointed to by __p has no type. Then it assigns to vec:
(vec) = (void *)(&__p[2]);
First, __p is defined as size_t *, so &__p[2] creates a pointer to a location after 2 objects of type size_t, casts that pointer to void *, and assigns it to vec. At this point, none of the allocated memory has a type yet. Next vector_set_capacity is called:
#define vector_set_capacity(vec, size) \
do { \
if(vec) { \
((size_t *)(vec))[-1] = (size); \
} \
} while(0)
This first casts vec to a size_t *, which is the original type of __p, and indexes element -1. This is valid because ((size_t *)(vec))[-1] is the same as __p[1]. Now a value of type size_t is written here, so the sizeof(size_t) bytes starting at from __p[1] contains an object of type size_t.
Similarly for vector_set_size:
#define vector_set_size(vec, size) \
do { \
if(vec) { \
((size_t *)(vec))[-2] = (size); \
} \
} while(0)
((size_t *)(vec))[-2] is the same as __p[0], and writing there also creates an object of type size_t.
So now the memory looks like this:
+--------+----------+---------+
| size_t | size_t | untyped |
+--------+----------+---------+
^ ^ ^
| | |
__p[0] __p[1] __p[2]==vec
Now when a user uses vector_push_back it does this:
vec[vector_size(vec)] = (value);
Which works the same as writing to any allocated memory space.
So because __p[0] and __p[1] are only accessed via a size_t *, there is not strict aliasing violation.
One thing that is a problem however is alignment. Memory returned from malloc is suitably aligned to handle data of any type. However, when creating different object in this allocated memory without using a struct those objects might not be properly aligned.
Let's take as an example a system where both int and size_t are 2 bytes in size, and assume a block of memory returned from malloc has an offset of 0. Now we create a vector of type long long, which is at least 8 bytes in size. After creating the vector, the first size_t sits at offset 0 and the second at offset 2. This is fine, because the offset of each is a multiple of the size. However, this means the vector data starts at offset 4. This is not a multiple of 8, so an object of type long long would be misaligned here.
The alignment issue can be resolved by creating a union of max_align_t and a struct of two size_t:
union vector_meta {
struct {
size_t size;
size_t capacity;
}
max_align_t align[2];
};
Then vec would be created like this:
union vector_meta *__p = malloc((count) * sizeof(*(vec)) + (sizeof(union vector_meta)));
assert(__p);
(vec) = (void *)(&__p[1]);
And you would access the size and capacity as:
((union vector_meta *)vec)[-1].size
((union vector_meta *)vec)[-1].capacity
This ensures that the memory after the metadata header is aligned properly for any use, and that the size and capacity fields can be accessed safely.
There isn't an aliasing problem, because the two cells at the beginning of the object are always accessed as size_t.
The library has an alignment problem, however. It assumes that a pointer obtained from malloc which is displaced by 2 * sizeof (size_t) bytes is still suitably aligned for any object type.
This is quite likely true on mainstream architectures, but it's not a standard-defined guarantee. A way to address that would be to define some constant that can be tweaked, like:
#define VEC_HEADER_SIZE (2*sizeof(size_t)) // redefine if insufficient for alignment
The two cell header can then obtained using (size_t *)((char *)(vec)-VEC_HEADER_SIZE), which can then be indexed using [0] and [1] to get at the two size_t cells.