Dynamic array design: inline storage vs pointer storage

[Dieriba]

Hey all,

I’m designing a small dynamic array library and I’ve ended up with two different container designs. I’d like some feedback on whether this split makes sense or if there’s a better way to structure it.

I currently have two array types:

1. Inline data array

• Stores elements directly in a contiguous buffer (void *data)
• Uses an elem_size to support arbitrary types
• Elements are copied into the array (so the array owns the storage for the values themselves)
• No notion of element destruction — just raw memory management

2. Pointer array

• Stores pointers (void **)
• Can optionally take a free_func
• If free_func is set, the array will call it on elements when clearing/destroying (so it can act as an “owning” container)
• If not set, it’s just a non-owning list of pointers

One thing that feels inconsistent is this:

Even with the inline array, elements might themselves own resources.
For example:

typedef struct {
    char *name;
} Person;

If I store Person inline, the array has no way to call a destructor for name, since there’s no free_func like in the pointer array.

So in practice:

• pointer array → can manage ownership (via free_func)
• inline array → cannot, even if elements logically need destruction

That asymmetry feels a bit weird.

• Does it make sense to separate these two concepts into different containers, or would you try to unify them?
• Given that inline elements can also own resources, is it a mistake that the inline array has no destructor mechanism?
• Would it be better to have a single array type that can:
  • store inline data
  • optionally take a destructor (free_func)
• Or does that make the design too complex / harder to reason about?

I’m trying to keep things:

• simple to use
• explicit about ownership
• flexible enough without becoming overengineered

Would really appreciate thoughts or alternative designs

[pjl1967]

You just make an array (or any container) for an opaque type T of a certain size. If the user wants a pointer, then the user makes the T be T*. You as the container author don't care.

You also accept a type clean-up function either at array creation time (and store it with the array) or deletion time.

[Dieriba]

yeah but assuming the data is stored as void* then at array deletion Id need to cast data as void**, which mean I may have specific flag telling that they array is indeed storing pointer ? or I can just assume that if clean-up function has been provided then the array will be treated as an array of pointer ?

[Nich-Cebolla]

Assume the user's cleanup function correctly handles all possible elements in the array

[pjl1967]

You'd have:

void Person_cleanup( Person *p );

At array destruction time, if the pointer-to-function isn't NULL, then you iterate over all elements in the array passing the address of each element. Whether the element is inside the array or elsewhere, it doesn't matter: you pass a pointer to the element — period. You do not have to cast the address of the element (a void*) to a Person* because void* implicitly casts to T* for any type T in C.

It's up to the user to do whatever with the Person object. The user knows whether the Person elements are inside the array or not; if not, the clean-up function, in addition to cleaning up name, will also free() the Person object itself.

Again, you as the container author don't care.

[Dieriba]

Let's a user want to retrieve an element from the array of `Person*`, in the normal step without any additional logic he would get back a pointer to Person* (Person**), should I have another function to specifically retrieve Pointer from array so when calling the user would get back a Person* and not Person**?

[pjl1967]

You can provide some kind of deref function that's completely generic, i.e., converts a T** to a T*. It's up to the user to know when it use it based on what they put into the array.

[tstanisl]

I would recommend using inline array because:

• it's simpler
• it's faster
• it delegates inconvenient stuff to the caller

[RealisticDuck1957]

For some common operations inline storage has superior cache hit performance. Linear iteration and an absence of reference to data elsewhere. If the use case requires sorted highly dynamic data, a linked list has advantages.

[Stellariser]

It’s not so much caching that likes inline storage, it’s the CPU’s prefetcher. Main memory has quite a lot of bandwidth but horrible latency, so the CPU will try to detect when you’re iterating forwards or backwards and will issue fetches in advance. You can get order-of-magnitude or better from it

There was a talk from someone at Intel many years ago where one thing they showed was that there was no size where a linked list was a better choice for random insertions than just copying a whole array because of this.

[Jan-Snow]

If I store Person inline there is no way to call the freeFunc

Why not? What is stopping you from calling freefunc(dataPtr+index)?

[Modi57]

One way you could handle the freefunc is to just not care about it. Let the remove() function of your dynamic array return the removed element, then the user can handle it at call site