How to allocate in contiguous memory a structure containing 1 vector with user-defined size?

Question

How to allocate in contiguous memory a structure containing 1 vector with user-defined size?

I was thinking about how to answer this question and I came to the conclusion that I would need a data structure with:

the size of a set
a previously reported size vector

Would be something like the structure:

struct conjunto {
  int tamanho;
  int *conteudo;
};

In my first naive idea, I would allocate one memory region for the structure and then another for its contents:

struct conjunto* aloca_conjunto(int n) {
  struct conjunto *set = malloc(sizeof(struct conjunto));
  set.conteudo = n? malloc(sizeof(int)*n): NULL;
  set.tamanho = n;

  return set;
}

However, this double allocation it bothers for two reasons:

memory fragmentation
possible loss of reference locality

So my main doubt is

What would be the alternative to implement in a single allocation?

I know that even if, hypothetically, I could do this single allocation, accessing the element of the n - th position of the set would involve two dereferences: set->conteudo[n], but at least the pointer set->conteudo would be close to the desired memory region, maximizing the chance of a cache hit due to spatial locale.

An extra point of curiosity, to deepen the question:

and if I were to put several such elements in a contiguous region of memory (instead of a vector with the pointers), how would I rescue the n-th element of type struct conjunto from this region of memory?

3

c struct array memória alocação

Author: Maniero, 2019-04-04

Source

1 answers

score 1 · Accepted Answer

Is quite simple to do if you are using a compiler that conforms to at least the C99 standard, which in practice almost any situation. Use a Variable Array length (VLA). Just have to take care to allocate memory to the structure and data together. I believe this meets the requirements of the question.

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

typedef struct {
    size_t tamanho;
    int conteudo[];
} Conjunto;

int main(void) {
    Conjunto *dados = malloc(sizeof(Conjunto) + 10 * sizeof(int));
    dados->tamanho = 10;
    for (int i = 0; i < dados->tamanho; i++) dados->conteudo[i] = i;
    for (int i = 0; i < dados->tamanho; i++) printf("%d, ", dados->conteudo[i]);
}

See working on ideone. E no repl.it. also I put on GitHub for future reference .

If need to grow just make a realloc() updating the size with the part that calculates the space for the elements of the array.

If this is not possible by using a non-compliant compiler then for this case the solution of using only one array can be a good one leaving the 0 position reserved for the size. It is not perfect, but it should work well in almost any real case, just need to be some care.

The idea of auxiliary indices seems pretty bad and even worse that fragmentation.